第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)

Data-Intensive Text Processing with MapReduce ch6.1

View more presentations from Sho Shimauchi.

補足: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^{'} }$