От интуиции к реализации

В мире машинного обучения можно выделить две основные области: обучение с учителем и обучение без учителя. Основное различие между ними заключается в характере данных, а также в подходах, используемых для их обработки. Кластеризация - это проблема неконтролируемого обучения, при которой мы намереваемся найти кластеры точек в нашем наборе данных, которые имеют некоторые общие характеристики. Предположим, у нас есть набор данных, который выглядит так:

Наша задача - найти наборы точек, которые выглядят близко друг к другу. В этом случае мы можем четко идентифицировать два кластера точек, которые мы будем окрашивать в синий и красный цвета соответственно:

Обратите внимание, что сейчас мы вводим некоторые дополнительные обозначения. Здесь μ1 и μ2 - это центроиды каждого кластера и параметры, которые идентифицируют каждый из них. Популярный алгоритм кластеризации известен как K-means, который будет следовать итеративному подходу для обновления параметров каждого кластера. В частности, он будет вычислять средние значения (или центроиды) каждого кластера, а затем вычислять их расстояние до каждой из точек данных. Последние затем помечаются как часть кластера, который определяется их ближайшим центроидом. Этот процесс повторяется до тех пор, пока не будет выполнен некоторый критерий сходимости, например, когда мы не увидим дальнейших изменений в назначениях кластера.

Одной из важных характеристик K-средних является то, что это метод жесткой кластеризации, что означает, что он будет связывать каждую точку с одним и только одним кластером. Ограничением этого подхода является отсутствие меры неопределенности или вероятности, которая сообщает нам, насколько точка данных связана с конкретным кластером. Так что насчет использования мягкой кластеризации вместо жесткой? Это именно то, что пытаются сделать модели гауссовской смеси или просто GMM. Давайте теперь обсудим этот метод подробнее.

Определения

Гауссовская смесь - это функция, состоящая из нескольких гауссианов, каждый из которых обозначается k ∈ {1,…, K}, где K - количество кластеров в нашем наборе данных. Каждый гауссов k в смеси состоит из следующих параметров:

  • Среднее значение μ, определяющее его центр.
  • Ковариация Σ, определяющая ее ширину. Это было бы эквивалентно размерам эллипсоида в многомерном сценарии.
  • Вероятность смешивания π, которая определяет, насколько большой или малой будет функция Гаусса.

Давайте теперь проиллюстрируем эти параметры графически:

Здесь мы видим, что есть три функции Гаусса, следовательно, K = 3. Каждый Гауссиан объясняет данные, содержащиеся в каждом из трех доступных кластеров. Коэффициенты смешивания сами по себе являются вероятностями и должны удовлетворять этому условию:

Как теперь определить оптимальные значения этих параметров? Чтобы достичь этого, мы должны убедиться, что каждый гауссиан соответствует точкам данных, принадлежащим каждому кластеру. Это именно то, что делает максимальная вероятность.

В общем, функция плотности Гаусса определяется как:

Где x представляет наши точки данных, D - количество измерений каждой точки данных. μ и Σ - среднее значение и ковариация соответственно. Если у нас есть набор данных, состоящий из N = 1000 трехмерных точек (D = 3), то x будет матрицей 1000 × 3. . μ будет вектором 1 × 3, а Σ будет матрицей 3 × 3. Для дальнейших целей мы также сочтем полезным взять логарифм этого уравнения, который определяется как:

Если мы продифференцируем это уравнение относительно среднего значения и ковариации, а затем приравняем его к нулю, то мы сможем найти оптимальные значения для этих параметров, а решения будут соответствовать оценкам максимального правдоподобия (MLE) для этого параметра. Однако, поскольку мы имеем дело не только с одним, но и со многими гауссианами, все станет немного сложнее, когда придет время найти параметры для всей смеси. В связи с этим нам нужно будет ввести некоторые дополнительные аспекты, которые мы обсудим в следующем разделе.

Начальные отведения

Мы собираемся ввести некоторые дополнительные обозначения. Просто предупреждение. Математика идет вперед! Не волнуйся. Я постараюсь, чтобы обозначения были как можно более чистыми, чтобы лучше понимать происхождение. Во-первых, предположим, что мы хотим знать, какова вероятность того, что точка данных x n происходит от гауссова k. Мы можем выразить это как:

Что гласит: «с учетом точки данных x , какова вероятность, что она получена из гауссовского k?» В этом случае z - это скрытая переменная, которая принимает только два возможных значения. Это единица, когда x происходит от гауссова k, и ноль в противном случае. На самом деле, мы не видим эту переменную z в реальности, но знание вероятности ее появления может помочь нам определить параметры гауссовой смеси, как мы обсудим позже.

Точно так же мы можем заявить следующее:

Это означает, что общая вероятность наблюдения точки, которая исходит от гауссиана k, фактически эквивалентна коэффициенту смешивания для этой гауссианы. Это имеет смысл, потому что чем больше гауссиан, тем выше, по нашему мнению, будет эта вероятность. Теперь пусть z будет набором всех возможных скрытых переменных z, следовательно:

Мы заранее знаем, что каждый z возникает независимо от других и что они могут принимать значение только одного, когда k равно кластеру, из которого происходит точка. Следовательно:

А как насчет определения вероятности наблюдения наших данных с учетом того, что они получены по гауссову k? Оказывается, это и есть сама функция Гаусса! Следуя той же логике, которую мы использовали для определения p (z), мы можем заявить:

Хорошо, теперь вы можете спросить, зачем мы все это делаем? Помните, нашей первоначальной целью было определить, какова вероятность z с учетом нашего наблюдения x? Что ж, оказывается, что только что выведенные нами уравнения вместе с правилом Байеса помогут нам определить эту вероятность. Из правила произведения вероятностей мы знаем, что

Хм, похоже, сейчас мы куда-то идем. Операнды справа - это то, что мы только что нашли. Возможно, некоторые из вас ожидают, что мы воспользуемся правилом Байеса для получения вероятности, которая нам в конечном итоге понадобится. Однако сначала нам понадобится p (x n ), а не p (x n, z). Итак, как нам здесь избавиться от z? Да, вы правильно угадали. Маргинализация! Нам просто нужно подвести итог по z, поэтому

Это уравнение, которое определяет гауссову смесь, и вы можете ясно видеть, что оно зависит от всех параметров, которые мы упоминали ранее! Чтобы определить оптимальные значения для них, нам нужно определить максимальную вероятность модели. Мы можем найти вероятность как совокупную вероятность всех наблюдений x n, определяемую следующим образом:

Как и в случае с исходной функцией плотности Гаусса, давайте применим логарифм к каждой стороне уравнения:

Большой! Теперь, чтобы найти оптимальные параметры для гауссовой смеси, все, что нам нужно сделать, это продифференцировать это уравнение по параметрам, и все готово, верно? Ждать! Не так быстро. У нас тут проблема. Мы видим, что на второе суммирование влияет логарифм. Вычислить производную этого выражения и затем определить параметры будет очень сложно!

Что мы можем сделать? Что ж, нам нужно использовать итерационный метод для оценки параметров. Но сначала помните, что мы должны были найти вероятность z при x? Что ж, давайте сделаем это, поскольку на данный момент у нас уже есть все необходимое, чтобы определить, как будет выглядеть эта вероятность.

Из правила Байеса мы знаем, что

Из наших более ранних выводов мы узнали, что:

Итак, давайте теперь заменим их в предыдущем уравнении:

И это то, что мы искали! В дальнейшем мы будем часто видеть это выражение. Далее мы продолжим обсуждение с помощью метода, который поможет нам легко определить параметры гауссовой смеси.

Ожидание - алгоритм максимизации

Итак, на данный момент мы получили некоторые выражения для вероятностей, которые мы сочтем полезными при определении параметров нашей модели. Однако в предыдущем разделе мы могли видеть, что простая оценка (3) для нахождения таких параметров оказалась бы очень сложной. К счастью, есть итеративный метод, который мы можем использовать для достижения этой цели. Это называется ожидание - максимизация или просто алгоритм EM. Он широко используется для задач оптимизации, в которых целевая функция имеет сложности, подобные той, с которой мы только что столкнулись в случае GMM.

Пусть параметры нашей модели равны

Давайте теперь определим шаги, которым будет следовать общий алгоритм EM¹.

Шаг 1. Инициализируйте θ соответствующим образом. Например, мы можем использовать результаты, полученные при предыдущем прогоне K-средних, в качестве хорошей отправной точки для нашего алгоритма.

Шаг 2 (шаг ожидания). Оцените

Что ж, на самом деле мы уже нашли p (Z | X, θ). Помните выражение γ, которое мы получили в предыдущем разделе? Для большей наглядности приведем здесь наше предыдущее уравнение (4):

Для моделей гауссовой смеси этап ожидания сводится к вычислению значения γ в (4) с использованием старых значений параметров. Теперь, если мы заменим (4) в (5), у нас будет:

Звучит хорошо, но нам все еще не хватает p (X, Z | θ *). Как его найти? Что ж, на самом деле это не так уж и сложно. Это всего лишь полная вероятность модели, включая X и Z, и мы можем найти ее, используя следующее выражение:

Это результат вычисления совместной вероятности всех наблюдений и скрытых переменных и расширение наших исходных выводов для p (x). Журнал этого выражения дается

Отлично! И мы наконец-то избавились от этого неудобного логарифма, который повлиял на суммирование в (3). При наличии всего этого нам будет намного проще оценить параметры, просто максимизируя Q по отношению к параметрам, но мы разберемся с этим на этапе максимизации . Кроме того, помните, что скрытая переменная z будет только равняться 1 при каждой оценке суммирования. Обладая этими знаниями, мы можем легко избавиться от него по мере необходимости для наших выводов.

Наконец, мы можем заменить (7) в (6), чтобы получить:

На шаге максимизации мы найдем исправленные параметры смеси. Для этого нам нужно будет сделать Q ограниченной задачей максимизации и, таким образом, мы добавим множитель Лагранжа к (8). Давайте теперь рассмотрим шаг максимизации.

Шаг 3 (шаг максимизации): найдите измененные параметры θ *, используя:

Где

Это то, к чему мы пришли на предыдущем шаге. Однако Q также должен учитывать ограничение, что все значения π должны быть в сумме равными единице. Для этого нам нужно добавить подходящий множитель Лагранжа. Поэтому следует переписать (8) так:

И теперь мы можем легко определить параметры, используя максимальное правдоподобие. Теперь возьмем производную Q по π и положим ее равной нулю:

Затем, переставляя члены и применяя суммирование по k к обеим частям уравнения, получаем:

Из (1) мы знаем, что сумма всех коэффициентов смешивания π равна единице. Кроме того, мы знаем, что суммирование вероятностей γ по k также даст нам 1. Таким образом, мы получаем λ = N. Используя этот результат, мы можем найти π:

Точно так же, если мы продифференцируем Q относительно μ и Σ, приравняем производную к нулю и затем решим для параметров, используя определенное нами уравнение логарифма правдоподобия (2), мы получим:

Вот и все! Затем мы будем использовать эти пересмотренные значения для определения γ в следующей итерации EM и так далее, и так далее, пока мы не увидим некоторую сходимость в значении правдоподобия. Мы можем использовать уравнение (3) для отслеживания логарифма правдоподобия на каждом этапе, и мы всегда гарантируем достижение локального максимума.

Было бы неплохо увидеть, как мы можем реализовать этот алгоритм с помощью языка программирования, не так ли? Далее мы увидим части записной книжки Jupyter, которую я предоставил, чтобы вы могли увидеть работающую реализацию GMM на Python.

Реализация на Python

В качестве примечания, полная реализация доступна в виде записной книжки Jupyter по адресу https://bit.ly/2MpiZp4.

Я использовал набор данных Iris для этого упражнения, в основном для простоты и быстрого обучения. Из наших предыдущих выводов мы заявили, что алгоритм EM следует итеративному подходу для нахождения параметров модели гауссовой смеси. Нашим первым шагом была инициализация наших параметров. В этом случае мы можем использовать значения K-средних для этой цели. Код Python для этого будет выглядеть так:

Далее выполняем шаг ожидания. Здесь мы рассчитываем

И соответствующий код Python будет выглядеть так:

Обратите внимание, что для вычисления суммирования мы просто используем члены числителя и делим соответственно.

Затем у нас есть шаг максимизации, на котором мы вычисляем

Соответствующий код Python для этого будет следующим:

Обратите внимание: чтобы немного упростить вычисления, мы использовали:

Наконец, у нас также есть расчет логарифма правдоподобия, который дается выражением

Код Python для этого будет

Мы предварительно вычислили значение второго суммирования на этапе ожидания, поэтому мы просто используем его здесь. Кроме того, всегда полезно создавать графики, чтобы увидеть, насколько прогрессирует вероятность.

Мы ясно видим, что алгоритм сходится примерно через 20 эпох. EM гарантирует, что локальный максимум будет достигнут после заданного количества итераций процедуры.

Наконец, в рамках реализации мы также генерируем анимацию, которая показывает нам, как настройки кластера улучшаются после каждой итерации.

Обратите внимание, как GMM улучшает центроиды, оцененные с помощью K-средних. По мере того, как мы сходимся, значения параметров для каждого кластера больше не меняются.

Заключительные замечания

Модели гауссовой смеси - очень мощный инструмент, который широко используется в различных задачах, связанных с кластеризацией данных. Надеюсь, этот пост был вам полезен! Не стесняйтесь обращаться с вопросами или комментариями. Я также настоятельно рекомендую вам попробовать эти производные самостоятельно, а также глубже изучить код. Я с нетерпением жду возможности создать больше подобных материалов в ближайшее время.

Наслаждаться!

[1] Бишоп, Кристофер М. Распознавание образов и машинное обучение (2006) Springer-Verlag Berlin, Heidelberg.

[2] Мерфи, Кевин П. Машинное обучение: вероятностная перспектива (2012) MIT Press, Кембридж, Массачусетс,