Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 44
Текст из файла (страница 44)
Вывод соответствующих уравнений для оценки по максимуму правдоподобия для этого случая рассматривается в задачах 5 и 6. б.4.4. ПРОСТйй ПРИВ««ИЖВННйй ПРОЦВ»«УРй Из различных способов, которые используются для упрощения вычисления и ускорения сходимости, мы кратко рассмотрим один элементарный приближенный метод. Из соотношения (17) ясно, что вероятность Р (ю;'1хэ, В,) велика, когда квадрат махалонобисова расстояния (х„— (ле)г Х-,»(хь — «л,) мал, Предположим, что мы просто вычислЯем кваДРат евклидова РасстоЯниЯ 11ха — (а,)Р и находим среднее (ь„, ближайшее к хэ, и аппроксимируем Р(в,~ха, Ое) как ( 1 при (=пг, ( 0 в противном случае. Тогда итеративное применение формулы (15) приводит к следую- щей процедуре ') нахождения 1а„ ..., зь,: Процедура: Базовые Изоданные 1.
Выбираем некоторые начальные значения для средних (л! у 1ас. Цикл: 2. Классифицируем п выборок, разбивая их на классы по ближайшим средним. 3. Вновь вычисляем средние как средние значения выборок в своем классе. 4. Если какое-нибудь среднее изменило значение, переходим к Циклу; иначе останов. Это типичные для некоторого класса процедуры, известные как процедуры группировки (кластер-процедуры). Позже мы поместим ее в класс итерационных оптимизационных процедур, поскольку средние имеют тенденцию изменяться так, чтобы минимизировать функцию критерия квадратичной ошибки.
В настоящий момент мы рассматриваем это просто как приближенный способ получения оценки по максимуму правдоподобия для средних. Полученные значения можно принять за ответ или использовать как начальные точки для более точных вычислений, ') В этой главе мы назовем и опишем различные итерационные процедуры как программы для ЭВМ, Все эти процедуры действительно были запрограммиро.
ваны, часто с различными дополнительными элементами, такими, как разрешение неоднозначности, избежание состояний «ловушки» и обеспечения особых условий окончания работы. Таким образом, мы включили слово «базовые» в название, чтобы подчеркнуть, что наш интерес ограничивается только объяснением основных понятий. Гл. б. Обучение без учителя и еруппирсена Интересно посмотреть, как эта процедура ведет себя на примере данных из табл. 6.1. Рис. 6,4 показывает последовательность значений длЯ 1е, и 1ее, полУченных длЯ нескольких Различных начальных точек. Так как взаимная замена р, и р, просто взаимозаменяет метки, присвоенные данным, траектория симметрична относительно линии р,=р,, Траектория приводит или к точке р,,= — 2,176, н Ре Рис.
6ли Траектории дпя процедуры. Базовые изоданные, р,=1,684, или к ее отображению. Это близко к решению, найденному методом максимума правдоподобия (р,= — 2,130 и ре=1,668), н траектории в общем сходны с траекториями, показанными на рис. 6.3. В общем случае, когда пересечение между плотностями компонент мало, можно ожидать, что метод максимального правдоподобия и процедура Изоданные дадут похожие результаты. 6,5. БАЙЕСОВСКОЕ ОБУЧЕНИЕ БЕЗ УЧИТЕЛЯ 6ДЛ. БАйЕСОВСКИй КЛАССИФИКАТОР Методы максимума правдоподобия не рассматривают вектор параметров Б как случайный — он просто неизвестный.
Предварительное знание о возможных значениях 9 необязательно, хотя на б.б. Байеооеояое обучение бео учителя практике такое знание можно использовать для выбора хорошей начальной точки при процедуре подьема на вершину. В этом раз. деле мы используем байесовский подход к обучению без учителя. Предположим, что Π— случайная величина с известным априорным распределением р(0), и будем использовать выборки для вычисления апостериорной плотности р(01Я).
Весьма интересно, что такой анализ в основном будет подобен анализу байесовского обучения с учителем, что указывает на большое формальное сходство задач. Начнем с четкого определения основных предположений. Пред. полагаем, что 1. Число классов известно. 2. Априорные вероятности Р(ат) для каждого класса известны, )=1, ..., с. 3. Вид условных по классу плотностей р(х)сот, 0,) известен, )=1,..., с, ио вектор параметров 6=(8„..., 0,) неизвестен. 4. Часть знаний о 0 заключена в известной априорной плотно. сти р (6).
5. Остальная часть знаний о О содержится в множестве Я" из и выборок х„..., х„, извлеченных независимо из смеси с плотностью с р (х)О) = ~~.", р (х ~ а~, 8,) Р (а,). (1) После этого мы могли бы непосредственно начать вычисление р(01Я"). Однако давайте сначала посмотрим, как эта плотность используется для определения байесовского классификатора. Предположим, что состояние природы выбирается с вероятностью Р(а~) и вектор признаков х выбран в соответствии с вероятностным вако.
ном р(х(аь 8,). Чтобы вывести байесовский классификатор, мы должны использовать всю имеющуюся информацию для вычисления апостериорной вероятности Р(а,)х). Покажем явно роль выборок, записав это в виде Р(а,)х, Я'). По правилу Вайеса Р ( ~ я) Р(х(во Я') Р(~~1 Я") с ~~~ р(х)вр Я') Р(вт)Я) !=1 Так как выбор состояния природы ае был сделан независимо от ранее полученных выборок: Р(а;)Я)=Р (ае), то мы получим р(х(вь Я) Р (вй (18) ~~ Р(х)вр Я') Р (в)) )=! Введем вектор неизвестных параметров, написав р (х )ав Я ) = ~ р (х, 0 ~ ае, Я") е(8 ) р (х ~ О, ап Я") р (О ~ ап Я') е(0. Гл.
6. Оуучение аее учителя и груняираеяа Поскольку сам х ие зависит от выборок, то р(х(0, аг, Я)= =р(х(аь О!). Аналогично, так как знание состояния природы при выбранном х нам ничего не говорит о распределении О, имеем р(8!аь .я )=р(0(Я"). Таким образом, получаем р (х ! ао .й") = ~ р (х ( ао 8!) р (8 ) .й") е(0. (19) То есть наша наилучшая оценка для р(х(а!) получена усреднением р(х(аг, О!) по йь Хорошая это или плохая оценка, зависит от природы р(0!.й"), и мы должны, наконец, заняться этой плотностью.
6.5.2. ОБУЧЕНИЕ ВЕКТОРУ ПАРАМЕТРОВ Используя правило Байеса, можем написать р(й(в) (е) ~ р(,У:!в) р(е)ае где независимость выборок приводит к я р(Я" /О) =Д р(х ~8). (20) (21) С другой стороны, обозначив через й н множество и выборок, мы можем записать соотношение (20) в рекуррентной форме (22) р (8 ~ Я'я) ~ р( „(е) р(в(.й'"- ) лв Это основные соотношения для байесовского обучения без учителя. Уравнение (20) подчеркивает связь между байесовским решением и решением по максимуму правдоподобия. Если р(0) существенно равномерна в области, где имеется пик у р(й 10), то у р(8! В) имеется пик в том же самом месте.
Если имеется только один существенный пик при 0=6 и этот пик очень острый, то соотношения (19) и (18) дают р(х(а„.й) жр(х! аг, 8), реа !х й.!ж р(х(аь йДР(ай ~ч~~ ~р (я ( ар вг) Р (а г) ! ! То есть эти условия оправдывают использование оценки по максимуму правдоподобия, используя ее в качестве истинного значения 0 при создании байесовского классификатора. Естественно, если плотность р(0) была получена при обучении с учителем с использованием большого множества помеченных вы- 227 6.5. Байесовское оау ение бвз учивеля борок, она будет далека от равномерной и это решающим образом повлияет на р(ОьХ"), когда п мало.
Соотношение (22) показывает, как прн наблюдении дополнительных непомеченных выборок изменяется наше мнение об истинном значении 0 и особое значение приобретают идеи модернизации и обучения. Если плотность) смеси р(х)0) идентифицируема, то с каждой дополнительной выборкой р (6(Х") становится все более острой, и при достаточно общих условиях можно показать, что Р(0(Я'") сходится (по вероятности) к дельта. функции Дирака с центром в истинном значении 8. Таким образом, даже если мы не знаем класса выборок, идентифицируемость дает нам возможность узнать вектор неизвестных параметров 8 и вместе с этим узнать плотности компонент р(харви 0).
Тогда это и есть формальное байесовское решение задачи обучения без учителя. В ретроспективе тот факт, что обучение без учителя параметрам плотности смеси тождественно обучению с учителем параметрам плотности компонент, не является удивительным.
Действительно, если плотность компонент сама по себе является смесью, то тогда действительно не будет существенной разницы между этими двумя задачами. Однако существуют значительные различия между обучениями с учителем и без учителя. Одно из главных различий касается вопроса идентифицируемости. При обучении с учителем отсутствие идентифицируемости просто означает, что вместо получения единственного вектора параметров мы получаем эквивалентный класс векторов параметров. Однако, поскольку все это приводит к той же плотности компонент, отсутствие идентифицируемости н4'представляет теоретических трудностей. При обучении без учителя отсутствие идентифицируемостн представляет более серьезные трудности.
Когда 0 нельзя определить единственным образом, смесь нельзя разложить на ее истинные компоненты. Таким образом, в то время как р (х(Я' ) может все еще сходиться к р (х), величина р(х~аь Х"), описываемая выражением (19), в общем не сойдется к р (х)а;), т. е. существует теоретический барьер в обучении. Другая серьезная проблема для обучения без учителя — это вычислительная сложность. При обучении с учителем возможность нахождения достаточной статистики дает возможность получить решения, которые решаются как аналитическими, так и численными методами.
При обучении без учителя нельзя забывать, что выборки получены из плотности смеси е р(х(О) = Д Р (х(вю 07) Р(а ), и поэтому остается мало надежды найти простые точные решения для р (О(.й'). Такие решения связаны с существованием простой достаточной статистики, и теорема факторизации требует возможности Ге. б. Обучение бее учителя и груллиуееяи представления р(Х(9) следующим образом: р(.9 !О) =д(з, О) й(Х).
Но по формулам (21) и (! ) имеем л г а Р(Х(0)=Д ~~ Р(хе(а, О.) Р(а) Таким образом, р(Х18) есть сумма сл произведений плотностей компонент. Каждое слагаемое суммы можно интерпретировать как общую вероятность получения выборок х„..., х„с определенными метками, причем сумма охватывает все возможные способы пометки выборок. Ясно, что зто приводит к общей смеси О и всех х, и нельзя ожидать простой факторизации. Исключением является случай, когда плотности компонент не перекрываются, так что, как только в 9 изменяется один член, плотность смеси не равна нулю.
В этом случае р(Я")О) есть произведение и ненулевых членов и может обладать простой достаточной статистикой. Однако, поскольку здесь допускается возможность определения класса любой выборки, это сводит задачу к обучению с учителем и, таким образом, не является существенным исключением. Лругой способ сравнения обучения с учителем и без учителя состоит в подстановке плотности смеси р(х„(8) в (22) и получении с р (х» ( вр Оу) Р (ау) Р(8(Х») !=' Р (8) Я"-!). (23) ~», '~ р(х„(ар ОД Р (ау) р(О(Я'»-!) бО Рл 1 Если мы рассматриваем особый случай, где Р(а,) 1, а все остальные априорные вероятности равны нулю, соответствующий случаю обучения с учителем, в котором все выборки из класса 1, то формула (23) упрощается до 9») р(х !а>, О!) Р(о( 9'л !) (24) )е р(х„~ аив,)р(О ~.9"-!) бв Сравним уравнения (23) и (24), чтобы увидеть, как дополнительная выборка изменяет нашу оценку О. В каждом случае мы можем пренебречь знаменателем, который не зависит от 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
