题目标题

简述EM 算法、HMM、CRF。

难度:中级

机器学习 NLP
参考解析

(1)EM 算法
EM 算法是用于含有隐变量模型的极大似然估计或者极大后验估计,有
两步组成:E 步,求期望(expectation);M 步,求极大
(maxmization)。本质上 EM 算法还是一个迭代算法,通过不断用上一
代参数对隐变量的估计来对当前变量进行计算,直到收敛。
注意:EM 算法是对初值敏感的,而且 EM 是不断求解下界的极大化逼
近求解对数似然函数的极大化的算法,也就是说 EM 算法不能保证找到全
局最优值。对于 EM 的导出方法也应该掌握。
(2)HMM 算法
隐马尔可夫模型是用于标注问题的生成模型。有几个参数(π,A, B):初始状态概率向量π,状态转移矩阵 A,观测概率矩阵 B。称为马尔
科夫模型的三要素。
马尔科夫三个基本问题:
概率计算问题:给定模型和观测序列,计算模型下观测序列输出的概率。
–》前向后向算法
学习问题:已知观测序列,估计模型参数,即用极大似然估计来估计参
数。–》Baum-Welch(也就是 EM 算法)和极大似然估计。
预测问题:已知模型和观测序列,求解对应的状态序列。–》近似算法(贪
心算法)和维比特算法(动态规划求最优路径)
(3)条件随机场 CRF
给定一组输入随机变量的条件下另一组输出随机变量的条件概率分布
密度。条件随机场假设输出变量构成马尔科夫随机场,而我们平时看到的
大多是线性链条随机场,也就是由输入对输出进行预测的判别模型。求解
方法为极大似然估计或正则化的极大似然估计。
之所以总把 HMM 和 CRF 进行比较,主要是因为 CRF 和 HMM 都利
用了图的知识,但是 CRF 利用的是马尔科夫随机场(无向图),而 HMM
的基础是贝叶斯网络(有向图)。而且 CRF 也有:概率计算问题、学习问
题和预测问题。大致计算方法和 HMM 类似,只不过不需要 EM 算法进行
学习问题。
(4)HMM 和 CRF 对比
其根本还是在于基本的理念不同,一个是生成模型,一个是判别模
型,这也就导致了求解方式的不同