2010 Лекции МОТП (Ветров) (1185317), страница 16
Текст из файла (страница 16)
На каждой итерации для текущих значенийα с помощью EM-алгоритма оцениваются W, µ, σ 2 , а затемкоэффициенты α пересчитываются. В EM-алгоритмеформула для пересчета W выглядит следующим образом:"WnewNX=(xn − x)EtTnn=1Здесь A = diag(α1 , . . . , αD ).#"NXn=1#−1Etn tTn2+σ AПлан лекцииЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.1 Метод главных компонент (PCA)Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие модели2 Вероятностный метод главных компонентВероятностная формулировка методаEM-алгоритм для PCAВыбор числа главных компонент с помощью байесовского п3 Другие моделиНедостатки PCAЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие модели• Метод главных компонент способен находить тольколинейные подпространства исходного пространства,которые «объясняют» данные с высокой точностью.
Напрактике поверхность, вдоль которой располагаютсяданные, может быть существенно нелинейной• PCA является инвариантным относительно поворотакоординат в пространстве латентных переменных. Этоозначает, что восстановление значений латентныхпеременных является неоднозначным. В ряде случаевтакая ситуация может быть неадекватной, например, взадаче разделения независимых источников,представленных линейной смесью с неизвестнымикоэффициентами.Метод независимых компонент, ICAЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиПусть наблюдаемые данные x = (x1 , . . . , xd ) являютсялинейной комбинацией независимых источниковt = (t1 , . . . , td ):x = Wt,причем размерности x и t совпадают, а матрица Wнеизвестна.Если преобразование W является невырожденным, тоt = W T x.
Рассмотрим задачу поиска одного источника t1 .Будем искать t1 как линейную комбинацию наблюдаемыхданных t1 = aT x. Задача – определить вектор a.Лекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиЕсли a совпадает с колонкой матрицы W, то t1 будет однимиз искомых источников.t1 = aT x = aT Wt = {z , W T a} = zT t = z1 t1 + · · · + zd tdПо центральной предельной теореме сумма случайныхвеличин приближается к нормальному распределению.Следовательно, чем больше слагаемых в суммеz1 t1 + · · · + zd td , тем более она похожа на гауссиану. Отсюдаa должен быть таким, чтобы aT x было как можно меньшепохоже на гауссиану.Критерии негауссовостиЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие модели• Эксцесс.kurt = Et4 − 3(Et2 )2В предположении, что случайная величина tнормализована, kurt = Et4 . Для гауссианы значение эксцессаравно 0, для остальных распределений может быть какположительным, так и отрицательным.
Поэтому в качествемеры негауссовости выбирают модуль или квадрат эксцесса.• Негэнтропия.ZH(t) = −log p(t)p(t)dtУ гауссовского распределения энтропия H(t) являетсямаксимальной среди всех распределений с одинаковойматрицей ковариации. Поэтому в качестве мерынегауссовости используется негэнтропияH(tgauss ) − H(t)Здесь tgauss — гауссиана с той же матрицей ковариации, чтои t.
Негэнтропия является неотрицательной, и ее нужномаксимизировать для поиска независимых источников.ICA vs. PCA. Пример.Лекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиАнализ независимых факторов, IndependentFactor Analysis, IFAЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиВ методе PCA и факторном анализе в качестве априорногораспределения латентных переменных предполагается выбиратьнормальное распределение с центром в нуле и некоторойдисперсией, возможно, различной для разных направлений. Ванализе независимых факторов в качестве априорногораспределения предлагается выбирать независимое:p(t) =dYp(ti ),p(x|t) = N (x|Wt + µ, Ψ)i=1С одной стороны, данная модель является существеннымобобщением PCA и позволяет находить, вообще говоря,нелинейные зависимости, с другой стороны, модель являетсядостаточно простой, чтобы можно было предложить вариантыEM-алгоритма для ее оптимизации.Одним из возможных вариантов реализации данного методаявляется моделирование распределений отдельных факторов спомощью смеси гауссиан с разным числом компонентов дляразных факторов.Локальное линейное погружение, LocalLinear Embedding, LLEЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиЕсли данные располагаются вдоль некоторой поверхности,то разумно искать такое преобразование признаковогопространства, при котором близкие объекты на этойповерхности были бы близки в новом пространстве. Приэтом близкие в евклидовом смысле объекты в результатетакого преобразования могут оказаться очень далекими.PCA не позволяет находить преобразования с подобнымисвойствами!Схема LLEЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентОсновная идея — искать преобразование с сохранениемотношения соседства между объектами• Восстановление структуры соседства на обучающейвыборке:ε(W) =XДругие моделиNXkxn −n=1Xj∈Neighbours(xn )Wnj xj k2 → minWWnj = 0j• Поиск координат в новом пространстве со схожейструктурой соседства:Φ(T) =NXn=1NXn=1tn = 0,ktn −Xj∈Neighbours(xn )N1 X Ttn tn = IN n=1Wnj tj k2 → minTИллюстрация LLEЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиАвтоассоциативные нейронные сетиЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Рассмотрим многослойный персептрон следующего вида:Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиЗдесь d < D. Задача нейронной сети — объяснить какможно точнее входные данные с помощью выходных.Таким образом, функционалом качества обучения являетсяследующий:NE(w) =1Xky(xn , w) − xn k22n=1Если в сети только один скрытый слой, то даже сиспользованием нелинейной сигмоидной функциейактивации результат обучения сети совпадает сЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.F1F2xdxdвходывыходыМетод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентx1x1нелинейныефункции активацииДругие моделиx3F1x1x2z2x3F2x1z1x2Generative Topographic Mapping, GTMЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентМетод GTM используется, в основном, для визуализацииданных и является вероятностным обобщениемсамоорганизующихся сетей Кохонена.В модели GTM предполагается, что данные образуются врезультате нелинейного преобразования латентныхпеременных с добавлением нормального шума:p(x|t) = N (x|y(t, W), σ 2 I)Другие моделиПространство латентных переменных являетсядвухмерным, а распределение латентных переменныхпредставляет собой сумму дельта-функций с центрами внекоторой регулярной сетке:lp(t) =1Xδ(t − tj )lj=1Иллюстрация GTMЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиФункция правдоподобия выглядит следующим образом:lNXX1log p(X|W, σ 2 ) =log p(xn |tj , W, σ 2 )ln=1j=1Иллюстрация GTMЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиВ качестве функции регрессии предлагается взятьобобщенную линейную:y(t, W) = Wφ(t){φj (t)}dj=1Здесь— набор фиксированных базисныхфункций, в качестве которых могут выступать, например,гауссианы с центрами в регулярной сетке.
Тогда можнопредложить эффективный EM-алгоритм для оптимизациитакой модели.Разрезы графовВетровЛикбезМарковские сетиРазрезы графовРазрезы графовСубмодулярныефункцииАльфарасширениеЮ. И. Журавлев1 , Д. П. Ветров11МГУ, ВМиК, каф. ММПКурс «Математические основы теориипрогнозирования»ПланРазрезы графовВетровЛикбез1 ЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение2 Марковские сети3 Разрезы графов4 Субмодулярные функции5 Альфа-расширениеПотоки в сетяхРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• Рассмотрим неориентированный граф с двумявыделенными вершинами (стоком t и истоком s)• Пусть с каждым ребром (u, v) ∈ E ассоциированонекоторое неотрицательное число c(u, v) ≥ 0 —пропускная способностьПотоки в сетяхРазрезы графовВетровЛикбезМарковские сети• Назовем потоком неотрицательную функцию f (u, v),определенную на ребрах графа, такую чтоf (u, v) ≤ c(u, v)XXf (u, v) −f (v, u) = 0, ∀u 6= {s, t}v:(u,v)∈Ev:(v,u)∈EРазрезы графов• Первое условие ограничивает поток через ребро его пропускнойСубмодулярныефункцииспособностью, а второе гарантирует отсутствие источников истоков вне выделенной пары вершин• Задача поиска максимального потока состоит в максимизациивеличиныXM(f ) =f (s, v) → maxАльфарасширениеv:(s,v)∈Eпо всем допустимым потокамfРазрезы графовРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• (s − t)-разрезом графа называется разбиение вершинграфа на два непересекающихся множества S и T,такие что s ∈ S, t ∈ T• Величиной разреза называется сумма пропускныхспособностей всех ребер, один конец которыхнаходится в множестве S, а другой — в множестве TXc(S, T) =c(u, v)(u,v)∈E,u∈S,v∈TТеорема Форда-ФалкерсонаРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• Известная теорема Форда-Фалкерсона гласит, чтомаксимальный поток в сети равен ее минимальномуразрезу• Существует эффективный (полиномиальнойсложности) алгоритм решения задачи поискаминимального разреза в графе• Задачи поиска максимального потока и минимальногоразреза являются двойственнымиминимальныйразрезмаксимальный потокМарковские решеткиРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• В дальнейшем будем рассматривать т.н.
марковскиерешетки, в которых размер максимальной клики непревосходит двух• В этом случае совместное распределение переменныхмарковской сети выражается формулой1 Yp(Y) =ψij (yi , yj )Z(yi ,yj )∈E• Наиболее типичным примером таких сетей являютсяизображенияxjtjМарковские решетки с бинарнымипеременнымиРазрезы графовВетров• В дальнейшем будем рассматривать марковскиерешетки такого видаxjЛикбезМарковские сетиРазрезы графовtjСубмодулярныефункцииАльфарасширение• Необходимо по наблюдаемым переменным Xвосстановить наиболее вероятные значения скрытыхпеременных TTMP = arg max P(T|X)T• Остановимся на важном частном случае, когдаскрытые переменные бинарные t ∈ {0, 1}Марковские решетки с бинарнымипеременнымиxjРазрезы графовВетровtjЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• Распределение скрытых переменных марковской сети в этомслучае выглядит такYYp(X, T)p(T|X) ==ψij (ti , tj )ψi (xi , ti ) × Constp(X)i(i,j)∈E• В энергетической нотации задача максимизации этогораспределения принимает вид минимизации энергии, что болееудобно с вычислительной точки зренияXXE(T|X) =Eij (ti , tj ) +Ei (xi , ti ) =(i,j)∈E−Xi(i,j)∈Elog ψij (ti , tj ) −Xilog ψi (xi , ti ) → minTПример задачи сегментацииРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширениеЗначения скрытых переменных кодируют принадлежностькаждого пикселя к объекту либо к фону.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
