¿Por qué ‘K-means es equivalente al algoritmo de maximización de expectativas con una matriz de covarianza diagonal pequeña y completamente igual’?

Answer 1

Expectativa-maximización hace agrupación suave. Tome un punto [math] x [/ math] y considere los centros de clúster actuales [math] y_1, \ ldots, y_n [/ math]. Cluster [math] y_i [/ ​​math] calcula [math] w_i \ sim \ exp (- (x-y_i) ^ T \ Sigma ^ {- 1} (x-y_i)) [/ math], donde [math] \ Sigma [/ math] es la matriz de covarianza, y la línea ondulada se refiere a mí ignorando constantes.

Con los términos [math] w_1, \ ldots, w_n [/ math], el grupo i obtiene peso [math] \ frac {w_i} {\ sum_j w_j} [/ math].

Ahora, imagine lo que sucede cuando [math] \ Sigma [/ math] es diagonal y sus entradas se vuelven pequeñas. Entonces [math] \ Sigma ^ {- 1} [/ math] se hace más grande, y así comienza la expresión [math] – (x-y_i) ^ T \ Sigma ^ {- 1} (x-y_i) [/ math] preocuparse mucho por el término [matemáticas] x- y_i [/ ​​matemáticas]. En particular, la expresión es cuadrática en este término. Sea [math] y_i ^ * [/ math] el centro más cercano a x, lo que minimiza el término [math] || x-y_i || [/ matemáticas] sobre todo i. Entonces, como [math] \ Sigma \ rightarrow 0 [/ math], [math] w_ {i ^ *} [/ math] comienza a dominar el resto de [math] w_i [/ ​​math], lo que significa que [math] \ frac {w_ {i ^ *}} {\ sum_j w_j} \ rightarrow 1 [/ math] y alguna otra [math] \ frac {w_i} {\ sum_j w_j} \ rightarrow 0. [/ math] Por lo tanto, los puntos se asignan básicamente peso completo al grupo más cercano, que es K-means.