Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 44
Текст из файла (страница 44)
..., П, тО ЭЛЕМЕНТЫ гс МатРИЦЫ Я ИМЕЮТ ВИД л, = ехр( — а~1 — т~Т7п) = рн "и'", 1, т = 1, ..., п, (8.112) где р = ехр( — аТ). (8.113) Коэффициенты ошибки (8.110) определяются собственными значениями матрицы Я. Варьируя р и п (8.112), мы получим семейство матриц Я. Найдем коэффициенты ошибки для различных матриц этого семейства. Величина р фиксирована. Для каждого значения п имеем п коэффициентов ошибки ~сс, ..., ~с . Считаем, что ус упорядочены в соответствии с уменьшением Хь На рис. 8.5 приведен график изменения коэффициентов у, в зависимости от и для г ~ п и р = О, 1.
Наиболее важный вывод заключается в том, что значения коэффициентов ошибки лежат в пределах от 0,1 до 100, Таким образом, число точек, ~ ~1й,й ф $8 4 ОЦЕНИВАНИЕ СОБСТВЕННЫХ ЗНАЧЕНИИ фФ й Ъ, 41У НР11ложение 8.1 259 258 ГЛ. 8. СЛУЧАЙ ОДНОГО РАСПРЕДЕЛЕ11ИЯ 8.4.3. Доминирующие собственные значения,. В этом разделе мы рассмотрим задачу оценивания домипирующглх собственных значений и собственных векторов. Вычисление только доминирующих собственных значений и собственных векторов является очень зффективным, так как во многих задачах распознавания образов число доминирующих собственных значений и собственных векторов мало по сравнению с исходной размерностью. Эта задача уже рассматривалась в разделе, посвященном определен1по размерности; здесь мы рассмотрим другой метод ее решения.
Предположим,что нам каким-то образом известно, что число доминирующих собственных значений не превосходит т(т « п). Разделим Ж выборочных векторов на У/т групп по т векторов в каждой группе(Х~1'~, Х(2'),..., Х('), 1= 1, 2, ..., У/т. Для 1-й группы можно сформировать матрицу данных И"' размерностью пХт (см. пример 2.20) и вычислить т собственных векторов и собственных значений матрицы (И""И"')/т, лмеющей размер- СС) (1) ность тХт. Если Ф х и Л х — матрицы этих сооственных векторов и собственных значений, то глз (2.169) — (2.175) следует, что в качестве оценок домипирующглх и-мерных собственных вектоРов и собственных значений можно пРинЯть (И'(ОФ(с))„х и Л(„)х .
Более точнымгл оценками (И'Ф)„х„, и Л х являются средние арифметические зтглх оценок г, Аг(т (И Ф)„хт — (т/Л') ~ (И"' Ф' ')ихтс С вЂ” 1 М(т Л„х — — (т/Х) Х Л"х . С 1 (8.114) (8.115) Чтобы быть уверенными, что все домлнирующие собственные зна- чения включены в эти т собственных значений Лтх, покажем, что '(8.116) МЛгггхт ' .
1гг~гсхгсс Негауссовские процессы. Результаты, полученные для нормальных процессов, полезны во многих задачах, в которых случайный процесс имеет унимодальное распределение. Если структура распределения очень сложна или неизвестна, вычисление оценок (8.104) и (8.105) становится очень сложным. В атом случае и применимость разложения Карунена — Лоева сама по себе становится сомнительной. Таким образом, условие унимодальности, по-вглдимому, является естественным ограниченглем. где Я„х„— выборочная корреляционная матрица, вычисленная по Л/ точкам, а след $г Я„х„равен сумме всех собственных значений матрицы Я„х„. Из (8.114) и (2.172) имеем: М(т ~гЛ,„х„— — (т/Х) ~ 1г Л'"„ 1=1 М(т = (~/х),~~ (1/т) 1г [Ф~ пхт (И'~1~'и1~Ц) ф® С=1 =1г Я„х„.
(8,117) ПРП ЧОгКЕН ИЕ 81 Вычисление Е )1(ФЯФ;)') Вспоминая что Я=(1/Х) ХХ Х', (П8.1.1) имеем Ф';ЯФ; = (1/Х) ~ у;„у,„, 1с=1 где у1„= Ф';Х„. Если правую и левую части (П8.1.2) возвести в квадрат и взять математическое ожидание, то в результате будем иметь Х= )(Ф';ЯФ;) ) = (1/Х'),~~,~~ Е(у(,у,~у(,у;,) = = (1/Х') ~,~~ Е(у,у~„) Е(у(,у;,)+ + (1/Х') ~ Е )ус1,у,А), (П8.1.4) 1=-1 так как случайные величины Хс, независимы. Далее Е(у,Ау, ) = Ф'; Е)(Х,Х1',)) Ф; = ХА;,, (П8.1.5) '''..Л~х Сг [ =Сг[ (П8.1.
2) (П8.1.З) 260 ГЛ. 8. СЛУЧАИ ОДНОГО РЛСПРЕДЕЛЕНИЯ ПРИЛОЖЕНИЕ 8.2 261 и (П8Л.4) можно переписать в виде Е ) (ФЯФ )2) = )(Л вЂ” 1рЛ~) ~Л Х б,, + (1~Л~) Е [ угу,') . (П8Л.6) Второй индекс у опущен, так как все Х„распределены одинаково. Последний член в (П8.1.6) можно вычислить, если известна производящая функция случайного вектора Х, Совместная производящая функция у~ и у~ имеет вид м;~ (~„8,) = Е 1ехр ( ~,Ф4х + ~,Ф';х)) = = Е )ехр ~(~,ф'; + ~,ф';) Х1) = М, (~,Ф; + ~,Ф;), (П8.1.7) где М,( ° ) — производящая функция Х. Отсюда следует, что г г д М'~ (г' гг)~(д~'д~г) ~' ="=о ~ ~ ! Е1у;у;) = ' (П8.1.8) 2 д М; (~„~ )И~ Если Х подчиняется многомерному нормальному распределению с вектором математического ожидания М и корреляционной матрицей Я, то Е )у';у,') = 2Х;6; + Х Х; — 2йд', (П8.1.9) ПРИЛОЖЕНИЕ 82 Ускоренное вычисление собственных значений и собственных векторов В этом приложении мы дадим (на базе 5 8.4) ускоренный алгоритм вычисления собственных значений и собственных векторов корреляционной матрицы Я [Фукупага, 1970б].
Многие существующие алгоритмы для вычисления собственных значений и собственных векторов являются итеративными. Вычисления начинаются с некоторой ортогональной матрицы Ф'", и формируется последовательность (Ф'"'), такая, что Ф = 1пп Ф~~~, (П8.2.1) н~со где ФтЯФ =Л '(П8.2.2) '(П8.2.3) Фтф где Л вЂ” диагональная, а 1 — единичная матрица. В большинстве зтих алгоритмов в качестве начальной матрицы берется Ф'"= 1. Комбинируя (П8Л.9) и (П8Л.6), получим Е )(ф~~с"ф )2) Р„гб ) (1УУ) (Р„~гб . ) Р„Р~ 2 Уг Уг) (П8 4 10) ! где 4 определено в (8Л08).
Предположим, однако, что матрица Яг", имеющая размерность 2пК 2п, разбита на подматрицы в соответствии с (8.82) и вектор Фл (8.84) уже известен. Тогда матрицу Фго" (8.85)', можно йсполь зовать в качестве начального приближения в итеративном алгоритме. Если удвоить и, размерность корреляционной матрицы увеличится до 4п Х4п.
Обозначим ее 54". Следовательно, можно Яг Я4 Я8 Алгоритм заключается в следующем: 1. Взять в качестве начального приближения собственный вектор матрицы Я', равный 1. 2. Располагая вычисленными собственными векторами мата ,т гл рицы Я, использовать Фо в качестве начального приближения в итерационной процедуре для вычисления собственных векторов матрицы Яг". 3. Повторять шаг 2 до тех пор, пока и не достигнет требуемого значения. Этот алгоритм называют быстрым алгоритмом определения собственных векторов, потому что его идея заимствована из быстрого преобразования Фурье. Вычислительное время этого алгоритма зависит от используемого итеративного метода.
Одним из широко используемых итеративных методов является метод пореза Якоби [Гринштадт, 19621. Вычислительное время в случае использования этого метода приближенно оценивается как Т Кпз (П8.2.4) Для использования начального приближения в методе Якоби нужно преобразовать матрицу Я~" в матрицу ~2" следующим образом: ~32и ф2ит дгйф2й (П8.2.5) и применить последовательные преобразования Якоби для диагонализации матрицы ~~". Подставляя (8.82) и (8.85) в (П8.2.5), получим (Л + Вв + В42 + В~~) (Л вЂ” В,~ + В1 — В~~) (Л -~- В,~ — В42 — В~~) (Л вЂ” В1~ — В~2 + В~~) (П8.2.6) где В12 = Ф"~Я~гф" (П8.2.7) (П8.2.8) В„= Ф" Яггф". Следовательно, нам нужно вычислить только В12 и Вгг.
Общее число требуемых для этого умножений составляет около 0,5 и', Это время должно быть добавлено к Т~. Однако, так как К, ы 10, это добавочное время незначительно. 263 ЗАДАЧИ 262 ,(П8.2.10) н — я и' (П8.2.11) Ю й Х Уй УХ Ю Ы Л7 ' Чцспц иа5лю3ений ЗАДАЧИ ГЛ. Б. СЛУЧА11 ОДНОГО РАС11РЕДВПЕП11Я В описанном выше алгоритме метод Якоби применяется т раз для п = 2, 4, ..., 2".
Вычислительное время, расходуемое на 1-м шаге, уменьшается за счет использования начальных условий. Учтем это путем его умножеппя на некоторый коэффициент 01. Рис. П8.2.1. Вкспериментальные кривые для определения коэффициента схо димости ~Фукунага, 1970б]. Для простоты предположим, что 01 — константа, т. е. О, = О. Тогда общее время Тгз будет равно т т т =~ К,О(2)'=2'"К,О ~ 2 " 1=1 1=1 <2 К О/(1 — 2 ) =з7,0т . (П8.2.9) Следовательно, вычислительное время уменьшается в з/10 раз по сравнению с методом Якоби.
Для метода Якоби параметр 0 определяется экспериментально. Вычислительное время пропорционально числу итераций метода Якоби, требуемых для получения желаемой точности. Таким образом, О определяется как 0 = 1„/1„ где 1„ — число итераций, требуемых для получения из вектора Ф" вектора Ф2", а 1х — обьгч~но требуемое число итераций. На рис.
П8.2.1 приведены кривые 1„и 1х для матрицы Я с элементами в зависимости от размерности матрицы при разных значениях т. Расстояние между кривыми, соответствующими быстрому и обычному методам, на полулогарифмическом графике является почти константой для данного т~, а О колеблется между 0,25 и 0,35. Таким образом, быстрый алгоритм позволяет уменьшить время вычислений. Фактическая экономия времени зависит, конечно, от конкретной задачи. ЗАДАНИЕ НА СОСТАВЛЕНИЕ ПРОГРАММ Составьте следующие программы: 8.1. Программу, вычисляющую разложение Карунена — Лоева для ковариационной и корреляционной матриц. а) Вычислите собственные значения и отношения собственных значений к их общей сумме, а затем упорядочите их от наибольшего значения к наименьшему. б) Напечатайте собственные векторы.
Исходные данн,ые: а) стандартные данные 1 = 1, 2; б) смесь стандартных данных 1 = 1, 2. 8.2. Программу выбора признаков, максимизирующих энтропию, для нормальных распределепий. Исходные данные: а) стандартные данные 1 = 1, 2; б) смесь стандартных данных ~ = 1, 2. 8.3. Вычислите собственные значения ковариационной матрицы стационарного процесса х(1) для ~ — Т/2, Т!21, ковариационная функция которого равна ехр( — а~1 — т~).
Сравлите результаты, полученные при разных интервалах между соседними лаблюдениями, со спектральной функцией процесса. 8.4. Дополните программу 81: а) программой автоматического выбора интервала между соседними наблюдениями; б) программой, реализующей быстрый алгоритм вычислен ля собственлых векторов. 8.5. Вычислите собственные значения по т(т ( п) точкам и повторите эти вычисления для й мложеств по и точек.
Сравните выборочное среднее этих собственных значений с собствелными значениями, вычисленными по т Х 7с точкам. Исходные данные: данные, гелерированные в соответствии с выбранным распределением собственных значений. 8.1. Пусть даны три объекта, как показано на рисунке. а) Найдите разложение Карунена — Лоева выборочной корреляционной матрицы и вычислите среднеквадратичную ошибку в случае, если выбирается только один признак. б) Решите ту же задачу для выборочной ковариационной матрицы. 264 ЗАДАЧИ 265 р (Х/вт) 1н р (Х /ве) е/Х Я К задаче 8.7.
т т з (1/Т) е (1) — Ь (1, т) х (т) ат сй о о =Е[ т о!т~) ьо) — в[цга~ о Е[ ГЛ. 8. СЛУЧАИ ОДНОГО РАС11РЕДЕЛЕНИЯ 8.2. В задаче 8.1б покажите, что Х~ равно наибольшему числу среди Е (у1~1, где у~ и уе получаются из х, и хе различными ортогональными пре- 21 образованиями. (Докажите (8.25) в этом простейшем случае другим методом.) 8.3. Обозначим два множества объектов через Х<'> я а~ и ХОВ я оэе.
Они являются взаимно незавпсимымп. Матрица рассеяния между классами определяется выражением Яь = Е ((Х<Π— Х(е>) (ХО~ Хмв)т) Выразите Зе через ковариационные матрицы и математические ожидания этих объектов. 8.4. Вычислите где р (Х/в;) — нормальное распределение К задаче 8.1. с математическим ожиданием М; и корре ляционной матрицей Хе. 8.5. Корреляционная функция и математическое ожидание стационарного процесса х(1) в интервале [ — /„+ /,) равны соответственно ехр( — 4~1 — т~) и О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
