目录

• EM算法

EM算法

参考https://blog.csdn.net/fuqiuai/article/details/79484421

分布式的EM，以PLSI为例，看google www07发的那篇讲google news的推荐算法的：Google News Personalization: Scalable Online Collaborative Filtering

对于$T$个训练样本来讲，新闻是$s$，用户是$u$，引入一个中间隐变量$z$，就有两个条件概率(CPD, conditional probability distribution)$p(z|u)$和$p(s|z)$，(也就是从u到z再到s)然后就是要最大化条件似然的乘积，也就是要最小化负的经验log风险：

$$L(\theta) = - \frac{1}{T}\sum ^{T}_{t=1}\log(p(s_t|u_t;\theta))$$

而这可以通过EM来解。

E-step计算如下的$Q$值，也就是后验的隐变量的概率：

$$q^*(z;u,s;\hat{\theta}):=p(z|u,s;\hat{\theta})=\frac{\hat{p}(s|z)\hat{p}(z|u)}{\sum_{z\in Z}\hat{p}(s|z)\hat{p}(z|u)}$$

M-step使用上面的Q计算如下分布：

$$\begin{matrix} p(s|z) &= \frac{\sum_uq^*(z;u,s;\hat{\theta})}{\sum_s\sum_uq^*(z;u,s;\hat{\theta})}\\ p(z|u) &= \frac{\sum_sq^*(z;u,s;\hat{\theta})}{\sum_z\sum_sq^*(z;u,s;\hat{\theta})} \end{matrix}$$

其中的$\hat{p}$指的是上一轮EM迭代产出的$p$。

假设M=N=1kw，L=1000,也就是1kw个user，1kw个item，然后有1000个隐变量，那么需要存$(M+N)\times L\times 4=80GB$的内存来存储两个CPD(假设double占4字节)。单机是不行的，搞成分布式的。。

加两个中间项：

$$\begin{matrix} N(z,s)=\sum_uq^*(z;u,s;\hat{\theta})\\ N(z)=\sum_s\sum_u^*(z;u,s;\hat{\theta}) \end{matrix}$$

那么，

$$q^*(z;u,s;\hat{\theta}):=p(z|u,s;\hat{\theta})=\frac{\frac{N(z,s)}{N(z)}\hat{p}(z|u)}{\sum_{z\in Z}\frac{N(z,s)}{N(z)}\hat{p}(z|u)}$$

其中，

$$\hat{p}(z|u) = \frac{\sum_sq^*(z;u,s;\hat{\theta})}{\sum_z\sum_sq^*(z;u,s;\hat{\theta})}$$

这样，就可以把$p(s|z)$干掉了

对于每个给定的(u,s)的pair对，计算 $q^*(z;u,s;\hat{\theta}):=p(z|u,s;\hat{\theta})$时，需要之前多轮迭代的信息：$\hat{p}(z|u)$、$N(z,s)$和$N(z)$。当统计信息足够多时，对于一个(u,s)对，计算$q^*$是可以独立且并行的。

我们看一个$R\times K$的shard。假设所有用户被hash到$R$个group里，所有news被hash到$K$个group里。也就是说$(u_1,s_1)$这个pair对，按下图就是被分到了$C_{R3}$这个shard里去了。然后在一个shard中，只要存储这个shard里的所有(u,s)的pair对的点展信息就行了，来计算里面的CPD。所以一个shard需要存的CPD就只有1/R的用户的CPD和1/K的news的CPD。

map输出3个kv：$(u,q^*)$、$(i,q^*)$和$(z,q^*)$。

对于reduce来说，

• 负责s的reduce对所有的z计算$N(z,s)$
• 负责u的reduce计算$p(z|u)$
• 负责z的reduce计算$N(z)$。每一个(u,s)的pair就会产出一条记录给负责z的reduce。。所以可以在shuffle阶段做一些预处理，防止reduce单节点太慢