読者です 読者をやめる 読者になる 読者になる

第4回MapReduce本読書会

第1回 第2,3回

日時 2010/10/17 19:30 - 21:00
場所 都内某所
挑戦者 marqs shiumachi
標的 Data-Intensive Text Processing with MapReduce
範囲 5章残り(marqs), 6.1 (shiumachi)

補足:6.1.5の式の説明

スライドに書いてある内容は省略してます。

前提条件とかも全部すっ飛ばしてますのでまずはスライドの方をご覧ください。

q(x,y;\theta^{(i)} ) を出すためにはまず、 f(x) と全ての Pr(y|x;\theta^{(i)} ) を求める必要があります。
 f(x) は全試行回数における x の相対頻度ですので、

 f(x|\bf{x}) = \frac{ N_x } { N }

となります。次に Pr(y|x;\theta^{(i)} ) ですが、Pr(0|a;\theta^{(i)} )Pr(3|c;\theta^{(i)} ) は明らかに 1 です。

残りの2つは以下の通りです。簡単な確率の話なので説明は省略。

Pr(1|b;\theta^{(i)} ) = \frac{ (1-p_0^{(i)} )p_1^{(i)} } { (1-p_0^{(i)} )p_1^{(i)} + p_0^{(i)} (1-p_2^{(i)} ) }

Pr(2|b;\theta^{(i)} ) = \frac{ p_0^{(i)} (1-p_2^{(i)} ) } { (1-p_0^{(i)} )p_1^{(i)} + p_0^{(i)} (1-p_2^{(i)} ) }

これの結果を元にスライド29枚目の q(x,y;\theta^{(i)} ) \log Pr(y|x;\theta^{(i)} ) を表にしたものがスライド32枚目です。

スライド29枚目のMステップの式より、全ての (x,y) の組み合わせ、すなわち (a,0), (b,1), (b,2), (c,3) についての q(x,y;\theta^{(i)} ) \log Pr(y|x;\theta^{(i)} ) の積の和が q(x,y;\theta^{(i+1)} ) になるわけです。

これを式にすると、

\begin{eqnarray*}q(x,y;\theta^{(i+1)} ) = \frac{ N_a } { N }\{\log (1 - p_0^{'})  + \log (1 - p_1^{'})\} \\ &+& \frac{ N_b } { N } Pr(1|b;\theta^{(i)}) \{\log (1 - p_0^{'}) + \log p_1^{'}\} \\ &+& \frac{ N_b } { N } Pr(2|b;\theta^{(i)}) \{\log p_0^{'} + \log (1 - p_2^{'})\} \\ &+& \frac{ N_c } { N }\{\log p_0^{'} + \log p_2^{'}\}\end{eqnarray*}

ここで、q(x,y;\theta^{(i)} ) = < p_0^{(i)}, p_1^{(i)}, p_2^{(i)} > の 各々の p を独立だと仮定すると、偏微分により全ての p を個別に計算することができます。

以下 p_0 を例にとって偏微分すると、

 \frac{\partial \theta}{\partial p_0} = - \frac{ N_a } { N } \frac{1} { 1 - p_0^{'} } - \frac{ N_b } { N } Pr(1|b;\theta^{(i)})\frac{1} { 1 - p_0^{'} } + \frac{ N_b } { N } Pr(2|b;\theta^{(i)}) \frac{1} { p_0^{'} } + \frac{ N_a } { N } \frac{1} { p_0^{'} }

 \theta を最大にしたいので、上の式が 0 になるような  p_0 の値を求めます。

変形すると、

 p_0 = \frac{ Pr(2|b;\theta^{(i)})N_b + N_c } { N_a + Pr(1|b;\theta^{(i)})N_b + Pr(2|b;\theta^{(i)})N_b + N_c }

ここで分母の和を見ると N になっていますので、

 p_0 = \frac{ Pr(2|b;\theta^{(i)})N_b + N_c } { N }

これでようやく スライド32枚目下部の  p_0 の式が出ました。

同様にすれば、 p_1  p_2 も算出できます。