Aplicando a maximização da expectativa a exemplos de sorteio

Ultimamente, tenho estudado a Maximização de Expectativas e peguei alguns exemplos simples no processo:

A partir daqui : Há três moedas $c_0$ , $c_1$ e $c_2$ com $p_0$ , $p_1$ e $p_2$ a respectiva probabilidade de aterragem na cabeça quando atiradas. Atire $c_0$ . Se o resultado for Cabeça, jogue $c_1$ três vezes, depois jogue $c_2$ três vezes. Os dados observados produzidos por $c_1$ e $c_2$ são assim: HHH, TTT, HHH, TTT, HHH. Os dados ocultos são o resultado de $c_0$ . Estimativa $p_0$ ,$p_1$ e$p_2$ .

E a partir daqui : Há duas moedas $c_A$ e $c_B$ com $p_A$ e $p_B$ sendo a respectiva probabilidade de aterragem na cabeça quando jogou. Cada rodada, selecione uma moeda aleatoriamente e jogue-a dez vezes; registre os resultados. Os dados observados são os resultados do sorteio fornecidos por essas duas moedas. No entanto, não sabemos qual moeda foi selecionada para uma rodada específica. Estimado $p_A$ e $p_B$ .

Embora eu possa obter os cálculos, não posso relacionar as maneiras como eles são resolvidos com a teoria EM original. Especificamente, durante o M-Step de ambos os exemplos, não vejo como eles estão maximizando alguma coisa. Parece que eles estão recalculando os parâmetros e, de alguma forma, os novos parâmetros são melhores que os antigos. Além disso, os dois E-Steps nem se parecem, sem mencionar o E-Step da teoria original.

Então, como exatamente esses exemplos funcionam?

(Esta resposta usa o segundo link que você forneceu.)

$\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 o estimador de probabilidade máxima . O algoritmo Expectation-Maximization (EM) é um desses métodos para encontrar (pelo menos local) . Ele funciona encontrando a expectativa condicional, que é usada para maximizar . A idéia é que, ao encontrar continuamente um mais provável (ou seja, mais provável) em cada iteração, aumentaremos continuamente que, por sua vez, aumenta a função de probabilidade. Há três coisas que precisam ser feitas antes de seguir adiante, projetando um algoritmo baseado em EM. q qqPr[X,Z| θ$\hat{\theta}$$\hat{\theta}$$\theta$$\theta$$\Pr[X,Z|\theta]$

1. Construa o modelo
2. Calcular expectativa condicional no modelo (E-Step)
3. Maximize nossa probabilidade atualizando nossa estimativa atual de (M-Step)$\theta$

Construir o modelo

Antes de avançarmos com o EM, precisamos descobrir exatamente o que estamos computando. Na etapa E, estamos computando exatamente o valor esperado para . Então, qual é esse valor, realmente? Observe que O motivo é que temos cinco experimentos para explicar e não sabemos qual moeda foi usada em cada uma. A desigualdade é devido 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$sendo côncavo e aplicando a desigualdade de Jensen. A razão pela qual precisamos desse limite inferior é que não podemos computar diretamente o arg max na equação original. No entanto, podemos calculá-lo para o limite inferior final.

Agora, o que é ? É a probabilidade de vermos a moeda dada a experiência e . Usando probabilidades condicionais, temos,$\Pr[Z_i=C|X_i,\theta]$$C$ θ Pr [ Z i = C | X i , θ ] = Pr [ X i , Z i = C | θ $X_i$$\theta$

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

Embora tenhamos feito algum progresso, ainda não terminamos o modelo. Qual é a probabilidade de uma determinada moeda a sequência ? Deixando Agora é claramente apenas a probabilidade sob as duas possibilidades de ou . Como , temos, h i = # cabeças em  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

Ok ... isso não foi tão divertido, mas podemos começar a trabalhar agora em EM. O algoritmo EM começa fazendo uma suposição aleatória para . Neste exemplo, temos . Calculamos Esse valor está alinhado com o que está no papel. Agora podemos calcular o número esperado de cabeças em da moeda , Fazendo a mesma coisa pela moeda que obtemos, θ $\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 o mesmo para o número de caudas substituindo por . Isso continua para todos os outros valores de e . Graças à linearidade da expectativa, podemos descobrir $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]$$

M-Step

Com nossos valores esperados em mãos, agora vem a etapa M em que queremos maximizar considerando nossos valores esperados. Isso é feito por normalização simples! Da mesma forma para . Esse processo começa novamente com o E-Step e e continua até os valores de convergirem (ou para algum limite permitido). Neste exemplo, temos 10 iterações e . Em cada iteração, o valor de aumenta, devido à melhor estimativa 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$ .

Agora, neste caso, o modelo era bastante simplista. As coisas podem ficar muito mais complicadas rapidamente, no entanto, o algoritmo EM sempre convergirá e sempre produzirá um estimador de probabilidade máxima . Pode ser um estimador local , mas para contornar isso, podemos simplesmente reiniciar o processo EM com uma inicialização diferente. Podemos fazer isso uma quantidade constante de vezes e manter os melhores resultados (ou seja, aqueles com a maior probabilidade final).$\hat{\theta}$