概率图模型分类
- 有向图：静态贝叶斯、动态贝叶斯（隐马尔可夫模型）
- 无向图：马尔可夫网络（条件随机场、玻尔兹曼机）
隐马尔可夫模型
评估问题
$HMM<S,O,Theta>, Theta=<pi ,A, B>$
隐藏状态S，观测状态O，初始状态的概率分布$pi$，隐藏状态转移概率A，观测状态转移概率B
计算观测序列概率
- $p(O|Theta)=sum_{S}^{ }p(O,S|Theta)=sum_{S}^{ }p(O|S,Theta)p(S|Theta)$
- $p(O|S,Theta)=prod_{i}^{ }p(O_i|S_i,Theta)=prod_{i}^{ }B(O_i,S_i)$
- $p(S|Theta)=pi(S_0)prod_{i}^{ }p(S_{i+1}|S_i)$
递归公式（前向算法）
- $p(O_1^t|Theta)=sum_i^{ } p(O_1^t,S_{t+1}=i|Theta)=sum_i^{ }alpha_t(i)$
- $alpha_{t+1}(i)=sum_j^{ } p(O_1^t,O_{t+1},S_t=j,S_{t+1}=i|Theta)=sum_j^{ } p(O_{t+1},S_{t+1}=i|S_t=j,O_1^t,Theta)p(O_1^t,S_t=j|Theta)$
- $=sum_j^{ } p(O_{t+1},S_{t+1}=i|S_t=j,Theta)alpha_t(i)=sum_j^{ } B(O_{t+1},i)A(i,j)alpha_t(i)$
解码问题
解码问题：求解隐藏序列$arg\,max_Sp(S|O,Theta)$，viterbi/A*算法
- 输入为音子时，观察与状态之间为多对一关系
- $arg\,max_Sp(S|O,Theta)=arg\,max_Sp(O|S,Theta)p(S|Theta)=arg\,max_Sprod_{i}^{ }B(O_i,S_i)pi(S_0)prod_{i}^{ }A(S_{i+1},S_i)$
- 序列空间约束：$given\,S_{n+1}, S_n=arg\,max_sB(O_{n+1}, S_{n+1})A(S_{n+1}, s)$
- 递归公式：$delta_i(t)=max_{q_{1}^{t-1}}p(O_{1}^{t},q_{1}^{t-1},q_t=i)$；$delta_{i+1}(t)=max_{i}[delta_i(t)A(j,i)]B(O_{t+1},j)$
学习问题
参数估计$arg\,max_{Theta}p(O|Theta)$
- 引入中间变量，采用 EM/向前向后算法
- 后向变量：$eta_t(j)=p(O_{t+1}^T |q_t=j,Theta)$
- $xi_t(i,j)=p(q_t=i,q_{t+1}=j|O,Theta)=frac{p(q_t=i,q_{t+1}=j,O|Theta)}{p(O|Theta)}=frac{alpha_t(i)A(j,i)B(O_{t+1},j)eta_{t+1}(j)}{sum_{i}^{ }alpha_T(i)}$
- $pi(i)=p(q_1=i|O)=sum_{i}^{ }xi_1(i,j)=gamma_1(i)$
- $A(j,i)=frac{sum_{t}^{ }p(q_t=i,q_{t+1}=j|O)}{sum_{t}^{ }p(q_t=i|O)}=frac{sum_{t}^{ }xi_t(i,j)}{sum_{t}^{ }gamma_t(i)}$
- $B(O_T,i)=frac{sum_{t}^{ }p(q_t=i,O_t|O)}{sum_{t}^{ }p(q_t=i|O)}=frac{sum_{t}^{ }gamma_t(i)delta(o=O_t)}{sum_{t}^{ }gamma_t(i)}$
条件随机场
马尔可夫随机场MRF
- 无向图表示的联合概率分布
- 成对马尔可夫性：任意不相邻的节点a,b在其它节点已知的条件下概率独立
- $p(a,b|C)=p(a|C)p(b|C)$
- 团：完全子图
- 联合概率等于所有最大团的联合概率的乘积
- $p(x)=frac{1}{Z}prod_cPsi (X_c)$
条件随机场CRF
- 如果 Y 为 MRF，那么P(Y|X)为CRF
- 线性链随机场：$p(Y_i|X,Y)=p(Y_i|X,Y_{i-1},Y_{i+1})$
- $=frac{1}{Z(x)}exp(sum_{i,k}^{ } w_kf_k(y_{i-1},y_i,x,i))=frac{1}{Z(x)}exp( W^TF(y,x))$
- 预测问题：$arg\,max_yfrac{1}{Z(x)}exp( W^TF(y,x))=arg\,max_yexp( W^TF(y,x))$
- 学习问题：$arg\,max_wfrac{1}{Z(x)}exp( W^TF(y,x))$
概率采样算法
定理：[细致平稳条件](detailed balance condition)
- 如果非周期马氏链的转移矩阵P和分布$pi(x)$满足$forall i,j\,pi(i)P_{ij}=pi(j)P_{ji}$，则$pi(x)$是马氏链的平稳分布
Metropolis-Hastings
- 根据转移矩阵P的马氏链，构造平稳分布为p(x)的马氏链
- 需要串联一个因子$alpha$，$pi(i)P_{ij}alpha_{ij}=pi(j)P_{ji}alpha_{ji}$，满足细致平稳条件。相当于修正转移矩阵。
- $alpha=min(1,frac{pi(i)P_{ij}}{pi(j)P_{ji}})$
Metropolis/MCMC伪代码
- 初始化状态x0
- 根据转移矩阵P ，生成状态y
- 生成r=uniform()，如果r<α(x,y)，接受xn+1=y
- 迭代直到收敛，采样为分布
模拟退火
- 避免极小值，逐渐降低温度，使得Metropolis算法快速收敛
玻尔兹曼机
Gibbs采样算法
- 观察到任意$p(x_1,x_C)p(x_2|x_C)=p(x_2,x_C)p(x_1|x_C)$，满足细致平稳条件
- 每次按照边缘条件分布概率，改变一个分量
- 收敛到联合分布，通常为Gibbs分布：$p_x=frac{1}{Z}e^{-frac{E_x}{k_BT}}$
Boltzmann机
- 状态向量分为可见部分$x_a$和隐藏部分$x_b$
- $p(x)=frac{1}{Z}e^{-E(x)}$，这里$E(x)=frac{1}{2}x^TWx$
- $p(x_j|[x_i|i eq j])=phi(xsum_{i eq j}^{ } w_{ji}x_i)$
- 最大化似然函数：$L(w)=sum log(p(x_a))=-sum E(x)-sum log(Z)$
- 配分函数Z难以计算
受限Boltzmann机
- 具有随机性的可见层v和一层隐藏层h，无向的二分图
- 能量定义为：$E(v,h)=-a^Tv-b^Th-h^TWv$
- p(h|v)与 p(v|h)易于计算和采样，因此可以采用CD、SML(PCD)、比率匹配等技术。
CD算法
- 取 m 个样本，得到 ML 的正项
- Gibbs 采样到平衡，得到负项估计
- 得到上升梯度
参考文献
- Deep learning, www.deeplearning.net
- 俞栋、邓力，解析深度学习：语言识别实践，电子工业出版社，2016.7