Уменьшение размерности в данных. Метод главных компонент (1185332), страница 3
Текст из файла (страница 3)
Тогда v T Cv = λi − σ 2 +σ 2 = λi . Таким образом, вероятностная модель PCA корректно восстанавливает дисперсииданных в пространстве гиперплоскости и аппроксимирует дисперсию средним значением вортогональном пространстве.Зная параметры W, µ, σ, задача поиска для объекта x представления t в пространстве Rdсводится к вычислению математического ожидания условного распределенияp(t|x) = ∫p(t, x)= N (t|(σ 2 I + W T W )−1 W T (x − µ), I + σ −2 W T W ),p(t, x)dxEt|x t = (σ 2 I + W T W )−1 W T (x − µ).Как было отмечено выше, рассмотрение вероятностной модели со скрытыми переменнымипозволяет решать задачу максимизации правдоподобия с помощью итерационного ЕМалгоритма.
Однако, прежде чем перейти к рассмотрению ЕМ-алгоритма для модели PPCA,рассмотрим схему ЕМ-алгоритма в общем виде и ее применение для восстановления смесинормальных распределений.EM-алгоритм в общем видеПусть имеется вероятностная модель, задаваемая совместным распределением p(X, T |Θ).Здесь X – набор наблюдаемых переменных, T – набор ненаблюдаемых переменных и Θ –набор параметров модели.
Задача состоит в оценке параметров модели Θ с помощью методамаксимального правдоподобия:∫log p(X|Θ) = log p(X, T |Θ)dT → max .(5)ΘЕМ-алгоритм для решения этой задачи представляет собой итерационную процедуру.Пусть фиксировано некоторое значение параметров Θold . На Е-шаге алгоритма вычисляетсяраспределение значений скрытых переменных при данных параметрах:p(T |X, Θold ) = ∫p(X, T |Θold ).p(X, T |Θold )dTЗатем на М-шаге новое значение параметров находится с помощью максимизации полногоправдоподобия, усредненного по апостериорному распределению для T :Θ = arg max ET |X,Θold log p(X, T |Θ).Θ(6)Шаги Е и М повторяются в цикле до сходимости.
Можно показать, что в процессе ЕМ-итерацийзначение правдоподобия p(X|Θ) не убывает. Таким образом, ЕМ-алгоритм позволяет находитьлокальный максимум правдоподобия.Заметим, что во многих практических случаях решение задачи (6) намного проще, чемрешение задачи (5). В частности, во всех рассматриваемых ниже моделях задача оптимизациина М шаге может быть решена аналитически.Вычисление значения функции правдоподобия p(X|Θ) в фиксированной точке Θ требуетинтегрирования по пространству T и в ряде случаев может представлять собой вычислительнотрудоемкую задачу. Заметим, что эта величина правдоподобия стоит также в знаменателеформулы на Е шаге.
Однако, апостериорное распределение p(T |X, Θold ), вычисляемое на10Е шаге, используется затем только для вычисления математического ожидания логарифмаполного правдоподобия на М шаге. Как правило, здесь не требуется знать все апостериорноераспределение целиком, а достаточно знать лишь несколько статистик этого распределения(например, только мат.ожидания отдельных компонент ET |X,Θold tn и парные ковариацииET |X,Θold tn tk ). Поэтому ЕМ-алгоритм может быть вычислительно эффективен даже в техслучаях, когда вычисление значения правдоподобия p(X|Θ) в одной точке затруднено.EM-алгоритм для разделения гауссовской смесиРассмотрим вероятностную модель гауссовской смеси:p(x) =K∑πk N (x|µk , Σk ),k=1K∑πk = 1, πk ≥ 0,(7)k=1≻ 0 (символом Σ ≻ 0 обозначены положительно определенные матрицы).где Σk : Σk =NKЗадача восстановления параметров смеси π, M = {µk }Kk=1 , S = {Σk }k=1 по выборке X = {xn }n=1с помощью метода максимального правдоподобия может быть записана как(∑K)∑Nlogp(X|π,M,S)=logπN(x|µ,Σ)→ max ,knkkn=1k=1π,M,S∑K(8)k=1 πk = 1, πk ≥ 0,Σ = ΣT , Σ ≻ 0.kkkΣTk , ΣkПостроим вероятностную модель со скрытыми переменными, эквивалентную (7).
Для этоговведем бинарный вектор t ∈ {0, 1}K длины K, в котором только одно значение равно единице.Рассмотрим следующую вероятностную модель:p(t) =K∏πktk ,k=1K∏p(x|t) =(9)(N (x|µk , Σk ))tk .(10)k=1Генерация объекта из модели (9)-(10) происходит следующим образом. Сначала свероятностями, пропорциональными π, генерируется номер компоненты смеси, из которой∫затем генерируется точка x. Можно показать, что маргинальное распределение p(x) =p(x|t)p(t)dt в модели (9)-(10) совпадает с распределением (7). В этом смысле модели (9)-(10)и (7) эквивалентны.Рассмотрим теперь применение ЕМ-алгоритма для вероятностой модели со скрытымипеременными (9)-(10) для решения задачи максимизации правдоподобия (8).
Для этоговычислим значение мат.ожидания логарифма полного правдоподобия, необходимого длярешения задачи оптимизации на М шаге:E log p(X, T |π, M, S) =N ∑K∑Etnk (log πk + log N (xn |µk , Σk )).(11)n=1 k=1Заметим, что это выражение зависит только от мат.ожиданий отдельных компонент tnk .Нетрудно показать, что эти величины можно вычислить следующим образом:oldπ old N (xn |µoldk , Σk ).γnk = ET |X,πold ,M old ,S old tnk = ∑K k oldoldoldj=1 πj N (xn |µj , Σj )11(12)222L=1000−2−2−2−20(a)22−20(b)22L=2−20−2−2−2(d)220(f)2L = 2000(c)2L=50−20−20(e)2−2Рис.
6: Иллюстрация применения ЕМ-алгоритма для разделения смеси нормальныхраспределений с двумя компонентами. На рис. а показана исходная выборка и начальноеприближение для двух компонент. На рис. b показан результат Е шага. При этом цвета объектовсоответствуют значениям γnk . На рис. c-f показаны результаты вычислений после 1, 2, 5 и 20итераций.Также нетрудно показать, что задача максимизации критерия (11) при ограничениях1, πk ≥ 0 может быть решена аналитически:1 ∑πk =γnk ,N n=1∑Nn=1 γnk xnµk = ∑,Nn=1 γnk∑Nγnk (xn − µk )(xn − µk )T.Σk = n=1∑Nn=1 γnk∑Kk=1πk =N(13)(14)(15)Заметим, что решение для Σk (15) удовлетворяет условию симметричности и положительнойопределенности. Кроме того, формулы (14),(15) соответствуют оценке максимальногоправдоподобия для многомерного нормального распределения, в которых каждый объект xnберется с весом γnk .Таким образом, ЕМ-алгоритм для смеси нормальных распределений заключается витерационном применении формул (12) и (13)-(15).
Этот процесс имеет простую интерпретацию.Величина γnk показывает степень соответствия между объектом xn и компонентой k(определяет вес объекта xn для компоненты k). Эти веса затем используются на М шаге для12Рис. 7: Пример реального распределения (оцененного с помощью гистограммы) и егоаппроксимация с помощью смеси пяти гауссиан.вычисления новых значений параметров компонент. Иллюстрация применения ЕМ-алгоритмадля разделения нормальной смеси с двумя компонентами показана на рис. 6.Одно из применений смеси нормальных распределений – аналитическая аппроксимациясложных распределений, возникающих на практике.
На рис. 7 приведен пример распределениявыборки (оцененный с помощью гистограммы) и его аппроксимация с помощью смеси пятигауссиан.Другим применением смеси нормальных распределений является решение задачикластеризации на K кластеров. В этом случае номер кластера для объекта xn определяетсявеличинойkn = arg max γnk .kТакая схема кластеризации является вероятностным обобщением известного методакластеризации K-средних.EM-алгоритм для вероятностного метода главных компонентРассмотрим теперь применение ЕМ-алгоритма для вероятностной модели PCA:p(X, T |W, σ , µ) =2N∏p(xn |tn , W, µ, σ 2 )p(tn ),n=1p(xn |tn , W, µ, σ ) = N (xn |W tn + µ, σ 2 I),p(tn ) = N (tn |0, I).213Е-шаг:2p(T |X, Wold , σold, µold )=N∏2p(tn |xn , Wold , σold, µold ),n=12p(tn |xn , Wold , σold , µold ) = N (tn |µn , Σn ),Tµn = Mold Wold(xn − µold ),2Σn = σold Mold ,T2Mold = (WoldWold + σoldI)−1 .M-шаг:1 ∑µnew =xn ,N n=1( N)( N)−1∑∑Wnew =(xn − µnew )EtTnEtn tTn,N2σnewn=1N (∑1=NDn=1)(xn − µnew ) (xn − µnew ) −TT2EtTn Wnew(xn− µnew ) +TtrWnewWnew Etn tTn.n=1При этом необходимые статистики вычисляются следующим образом:Etn = µn ,Etn tTn = Σn + µn µTn .Заметим, что в процессе ЕМ-итераций значение µ не меняется и равно выборочномусреднему.
Поэтому при практическом применении ЕМ-алгоритма для PPCA выборка X сначалацентрируется, а затем все вычисления проводятся без пересчета µ.ЕМ-алгоритм сходится к решению для W (4) с некоторой неединичной матрицей R.Таким образом, полученные признаки не обладают свойством некоррелированности. Крометого, столбцы W не являются, вообще говоря, ортогональными. Поэтому для полученияортогонального базиса требуется дополнительно проводить процесс ортогонализации ГраммаШмидта.Как уже было отмечено выше, итерационный ЕМ-алгоритм является вычислительно болееэффективным по сравнению с аналитическим решением (4) для больших выборок и вситуациях, когда d ≪ D. Действительно, вычисление выборочной матрицы ковариаций требуетO(N D2 ), а поиск ее собственных значений и собственных векторов – O(D3 ) или O(N 3 ).
В ЕМалгоритме самые сложные операции требуют O(N Dd) и O(d3 ), что может дать существенныйвыигрыш при больших N и d ≪ D.2.1Учет пропусков в данныхОдно из преимуществ использования ЕМ-алгоритма для максимизации правдоподобия в моделиPPCA – возможность прямого обобщения метода на случай наличия пропусков в данных.Обозначим Kn — множество известных значений объекта xn и Un — множество пропущенныхзначений объекта xn , Kn ∪ Un = {1, . . . , D}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
