Dlaczego maksymalizacja oczekiwań jest ważna dla modeli mieszanin?

Istnieje wiele literatury podkreślającej metodę maksymalizacji oczekiwań na modelach mieszanin (mieszanina modelu Gaussa, model ukrytego Markowa itp.).

Dlaczego EM jest ważny? EM to tylko sposób na optymalizację i nie jest szeroko stosowany jako metoda oparta na gradiencie (metoda przyzwoitego gradientu lub metoda newtona / quasi-newtona) lub inna metoda bez gradientu omówiona TUTAJ . Ponadto EM nadal ma problem z lokalnymi minimami.

Czy to dlatego, że proces jest intuicyjny i można go łatwo przekształcić w kod? Lub jakie inne powody?

— Haitao Du
źródło

Odpowiedzi:

Zasadniczo zarówno optymalizacja EM, jak i standardowe optymalizacje mogą działać w celu dopasowania rozkładów mieszanin. Podobnie jak EM, wypukłe solwery optymalizacyjne zbiegną się do lokalnego optimum. Istnieje jednak szereg algorytmów optymalizacyjnych do poszukiwania lepszych rozwiązań w obecności wielu lokalnych optymów. O ile mi wiadomo, algorytm o najlepszej szybkości konwergencji będzie zależał od problemu.

Jedną z zalet EM jest to, że w naturalny sposób wytwarza prawidłowe parametry dla rozkładu mieszaniny przy każdej iteracji. Natomiast standardowe algorytmy optymalizacji wymagałyby ograniczenia. Załóżmy na przykład, że dopasowujesz model mieszanki Gaussa. Standardowe podejście do programowania nieliniowego wymagałoby ograniczenia macierzy kowariancji jako dodatnich półfinałów oraz ograniczenia wag składników mieszanki jako nieujemnych i sumujących się do jednego.

Aby osiągnąć dobrą wydajność w przypadku problemów z dużymi wymiarami, nieliniowy solver programistyczny zazwyczaj musi wykorzystywać gradient. Trzeba więc wyprowadzić gradient lub obliczyć go z automatycznym różnicowaniem. Gradienty są również potrzebne do funkcji ograniczeń, jeśli nie mają standardowej postaci. Metoda Newtona i podobne podejścia (np. Metody regionu zaufania) również wymagają Hesji. Można zastosować metody różnicowania skończonego lub metody bez pochodnych, jeśli gradient jest niedostępny, ale wydajność ma tendencję do słabego skalowania wraz ze wzrostem liczby parametrów. Natomiast EM nie wymaga gradientu.

EM jest koncepcyjnie intuicyjny, co jest wielką zaletą. Często dotyczy to również standardowych metod optymalizacji. Istnieje wiele szczegółów implementacji, ale ogólna koncepcja jest prosta. Często możliwe jest użycie standardowych solverów optymalizacyjnych, które wyodrębniają te szczegóły pod maską. W takich przypadkach użytkownik musi jedynie podać funkcję celu, ograniczenia i gradienty, a także mieć wystarczającą wiedzę praktyczną, aby wybrać solver dobrze dopasowany do problemu. Ale specjalistyczna wiedza jest z pewnością wymagana, jeśli dojdzie do punktu, w którym użytkownik musi przemyśleć lub wdrożyć szczegóły niskiego poziomu algorytmu optymalizacji.

Inną zaletą algorytmu EM jest to, że można go stosować w przypadkach, gdy brakuje niektórych wartości danych.

Interesujące (w tym komentarze):

— user20160
źródło

\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$

Racja, racja, chłodny rozkład. Dużo lepiej.

— user20160

+1 świetna odpowiedź! czy mógłbyś wyjaśnić więcej na temat „naturalnie produkuje prawidłowe parametry dla rozkładu mieszaniny przy każdej iteracji”? W przypadku innych metod nadal mamy wartości zmiennych decyzyjnych dla każdej iteracji, prawda?

— Haitao Du

Myślę, że odpowiedź user20160 stanowi bardzo dobre wytłumaczenie, najważniejszym powodem, dla którego metody oparte na gradientach nie są tutaj odpowiednie, jest ograniczenie macierzy kowariancji jako dodatnich półfinałów, a współczynniki mieszania są nieujemne i sumują się do jednego.

Chcę tylko zaznaczyć, że jeśli ograniczymy macierze kowariancji do diagonalnej, wówczas te dwa ograniczenia można łatwo wyrazić.

Σ = [\begin{matrix} σ_{1}^{2)} \\ ⋱ \\ σ_{N.}^{2)} \end{matrix}]

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

ϕ_{k} = {mi}^{p_{k}} / \sum_{K.} {mi}^{p_{ja}}

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

Ponadto pozwala nam to bezpośrednio optymalizować pod kątem prawdziwego prawdopodobieństwa zamiast wariacyjnej dolnej granicy (ELBO), eliminując w ten sposób potrzebę ukrytych zmiennych.

Jednak nawet w takich przypadkach EM często okazuje się lepszym algorytmem niż przyzwoity gradient.

— dontloo
źródło