2010 Лекции МОТП (Ветров) (1185317), страница 15
Текст из файла (страница 15)
Методглавныхкомпонент.1 Метод главных компонент (PCA)Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие модели2 Вероятностный метод главных компонентВероятностная формулировка методаEM-алгоритм для PCAВыбор числа главных компонент с помощью байесовского п3 Другие моделиМотивацияЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие моделиPCA может быть сформулирован как вероятностная модель слатентными переменными, для оптимизации которойиспользуется метод максимального правдоподобия.Преимущества вероятностной постановки:• Вычисление правдоподобия на тестовой выборке позволяетнепосредственно сравнивать различные вероятностныемодели• EM-алгоритм для PCA позволяет быстро находитьрешения в ситуациях, когда требуется небольшое числолидирующих главных компонент, а также позволяетизбежать вычисление выборочной матрицы ковариации вкачестве промежуточного шага• Возможность применения байесовского подхода дляавтоматического определения количества главныхкомпонент (по аналогии с методом релевантных векторов)• Можно работать со смесью PCA и использовать вариантEM-алгоритма для обучения в такой моделиВероятностная модель PCAЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие моделиПусть имеется выборка {xn }Nn=1 , xn ∈ Rd .
Рассмотрим длякаждого объекта xn латентную переменную tn ∈ Rd каккоординаты объекта xn в подпространстве, вообще говоря,меньшей размерности d < D. Определим априорноераспределение в пространстве латентных переменных какp(t) = N (t|0, I)Модель наблюдаемых переменных x представляет собойлинейное преобразование латентной переменной сдобавлением гауссовского шума с единой дисперсией повсем направлениям:p(x|t) = N (x|Wt + µ, σ 2 I)Здесь W ∈ RD×d , µ ∈ RD .Иллюстрация вероятностной модели PCAЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие моделиФункция правдоподобияЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие моделиФункция правдоподобия может быть вычислена какZp(x) = p(x|t)p(t)dtЭтот интеграл является сверткой двух нормальныхраспределений и может быть вычислен аналитически. Врезультате получается снова нормальное распределениеp(x) = N (x|µ, C),C = WW T + σ 2 IДействительно,Ex = E(Wt + µ + ε) = µE(x − µ)(x − µ)T = E(Wt + ε)(Wt + ε)T == WEttT W T + EεεT = WW T + σ 2 IИнвариантность относительно поворота координат впространстве латентных переменныхЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие моделиПусть R — некоторая ортогональная матрица. Рассмотримматрицу базисных векторов W̃ = WR.
В этом случаевероятностная модель PCA приводит к тому жераспределению, что и в случае матрицы W. Действительно,т.к. RRT = I, тоC = W̃ W̃ T + σ 2 I = WRRT W T + σ 2 I = WW T + σ 2 IРешениеЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Логарифм правдоподобия для рассматриваемой моделивыглядит какlog p(X|µ, W, σ 2 ) =NXlog p(xn |µ, W, σ 2 ) =n=1Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие модели=−NNDN1X(xn − µ)T C−1 (xn − µ)log 2π − log det C −222 n=1Дифференцируя правдоподобие и приравнивая производную кнулю, получаем:µML =N1 Xxn ,N n=1σ 2ML =DX1λiD − d i=d+1WML = Ud (Ld − σ 2 I)1/2 RЗдесь Ud ∈ RD×d — матрица, состоящая из d собственныхвекторов выборочной матрицы ковариации, отвечающие dнаибольшим собственным значениям λ1 , .
. . , λd ,Ld = diag(λ1 , . . . , λd ), R — произвольная ортогональная матрица.Апостериорное распределение латентнойпеременнойЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие моделиМожно показать, чтоp(t|x) = N (t|M −1 W T (x − µ), σ 2 M −1 )Здесь M = W T W + σ 2 I. Для решения задачи визуализацииданных в пространстве латентных переменных требуетсямат. ожидание латентной переменной по своемуапостериорному распределению:E(t) = M −1 WML (x − x)EM-алгоритм в общем видеЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие моделиПусть имеется вероятностная модель, в которой:• часть переменных X — известна• часть переменных T — не известна• имеется некоторый набор параметров ΘТребуется оценить набор параметров Θ с помощью методамаксимального правдоподобия:Zp(X|Θ) = p(X, T|Θ)dT → maxΘСхема EM-алгоритмаЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Требуется найти максимум правдоподобия в вероятностноймодели со скрытыми переменными:µZ¶Zp(X|Θ) = p(X, T|Θ)dT → max ⇔ logp(X, T|Θ)dT → maxΘМетод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие моделиΘ• E-шаг.
Фиксируется значение параметров Θold .Оценивается апостериорное распределение на скрытыепеременные p(T|X, Θold ), и полное правдоподобиеусредняется по полученному распределению:ZET|X,Θold log p(X, T|Θ) = log p(X, T|Θ)p(T|X, Θold )dT• М-шаг. Фиксируется апостериорное распределениеp(T|X, Θold ), и производится поиск новых значенийпараметров Θnew :Θnew = arg max ET|X,Θold log p(X, T|Θ)Θ• Шаги E и M повторяются до сходимости.Нижняя оценка для логарифмаправдоподобияЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие моделиМожно показать, чтоlog p(X|Θ) ≥ ET|X,Θold log p(X, T|Θ) + Const и =⇔ Θ = ΘoldЗдесь Const - некоторая константа, не зависящая от Θ.Иллюстрация EM-алгоритмаЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие моделиEM-алгоритм для PCAЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Etn = M −1 W T (x − x)Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие моделиWnewEtn tTn = σ 2 M −1 + Etn EtTn" N#" N#−1XXTT=(xn − x)EtnEtn tnn=12σnew=1NDNXn=1n=1TT[kxn − xk2 − 2EtTn Wnew(xn − x) + tr(Etn tTn WnewWnew )]Мотивация EM-алгоритма для PCAЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие моделиНесмотря на существование решения для W и σ 2 в явном виде,использование EM-алгоритма может быть предпочтительным вряде случаев:• EM-алгоритм избегает вычисления выборочной матрицыковариации (сложность O(ND2 )) и поиска ее собственныхзначений (сложность O(D3 )). Самые сложные операции вEM-алгоритме требуют O(NDd) и O(d3 ), что может датьсущественный выигрыш в скорости для данных большихразмерностей.• EM-алгоритм может быть применен для моделифакторного анализа, для которой не существует решения вявном виде. Эта модель полностью повторяетвероятностную модель для PCA, однако различныефакторы могут иметь разную дисперсию:p(x|t) = N (x|Wt + µ, Ψ)Здесь Ψ — диагональная матрица.Проблема выбора количества главныхкомпонент dЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие модели• Параметр d является типичным структурнымпараметром и должен задаваться до стартаEM-алгоритма• Одним из возможных способов выбора d являетсявизуальное оценивание распределения собственныхзначений выборочной матрицы ковариации свыделением области, в которой собственные значенияне отличаются существенно от нуля. К сожалению, напрактике такой порог часто провести не удается.• Разумной альтернативой является байесовский подходАприорное распределение на базисныевектораЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаВыберем в качестве априорного распределения на весанормальное распределение с отдельными коэффициентамирегуляризации для каждого базисного вектора:p(W|α) =D ³Yαi ´D/2i=12πµ¶1exp − αi wTi wi2Здесь wi — i-ая колонка матрицы W. Для подборакоэффициентов α можно использовать максимизациюобоснованности:Zp(X|α, µ, σ 2 ) = p(X|W, µ, σ 2 )p(W|α)dWДругие моделиДанный интеграл не берется аналитически, поэтомувозможными путями являются приближение Лапласа ивариационный подход.Процедура обученияЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентВероятностнаяформулировкаметодаEM-алгоритмдля PCAВыбор числаглавныхкомпонент спомощьюбайесовскогоподходаДругие моделиИспользование приближения Лапласа приводит кследующей формуле пересчета коэффициентоврегуляризации:Dαinew = Twi wiТаким образом, процедура обучения являетсяитерационной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
