条件随机场(Conditional Random Field, CRF)是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型。常常用于标注问题。隐马尔科夫模型和条件随机场是自然语言处理中最重要的算法。CRF最重要的就是根据观测序列，把标记序列给推测出来。

概率无向图模型

概率无向图模型又称为马尔科夫随机场，是一个可以由无向图表示的联合概率分布。一些类似内容。

有一组随机变量$Y \in \Gamma$，联合概率分布为$P(Y)$，由图$G=(V,E)$表示。节点v代表变量$Y_v$，节点之间的边代表两个变量的概率依赖关系。

定义

马尔可夫性就是说，给定一些条件下，没有连接的节点之间是条件独立的。

成对马尔可夫性

设$u$和$v$是两个没有边连接的节点，其它所有节点为$O$。成对马尔可夫性是说，给定随机变量组$Y_O$的条件下，随机变量$Y_u$和$Y_v$是独立的。即有如下： \[ P(Y_u, Y_v \mid Y_O) = P(Y_u \mid Y_O)P(Y_v \mid Y_O) \] 局部马尔可夫性

节点$v$，$W$是与$v$连接的所有节点，$O$是与$v$没有连接的节点。局部马尔可夫性认为，给定$Y_w$的条件下，$Y_v$和$Y_O$独立。即有： \[ P(Y_v, Y_O \mid Y_W) = P(Y_v \mid Y_W) P(Y_O \mid Y_W) \] 全局马尔可夫性

节点集合$A$，$B$被中间节点集合$C$分隔开，即不相连。全局马尔可夫性认为，给定$Y_C$的条件下，$Y_A$和$Y_B$是独立的。即有： \[ P(Y_A, Y_B \mid Y_C) = P(Y_A \mid Y_C) P(Y_B \mid Y_C) \] 上面的3个马尔可夫性的定义是等价的。

概率无向图模型

设有联合概率密度$P(Y)$，由无向图$G=(V,E)$表示。节点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率密度$P(Y)$满足马尔可夫性，那么就称此联合概率分布为概率图模型，或马尔可夫随机场。

实际上我们更关心怎么求联合概率密度，一般是把整体的联合概率写成若干个子联合概率的乘积，即进行因子分解。概率无向图模型最大的优点就是易于因子分解。

概率无向图因子分解

团与最大团

团：无向图中的一个子集，任何两个节点均有边连接。

最大团：无向图中的一个子集，任何两个节点均有边连接。不能再加入一个节点组成更大的团了。

如$\{Y_1, Y_2\}$，$\{Y_1, Y_2, Y_3\}$ 都是团，其中后者是最大团。而$\{Y_1, Y_2, Y_3, Y_4\}$ 不是团，因为$Y_1$和$Y_4$没有边连接。

因子分解

有无向图模型$G$, $C$ 是 $G$ 上的最大团，有很多个。$Y_C$ 是$C$ 对应的随机变量。则联合概率分布$P(Y)$ 可以写成多个最大团$C$ 上的势函数的乘积。 \[ \color{blue}{P(Y)} = \frac {1} {Z} \prod_C \Psi_C(Y_C), \quad Z = \sum_Y \prod_C \Psi_C(Y_C) \] 其中$Z$是规范化因子。$\Psi_C(Y_C)$是 势函数，是一个严格正函数。等式左右两端都取条件概率也是可以的。下文就是。 \[ \color{blue}{\Psi_C(Y_C)} = \exp \left(-E(Y_C) \right) \] 其中$\color{blue}{E(Y_C) }$ 是能量函数。

条件随机场的定义与形式

HMM的问题

这里是HMM的讲解。HMM有下面几个问题

需要给出隐状态和观察符号的联合概率分布，即发射概率 $b_j(k)$，是生成式模型，也是它们的通病。
观察符号需要是离散的，可以枚举的，要遍历所有观察符号。如果是一个连续序列，则不行。
观察符号是独立的，没有观察相互之间的依赖关系。如一个句子的前后，都有关联才是。即输出独立性假设问题。
无法考虑除了字词顺序以外的其它特征。比如字母为大小写，包含数字等。
标注偏置问题。

标注偏置问题，举例，是说有两个单词"rib-123"和"rob-456"，"ri"应该标记为"12"，"ro"应该标记为"45"。

\[ \begin {align} & P(12 \mid ri) = P(1 \mid r)P(2 \mid i, r=1) = P(1 \mid r) \cdot 1 = P(1 \mid r) \\ & P(45 \mid ro) = P(4 \mid r)P(5 \mid o, r=4) = P(4 \mid r) \cdot 1 = P(4 \mid r) \\ \end {align} \] 由上面计算概率可知，ri标为12和 ro标为45的概率最终变成r标为1和4的概率。但是由于语料库中"rob"的出现次数很多，所以$P(4 \mid r) > P(1 \mid r)$ ，所以可能会一直把"rib"中的"i"标记为1，会导致标记出错。这就是标记偏置问题。

定义

条件随机场是给定随机变量$X$条件下，随机变量$Y$ 的马尔可夫随机场。我们主要关心线性链随机场，它可以用于标注问题。

条件随机场

$X$与$Y$是随机变量，条件概率分布$P(Y \mid X)$。随机变量$Y$可以构成一个无向图表示的马尔可夫随机场。任意一节点$Y_v$，$Y_A$是与$v$相连接的节点，$Y_B$是除了$v$以外的所有节点。若都有 \[ P(Y_v \mid X, Y_B) = P(Y_v \mid X, Y_A) \] 则称$P(Y \mid X)$ 为条件随机场。并不要求$X$和$Y$ 具有相同的结构。

线性链条件随机场

$X$和$Y$ 有相同的线性结构。设$X = (X_1, X_2, \cdots, X_n)$，$Y = (Y_1, Y_2, \cdots, Y_n)$均为线性链表示的随机变量序列。每个最大团包含2个节点。

$P(Y \mid X)$ 构成条件随机场，即满足马尔可夫性 \[ P(Y_i \mid X, Y_1, \cdots, Y_{i-1}, Y_{i+1}, \cdots, Y_n) = P(Y_i \mid X, Y_{i-1}, Y_{i+1}), \quad i=1,\cdots, n。 \; (1和n时只考虑单边) \] 则称$P(Y \mid X)$为线性链条件随机场。

HMM，每个观察状态只与当前的隐状态有关系，分离了关系。就像1个字1个字地向后讲。输出观察符号还需要条件独立。

线性链条件随机场，每个状态都与整个序列有关系。即先想好了整句话，再依照相应的次序去说出来。更加直击语言模型的核心。$X_1, X_2$ 不需要条件独立。

基本形式

两种特征函数

状态转移特征函数t，只依赖与当前和前一个位置，即$y_i$和$y_{i-1}$。一般是01函数。 \[ t(y_{i-1}, y_i, x, i) = \begin {cases} 1, \quad & 满足某种条件, i \in [2, n]. \;例如y_{i-1}+y_{i}=3 \\ 0, \quad & 其他 \end {cases} \] 状态特征函数s，只依赖与当前位置$y_i$ \[ s(y_i, x, i) = \begin {cases} 1, \quad & 满足某种条件, i \in [1, n]. \;例如y_{i}是偶数 \\ 0, \quad & 其他 \end {cases} \] 基础形式

设有$K_1$个状态特征转移函数，$K_2$个状态特征函数。分别对应的权值是$\lambda_{k_1}$和$\mu_{k_2}$。则线性链条件随机场参数化形式$P(y \mid x)$ 如下： \[ P(y \mid x) = \frac {1}{Z(x)} \exp \left( \sum_k^{K_1}\lambda_k \sum_{i=2}^n t_k(y_{i-1}, y_i, x, i) + \sum_k^{K_2}\mu_k \sum_{i=1}^n s_k(y_i, x, i) \right) \] 其中$Z(x)$是规范化因子，如下 \[ Z(x) = \sum_x \exp \left( \sum_k^{K_1}\lambda_k \sum_{i=2}^nt_k(y_{i-1}, y_i, x, i) + \sum_k^{K_2}\mu_k \sum_{i=1}^n s_k(y_i, x, i) \right) \] 条件随机场完全由特征函数$t_{k_1}$ 、$s_{k_2}$，和对应的权值$\lambda_{k_1}$ 和$\mu_{k_2}$ 决定的。 特征函数实际上也是势函数。

简化形式

有$K=K_1 + K_2$个特征，特征函数如下： \[ f_k(y_{i-1}, y_i, i) = \begin {cases} t_k(y_{i-1}, y_i, x, i) \quad & k = 1, \cdots, K_1 \\ s_k(y_i, x, i) \quad & k = K_1 + l; \; l = 1, \cdots, K_2 \\ \end {cases} \] 同一个特征函数，要在整个$Y$序列的各个位置进行计算，可以进行求和，即转化为全局特征函数， 新的特征函数$f_k (y, x)$如下： \[ \color{blue} {f_k (y, x)} = \sum _{i=1} ^n f_k(y_{i-1}, y_i, i), \quad k = 1, \cdots, K \] $f_k (y, x)$ 对应的新的权值$w_k$如下 \[ \color{blue} {w_k} = \begin {cases} \lambda_{k}, \quad & k = 1, \cdots, K_1 \\ \mu_{k - K_1}, \quad & k = K_1 + 1, K_1 + 2, \cdots, K \\ \end {cases} \] 所以新的条件随机场形式如下： \[ P(y \mid x) = \frac {1} {Z(x)} \exp \sum_{k=1} ^K w_k f_k(y, x) , \quad Z(x) = \sum_y \exp \sum_{k=1} ^K w_k f_k(y, x) \] 可以看出，格式和最大熵模型很像。条件随机场最重要的就是，根据观察序列，把标记序列给推测出来。

向量形式

向量化特征函数和权值 \[ F(y, x) = (f_1(y, x), \cdots, f_K(y, x))^T, \quad w = (w_1, \cdots, w_K)^T \] 可以写成向量内积的形式 \[ P_w (y \mid x) = \frac{1}{Z(x)} \exp (w \cdot F(y, x)) , \quad Z(x) = \sum_y \exp (w \cdot F(y, x)) \]

矩阵形式

为状态序列$Y$设置起点和终点标记，$y_0 = start$ 和$y_{n+1} = stop$。从$0 \to n+1$中，有$n+1$次的状态转移。我们可以用$n+1$ 个状态转移矩阵来表示状态转移的概率。

设$\color{blue}{M_i(x)}$ 是$i-1 \to i$的转移矩阵，是$m$阶，$m$ 是$y_i$ 取值的个数。表示了各种取值情况互相转化的概率。 \[ M_1(x) = \begin{bmatrix} a_{01} & a_{02} \\ 0 & 0 \\ \end{bmatrix} , \; M_2(x) = \begin{bmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \\ \end{bmatrix} , \; M_3(x) = \begin{bmatrix} c_{11} & c_{12} \\ c_{21} & c_{22} \\ \end{bmatrix} , \; M_4(x) = \begin{bmatrix} 1 & 0 \\ 1 & 0 \\ \end{bmatrix} \] 要求什么样的路径概率，则相乘相应的数值概率即可。那么这些矩阵里面的数值是怎么来的呢。有下面的矩阵定义 ： \[ \color{blue} {g(y_{i-1}, y_i, x, i)} = M_i(y_{i-1}, y_i \mid x) = \exp \sum_{k=1}^K w_kf_k(y_{i-1}, y_i, i, x) ,\quad \color{blue} {M_i(x)} = [g(y_{i-1}, y_i, x, i) ] \] 每一步转移的时候，由于$(y_{i-1}, y_i)$ 有$m^2$ 种情况，计算$g$时会得到多个值，即可得到一个矩阵。

其中$g(y_{i-1}, y_i, x, i)$ 在计算的时候，会根据$i$ 的不同，而选择不同的特征函数进行计算。不要忘记了$f_k$函数的定义。 \[ \color{blue} {f_k(y_{i-1}, y_i, i)} = \begin {cases} t_k(y_{i-1}, y_i, x, i) \quad & k = 1, \cdots, K_1 \\ s_k(y_i, x, i) \quad & k = K_1 + l; \; l = 1, \cdots, K_2 \\ \end {cases} \] 所以非规范化条件概率可以通过矩阵的某些元素的乘积表示，有 \[ P_w( y \mid x) = \frac {1}{Z_w(x)} \prod_{i=1}^{n+1} M_i(y_{i-1}, y_i \mid x) \] 其中规范化因子 是$n+1$的矩阵相乘的结果矩阵中，第$(start, stop)$ 元素。例如第$(0, 0)$。其中是$(start, end)$ 是矩阵下标对应。

条件随机场的概率计算问题

主要问题是给定条件随机场$P(Y \mid X)$ ，给定输入序列$x$ 和输出序列$y$，求$P(Y_i = y_i \mid x)$ 和$P(Y_{i-1} = y_{i-1}, Y_i = y_{i} \mid X)$，以及相应的期望问题。

关键是求这些特征函数期望值，当模型训练好之后，去验证我们的模型。

前向后向算法

$y_i$ 确定后， $\color{blue} {\alpha_i(y_i \mid x) }$ 表示，从$start \to i$，就是$y = (start, y_1, , y_i) $ 的概率，也就是从前面到位置$y_i$ 的概率。特别地 \[ \alpha_0(y \mid x) = \begin{cases} 1, \quad & y=start \\ 0, \quad & 其他 \\ \end{cases} \] 而$y_i$ 的取值有$m$ 种，所以前向变量 $\color{blue}{\alpha_i(x)}$ 到$y$ 到第 $i$ 个位置的所有概率取值向量。 \[ \color{blue} {\alpha_i^T(x)} = \alpha_{i-1}^T(x) \cdot M_i(x) ,\quad i = 1,2,\cdots, n+1 \] $y_i$ 确定后， $\color{blue} {\beta_i (y_i \mid x) }$ 表示，位置$i$的标记为$y_i$ ，并且后面为$y_{i+1}, \cdots, y_n, stop$ 的概率。同理一个是概率值。特别地 \[ \beta_{n+1}(y \mid x) = \begin{cases} 1, \quad & y=stop \\ 0, \quad & 其他 \\ \end{cases} \] 后向变量 $\color{blue} {\beta_i (y \mid x) }$，是一个m维向量 \[ \color{blue} {\beta_i (x) } = M_{i+1}(x) \cdot \beta_{i+1}(x) \]

可以得到$Z(x)$： \[ Z(x) = \alpha_n^T(x) \cdot 1 = 1^T \cdot \beta_{i+1}(x) \]

条件概率计算

位置是$i$ 标记$y_i$ 的条件概率$P(Y_i = y_i \mid x)$是 \[ P(Y_i = y_i \mid x) = \frac {1}{Z(x)} \cdot \alpha_i(y_i \mid x) \beta_i(y_i \mid x) \] 位置$i-1, i$ 分别标记为$y_{i-1}, y_i$ 的概率是 \[ P(Y_{i-1} = y_{i-1}, Y_i = y_i \mid x) = \frac{1}{Z(x)} \cdot \alpha_{i-1}(y_{i-1} \mid x) M_i(y_{i-1}, y_i \mid x) \beta_i (y_i \mid x) \]

特征期望值计算

两个期望值和最大熵模型的约束条件等式有点像。

特征函数$f_k$ 关于条件概率分布$P(Y \mid X)$ 的概率 \[ E_{P(Y \mid X)}(f_k) = \sum_y P(y \mid x) f_k(y, x) = \sum_{i=1}^{n+1}\sum_{y_{i-1}y_i} f_k(y_{i-1}, y_i, x, i) P(y_{i-1}, y_i \mid x) \] 特征函数$f_k$ 关于条件概率分布$P(X, Y)$ 的概率，$\hat P(x)$ 是经验分布 \[ E_{P(X, Y)}(f_k) = \sum_{x, y} P(x, y) \sum_{i=1}^{n+1} f_k(y_{i-1}, y_i, x, i) = \sum_{x} \hat P(x) \sum_y P(y \mid x) \sum_{i=1}^{n+1} f_k(y_{i-1}, y_i, x, i) \] 通过前向和后向向量可以计算出两个概率，然后可以计算出相应的期望值。就可以与我们训练出的模型进行比较。

学习算法

条件随机场模型实际上是定义在时序数据上的对数线性模型，学习方法有极大似然估计和正则化的极大似然估计。具体的优化实现算法有：改进的迭代尺度法IIS、梯度下降法和拟牛顿法。

改进的迭代尺度法

这里是最大熵模型中的改进的迭代尺度算法。每次更新一个$\delta_i$ 使得似然函数的该变量的下界增大，即似然函数增大。

已知经验分布$\hat P(X, Y)$，和模型如下 \[ P(y \mid x) = \frac {1} {Z(x)} \exp \sum_{k=1} ^K w_k f_k(y, x) , \quad Z(x) = \sum_y \exp \sum_{k=1} ^K w_k f_k(y, x) \] 对数似然函数和最大熵算法的极大似然函数很相似，如下：
\[ L(w) = L_{\hat P}(P_w) = \log \prod_{x,y} P_w(y \mid x) ^ {\widetilde P(x, y)} = \sum_{x,y} \widetilde P(x, y) \log P_w(y \mid x) \] 对数似然函数$L(w)$ \[ L(w) = \sum_{j=1}^{N} \sum_{k=1}^K w_k f_k(y_j, x_j) - \sum_{j=1}^N \log Z_w(x_j) \] 数据$(x, y)$ 中出现的特征总数$T(x, y)$ ： \[ T(x, y) = \sum_k f_k(y, x) = \sum_{k=1}^K \sum_{i=1}^{n+1}f_k(y_{i-1}, y_i, x) \] 输入：特征函数$t_1, t_2, \cdots, t_{K_1}$和$s_1, s_2, \cdots, s_{K_2}$ ；经验分布$\hat P(x, y)$

输出：模型参数$\hat w$，模型$P_{\hat w}$

步骤：

1 赋初值 $w_k = 0$

2 对所有$k$，求解方程，解为$\delta_k$ \[ \begin{align} & \sum_{x, y} \hat P(x) P(y \mid x) \sum_{i=1}^{n+1} t_k(y_{i-1}, y_i, x, i) \exp (\delta_k T(x, y)) = E_{\hat p}[t_k] , \quad k = 1, 2, \cdots, K_1 时 \\ & \sum_{x, y} \hat P(x) P(y \mid x) \sum_{i=1}^{n+1} s_l(y_{i-1}, y_i, x, i) \exp (\delta_k T(x, y)) = E_{\hat p}[s_l] , \quad k = K_1 + l, l = 1, 2, \cdots, K_2 时 \\ \end{align} \] 3 更新$w_k + \delta_k \to w_k$ ，如果还有$w_k$未收敛，则继续2

算法S

对于不同的数据$(x, y)$的特征出现次数$T(x, y)$ 可能不同，可以选取一个尽量大的数$S$作为特征总数，使得所有松弛特征$s(x, y) \ge 0$ ： \[ s(x, y) = S - \sum_{i=1}^{n+1}\sum_{k=1}^K f_k(y_{i-1}, y_i, x, i) \] 所以可以直接解得$\delta_k$ ，当然$f_k$ 要分为$t_k$和$s_k$，对应的期望值计算也不一样。具体见书上。
\[ \delta_k = \frac{1}{S} \log \frac{E_{ \hat P}[f_k] } {E_P[f_k]} \] 算法T

算法S中$S$会选择很大，导致每一步的迭代增量会加大，算法收敛会变慢，算法T重新选择一个特征总数 T(x) \[ T(x) = \max \limits_y T(x, y) \] 使用前后向递推公式，可以算得$T(x)=t$ 。

对于$k \in [1, K_1]$的$t_k$关于经验分布的期望： \[ E_{\hat P}[t_k] = \sum_{t=0}^{T_{max}} a_{k,t} \beta_{k}^t \] 其中，$a_{k,t}$是$t_k$的期待值， $\delta_k = \log \beta_k$

对于$k \in [1+K_1, K]$的$s_k$关于经验分布的期望： \[ E_{\hat P}[s_k] = \sum_{t=0}^{T_{max}} b_{k,t} \gamma_{k}^t \] 其中$\gamma_k^t$是特征$s_k$的期望值，$\delta_k = \log \gamma_k$。当然，求根也可以使用牛顿法去求解。

拟牛顿法

预测算法

预测问题

给定条件随机场$P(Y \mid X)$和输入序列$x$，求条件概率最大的输出序列（标记序列）$y^*$，即对观测序列进行标注。 \[ \begin{align} y^* & = \arg \max \limits_y P_w(y \mid x) = \arg \max \limits_y \frac{\exp (w \cdot F(y, x))}{Z_w(x)} \\ & = \arg \max \limits_y ( w \cdot F(y, x)) \\ \end {align} \] 其中路径$y$表示标记序列，下面是参数说明 \[ \begin {align} & w = (w_1, w_2, \cdots, w_k)^T \\ & F(y, x) = (f_1(y, x), \cdots, f_K(y, x))^T, \quad w = (w_1, \cdots, w_K)^T \\ & f_k (y, x) = \sum _{i=1} ^n f_k(y_{i-1}, y_i, x, i) \\ & F_i(y_{i-1}, y_i, x) = \left(f_1(y_{i-1}, y_i, x, i), f_2(y_{i-1}, y_i, x, i),\cdots, f_k(y_{i-1}, y_i, x, i) \right)^T \end {align} \] 所以，为了求解最优路径，只需计算非规范化概率，即转换为下面的问题： \[ \max \limits_y \quad \sum_{i=1}^n w \cdot F_i(y_{i-1}, y_i, x) \]

维特比算法

HMM的维特比算法。

维特比变量$\delta_i(l)$，到达位置$i$，标记为$l \in [1, m]$ 的概率 \[ \delta_i(l) = \max \limits_{1 \le j \le m} \{ \delta_{i-1}(j) + w \cdot F_i(y_{i-1} = j, y_i = l, x) \}, \quad j = 1, 2, \cdots, m \] 记忆路径$\psi_i(l) = a$ 当前时刻$t$标记为l, $t-1$时刻标记为a \[ \psi_i(l) = = \arg \max \limits_{1 \le j \le m} \{ \delta_{i-1}(j) + w \cdot F_i(y_{i-1} = j, y_i = l, x) \} \] 算法主体

输入：特征向量$F(y, x)$和权值向量$\mathbf{w}$，观测向量$x = (x_1, x_2, \cdots. x_n)$

输出：最优路径$y^* = (y_1^*, y_2^*, \cdots, y_n^*)$

步骤如下

初始化 \[ \delta_1(j) = w \cdot F_1(y_0 = start, y_1 = j, x), \quad j = 1, \cdots, m \] 递推 \[ \begin{align} & \delta_i(l) = \max \limits_{1 \le j \le m} \{ \delta_{i-1}(j) + w \cdot F_i(y_{i-1} = j, y_i = l, x) \}, \quad j = 1, 2, \cdots, m \\ & \psi_i(l) = \arg \max \limits_{1 \le j \le m} \delta_i(j), \quad \text{即上式的参数j} \\ \end{align} \] 终止 \[ \begin{align} & \max \limits_y (w \cdot F(y, x)) = \max \limits_{1 \le j \le m} \delta_n(j) \\ & y_n^* = \arg \max \limits_{1 \le j \le m} \delta_n(j) \\ \end{align} \] 返回路径 \[ y_i^* = \psi_{i+1} (y_{i+1}^*), \quad i = n-1, n-2, \cdots, 1 \] 求得最优路径$y^* = (y_1^*, y_2^*, \cdots, y_n^*)$

条件随机场