EM-алгоритм – полезный инструмент моделирования данных, когда максимизация правдоподобия "в лоб", через дифференцирование, невозможна. Кластеризация – одна из задач, где этот алгоритм приходит на помощь. В статье приведен общий вывод EM-алгоритма для кластеризации.
Задача
Множество точек нужно разбить на
кластеров.
Идея решения
Составим вероятностную модель распределения точек по кластерам. Найдём параметры модели, при которых вероятность наблюдать множество максимальна. С этими параметрами мы сможем определять, к какому кластеру наиболее вероятно относится данная точка
.
Модель данных
Введем ряд обозначений, заимствованных из курса.
— вероятность наблюдать точку
.
— вероятность наблюдать множество
.
— вероятность встретить точку
в кластере
. Это распределение параметризовано параметром (или вектором параметров)
, индивидуальным для кластера
.
— вероятность кластера
, т.е. вероятность того, что случайно выбранная точка относится к кластеру
. Случайно выбранная точка точно относится к какому-то кластеру, поэтому
.
Из определений выше следует, что , т.е. распределение точек моделируется как смесь распределений кластеров.
В итоге, вероятностная модель множества точек :
Поиск параметров
Параметры модели и
, как и обсуждалось выше, должны обеспечить максимальную вероятность нашим данным:
Сумма под знаком логарифма мешает решить задачу аналитически. Ограничение не дает нам просто применить автоматическое дифференцирование (например, TensorFlow или PyTorch).
Придется использовать трюк:
L := нижняя граница log p(X)
while log p(X) увеличивается заметно:
приближаем L к log p(X)
w, theta = argmax L
Иначе говоря, мы не будем оптимизировать сам , раз это сложно. Мы возьмем его нижнюю границу
и будем итеративно делать два шага:
- Уточнять
: "подтягивать" её вверх, ближе к
.
- Искать
и
, максимизирующие
.
Мы надеемся, что если полученные параметры максимизируют "близкую" нижнюю границу функции, то они неплохо максимизируют и саму функцию.
Нижняя граница ![$\mathcal{L}$](https://habrastorage.org/getpro/habr/formulas/028/e8a/1e7/028e8a1e74b8335d284dc41e5a41cf70.svg)
Ограничим снизу выражение:
Сначала дополним нашу вероятностную модель. Введем распределение вероятностей данной точки
быть в том или ином кластере:
Домножим и поделим на это распределение слагаемые под логарифмом:
Теперь применим неравенство Йенсена. Оно позволяет логарифм взвешенной суммы ограничить снизу взвешенной суммой логарифмов:
Чтобы неравентсво выполнялось, нужно чтобы веса были неотрицательны и их сумма была
.
В нашем случае будет весом: его значения неотрицательны и
. Применим неравенство:
Полученное выражение и будем использовать в качестве нижней границы:
Уточняем
(E-шаг)
Попробуем максимально приблизить к
. Параметры
и
будем считать фиксированными, а приближать
будем через выбор распределения
.
Запишем разность и
, а потом посмотрим, как её уменьшить:
Заметим, что под знаком логарифма можно выделить апостериорную вероятность кластера :
Тогда:
Мы получили интересное выражение: матожидание отношения двух распределений по первому из них. Оно называется дивергеницией Кульбака-Лейблера (или кратко KL-дивергенцией) и служит "расстоянием" между вероятностными распределениями.
Таким образом, разность и
— это сумма KL-дивергенций:
KL-дивергенция неотрицательна, поэтому лучшее, что мы можем сделать для приближения нижней границы — это сделать KL-дивергенцию нулевой. А этого несложно добиться: KL-дивергенция будет нулём, если её аргументы — это одинаковые распределения. Вот и сделаем распределение тождественным
:
Вычисление по данной формуле и позволит нам приблизить нижнюю границу
к
.
Максимизируем
по параметрам (M-шаг)
Теперь вторая часть итерации: поиск параметров по нижней границе. В этой части наши предположения будут противоположными:
- распределение
фиксированно;
- параметры
и
подлежат оптимизации.
Перед оптимизацией немного упростим :
Второе слагаемое не зависит от параметров и
, поэтому далее будем оптимизировать только первое слагаемое:
Разложим логарифм произведения на сумму логарифмов и получим:
Первая задача решается методом множителей Лагранжа. Результат:
Решение второй задачи зависит от конкретного вида распределения кластера . Как видно, для её решение больше не придётся иметь дело с суммой под знаком логарифма, поэтому, например, для гауссовых распределений решение может быть выписано аналитически.
Итог
Мы выяснили, в чем заключается суть итераций EM-алгоритма для кластеризации, и увидели, как в общем виде выводятся их формулы.