План лекции. 1 Смесь Гауссовских распределений. 2 EM-алгоритм. 3 Информационные методы

2 Смешанные модели Пусть W подмножество Евклидового пространства R d и W = N < Рассмотрим модель, в которой распределение P(W) множества W задается смесью распределений: P(W) = k i=1 p i P(X i ), где p i вероятности кластеров и P(X i ) распределение кластера для всех i 1..k Распределения кластеров P(X i ) могут быть разного вида: Бернулли, Пуассона, Нормальное и т.д. Для решения задачи кластеризации необходимо построить оценки параметров распределений смеси на основе входных данных w = (w 1. w N ). Для этого обычно применяют техники, основанные на скрытых параметрах, такие как алгоритмы Expectation Maximization (EM) и Gibbs sampling А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

3 Смесь Гауссовских распределений Смесь Гауссовских распределений, Gaussian Mixture Model (GMM) f (X k, w) = k p i G(w x i, i ), где G(w x i, i ) плотность i=1 Гауссовского распределения со средним x i и ковариационной матрицей i, i 1..k i = i U i D i U T i, i 1..k, где i константа объема ковариационной матрицы, U i матрица собственных векторов, определяющая ориентацию кластера, D i = diag( 1,i. d,i ) матрица собственных чисел, определяющая форму ковариационной матрицы, d,i d1,i. 1,i = 1 А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

4 Виды ковариационных матриц i Форма Ориентация Объем 1 I Сферическая N/A Одинаковый 2 i I Сферическая N/A Разный 3 Одинаковая Одинаковая Одинаковый 4 i Одинаковая Одинаковая Разный 5 U i DU T i Одинаковая Разная Одинаковый 6 i U i DU T i Одинаковая Разная Разный 7 i UD i U T Разная Одинаковая Разный 8 i Разная Разная Разный Таблица : Виды кластеров в зависимости от ковариационной матрицы. А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

5 Применение GMM Финансовые модели Определение тем текстовых документов Распознавание рукописных символов Распознавание речи, вместе с HMM Машинный перевод, модель IBM 2 Сегментация изображения Радиально-базисные функции (RBF). А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

6 Пример GMM Пусть d = 2, k = 2, x 1 = (0, 0), 1 = ( ) x 2 = (3, 3), 2 = ( ) , Рис. : Моделирование GMM Рис. : Гистограмма одной компоненты входных данных А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

7 Метод максимума правдоподобия Построим оценку параметров на основе ММП Функция правдоподобия: L(

i1..k ) = ( k ) ww p i G (w x i, i ) i=1 Прологарифмируем: F (X k ) = l(

i1..k ) = ww ln ( k i=1 ) p i G (w x i, i ) А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

8 Конечная формула Обозначим Їx i, i 1..k, как (1 + d + d 2 )-вектор, состоящий из p i, d-вектоа x i и элементов d Ч d матрицы i, ЇX (1 + d + d 2 ) Ч k матрица, состоящая из векторов Їx i, i 1..k. Їq(Їx, w) = ln p + (w x) T 1 (w x) Тогда, правило кластеризации: X i (ЇX) = , i 1..k, F (ЇX) = k i=1 wx i (ЇX) Їq(Їx i, w) minїx А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

9 Алгоритм Expectation Maximization (EM) Для максимизации логарифма функции правдоподобия применяется EM алгоритм Алгоритм Expectation Maximization предложен Dempster, Laird и Rubin в 1977 году EM алгоритм итеративная оптимизационная процедура, т.ч. на каждом ее шаге функция правдоподобия не уменьшается, что гарантирует сходимость к локальному максимуму функции Z N Ч k матрица скрытых переменных, т.ч. для каждого w t W, t 1..N t-ый столбец вектор скрытых переменных z n = ( z 1,t. z k,t ), представляющий вероятности того, что wt принадлежит каждому из k кластеров А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

10 Алгоритм Expectation Maximization (EM): инициализация Вход: W множество для кластеризации размера N, k число кластеров, Xk (0) начальное разбиение (опционально) Выход: Разбиение X k множества W на k кластеров Инициализация: Инициализация параметров смеси. Матрица Z 0 может быть инициализирована случайным присвоением 1 одному элементу в каждом столбце. В случае, если X k (0) дано, то модель определяется этим разбиением А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

11 Алгоритм Expectation Maximization (EM): M-шаг a. выборочный размер кластера i = N z i,t. t=1 b. выборочная вероятность кластера p i = i N. c. выборочное среднее кластера x i = 1 i N t=1 z i,t w t. d. Выборочная ковариационная матрица i вычисляется для каждого кластера. А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

12 Алгоритм Expectation Maximization (EM): E-шаг и критерий остановки E-шаг: Вычисление постериорных вероятностей по Байесовскому правилу: p i G (w t x i, ) i z i,t = k p i=1 ig (w t x i, ) i Критерий остановки: Остановка, если старая и новая модели достаточно близки, иначе M-шаг А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

13 Кластеризация при помощи EM-алгоритма Критерий кластеризации (минус функция правдоподобия): cl(їx) = N k t=1 z i,tїq(їx i, w t ) i=1 На каждом EM-шаге критерий кластеризации уменьшается, и процесс сходится к локальному минимуму за конечное число итераций В случае, когда ковариационные матрицы одинаковы i = 2 I, i 1..k), алгоритм кластеризации EM является аналогом алгоритма k-средних. Таким образом, EM алгоритм обобщение алгоритма k-средних Существуют рандомизированные модификации EM алгоритм для кластеризации, имеющие преимущества в скорости и устойчивости к помехам в измерениях А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

14 Пример кластеризации при помощи EM-алгоритма Рис. : Оценка ковариационной матрицы Рис. : Результат работы EM-алгоритма А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

15 Плюсы и минусы GMM Плюсы GMM: Распространенность модели Гибкость структуры кластера, определяемой ковариационной матрицей Строгий статистический вывод для полной модели Алгоритм k-средних часто является быстрым Минусы GMM: Выбор модели сложен. Данные могут не являться Гауссовскими. Сложность оценки ковариационной матрицы Проблема локального минимума Плохо работает в случае невыпуклых кластеров А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

16 Информационные методы Основное предположение: каждый элемент W принадлежит каждому кластеру с определенной вероятностью. Основной целью кластеризации является нахождение оптимальных вероятностей. Такой подход называется нечеткая кластеризация (fuzzy clustering) С точки зрения теории информации кластеризация методика сжатия данных с потерями Для двух дискретных случайных величин X и Y, принимающих значения , i = 1, 2. и , j = 1, 2. соответственно, рассмотрим взаимную информацию: I (X, Y ) = i,j p(x p(x i, y j ) log i,y j ) 2 p(x i )p(y j ) = i,j p(x p(y i, y j ) log j x i ) 2 p(y j ) А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

17 Информационные методы (кластеризация) Кластеризация сжимает исходные данные с помощью отбрасывания менее значимой информации. Для измерения значимости берется мера различия q i (w, w ), i 1..k Сжатие с потерями реализуется минимизацией взаимной информации: I (X k, W) = P(X P(X j w)p(w) log i w) 2 P(X i ) w,i Минимизация ограничена фиксированной мерой различия: F (X k, W) = w,i P(X i w)p(w)q i (x i, w), где x i представление (центорид) кластера X i А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

18 Информационные методы (свободная энергия) Формальное решение задачи достигается с помощью распределения Больцмана ( ) P(X i w) = P(X i ) Z(w,C) exp q i (x i,w), где C Z(w, C) = ( ) P(X i ) exp q i (x i,w) нормализационная C i константа и C множитель Лагранжа При обычной кластеризации распределение центоридов кластеров: P(X) = F e C, где F = C ( ( ln exp e C F w Y i q i (x i,w) C свободная энергия разбиения на кластеры Оптимальные параметры кластеризации находятся минимизацией свободной энергии ) ) А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

19 Информационные методы (частный случай) Пусть q i (x i, w) = (w x i ) 1 i (w x i ) Тогда F = C ( ( ln exp (wx i ) 1 C w i При фиксированном i из уравнений F результат x i = w wp(x j w) w P(X j w), i 1..k i (wx i ) x i )) = 0, i 1..k получаем Данный результат непосредственно связан с результатом, полученным по ММП с помощью EM алгоритма А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

20 Information bottleneck Information bottleneck method техника кластеризации, основанная на том, что каждый кластер отражает относительную информацию внутри данных p(w i w) = w i d i=1 w i Качество кластеризации определяется с помощью взаимной информации I (S; Y )/I (X ; Y ) В качестве мер различия рассматривают расстояние Кульбака-Леейблера (KullbackLeibler divergence) D KL (p(y x) p(y s)), расстояние Йенсена-Шеннона (Jensen-Shannon divergence) DJS(x, s) = (p(x) + p(s)) D JS (p(y x), p(y, s)) А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21

21 Конец Спасибо за внимание! А. А. Бояров, А. А. Сенов (СПбГУ) стохастическое программирование весна / 21