外观
命名实体识别：CRF与HMM深度解析
内容整理自学习笔记，仅供面试备考参考；不构成录用、培训或考试承诺。
1. CRF（条件随机场）常见面试题
1.1 什么是 CRF？CRF 的主要思想是什么？
设 X 与 Y 是随机变量，P(Y|X) 是给定条件 X 的条件下 Y 的条件概率分布，若随机变量 Y 构成一个由无向图 G=(V,E) 表示的马尔科夫随机场，则称条件概率分布 P(Y|X) 为条件随机场。
核心思想：CRF 统计全局概率，在做归一化时，考虑了数据在全局的分布。
1.2 CRF 的三个基本问题
| 问题 | 定义 | 解决方法 |
|---|---|---|
| 概率计算问题 | 给定观测序列 x 和状态序列 y，计算概率 P(y|x) | 前向计算、后向计算 |
| 学习计算问题 | 给定训练数据集估计 CRF 模型参数 | 随机梯度法、牛顿法、拟牛顿法、迭代尺度法 |
| 预测问题 | 给定 CRF P(Y|X) 和输入序列 x，求条件概率最大的输出序列 y* | 维特比算法 |
1.3 线性链条件随机场的参数化形式
在随机变量 X 取值为 x 的条件下，随机变量 Y 取值为 y 的条件概率包含以下要素：
| 要素 | 说明 |
|---|---|
| Z(x) | 规范化因子，求和在所有可能的输出序列上进行 |
| t_k | 定义在边上的特征函数，称为转移特征，依赖于当前和前一个位置 |
| s_l | 定义在结点上的特征函数，称为状态特征，依赖于当前位置 |
1.4 CRF 的优缺点
优点：
| 优点 | 说明 |
|---|---|
| 丰富的特征信息 | 为每个位置标注时可利用内部及上下文特征信息 |
| 特征融合优势 | 在结合多种特征方面存在优势 |
| 避免标记偏置 | 有效避免了标记偏置问题 |
| 性能更好 | 对特征的融合能力更强 |
缺点：
| 缺点 | 说明 |
|---|---|
| 训练时间长 | 训练时间比 ME 更长，且模型非常大，普通 PC 机可能无法执行 |
| 特征依赖 | 特征的选择和优化是影响结果的关键因素，直接决定性能高低 |
1.5 HMM 与 CRF 的区别
| 对比维度 | HMM | CRF |
|---|---|---|
| 图类型 | 有向图 | 无向图 |
| 特征使用 | 局部特征（齐次马尔科夫假设和观测独立性假设） | 全局特征（全局归一化） |
| 最优解 | 只能找到局部最优解 | 可以得到全局最优值 |
| 模型类型 | 生成模型 | 判别模型 |
| 概率分布 | 描述联合分布 P(I, O) | 描述条件概率 P(I|O) |
| 关系 | CRF 包含 HMM，HMM 是 CRF 的特殊情况 | — |
共性：两者都常用来做序列标注的建模，如词性标注。
1.6 生成模型与判别模型的区别
| 类型 | 学习目标 | 常见模型 | 直觉理解 |
|---|---|---|---|
| 生成模型 | 联合概率分布 P(x,y) | 朴素贝叶斯、混合高斯、HMM | 先学习山羊模型和绵羊模型，再分别计算概率比较 |
| 判别模型 | 条件概率分布 P(y|x) | 感知机、决策树、逻辑回归、SVM、CRF | 直接从历史数据学习，提取特征预测属于各类的概率 |
2. HMM（隐马尔可夫模型）常见面试题
2.1 什么是马尔科夫过程？
假设一个随机过程中，t_n 时刻的状态 x_n 的条件分布只与其前一状态 x_(n-1) 相关，即：
P(x_n | x_1, x_2, ..., x_{n-1}) = P(x_n | x_{n-1})
则将其称为马尔可夫过程。
2.2 马尔科夫过程的核心思想
当前时刻状态仅与上一时刻状态相关，与其他时刻不相关。
从马尔可夫过程图理解：每个状态间以有向直线连接，即当前时刻状态仅与上一时刻状态相关。
2.3 隐马尔可夫算法中的两个假设
| 假设 | 内容 |
|---|---|
| 齐次马尔可夫性假设 | 隐藏的马尔科夫链在任意时刻 t 的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻 t 无关 |
| 观测独立性假设 | 任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其他观测及状态无关 |
2.4 隐马尔可夫模型三个基本问题
| 问题 | 定义 | 解决方法 |
|---|---|---|
| 概率计算问题 | 给定模型 (A,B,π) 和观测序列，计算观测序列出现的概率 | 直接计算法复杂度太大 O(N²T)，使用前向与后向计算法 |
| 学习问题 | 已知观测序列，估计模型参数，使观测序列概率最大 | 极大似然估计，Baum-Welch 算法（EM 算法） |
| 预测问题（解码问题） | 已知模型和观测序列，求条件概率最大的状态序列 | 维特比算法（动态规划） |
维特比算法核心：边计算边删掉不可能是答案的路径，在最后剩下的路径中挑选最优路径。
2.5 三个基本问题的联系
三个基本问题存在渐进关系：
- 首先学会用前向算法和后向算法计算观测序列出现的概率
- 然后用 Baum-Welch 算法求参数时，某些步骤需要用到前向和后向算法
- 得到参数后，用于预测（解码任务是应用 HMM 的最终目的）
2.6 隐马尔可夫算法存在的问题
HMM 模型简化了很多问题，做了很强的假设，带来的影响：
| 方面 | 好处 | 坏处 |
|---|---|---|
| 强假设 | 简化求解难度 | 对真实情况的建模能力变弱 |
在序列标注问题中，隐状态（标注）不仅和单个观测状态相关，还和观察序列的长度、上下文等信息相关。例如词性标注问题中，一个词被标注为动词还是名词，不仅与它本身及前一个词的标注有关，还依赖于上下文中的其他词。
优化方向：可以使用最大熵马尔科夫模型（MEMM）进行优化。