Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 24
Текст из файла (страница 24)
д. Так что имеем 1=0, 1=1, 1, У1 (=п, (=о+1, Ую У1Уов (52) ф(х) = 1 = о(+ 1 + Н (о( — 1) /2, 1=й+2+й(б — 1)/2, Ул-1У4 У1УоУо~ то можно использовать отношения ортогональности, чтобы показать, что сумма квадратичной ошибки Х (Р(х) — Р(х))' минимизируется выбором Ь;=а,. Таким образом, усеченное разложение является оптимальным в смысле среднеквадратичной ошибки. Кроме того, коль скоро в аппроксимацию входит постоянный полипом ~у„можно легко показать, что л,Р(х)=1, что и требуется. Однако ничто не может предотвратить превращение Р (х) в отрицательную величину для некоторого х.
Действительно, если <р, не входит в полипом, то 4,Р (х) =О и по крайней мере одна из вероятностей должна быть отрицательной. Этого досадного результата можно избежать путем разложения 1он Р (х), а не Р (х), хотя в атом случае мы уже ие сможем большебытьуверенывтом, что суммирование полученной аппроксимации для Р(х) даст единицу.
Гх. 4. Не«ар«метр«хе««хе методы 1гВ Эти полиномы не ортогональны сами по себе, но они ортогональны, если ввести весовую функцию Р,(х) Др"1(1 р)' «1, 11 (53) т. е. 11, ,~~ хР1 (х) 2Р (х) Р, (х) = ) (54) 2 -1 Р(х)= ~~'., а12р;(х), где ае = ~~'., 2Р1 (х) Р, (х) Р (х), х В частности, функцию Р(х)/Р,(х) можно представить в виде 2 -1 Р(х)=Р,(х) ~~'., а12Р1(х), (55) где а1 —— ~~,'ехр1(х) Р (х) = Е 12р1(х)).
х (56) Вспомнив, что 1р1 (х) есть произведение нормированных переменных у;=(х1 — р1)/)/р,(1 — р1), видим, что а1 — это коэффициенты корреляции. Очевидно,что а,=1 и ах=...а«=0. Если определить р;«=Я1У;у~Р(х), х р1 1„— —,Я~ у„у уир (х), х (57) Рхв "«=ХУ1уе. У«Р(х)~ х то можно представить соотношение (55) как Р(х)=Р,(х) ~1+ ХР,УУ;У~+ Х РО«У;УУ«+ . 1<2 1<1<2 ° ° +р12 "«У1ух ° .У«~ ° (58) Это следует из того, что Р, (х) является распределением для случая с независимыми переменными и что в этом случае моменты ЕЪре(х) хр2(х)1 являются или нулем, нли единицей.
Следовательно, любую функцию, определенную на единичном И-кубе, можно разложить как 4.9. Аоироисимоция для бинарного случая 127 Оно известно как разложение Бахадура — Лазарсфельда Р(х). В нем содержится 2е — 1 коэффициентов, д вероятностей р; первого ад! / и''! порядка, ( 9 7! козффициентовкорреляциирмвторогопорядка, ! з 7! коэффициентов корреляции роя третьего порядка и т. д. Естественный способ аппроксимировать Р (х) — это игнорировать все корреляции свыше определенного порядка. Таким образом, Р, (х) = Д Р",' (1 — р!) ' "! 1=! есть аппроксимация первого порядка Р(х), Р, (х) = Р, (х) [1+ ~ р; у,у1 !<! есть аппроксимация второго порядка и т. д.
Если коэффициенты корреляции высокого порядка невелики и мы используем аппроксимацию 1од (1+х)жх, то видим, что!ой Р,(х) линейный относительно х, 1ой Р,(х) добавляет квадратичный член корреляции и т. д. Таким образом, логарифм разложения Бахадура — Лазарсфельда дает интересную последовательность аппроксимаций. Первая аппроксимация эквивалентна допущению независимости, и она линейна относительно х.
Вторая отвечает корреляции второго порядка и квадратична относительно х. Каждая последующая аппроксимация отвечает корреляциям более высокого порядка, но, конечно, требует вычисления большего количества членов. 4.9.3. РАЗЛОЖЕНИЕ ЧОУ Другой интересный класс аппроксимаций совместного распределения вероятностей Р(х) основан на тождестве Р (х) = Р (х„..., хо) = Р (хл) Р (х, ! х, ) Р (ля ) х„х,)...
...Р (хе ) хи „..., х,). (59) Если переменные статистически независимы, оно сводится к произведению отдельных вероятностей Р(х,). Предположим, что переменные не являются независимыми, но что Р(х!!х! „..., х,) зависит только от непосредственно предшествующей переменной хг,. Тогда имеем марковскую цепь первого порядка и Р (х) = Р (х,) Р (х, ) х,) Р (х, ) х,)... Р (хи ) х,,). (60) Мы увидим, что каждый сомножитель Р(х,)х! !) можно определить с помощью двух коэффициентов; значит, Р (х) можно определить с помощью 2с( — 1 коэффициентов, что будет менее сложно, чем если гбт бы мы допустили все ( 9 ) корреляций второго порядка.
Аналогичные марковские аппроксимации более высокого порядка можно по- Га. 4. Нееарссметасесисссса ссееседес !вз лучить, если допустить, что х, зависит только ат Ф непосредственно прцдшествующих переменных. Допущение, что заданная переменная хс зависит только от определенных предшествующих переменных, приемлемо, если мы имеем дело с временным процессом; для более общих случаев это допущение выглядит довольно нелепо. Тем не менее есть основание полагать, что заданная переменная хс может в основном зависеть только от нескольких других переменных. Предположим, что мы мажем занумеровать переменные так, что Р(х,!х, „..., х,) целиком зависит от некоторой предшествующей переменной хлп.
Например, допустим, что Р(х,)х„х„х,) =-Р(х,!х,) и Р(х,)х„х,) =Р(х,!х,). Тогда из (59) следует, что Р(х„х„х„х,) можно записать как Р(хс) Р(хс!хс) Р(хс!х,) Р(хс!хс). Вообще мы йолучаем разложение в виде произведения Р (х) = Р (х,) Р (х, ! хх мс)... Р (хе ! хт сю), (61) Подставляя О или 1вместо хс и хсссь читатель может проверить, что Р(хс!х~с ) =урсс(1 — Рс)' "3 ""Гс! с(1 — Чс)' "с~™( ', (62) где Р,=Р(хс — — 1!хссп — — 1) (66) и с(с=Р (хс=1!хссс,=О). (64) Полагая с),=Р(х,=!), подставляя (62) в соотношение (61), беря логарифм и собирая члены, получаем разложение Чоу !ояР(х)= ~,1од(1 — с!с)+ ~„хс1одсс' + с=с с Аналогичные результаты легко можно получить для зависимости более высокого порядка. Следует сделать несколько замечаний относительно этих результатов.
Во-первых, если переменные действительно независимы, мы замечаем, что Рс=с!с и последние две суммы в разложении исчезают, оставляя уже знакомые разложения для случая с независимыми иераманными. Когда зависимость имеется, мы получаем дополнительные линейные и квадратичные члены. Конечно, линейные члены можно абьединить так, чтобы в разложении содержались константа, с! линейных членов и с( — 1 квадратичных членов. ВЛО.
Линейный дискрииииаит Фишера 129 Сравнивая это разложение с разложением второго порядка Радемахера — Уолша или Бахадура — Лазерсфельда, для каждого из которых требуется д(д — 1)/2 квадратичных членов, видим, что преимущества данного разложения могут быть значительными. Конечно, эти преимущества можно реализовать только в том случае, если мы знаем дерево зависимости — функцию /(1), которая показывает ограниченную зависимость одной переменной от предыдущих переменных.
Если дерево зависимости нельзя вывести из физической значимости переменных, то может возникнуть необходимость в вычислении всех коэффициентов корреляции просто для того, чтобы найти значимые. Однако следует заметить, что даже в этом случае может быть предпочтительнее использовать разложение Чоу, так как получаемые при этом приближенные вероятности будут всегда неотрицательными и их сумма будет равна единице. 4.10. ЛИНЕЙНЫЙ ДИСКРИЗ1ИНАНТ ФИШЕРА Одной из непреходящих проблем, с которой сталкиваются при применении статистических методов для распознавания образов, является то, что Беллманом было названо проклятием размерности.
Процедуры, выполнимые аналитически нли непосредственным вычислением в пространствах небольшой размерности, могут стать совершенно неприменимыми в пространстве с 50 или 100 измерениями. Были разработаны различные методы уменьшения размерности пространства признаков в надежде получить задачу, поддающу1ося решению. Можно уменьшить размерность с д измерений до одного, просто' проецируя д-мерные данные на прямую. Конечно, особенно если выборки образуют хорошо разделенные компактные группы в дпространстве, проекция на произвольную прямую обычно смешивает выборки из всех классов. Однако, вращая эту прямую, мы можем найти такую ориентацию, для которой спроецированные выборки будут хорошо разделены.
Именно это является целью классического днскриминантного анализа. Предположим, что мы имеем множество и д-мерных выборок х„..., х„, и, в подмножестве Х„помеченном в„и и, в подмножестве Я'„помеченном а,. Если мы образуем линейную комбинацию компонент вектора х, получим скалярную величину у =чг'х (бб) и соответствующее множество и выборок у„..., у„, разделенное на подмножества Эт и 01.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
