O algoritmo EM é uma ferramenta de modelagem de dados útil quando não é possível maximizar a probabilidade "de frente", através da diferenciação. O armazenamento em cluster é uma das tarefas em que esse algoritmo ajuda. O artigo fornece uma conclusão geral do algoritmo EM para agrupamento.

Tarefa

Muitos pontos $$$X= \{ x_i, i\in1..N \}$deve ser dividido em$$$K$ clusters.

Idéia de solução

Compomos um modelo probabilístico da distribuição de pontos entre os clusters. Vamos encontrar os parâmetros do modelo para os quais a probabilidade de observar o conjunto$$$X$ máximo. Com esses parâmetros, poderemos determinar a qual cluster o ponto mais provável pertence.$$$x$ .

Modelo de dados

Introduzimos uma série de notações emprestadas do curso .

$$$p(x)$é a probabilidade de observar um ponto$$$x$ .

$$$p(X) = \prod_{i=1}^{N}p(x_i)$- probabilidade de observar o conjunto$$$X$ .

$$$p_j (x) = \varphi(x; \theta_j)$- probabilidade de encontrar o ponto$$$x$ no cluster$$$j$ . Essa distribuição é parametrizada por um parâmetro (ou vetor de parâmetro)$$$\theta_j$ indivíduo para o cluster$$$j$ .

$$$w_j$é a probabilidade do cluster$$$j$ , isto é a probabilidade de um ponto selecionado aleatoriamente pertencer a um cluster$$$j$ . Um ponto selecionado aleatoriamente se refere exatamente a um cluster, portanto$$$\sum_{j=1}^K w_j = 1$ .

Das definições acima, segue-se que $$$p(x) = \sum_{j=1}^K w_j p_j(x) = \sum_{j=1}^K w_j \varphi(x; \theta_j)$, .. .

, $$$X$:

$$

$$p(X) = \prod_{i=1}^{N}\left(\sum_{j=1}^K w_j \varphi(x_i; \theta_j)\right)$$

$$$w$$$$\theta$, , :

$$

$$w, \theta = \textrm{argmax} \ p(X) = \textrm{argmax} \ \log p(X) = \textrm{argmax}_{w, \theta} \sum_{i=1}^{N} \log \left(\sum_{j=1}^K w_j \varphi(x_i; \theta_j)\right)$$

. $$$\sum_{j=1}^K w_j = 1$(, TensorFlow PyTorch).

:

L :=   log p(X)
while log p(X)  :
     L  log p(X)
    w, theta = argmax L

, $$$\log p(X)$, . $$$\mathcal{L}$:

1. $$$\mathcal{L}$: "" , $$$\log p(X)$.
2. $$$w$$$$\theta$, $$$\mathcal{L}$.

, "" , .

$$$\mathcal{L}$

:

$$

$$\log p(X) = \sum_{i=1}^{N} \log \left(\sum_{j=1}^K w_j \varphi(x_i; \theta_j)\right)$$

. $$$g_i$$$$x_i$:

$$

$$g_i(j) \equiv p(\textrm{ } \ j| \textrm{ } \ i)$$

:

$$

$$\sum_{i=1}^{N} \log \left(\sum_{j=1}^K w_j \varphi(x_i; \theta_j)\right) =\sum_{i=1}^{N} \log \left(\sum_{j=1}^K \frac{ g_i(j) }{ g_i(j) } w_j \varphi(x_i; \theta_j)\right)$$

. :

$$

$$\log \left(\sum_i q_i x_i \right) \geq \sum_i q_i \log x_i$$

, $$$q_i$$$$1$.

$$$g_i(j)$: $$$\sum_{j=1}^K g_i(j) = 1$. :

$$

$$\sum_{i=1}^{N} \log \left(\sum_{j=1}^K \frac{ g_i(j) }{ g_i(j) } w_j \varphi(x_i; \theta_j)\right) \geq \sum_{i=1}^{N} \sum_{j=1}^K g_i(j) \log \left(\frac{ w_j \varphi(x_i; \theta_j) }{ g_i(j) }\right)$$

:

$$

$$\mathcal{L}(g, w, \theta) \equiv \sum_{i=1}^{N} \sum_{j=1}^K g_i(j) \log \left(\frac{ w_j \varphi(x_i; \theta_j) }{ g_i(j) }\right)$$

$$$\mathcal{L}$(E-)

$$$\mathcal{L}(g, w, \theta)$$$$\log p(X)$. $$$w$$$$\theta$, $$$\mathcal{L}$$$$g$.

$$$\log p(X)$$$$\mathcal{L}$, , :

$$

$$\log p(X) - \mathcal{L}(g, w, \theta) = \sum_{i=1}^N \log p(x_i) - \sum_{i=1}^{N} \sum_{j=1}^K g_i(j) \log \left(\frac{ w_j \varphi(x_i; \theta_j) }{ g_i(j) }\right)=$$

$$

$$= \sum_{i=1}^N \left(\log p(x_i) \sum_{j=1}^K g_i(j) - \sum_{j=1}^K g_i(j) \log \frac{w_j \varphi(x_i; \theta_j)}{g_i(j)} \right) = \sum_{i=1}^N \sum_{j=1}^K g_i(j) \log \frac{p(x_i) g_i(j)}{w_j \varphi(x_i; \theta_j)}$$

, $$$j$:

$$

$$p(j|x_i) = \frac{\varphi(x_i; \theta_j) w_j}{p(x_i)}$$

:

$$

$$\sum_{i=1}^N \sum_{j=1}^K g_i(j) \log \frac{p(x_i) g_i(j)}{w_j \varphi(x_i; \theta_j)} = \sum_{i=1}^N \sum_{j=1}^K g_i(j) \log \frac{g_i(j)}{p(j|x_i)}= \sum_{i=1}^N \mathbb{E}_{g_i} \frac{g_{i}}{p(j|x_i)}$$

: . - ( KL-) "" .

, $$$\log p(X)$$$$\mathcal{L}$— KL-:

$$

$$\log p(X) - \mathcal{L}(g, w, \theta) = \sum_{i=1}^N KL(g_i || p(j|x_i))$$

KL- , , — KL- . : KL- , — . $$$g_i(j)$$$$p(j|x_i)$:

$$

$$g_i(j) = p(j|x_i) = \frac{w_j \varphi(x_i; \theta_j)}{p(x_i)}$$

$$$g_i(j)$$$$\mathcal{L}$$$$\log p(X)$.

Maximizar $$$\mathcal{L}$por parâmetros (etapa M)

Agora a segunda parte da iteração: pesquisando parâmetros ao longo do limite inferior. Nesta parte, nossas suposições serão opostas:

• distribuição $$$g$fixo;
• parâmetros $$$w$e $$$\theta$sujeito a otimização.

Simplifique antes da otimização $$$\mathcal{L}$:

$$

$$\mathcal{L}(g, \theta) = \sum_{i=1}^N\left( \sum_{j=1}^K g_i(j) \log \frac{w_j p(x_i; \theta_j)}{g_i(j)} \right) =$$

$$

$$= \sum_{i=1}^N \sum_{j=1}^K g_i(j) \log \left( w_j p(x_i; \theta_j) \right) -\sum_{i=1}^N \sum_{j=1}^K g_i(j) \log g_i(j)$$

O segundo termo é independente dos parâmetros $$$w$e $$$\theta$, portanto, otimizaremos ainda mais o primeiro termo:

$$

$$w, \theta = \textrm{argmax}_{w, \theta}\sum_{i=1}^N \sum_{j=1}^K g_i(j) \log \left( w_j \varphi(x_i; \theta_j) \right)$$

Decompomos o logaritmo do produto na soma dos logaritmos e obtemos:

$$

$$w = \textrm{argmax}_{w}\sum_{i=1}^N \sum_{j=1}^K g_i(j) \log w_j, \textrm{ }\sum_{j=1} w_j = 1$$

$$

$$\theta_j = \textrm{argmax} \sum_{i=1}^N g_i(j) \log \varphi (x_i; \theta_j)$$

O primeiro problema é resolvido pelo método multiplicador de Lagrange. Resultado:

$$

$$w_j = \frac{1}{N} \sum_{i=1}^N g_i(j)$$

A solução para o segundo problema depende do tipo específico de distribuição de cluster $$$\varphi (x_i; \theta_j)$. Como você pode ver, para sua solução, você não precisa mais lidar com a soma sob o signo do logaritmo; portanto, por exemplo, para distribuições gaussianas, a solução pode ser escrita analiticamente.

Total

Descobrimos a essência das iterações do algoritmo EM para clustering e vimos como suas fórmulas são derivadas de uma maneira geral.