image
一 马尔科夫模型
• 每个状态只依赖之前有限个状态
– N阶马尔科夫：依赖之前n个状态
– 1阶马尔科夫（即《中文分词基础》中的二元模型）：仅仅依赖前一个状态
• p(w1,w2,w3,……,wn) = p(w1)p(w2|w1)p(w3|w1,w2)……p(wn|w1,w2,……,wn-1)
• =p(w1)p(w2|w1)p(w3|w2)……p(wn|wn-1)
• 例如：
• p(w1=今天，w2=我，w3=写，w4=了，w5=一个，w6=程序)
• =p(w1=今天)p(w2=我|w1=今天)p(w3=写|w2=我)……p(w6=程序|w5=一个)
image
总结：
image
• 参数（重要的3个概念）
– 状态，由数字表示，假设共有M个
– 初始概率，由𝜋 k 表示
如“时光荏苒，岁月如梭”，在100篇文章中，“时光”开头的文章共有10篇，则初始概率π（时光）= 10/100
image
– 状态转移概率，由a k,𝑚 表示
p（荏苒|时光）= 荏苒紧跟在时光后面的次数/所有文章（语料库）里“时光”的次数
image
例子：
• 天气
– 状态定义
• {晴天， 雨天， 多云}
– 状态转移概率a k,𝑚
• P(晴天|雨天)， P(雨天|多云)
– 初始概率𝜋 k
• P(晴天)， P(雨天)， P(多云)
image
马尔科夫模型参数估计
• 最大似然法（策略+算法）
– 状态转移概率a k,𝑚
• P(St+1=l|St=k)=l紧跟k出现的次数/k出现的总次数
– 初始概率𝜋 k
• P(S1=k)=k作为序列开始的次数/观测序列总数
马尔科夫模型应用
• 天气预测
– 前几天天气情况：晴天、晴天、雨天、多云
– 接下来一天的天气预计怎样？
– 接下来三天天气都是晴的可能性？
小结
• 马尔科夫模型是对一个序列数据建模，但有时我们需要对两个序列数据建模，此时只有一个序列的马尔科夫模型完全不能满足我们的需求
– 例如：
• 机器翻译：源语言序列 <-> 目标语言序列
• 语音识别：语音信号序列 <-> 文字序列
• 词性标注：文字序列 <-> 词性序列
– 写/一个/程序 ->输入序列分词
– Verb/Num/Noun ->输出序列是词性:动词/两次/名词
– 拼音纠错：原始文字序列 <--> 纠正过的文字序列
• 自己的事情自己做
• 自己的事情自已做
二 隐马尔科夫模型
• 观察序列O中的数据通常是由对应的隐藏序列数据决定的，彼此间相互独立
• 隐藏序列数据间相互依赖，通常构成了马尔科夫序列
– 例如，语音识别中声波信号每段信号都是相互独立的,有对应的文字决定
– 对应的文字序列中相邻的字相互依赖，构成Markov链
红色为输入序列，绿色为输出序列
image
• 观察和隐藏序列共同构成隐马模型
image
• O(𝑜1 𝑜 2 …𝑜 𝑇 )：观测序列，𝑜t 只依赖于𝑠 t
• S(𝑠 1 𝑠 2 …𝑠 𝑇 )：状态序列（隐藏序列），S是Markov序列，假设1阶Markov序列，则𝑠 t+1只依赖于𝑠t
HMM参数
– 状态，由数字表示，假设共有M个
– 观测，由数字表示，假设共有N个
– 初始概率，由𝜋k 表示 k出现在第一个的概率
– 状态转移概率，由 ak,l 表示
ak,l = P(𝑆t+1 = l|𝑆t = k ) k,l = 1,2,…,M
– 发射概率，由bk(u) 表示,是上图“这”-“信1”的桥梁，比如了读liao还是le
bk(u) = P (Ot = 𝑢|𝑆t = k) 𝑢 = 1,2,…,N k = 1,2,…,M
比如给定“了”，liao=40%,le=60%,所以发射概率为p(liao|了)=40%
• 初始概率（取概率的Log值）
image
– BEMS：位置信息
• B（开头）
• M（中间)
• E(结尾)
• S(独立成词）
– 词性：
• n 名词
• nr 人名
• ns 地名
• v 动词
• vd 副动词
• vn 名动词
比如“广州本田雅阁汽车”->广州：BE 本田雅阁：4个汉字组成的词语BMME（中间用M表示）
未登录词“雅阁汽车”在语料库中不存在，将其一个字为一个词切分，jieba分词然后通过HMM来解析，则输入序列为“雅”“阁”“汽”“车”，输出序列为<B,n>,<E,n>,<B,n>,<E,n>，则得到“雅阁”、“汽车”
如果输出序列为<B,n>,<E,n>,<M,n>,<S,n>，则得到“雅阁汽”、“车”
进入jieba-master\jieba\posseg，查看prob_start.py，可以看到文章以n开头的概率大于量词开头的概率，几乎都是B开头，ME几乎为0，只不过为了平衡，给了一个很小的默认值而已
image.png
• 转移概率
image
查看prob_trans.py
image.png
• 发射概率
image
查看prob_emit.py，比如由（B，a）发射成某一个汉字的概率，比如叹词词性，几乎就为啊唉呜哇
image.png
HMM生成过程
• 先生成第一个状态，然后依次由当前状态生成下一个状态，最后每个状态发射出一个观察值
HMM的生成过程
求两个序列的联合概率P(o1:t,s1:t)，等于所有转移概率和发射概率的连乘（初始概率所有的状态转移概率发射概率）,此时图已生成完成，初始概率πk和状态转移概率、发射概率都将不再发生变化。
• 三个基本问题
– 模型参数估计
M个状态就有M个初始概率 状态转移概率为一个M*M的矩阵 发射概率个数为M个状态和N个观测的乘积
参数估计
– 给定模型𝜃，计算一个观测序列出现的概率P𝜃（O）
O为HMM生成过程中序列O
– 给定模型𝜃和观测序列𝑃，找到最优的隐藏状态序列（切分方案）
QQ截图20180516103132.png
前向 - 后向算法
前向 - 后向概率
前向概率：
后向概率：t时刻k的概率，
前向概率
无论前M个状态如何转移，只要t时刻为K的概率，然后对1~t-1时刻的所有概率进行加和得到，这种方式过于粗暴了，实践复杂度太高
前向概率公式
前向概率公式的优化
image.png
公式推导
最终结果
后向概率
后向概率公式
其他概率
其他概率
其他概率公式
隐马模型参数估计
image.png
完全数据下的参数估计
完全数据下的参数估计
完全数据下的参数估计
完全数据下的参数估计
HMM的应用
image.png
• 给定O，寻找最优的S
• 寻找一条最优的路径
• 如果比较所有路径：遍历所有的S，算出一个最大的，则时间复杂度是𝑁 𝑇 ，不可接受！
image.png
HMM应用-viterbi算法
• 动态规划，在t+1位置重用t的结果
QQ截图20180331145551.png
image.png
网友评论