条件随机场
本章仅讨论条件随机场在 标注问题（tagging problem） 的应用，因此主要讲述 线性链（linear chain） 条件随机场。
概率无向图模型
成对马尔可夫性
节点 \(u\)、\(v\) 和所有其他节点 \(O\)，对应的随机变量分别为 \(Y_u\)、\(Y_v\)、\(Y_O\)（\(Y\) 表示随机变量）。它们具有以下概率关系： \[ P(Y_u, Y_v | Y_O) = P(Y_u | Y_O) P(Y_v | Y_O) \]
局部马尔可夫性
节点 \(v\)，\(W\) 是与 \(v\) 相邻的所有节点，\(O\) 是其余节点。它们具有以下概率关系： \[ P(Y_v, Y_O | Y_W) = P(Y_v | Y_W) P(Y_O | Y_W) \]
全局马尔可夫性
节点集合 \(A\)、\(B\)、\(C\)，其中 \(A\) 和 \(B\) 被 \(C\) 分离。它们具有以下概率关系： \[ P(Y_A, Y_B | Y_C) = P(Y_A | Y_C) P(Y_B | Y_C) \]
Definition: 概率无向图模型
如果联合概率分布 \(P(Y)\) 满足上述三个马尔可夫性质，就称此联合概率分布为概率无向图模型。
Definition: 团与最大团
团（Clique）： 图中的一个子集，其中任意两个节点都相邻连接。
最大团（Maximum Clique）： 不能再添加其他节点的团，即包含所有可能相邻节点的最大子集。
概率无向图模型的因子分解
\[ \begin{align} P(Y) &= \frac{1}{Z} \prod_{C} \psi_{C}(Y_C), \quad C \text{ is a maximum clique} \\ Z &= \sum_{Y} \prod_{C} \psi_{C}(Y_C), \quad Z \text{ is normalization factor} \\ \psi_{C}(Y_C) &= \exp\{-E(Y_C) \} \end{align} \]
其中，\(\psi\) 函数称为势函数，常用指数函数定义势函数。
\[ \psi_{C}(Y_{C}) = e ^{- H_{C}(Y_{C})} \]
\(H_{C}(Y_{C})\) 是一个定义在变量 \(Y_{C}\) 上的实值函数，常见形式为
\[ H_{C}(Y_{C}) = \sum_{u,v \in C, u \neq v} \alpha_{uv} x_u x_v + \sum_{v \in C} \beta_v x_v \]
其中，\(\alpha_{uv}\) 和 \(\beta_{v}\) 是参数。
CRF
Definition: 线性链条件随机场
我们假设 \(X\) 和 \(Y\) 是随机变量。如果随机变量 \(Y\) 是一个马尔可夫随机场，即满足： \[ P(Y_v | X, Y_w, w \neq v) = P(Y_v | X, Y_w, w \sim v) \] 其中 \(w \sim v\) 表示节点 \(v\) 与节点 \(w\) 相邻。
通常情况下，我们认为 \(X\) 与 \(Y\) 具有相同的结构。
我们有如下概率关系。 \[ P(Y_i | X, Y_1, \dots, Y_{i-1}, Y_{i+1}, \dots, Y_n) = P(Y_i | X, Y_{i - 1}, Y_{i + 1}) \]
条件随机场的参数化形式
\[ P(\mathbf{y} | \mathbf{x}) = \frac{1}{Z(\mathbf{x})} \exp \left(\sum_{i,k}\lambda_k t_k(y_{i -1}, y_i, \mathbf{x}, i) + \sum_{i,l}\mu_l s_l(y_i, \mathbf{x}, i))\right) \]
其中，
\[ Z(\mathbf{x}) = \sum_{\mathbf{y}} \exp \left(\sum_{i,k}\lambda_k t_k(y_{i -1}, y_i, \mathbf{x}, i) + \sum_{i,l}\mu_l s_l(y_i, \mathbf{x}, i)\right) \]
其中，\(t_k\) 和 \(s_l\) 是特征函数，\(\lambda_k\) 和 \(\mu_l\) 是对应的权重参数。
Simplification
\[ f_k(y_{i-1}, y_i, \mathbf{x}, i) = \begin{cases} t_k(y_{i-1}, y_i, \mathbf{x}, i), \quad &k = 1,2, \dots,K_1 \\\\ s_l(y_i, \mathbf{x}, i), \quad &k = K_1 + l; \text{ } l = 1,2,\dots, K_2 \end{cases} \]
\[ f_k(\mathbf{y}, \mathbf{x}) = \sum_{i=1}^{n} f_k(y_{i-1}, y_i, \mathbf{x}, i), \quad k = 1,2,\dots,K \]
\[ w_k = \begin{cases} \lambda_k, &k = 1,2,\dots,K_1 \\\\ \mu_l, &k = K_1 + l; \text{ } l = 1, 2, \dots, K_2 \end{cases} \] 即，
\[ \begin{align*} P(\mathbf{y} \mid \mathbf{x}) &= \frac{1}{Z(\mathbf{x})} \exp\left(\sum_{k=1}^{K} w_k f_k(\mathbf{y}, \mathbf{x})\right) \\\\ Z(\mathbf{x}) &= \sum_{\mathbf{y}} \exp\left(\sum_{k=1}^{K} w_k f_k(\mathbf{y}, \mathbf{x})\right) \end{align*} \] 注意，这里的 \(\sum_{\mathbf{y}}\) 是在对所有可能的标签序列求和，而不仅仅是一个确定的标签序列。
最后，
\[ \begin{align} P_{\mathbf{w}}(\mathbf{y} \mid \mathbf{x}) = \frac{\exp(\vec{w} \cdot \vec{F}(\mathbf{y}, \mathbf{x}))}{Z_{\mathbf{w}}(\mathbf{x})} \end{align} \]
\[ Z_{\mathbf{w}}(\mathbf{x}) = \sum_{\mathbf{y}} \exp(\vec{w} \cdot \vec{F}(\mathbf{y}, \mathbf{x})) \]
矩阵形式
对于每个标签序列，我们引入特殊的起始点和结束点标签，\(y_0 = \text{start}\) 和 \(y_{n+1} = \text{stop}\)。对于观测序列 \(\mathbf{x}\) 中的每个位置 \(i = 1,2,\dots,n+1\)，我们可以定义一个矩阵 \(M_i \in \mathbb{R}^{m \times m}\)：
\[ \begin{align*} M_i(\mathbf{x}) &= [M_i(y_{i-1}, y_i | \mathbf{x})] \\\\ M_i(y_{i-1}, y_i |\mathbf{x}) &= \exp \left(W_i(y_{i-1}, y_i | \mathbf{x})\right) \\\\ W_i(y_{i-1}, y_i |\mathbf{x}) &= \sum_{k=1}^{K}w_kf_k(y_{i-1},y_i,\mathbf{x},i) \end{align*} \]
因此： \[ P_w(\mathbf{y} |\mathbf{x}) = \frac{1}{Z_w(\mathbf{x})} \prod_{i=1}^{n+1} M_i(y_{i-1}, y_i |\mathbf{x}) \]
特别地： \[ Z_w(\mathbf{x}) = [M_1(\mathbf{x})M_2(\mathbf{x}) \cdots M_{n+1}(\mathbf{x})]_{\text{start},\text{stop}} \]
也就是矩阵 \((\text{start}, \text{stop})\) 位置上的元素。
矩阵形式不难理解，CRF 中的 \(M_i(\mathbf{x})\) 矩阵就是在每个位置 \(i\) 上，枚举所有可能的标签对 \((y_{i-1}, y_i)\)，并计算它们的转移得分。例如 \(m = 2\)，\(Y = \{A, B\}\)，则 \(M_1\) 为：
\[ M_1(\mathbf{x}) = \begin{bmatrix} M_1(A, A \mid \mathbf{x}) & M_1(A, B \mid \mathbf{x}) \\\\ M_1(B, A \mid \mathbf{x}) & M_1(B, B \mid \mathbf{x}) \end{bmatrix} \]
计算
接下来给出计算 \(P(Y_i = y_i |\mathbf{x})\)、\(P(Y_{i - 1} = y_{i - 1}, Y_i = y_i |\mathbf{x})\) 以及相应数学期望的解决方法。
前向-后向算法
对于每个索引 \(i = 0, 1, \dots, n + 1\)，我们定义前向列向量 \(\alpha_i(x)\)：
\[ \alpha_0(y|\mathbf{x}) = \begin{cases} 1, &y = \text{start} \\\\ 0, &\text{其他情况} \end{cases} \]
递推公式为：
\[ \alpha_i^T(y_i|\mathbf{x}) = \alpha_{i-1}^T (y_{i-1}|\mathbf{x}) [M_i(y_{i-1},y_i|\mathbf{x})],\quad i = 1,2,\dots,n+1 \tag{forward} \]
同样地，我们定义后向行向量：
\[ \begin{align} \beta_{n+1}(y_{n+1}|\mathbf{x}) &= \begin{cases} 1, &y_{n+1} = \text{stop} \\\\ 0, &\text{其他情况} \end{cases} \\\\ \beta_i(y_i|\mathbf{x})& = [M_{i+1}(y_i,y_{i+1}|\mathbf{x})] \beta_{i+1}(y_{i+1}|\mathbf{x}) \tag{backward} \end{align} \]
概率计算
\[ P(Y_i = y_i | \mathbf{x}) = \frac{\alpha_i^T(y_i | \mathbf{x}) \beta_i(y_i | \mathbf{x})}{Z(\mathbf{x})} \]
\[ P(Y_{i-1} = y_{i-1}, Y_i = y_i |\mathbf{x}) = \frac{\alpha_{i-1}^T(y_{i-1} |\mathbf{x}) M_i(y_{i-1},y_i |\mathbf{x}) \beta_i(y_i |\mathbf{x})}{Z(\mathbf{x})} \]
其中：
\[ Z(\mathbf{x}) = \alpha_n^T(\mathbf{x})\mathbf{1} = \mathbf{1}^T \beta_1(\mathbf{x}) \]
可以仿照隐马尔科夫模型计算相似问题时引入 \(\alpha\) 和 \(\beta\) 矩阵，
前向向量矩阵 \(\alpha\)
\[ \alpha = \begin{bmatrix} \alpha_0(A) & \alpha_0(B) & \cdots & \alpha_0(N) \\\\[10pt] \alpha_1(A) & \alpha_1(B) & \cdots & \alpha_1(N) \\\\[10pt] \vdots & \vdots & \ddots & \vdots \\\\[10pt] \alpha_{n+1}(A) & \alpha_{n+1}(B) & \cdots & \alpha_{n+1}(N) \end{bmatrix}^{T} \tag{CRF-1} \]
每一行表示在位置 \(i\) 的前向向量 \(\alpha_i\)，每一列对应一个标签 \(y_i \in \mathcal{Y}\)。
后向向量矩阵 \(\beta\)
\[ \beta = \begin{bmatrix} \beta_0(A) & \beta_0(B) & \cdots & \beta_0(N) \\\\[10pt] \beta_1(A) & \beta_1(B) & \cdots & \beta_1(N) \\\\[10pt] \vdots & \vdots & \ddots & \vdots \\\\[10pt] \beta_{n+1}(A) & \beta_{n+1}(B) & \cdots & \beta_{n+1}(N) \end{bmatrix} \tag{CRF-2} \]
每一行表示在位置 \(i\) 的后向向量 \(\beta_i\)，每一列对应一个标签 \(y_i \in \mathcal{Y}\)。
期望值计算
比较复杂，详情参考《统计学习方法》
优化学习算法
优化学习算法涉及改进迭代尺度法、梯度下降法以及拟牛顿法。这些方法曾在最大熵的学习算法中提及，可以比对学习。
改进的迭代尺度法
已知训练数据集，由此可知经验概率分布 \(\tilde{P}(X, Y)\)。可以通过极大化训练数据的对数似然函数来求模型参数。
训练数据的对数似然函数为：
\[ L(w) = L_{\tilde{P}}(P_{w}) = \sum_{\mathbf{x} ,\mathbf{y}} \tilde{P}(\mathbf{x} ,\mathbf{y}) \log P_{w}(\mathbf{y} |\mathbf{x}) \]
若
\[ \begin{align*} P(\mathbf{y} \mid \mathbf{x}) &= \frac{1}{Z(\mathbf{x})} \exp\left(\sum_{k=1}^{K} w_k f_k(\mathbf{y}, \mathbf{x})\right) \\\\ Z(\mathbf{x}) &= \sum_{\mathbf{y}} \exp\left(\sum_{k=1}^{K} w_k f_k(\mathbf{y}, \mathbf{x})\right) \end{align*} \]
则
\[ 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) \]
拟牛顿法
这里介绍的拟牛顿法是 \(\mathbf{BFGS}\) 算法。
输入：特征函数 \(f_1, f_2, \cdots, f_n\)；经验分布 \(\tilde{P}(X, Y)\)；精度要求 \(\epsilon\)； 输出：最优参数值 \(\hat{w}\)；最优模型 \(P_{\hat{w}}(\mathbf{y} |\mathbf{x})\)。
- 选定初始点 \(w^{(0)}\)，取 \(B_0\) 为正定对称矩阵，置 \(k = 0\)。
- 计算 \(g_k = g(w^{(k)})\)。 若 \(\lVert g_k \rVert < \epsilon\)，则停止计算，得 \(w^{*} = w^{(k)}\)；否则转第 3 步。
- 由 \(B_k p_k = -g_k\) 求出 \(p_k\)。
- 一维搜索，求 \(\lambda_k\) 使得 \[ f(w^{(k)} + \lambda_k p_k) = \min_{\lambda \geq 0} f(w^{(k)} + \lambda p_k) \]
- 置 \(w^{(k + 1)} = w^{(k)} + \lambda_k p_k\)。
- 计算 \(g_{k + 1} = g(w^{(k + 1)})\)。 若 \(\lVert g_{k + 1} \rVert < \epsilon\)，则停止计算，得 \(w^{*} = w^{(k + 1)}\)；否则，按下式求出 \(B_{k + 1}\)： \[ B_{k + 1} = B_k + \frac{y_k y_k^T}{y_k^T \delta_k} - \frac{B_k \delta_k \delta_k^T B_k}{\delta_k^T B_k \delta_k} \] 其中， \[ y_k = g_{k + 1} - g_k, \quad \delta_k = w^{(k + 1)} - w^{(k)} \]
- 置 \(k = k + 1\)，转第 3 步。
条件随机场的预测算法
采用隐马尔科夫模型相似的预测算法
维特比算法
输入：