生成式模型、判别式模型,有向概率图模型(贝叶斯网络)、无向概率图模型(马尔科夫随机场),无监督学习、有监督学习,这些概念都很high-level,而且都是相关的。这一系列概念,穿插在HMM、MEMM、CRF这几个序列标注的常用模型中。其中,还有一些常用的技术,比如EM算法,可以在无监督的情况下,做参数估计,EM算法,其实和K-means算法,本质是类似的,这也是生成式模型的优势之一:可以用EM进行无监督学习。

HMM、MEMM、CRF几个模型间的比较

MEMM和CRF这两个模型,同是判别式模型,不关注如何建模观察变量$X$(在分词、POS等问题中,就是单词序列),而只关注条件概率$P(Y|X)$,带来的好处就是,(1)不用为了tractable地建模$X$,而对$X$做出很强的独立性假设(在朴素贝叶斯和HMM中,对$X$的独立性假设都非常强,要不也不会称之为“朴素”)(2)为了预测当前label,不仅可以使用当前词的特征、还可以使用前后词的特征,特征种类也可以是各种各样的,例如单词前缀、后缀等,虽然这些特征只是线性加和(线性加和其实背后也是有独立性假设的,这也是为什么HMM和CRF称为Generative-Discriminative Pair),但总归比HMM可以使用更多特征。

CRF拥有MEMM的所有优点,同时解决了label bias(标记偏置)问题。标记偏置问题的原因在于,MEMM建模$P(y_1,y_2,…,y_n|X)$时,使用的是局部归一化,即$P(y_1|X) P(y_2|X,y_1) ... P(y_n|X,y_{n-1})$,每个状态转移的概率都是单独model的。这样做的问题在于,假设在训练数据中,状态$a$只会转移到状态$b$。也就是训练得到的模型无论输入$X$是什么,$P(b|a,X)=1$。这会导致熵小的状态,有“不正当的优势”,因为无论输入是什么,你只要把状态想法转移到$a$,后面的概率是1,这样总的概率就会很高。CRF的归一,是全局归一化,这样的“不正当的优势”就不存在了。其实,把总的条件概率,分解为连乘的形式,是没问题的,CRF同样有一阶马尔科夫假设,同样可以做类似的分解,问题出在局部归一化上。

换言之,序列标注的决策应该从全局的角度来做,而不是局部。比如rib的状态序列是0123rob的状态序列是04530是起始状态),只通过第一字母r是不知道该走123这条路还是453这条路的,起决定性作用的是io这两个字母。假如我们训练的打分函数,给r14状态上各打40和60分,给i25状态上各打40和10分。很明显,全局地看,ri更适合012状态序列而非045。但如果我们在每一步的决策中都将分数局部归一化,只让同一个状态向后转移的分数互相比较(归一化),ri012上的得分成了0.4和1,在045上的得分成了0.6和1,40与10的这种对比就被局部归一化抹去了。套用CRF原论文中的一段论述,局部归一化使得我们只能决定“score mass”被分配到后面的状态的比例,而不是总量,这样熵低的状态就会有优势。

MEMMs and other non-generative finite-state models based on next-state classifiers, such as discriminative Markov models (Bottou, 1991), share a weakness we call here the label bias problem: the transitions leaving a given state compete only against each other, rather than against all other transitions in the model. In probabilistic terms, transition scores are the conditional probabilities of possible next states given the current state and the observation sequence. This per-state normalization of transition scores implies a “conservation of score mass” (Bottou, 1991) whereby all the mass that arrives at a state must be distributed among the possible successor states. An observation can affect which destination states get the mass, but not how much total mass to pass on. This causes a bias toward states with fewer outgoing transitions. In the extreme case, a state with a single outgoing transition effectively ignores the observation. In those cases, unlike in HMMs, Viterbi decoding cannot downgrade a branch based on observations after the branch point, and models with statetransition structures that have sparsely connected chains of states are not properly handled. The Markovian assumptions in MEMMs and similar state-conditional models insulate decisions at one state from future decisions in a way that does not match the actual dependencies between consecutive states.

我觉得更深层次的理解这个问题,需要了解Hammersley-Clifford定理,也就是为什么无向概率图模型的概率分布可以写成这种全局归一化的形式(其实MEMM的有向概率图模型和CRF的无向概率图模型是等价的)。

EM算法

EM算法和无监督学习

生成式模型可以在无监督情况下(只有$X$,没有$Y$)进行训练,通过全概率公式,$P(X)$可以写成$\sum_{Y}{P(X,Y)}=\sum_{Y}{P(Y)P(X|Y)}$,利用EM算法,可以解决这种带隐含变量(未观测变量)$Y$的MLE问题。而判别式模型只能在有监督情况下训练,因为没有$Y$,根本无法估计$P(Y|X)$中的参数。

EM算法是一种优化算法

解决带隐含变量的$P(X)$的MLE问题,有好多种方法,比如GD,EM算法是另外一种。为什么需要EM?在概率限制下(概率求和为1),最大化$P(X)$,使用拉格朗日乘子法,算得每个参数的解不就得了么?但实际情况是,多个样本,要最大化$P(X^{(1)}) P(X^{(2)}) … P(X^{(N)})$,由于计算机浮点数有下限,所以要取$\log$,最后的优化目标是$\sum_{n=1}^{n=N}{\log{\sum_{Y^{n}}{P(Y^{n})P(X^{n}|Y^{n})}}}$。这里有log-sum,是得不到所有参数的解析解的。这种硬解的方法行不通,我们得想法绕过这个log-sum。

如果我们知道每个$X$对应的隐含变量,上面的sum就没了,我们就可以直接处理“全数据分布”$P(X,Y)$,而不是通常来说更复杂的“部分数据分布”$P(X)$。但是我们毕竟不知道隐含变量,只能最大化$P(X)$,那我们就来看看$\log{P(X,Y)}$和$\log{P(X)}$的关系。

$\log{P(X,Y|\theta)} = \log{P(X|\theta)} + \log{P(Y|X,\theta)}$

假设我们目前的参数是$\theta^{(t)}$,我们下一步想找一个$\theta^{(t+1)}$,使得$\log{P(X|\theta^{(t+1)})}-\log{P(X|\theta^{(t)})}$大于零,就可以达到一步一步优化的目的了。

$\log{P(X|\theta)} - \log{P(X|\theta^{(t)})} = \log{P(X,Y|\theta)} - \log{P(X,Y|\theta^{(t)})} + \log{\frac{P(Y|X,\theta^{(t)})}{P(Y|X,\theta)}}$

上面的式子,左面不好最大化(log-sum),右面的$(1)=\log{P(X,Y|\theta)} - \log{P(X,Y|\theta^{(t)})}$很好进行最大化(没有log-sum),右边的$(2)=\log{\frac{P(Y|X,\theta^{(t)})}{P(Y|X,\theta)}}$不好最大化(因为$P(Y|X,\theta)$还是要利用贝叶斯公式和全概率公式转化为log-sum的形式)。所以如果能消掉$(2)$就好了。这个地方就用到了信息熵和KL距离。左右同时对$P(Y|X,\theta^{(t)})$求期望,得到:

$\log{P(X|\theta)} - \log{P(X|\theta^{(t)})} = E_{P(Y|X,\theta^{(t)})}(\log{P(X,Y|\theta)} - \log{P(X,Y|\theta^{(t)})}) + E_{P(Y|X,\theta^{(t)})}\log{\frac{P(Y|X,\theta^{(t)})}{P(Y|X,\theta)}}$

上面式子右边最后一项是计算的是$P(Y|X,\theta^{(t)})$和$P(Y|X,\theta)$两个分布的KL距离,只有当两个分布完全一样的时候(也就是$\theta = \theta^{(t)}$)时为0,其他时候都是严格大于0的(Jensen inequality定理)。经过这样的操作,我们找到了$log{P(X|\theta)}$在$\theta^{(t)}$位置的“严格下界”(严格指的是下界在$\theta^{(t)}$与原目标相等,注意不严格是不足以保证优化下界就可以优化原目标的,下面的式子去掉了上式中的常数):

$E_{P(Y|X,\theta^{(t)})}\log{P(X,Y|\theta)}$

这就是EM算法中的Q函数,只要最大化它,就可以提高$\log{P(X|\theta)}$。EM中的E步骤,相当于在当前$\theta^{(t)}$下,确定下界函数(下图中的蓝线和绿线);M步更新参数得到$\theta^{(t+1)}$以最大化Q函数(找到下图中蓝线和绿线的最高点)。所以整个算法是一个迭代爬山的过程。PRML中的第8章,用混合高斯模型作为例子,从浅到深用三种不同的角度,介绍了EM算法。

EM算法和K-means聚类

如果我们把$Y$看成类别标签(例如词性标注问题中的词性,或者混合高斯模型中的不同高斯分布),EM算法可以看成是一种“软”聚类算法,因为在E步,我们算出了每个样本$X$属于每个类的概率(每个类的后验概率),而K-means算法是“硬”聚类算法。对比两个算法的步骤,我们会发现,两者非常相似。

K-means(EM):

  1. 将每个样本分配到最近的一个类(计算每个样本属于每个类的概率)
  2. 更新类中心(更新参数)

更准确地说,K-means算法是混合高斯模型的特例。混合高斯模型的假设是:数据点来源于$K$个高斯分布,各个高斯分布的方差(高维下为协方差矩阵)$\delta$,均值$\mu_1, …, \mu_K$,和先验概率$\pi_1, …, \pi_K$是待估计参数。在协方差矩阵$\delta = a I$(类为球型)且$a \rightarrow 0$(趋向于“硬”聚类)时,混合高斯模型就退化为K-means聚类,具体证明可以参考PRML中的9.3.2节。

em

参考资料:

  1. Discriminative Modeling vs Generative Modeling
  2. Lable Bias. Ramesh Nallapati
  3. Lafferty J, McCallum A, Pereira F. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. Proceedings of the eighteenth international conference on machine learning, ICML. 2001, 1: 282-289.
  4. A Note on the Expectation-Maximization (EM) Algorithm. Chengxiang Zhai
  5. EM, KMeans, Mixture of Gaussians. Tom M. Mitchell
  6. Maximum Entropy Modeling
  7. Hammersley-Clifford theorem for Markov random fields (proof). David Pollard