3.10. Библиографические и исторические сведения

Оценка параметров составляет основной предмет математической статистики, весьма полно представленный во многих классических трудах, таких, как работы Хоула (1971) и Уилкса (1962). Обычно на практике применяются оценки по максимуму правдоподобия и байесовские оценки, причем в качестве последних часто использует­ся среднее значение апостериорного распределения р(|). Оценка по максимуму правдоподобия введена Р. А. Фишером, указавшим на многие ее замечательные свойства. К таким свойствам, в частно­сти, относится возможность избежать решения сложного вопроса выбора соответствующей априорной плотностиp().

Необдуманное применение лапласовского принципа недостаточ­ного основания для введения предположения о равномерных априорных распределениях, а также принятие предположения о случайности параметра, который всего-навсего неизвестен, столь сурово осуждались Фишером и Нейманом, что принципиальная основа байесовской оценки стала пользоваться дурной репутацией. В последние годы байесовским методам возвращена их былая респек­табельность, что отчасти объясняется той легкостью, с которой они связывают известными условиями неизвестные параметры.

С введением новых принципов, таких, как принцип максимума энтропии, разъяснились некоторые старые парадоксы (Джайнес, 1968). Более спорная, но тем не менее живительная поддержка была оказана «субъективистской» или «индивидуалистской» школой ста­тистиков, рассматривающей априорные распределения как средство выражения нашего представления о неизвестных параметрах (Сэ-видж, 1962). Так как в обычных условиях байесовские оценки и оценки по максимуму правдоподобия приводят примерно к одним и тем же результатам, то, если объем выборки достаточен, принци­пиальное различие этих оценок редко имеет важные последствия.

Байесовский подход к обучению при распознавании образов основан на предположении, что подходящим путем использования выборок при неизвестных условных плотностях является вычис­ление Р(ω_i|х,) (Браверман, 1962). Абрамсоном и Браверманом (1962) получено рекуррентное байесовское решение для обучения среднему в случае нормальной плотности, а Кин (1965) развил это решение на случай, когда неизвестны вектор среднего значения и ковариационная матрица. Байесовское обучение для ряда неста­ционарных и отличных от нормального случаев исследовалось Байснером (1968) и Ченом (1969). Как пример использования байе­совского обучения в самом общем смысле Лейниотисом (1970) уста­новлена связь между нормальным решением для случая многих переменных и хорошо известными результатами из других областей, а именно кальмановской фильтрацией в теории управления и корреля­ционно-оценочным детектированием в теории связи. Чином и Фу (1967) исследовалась сходимость этих оценок посредством сопостав­ления байесовского обучения и стохастической аппроксимации. Хорошее, сжатое изложение вопросов сходимости предложено Аоки (1965).

Получение простого выражения для апостериорной плотности р(|) обычно требует тщательного выбора априорной плотностиp(), так называемой «естественно сопряженной» плотности. Спреджинсом (1965) показано, что существенное упрощение при исполь­зовании воспроизводящих плотностей получается не за счет какого-либо особого свойства априорной плотности, а благодаря наличию простой достаточной статистики для p(х|). Введение достаточных статистик—еще один вклад Фишера. Строгое обоснование теоремы факторизации получено Леманом (1959), а анализ плотностей, приводящих к простым достаточным статистикам, проведен Дынкиным (1951),

Проблемы, связанные с увеличением размерности, ясно разоб­раны в статье Кенала и Чандрасекарана (1968), оказавшей влияние и на наше отношение к данному вопросу. Задачи эти не сводятся только к параметрическим методам; кстати, применение к ним непа­раметрических методов более строго будет изложено в гл. 4 и 5. Хотя задачами такого рода насыщены многие из практических про­ектов, в ранних изданиях им уделялось мало внимания, видимо, в связи со сложностью анализа. Однако следы этих задач можно ус­мотреть в частых замечаниях о возможном несоответствии или не­представительности имеющихся данных. Кенал и Рендал (1964), рассмотрев задачу оценки ковариационных матриц, пришли к оцен­ке, предложенной для частного случая Т. Дж Харли, и сочли ее весьма важной. Исчерпывающие исследования, касающиеся линей­ного разделения, и распространение их на другие виды разделяющих поверхностей опубликованы Ковером (1965), указавшим на возмож­ность их применения при обработке конструктивных выборок. Олейс (1966) рассмотрел задачу оценки, в которой переменные были рас­пределены нормально, а для неизвестных параметров использова­лись оценки по максимуму правдоподобия. На основании проведен­ного анализа им были обоснованы условия, при которых увеличение числа переменных может повлечь за собой рост ожидаемого квадра­тичного отклонения, он же пришел к мысли, что сходные явления возможны и в задачах классификации. К сожалению, в простых слу­чаях это явление места не имеет. Результаты, полученные Чандра-секараном (1971), показывают, что если признаки статистически независимы, то эффект этот не проявляется никогда. Таким образом, это явление относится к трудным для анализа зависимым случаям.

Хугс (1968) предложил усреднение по задачам и разрубил этот гордиев узел, объединив задачи классификации всех типов — с пол­ной зависимостью, полной независимостью и все промежуточные случаи. Так как усредненный по задачам уровень ошибки сначала

убывает до некоторого минимума, а затем возрастает с ростом числа признаков, то

можно прийти к заключению, что такое поведение типично при ограниченном числе выборок.

Нами приведены ре­зультаты для случая, когда два класса предполагаются одинаково

правдоподобными. Хугсом рассмотрены также уровни ошибок для случаев произвольных

априорных вероятностей, но разъяснение этих результатов слишком трудно, поскольку они

бывают иногда даже хуже, чем при учете только априорных вероятностей. Абенд и Харли

(1969) пришли к выводу, что это поведение обусловлено использованием оценок по максимуму

правдоподобия вместо байе­совских, а Чандрасекаран и Харли (1969) получили и исследовали

усредненный по задачам уровень ошибки для байесовского случая. При равенстве априорных

вероятностей и равенстве числа выборок в каждом классе результаты байесовских оценок и

оценок по мак­симуму правдоподобия оказываются одинаковыми.

Другим источником дискуссий в ранних работах по распозна­ванию образов явился вопрос об

оценке действия и сравнении раз­личных классификаторов. Частично это можно представить из

за­меток по распознаванию рукописных букв, опубликованных в июне 1960 г. и марте 1961 г. в

IRE Transactions on Electronic Computers. Общая процедура использования некоторых выборок

для построе­ния и резервирования запаса для контроля часто называется удер­жанием или H-

методом. Исследования Хайлимана (1962) указывают на необходимость чрезвычайно большого

числа пробных выборок, однако Кенал и Чандрасекаран (1968) показали, что анализ, по

су­ществу, и предназначен для случая многих выборок. Проведенное Лахенбруком и Миккей

(1968) исследование методом Монте-Карло явилось свидетельством превосходства метода

поштучного исклю­чения, который они назвали U-методом. Хотя при применении этого метода

и требуется n-кратное построение классификатора, они по­казали, что по крайней мере в случае

нормального распределения работа, связанная с повторным обращением ковариационных мат­

риц, может быть значительно уменьшена посредством применения тождества Бартлетта (см.

задачу 10). Введенные Фукунагой и Кесселем (1971) простые и точные формулы

свидетельствуют о том, что дополнительных расчетов в этом случае требуется совсем немного.

СПИСОК ЛИТЕРАТУРЫ

Абенд, Харли (Abend К., Harley Т. J., Jr.)

Comments 'On the mean accuracy of statistical pattern recognizers', IEEE Trails.

Info. Theory, IT-15, 420—421 (May 1969). Абрамсон, Браверман (Abramson N, Bravennan D.)

Learning to recognize patterns in a random environment, IRE Trails. Info.

Theory, IT-8, S58—S63 (September 1962). Аоки (Aoki M.)

On some convergence questions in Bayesian optimization problems, IEEE Trails.

Auto. Control, AC-10, 180—182 (April 1965).

Байснер (Beisner H. M.)

A recursive Bayesian approach to pattern recognition, Pattern Recognition, 1 13—31 (July 1968). Браверман (Braverman D.)

Learning filters for optimum pattern recognition, IRE Trails. Info. Theory, IT-8, 280—285 (July 1962). Джайнес (Jaynes E. T.)

Prior probabilities, IEEE Trans. Sys. Sci. Cyb., SSC-4, 227—241 (September 1968). Дынкин Е. Б.

Необходимые и достаточные статистики для семейства распределений вероятностей, УМН, 6:1, 68—90 (1951). Кенал, Рендал (Kanal L. N., Randall N. С.)

Recognition system design by statistical analysis, ACM, Proc. 19th Nat. Conf., pp. D2.5-1—D2.5-10 (August 1964). Кенал, Чандрасекаран (Kanal L. N., Chandrasekaran В.)

On dimensionality and sample size in statistical pattern classification, Proc. NEC, 24, 2—7 (1968); also in Pattern Recognition, 3, 225—234 (October 1971). Кин (Keehn D. G.)

A note on learning for gaussian properties, IEEE Trans. Info. Theory IT-11 126—132 (January 1965). Ковер (Cover Т. М.)

Geometrical and statistical properties of systems of linear inequalities with appli­cations in pattern recognition, IEEE Trans. Elec. Сотр., EC-14, 326—334 (June 1965). Лейниотис (Lainiotis D. G.)

Sequential structure and parameter-adaptive pattern recognition — part I:

supervised learning, IEEE Trans. Info. Theory, IT-16, 548—556 (September 1970). Лахенбрук, Миккей (Lachenbruch P. A., Mickey M. R.)

Estimation of error rates in discriminant analysis, Technometrics, 10, 1—11 (Feb­ruary 1968). Леман (Lehmann E. L.)

Testing Statistical Hypotheses (John Wiley, New York, 1959). Олейс (AllaisD. С.)

The problem of too many measurements in pattern recognition and prediction, IEEE Int. Con. Rec., Part 7, 124—130 (March 1966). Спреджинс (Spragins J.)

A note on the iterative application of Bayes' rule, IEEE Trans. Info. Theory, IT-11, 544—549 (October 1965). Сэвидж (Savage L. J.)

The Foundations of Statistical Inference (Methuen, London, 1962). Уилкс (Wilks S. S.)

Mathematical Statistics (John Wiley, New York, 1962). [Русский перевод:

Математическая статистика, М., «Наука», 1967.] Фукунага, Кессель (Pukunaga К., Kessell D. L.)

Estimation of classification error, IEEE Trans. Сотр., С-20, 1521—1527 (December 1971).

Хайлиман (Highleyman W. H.)

The design and analysis of pattern recognition experiments, Bell Si/stem Technical

Journal, 41, 723—744 (March 1962). Хоул (Hoel P. G.)

Introduction of Mathematical Statistics (Fourth Edition, John Wilev, New

York, 1971). Xyrc (Hughes G. F.)

On the mean accuracy of statistical pattern recognizers, IEEE Trans. Info.

Theory, IT-14, 55—63 (January 1968).

Чандрасекаран (Chandrasekaran В.)

Independence of measurements and the mean recognition accuracy, IEEE Trans.

Info. Theory, IT-17, 452—456 (July 1971). Чандрасскаран, Харли (Chandrasekaran В., Harley Т. J., Jr.)

Comments 'On the mean accuracy of statistical pattern recognizers', IEEE

Trans. Info. Theory, IT-15, 421—423 (May 1969). Чен (Chen С. Н.)

A theory of Bayesian learning systems, IEEE Trans. Sys. Sci. Cyb., SSC-5,

30—37 (January 1969). Чин, Фу (Chien Y. Т., Fu К. S.)

On Bayesian learning and stochastic approximation, IEEE Trans. Sys. Sci. Cyb.,

SSC-3, 28—38 (June 1967).

Задачи

1. Пусть величина х распределена по экспоненциальному закону:

а) Изобразите зависимость p(x|) от х для постоянного значения параметра .

б) Изобразите зависимость p(x|) от , >0, для постоянного значениях.

в) Предположим, что независимо получено n выборок x₁, . . ., х_n в соответствии с p(x|). Покажите, что оценка по максимуму правдоподобия для определяется выражением

2. Пусть величина х распределена равномерно:

а) Изобразите зависимость p(x₁|) от для некоторого произвольного зна­чения x₁.

б) Предположим, что независимо получено п выборок в соответствии с p(x|). Покажите, что оценка по максимуму правдоподобия для есть.

3. Пусть выборки получаются последовательным независимым выбором со­стояний природы с неизвестной вероятностьюР(). Пусть z_ik =1, если со­стояние природы для k-й выборки есть , иz_ik =0 в противном случае. Пока­жите, что

и что оценка по максимуму правдоподобия для Р () есть

4. Пусть х есть бинарный (О, 1) вектор с многомерным распределением Бернулли

где = (₁, . . ., _d) — неизвестный параметрический вектор, а _i- — вероятность того, что x_i=1. Покажите, что оценка по максимуму правдоподобия для есть

5. Пусть , где известно, а неизвестна. Покажите, что оценка по максимуму правдоподобия для определяется выражением

,

последовательно выполняя следующие действия:

а) Докажите матричное тождество a^tAa=tr{Aaa^t}, где след trA есть сумма диагональных элементов матрицы А.

б) Покажите, что функцию правдоподобия можно записать в виде

в) Полагая, что A=^-1и, . . ., суть собственные значения матрицыА, покажите, что это приводит к выражению

г) Завершите доказательство, показав, что максимум правдоподобия дости­гается при = . . .==1.

6. Предположим, что , где — общая ковариацион­ная матрица для всех с классов. Пусть п выборок x₁, . . ., х_n извлекаются обычным путем, и пусть l₁, . . ., l_n— их индексы, т. е. l_k=i, если состояние природы для х_k было .

а) Покажите, что

б) Используя результаты для выборок из одного нормально распределенного семейства, покажите, что оценки по максимуму правдоподобия параметров и

определяются выражениями

и

7. Рассмотрите задачу обучения при восстановлении среднего значения одно­мерного нормального распределения. Пусть n=/есть догматизм, и пред­ставим, чтообразуется посредством усредненияn₀ вымышленных выборок ,k=—n₀ +l, . . ., 0. Покажите, что выражения (23) и (24) для , идают

и

Воспользуйтесь полученным результатом для интерпретации априорной плотности .

8. Докажите матричное тождество

где A и B — невырожденные матрицы одного порядка. Воспользуйтесь получен­ным результатом, чтобы доказать, что соотношения (31) и (32) на самом деле сле­дуют из (28) и (29).

9. Пусть выборочное среднее m_n и выборочная ковариационная матрица С_n для множества п выборок x₁, . . ., х_n определяются выражениями

и

Покажите, что влияние на эти величины добавления новой выборки x_n+1 можно выразить рекуррентными формулами

и

10. Выражения из задачи 9 позволяют вводить поправки в оценки ковариа­ционных матриц. Однако нередко представляет интерег обратная ковариацион­ная матрица, а се обращение отнимает много времени. Доказав матричное тождество

и используя результаты, полученные в задаче 9, покажите, что

11. В данной задаче ставится цель получить байесовский классификатор для случая многомерного распределения Бернулли. Как всегда, мы имеем дело с каж­дым классом в отдельности, истолковывая Р(х|) как среднееP(x|, ). Пусть условная вероятность для данного класса определяется выражением

и пусть есть множествоп выборок x₁, . . ., х_n независимо извлекаемых в соот­ветствии с этим вероятностным распределением.

а) Полагая, что s=(s₁ , .. ., s_d)^t есть сумма п выборок, покажите, что

б) Полагая, что распределение равномерно, с учетом тождества

покажите, что

Изобразите эту плотность для случая d=1, n=1 и двух значений получаемых вероятностей для s₁.

в) Посредством интегрирования по произведенияР (х|)p (|) получите требуемую условную вероятность

Если считать, что Р(х|) получается подстановкой оценки в Р(х|) на место , то что является эффективной байесовской оценкой для ?

12. Исходя из данных табл. 3.1, покажите, что оценка по максимуму правдо­подобия для параметра при распределении Релея определяется выражением

13. Исходя из данных табл. 3.1, покажите, что оценка по максимуму прав­доподобия для параметра при распределении Максвелла определяется выра­жением

14. Исходя из данных табл. 3.1, покажите, что оценка по максимуму правдо­подобия для параметра при полиномиальном распределении определяется вы­ражением

где вектор s=(s₁ , .. ., s_d)^t —среднее для п выборок x₁, . . ., х_n.

15. Рассмотрим случай двух классов, описанный в задаче 16 гл. 2, когда известно, что вероятность ошибки стремится к нулю при стремлении размерности d к бесконечности.

а) Предположим, что извлекается одна выборка х=(x₁, . . ., х_d)^t из класса 1. Покажите, что оценка по максимуму правдоподобия для р определяется выра­жением

б) Опишите поведение при стремлении d к бесконечности. Объясните, по­чему, если допустить беспредельное увеличение числа признаков, можно получить безошибочный классификатор даже при наличии только одной выборки всего из одного класса.

1В литературе по математической статистике выборка объемаnсоответствует наборуnтаких представителей. Считая каждый из представителей выборкой, мы следуем практике, принятой в технической литературе. Статистикам следо­вало бы каждую из рассматриваемых здесь выборок считать выборкой единичного объема.

2Некоторые авторы предпочитают запись видаp(x|ω_j),так как, строго говоря, обозначениеp(x|ω_j, θ_j).подразумевает, что θ_j,есть случайная переменная. Мы пренебрежем этим различием в обозначениях, и будем считать θ_j,обычным пара­метром при анализе по максимуму правдоподобия и случайной переменной при байесовском анализе.

3Иногда это и не имеет места, например когда все выборки входят в одну и ту же ковариационную матрицу. Что следует делать в таких случаях, показано в задаче 6.

4 Андерсон, Введение в многомерный статистический анализ, гл. 3, М., Физматгиз, 1963.

5Заметим, что в данном уравнении каждая вероятность и функция плотности условны по отношению к множеству выборок. То обстоятельство, что данное равнение и есть просто байесовское правило, становится более ясным, если опустить общие величины, входящие в виде условий. Читатель может найти этот прием слезным при интерпретации сходных уравнений в других местах данной главы.

6На протяжении данной главы областью интегрирования для всех интегра­лов будет все упомянутое пространство.

7Напомним, что для простоты мы не различаем классы, но все выборки здесь принадлежат одному и тому же классу, скажем , так что p(x|) на деле есть p(x|, ).

8При необходимости различать функцию и ее значение будем использовать запись s=.

9В математической статистике есть соответствующее нашим требованиям понятие минимальной достаточной статистики. Однако и минимальная достаточ­ная статистика не представляет значительного интереса, если не упрощает вы­числений.

10Если пространство параметров конечно, мы в самом деле можем считать распределениер()равномерным. Хотя в случае непрерывного пространства параметров равномерное распределение невозможно, такое приближение часто и здесь оказывается удовлетворительным.

11Если быть более точным, то необходимо предположить, что. Когда в литературе встречается утверждение, что «признаки предполагаются статистически независимыми», то почти всегда под этим подра­зумевается, что они независимы внутри класса.

12Мы еще вернемся к вопросам уменьшения размерности в гл. 4и 6.

13Говорят, что точки в d-мерномпространстве находятся вобщем расположе­нии,если никакое из подмножеств, содержащих (d+l) точек, не попадает в одно(d—1)-мерное подпространство.

14В ранних работах по распознаванию образов, когда эксперименты нередко проводились с весьма малым количеством выборок, при проектировании и испы таниях классификатора нередко использовались одни и те же данные. Такой неверный подход обычно назывался «испытанием по тренировочным данным». Родственная, хотя и менее очевидная задача соответствует случаю, когда класси­фикатор подвергается многим последовательным усовершенствованиям, прово­димым на основании повторных испытаний при одних и тех же эксперименталь­ных данных. Такого вида «испытание по тренировочным данным» часто кажется привлекательным до получения новых пробных выборок.

15Чтобы это предположение оказалось верным, состояния природы должны выбираться случайно. В результате в задачах со многими классами некоторые классы могут вообще не быть представлены. Чтобы обойти эту неприятность, явно вызванную малым числом выборок, обычно принято делать число пробных выборок для каждого класса хотя бы грубо соответствующим априорным вероят­ностям. При этом оценка уровня ошибок уточняется, однако точный анализ усложняется.