Aplicar la maximización de las expectativas a los ejemplos de lanzamiento de monedas

Question

He estado auto-estudiando la maximización de las expectativas últimamente, y me agarré algunos ejemplos simples en el proceso:

De aquí: Hay tres monedas $ c_0 $, $ c_1 $ y $ c_2 $ con $ p_0 $, $ p_1 $ y $ p_2 $ la probabilidad respectiva para aterrizar en la cabeza cuando se lanza. Mezcle $ C_0 $. Si el resultado es cabeza, tire $ C_1 $ tres veces, de lo contrario, mezcle $ C_2 $ tres veces. Los datos observados producidos por $ C_1 $ y $ C_2 $ son así: HHH, TTT, HHH, TTT, HHH. Los datos ocultos son el resultado de $ C_0 $. Estime $ P_0 $, $ P_1 $ y $ P_2 $.

Y de aquí: Hay dos monedas $ c_a $ y $ c_b $ con $ p_a $ y $ p_b $ es la probabilidad respectiva para aterrizar en la cabeza cuando se lanza. Cada ronda, seleccione una moneda al azar y tírela diez veces; Registre los resultados. Los datos observados son los resultados del lanzamiento proporcionados por estas dos monedas. Sin embargo, no sabemos qué moneda fue seleccionada para una ronda particular. Estime $ P_A $ y $ 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 paso M 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 pasos electrónicos ni siquiera se parecen entre sí, sin mencionar el paso electrónico de la teoría original.

Entonces, ¿cómo funcionan exactamente estos ejemplos?

Answer 1

(Esta respuesta usa el segundo enlace que dio).

$ newcommand { me gusta} { text {l}} newcommand { e} { text {e}} $ Recuerde la definición de probabilidad: $$ me gusta [ theta | X] = pr [x | theta] = sum_z pr [x, z | theta] $$ Donde en nuestro caso $ theta = ( theta_a, theta_b) $ son los estimadores de la probabilidad de que las monedas A y B respecten los cabezales, $ x = (x_1, dotsc, x_5) $ es el Resultados de nuestros experimentos, cada uno $ x_i $ consta de 10 flips y $ z = (z_1, dotsc, z_5) $ es la moneda utilizada en cada experimento.

Queremos encontrar un estimador de máxima probabilidad $ hat { theta} $. El algoritmo de maximización de expectativas (EM) es uno de esos métodos para encontrar (al menos local) $ hat { theta} $. Funciona al encontrar la expectativa condicional, que luego se usa para maximizar $ theta $. La idea es que al encontrar continuamente un $ probable (es decir, más probable) $ theta $ en cada iteración aumentaremos continuamente $ pr [x, z | theta] $ 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.

1. Construir el modelo
2. Calcule la expectativa condicional bajo el modelo (E-Step)
3. Maximice nuestra probabilidad actualizando nuestra estimación actual de $ theta $ (m-step)

Construir el modelo

Antes de ir más allá con Em, necesitamos descubrir qué es exactamente lo que estamos calculando. En el paso electrónico estamos calculando exactamente el valor esperado para $ log pr [x, z | theta] $. Entonces, ¿cuál es este valor, realmente? Observe que $$ 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 {alinearse*} $$ La razón es que tenemos 5 experimentos para tener en cuenta, y no sabemos qué monedas se usó en cada uno. La desigualdad se debe a que $ log $ es cóncavo y aplica la desigualdad de Jensen. La razón por la que necesitamos ese límite inferior es que no podemos calcular directamente el arg max a la ecuación original. Sin embargo, podemos calcularlo para el límite inferior final.

Ahora, ¿qué es $ pr [z_i = c | x_i, theta] $? Es la probabilidad de que veamos Coin $ C $ Daded Experiment $ x_i $ y $ theta $. Uso de probabilidades condicionales que tenemos, $$ pr [z_i = c | X_i, theta] = frac { pr [x_i, z_i = c | theta]} { pr [x_i | theta]}. $$

Si bien hemos hecho algunos progresos, todavía no hemos terminado con el modelo. ¿Cuál es la probabilidad de que una moneda dada volteara la secuencia $ x_i $? Dejar $ h_i = # text {cabezales en} x_i $ $$ pr [x_i, z_i = c | theta] = frac {1} {2} cdot theta_c^{h_i} (1 - theta_c)^{10 - h_i}, text {para} c in {a, b } . $$ ahora $ pr [x_i | theta] $ es claramente la probabilidad bajo ambas posibilidades de $ z_i = a $ o $ z_i = b $. Dado que $ pr [z_i = a] = pr [z_i = b] = 1/2 $ tenemos, $$ pr [x_i | theta] = 1/2 cdot ( pr [x_i | z_i = a , theta] + pr [x_i | z_i = b, theta]). $$

Paso electrónico

De acuerdo ... eso no fue tan divertido, pero podemos comenzar a hacer un trabajo ahora. El algoritmo EM comienza haciendo una suposición aleatoria por $ theta $. En este ejemplo tenemos $ theta^0 = (0.6,0.5) $. Computamos $$ 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 0.4 ^5) + (0.5^5 CDOT 0.5^5))} aprox 0.45. $$ Este valor se alinea con lo que hay en el papel. Ahora podemos calcular el número esperado de cabezas en $ x_1 = (H, T, T, H, H, T, H, T, H) $ de Coin $ A $, $$ e [ text {cabezas de monedas} a | X_1, theta] = h_1 cdot pr [z_1 = a | x_1, theta] = 5 cdot 0.45 aprox 2.2. $$ haciendo lo mismo para monedas $ b $ obtenemos, $$ e [ e [ # text {Heads by Coin} b | X_1, theta] = h_1 cdot pr [z_1 = b | x_1, theta] = 5 cdot 0.55 aprox 2.8. $$ Podemos calcular lo mismo para el número de colas sustituyendo $ h_1 $ por $ 10 - H_1 $. Esto continúa para todos los demás valores de $ x_i $ y $ h_i $ $ 1 leq i leq 5 $. Gracias a la linealidad de la expectativa, podemos descubrir $$ e [# text {Heads by Coin} a | x, theta] = sum_ {i = 1}^5 e [ text {Heads by moneda} a | X_i, theta] $$

M-paso

Con nuestros valores esperados en la mano, ahora viene el paso M en el que queremos maximizar $ theta $ dados nuestros valores esperados. ¡Esto se hace por normalización simple! $$ theta_a^1 = frac {e [# text {Heads Over} x text {by Coin} a | x, theta]} {e [ text {Heads and Tails Over} x texto {por monedas} a | x, theta]} = frac {21.3} {21.3 + 9.6} aprox 0.71. $$ también por $ b $. Este proceso comienza nuevamente con el paso E y $ theta^1 $ y continúa hasta que los valores para $ theta $ converge (o con algún umbral permitido). En este ejemplo tenemos 10 iteraciones y $ hat { theta} = theta^{10} = (0.8, 0.52) $. En cada iteración, el valor de $ pr [x, z | theta] $ aumenta, debido a la mejor estimación de $ theta $.

Ahora, en este caso, el modelo era bastante simplista. Las cosas pueden volverse mucho más complicadas con bastante rapidez, sin embargo, el algoritmo EM siempre convergerá, y siempre producirá un estimador de probabilidad máxima $ hat { theta} $. Puede ser un local Estimador, pero para evitar esto 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 más alta probabilidad final).