马尔可夫链
马尔可夫链因俄国数学家Andrey Andreyevich Markov得名, 为状态空间中从一个状态到另一个状态转换的随机过程, 该过程要求具备"无记忆"的性质, 下一状态的概率分布只能由当前状态决定, 在时间序列中和它前面的事件无关, 这种特定类型的"无记忆性"称作马尔可夫性质.
马尔可夫假设
马尔可夫假设是马尔可夫链的基础.公式可以表示为\(p(X)=\prod_{i=1}^n p(S_t|S_{t-1})\). 它说明, 当前状态\(S_{t}\)只依赖于上一个状态\(S_{t-1}\), 而与之前的状态\(S_{1}, ..., S_{t-2}\)无关. 对于其余状态也是同理的.
上述只是一阶马尔可夫假设, 即假定当前的状态仅依赖于前面一个状态. 由此衍生出\(k\)阶马尔可夫假设, 即假设当前状态依赖于最近的\(k\)个状态, 即\(p(X)=\prod_{i=1}^n p(S_t|S_{t-1}, ..., S_{t-k})\). 这个概率又叫作状态转换概率.
例子
通过今天的天气预测明天的天气. 假设今天是雨天☔️, 预测明天的天气, 符合(一阶)马尔可夫假设. 下面是形象的概率图.
我们可以看到, 从雨天到晴天的概率是\(0.3\), 从雨天到阴天的概率是\(0.3\), 从雨天到雨天的概率是\(0.4\), 所以明天大概率还是雨天. 我们可以将上图用一个矩阵来表示.
其中\(S_{ij}=p(S_t=j|S_{t-1}=i)\), 表示从\(i\)到\(j\)的转换概率. 那么, 我们可不可以从任意的初始状态开始, 推导出后面的所有状态呢? 假设起始概率为\(\pi_i\), 表示马尔可夫链从状态\(i\)开始.
给你一个小小的练习, 计算下列天气变化的可能性:
- 晴天 -> 晴天 -> 多云 -> 多云
- 多云 -> 晴天 -> 多云 -> 雨天
隐马尔可夫模型
在普通的马尔可夫模型中, 系统的状态是完全可见的. 也就是说, 每个时刻系统处于哪个状态是已知的, 可以直接观测到. 而在隐马尔可夫模型, HMM中, 系统的状态是隐藏的, 无法直接观测到, 但是受状态影像的某些变量是可见的. 每一个状态在可能输出的序号上都有一概率分布, 因此输出符号的序列能够透露出状态序列的一些信息.
例子
假设现在我们漂到了一个岛上, 这里没有天气预报, 只有一片片的海藻, 而这些海藻的状态如干燥, 潮湿等和天气的变换有一定的关系, 既然海藻是能看到的, 那它就是观测状态, 天气信息看不到就是隐藏状态.
再举一个例子, 如下图所示是一个普通马尔可夫模型.
HMM就是在这个基础上, 加入了一个隐藏状态和观测状态的概念.
图中, X的状态是不可见的, 而Y的状态是可见的. 我们可以将X看成是天气情况, 而Y看成是某个人穿的衣物类型, 如下图所示.
我们的任务就是从这个人穿的衣物类型预测天气变化. 在这里, 有两种类型的概率:
- 转换概率: transition probabilities, 从一个隐藏状态到另一个隐藏状态的概率
- 观测概率: emission probabilities, 从一个隐藏状态到一个观测变量的过程
注意⚠️, HMM模型做了两个很重要的假设:
- 齐次马尔可夫链假设: 当前的隐藏状态之和前一个隐藏状态有关
- 观测独立性假设: 某个观测状态之和生成它的隐藏状态有关, 和别的观测状态无关
下图给出了一个可能的观测状态和隐藏状态之间的关系, 这个就是HMM所要达到的最终效果.
可视化表达:
参数
HMM的参数可以表示为\(\lambda = (\bm{A}, \bm{B}, \bm{\pi})\), 定义隐状态的可能的取值的数量为\(N\), 如雨天, 阴天, 晴天, \(N=3\). 观测变量的可能的取值的数量为\(M\), 如穿夹克, 穿棉袄, \(M=2\).
- 初始状态概率向量\(\bm{\pi}\). 它是一个长度为\(N\)的向量, 其中\(\pi_i\)表示在初始时刻\(t=1\)时处于隐状态\(i\)的概率, 所有的初始状态满足\(\sum_{i=1}^N \pi_i=1\)
- 状态转移概率矩阵\(\bm{A}\), \(\bm{A}=[a_{ij}]\), 它是一个\(N\times M\)的矩阵. \(a_{ij}\)表示在时刻\(t\)处于隐状态\(i\)时, 下一时刻\(t+1\)转移到隐状态\(j\)的概率, 所有的转移概率满足\(\sum_{j=1}^N a_{ij}=1\)
- 观测概率矩阵\(\bm{B}\), \(\bm{B}=[b_j(o_k)]\), 它是一个\(N\times M\)的矩阵. \(b_j(o_k)\)表示在隐状态\(j\)下生成观测值\(o_k\)的概率. 对于连续的观测值, 可以使用概率密度函数来表示概率
假设
HMM做了两个基本假设, 在上面的例子中也提到了.
- 齐次性假设: 即假设隐藏的马尔可夫链在任意时刻\(t\)的状态只依赖于它在前一时刻的状态, 与其他时刻的状态和观测无关, 也与时刻\(t\)本身无关
- 观测独立性假设: 即假设任意时刻的观测值只依赖于该时刻的马尔可夫链的状态, 与其他观测及状态无关
问题
HMM的三个基本问题:
- 概率计算问题: 给定模型\(\lambda = (\bm{A}, \bm{B}, \bm{\pi})\)和观测序列\(\bm{O}=(o_1, o_2, ..., o_M)\), 计算观测序列\(O\)出现的概率\(p(\bm{O}; \lambda)\). 即评估模型\(\lambda\)与观测序列\(\bm{O}\)之间的匹配程度
- 学习问题: 已知观测序列\(\bm{O}=(o_1, o_2, ..., o_M)\), 估计模型\(\lambda=(\bm{A}, \bm{B}, \bm{\pi})\)的参数, 使得在该模型下的观测序列概率\(p(\bm{O}; \lambda)\)最大, 即用极大似然估计的方法估计参数
- 预测问题(也称为解码问题): 已知模型\(\lambda = (\bm{A}, \bm{B}, \bm{\pi})\)和观测序列\(\bm{O}=(o_1, o_2, ..., o_M)\), 求对给定观测序列的条件概率\(P(\bm{I}|\bm{O})\)最大的状态序列\(\bm{I}=(i_1, i_2, ..., i_r)\), 即给定观测序列, 求最可能的对应的状态序列