Почему максимизация ожидания важна для моделей смесей?

Существует много литературы, в которой подчеркивается, что метод максимизации ожиданий на моделях смесей (смесь гауссовской, скрытой марковской модели и т. Д.).

Почему EM важен? EM - это просто способ оптимизации, который широко не используется в качестве метода, основанного на градиенте (метод градиентного приличия или метод Ньютона / квазиньютона) или другого метода, не обсуждаемого здесь . Кроме того, у EM все еще есть проблема локальных минимумов.

Это потому, что процесс интуитивно понятен и его легко превратить в код? Или какие еще причины?

machine-learning optimization expectation-maximization gaussian-mixture Хайтау Ду
источник

Ответы:

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

Одно из преимуществ EM состоит в том, что он естественно создает действительные параметры для распределения смеси на каждой итерации. Напротив, стандартные алгоритмы оптимизации требуют ограничений. Например, допустим, вы подходите для гауссовой модели смеси. Стандартный подход нелинейного программирования требует, чтобы ограничивающие ковариационные матрицы были положительными полуопределенными, а весовые коэффициенты компонентов смесей должны быть неотрицательными и суммироваться в единицу.

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

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

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

Также интерес (включая комментарии):

user20160
источник

\sum_{i} p_{i} = 1

$\sum_i p_i = 1$

q_{i} \in R

$q_i \in \mathbb{R}$

p_{i} = \frac{\exp (q_{i})}{\sum_{j} \exp (q_{j})}

$p_i = \frac{\exp(q_i)}{\sum_j\exp(q_j)}$

C

$C$

U

$U$

C = U^{T} U

$C = U^T U$

C

$C$

U

$U$

0

$0$

Правильно, верно, разложение холецкого. Намного лучше.

user20160

+1 отличный ответ! Не могли бы вы объяснить больше о том, что «он, естественно, создает допустимые параметры для распределения смеси на каждой итерации»? Для других методов у нас все еще есть значения переменных решения для каждой итерации, верно?

Haitao Du

Я думаю, что ответ user20160 дает очень хорошее объяснение. Самая важная причина, по которой методы, основанные на градиенте, здесь не подходят, заключается в том, что ковариационные матрицы являются положительными полуопределенными, а смешанные коэффициенты неотрицательными и суммируют до одного.

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

Σ знак равно [\begin{matrix} σ_{1}^{2} \\ ⋱ \\ σ_{N}^{2} \end{matrix}]

$\Sigma = \begin{bmatrix} \sigma^2_{1} & & \\ & \ddots & \\ & & \sigma^2_{N} \end{bmatrix}$

φ_{К} знак равно е^{п_{К}} / \underset{К}{Σ} е^{п_{я}}

$\phi_k=e^{p_k}/\sum_Ke^{p_i}$

Более того, это позволяет нам напрямую оптимизировать для истинного правдоподобия вместо вариационной нижней границы (ELBO), тем самым устраняя необходимость в скрытых переменных.

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

dontloo
источник