机器学习 - 条件随机场

作者: nlpming | 来源:发表于2021-11-06 12:42 被阅读0次

1. 条件随机场模型

条件随机场是一种判别式模型，直接对 $p(y|x)$ 进行建模；条件随机场假设 $\color{blue}{p(x,y) \propto exp(w \cdot \phi(x,y))}$ ；其中 $\phi(x,y)$ 是特征向量； $w$ 是特征向量对应的权重，从训练数据中学习得到；
$p(y|x) = \frac{p(x,y)}{\sum_{y'} p(x, y')} = \frac{exp(w \cdot \phi(x,y))} {\sum_{y' \in Y} exp(w \cdot \phi(x,y'))} = \frac{exp(w \cdot \phi(x,y))}{Z(x)}$

2. CRF与HMM的关系

2.1 HMM模型

对于HMM模型直接对联合概率 $p(x,y)$ 进行建模：下式中 $p(y_1|start)$ 表示初始概率； $p(y_{l+1}|y_l)$ 表示转移概率； $p(x_l|y_l)$ 表示发射概率；
$p(x,y) = p(y_1|start) \prod_{l=1}^{l-1}p(y_{l+1}|y_l) p(end|y_L) \prod_{l=1}^{L} p(x_l|y_l)$
对上式取log可以将相乘变成相加：
$log p(x,y) = logp(y_1|start) + \sum_{l=1}^{l-1} logp(y_{l+1}|y_l) + logp(end|y_L) + \color{blue}{\sum_{l=1}^{L} logp(x_l|y_l)}$

2.2 发射概率 $p(x_l|y_l)$

对于上述蓝色部分的发射概率公式，可以表示成如下形式：其中 $p(t|s)$ 为给定标签 $s$ ，其单词为 $t$ 的概率； $N_{s,t}(x,y)$ 表示在样本 $(x,y)$ 中 $s,t$ 共同出现的次数； $\sum_{s,t}$ 表示枚举语料中所有可能的 $s,t$ 的组合；
$\sum_{l=1}^{L} logp(x_l|y_l) = \sum_{s,t} \color{blue}{logp(t|s)} \times \color{red}{N_{s,t}(x,y)}$

发射概率另外一种表达方式.png

2.3 HMM模型转换

对HMM中所有的概率项进行转换，可以得到如下形式：
$\begin{align} log(y_1|start) &= \sum_s \color{blue}{logp(s|start)} \times \color{red}{N_{start,s}(x,y)} \\ \sum_{l=1}^{L-1} logp(y_{l+1}|y_l) &= \sum_{s,s'} \color{blue}{logp(s'|s)} \times \color{red}{N_{s,s'}(x,y)} \\ logp(end|y_L) &= \sum_s \color{blue}{logp(end|s)} \times \color{red}{N_{s,end}(x,y)} \\ \sum_{l=1}^{L} logp(x_l|y_l) &= \sum_{s,t} \color{blue}{logp(t|s)} \times \color{red}{N_{s,t}(x,y)} \end{align}$
从下图可以看出，HMM模型可以表示成如下形式： $\color{blue}{ p(x,y) = exp(w \cdot \phi(x,y)) }$

HMM模型另外一种表达.png

2.4 HMM vs CRF模型

从下图可以看出CRF模型其实跟HMM模型是一样的，只是CRF模型可以自定义各种特征；

CRF模型 vs HMM模型.png

3. CRF转移特征&状态特征

转移特征定义了隐状态之间的关系，对于词性标注问题即（tag, tag）之间的关系；状态特征定义了（word, tag）之间的关系；
对于一个单一的样本，状态特征定义如下表所示：假设总共有 $|S|$ 个可能的tag， $|L|$ 可能的word，则最终的状态特征的数量为： $|S| \times |L|$ ；

状态特征.png

转移特征定义如下表所示：

转移特征.png
转移特征的数量为： $|S| \times |S| + 2|S|$ ；条件随机场的优势在于，你可以自定义所有可能的特征；

image.png

4. 条件随机场训练目标

假设给定训练集： $\{(x^1,\hat{y}^1), (x^2,\hat{y}^2), (x^3,\hat{y}^3), ..., (x^N,\hat{y}^N) \}$ ；
条件随机场的目标是：找到特征向量 $w^*$ ，是的目标函数 $O(w)$ 最大化；为了最大化目标函数 $O(w)$ ，则需要将 $p(x^n, \hat{y}^n)$ （训练语料中出现的组合）最大化，并且使得 $\sum_{y'} p(x^n, y')$ （训练语料中没有出现的组合）最小化；
$\begin{align} p(y|x) &= \frac{p(x, y)}{\sum_{y'} p(x, y')} \\ w^* &= \arg\max_w O(w) \\ O(w) &= \sum_{n=1}^{N} log p(\hat{y}^n|x^n) \\ log p(\hat{y}^n|x^n) &= log p(x^n, \hat{y}^n) - log \sum_{y'} p(x^n, y') \end{align}$
条件随机场模型的学习算法可以采用：改进的迭代尺度法（IIS）、梯度下降法、拟牛顿法（BFGS）；

5. 条件随机场预测

条件随机场预测目标是找到 $y$ ，使得 $p(y|x)$ 最大化；也可以使用维特比算法进行求解；
$\begin{align} y^* &= \arg\max_{y \in Y} p(y|x) \\ &= \arg\max_{y \in Y} w \cdot \phi(x, y） \end{align}$
条件随机场预测的维特比算法如下：

输入：模型特征向量 $F(x,y)$ 和权值向量 $w$ ，观测序列 $x = (x_1, x_2, ..., x_n)$ ；
输出：最优路径 $y^* = (y_1^*, y_2^*, ..., y_n^*)$ ；其中 $m$ 表示标签的数量；
（1）初始化
$\delta_1(j) = w \cdot F_1(y_0=start, y_1=j, x), \quad j=1,2,...,m$
（2）递推，对 $i = 2,3,...,n$
$\delta_i(l) = \max_{1 \leq j \leq m} \left\{ \delta_{i-1}(j) + w \cdot F_i(y_{i-1}=j, y_i=l, x) \right\}, \quad l=1,2,...,m$
$\psi_i(l) = \arg\max_{1 \leq j \leq m} \left\{ \delta_{i-1}(j) + w \cdot F_i(y_{i-1}=j, y_i=l, x) \right\}, \quad l=1,2,...,m$
（3）终止
$\max_{y} \left( w \cdot F(y,x) \right) = \max_{1 \leq j \leq m} \delta_n(j)$
$y_n^* = \arg\max_{1 \leq j \leq m} \delta_n(j)$
（4）返回路径
$y_i^* = \psi_{i+1}(y_{i+1}^*), \quad i=n-1, n-2, ..., 1$
求得最优路径： $y^* = (y_1^*, y_2^*, ..., y_n^*)$