概率图模型基础¶
马尔可夫随机场 (Markov Random Field)¶
结点间的联结关系表示了联合分布变量之间的条件独立性（马尔可夫性质）
概率图模型 (Probabilistic Graphical Model)¶
由联合概率分布 $P(X)$ 和表示它的无向图 $G$ 定义，具有以下马尔可夫性质：
- 成对马尔可夫性：设 $X_u$ 和 $X_v$ 是图中无边连接的两个结点，则对任意固定 $X_{V-\{u,v\}}$，有 $X_u \perp X_v | X_{V-\{u,v\}}$ （条件独立）
- 局部马尔可夫性：设 $X_u$ 是任一节点，$N(u)$ 是其邻居结点，则对任意固定 $X_{V-\{u \cup N(u)\}}$，有 $X_u \perp X_{V-\{u \cup N(u)\}} | X_{N(u)}$ （条件独立）
- 全局马尔可夫性：设结点集合A和B在图G中被C分开，则 $X_A \perp X_B | X_C$
因子分解¶
正确性与局部、全局马尔可夫性是等价的
设联合分布在图 $G=(V,E)$ 上表示，如果 $P(X)$ 满足局部或全局马尔可夫性，则可以表示为：
$$ P(x) = \frac{1}{\mathcal{Z}} \prod_{c} \phi_c(x_c) $$
其中：
- 最大团（Maximal Clique）：在图中，任两个节点均有边连接的团 $C$，若不能加入一个节点而成为更大的团
- 势函数 $\phi_c(x_c) = \exp(\theta_c x_c)$（通常定义为指数函数）
- 归一化因子 $\mathcal{Z} = \sum_{x} \prod_{c} \phi_c(x_c)$
条件随机场理论¶
条件随机场的定义¶
给定随机变量 $X$ 和 $Y$，如果 $P(Y|X)$ 满足马尔可夫性质，则称 $P(Y|X)$ 为条件随机场。
条件随机场是判别式模型，直接对条件概率 $P(Y|X)$ 进行建模，避免了对 $P(X)$ 的复杂建模。
线性链条件随机场 (Linear Chain CRF)¶
定义在序列上的条件随机场，由参数化的对数线性模型表示：
$$ P(y|x) = \frac{1}{Z(x)} \exp\left(\sum_{i=1}^{n} \sum_{k=1}^{K} \lambda_k t_k(y_{i-1}, y_i, x, i) + \sum_{i=1}^{n} \sum_{l=1}^{L} \mu_l s_l(y_i, x, i)\right) $$
其中：
- $t_k(y_{i-1}, y_i, x, i)$：定义在边（相邻标签间）的特征函数
- $s_l(y_i, x, i)$：定义在节点（单个标签）的特征函数
- $\lambda_k, \mu_l$：特征函数的权重参数
- $Z(x) = \sum_y \exp(\cdots)$：归一化因子
- 特征函数为局部特征，取值通常为 0 或 1，依赖于位置 $i$
条件随机场的三大问题¶
问题一：评估问题（计算概率）¶
前向-后向算法¶
定义前向变量 $\alpha_i(y_i|x)$：
从时刻 1 到 $i$，标注序列到 $y_i$ 的所有路径的总非规范化概率：
$$\alpha_i(y_i|x) = \sum_{y_{i-1}} \alpha_{i-1}(y_{i-1}|x) \exp\left(\sum_{k=1}^{K} \lambda_k t_k(y_{i-1}, y_i, x, i) + \sum_{l=1}^{L} \mu_l s_l(y_i, x, i)\right)$$
边界条件：$\alpha_0(x) = 1$
定义后向变量 $\beta_i(y_i|x)$：
从时刻 $i$ 到 $n$，从 $y_i$ 开始的所有路径的总非规范化概率：
$$\beta_i(y_i|x) = \sum_{y_{i+1}} \exp\left(\sum_{k=1}^{K} \lambda_k t_k(y_i, y_{i+1}, x, i+1) + \sum_{l=1}^{L} \mu_l s_l(y_{i+1}, x, i+1)\right) \beta_{i+1}(y_{i+1}|x)$$
边界条件：$\beta_n(y_n|x) = 1$
归一化因子计算：
$$Z(x) = \sum_{y_n} \alpha_n(y_n|x) = \sum_{y_1} \alpha_1(y_1|x) \beta_1(y_1|x)$$
边际概率计算：
$$P(Y_i = y_i | x) = \frac{\alpha_i(y_i|x) \beta_i(y_i|x)}{Z(x)}$$
$$P(Y_i=y_i, Y_j=y_j | x) = \frac{\alpha_i(y_i|x) \exp(\text{edge score}_{ij}) \beta_j(y_j|x)}{Z(x)}, \quad i < j$$
问题二：学习问题（参数估计）¶
给定训练数据集 $T = \{(x^{(i)}, y^{(i)}) | i = 1, 2, \ldots, N\}$，使用极大似然估计求解参数 $\lambda_k, \mu_l$。
学习算法：
- 改进的迭代尺度法（Improved Iterative Scaling）
- 拟牛顿法（Quasi-Newton methods，如 L-BFGS）
问题三：预测问题（Viterbi算法）¶
给定模型 $P(Y|X)$ 和观测序列 $X = (x_1, x_2, \ldots, x_n)$，求最可能的标注序列 $Y^*$：
$$Y^* = \arg\max_Y P(Y|X) = \arg\max_Y \log P(Y|X)$$
使用动态规划求解：
初始化¶
$$ \delta_1(j) = \sum_{k=1}^{K} \lambda_k t_k(\text{start}, y_1=j, x, 1) + \sum_{l=1}^{L} \mu_l s_l(y_1=j, x, 1), \quad j=1,\ldots,m $$
递推¶
$$ \delta_i(j) = \max_{j'} \left[\delta_{i-1}(j') + \sum_{k=1}^{K} \lambda_k t_k(j', j, x, i) + \sum_{l=1}^{L} \mu_l s_l(j, x, i)\right], \quad i=2,\ldots,n $$
$$ \psi_i(j) = \arg\max_{j'} [\delta_{i-1}(j') + \text{score}(j', j, i)] $$
终止与回溯¶
$$ y_n^* = \arg\max_{j=1}^m \delta_n(j) $$
$$ y_i^* = \psi_{i+1}(y_{i+1}^*), \quad i=n-1,\ldots,1 $$
应用¶
线性链CRF的重要应用包括：
- 命名实体识别（NER）：识别文本中的人名、地名、组织名等
- 词性标注（POS tagging）：为每个词标注其词性
- 分词（Word Segmentation）：将文本分割成单词序列
- 语义角色标注（Semantic Role Labeling）：识别谓词及其论元
注：本文使用Qwen转换自本人的统计学习方法笔记。
