GLADJacob Whitehill在2009年NIPS上提出了一个算法,其本质只是采用简化的Item Response Theory中的模型,利用EM算法求解隐含变量,得到题目正确的答案。

先介绍GLAD要解决的问题,在处理多人图片标注数据时,只采用Majority Vote即认为大多数人选择的答案就是正确答案的方式在题目难度较大时并不能得到好的结果。所以采用Rasch模型来表示每个人回答正确的能力,以正确答案为隐含变量。

形式化的定义这个问题,首先假设要处理的问题为Y/N的二值问题,存在\(N\)个题目,第\(j\)个题目正确答案为\(z_j\),存在\(M\)个工作者,然后我们采用如下形式定义一个第\(i\)个工作者答对第\(j\)个题目的标记答案为\(L_{ij}\),其正确的概率为: \[p(L_{ij}=Z_j|\alpha_i,\beta_j) = \dfrac{1}{1+e^{-\alpha_i\beta_j}}\]

其中\(\alpha_i\)为第i个工作者的能力其范围为\((-\infty,+\infty)\),而\(1/\beta_j\)为第j个题目的难度其范围为\([0,\infty)\)。 图模型为: 我们观测到的标签是由真实标签在通过工作者判断函数后得到的结果,其中真实标签正是我们想要求的隐藏变量,其对数似然应该为 \[p(L|\alpha,\beta)=\sum_i^M{\sum_j^N{\ln\{\sum_l^Kp(z_{l})p(L|\alpha,\beta,z_l)\}}}\] 像常见的高斯混合模型一样,由于隐藏变量作为指示变量存在导致我们在直接使用极大似然的时候容易获得由于\(p(z_l)\)趋向于\(\infty\)而产生的极大值,这显然不是我们愿意见到的情况,何况\(z_j\)的值是我们想要得到的信息。所以我们采用EM算法来解决这个问题。 我们之前遇到的问题是在隐藏变量存在的情况下,我们难以直接极大化似然,我们能不能换种方法直接极大化似然呢? 我们用\(X\)表示观察到变量,\(Z\)表示隐藏变量,而\(\theta\)表示参数,则我们想极大化的似然为 \[p(X|\theta)=\sum_{Z}p(X,Z|\theta)\] 我们先放弃直接优化,利用贝叶斯公式变形,取对数似然.由 \[\ln p(X,Z|\theta)=\ln p(Z|X,\theta)+\ln p(X|\theta)\]\[\ln p(X|\theta)=\ln p(X,Z|\theta)-\ln p(Z|X,\theta)\] 然后我们取一个关于\(Z\)分布\(q(Z)\),注意这里我们并不关心\(q(Z)\)是什么样子,而不对它做任何假设。则上面的式子可以变成 \[\begin{split}\ln p(X|\theta)=& \ln p(X,Z|\theta)-\ln p(Z|X,\theta) \\=&\ln p(X,Z|\theta)-\ln q(Z)-[\ln p(Z|X,\theta)-\ln q(Z)]\\=& \ln \frac{ p(X,Z|\theta)}{q(Z)}-\ln \frac{ p(Z|X,\theta)}{q(Z)} \\\end{split}\]

由于\(q(Z)\)是关于\(Z\)的分布所以应该有\(\sum_Z q(Z)=1\),而且\(Z\)与已经将\(Z\)积分掉的\(p(x|\theta)\)独立,所以我们可以继续将上式先乘以\(q(Z)\)然后对\(Z\)求和。 \[\sum_{z}q(Z) \ln p(X|\theta)=\sum_{z}[q(Z)(\ln \frac{ p(X,Z|\theta)}{q(Z)}-\ln \frac{ p(Z|X,\theta)}{q(Z)})]\] \[\ln p(X|\theta)=\sum_{z}q(Z)\ln \frac{ p(X,Z|\theta)}{q(Z)}-\sum_{z}q(Z)\ln \frac{ p(Z|X,\theta)}{q(Z)}\]

\[\ln p(X|\theta)=\mathcal{L}(q,\theta)+KL(q||p)\]

其中

\[\mathcal{L}(q,\theta)=\sum_{z}q(Z)\ln \frac{ p(X,Z|\theta)}{q(Z)}\] \[KL(q||p)=\sum_{z}q(Z)\ln \frac{ q(Z)}{p(Z|X,\theta)}\]

(很多推断算法中都有这个式子的身影) 现在再看这个式子,先看KL散度的部分,它描述了分布\(q(Z)\)\(p(X,Z|\theta)\)的差距,如果当\(q(Z)\)\(P(Z|X,\theta)\)像相似,我们不妨用\(P(Z|X,\theta)\)来替换\(q(Z)\),为了区分我们把替换的分布写成\(p(Z|X,\theta^{old})\),于是我们可以把\(\mathcal{L}(q,\theta)\)写成

\[\mathcal{L}(q,\theta) = \mathcal{Q}(\theta,\theta^{old})+const\]

其中

\[\begin{split} \mathcal{Q}(\theta,\theta^{old}) = &\sum_zp(Z|X,\theta^{old})\ln p(X,Z|\theta)\\=&E_z[\ln p(X,Z|\theta)]\end{split}\] 这里\(E_Z[\ln p(X,Z|\theta)]是指在分布\)q(Z)下\(\ln p(X,Z|\theta)\)值的期望。 由于后面的一项只和\(q(Z)\)有关所以置换为 \[const=-\sum_Zp(Z|X,\theta^{old})\ln p(Z|X,\theta^{old})\]

这里我们似乎找到了一种在分布\(q(Z)\)\(p(X,Z|\theta)\)很小的情况下,利用\(\mathcal{L}(q,\theta)\)(本质上是利用\(\mathcal{Q}(\theta,\theta^{old})\)或者说\(E_z[\ln p(X,Z|\theta)]\))接近真实\(\ln p(X|\theta)\)的方法。现在还差如何尽量减少\(KL(q||p)\)的部分了。考虑到上面我们想到了固定\(Z\)优化\(\theta\)的方面,优化\(KL(q||p)\)的过程其实就是固定\(\theta\)优化\(Z\),由于KL散度的形式,其实就是优化\(p(Z|X,\theta)\),我们很高兴的发现这次问题简单了很多,由于我们处理的数据中\(X\)中往往是包含独立同分布的\(\{x_n\}\),以及相互独立的指示变量\(\{z_n\}\),所以显然 \[p(Z|X,\theta)=\frac{p(X|Z,\theta)}{\sum_Zp(X,Z|\theta)}=\frac{\prod_{n=1}^{N}p(x_n,z_n|\theta)}{\sum_Z\prod_{n=1}^{N}p(x_n,z_n|\theta)}=\prod^N_{n=1}p(z_n|x_n,\theta)\]

即为了优化KL散度,我们只要让\(z_n\)取在给定\(\theta,x_n\)下的最优值就好了。

至此,需要优化的参数都存在循环依赖,我们只要分步迭代优化就好了,这就是所谓的Expectation Maximization(期望极大化)算法。 (这里采用一个不怎么合理的顺序介绍了EM算法的原理与推导,我也不知道发明算法的是怎么发现这种方法的,不过这是我认为最好理解的顺序)

总结一下,所谓的EM(Expectation Maximization)算法, E步:在给定\(\theta\)的情况下,求得最优的\(\{z_n\}\),以求得\(E_z[\ln p(X,Z|\theta)]\)。本质上也是减少KL的过程。 M步:优化\(\theta\),用来极大化期望\(E_z[\ln p(X,Z|\theta)]\),即极大化\(\mathcal{L}(q,\theta)\)的过程。 《PRML》中的图很好的解释了这个过程。

开始

E步

M步

了解了EM的原理,我们回到GLAD模型的求解问题,有了EM,求解GLAD模型变得十分简单, 在E步,我们要求解每一个\(p(z_j|l,\alpha,\beta)\),由于每个\(\{z_j\}\)都是独立的,采用贝叶斯公式变形,则有 \[\begin{split}p(z_j|l,\alpha,\beta)=&p(z_j|l_j,\alpha,\beta_j) \\ \propto &p(z_j|\alpha,\beta_j)p(l_j|z_j,\alpha,\beta_j)\\ \propto&p(z_j)\prod_ip(l_{ij}|z_j,\alpha_i,\beta_j)\end{split}\]

我们在式子中省略了归一化的项。这里也可以看出\(z_j\)的值是所有完成第\(j\)题的人的选项的在每个人作对概率上的期望。这也符合E步的意义。

在M步中,对于\(Q\)函数,有 \[\begin{split}Q(\alpha,\beta)=&E[\ln p(l,z|\alpha,\beta)]\\ =& E[\ln\prod_j(p(z_j)\prod_i\ln p(l_{ij}|z_j,\alpha_i,\beta_j))] \\=&\sum_jE[\ln p(z_j)]+\sum_{ij}E[\ln p(l_{ij}|z_j,\alpha_i,\beta_j)] \end{split}\]

现在第一项与\(\alpha,\beta\)无关,不是我们关心的,我们只要将最后一项展开,然后利用梯度下降的方法求得最优值就好了。

至此,我们了解了EM算法以及GLAD模型的求解方法。

针对GLAD模型,这是一个相当简单的假设,尤其是那个用户判断正确的模型十分实用,在很多复杂的模型中都使用过,但是GLAD模型在面对多分类的情况显得有些乏力,如果假设工作者在面对非正确答案时采取相同的概率选择答案,这样的假设显然并不合理,如果在不同选项中都加入相应的权值参数以改进效果,会导致参数个数随着工作者与答案选项个数增加的速度太快,这显然不是我们想见到的,所以这种情况下还有另外的建模方式,所谓的confuse matrix。

针对EM算法,还有一些有用的地方。

首先,一开始我们就指出我们要优化的是对数似然,其实在很多时候我们想要采用MAP(极大后验概率)的方式,即: \[\begin{split}\ln p(\theta|X) =& \ln p(\theta,X)-\ln p(X) \\ =&\mathcal{L}(q,\theta)+KL(q||p)-\ln p(X)\end{split}\]

其中\(\ln p(X)\)常数,考虑到\(q\)其实只在\(\mathcal{L}\)中存在,所以在E步上来说,MAP并没有很大的不同,M步由于存在\(\ln p(\theta)\),所以和普通EM差距也不大,实际在GLAD的也好像只是多了一个乘数项(很久之前推的,当时的推导找不到了,反正换成MAP之后,在它数据集上的效果基本没有提高)。

另外一方面,我们意识到EM其实就是在E、M两个步骤分布优化的过程,普通的EM算法希望在M步中获取\(\mathcal{L}\)的极大值,在\(\mathcal{L}\)很复杂的时候,我们难以直接求最优解,此时,我们可以放弃求最优解,转而求较优解,甚至是将参数再分为几个子集,每一次M步骤中分别优化不同的子集,总之,只要我们保证每次迭代之后\(\mathcal{L}\)都比开始接近似然就可以保证整体可以取得更优解。 于此相似的,E步我们也可以采用相似的策略,由于显然在\(mathcal{L}\)取得局部最优解的情况下,\(\ln p(X|\theta)\)显然也应该处于局部最优解,所以我们显然可以将数据集\({x_n}\)分组,采用类似于随机梯度下降的方式迭代EM算法,尤其是在分布本身是指数家族的时候,在M步需要所有数据点的信息时,由于其分布可以通过充分统计量还原,仅仅采用充分统计量迭代往往有着更简单的形式。




X