​

17. 条件随机场（Conditional Random Field，CRF）

17.1. 背景

  机器学习分类模型中，有硬分类和软分类两种主流思想，其中硬分类模型有支持向量机SVM（最大化几何间隔）、感知机PLA（误差驱动优化）、线性判别分析LDA（类间大，类内小）等，通过严格的决策边界来区分多类样本；而软分类模型有逻辑回归（及Softmax回归等）和朴素贝叶斯模型等。

  同时机器学习分类模型也有概率生成模型和概率判别模型两种思想：

• 软分类中的逻辑回归是概率判别模型，优化思想是最大熵（见另一篇笔记机器学习 [白板推导]（六）8.4.，给定均值和方差而无其他信息时，熵值最大的分布是高斯分布，同时最大熵思想是使模型贴近已有样本，而样本无法提供的信息使其尽量服从高斯分布）。
• 朴素贝叶斯是概率生成模型，并从中衍生出了隐马尔可夫模型（可以看做时序版本的朴素贝叶斯，同时认为每个观测变量每个时刻都有一个隐状态，为了求解这个隐状态，引入了齐次马尔可夫假设和观测独立假设）。

  从软分类的概率生成模型和概率判别模型的研究成果中，结合了最大熵思想和隐马尔可夫模型的优点，诞生了最大熵马尔可夫模型（Maximum Entropy Markov Model，MEMM），这是一个概率判别模型，即求解的问题是 $P(Y|X)$，同时是一种新的马尔可夫模型，其引入了一个全局变量，使得观测独立假设被打破，这在实际问题中更加合理，样本信息被更多地利用。

  上述图中阴影部分为MEMM求解过程的的一个步骤，即 $P(y_2|x_2,y_1)$，但这样的条件概率求出以后需要进行归一化才能使其符合概率分布特性（求和为1），这样的操作为局部归一化，但每次归一化时没有考虑全局信息，会导致标签偏差问题（Label Bias Problem），而将MEMM的概率图模型变为无向图即可解决这个问题，因此诞生了条件随机场CRF。

  标签偏差问题是在Learning问题有效收敛的前提下，decoding任务中出现了明显偏差的现象，因为MEMM和CRF中的隐状态常常是标签（用 $y_t$ 表示，例如词性标注中具体词语是观测变量，词性如名词、动词、形容词为隐变量），因此叫做标签偏差问题

  举例来说：

• 在经典的John Lafferty论文中的例子是：
  • 假如样本数据有15个 $r\to i\to d$，5个 $r\to o\to d$，忽视发射矩阵，仅考虑状态转移，那么在Learning阶段，理想的概率图模型应该如下图所示，此时在decoding阶段，给定观测变量 $r\to o\to d$，得到 $i_2\to i_4\to i_5$ 的隐变量序列。
    
  • 但如果在o2位置有更多的隐变量取值空间，则Learning阶段可能学习到下图所示的，则在decoding阶段给定观测变量 $r\to o\to d$ 时，会在第一步走向 $i_1$ 的路径，从而得到 $i_1\to i_3\to i_5$ 的隐变量序列，这显然是不正确的。
    
• 西湖大学NLP课程中给出例子为：如下图，根据频率统计，d4出现了2次，比d6频率更高，但根据维特比算法求出二者的概率，却是d6比d4概率高，因为l3有两种转移的可能，即便两种可能出现的频率更高（l2→l1有2次，l3→l3有2次），但经过归一化后都为0.5的概率值，而l2只有一种转移的可能，即便出现频率低（只有l2→l2有1次），但经过归一化后概率值依然为1，因此d6算得的概率更高，这种现象本质上是局部归一化导致的。
  
• Toutanova在论文中也讨论了标签偏差现象的原因，提出有一种情况是发射概率过高，例如下图同样是词性标注问题，Will to fight是句子，是观测变量，NN MODAL TO VB是词性（NN指名词，MODAL指情态动词，TO指to专属词性，VB指动词），而MEMM在decoding任务中需要计算的是，而因为TO是to的专属词性，因此只要见到t时刻观测变量为to即可直接标注词性为TO，无需纳入前一时刻Will的词性作为考虑，这样的模型Learning阶段会无法学习到NN→TO和MODAL→TO之间的状态转移关系，而事实上情态动词后面是基本不搭配to的，因此对Will的词性出现了标签偏差问题，这样的问题本质上也是对to→TO的发射概率进行了局部归一化所导致。
  

  因此CRF将MEMM改为无向图连接，使得局部归一化变为了全局归一化，解决了标签偏差问题，同时打破了齐次马尔可夫假设，使得模型更加有效地利用信息。

17.2. CRF的概率密度函数——Decoding

17.2.1. 无向图模型的概率密度函数

  团：对于一个无向图，其中某个子图满足各个节点相互连通，则作为原无向图的一个团，而对于一个团，若其无法添加一个新节点使其变为一个更大的团（也不能等于原无向图），则称为最大团。

  概率因子分解法：

• 对于一个无向图形式的概率图模型，要求解其概率密度函数时，常常用到概率因子分解法，具体来说是找到图模型的所有最大团，对每个最大团求解势函数，相乘并归一化得到概率密度函数。
• 公式：设概率图模型中所有变量集合为 X={x1,x2,⋯,xm}X=\{ x_1,x_2,\cdots,x_m\}X={x1​,x2​,⋯,xm​}，每个 $x_i$ 为一个节点，对图划分得到$K$个最大团 C={c1,⋯,cK}C=\{ c_1,\cdots,c_K \}C={c1​,⋯,cK​}，每个团的势函数为 ${\Psi }_i(x_j\in c_i)$，则联合概率密度为 $P(X)=\frac{1}{Z}{\prod }_{i=1}^K{\Psi }_i(x_j\in c_i)$，其中归一化因子 $Z={\int }_X{\prod }_{i=1}^K{\Psi }_i(x_j\in c_i)dX$.
• 举例：
  

  可以进一步简化概率因子分解的公式：P(X)=1Z∏i=1KΨi(xj∈ci)=1Z∏i=1Kexp⁡{−Ei(xj∈ci)}P(X)=\frac{1}{Z}\prod_{i=1}^K\Psi_i(x_j\in c_i)=\frac{1}{Z}\prod_{i=1}^K\exp\{-E_i(x_j\in c_i)\}P(X)=Z1​∏i=1K​Ψi​(xj​∈ci​)=Z1​∏i=1K​exp{−Ei​(xj​∈ci​)}，其中 $E(x)$ 为能量函数，再设 $F(x)=-E(x)$，则 P(X)=1Z∏i=1Kexp⁡{Fi(xj∈ci)}=1Zexp⁡[∑i=1K{Fi(xj∈ci)}]P(X)=\frac{1}{Z}\prod_{i=1}^K\exp\{F_i(x_j\in c_i)\}=\frac{1}{Z}\exp\left [\sum_{i=1}^K\{F_i(x_j\in c_i)\} \right ]P(X)=Z1​∏i=1K​exp{Fi​(xj​∈ci​)}=Z1​exp[∑i=1K​{Fi​(xj​∈ci​)}].

17.2.2. CRF的概率密度函数（参数形式）

  下图是一个典型的CRF概率图，其中每个最大团是 ct={yt−1,yt,x1:T}c_t=\{ y_{t-1},y_t,x_{1:T} \}ct​={yt−1​,yt​,x1:T​}，三个节点组成。

  由概率因子分解可得，P(Y∣X)=1Zexp⁡[∑t=1T{Ft(yt−1,yt,x1:T}]P(Y|X)=\frac{1}{Z}\exp\left [\sum_{t=1}^T\{F_t(y_{t-1},y_t,x_{1:T}\} \right ]P(Y∣X)=Z1​exp[∑t=1T​{Ft​(yt−1​,yt​,x1:T​}]，因为decoding问题中观测变量 $x_{1:T}$ 给定，则可以写作 $F_t(y_{t-1},y_t,x_{1:T})=F(y_{t-1},y_t)=F_a(y_{t-1})+F_b(y_t)+F_c(y_{t-1},y_t)$.

  由于在计算 $F_t$ 时，$y_{t-1}$ 已知，所以只关注 $F_b(y_t)$ 和 $F_c(y_{t-1},y_t)$；其中 $F_b(y_t)$ 所表达的信息比较类似HMM中的发射矩阵，而 $F_c(y_{t-1},y_t)$ 类似状态转移矩阵，可以通过这个思路来设计合理的函数使得模型更加合理和有效，例如设 $F_b(y_t)={\sum }_{i=1}^K{\eta }_i\cdot g_i(y_t)$，$F_a(y_{t-1})+F_c(y_{t-1},y_t)={\sum }_{i=1}^L{\lambda }_i\cdot f_i(y_{t-1},y_t)$，其中根据应用场景设计 $f_i(\cdot )$ 和 $g_i(\cdot )$，而将 ${\lambda }_i$ 和 ${\eta }_i$ 作为可学习参数，这就完成参数形式的概率密度函数。

  整理参数形式的概率密度函数为：
$$\begin{array}{rl}P(Y|X)& =\frac{1}{Z}\exp \left\{\sum _{t=1}^T\left[\sum _{i=1}^K{\eta }_i\cdot g_i(y_t)+\sum _{i=1}^L{\lambda }_i\cdot f_i(y_{t-1},y_t)\right]\right\}\\ & =\frac{1}{Z}\exp \left\{\sum _{t=1}^T\left[{\vec{\eta }}^T\cdot \vec{g}(y_t)+{\vec{\lambda }}^T\cdot \vec{f}(y_{t-1},y_t)\right]\right\},\end{array}\text{\hspace{1em}(17.1)}$$其中 η⃗={η1,η2,⋯,ηK}T\vec{\eta}=\{ \eta_1,\eta_2,\cdots,\eta_K \}^Tη​={η1​,η2​,⋯,ηK​}T，g⃗(⋅)={g1(⋅),g2(⋅),⋯,gK(⋅)}T\vec{g}(\cdot)=\{g_1(\cdot),g_2(\cdot),\cdots,g_K(\cdot) \}^Tg​(⋅)={g1​(⋅),g2​(⋅),⋯,gK​(⋅)}T，$\vec{\lambda }$ 和 $\vec{f}(\cdot )$ 同理.

17.3. CRF的边缘概率密度——Smoothing

  在Decoding中求出概率密度函数 $P(Y|X)$，还需要求解边缘概率密度函数 $P(y_t|X)$，先直接写出公式
$$\begin{array}{rl}P(y_t|X)& ={\int }_{y_1,\cdots ,y_{t-1},y_{t+1},\cdots ,y_T}P(Y|X)\\ & ={\int }_{y_1,\cdots ,y_{t-1},y_{t+1},\cdots ,y_T}\frac{1}{Z}\prod _{i=1}^T{\Psi }_i(y_{i-1},y_i,X),\end{array}\text{\hspace{1em}(17.2)}$$
这个连乘与积分的计算是非常复杂的（指数级时间复杂度），需要使用动态规划方法递推求解。

  拆解 $P(y_t|X)={\int }_{y_1,\cdots ,y_{t-1}}{\int }_{y_{t+1},\cdots ,y_T}\frac{1}{Z}{\prod }_{i=1}^T{\Psi }_i(y_{i-1},y_i,X)$，则可以令 ${\alpha }_t(y_t)={\int }_{y_1,\cdots ,y_{t-1}}{\prod }_{i=1}^t{\Psi }_i(y_{i-1},y_i,X)$，${\beta }_t(y_t)={\int }_{y_{t+1},\cdots ,y_T}{\prod }_{i=t+1}^T{\Psi }_i(y_{i-1},y_i,X)$，因此 $P(y_t=i|X)={\alpha }_t(i)\cdot {\beta }_t(i)$.

  建立递推关系（也是一种前向后向算法）：
$$\begin{array}{rl}{\alpha }_t(y_t)& ={\int }_{y_1,\cdots ,y_{t-1}}\prod _{i=1}^t{\Psi }_i(y_{i-1},y_i,X)\\ & ={\int }_{y_{t-1}}{\Psi }_t(y_{t-1},y_t,X)\left[{\int }_{y_{t-2}}{\Psi }_{t-1}(y_{t-2},y_{t-1},X)\left[\cdots \left[{\int }_{y_2}{\Psi }_2(y_1,y_2,X)\left[{\int }_{y_1}{\Psi }_1(y_0,y_1,X)\right]\right]\right]\right]\\ & ={\int }_{y_{t-1}}{\Psi }_t(y_{t-1},y_t,X)\cdot {\alpha }_{t-1}(y_{t-1}).\end{array}\text{\hspace{1em}(17.3)}$$
$$\begin{array}{rl}{\beta }_t(y_t)& ={\int }_{y_{t+1},\cdots ,y_T}\prod _{i=t+1}^T{\Psi }_i(y_{i-1},y_i,X)\\ & ={\int }_{y_{t+1}}{\Psi }_{t+1}(y_t,y_{t+1},X)\left[{\int }_{y_{t+2}}{\Psi }_{t+2}(y_{t+1},y_{t+2},X)\left[\cdots \left[{\int }_{y_{T-1}}{\Psi }_{T-1}(y_{T-2},y_{T-1},X)\left[{\int }_{y_T}{\Psi }_T(y_{T-1},y_T,X)\right]\right]\right]\right]\\ & ={\int }_{y_{t+1}}{\Psi }_{t+1}(y_t,y_{t+1},X)\cdot {\beta }_{t+1}(y_{t+1}).\end{array}\text{\hspace{1em}(17.4)}$$

17.4. CRF的参数估计——Learning

  CRF的Learning就是根据已有的样本数据来最大化似然函数，即 $\theta =<\vec{\lambda },\vec{\eta }>=\underset{\vec{\lambda },\vec{\eta }}{\mathrm{argmax}}{\prod }_{i=1}^{N}P(Y^{(i)}|X^{(i)})$，等价于求对数似然函数
$$\begin{array}{rl}<\vec{\lambda },\vec{\eta }>& =\underset{\vec{\lambda },\vec{\eta }}{\mathrm{argmax}}\log \prod _{i=1}^N\frac{1}{Z^{(i)}}\exp \left\{\sum _{t=1}^T\left[{\vec{\eta }}^T\cdot \vec{g}(y_t^{(i)})+{\vec{\lambda }}^T\cdot \vec{f}(y_{t-1}^{(i)},y_t^{(i)})\right]\right\}\\ & =\underset{\vec{\lambda },\vec{\eta }}{\mathrm{argmax}}\sum _{i=1}^N\left\{-\log Z^{(i)}(X^{(i)},\vec{\lambda },\vec{\eta })+\sum _{t=1}^T\left[{\vec{\eta }}^T\cdot \vec{g}(y_t^{(i)})+{\vec{\lambda }}^T\cdot \vec{f}(y_{t-1}^{(i)},y_t^{(i)})\right]\right\}.\end{array}\text{\hspace{1em}(17.5)}$$

  对上述最大化似然函数，可以使用梯度上升法逼近数值解，即
$${▽}_{\vec{\lambda }}=\sum _{i=1}^N-\frac{1}{Z^{(i)}}\frac{\partial Z^{(i)}}{\partial \vec{\lambda }}+\sum _{i=1}^N\sum _{t=1}^T\vec{f}(y_{t-1}^{(i)},y_t^{(i)})$$其中 $Z^{(i)}={\int }_Y\exp \left\{{\sum }_{t=1}^T\left[{\vec{\eta }}^T\cdot \vec{g}(y_t^{(i)})+{\vec{\lambda }}^T\cdot \vec{f}(y_{t-1}^{(i)},y_t^{(i)})\right]\right\}dY$，则
$$\begin{array}{rl}\sum _{i=1}^N-\frac{1}{Z^{(i)}}\frac{\partial Z^{(i)}}{\partial \vec{\lambda }}& =\sum _{i=1}^N-{\int }_Y\underset{P(Y^{(i)}|X^{(i)})}{\underbrace{\frac{\exp \left\{{\sum }_{t=1}^T\left[{\vec{\eta }}^T\cdot \vec{g}(y_t^{(i)})+{\vec{\lambda }}^T\cdot \vec{f}(y_{t-1}^{(i)},y_t^{(i)})\right]\right\}}{Z^{(i)}}}}\cdot \vec{f}(y_{t-1}^{(i)},y_t^{(i)})dY\\ & =\sum _{i=1}^N-E\left[\vec{f}(y_{t-1}^{(i)},y_t^{(i)})\right].\end{array}\text{\hspace{1em}(17.6)}$$

  因为
$$\begin{array}{rl}{\int }_{Y}P(Y|X)\cdot \vec{f}(y_{t-1},y_t)dY& ={\int }_{y_1}\cdots {\int }_{y_T}\left[P(y_1,\cdots ,y_T|X)\cdot \vec{f}(y_{t-1},y_t)\right]d{y}_1\cdots d{y}_T\\ & ={\int }_{y_{t-1}}{\int }_{y_t}\left[P(y_{t-1},y_t|X)\cdot \vec{f}(y_{t-1},y_t)\right]d{y}_{t-1}d{y}_t,\end{array}\text{\hspace{1em}(17.7)}$$其中 $P(y_{t-1},y_t|X)$ 可以用前向后向算法求得（见上文17.3），将该式带入上一步，可以求得 ${▽}_{\vec{\lambda }}$，则 ${▽}_{\vec{\eta }}$ 也可以同理计算。
​