Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 42
Текст из файла (страница 42)
Чтп ПрОНСХОдпт В СЛуЧаЕ ОтрИцатЕЛЬНОГО 51 12. Пусть (уп ..., у„) — конечное множество линейно разделяемых выборок. Предложите процедуру, с помощью которой разделяющий вектор может быть получен через конечное чнсло шагов. (Указание: рассмотрите весовые векторы, компонентами которых являются целые числа.) 13. Рассмотрим функцию критерия ,(ч (а) = ~ (а'у — Ь)з, уеЭ где Э(а) — множество выборок, для которых агу<6. Пусть у, — единственная выборка в Э(ва).
Покажите, что р/ (аа)=2(аау,— Ь)у» а матрица вторых част. д ных производных определяегся выражением !)=2у,уг. Используя этот результат, покажите, что если в выражение (8) подставить оптимальное значение рю то ал- горитм градиентного спуска примет вид Ь вЂ” агу, аа„= аз +-~ — )(э' у„. 14. Покажите, что прн использовании метода нанменьшнх квадратов масштабный коэффициент сг в решении, соответствующем разделяющей функции Фишера (п.
5.8.2), определяется выражением ! сев !+ — '' (ш,— шз)!ай~ (шэ — шэ) и 15. Обобщите результаты п, 5.8,3 для того, чтобы показать, что вектор в, который минимизирует функцию критерия .(;(а) = ~ (а'у — ()ьэг — Хы))з+ ~ (а'у — (),1з — Лзз))з, хеЭ~ у е Ээ обеспечивает асимптотически наилучшее в смысле минимума среднеквадратичной ошибка приблнженне для байесовской разделяющей функция (ьы — )чар(ы,(х)— ()чз Хзз)Р (юз!Х) 210 Га. Б. Линейные разделяющие функции 16. Рассмотрим функцию критерия Хи(а)=Е((аеу(х) — г)т) н байесовскую разделяющую функцию ир(х).
а) Покажите, что 3 = Е ((ыгУ вЂ” Дь)Ч вЂ” 2Е Ка'У вЂ” Е,) (г — Ие')1+ Е ((г — й' )з) б) Используя тот факт, что условное среднее значение г равно яз(х), покажите, что вектор а, минимизирующий е'и, одновременно доставляет минимум функционалу Е((вту — йс)з). !7. Скалярный аналог отыашеыня 11~+а=йа~+уауа, используемого и методе стохастической аппроксимации, имеет вид ра+г=р аа+уа. Покажите, что рещеяие в замкнутой форме для данного уравнения имеет вид р, е',— 2+рг ~к~~ уг г=! Приняв р,)0 и 0(а<уг <Ь(еь, покажыте, почему указанная последователь. ность козффициентов удовлетворяет соотношениям Хра — + оо И ХР3а — Г.
( оо. 18. Задача линейного программирования, сформулированная в и. 5.10,2, включала в себя минимизацию единственной искусственной переменной Г прн ограничениях азу;+Г)Ьг и 1,иб. Покажите, что результирующий весовой вектор минимизирует фуйкцию критерия ,ге(а) = игах [Ьг — агу,). ау <Ьг 19. Предложите обобщение на случай многих классов метода потенциальных функций, включающего е разделяющих функций; предаожите итеративную процедуру горрзкции ошибок для определения разделяющих функций. Глава 6 ОБУЧЕНИЕ БЕЗ УЧИТЕЛЯ И ГРУППИРОВКА егк вввдкник До сих пор мы предполагали, что обучающие выборки, используемые для создания классификатора, были помечены, чтобы показать, к какой категории они принадлежат.
Процедуры, использующие помеченные выборки, называются процедурами с учителем. Теперь рассмотрим процедуры без учителя, использующие непомеченные выборки. То есть мы посмотрим, что можно делать, имея набор выборок без указания нх классификации. Возникает вопрос: целесообразна ли такая малообещающая задача и возможно ли в принципе обучить чему-либо по непомеченным выборкам. Имеются три основные причины, по которым мы интересуемся процедурами без учителя. Во-первых, сбор и пометка большого количества выборочных образов требуют много средств и времени.
Если классификатор можно в первом приближении создать на небольшом помеченном наборе выборок и после этого его «настроить> на использование без учителя на большом непомеченном наборе, мы сэкономим много труда н времени. Во-вторых, во многих практических задачах характеристики образов медленно изменяются во времени. Если такие изменения можно проследить классификатором, работающим в режиме обучения без учителя, это позволяет повысить качество работы. В-третьих, на ранних этапах исследования иногда бывает интересно получить сведения о внутренней природе или структуре данных. Выделение четких подклассов или основных отклонений от ожидаемых характеристик может значительно изменить подход, принятый при создании классификатора. Ответ на вопрос, можно илн нельзя в принципе обучить чему- либо по непомеченным данным, зависит от принятых предположений — теорему нельзя доказать без предпосылок.
Мы начнем с очень ограниченного предположения, что функциональный вид плотностей распределения известен, и единственное, что надо узнать,— это значение вектора неизвестных параметров. Интересно, что формальное решение этой задачи оказывается почти идентичным решению задачи об обучении с учителем, данному в гл. 3. К сожалению, в случае обучения без учителя решение наталкивается на обычные проблемы, связанные с параметрическими предположениями, не способствующими простоте вычислений. Это приводит нас к различ- 2!2 Гл. б, Обучение без учипгелп и группировка ным попыткам дать новую формулировку задачи как задачи разделения данных в подгруппы, или кластеры.
Хотя некоторые из результирующих процедур группировки и не имеют большого теоретического значения, онн являются одним из наиболее полезных средств решения задач распознавания образов. 6.2, ПЛОТНОСТЬ СМЕСИ И ИДЕНТИФИЦИРггЕМОСТЬ Начнем с предположения, что мы знаем полную вероятностную структуру задачи, за исключением лишь значений некоторых параметров. Более точно, мы делаем следующие предположения: 1. Выборки производятся из известного числа с классов. 2.
Априорные вероятности Р (ог,) для каждого класса известны, г'=1, ..., с. 3. Вид условных по классам плотностей р (к~гоп 0) известен, 1=1,..., с. 4. Единственные неизвестные — это значения с параметрических векторов 0„..., О,. Предполагается, что выборки получены выделением состояния природы во; с вероятностью Р(во,) и последующим выделением х в соответствии с вероятностным законом р (хавин О). Таким образом, функция плотности распределения выборок определяется как с р (х ~ О) = ~ р (х ~ ва „О.) Р (ог.), (1) (=1 где 9= (О„..., 9,).
Функция плотности такого вида называется плотностью смеси. Условные плотности р(х)чан Ог) называются плотностями компонент, а априорные вероятности Р(вот) — параметрами смеси. Параметры смеси можно включить и в неизвестные параметры, но иа данный момент мы предположим, что неизвестно только 9. Наша основная цель — использовать выборки, полученные согласно плотности смесн,'для оценки неизвестного вектора параметров 9.
Если мы знаем О, мы можем разложить смесь на компоненты, и задача решена. До получения явного решения задачи выясним, однако, возможно ли в принципе извлечь 8 из смеси. Предположим, что мы имеем неограниченное число выборок и используем один из непараметрическнх методов гл. 4 для определения значения р(х10) для каждого х. Если имеется только одно значение О, которое дает наблюденные значения для р (х19), то в принципе решение возможно. Однако если несколько различных значений 8 могут дать одни и те же значения для р (х10), то нет надежды получить единственное решение. Эти рассмотрения приводят нас к следующему определению; плотность р (х~8) считается идентифиг(ируемой, если из Очьй' б.З.
Оценки ло максимуму лраеалодабин 213 следует, что существует х, такой, что р(х)0)~р(х(8'). Как можно ожидать, изучение случая обучения без учителя значительно упро- щается, если мы ограничиваемся идентлфицируемыми смесями. К счастью, большинство смесей с обычно встречающимися функци- ями плотности идентнфицируемо. Смеси с дискретным распределе- нием не всегда так хороши. В качестве простого примера рассмот- рим случай, где х бинарен и Р (х)8) — смесь: Р(х)8) =-,' О;(1 — 8,) —.+ — 'О;(1 — 8,) -*= 3 (О, + 8,), если х = 1, 1 1 — — (8, + 8,), если х = О.
Если мы знаем, например, что Р(х=)10)=0,6 и, следовательно, Р (х=010)=0,4, то мы знаем функцию Р (х10), но не можем опреде- лить 0 и поэтому не можем извлечь распределение компонент. Са- мое большее, что мы можем сказать, — это что О,+0,=1,2. Таким образом, мы имеем случай, в котором распределение смеси неиден- тифицируемо, и, следовательно, это случай, в котором обучение без учителя в принципе невозможно. Как правило, при дискретных распределениях возникает такого рода проблема. Если в смеси имеется слишком много компонент, то неизвестных может быть больше, чем независимых уравнений, и иден- тифицируемость становится сложной задачей. Для непрерывного случая задачи менее сложные, хотя иногда и могут возникнуть не- большие трудности. Таким образом, в то время как можно показать, что смеси с нормальной плотностью обычно идентифицируемы, пара- метры в простой плотности смеси р(х(8) = — ехр )с — — (х — 8,)'~ + ехр ~ — — (х — О,)'~ Р(м,) Г 1 1 Р(са) Г 1 )йл ~ '! Ул не могут быть идентифицированы однозначно, если Р(ео,)=Р(еаа), так как тогда О, и О, могут взаимнозаменяться, не влияя на р(х)0).
Чтобы избежать таких неприятностей, мы признаем, что идентифи- цируемость является самостоятельной задачей, но в дальнейшем предполагаем, что плотности смеси, с которыми мы работаем, иден- тифицируемы. 6.3. ОЦЕНКИ ПО МАКСИМУМУ ПРАВДОПОДОБИЯ Предположим теперь, что нам дано множество в = (х„... ..., х„) и непомеченных выборок, извлеченных независимо из смеси с плотностью с р(х(8) = ~р(х~еор Оу) Р(со,), (1) 1 1 214 Ге. б. Обучение бег учители и груннириена где вектор параметров 9 фиксирован, но неизвестен. Правдоподобие наблюдаемых выборок по определению — это совместная плотность и р(Х10) = П р(х ~ 9).
(2) Оценка по максимуму правдоподобия 9 — это то значение О, которое максимизирует р (Х18). Если мы предположим, что р (Я")0) — дифференцируемая функция по О, то можем получить некоторые интересные необходимые условия для О. Пусть 1 — логарифм правдоподобия, и пусть р»!1 — градиент 1 по отношению к Оь Тогда и 1 = ~~Р ~1ой р (хг ~ 8) (3) н е Чв 1 = ~, р („„181 7е! ~~~' р (хи ~ и!Р Оу) Р(ев) г ! " !=! Если мы предположим, что элементы векторов О; и О! функционально независимы при г~1', и если вводим апостериорную вероятность р! ! е! 2(Ъ! ~ ЧОЕ! б (4) р (хг ! в) то видим, что градиент логарифма правдоподобия можно записать в удобной форме: уэ.(= ~Р(еаг~х,, 8!) рэ,!ойр(хи~во О!).
г=! Поскольку градиент должен обратиться в нуль при О„которое максимизирует 1, оценка по максимуму правдоподобия 9, должна удовлетворять условиям ,ееиР(еие1х~, О!) ув,1ойр(х~!еаг, 0~)=О, !=1, ..., с, (б) и=! Обратно, среди решений этих уравнений для 9; мы найдем решение, удовлетворяющее максимуму правдоподобия. Нетрудно обобщить зти результаты, включив априорные вероятности Р(а!) в неизвестные величины. В этом случае поиск максимального значения Р (Х!8) распространяется на О и Р (еа!) при ограничениях Р(га;))О, ! =1, ..., с, (8) 6.4. Приложение и случаю нормален!ел смесеа 21о. Пусть Р (в!) — оценка по максимуму правдоподобия для Р(а;), и пусть О! — оценка по максимуму правдоподобия для О,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
