Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 35
Текст из файла (страница 35)
я) Найдите разложение Уолша. б) Найдите разлоясение Бахадура. Таблица 65 207 О)1 $"Х+ г 0 — Хя (7.1) 1г. Тогда текущее И" по следу1ощпм где ~тО= '1 и 1у;=ХО 7:= 1, 2, И' заменяется новым значением ~Нильсон, 1Ч67]: 1. И" = — И', если значение правилам КеО1 и Цт К) 0 У ~ О1~ и И" У < 0 если У~ О>1 и И"К ( если У ~ О1~ и И" У ~) (7.3)' (7.4)' (7.5)' илп если Ит И +сУ Ит Ит сУ О, О.
Глив и 7 ПОСЛЕДОВАТЕЛЬНОЕ ОЦЕНИВАНИЕ ПАРАМЕТРОВ В рассмотренных до сих пор методах оценивания параметров оценивание производилось по всем наблюденным данным за один просчет. Иногда более практичной оказывается процедура, основанная на последовательных вычислениях. В этом случае параметры в первом приближении определяются путем «угадывания». Затем каждый вектор наблюдения используется для улучшения оценки. Предполагается, что по мере увеличения числа наблюдений оценка будет сходиться в каком-либо смысло к истинным значениям параметров.
Основное преимущество последовательного метода заключается в том, что он позволяет использовать бесконечное число наблюдений, располагая лишь конечным объемом памяти. 5 7.1. Последовательная корректировка линейного классификатора Если каждая из условных плотностей вероятности, соответствующих разделяемым классам, принадлежит известному параметрическому семейству, то классификатор строится довольно просто: оцениваются неизвестные параметры, после чего находится байесовское решающее правило.
Однако довольно часто даже вид условных плотностей вероятности неизвестен. Эти плотности можно аппроксимировать методами, описанными в гл. 6. Однако существует и другой путь решения задачи, позволяющей избежать вычисления плотности вероятности. Допустим, что можно априори предположить, что решающее правило принадлежит некоторому параметрическому семейству решающих правил. Тогда задача сводится к задаче оценивания параметров этого решающего правила. При таком подходе к решению задачи мы жертвуем, быть может, более глубоким пониманием ее сущности, однако, эта жертва часто оказывается более чем оправданной с вычислительной точки зрения.
$ 7.1. кОРРектиРОвкА линейного клАссиФикАТОРА Пусть в задаче классификации па два класса решено исполь.зовать линейный классификатор вида Тогда задача сводится к Оцепиванию параметров У и гО. Линейный классификатор выбран здесь из-за его простоты, однако, как уже говорилось в гл. 4, решающее правило (7.1) включает широкий класс нелинейных разделяющих функций. Это имеет место, когда Х рассматривается как вектор в функциональном пространстве, а не в пространстве исходных переменных. В гл. 4 рассматривалась процедура нахождения параметров У и гО по данному множеству наблюдений при условии, что наблюдения имеются в нашем распоряжении одновремепно.
В алгоритмах,' рассматриваемых в этой главе, мы не запоминаем одновременно все наблюдаемые векторы. Вместо этого в памяти хранится только текущая оценка параметра, которая обновляется всякий раз, когда на вход системы поступает очередной вектор наблюдений. Система этого типа, первоначально предложенная в качестве упрощенной модели обучения и принятия решений в первых исследованиях по распознаванию образов, получила название персе1гтрон,.
Модель этого типа должна иметь алгоритм, который модифицирует параметры с учетом вновь поступившего вектора наблюдений и теку1цего зпачепия этих параметров. 7.1.1. Линейный классификатор для задач распознавания двух классов. Перепишем (7.1) следующим образом: и ОЭ Ь(У) =И"У= ~~ ю,1~,~0 — э-У~ (7.2) 1=-0 О),' Так как вектор параметров И' в случае (7.3) обеспечивает правильную классификацию объекта, то нет основания его менять.
В случае (7.4) И' следует изменить так, чтобы увеличить И~'У. Значение И", вычисленное по правилу (7.4), удовлетворяет, 208 Гл. 7. последовАтельегое ОцениВАпие пАРАметров % 7.1. КОРРЕКТИРОВКА ЛИНЕЙНОГО КЛАССИФИКАТОРА 209 этому условию, так как И' У вЂ” И'У+сУ У) И'У. (7.6) Аналогичным образом значение И"', вычисленное по правилу ~,'(7.5), уменьшает И'"У.
Так как мы при корректировке И~ сами ограничились использованием только одного объекта и текущих значений параметров, описанная выше процедура является достаточно общей и нужно выбрать только значение параметра с. Существует три возможности для выбора с. 1. Правило фиксированного приращения: с — константа. 2. Правило полной коррекции: выбрать с достаточно большим, так чтобы получить И'"У ) 0 для У~ а1 и И"'У ( 0 для У ~ о«г, т. е. И"'У = '(И'+ сУ)'У ) 0 при У~ о«1 и И'У(0, (7.7)' Ит У= (И~ — сУ) У(О при У~о«2 и Ит У~~О. (78) Для того чтобы выполнить требования (7.7) и (7.8), параметр с должен удовлетворять условию с ) ~ И' У~/(У У). (7.9) ~) О, У~о«„ 2,— 1 (( О, У ~= о1,.
(7.11) Как видно из рис. 7.1, этот классификатор правильно разделяет данные четыре объекта 3. Градиентное правило коррекции. Если максимизируется или минимизируется некоторый критерий (например, среднеквадратичное отклонение теоретических значений выхода от фактических), то можно определить с ( У, И') таким образом, чтобы двигаться идоль градиента критерия, Например, по аналогии с (4.76) можно минимизировать среднеквадратичное отклонение И"Х от у(Х), выбирая с = р[т(Л) Ит'Л], (7.10) где Я = У для У ~ а1 и Л~ — У для У ~ о«г. Очевидно, выбор с зависит от выбранного критерия, а р — нужным образом выбранная положительная константа. Прим е р 7.1. Построим классификатор, разделяющий четыре объекта, представленных на рис. 7.1.
Объекты предъявляются машине в такой последовательности: Уо, У1р У~, Уа, Уо, Применяется правило фиксированного приращения с с = 1. Последовательность получающихся в ходе обучения значений И~ приведена в табл. 7.1. Вектор параметров И' сходится к вектору ,( — 1, 2, 0), и мы получаем следующий классификатор: Пример 7.2. Рассмотрим случай, когда правильное разделение с использованием линейного решающего правила невозможно. 1Песть объектов, показанных на рис.
7.2, вводятся в Объекты на входе Класс Ур Ур ' Ур «о Уз Рис. 7.1, Обьекты примера 7.1. машину в последовательности Уо, У1, ..., Уб, У . У у Снова применим правило фиксированного приращения с с = 4. Последовательность получающихся в ходе обучения значений вектора И~ приведена в табл. 7.2. Мы получаем циклическую Таблица 71 Последовательность И~ Н ~все 1У Текущее И' Истинный класс Коррек- ция Сбъекты на входе 1Ут1, ир ир те, нрр О 2 Π— 1 2 О «о Нет й г со а ро н Нет — 1 2 Π— 1 2 О Нет Сет — 1 2 О ! — 1 ~ сох Нет ~ — 1 2 О «о последовательность параметра: сходимость отсутствует, несмотря на то, что полученная последовательность содержит наилучший линейный классификатор [иро ир1 и2] = [О 2 2]. «о Уг У, Уз «о Ут Уа Уо ΠΠΠ— 1 О О О 1 Π— 1 1 — 1 «о И'+Ут И' — У, И'+ Ух О О О О 1 1 — 1 О О О 1 Π— 1 1 — 1 О 2 О' — 1 2 Π— 1 2 Π— 1 2 Π— 1 2 О 210 Введем новыи вектор Я Я = У при У~а1, Я = — У при У~ а2.
(7.12) Уг Объекты на вхсде Класс (7.13) О 2 1 о Ут 1 4 1 о 2 ΠΠ— 2 — 1 — 1 1 — 2 О Ио Текущее И' и ~вле Иl Истин- ный клясс Ксррек- нил Объекты па входе и, чя~ 1е, вч ю, ΠΠ— 3 — 3 О О О 0 ΠΠΠ— 1 — 1 — 1 О 1 — 1 1 1 О О О Нет д' — у 1Г+ У, 1У вЂ” Уо и +У4 И' — У, ΠΠΠ— 1 — 1 — 1 О 1 — 1 — 1 1 ΠΠΠ— 1 2 О Уо Ут ° ~ 2 Уо У4 о И1 Ио И1 Ие И1 1в2 Ф Г со О, о~ Е где — 1 4 1 — 3 — 3 О 2 О 2 2 1 1 1 О О И'+~ о И' — У1 Нет Нет И+~ 4 о Π— 1 — 1 — 1 Π— 1 Уо У2 Уо Уо Уо 2 2 1 1 1 О О 2 О И 'Я*< О.
И1 1в2 (7.16) Π— 1 — 1 — 1 О Щ 1о2 И1 1с2 — 1 2 О (7. 17) Выбирая а шах Ялама и Ь) О, (7. 18) ГЛ. 7, ПОСЛЕДОВЛТЕЛЬНОН ОЦННИВЛНИЕ ПАРЛМЕТРОВ Всякий раз, когда мы имеем дело с итеративным процессом, возникает вопрос о сходимости этого процесса. Доказано, что если два распределения линейно разделимы, то правило фикси- Рис. 7.2. Пример линейной неразделимости классов. рованного приращения, правило полной коррекции и градиентное правило коррекции при подходящем выборе р обеспечивают сходимость описанного выше процесса.
Таблица 7.2 Последовательность И~ для случая линейно неразделимых классов 7.1.2. Доказательство сходимости для случая линейной разделимости классов. Доказательство сходимости описанного вышв алгоритма проводится следующим образом [Нильсон, 1967~. $7,1. КОРРНКТИРОВКЛ ЛИНЕЙНОГО КЛЛССИФИКЛТОРЛ 'Хогда классификатор (7.2) принимает вид ИттЯ) О При Я~а1 И Я~а2, а правила модификации текущего вектора .параметров И' (7.4) и (7.5): Ит' = Ит+ сЯ, если ЪУ'Я ( О, с ) О. (7.14) Исключим из обучающей последовательности Я1, Я~, ..., Я, те объекты Я, предъявление которых не изменяет Ит. Назовем полученную в результате последовательность Я1, 72, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
