El algoritmo EM es una herramienta útil de modelado de datos cuando no es posible maximizar la probabilidad "en la frente" mediante la diferenciación. El agrupamiento es una de las tareas en las que este algoritmo viene al rescate. El artículo proporciona una conclusión general del algoritmo EM para la agrupación.

Tarea

Muchos puntos $X= \{ x_i, i\in1..N \}$ debe dividirse en $K$ agrupaciones.

Idea de la solución

Componemos un modelo probabilístico de la distribución de puntos a través de grupos. Encontremos los parámetros del modelo para los cuales la probabilidad de observar el conjunto $X$ máximo. Con estos parámetros, podremos determinar a qué grupo pertenece el punto más probable. $x$ .

Modelo de datos

Introducimos una serie de notación prestada del curso .

$p(x)$ es la probabilidad de observar un punto $x$ .

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

$p_j (x) = \varphi(x; \theta_j)$ - probabilidad de cumplir el punto $x$ en el clúster $j$ . Esta distribución está parametrizada por un parámetro (o vector de parámetros) $\theta_j$ individual para el clúster $j$ .

$w_j$ es la probabilidad del grupo $j$ , es decir la probabilidad de que un punto seleccionado aleatoriamente pertenezca a un grupo $j$ . Un punto seleccionado al azar se refiere exactamente a un grupo, por lo que $\sum_{j=1}^K w_j = 1$ .

De las definiciones anteriores se deduce 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} (\sum_{j = 1}^{K} w_{j} φ (x_{i}; θ_{j}))

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

$w$ $\theta$ , , :

w, θ = argmax p (X) = argmax \log p (X) = {argmax}_{w, θ} \sum_{i = 1}^{N} \log (\sum_{j = 1}^{K} w_{j} φ (x_{i}; θ_{j}))

$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}$ :

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

, "" , .

$\mathcal{L}$

\log p (X) = \sum_{i = 1}^{N} \log (\sum_{j = 1}^{K} w_{j} φ (x_{i}; θ_{j}))

$\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 (быть в кластере j | это точка i)

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

\sum_{i = 1}^{N} \log (\sum_{j = 1}^{K} w_{j} φ (x_{i}; θ_{j})) = \sum_{i = 1}^{N} \log (\sum_{j = 1}^{K} \frac{g_{i} (j)}{g_{i} (j)} w_{j} φ (x_{i}; θ_{j}))

$\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 (\sum_{i} q_{i} x_{i}) \geq \sum_{i} q_{i} \log x_{i}

$\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 (\sum_{j = 1}^{K} \frac{g_{i} (j)}{g_{i} (j)} w_{j} φ (x_{i}; θ_{j})) \geq \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log (\frac{w_{j} φ (x_{i}; θ_{j})}{g_{i} (j)})

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

L (g, w, θ) \equiv \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log (\frac{w_{j} φ (x_{i}; θ_{j})}{g_{i} (j)})

$\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) - L (g, w, θ) = \sum_{i = 1}^{N} \log p (x_{i}) - \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log (\frac{w_{j} φ (x_{i}; θ_{j})}{g_{i} (j)}) =

$\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} (\log p (x_{i}) \sum_{j = 1}^{K} g_{i} (j) - \sum_{j = 1}^{K} g_{i} (j) \log \frac{w_{j} φ (x_{i}; θ_{j})}{g_{i} (j)}) = \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log \frac{p (x_{i}) g_{i} (j)}{w_{j} φ (x_{i}; θ_{j})}

$= \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{φ (x_{i}; θ_{j}) w_{j}}{p (x_{i})}

$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} φ (x_{i}; θ_{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} E_{g_{i}} \frac{g_{i}}{p (j | 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) - L (g, w, θ) = \sum_{i = 1}^{N} K L (g_{i} | | p (j | x_{i}))

$\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} φ (x_{i}; θ_{j})}{p (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)$ .

$\mathcal{L}$ (M-)

: . :

$g$ ;
$w$ $\theta$ .

$\mathcal{L}$ :

L (g, θ) = \sum_{i = 1}^{N} (\sum_{j = 1}^{K} g_{i} (j) \log \frac{w_{j} p (x_{i}; θ_{j})}{g_{i} (j)}) =

$\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 (w_{j} p (x_{i}; θ_{j})) - \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log g_{i} (j)

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

El segundo término es independiente de los parámetros. $w$ y $\theta$ , por lo tanto, optimizaremos aún más solo el primer término:

w, θ = {argmax}_{w, θ} \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log (w_{j} φ (x_{i}; θ_{j}))

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

Descomponemos el logaritmo del producto en la suma de los logaritmos y obtenemos:

w = {argmax}_{w} \sum_{i = 1}^{N} \sum_{j = 1}^{K} g_{i} (j) \log w_{j}, при условии \sum_{j = 1} w_{j} = 1

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

θ_{j} = argmax \sum_{i = 1}^{N} g_{i} (j) \log φ (x_{i}; θ_{j})

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

El primer problema se resuelve con el método multiplicador de Lagrange. Resultado:

w_{j} = \frac{1}{N} \sum_{i = 1}^{N} g_{i} (j)

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

La solución al segundo problema depende del tipo específico de distribución del clúster. $\varphi (x_i; \theta_j)$ . Como puede ver, para su solución, ya no tiene que lidiar con la suma bajo el signo del logaritmo, por lo tanto, por ejemplo, para distribuciones gaussianas, la solución puede escribirse analíticamente.

Total

Descubrimos la esencia de las iteraciones del algoritmo EM para la agrupación y vimos cómo sus fórmulas se derivan de manera general.

Algoritmo EM para agrupamiento

Tarea

Idea de la solución

Modelo de datos

$\mathcal{L}$

$\mathcal{L}$ (E-)

$\mathcal{L}$ (M-)

Total

More articles:

Algoritmo EM para agrupamiento

Tarea

Idea de la solución

Modelo de datos

L\mathcal{L}

L\mathcal{L}(E-)

L\mathcal{L}(M-)

Total

More articles:

$\mathcal{L}$

$\mathcal{L}$ (E-)

$\mathcal{L}$ (M-)