Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 23
Текст из файла (страница 23)
4.8. АППРОКСИМАЦИИ ПУТЕМ РАЗЛОЖЕНИЯ В РЯД <Р( — „' ) = ~1' лефе(х) У (х,), 1=1 (37) тогда л ПФ л ~Р(', ')=,~' аРР (х) ~Ч» )(,(хе), 1=и " 1=1 С=И Все описанные до сих пор непараметрические методы имеют тот недостаток, что требуют хранения в памяти всех выборок. А так как для получения хороших оценок необходимо большое количество выборок, потребность в памяти может быть слишком велика. Кроме того, может потребоваться значительное время вычисления каждый раз, когда один из этих методов используется для оценки величины Р(х) или классификации нового х, При определенных обстоятельствах процедуру окна Парзена можно несколько видоизменить, чтобы значительно сократить эти требования.
Основная идея заключается в аппроксимации функции окна путем разложения ее в конечный ряд, что делается с приемлемой точностью в представляющей интерес области. Если нам сопутствует удача имыможем найти два множества функций ф>(х) и те(х), которые допускают разложение Гл. 4.
Непарнметрические мемеды и из уравнения (8) имеем р„(х) = ~'.~ Ь|«р (х), !м! (38) гда Ьу — - й~~- ~~«~ )(у (х!). "«=! (39) а! Следует, однако, заметить, что если й уменьшается при добавлении новых выборок, то «р будет больше приближаться к выбросу н в действительности для получения точной нппрокснмаппн м«виет потребоваться больше членов уравнения. Этот подход имеет некоторые очевидные преимущества в том сл)- чае, когда можно получить дпстаточно точное разложение с приемлемым значением лт. Информация, содержащаяся в и выборках, сводится к лт коэффициентам ЬР Если получают дополнительные выборки, соотношение (39) для Ь) можно легко обновить, причем количество к«эффициентов остается неизменным').
Если функции «рт и т«! являются полиномами от компонент х и х«, то выражение для оценки р„(х) есть также полипом, который можно довольно зффсктнвно вычислить. Более того, использование этой оценки для получения разделяющих функций р(х!«о!) Р(«о!) приводит к простому способу получения лолиномиаломых разделяли«(их функ«(ай. Тут все же следует отметить одну из проблем, возникающую при применении этого способа. Основным достоинством функции окна является ее тенденция к возрастанию в начале координат и снижению в других точках. Так что «р ((х — х!)/Ьн) будет иметь резкий максимум при х х, и мало влиять на аппроксимацию р„(х) для х, удаленного от х!. К сожалеищо, полинамы обладают досадным свойством, заключающимся в том, что они могут содержать неограниченное «ел«честно членов. Псетому при разложении пол«нома могут обнаружиться члены, ассоциируемые с хь удаленным от х, но сильно, а не слабо влияющим иа разложейие, Следовательио, важно убедиться.
что рааложенне каждой фун«ции окна действительно точное в представляющей интерес области, а для этого может потребоваться болыпое число членов. Существует много видов разложения в ряд. Читатели, знакомые с интегральными уравнениями, вполне естеетвецно интерпретируют соотношение (37) «ак разложение ядра «р (х, х!) в ряды по собственным функциям. Вместо вычисления собственных функций мФкно выбрать любое приемлемое множество функций, ортогональных в интересующей нас области, и получить согласие по методу наименьших квадратов с функцией окпз. Яы применим еще более непосредственный подход и разложим функцию окна в ряд Тейлора.
Для про- 4Я, Аппроксимации ауеем раз«ож«н«««в ряд стоты ограничимся одномерным случаем с гауссовской функцией окна: 3/йф(п)=е-"* ж т- ! = Е( — 1)'"— ' 1=« Самым точным это разложение будет в окрестности и=О, где ошибка будет составлять менее и'"/!и!. Если мы подставим х — х! и=— Ь то получим полипом степени 2 (и! — 1) от х и хо Например, если т=2, то '" ' — "."') ='- 1 — "."')'= 2 1 1 ж 1+ — хх — — х' — -~. х', ь' ' а« ь и, таким образом,- « )/и р„(х)= — „~~ )/л Ч!( — "„') жЬ,+Ь«х+Ь«х«, ! ! где 1 ч.~ Ь = — — — —,~„х~ 6 Ь«зЛ !=1 2 !ч~ Ь = — — ~х, Ь«л~ с=! 1 Ь = — —.
а' ' Это простое разложение «сжимаетз информацию из а выборок в три козффициента Ь„Ь, и Ь,. Оно будет точным, если наибольшее значение 1х — х, ~ не превышает Ь. К сожалению, зто заставляет нас пользоваться очень широким окном, которое не дает большого разрешения. Беря большое количество членов, мы можем использовать более узкое окно. Если мы считаем г наибольшим значением 1х — х! ), то, пользуясь тем фактом, что ошибка в и-членном разложении функции )/и !р1(х — х!)/М меньше, чем (г//«)«"'т1, и пользуясь аппроксимацией Стирлинга для т1, найдем, что ошибка в аппроксимации р„(х) будет меньше, чем г 122 г'л. 4, Не»еремее!рпчеекие мепкнЪ Таким образом, ошибка мала только тогда, когда т~е(г/Ь)е. Это говорит о том, что требуется много членов, если ширина окна 6 невелика по сравнению с расстоянием е от х до наиболее удаленной выборки.
Несмотря на то что этот пример элементарен, аналогичные рассуждения действительны и для многомерного случая, даже при использовании более сложных разложений; процедура выглядит более привлекательной, когда ширина окна относительно велика. 4.9. АППРОКСИМАЦИЯ ДЛЯ БИНАРНОГО СЛУЧАЯ 4.9.1. РАЗЛОЖЕНИЕ РАДЕМАХ ЕРА — УОЛША Когда составляющие вектора х дискретны, задача оценки плотности распределения становится задачей оценки вероятности Р(х= з у ). По идее задача эта еще проще„нужно только считать, сколько раз наблюдается х, чтобы получить значение ч„и воспользоваться законом больших чисел. Однако рассмотрим случай, когда е( составляющих вектора х бинарны (имеют значения 0 или 1). Поскольку имеется 2» возможных векторов че, мы должны оценить 2» вероятностей, что представляет собой огромную задачу при больших значениях е(, часто возникающих в работе по распознаванию образов.
Если составляющие вектора х статистически независимы, задача намного упрощается. В этом случае можем написать Р (х) = Ц Р (х!) = Д р,"' (1 — р,)' (40) 1=! е= ! р; = Р (х! = 1), (41) 1 — р; = Р (х; =- О). (42) Таким образом, в этом частном случае оценка для Р (х) сводится к оценке е! вероятностей р,.
Более того, если мы возьмем логарифм Р(х), то увидим, что он является линейной функцией от х, что упрощает как запоминание данных, так и вычисление: 1оЯР(х) = ~~~~ и!;х,+и!„ (43) где, (44) Естественно поинтересоваться, существуют ли какие-либо компромиссные решения между полной строгостью, для достижения которой требуется оценка 2» вероятностей, и вынужденным приня- 43.
Аянроксимация для бинарного случая 123 1=0, 1=1, 1, 2х„— 1, 1=11, г=с(+1, 2ха — 1, (2х, — 1) (2кя — 1), (45) (2ха, — 1) (2ха — 1) 1 = сл + 1 + с((д — 1)/2, (2х,— 1) (2кя — 1) (2х,— 1), 1=с(+2+-с((с( — 1)12, (2х,— 1)... (2ха — 1), 1=2" — 1, Нетрудно заметить, что эти полиномы удовлетворяют отношению ортогональности 1 2а, 1=1, ~~'., <р; (х) ср, (х) =-( (46) где суммирование проводится по 2" возможным значениям х.
Итак, любую функцию Р(х), определенную на единичном с(-кубе, можно разложить как 2 — ! Р (х) = ч~Р а; р; (х) „ (47) 1=О где а; = — ~" срг(х) Р (х). 2" (48) Рассматривая Р(х) как вероятностную функцию видим, что а; = — Е (сР1(Х)). (49) тием статистической независимости, что сведет всю проблему к оценке только с( вероятностей. Разложение для Р(х) и аппроксимация Р(х) частичной суммой дают один ответ. Когда имеются бинарные переменные, естественно использовать полиномы Радемаяера— Уолша в качестве базисных функций.
Такое множество 2" полиномов можно получить путем систематического образования произведений различных сомножителей 2х,— 1, которые получаются следующим образом: ни одного сомножителя, один сомножитель, два и т. д. Таким образом, имеем Гл. е Иеиараиетричесяие мепичум Поскольку функции Радемахера — Уолша <р! (х) — полиномы, видим, что коэффициенты и! являются в сущности моментами. Так что. если Р(х) неизвестна, но имеется и выборок х„..., х„, коэффициенты а! можно оценить, вычисляя моменты выборок б!! бг- — "~ ~ч!г(х ).
1=! В пределе с устремлением и к бесконечности эта оценка по закону больших чисел должка сойтись (по вероятности) к истинному значению а!. Теперь выражение (47) дает нам точное разложение для Р(х), и в этом случае оно не упрощает наши вычисления. Вместо оценки 2" совместных вероятностей мы должны оценить 2" моментов — коэффициентов а!. Можно, однако, аппроксимировать Р(х), усекая разложение н вычисляя только моменты низкого порядка. Аппроксимация первого порядка, полученная с помощью первых 1+!( членов, будет линейной относительно х. Аппроксимация второго порядка, содержащая первые 1+!(+й(д — 1)/2 членов, будет квадратичной относительно х').
В целом выражение (47) показывает, что для аппроксимации полиномами Радемахера — Уолша степени й требуется оценка моментов порядка й и ниже'. Эти моменты можно оценить, исходя из данных, или вычислить непосредстпенно нз Р (х). В последнем случае тот факт, что можно суммировать сначала но переменным, не включенным в полином, говорит о том, что нужно знать только вероятности каждой переменной порядкай, Например, разложение первого порядка определяется вероятностями р,= =Р (хг=1).' и Р,(х)=а,+ ~ аг(2х; — 1), г=! где )' 2-е, г=О, 1, 2 "(2р! — 1), ! =1, ..., с(. Естественно поинтересоваться, насколько хороша такое усеченное разложение аппроксимируат действительную вероятность Р (х).
В общем, если мы аппроксимируем Р (х) с помощью рядов, включающих подмножество полнномов Радемахера — Уолша, Р(х) = Х Ьг!рг(х), ! е! т) поскольку компоненты вектора к бинарные, такие произведения, как к!ля особенно легко вычислять; на ЭЬМ их мовена реалиаовать аппаратно с помощью схем совпадений.
4.9. Анироноимация для динаунооо олуноя 126 4.9.2. РАЗЛО)КЕНИЕ БАХАДУРА — ЛАЗАРСФЕЛЪДА Другое интересное разложение получают введением нормированных величин Уг = (51) у%О ш) считая, конечно, что р, не является ни нулем, нн единицей. Эти нормированные переменные имеют нулевое среднее и дисперсию, равную единице. Множество полииомов, похожих на полиномы Радсмахера — Уолша, можно получить, систематически образуя различные произведения сомножителей у~ в следующем порядке: ни одного сомножителя, один сомножитель, два и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
