Объяснение моделей гауссовой смеси и лежащего в ее основе алгоритма максимизации ожидания в упрощенном виде

После того, как вы научитесь кластеризовать выборки немаркированных точек данных с помощью простейшего алгоритма кластеризации k-средних, мы начинаем видеть несколько недостатков k-средних при применении этого метода к реальному набору данных. Следующим шагом инженера машинного обучения будет применение более сложных алгоритмов для понимания различных группировок (кластеров) в его / ее выборках данных, и, скорее всего, этот алгоритм будет моделированием гауссовой смеси (GMM). Из-за наличия программного обеспечения с открытым исходным кодом и нескольких фреймворков машинного обучения, таких как Scikit-learn, достаточно всего пары строк, чтобы использовать этот алгоритм. Однако многим было трудно понять математику, лежащую в основе этого процесса. В этой статье мы более интуитивно рассмотрим внутреннюю работу этого алгоритма.

Преимущества GMM перед k-means

Давайте начнем строить наши концепции моделирования гауссовой смеси, обращая внимание на недостатки k-средних.

  • Непропорциональные размеры кластеров: k-means работает по простому принципу привязки выборок данных к ближайшему предполагаемому центру кластера, таким образом формируя диаграмму Вороного на гиперплоскости. Как следствие, несколько выборок данных будут неправильно классифицированы, если кластер находится слишком далеко от его правильного центра кластера. С GMM разброс ваших точек данных в кластере не обязательно должен быть равномерным от его центров кластера.

  • Различные формы кластеров. Другой способ увидеть указанную выше проблему - k-среднее может нарушить форму кластера, хотя образцы данных плотно упакованы внутри кластера. При изменении ориентации кластера результаты k-средних могут значительно измениться.

  • Перекрывающиеся кластеры: Иногда точки данных, принадлежащие разным кластерам, могут быть очень плотно упакованы, и алгоритм k-средних без колебаний рассуждает о распределении выборок в своем кластере. k-means проведет жесткую границу между кластерами, даже если образцы могут быть бесконечно близки к границе. Используя GMM, вы формулируете свою модель с постулатом об отсутствии жестких границ в кластерах, что приводит нас к следующему главному преимуществу GMM.

  • Мягкое присвоение: с помощью стандартного алгоритма k-средних вы выделяете точку данных кластеру со 100% вероятностью. Однако в GMM для каждой выборки данных в наборе данных вы назначаете набор правдоподобия, с какой вероятностью выборка данных принадлежит каждому кластеру, присутствующему в системе. Например, в приведенном ниже распределении, состоящем из 4 кластеров, вы назначаете равную вероятность (по 25% каждый) для образца данных, присутствующего в центре, если GMM попросят его кластеризовать.

Гауссово распределение

Итак, как математически представить функции этих кластеров, которые могут иметь разные размеры, формы, ориентации и, возможно, перекрывать друг друга? Как следует из названия этого метода, мы используем распределение Гаусса для представления каждого кластера отдельно в системе. Прежде чем мы рассмотрим, как это возможно, давайте сделаем краткий обзор гауссова распределения в одномерном пространстве.

Здесь мы показываем несколько функций плотности вероятности (PDF) распределения Гаусса. Горбинка этой унимодальной функции представляет собой среднее значение и также находится в центре этого распределения. Разброс этого распределения вокруг среднего определяется стандартным отклонением. Член в квадрате стандартного отклонения известен как дисперсия этого распределения.

Но поскольку наш набор данных будет в более высоких измерениях (скажем, n), нам придется использовать n-мерную функцию распределения Гаусса для представления нашего кластера. Поскольку на гауссиану влияет несколько характеристик (представленных осью на изображении), мы перейдем от простой дисперсии к ковариационной матрице, которая поможет нам получить информацию о разбросе (через дисперсию) и ориентации (через корреляцию). ) также.

Создание кластеров с гауссианами

Давайте теперь создадим кластеры различных положений, размеров, форм и ориентации с функциями распределения Гаусса. Давайте рассмотрим, что у нас есть 2-мерный набор функций, который приведет к 2X2-мерной ковариационной матрице. Вот наша ковариационная матрица, чтобы создать простой круговой кластер.

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

Вышеупомянутый кластер представляет собой ось, выровненную в обычной декартовой системе координат X-Y. И чтобы изменить ориентацию от обычного выравнивания оси, мы добавляем члены корреляции в недиагональные положения.

И как нам изменить положение этих кластеров? Для этого мы используем n-мерный средний вектор (обозначенный μ). Например, ниже представлен набор из четырех смоделированных по Гауссу кластеров выборок данных, каждый из которых имеет свой средний вектор и ковариационную матрицу.

Как нам объединить эти смоделированные по Гауссу кластеры?

Хотя мы представили четыре кластера выше, как мы их просто объединили? Разве не должно быть отношений, которые отражают важность каждого кластера над другим? Это приводит нас к другому параметру, представленному π, который количественно определяет относительную долю весов каждого кластера в системе. Поскольку это относительный масштаб, мы гарантируем, что сумма всех π в системе будет равна 1.

Таким образом, чтобы представить компонент нашего кластера (или смеси), нам нужно будет использовать в общей сложности три параметра (среднее значение μ, ковариация ∑ и вес пропорции π), которые вместе известны как параметры кластера.

Как мы отслеживаем мягкие назначения?

Придется добавить еще одну терминологию. Нам нужно выразить вероятности присвоения каждой выборки данных всем существующим кластерам в системе. Мы зафиксируем это мягкое назначение вектором ответственности, обозначенным rᵢₖ, который переходит в объем ответственности, кластер k примет за образец данных i. Поскольку это вероятности, сумма обязанностей, связанных с отдельной точкой данных, будет равна 1. Итак, мы имеем

Постановка модели

Теперь, когда у нас есть гауссовское распределение, готовое для представления кластера, давайте извлечем некоторую полезную информацию из модели. Первый вопрос, на который мы попытаемся ответить: если вы случайным образом выберете выборку данных (скажем, выборку i), с какой вероятностью она принадлежит каждому из этих кластеров (скажем, всего k кластеров)? Ответ - это просто наш компонент весовой пропорции π каждого кластера, поскольку он переводит на важность / доминирование каждого кластера в системе. Математически,

Другими словами, это уравнение соответствует априорной вероятности присвоения выборки данных кластеру k.

А теперь сделаем шаг вперед. Представьте, что мы узнали, что наша ранее увиденная iᵗʰ выборка (обозначенная zᵢ) принадлежала кластеру k, а затем давайте попробуем вычислить, какова вероятность для конкретной конфигурации входного вектора (обозначенного xᵢ), присутствующего внутри выборки данных. zᵢ принадлежит кластеру k? Если вы вообразите, ответ на этот вопрос равен функции распределения по Гауссу для кластера k, поскольку функция распределения, другими словами, представляет собой индивидуальный набор образцов, присутствующих внутри него. Образцы здесь состоят из входных векторов. Итак, математически мы имеем

Это уравнение соответствует вероятности появления xᵢ при условии, что zᵢ принадлежит кластеру k.

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

Шаг 1. Предположим, что параметры кластера известны.

Хотя на самом деле мы этого не знаем, давайте на время предположим, что нам известны значения параметров кластера {μ, ∑ и π} всех кластеров и, следовательно, известно распределение гауссовых функций. Теперь нам нужно вычислить вероятности мягкого присваивания. Индивидуальное значение вероятности внутри вектора ответственности для конкретной выборки данных zᵢ в кластере k преобразуется в вероятность наблюдения выборки данных zᵢ в кластере k, усиленную весовым коэффициентом (априорной вероятностью) этого кластера k. Математически это выражается так:

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

Шаг 2: Предположим, что мягкие назначения известны

Ранее мы предполагали, что параметры кластера известны, а затем мы нашли способ вычислить мягкие назначения. Теперь давайте проделаем обратный путь на этом шаге. Давайте найдем способ вычисления параметров кластера, предполагая, что мягкие назначения известны.

Чтобы упростить процедуру расчета, мы временно будем считать, что присвоение каждой выборки данных кластеру является абсолютным (жестким), аналогичным k-средним. Теперь нам нужно вычислить {μ, ∑ и π} для всех кластеров, используя выборки данных, принадлежащие каждому кластеру отдельно. Это прямое применение оценки максимального правдоподобия, при котором мы пытаемся найти наилучшие значения для параметров целевой функции и затем подбираем функцию с наилучшими значениями.

Однако мы воспользуемся сокращением, поскольку мы уже знаем значения среднего вектора и ковариационной матрицы в гауссовском распределении, и мы не будем выводить значения, используя стандартную процедуру MLE с оптимизатором. Итак, оценочные значения среднего и ковариации:

Nₖ обозначает количество выборок в кластере k, а N соответствует общему количеству выборок в наборе данных. Расчетный параметр доли кластера π представляет собой прямое значение вероятности появления выборок данных, принадлежащих кластеру k. Так,

Теперь, когда готовы уравнения для расчетных параметров кластера, давайте решим исходную задачу, предполагая, что кластерные назначения были мягкими, а не жесткими или абсолютными. Для этого мы можем построить на основе наших уже выведенных уравнений, используя жесткие присвоения. В сложных заданиях мы работали с полным наблюдением xᵢ в кластере k, но теперь нам просто нужно уменьшить абсолютный (100% или 0%) вклад в его долю относительной ответственности (от 0,0 до 1,0). Обновленные оценки параметров кластера с мягкими присвоениями будут:

Из любопытства вы можете преобразовать эти уравнения в уравнения жестких назначений, изменив вектор ответственности на абсолютный (1.0 или 0.0).

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

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

Давайте формально определим два шага, которые мы видели.

E-step: это описано в шаге 1 нашего объяснения. На этом этапе мы оцениваем векторы ответственности кластера для данных оценок параметров кластера на этом временном шаге.

M-шаг: это описано в шаге 2 нашего объяснения. На этом этапе мы максимизируем вероятность по параметрам кластера для заданных векторов ответственности на этом временном шаге.

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

В этой статье мы исследовали метод неконтролируемого обучения кластеризации с моделированием гауссовой смеси и лежащий в его основе алгоритм максимизации ожидания. Поделитесь своим мнением о содержании этой статьи.