Aplicación de la maximización de expectativas a los ejemplos de lanzamiento de monedas

Últimamente he estado estudiando la Maximización de Expectativas y obtuve algunos ejemplos simples en el proceso:

A partir de aquí : Hay tres monedas , y con , y la probabilidad respectiva para aterrizar en la cabeza cuando se arrojó. Lanzar . Si el resultado es Cabeza, tres veces, de lo contrario tres veces. Los datos observados producidos por y son así: HHH, TTT, HHH, TTT, HHH. Los datos ocultos son el resultado de . Estima , y .c 1 c 2 p 0 p 1 p 2 c 0 c 1 c 2 c 1 c 2 c 0 p 0 p 1 p $c_0$$c_1$$c_2$$p_0$$p_1$$p_2$$c_0$$c_1$$c_2$$c_1$$c_2$$c_0$$p_0$$p_1$$p_2$

Y a partir de aquí : hay dos monedas y con y siendo la probabilidad respectiva de aterrizar en la Cabeza cuando se arrojan. Cada ronda, selecciona una moneda al azar y tírala diez veces; registra los resultados. Los datos observados son los resultados de lanzamiento proporcionados por estas dos monedas. Sin embargo, no sabemos qué moneda se seleccionó para una ronda en particular. Estime y .c B p A p B p A p $c_A$$c_B$$p_A$$p_B$$p_A$$p_B$

Si bien puedo obtener los cálculos, no puedo relacionar las formas en que se resuelven con la teoría EM original. Específicamente, durante el M-Step de ambos ejemplos, no veo cómo están maximizando nada. Parece que están recalculando los parámetros y de alguna manera, los nuevos parámetros son mejores que los antiguos. Además, los dos E-Steps ni siquiera se parecen entre sí, sin mencionar el E-Step de la teoría original.

Entonces, ¿cómo funcionan exactamente estos ejemplos?

(Esta respuesta utiliza el segundo enlace que le dio).

$\newcommand{\Like}{\text{L}}\newcommand{\E}{\text{E}}$θ = ( θ A , θ B ) X = ( X 1 , … , X 5 ) X i Z = ( Z 1 , … , Z 5

$$\Like[\theta | X] = \Pr[X| \theta] = \sum_Z \Pr[X, Z | \theta]$$ $\theta = (\theta_A, \theta_B)$$X = (X_1, \dotsc, X_5)$$X_i$$Z = (Z_1, \dotsc, Z_5)$

Queremos encontrar el estimador de máxima verosimilitud . El algoritmo Expectation-Maximization (EM) es uno de esos métodos para encontrar (al menos local) . Funciona al encontrar la expectativa condicional, que luego se utiliza para maximizar . La idea es que al encontrar continuamente una más probable (es decir, más probable) en cada iteración, aumentaremos continuamente que a su vez aumenta la función de probabilidad. Hay tres cosas que deben hacerse antes de seguir diseñando un algoritmo basado en EM. theta thetathetaPr[X,Z| θ$\hat{\theta}$$\hat{\theta}$$\theta$$\theta$$\Pr[X,Z|\theta]$

1. Construye el modelo
2. Calcular la expectativa condicional bajo el modelo (E-Step)
3. Maximice nuestra probabilidad actualizando nuestra estimación actual de (M-Step)$\theta$

Construye el modelo

Antes de seguir adelante con EM, necesitamos descubrir qué es exactamente lo que estamos computando. En el E-step estamos calculando exactamente el valor esperado para . Entonces, ¿cuál es este valor, realmente? Observe que La razón es que tenemos 5 experimentos para tener en cuenta, y no sabemos qué moneda se utilizó en cada uno. La desigualdad se debe alog Pr [ X , Z | θ $\log \Pr[X,Z|\theta]$

$$\begin{align*} \log \Pr[X,Z|\theta] &= \sum_{i=1}^5 \log\sum_{C\in \{A,B\}}\Pr[X_i, Z_i=C| \theta]\\ &=\sum_{i=1}^5 \log\sum_{C\in \{A,B\}} \Pr[Z_i=C | X_i, \theta] \cdot \frac{\Pr[X_i, Z_i=C| \theta]}{\Pr[Z_i=C | X_i, \theta]}\\ &\geq \sum_{i=1}^5 \sum_{C\in \{A,B\}} \Pr[Z_i=C | X_i, \theta] \cdot \log\frac{\Pr[X_i, Z_i=C| \theta]}{\Pr[Z_i=C | X_i, \theta]}. \end{align*}$$ $\log$ser cóncavo y aplicar la desigualdad de Jensen. La razón por la que necesitamos ese límite inferior es que no podemos calcular directamente el argumento max a la ecuación original. Sin embargo, podemos calcularlo para el límite inferior final.

Ahora, ¿qué es ? Es la probabilidad de que veamos la moneda dado el experimento y . Usando probabilidades condicionales que tenemos,C X i θ Pr [ Z i = C | X i , θ ] = Pr [ X i , Z i = C | θ $\Pr[Z_i=C|X_i,\theta]$$C$$X_i$$\theta$

$$\Pr[Z_i=C| X_i, \theta] = \frac{\Pr[X_i, Z_i = C|\theta]}{\Pr[X_i|\theta]}.$$

Si bien hemos progresado, todavía no hemos terminado con el modelo. ¿Cuál es la probabilidad de que una moneda dada voltee la secuencia ? Dejar que Ahora es claramente sólo la probabilidad bajo las dos posibilidades de o . Como tenemos, h i = # cabezas en  X i Pr [ X i , Z i = C | θ ] = $X_i$$h_i = \#\text{heads in } X_i$ Pr[Xi| θ]Zi=AZi=BPr[Zi=A]=Pr[Zi=B]=1/

$$\Pr[X_i, Z_i = C| \theta] = \frac{1}{2} \cdot \theta_C^{h_i} (1 - \theta_C)^{10 - h_i},\ \text{ for } \ C \in \{A, B\}.$$ $\Pr[X_i|\theta]$$Z_i=A$$Z_i=B$$\Pr[Z_i = A] = \Pr[Z_i = B] = 1/2$ $$\Pr[X_i|\theta] = 1/2 \cdot (\Pr[X_i |Z_i = A, \theta] + \Pr[X_i |Z_i = B, \theta]).$$

E-Step

De acuerdo ... eso no fue tan divertido, pero podemos comenzar a hacer un poco de EM ahora. El algoritmo EM comienza haciendo una suposición aleatoria de . En este ejemplo tenemos . Calculamos Este valor se alinea con lo que está en el papel. Ahora podemos calcular el número esperado de en de la moneda , Haciendo lo mismo para la moneda , obtenemos $\theta$$\theta^0 = (0.6,0.5)$

$$\Pr[Z_1=A|X_1,\theta] = \frac{1/2 \cdot (0.6^5 \cdot 0.4^5)}{1/2 \cdot ((0.6^5 \cdot 0.4^5) + (0.5^5 \cdot 0.5^5))} \approx 0.45.$$ $X_1 = (H,T,T,T,H,H,T,H,T,H)$$A$ $$\E[\# \text{heads by coin }A | X_1, \theta] = h_1 \cdot \Pr[Z_1=A|X_1,\theta] = 5 \cdot 0.45 \approx 2.2.$$ $B$ $$\E[\# \text{heads by coin }B | X_1, \theta] = h_1 \cdot \Pr[Z_1=B|X_1,\theta] = 5 \cdot 0.55 \approx 2.8.$$ Podemos calcular lo mismo para el número de colas sustituyendo por . Esto continúa para todos los demás valores de y . Gracias a la linealidad de la expectativa podemos descubrir $h_1$$10 - h_1$$X_i$$h_i$ $1 \leq i \leq 5$ $$\E[\#\text{heads by coin } A|X ,\theta] = \sum_{i=1}^5 \E[\# \text{heads by coin }A | X_i, \theta]$$

Paso M

Con nuestros valores esperados en la mano, ahora viene el paso M donde queremos maximizar dados nuestros valores esperados. Esto se hace por simple normalización! Asimismo para . Este proceso comienza nuevamente con el E-Step y y continúa hasta que los valores para convergen (o hasta algún umbral permitido). En este ejemplo tenemos 10 iteraciones y . En cada iteración, el valor de aumenta, debido a la mejor estimación de$\theta$

$$\theta_A^1 = \frac{E[\#\text{heads over } X \text{ by coin } A|X ,\theta]}{E[\#\text{heads and tails over } X \text{ by coin } A|X ,\theta]} = \frac{21.3}{21.3 + 9.6} \approx 0.71.$$ $B$$\theta^1$$\theta$$\hat{\theta} = \theta^{10} = (0.8, 0.52)$$\Pr[X,Z|\theta]$$\theta$ .

Ahora, en este caso, el modelo era bastante simplista. Las cosas pueden complicarse mucho más rápidamente, sin embargo, el algoritmo EM siempre convergerá y siempre producirá un estimador de probabilidad máxima . Puede ser un estimador local , pero para evitar esto, simplemente podemos reiniciar el proceso EM con una inicialización diferente. Podemos hacer esto una cantidad constante de veces y retener los mejores resultados (es decir, aquellos con la mayor probabilidad final).$\hat{\theta}$