HMM隐马尔科夫模型
对HMM做概述，主要摘抄自《统计学习方法》，概率计算为主，对学习和预测算法暂时忽略。
最后补充一些HMM在地图匹配上的应用
1.HMM
定义和理解
隐马尔可夫模型(Hidden Markov Model)，标注问题，生成模型。
定义：隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。
变量：
1. 状态集合：Q=\{q_1,q_2,...,q_N\}
2. 观测集合：V=\{v_1,v_2,...,v_M\}
3. 状态序列：I=(i_1,i_2,...,i_T)
4. 观测序列：O=(o_1,o_2,...,o_T)
5. 状态转移概率矩阵：表示时刻t时状态q_i且时刻t+1时状态q_j的概率
6. 观测概率矩阵：表示时刻 处于状态的条件下生成观测 v_k的概率
7. 初始状态概率向量：表示t=1时处于状态 的概率
隐马尔可夫模型由初始状态概率向量\pi、状态转移概率矩阵A、观测概率矩阵B决定
和确定了隐藏的马尔可夫链，生成不可观测的状态序列；决定了从状态序列生成观测序列
则模型表示为
两个基本假设：
1. 齐次马尔可夫性假设。即假设隐藏的马尔可夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其他时刻的状态和观测无关，也与时刻t无关2. 观测独立性假设。即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关
举个例子：从ABCD四个盒子拿球，每个盒子装有RW两色的球，已知取了5次得到的颜色，那么
状态集合：{A,B,C,D}
观测集合：{R,W}
观测序列：{R,R,W,W,R}
状态序列：隐含状态，一般是求解目标
观测序列生成过程
输入：HMM模型\lambda=(A,B,\pi)，观测序列长度T
输出：观测序列
步骤：
1. 按照初始状态分布生成状态i_1
2. t=1
3. 按状态i_t的观测概率分布b_{i_t}(k)生成o_t
4. 按状态的状态转移概率分布\{a_{i_ti_{t+1}}\}昌盛状态i_{t+1}
5. t=t+1，转到3，直到t=T
HMM的三个基本问题
- 概率计算问题。给定模型和观测序列，计算P(O|\lambda)
- 学习问题。一致观测序列O(o_1,o_2,...,o_T)，估计模型参数，使得在该模型下序列概率最大。即极大似然估计法
- 预测问题，即解码问题。已知模型和观测序列，求对给定观测序列的条件概率P(I|O)最大的状态序列
2.概率计算算法
前向算法
(前向概率)定义：给定隐马尔可夫模型\lambda，定义到时刻部分观测序列为o_1,o_2,...,o_t且状态为的概率为前向概率，记做
观测序列概率的前向算法
输入：隐马尔可夫模型，观测序列O
输出：观测序列概率
流程：
1. 初值。即时刻，状态为i且观测为o_1的概率2. 递推。即上一时刻各个状态下，转移到状态 的概率和，再计算观测为o_t+1的概率
3. 终止。
后向算法
(后向概率)定义：给定隐马尔可夫模型，定义到时刻状态为的条件下，从t+1到T部分观测序列为o_{t+1},o_{t+2},...,o_T的概率为后向概率，记做
观测序列概率的后向算法
输入：隐马尔可夫模型，观测序列
输出：观测序列概率
流程：
1. 初值。2. 递推。
3. 终止。
其他一些公式
- 利用前后向概率定义可以将序列概率如下。其中，t=T-1和t=1时，分别为前后向概率公式
- 给定模型和观测，在时刻处于状态的概率，记为
由前后向概率定义有
所以
-
给定模型和观测，在时刻处于状态且在时刻处于状态的概率为
-
在观测下状态出现的期望
-
在观测下状态转义的期望值
-
在观测下状态转移到状态j的期望值
学习算法
可以通过监督学习的极大似然估计解
或通过非监督的Baum-Welch算法（EM算法）求解
预测算法
主要解决给定模型和观测序列的情况下，最大概率的状态序列。
通过近似算法(取每个时刻最优)或维特比算法(动态规划)
地图匹配
-
- 基础数据：GPS轨迹点+道路网
-
应用：轨迹分类、轨迹离群值/异常检测、轨迹不确定性、轨迹模式挖掘
-
流程：基础数据->数据清洗->建立索引->选取候选路段->确定匹配路段
-
按依据信息划分：
1）几何匹配：点到点、点到线、线到线
2）拓扑关系：简单拓扑(作为筛选)、加权拓扑(作为权重)
3）概率统计：置信区间匹配、新型概率匹配方法（绘制概率椭圆）
4）先进匹配算法：模糊逻辑、证据理论、卡尔曼滤波、贝叶斯推理 -
问题：噪声和数据稀疏
-
按采样点范围划分(按计算时间)：局部/增量的方法(online)、全局方法(offline)
-
按采样频率划分：高频、低频、更低频
- HMM方法
1）隐含状态序列：路网
2）可观测序列：GPS点
3）状态转移概率矩阵A：t时刻i状态到t+1时刻j状态的概率，N*N；【状态中前后点越近概率越大；路段上的距离和观测上的距离越相近概率越大；考虑拓扑、考虑速度等】
4）观测概率矩阵B：t时刻i状态，观测到k的概率；【点与路段越近，概率越大】
5）初始状态概率矩阵：表示初始状态的概率