隐马尔可夫模型
HMM基本概念
隐马尔可夫模型（Hidden Markov Model, HMM）是一种用于建模序列数据的概率图模型，包含隐藏状态序列和观测序列。
HMM的组成
- 状态集合 S = {s₁, s₂, ..., sₙ}： 隐藏状态空间
- 观测集合 O = {o₁, o₂, ..., oₘ}： 可观测输出空间
- 状态转移概率 A = [aᵢⱼ]： aᵢⱼ = P(sⱼ | sᵢ)，从状态i转移到状态j的概率
- 观测概率 B = [bⱼ(k)]： bⱼ(k) = P(oₖ | sⱼ)，在状态j下观测到oₖ的概率
- 初始状态概率 π = [πᵢ]： πᵢ = P(s₁ = sᵢ)，初始状态为sᵢ的概率
马尔可夫假设
一阶马尔可夫性： 当前状态只依赖于前一时刻的状态，与更早的历史无关。
P(qₜ | qₜ₋₁, qₜ₋₂, ..., q₁) = P(qₜ | qₜ₋₁)
💡 典型应用
- • 语音识别：观测是声学信号，隐藏状态是音素或词
- • 词性标注：观测是单词，隐藏状态是词性（名词、动词等）
- • 生物序列分析：基因序列分析、蛋白质结构预测
HMM的三个基本问题
1. 概率计算问题（Evaluation）
给定模型λ=(A, B, π)和观测序列O，计算P(O|λ)
算法：前向算法（Forward Algorithm）或后向算法（Backward Algorithm）
2. 学习问题（Learning）
给定观测序列O，学习模型参数λ=(A, B, π)使得P(O|λ)最大
算法：Baum-Welch算法（EM算法的特例）
3. 解码问题（Decoding）
给定模型λ和观测序列O，找到最可能的隐藏状态序列Q
算法：Viterbi算法（动态规划）
Viterbi算法
Viterbi算法用动态规划找到最可能的状态序列，是HMM解码的核心算法。
算法步骤
- 初始化：δ₁(i) = πᵢ · bᵢ(o₁)，ψ₁(i) = 0
- 递推：对t = 2, 3, ..., T：
δₜ(j) = maxᵢ [δₜ₋₁(i) · aᵢⱼ] · bⱼ(oₜ)
ψₜ(j) = argmaxᵢ [δₜ₋₁(i) · aᵢⱼ]
- 终止：P* = maxᵢ δₜ(i)，q*ₜ = argmaxᵢ δₜ(i)
- 回溯：q*ₜ₋₁ = ψₜ(q*ₜ)，得到最优路径
时间复杂度：O(TN²)，其中T是序列长度，N是状态数量。
Viterbi算法可视化
动态展示Viterbi算法在词性标注任务中的解码过程
🚧 开发中...
马尔可夫随机场
概率图模型概述
概率图模型（Probabilistic Graphical Model, PGM）用图结构表示变量间的概率依赖关系，节点表示随机变量，边表示依赖关系。
有向图模型（贝叶斯网络）
用有向无环图（DAG）表示因果关系，边表示条件概率。 联合概率分解为条件概率的乘积。
无向图模型（马尔可夫随机场）
用无向图表示变量间的对称依赖关系，基于团（clique）定义联合概率。
马尔可夫随机场（MRF）
马尔可夫随机场（Markov Random Field, MRF）是一种无向概率图模型，满足局部马尔可夫性质。
成对马尔可夫性
给定其他所有变量，两个不相邻的变量条件独立：
u ⊥ v | X \ {u, v} （如果u和v不相邻）
局部马尔可夫性
给定邻居变量，一个变量与其他变量条件独立：
v ⊥ X \ {v} ∪ N(v) | N(v)
N(v)是v的邻居集合
基于势函数的联合概率
联合概率由各个团（clique）上的势函数（potential function）定义：
P(X) = (1/Z) ∏C∈𝓒 ψC(XC)
Z是归一化因子（配分函数），ψC是团C上的势函数
条件随机场（CRF）
条件随机场（Conditional Random Field, CRF）是给定观测序列条件下的马尔可夫随机场，常用于序列标注任务。
线性链CRF
对于序列标注，条件概率定义为：
P(y|x) = (1/Z(x)) exp(Σₜ Σₖ λₖfₖ(yₜ₋₁, yₜ, x, t))
fₖ是特征函数，λₖ是对应权重，Z(x)是归一化因子
💡 CRF vs HMM
- HMM： 生成式模型，建模P(x, y) = P(y)P(x|y)，有严格的独立性假设
- CRF： 判别式模型，直接建模P(y|x)，可以使用任意特征，无需独立性假设
CRF通常比HMM在序列标注任务上表现更好，但训练更复杂。
应用： 词性标注、命名实体识别、中文分词、信息抽取等序列标注任务。
CRF序列标注演示
展示CRF在命名实体识别任务中的标注过程
🚧 开发中...
学习与推断
概率图模型的推断
推断（Inference）是概率图模型的核心任务， 包括边际概率计算、最大后验估计（MAP）等。
精确推断
- 变量消除（Variable Elimination）： 利用分配律，通过消除变量逐步计算边际概率
- 信念传播（Belief Propagation）： 在树结构图上通过消息传递进行推断
- 团树算法（Junction Tree）： 将图转换为树结构后进行精确推断
近似推断
当精确推断计算复杂度过高时（NP难），使用近似方法：
- 采样方法： MCMC（马尔可夫链蒙特卡洛）、吉布斯采样
- 变分推断： 用简单分布近似复杂分布，转化为优化问题
- 循环信念传播： 在有环图上迭代运行信念传播直到收敛
参数学习
学习概率图模型的参数，使其能够很好地拟合训练数据。
完全数据的参数学习
当所有变量都可观测时，可以直接用最大似然估计：
- • 有向图：估计每个条件概率表（CPT）
- • 无向图：估计各团的势函数参数
隐变量的参数学习
当存在隐变量时，使用EM算法：
- E步：根据当前参数计算隐变量的后验分布
- M步：最大化期望对数似然，更新参数
- 重复直到收敛
HMM的Baum-Welch算法和GMM的EM算法都是这一框架的实例。
结构学习
结构学习是从数据中学习图的结构（变量间的依赖关系）， 比参数学习更具挑战性。
基于评分的方法
定义评分函数（如BIC、AIC），搜索使得评分最高的图结构：
score(G) = log P(D|G) - (d/2) log m
第一项：数据拟合度，第二项：模型复杂度惩罚
基于约束的方法
通过统计独立性测试发现变量间的条件独立关系，据此构建图结构。 例如PC算法、IC算法等。
挑战： 结构学习的搜索空间巨大（超指数级），且很多问题是NP难的。 实际中常结合领域知识或使用启发式搜索。
贝叶斯网络结构学习
从数据中学习变量间的依赖关系并构建贝叶斯网络
🚧 开发中...
近似推断
MCMC采样
马尔可夫链蒙特卡洛（MCMC）通过构造马尔可夫链来对目标分布进行采样，从而近似计算期望和边际概率。
Metropolis-Hastings算法
- 初始化状态 x(0)
- 对t = 1, 2, ..., T：
- • 从提议分布q(x'|x(t-1))采样候选状态x'
- • 计算接受率：α = min(1, [P(x')q(x(t-1)|x')] / [P(x(t-1))q(x'|x(t-1))])
- • 以概率α接受x'，否则保持x(t-1)
经过足够多步骤后，样本的分布收敛到目标分布P(x)
吉布斯采样（Gibbs Sampling）
MH算法的特例，每次只更新一个变量，条件概率作为提议分布：
- 随机初始化所有变量
- 循环：对每个变量xᵢ，从条件分布P(xᵢ | x₋ᵢ)中采样更新
- 重复直到收敛
吉布斯采样简单易实现，在高维问题中广泛应用。
变分推断
变分推断（Variational Inference）将推断问题转化为优化问题，用简单分布q(x)近似复杂的后验分布p(x|D)。
KL散度最小化
目标是最小化q(x)和p(x|D)之间的KL散度：
min KL(q||p) = min 𝔼q[log q(x)] - 𝔼q[log p(x, D)]
平均场近似
假设q(x)可以分解为独立分布的乘积：
q(x) = ∏ᵢ qᵢ(xᵢ)
通过坐标上升法迭代优化每个qᵢ，直到收敛。
✓ 变分推断优点
- • 确定性算法，可重复
- • 收敛速度通常比MCMC快
- • 易于分布式计算
✗ 变分推断缺点
- • 只能得到近似解
- • 可能陷入局部最优
- • 需要选择近似分布族
MCMC vs 变分推断
对比MCMC采样和变分推断在后验估计任务上的效果
🚧 开发中...
话题模型
隐狄利克雷分配（LDA）
LDA（Latent Dirichlet Allocation）是一种话题模型，用于发现文档集合中的潜在主题。
生成过程
LDA假设每篇文档由多个话题混合而成，每个话题由词的分布定义：
- 对每个话题k，从Dirichlet分布生成词分布 φₖ ~ Dir(β)
- 对每篇文档d：
- 从Dirichlet分布生成话题分布 θd ~ Dir(α)
- 对文档中的每个词位置n：
- • 从多项分布选择话题 zdn ~ Mult(θd)
- • 从该话题的词分布选择词 wdn ~ Mult(φzdn)
超参数
- • α：文档-话题分布的Dirichlet先验，控制话题稀疏性
- • β：话题-词分布的Dirichlet先验，控制词稀疏性
- • K：话题数量（需要预先指定）
LDA推断
推断隐变量（话题分配z）和参数（θ, φ）：
- 吉布斯采样： 迭代采样每个词的话题分配，基于其他词的话题
- 变分EM： 用变分推断近似后验分布，交替优化参数
💡 应用
- • 文档分类：基于话题分布对文档分类
- • 信息检索：基于话题相似度检索相关文档
- • 推荐系统：基于用户的话题偏好推荐
- • 文本摘要：提取代表性话题和词汇
LDA话题建模演示
在新闻文档集上运行LDA，可视化发现的话题和词分布
🚧 开发中...