自然语言处理基础
通用应用
1、机器翻译:计算机具备将一种语言翻译成另一种语言的能力
2、情感分析:计算机能够判断用户评论的情感色彩
3、智能问答:计算机能够正确的回答输入的问题
4、文摘生成:计算机能够准确归纳、总结并生成文本摘要
5、文本分类:计算机能够采集各种文章,进行主题分析,从而进行自动分类
6、舆论分析:计算机能够判断目前的舆论的导向
7、知识图谱:知识点相互连接而形成的语义网络
基本术语
1、分词(Segment):将文本分割成最小的能够独立活动的有意义的语言成分。对中文来说十分重要。例如:“美国/会/通过对台售武法案”又可“美/国会/通过对台售武法案”
2、词性标注(Part-of-speech Tagging):将词性(动词、名词、形容词等)标注,目的是表征词的一种隐藏状态,隐藏状态的转移就构成了状态转移序列。例如:我/r 爱/v 北京/ns 天安门/ns
3、命名实体识别(NER, Named Entity Recognition):从文本中识别具有特定类别的实体(通常是名词),例如人名、地名、机构名、专有名词等。例如:山东鲁能泰山
4、句法分析(Syntax Parsing):最初利用语言学家的只是来构建的。目的是解析句子中各个成分的依赖关系,往往最终生成的结果是一颗句法分析树。句法分析可以解决传统词袋模型不考虑上下文的问题。
5、指代消除(Anaphora Resolution):他她它,这里...等代词到底代表前文的什么内容
6、情感识别(Emotion Recognition):情感识别本质是分类问题,一般可分为正面、负面、中性等。
7、纠错(Correction):自动纠错在搜索技术以及输入法中利用的多。由于用户单词拼错等等...
8、问答系统(QA System):类似机器人的人工智能系统
知识结构
1、句法语义分析:针对目标句子,进行各种句法分析,如分词、词性标记、命名实体识别及链接、句法分析、语义角色和多义词消歧等。
2、关键词抽取:抽取目标文本的主要信息,比如从一条新闻中抽取关键信息。主要是了解是谁、于何时、为何、对谁、做了何事、产生了有什么结果。涉及实体识别、时间抽取、因果关系抽取等多项关键技术。
3、文本挖掘:主要包含了对文本的聚类、分类、信息抽取、摘要、情感分析以及对挖掘的信息和知识的可视化、交互式的呈现界面
4、机器翻译:将输入的源语言通过自动翻译转化为另一种语言的文本。根据输入的数据类型的不同,可细分为文本翻译、语音翻译、手语翻译、图形翻译等。
5、信息检索:对大规模的文档进行索引。可简单对文档中的词汇,赋以不同的权重来建立索引,也可使用算法模型来建立更加深层次的索引。查询时,首先对输入来进行分析,然后在索引里面查找匹配的候选文档,再根据一个排序机制把候选文档排序,最后输出排序得分较高的文档。
6、问答系统:针对某个自然语言表达的问题,由问答系统给出一个精准的答案。需要对自然语言查询语句进行语义分析,包括实体链接、关系识别,形成逻辑表达式,然后到知识库中查找可能的候选答案并通过一个排序机制找出最佳的答案。
7、对话系统:系统通过多回合对话,跟用户进行聊天、回答、完成某项任务。主要涉及用户意图理解、通用聊天引擎、问答引擎、对话管理等技术。此外,为了体现上下文相关,要具备多轮对话能力。同时,为了体现个性化,对话系统还需要基于用户画像做个性化回复。
三个层面
1、词法层面:包括分词和词性标注两部分。
2、句法分析:对输入的文本以句子为单位,进行分析得到句子的句法结构的处理过程。
3、语义分析:理解句子表达的真实语义。
自然语言处理发展
前期分为两个阶段:人类学习语言的方式(基于规则)、基于数学模型和统计方法(基于统计);
时至今日,大家在使用深度学习解决问题,探索知识图谱在自然语言处理领域的方法。
人类学习语言的方式(基于规则)
20世纪50至70年代,对计算机处理自然语言的认识基本都基于人类学习语言的方式,也就是说,想方设法用电脑模拟人脑。当时,学术界认为要让机器完成翻译或者语音识别等人类才能做得事,必须要让计算机拥有类似人类这样的智能。
基于数学模型和统计方法(基于统计)
20世纪70年代,基于统计的方法的核心模型是通信系统 加隐马尔可夫模型 。之后随着计算能力的提高和数据量的不断增加,通过统计得到的句法规则甚至比语言学家总结的更具说服力。
基于深度学习的方法
基于知识图谱的方法
To be continued
通信模型
一个典型的通信系统:发送者(人或者机器)发送信息时,需要采取一种能在媒体中(比如空气、电线)传播的信号(语音或电话线的调制信号),这个过程就是广义上的编码。然后通过媒体传播到接收方,这个过程就是信道传输。在接收方,接受者(人或者机器)根据事先约定好的方法,将这些信号还原成发送者的信息,这个过程就是广义上的解码。
其中 S 1 , S 2 , S 3 , … S_1,S_2,S_3,\dots S 1 , S 2 , S 3 , … 表示信息源发出的信号(比如手机发送的信号)。 O 1 , O 2 , O 3 , … O_1,O_2,O_3,\dots O 1 , O 2 , O 3 , … 是接收器(比如另一部手机)接收到的信号。通信中的解码就是根据接收到的信号 O 1 , O 2 , O 3 , … O_1,O_2,O_3,\dots O 1 , O 2 , O 3 , … 还原发送的信号 S 1 , S 2 , S 3 , … S_1,S_2,S_3,\dots S 1 , S 2 , S 3 , … 。在通信中,如何根据接收端的观测信号来推测信号源发送的信息呢?只需要从所有的源信息中找到最可能产生出观测信号的那一个信息。用概率论的语言来描述,就是在已知 O 1 , O 2 , O 3 , … O_1,O_2,O_3,\dots O 1 , O 2 , O 3 , … 的情况下,求得令条件概率
P ( S 1 , S 2 , S 3 , ⋯ ∣ O 1 , O 2 , O 3 , ⋯ ) P(S_1,S_2,S_3,\cdots|O_1,O_2,O_3,\cdots) P ( S 1 , S 2 , S 3 , ⋯ ∣ O 1 , O 2 , O 3 , ⋯ ) 达到最大值的那个信息串 S 1 , S 2 , S 3 , ⋯ S_1,S_2,S_3,\cdots S 1 , S 2 , S 3 , ⋯ ,即
S 1 , S 2 , S 3 , ⋯ = a r g m a x a l l S 1 , S 2 , S 3 , ⋯ P ( S 1 , S 2 , S 3 , ⋯ ∣ O 1 , O 2 , O 3 , ⋯ ) S_1,S_2,S_3,\cdots = \mathop{arg max} \limits_{all S_1,S_2,S_3,\cdots} P(S_1,S_2,S_3,\cdots|O_1,O_2,O_3,\cdots) S 1 , S 2 , S 3 , ⋯ = a ll S 1 , S 2 , S 3 , ⋯ a r g ma x P ( S 1 , S 2 , S 3 , ⋯ ∣ O 1 , O 2 , O 3 , ⋯ )
上面的概率不容易直接求出,不过可以间接地计算它。利用贝叶斯公式可以把上述公式等价变换成
P ( O 1 , O 2 , O 3 , ⋯ ∣ S 1 , S 2 , S 3 , ⋯ ) ⋅ P ( S 1 , S 2 , S 3 , ⋯ ) P ( O 1 , O 2 , O 3 , ⋯ ) \frac{P(O_1,O_2,O_3,\cdots|S_1,S_2,S_3,\cdots)\cdot P(S_1,S_2,S_3,\cdots)}{P(O_1,O_2,O_3,\cdots)} P ( O 1 , O 2 , O 3 , ⋯ ) P ( O 1 , O 2 , O 3 , ⋯ ∣ S 1 , S 2 , S 3 , ⋯ ) ⋅ P ( S 1 , S 2 , S 3 , ⋯ )
其中 P ( O 1 , O 2 , O 3 , ⋯ ∣ S 1 , S 2 , S 3 , ⋯ ) P(O_1,O_2,O_3,\cdots|S_1,S_2,S_3,\cdots) P ( O 1 , O 2 , O 3 , ⋯ ∣ S 1 , S 2 , S 3 , ⋯ ) 表示信息 S 1 , S 2 , S 3 , ⋯ S_1,S_2,S_3,\cdots S 1 , S 2 , S 3 , ⋯ 在传输后变成接收的信号 O 1 , O 2 , O 3 , ⋯ O_1,O_2,O_3,\cdots O 1 , O 2 , O 3 , ⋯ 的可能性;而 P ( S 1 , S 2 , S 3 , ⋯ ) P(S_1,S_2,S_3,\cdots) P ( S 1 , S 2 , S 3 , ⋯ ) 表示 S 1 , S 2 , S 3 , ⋯ S_1,S_2,S_3,\cdots S 1 , S 2 , S 3 , ⋯ 本身是一个在接收端合乎情理的信号(比如一个合乎情理的句子)的可能性;最后 P ( O 1 , O 2 , O 3 , ⋯ ) P(O_1,O_2,O_3,\cdots) P ( O 1 , O 2 , O 3 , ⋯ ) 表示在发送端(比如说话的人)产生信息 O 1 , O 2 , O 3 , ⋯ O_1,O_2,O_3,\cdots O 1 , O 2 , O 3 , ⋯ 的可能性,因为一旦信息 O 1 , O 2 , O 3 , ⋯ O_1,O_2,O_3,\cdots O 1 , O 2 , O 3 , ⋯ 产生了,它就不会改变了,这时 P ( O 1 , O 2 , O 3 , ⋯ ) P(O_1,O_2,O_3,\cdots) P ( O 1 , O 2 , O 3 , ⋯ ) 就是一个可以忽略的常数。因此,上面的公式可等价成
P ( O 1 , O 2 , O 3 , ⋯ ∣ S 1 , S 2 , S 3 , ⋯ ) ⋅ P ( S 1 , S 2 , S 3 , ⋯ ) P(O_1,O_2,O_3,\cdots|S_1,S_2,S_3,\cdots)\cdot P(S_1,S_2,S_3,\cdots) P ( O 1 , O 2 , O 3 , ⋯ ∣ S 1 , S 2 , S 3 , ⋯ ) ⋅ P ( S 1 , S 2 , S 3 , ⋯ )
虽然多了一项,但这个公式完全可以用隐马尔可夫模型来估计。
隐马尔可夫模型
更详细可见机器学习概率图模型部分。
马尔可夫链
假设随机过程中各个状态s t s_t s t 的概率分布,只与它之前的一个状态s t − 1 s_{t-1} s t − 1 有关,即 P ( s t ∣ s 1 , s 2 , s 3 , … , s t − 1 ) = P ( s t ∣ s t − 1 ) P(s_t|s_1,s_2,s_3,\dots,s_{t-1}) = P(s_t|s_{t-1}) P ( s t ∣ s 1 , s 2 , s 3 , … , s t − 1 ) = P ( s t ∣ s t − 1 ) 。比如硬性规定今天的气温只跟昨天有关,跟前天或之前的天气无关。这种假设未必适用所有的应用,但是至少对以前很多不好解决的问题给出了近似解。这个假设后来被命名为马尔可夫假设,而符合这个假设的随机过程则称为马尔可夫过程,也称为马尔可夫链。
上图中,四个圈表示四个状态,每条边表示一个可能的状态转换,边上的权值为转移概率。例如,状态 m 1 m_1 m 1 到状态 m 2 m_2 m 2 之间只有一条边,且边上的权重为1.0。这表示从状态 m 1 m_1 m 1 只可能转换到状态 m 2 m_2 m 2 ,转移概率为1.0。从 m 2 m_2 m 2 出发的有两条边:到 m 3 m_3 m 3 和到 m 4 m_4 m 4 。其中权值0.6表示:如果某个时刻 t t t 的状态 s t s_t s t 是 m 2 m_2 m 2 ,则下一个时刻的状态 s t + 1 = m 3 s_{t+1} = m_3 s t + 1 = m 3 的概率是60%。如果用数学符号表示是 P ( s t + 1 = m 3 ∣ s t = m 2 ) = 0.6 P(s_{t+1}=m_3|s_t=m_2) = 0.6 P ( s t + 1 = m 3 ∣ s t = m 2 ) = 0.6 。类似的,有 P ( s t + 1 = m 4 ∣ s t = m 2 ) = 0.4 P(s_{t+1}=m_4|s_t=m_2) = 0.4 P ( s t + 1 = m 4 ∣ s t = m 2 ) = 0.4 。随机选择一个状态作为初始状态,随后按照上述规则随机选择后续状态。这样运行一段时间 T T T 后,就会产生一个状态序列: s 1 , s 2 , s 3 , … , s T s_1,s_2,s_3,\dots,s_T s 1 , s 2 , s 3 , … , s T 。
隐马尔可夫模型
隐马尔可夫模型是马尔可夫链的一个扩展:任一时刻 t t t 的状态 s t s_t s t 是不可见的。观察者没法通过观察到一个状态序列 s 1 , s 2 , s 3 , … s T s_1,s_2,s_3,\dots s_T s 1 , s 2 , s 3 , … s T 来推测转移概率等参数。但是,隐马尔可夫模型在每个时刻 t t t 会输出一个符号 o t o_t o t ,而且 o t o_t o t 跟 s t s_t s t 相关且仅跟 s t s_t s t 相关。即,我们观测不到状态变化,只能观测到输出符号。
基于马尔可夫假设和独立输出假设,我们可以计算出某个特定的状态序列 s 1 , s 2 , s 3 , ⋯ s_1,s_2,s_3,\cdots s 1 , s 2 , s 3 , ⋯ 产生输出符号 o 1 , o 2 , o 3 , ⋯ o_1,o_2,o_3,\cdots o 1 , o 2 , o 3 , ⋯ 的概率
P ( s 1 , s 2 , s 3 , ⋯ , o 1 , o 2 , o 3 , ⋯ ) = ∏ t P ( s t ∣ s t − 1 ) ⋅ P ( o t ∣ s t ) P(s_1,s_2,s_3,\cdots,o_1,o_2,o_3,\cdots) = \prod \limits_t P(s_t|s_{t-1})\cdot P(o_t|s_t) P ( s 1 , s 2 , s 3 , ⋯ , o 1 , o 2 , o 3 , ⋯ ) = t ∏ P ( s t ∣ s t − 1 ) ⋅ P ( o t ∣ s t )
现在我们把马尔可夫假设和独立输出假设用于通信编码问题(上一节最后一个公式),即把
P ( o 1 , o 2 , o 3 , ⋯ ∣ s 1 , s 2 , s 3 , ⋯ ) = ∏ t P ( o t ∣ s t ) P(o_1,o_2,o_3,\cdots|s_1,s_2,s_3,\cdots) = \prod \limits_t P(o_t|s_t) P ( o 1 , o 2 , o 3 , ⋯ ∣ s 1 , s 2 , s 3 , ⋯ ) = t ∏ P ( o t ∣ s t )
P ( s 1 , s 2 , s 3 , ⋯ ) = ∏ t P ( s t ∣ s t − 1 ) P(s_1,s_2,s_3,\cdots) = \prod \limits_t P(s_t|s_{t-1}) P ( s 1 , s 2 , s 3 , ⋯ ) = t ∏ P ( s t ∣ s t − 1 )
这样通信的解码问题就可以用隐马尔可夫模型来解决了。至于如何找出上面式子的最大值,进而找出识别的句子 s 1 , s 2 , s 3 , ⋯ s_1,s_2,s_3,\cdots s 1 , s 2 , s 3 , ⋯ ,可以利用维特比算法来解决。
针对不同的应用, P ( s 1 , s 2 , s 3 , ⋯ ∣ o 1 , o 2 , o 3 , ⋯ ) P(s_1,s_2,s_3,\cdots|o_1,o_2,o_3,\cdots) P ( s 1 , s 2 , s 3 , ⋯ ∣ o 1 , o 2 , o 3 , ⋯ ) 的名称也各不相同,在语音识别中它称为“声学模型”,机器翻译中是“翻译模型”,在拼写矫正中是“纠错模型”。
隐马尔可夫模型的训练
围绕着隐马尔可夫模型有三个基本问题:
1、给定一个模型,如何计算某个特定的输出序列的概率
2、给定一个模型和某个特定的输出序列,如何找到最能产生这个输出序列的状态序列
3、给定足够量的观测数据,如何估计隐马尔可夫模型的参数
1、给定一个模型,如何计算某个特定的输出序列的概率
使用前向与后向(Forward-Backward)算法。
2、给定一个模型和某个特定的输出序列,如何找到最能产生这个输出序列的状态序列
使用维特比(Viterbi Algorithm)算法。
3、给定足够量的观测数据,如何估计隐马尔可夫模型的参数
使用鲍姆-韦尔奇算法。
1、给定一个模型,如何计算某个特定的输出序列的概率
使用前向与后向(Forward-Backward)算法。现实任务中,许多任务需要根据以往的观测序列来推测当前时刻最有可能的观测值,这显然可转化为这个计算特定输出序列的概率的问题。
前向算法
给定隐马尔可夫模型 λ \lambda λ ,定义到时刻 t t t 部分观测序列为 o 1 , o 2 , … , o t o_1,o_2,\dots,o_t o 1 , o 2 , … , o t 且状态为 q i q_i q i 的概率为前向概率 ,记作: α t ( i ) = P ( o 1 , o 2 , … , o t , i t = q i ∣ λ ) \alpha_t(i)=P(o_1,o_2,\dots,o_t,i_t=q_i|\lambda) α t ( i ) = P ( o 1 , o 2 , … , o t , i t = q i ∣ λ ) 可以递推地求得前向概率 α t ( i ) \alpha_t(i) α t ( i ) 及观测序列概率P ( O ∣ λ ) P(O|\lambda) P ( O ∣ λ )
输入:隐马尔可夫模型 λ \lambda λ ,观测序列 O O O
输出:观测序列概率 P ( O ∣ λ ) P(O|\lambda) P ( O ∣ λ )
(1)初值: α 1 ( i ) = π i b i ( o 1 ) , i = 1 , 2 , … , N \alpha_1(i)=\pi_ib_i(o_1),\ \ i=1,2,\dots,N α 1 ( i ) = π i b i ( o 1 ) , i = 1 , 2 , … , N
(2)递推:对 t = 1 , 2 , … , T − 1 t = 1,2,\dots,T-1 t = 1 , 2 , … , T − 1
α t + 1 ( i ) = [ ∑ j = 1 N α t ( j ) α j i ] b i ( O t + 1 ) , i = 1 , 2 , … , N \alpha_{t+1}(i) = [\sum\limits_{j=1}^N\alpha_t(j)\alpha_{ji}]b_i(O_{t+1}), \ \ \ i=1,2,\dots,N α t + 1 ( i ) = [ j = 1 ∑ N α t ( j ) α ji ] b i ( O t + 1 ) , i = 1 , 2 , … , N
(3)终止: P ( O ∣ λ ) = ∑ i = 1 N α T ( i ) P(O|\lambda) = \sum\limits_{i=1}^N\alpha_T(i) P ( O ∣ λ ) = i = 1 ∑ N α T ( i )
递推部分就是上个状态转移到当前状态的所有可能乘上当前状态出现对应观测的概率;终止部分即把所有可能出现这种观测的可能加起来,即 P ( O ∣ λ ) P(O|\lambda) P ( O ∣ λ )
举例如下
考虑盒子和球模型 λ = ( A , B , π ) \lambda=(A,B,\pi) λ = ( A , B , π ) ,状态集合 Q = { 1 , 2 , 3 } Q = \{1,2,3\} Q = { 1 , 2 , 3 } ,观测集合 V = { 红 , 白 } V = \{红,白\} V = { 红 , 白 } ,
A = [ 0.5 0.2 0.3 0.3 0.5 0.2 0.2 0.3 0.5 ] A = \left[ \begin{matrix} 0.5\ \ \ \ 0.2\ \ \ \ 0.3\\ 0.3\ \ \ \ 0.5\ \ \ \ 0.2\\ 0.2\ \ \ \ 0.3\ \ \ \ 0.5\end{matrix} \right] A = 0.5 0.2 0.3 0.3 0.5 0.2 0.2 0.3 0.5 , B = [ 0.5 0.5 0.4 0.6 0.7 0.3 ] B = \left[ \begin{matrix} 0.5\ \ \ \ 0.5\\ 0.4\ \ \ \ 0.6\\ 0.7\ \ \ \ 0.3\end{matrix} \right] B = 0.5 0.5 0.4 0.6 0.7 0.3 , π = ( 0.2 , 0.4 , 0.4 ) T \pi = (0.2,0.4,0.4)^T π = ( 0.2 , 0.4 , 0.4 ) T
设 T = 3 T = 3 T = 3 , O = ( 红 , 白 , 红 ) O = (红,白,红) O = ( 红 , 白 , 红 ) ,用前向算法计算 P ( O ∣ λ ) P(O|\lambda) P ( O ∣ λ )
(1)初值: α 1 ( 1 ) = π 1 b 1 ( o 1 ) = 0.2 × 0.5 = 0.1 \alpha_1(1) = \pi_1b_1(o_1)=0.2\times 0.5 = 0.1 α 1 ( 1 ) = π 1 b 1 ( o 1 ) = 0.2 × 0.5 = 0.1
α 1 ( 2 ) = π 2 b 2 ( o 1 ) = 0.4 × 0.4 = 0.16 \alpha_1(2) = \pi_2b_2(o_1)=0.4\times 0.4 = 0.16 α 1 ( 2 ) = π 2 b 2 ( o 1 ) = 0.4 × 0.4 = 0.16
α 1 ( 3 ) = π 3 b 3 ( o 1 ) = 0.4 × 0.7 = 0.28 \alpha_1(3) = \pi_3b_3(o_1)=0.4\times 0.7 = 0.28 α 1 ( 3 ) = π 3 b 3 ( o 1 ) = 0.4 × 0.7 = 0.28
α 2 ( 1 ) = [ ∑ i = 1 3 α 1 ( i ) α i 1 ] b 1 ( o 2 ) = [ 0.1 × 0.5 + 0.16 × 0.3 + 0.28 × 0.2 ] × 0.5 = 0.077 \alpha_2(1)=[\sum\limits_{i=1}^3\alpha_1(i)\alpha_{i1}]b_1(o_2) = [0.1\times 0.5+0.16\times 0.3+0.28\times 0.2]\times 0.5=0.077 α 2 ( 1 ) = [ i = 1 ∑ 3 α 1 ( i ) α i 1 ] b 1 ( o 2 ) = [ 0.1 × 0.5 + 0.16 × 0.3 + 0.28 × 0.2 ] × 0.5 = 0.077
α 2 ( 2 ) = [ ∑ i = 1 3 α 1 ( i ) α i 2 ] b 2 ( o 2 ) = [ 0.1 × 0.2 + 0.16 × 0.5 + 0.28 × 0.3 ] × 0.6 = 0.1104 \alpha_2(2)=[\sum\limits_{i=1}^3\alpha_1(i)\alpha_{i2}]b_2(o_2) = [0.1\times 0.2+0.16\times 0.5+0.28\times 0.3]\times 0.6=0.1104 α 2 ( 2 ) = [ i = 1 ∑ 3 α 1 ( i ) α i 2 ] b 2 ( o 2 ) = [ 0.1 × 0.2 + 0.16 × 0.5 + 0.28 × 0.3 ] × 0.6 = 0.1104
α 2 ( 3 ) = [ ∑ i = 1 3 α 1 ( i ) α i 3 ] b 3 ( o 2 ) = [ 0.1 × 0.3 + 0.16 × 0.2 + 0.28 × 0.5 ] × 0.3 = 0.0606 \alpha_2(3)=[\sum\limits_{i=1}^3\alpha_1(i)\alpha_{i3}]b_3(o_2) = [0.1\times 0.3+0.16\times 0.2+0.28\times 0.5]\times 0.3=0.0606 α 2 ( 3 ) = [ i = 1 ∑ 3 α 1 ( i ) α i 3 ] b 3 ( o 2 ) = [ 0.1 × 0.3 + 0.16 × 0.2 + 0.28 × 0.5 ] × 0.3 = 0.0606
α 3 ( 1 ) = [ ∑ i = 1 3 α 2 ( i ) α i 1 ] b 1 ( o 3 ) = 0.04187 \alpha_3(1)=[\sum\limits_{i=1}^3\alpha_2(i)\alpha_{i1}]b_1(o_3) =0.04187 α 3 ( 1 ) = [ i = 1 ∑ 3 α 2 ( i ) α i 1 ] b 1 ( o 3 ) = 0.04187
α 3 ( 2 ) = [ ∑ i = 1 3 α 2 ( i ) α i 2 ] b 2 ( o 3 ) = 0.03551 \alpha_3(2)=[\sum\limits_{i=1}^3\alpha_2(i)\alpha_{i2}]b_2(o_3) =0.03551 α 3 ( 2 ) = [ i = 1 ∑ 3 α 2 ( i ) α i 2 ] b 2 ( o 3 ) = 0.03551
α 3 ( 3 ) = [ ∑ i = 1 3 α 2 ( i ) α i 3 ] b 3 ( o 3 ) = 0.05284 \alpha_3(3)=[\sum\limits_{i=1}^3\alpha_2(i)\alpha_{i3}]b_3(o_3) =0.05284 α 3 ( 3 ) = [ i = 1 ∑ 3 α 2 ( i ) α i 3 ] b 3 ( o 3 ) = 0.05284
(3)终止: P ( O ∣ λ ) = ∑ i = 1 3 α 3 ( i ) = 0.13022 P(O|\lambda)=\sum\limits_{i=1}^3\alpha_3(i)=0.13022 P ( O ∣ λ ) = i = 1 ∑ 3 α 3 ( i ) = 0.13022
后向算法
给定隐马尔可夫模型 λ \lambda λ ,定义在时刻 t t t 状态为 q i q_i q i 的条件下,从 t + 1 t+1 t + 1 到 T T T 的部分观测序列为 o t + 1 , o t + 2 , … , o T o_{t+1},o_{t+2},\dots,o_{T} o t + 1 , o t + 2 , … , o T 的概率为后向概率 ,记作: β t ( i ) = P ( o t + 1 , o t + 2 , … , o T ∣ i t = q i , λ ) \beta_t(i)=P(o_{t+1},o_{t+2},\dots,o_T|i_t=q_i,\lambda) β t ( i ) = P ( o t + 1 , o t + 2 , … , o T ∣ i t = q i , λ ) 可以用递推地方法求得后向概率 β t ( i ) \beta_t(i) β t ( i ) 及观测序列概率 P ( O ∣ λ ) P(O|\lambda) P ( O ∣ λ )
输入:隐马尔可夫模型 λ \lambda λ ,观测序列 O O O
输出:观测序列概率 P ( O ∣ λ ) P(O|\lambda) P ( O ∣ λ )
(1) β T ( i ) = 1 , i = 1 , 2 , … , N \beta_T(i)=1,\ \ \ i=1,2,\dots,N β T ( i ) = 1 , i = 1 , 2 , … , N
(2)对 t = T − 1 , T − 2 , … , 1 t = T-1,T-2,\dots,1 t = T − 1 , T − 2 , … , 1
β t ( i ) = ∑ j = 1 N α i j b j ( o t + 1 ) β t + 1 ( j ) , i = 1 , 2 , … , N \beta_t(i)=\sum\limits_{j=1}^N\alpha_{ij}b_j(o_{t+1})\beta_{t+1}(j),\ \ \ i=1,2,\dots,N β t ( i ) = j = 1 ∑ N α ij b j ( o t + 1 ) β t + 1 ( j ) , i = 1 , 2 , … , N
(3) P ( O ∣ λ ) = ∑ i = 1 N π i b i ( o 1 ) β 1 ( i ) P(O|\lambda) = \sum\limits_{i=1}^N\pi_ib_i(o_1)\beta_1(i) P ( O ∣ λ ) = i = 1 ∑ N π i b i ( o 1 ) β 1 ( i )
2、给定一个模型和某个特定的输出序列,找到最能产生这个输出序列的状态序列
使用维特比(Viterbi Algorithm)算法。在语音识别等任务中,观测值为语音信号,隐藏状态为文字,目标就是根据观测信号来推断最有可能的状态序列(即对应的文字)。
维特比算法是一种动态规划方法,核心思想是:如果最终的最优路径经过某个 o i o_i o i ,那么从初始节点到 o i − 1 o_{i-1} o i − 1 点的路径必然也是一个最优路径,因为每一个节点 o i o_i o i 只会影响前后两个P ( o i − 1 ∣ o i ) P(o_{i-1}|o_i) P ( o i − 1 ∣ o i ) 和 P ( o i ∣ o i + 1 ) P(o_i|o_{i+1}) P ( o i ∣ o i + 1 )
维特比算法实际上是用动态规划解隐马尔可夫模型预测问题,即用动态规划求概率最大路径。这时一条路径对应着一个状态序列。根据动态规划原理,最优路径具有这样的特性:如果最优路径在时刻 t t t 通过结点 i t ∗ i_t^* i t ∗ ,那么这一路径从结点 i t ∗ i_t^* i t ∗ 到终点 i T ∗ i_T^* i T ∗ 的部分路径,对于从 i t ∗ i_t^* i t ∗ 到 i T ∗ i_T^* i T ∗ 的所有可能的部分路径来说,必须是最优的。因为假如不是这样,那么从 i t ∗ i_t^* i t ∗ 到 i T ∗ i_T^* i T ∗ 就有另一条更好的部分路径存在,如果把它和从 i 1 ∗ i_1^* i 1 ∗ 到 i t ∗ i_t^* i t ∗ 的部分路径连接起来,就会形成一条比原来的路径更优的路径,这是矛盾的。依据这一原理,我们只需从时刻 t = 1 t = 1 t = 1 开始,递推地计算在时刻 t t t 状态为 i i i 的各条部分路径的最大概率,直至得到时刻 t = T t = T t = T 状态为 i i i 的各条路径的最大概率。
输入:模型 λ = ( A , B , π ) \lambda =(A,B,\pi) λ = ( A , B , π ) 和观测 O = ( o 1 , o 2 , … , o T ) O = (o_1,o_2,\dots,o_T) O = ( o 1 , o 2 , … , o T )
输出:最优路径 I ∗ = ( i 1 ∗ , i 2 ∗ , … , i T ∗ ) I^* = (i_1^*,i_2^*,\dots,i_T^*) I ∗ = ( i 1 ∗ , i 2 ∗ , … , i T ∗ )
(1)初始化: δ 1 ( i ) = π i b i ( o 1 ) , i = 1 , 2 , … , N ψ 1 ( i ) = 0 , i = 1 , 2 , … , N \delta_1(i)=\pi_ib_i(o_1),\ \ \ i=1,2,\dots,N\ \ \ \ \psi_1(i)=0,\ \ \ i=1,2,\dots,N δ 1 ( i ) = π i b i ( o 1 ) , i = 1 , 2 , … , N ψ 1 ( i ) = 0 , i = 1 , 2 , … , N
(2)递推:对 t = 2 , 3 , … , T t = 2,3,\dots,T t = 2 , 3 , … , T
δ t ( i ) = max 1 ≤ j ≤ N [ δ t − 1 ( j ) a j i ] b i ( o t ) , i = 1 , 2 , … , N \delta_t(i) = \max\limits_{1\leq j\leq N}[\delta_{t-1}(j)a_{ji}]b_i(o_t),\ \ \ i=1,2,\dots,N δ t ( i ) = 1 ≤ j ≤ N max [ δ t − 1 ( j ) a ji ] b i ( o t ) , i = 1 , 2 , … , N
ψ t ( i ) = arg max 1 ≤ j ≤ N [ δ t − 1 ( j ) a j i ] , i = 1 , 2 , … , N \psi_t(i) = \arg\max\limits_{1\leq j \leq N}[\delta_{t-1}(j)a_{ji}],\ \ \ i=1,2,\dots,N ψ t ( i ) = arg 1 ≤ j ≤ N max [ δ t − 1 ( j ) a ji ] , i = 1 , 2 , … , N
(3)终止: P ∗ = max 1 ≤ i ≤ N δ T ( i ) P^* = \max\limits_{1\leq i\leq N}\delta_T(i) P ∗ = 1 ≤ i ≤ N max δ T ( i ) i T ∗ = arg max 1 ≤ i ≤ N [ δ T ( i ) ] i_T^* = \arg\max\limits_{1\leq i \leq N}[\delta_T(i)] i T ∗ = arg 1 ≤ i ≤ N max [ δ T ( i )]
(4)最优路径回溯:对 t = T − 1 , T − 2 , … , 1 t = T-1,T-2,\dots,1 t = T − 1 , T − 2 , … , 1
i t ∗ = ψ t + 1 ( i t + 1 ∗ ) i_t^* = \psi_{t+1}(i_{t+1}^*) i t ∗ = ψ t + 1 ( i t + 1 ∗ )
举例如下
考虑盒子和球模型 λ = ( A , B , π ) \lambda=(A,B,\pi) λ = ( A , B , π ) ,状态集合 Q = { 1 , 2 , 3 } Q = \{1,2,3\} Q = { 1 , 2 , 3 } ,观测集合 V = { 红 , 白 } V = \{红,白\} V = { 红 , 白 } ,
A = [ 0.5 0.2 0.3 0.3 0.5 0.2 0.2 0.3 0.5 ] A = \left[ \begin{matrix} 0.5\ \ \ \ 0.2\ \ \ \ 0.3\\ 0.3\ \ \ \ 0.5\ \ \ \ 0.2\\ 0.2\ \ \ \ 0.3\ \ \ \ 0.5\end{matrix} \right] A = 0.5 0.2 0.3 0.3 0.5 0.2 0.2 0.3 0.5 , B = [ 0.5 0.5 0.4 0.6 0.7 0.3 ] B = \left[ \begin{matrix} 0.5\ \ \ \ 0.5\\ 0.4\ \ \ \ 0.6\\ 0.7\ \ \ \ 0.3\end{matrix} \right] B = 0.5 0.5 0.4 0.6 0.7 0.3 , π = ( 0.2 , 0.4 , 0.4 ) T \pi = (0.2,0.4,0.4)^T π = ( 0.2 , 0.4 , 0.4 ) T
已知观测序列 O = ( 红 , 白 , 红 ) O = (红,白,红) O = ( 红 , 白 , 红 ) ,求最优状态序列,即最优路径 I ∗ = ( i 1 ∗ , i 2 ∗ , i 3 ∗ ) I^* = (i_1^*,i_2^*,i_3^*) I ∗ = ( i 1 ∗ , i 2 ∗ , i 3 ∗ )
(1)初始化。在 t = 1 t = 1 t = 1 时,对每一个状态 i , i = 1 , 2 , 3 i,\ i=1,2,3 i , i = 1 , 2 , 3 ,求状态 i i i 观测 o 1 o_1 o 1 为红的概率,记此概率为 δ 1 ( i ) \delta_1(i) δ 1 ( i ) ,则
δ 1 ( i ) = π i b i ( o 1 ) = π i b i ( 红 ) , i = 1 , 2 , 3 \delta_1(i) = \pi_ib_i(o_1)=\pi_ib_i(红),\ \ \ i=1,2,3 δ 1 ( i ) = π i b i ( o 1 ) = π i b i ( 红 ) , i = 1 , 2 , 3
代入实际数据
δ 1 ( 1 ) = 0.2 × 0.5 = 0.1 \delta_1(1) = 0.2\times0.5=0.1 δ 1 ( 1 ) = 0.2 × 0.5 = 0.1 δ 1 ( 2 ) = 0.4 × 0.4 = 0.16 \delta_1(2) = 0.4\times0.4=0.16 δ 1 ( 2 ) = 0.4 × 0.4 = 0.16 δ 1 ( 3 ) = 0.4 × 0.7 = 0.28 \delta_1(3) = 0.4\times0.7=0.28 δ 1 ( 3 ) = 0.4 × 0.7 = 0.28
记 ψ 1 ( i ) = 0 , i = 1 , 2 , 3 \psi_1(i)=0,\ i=1,2,3 ψ 1 ( i ) = 0 , i = 1 , 2 , 3
(2)在 t = 2 t = 2 t = 2 时,对每个状态 i , i = 1 , 2 , 3 i,\ i=1,2,3 i , i = 1 , 2 , 3 ,求在 t = 1 t = 1 t = 1 时状态为 j j j 观测为红并在 t = 2 t = 2 t = 2 时状态为 i i i 观测 o 2 o_2 o 2 为白的路径的最大概率,记此最大概率为 δ 2 ( i ) \delta_2(i) δ 2 ( i ) ,则
δ 2 ( i ) = max 1 ≤ j ≤ 3 [ δ 1 ( j ) α j i ] b i ( o 2 ) \delta_2(i) = \max\limits_{1\leq j \leq 3}[\delta_1(j)\alpha_{ji}]b_i(o_2) δ 2 ( i ) = 1 ≤ j ≤ 3 max [ δ 1 ( j ) α ji ] b i ( o 2 )
同时,对每个状态 i , i = 1 , 2 , 3 i,\ i=1,2,3 i , i = 1 , 2 , 3 ,记录概率最大路径的前一个状态 j j j
ψ 2 ( i ) = arg max 1 ≤ j ≤ 3 [ δ 1 ( j ) α j i ] , i = , 1 , 2 , 3 \psi_2(i)=\arg\max\limits_{1\leq j \leq 3}[\delta_1(j)\alpha_{ji}],\ \ \ i=,1,2,3 ψ 2 ( i ) = arg 1 ≤ j ≤ 3 max [ δ 1 ( j ) α ji ] , i = , 1 , 2 , 3
计算: δ 2 ( 1 ) = max 1 ≤ j ≤ 3 [ δ 1 ( j ) a j 1 ] b 1 ( o 2 ) \delta_2(1)=\max\limits_{1\leq j\leq 3}[\delta_1(j)a_{j1}]b_1(o_2) δ 2 ( 1 ) = 1 ≤ j ≤ 3 max [ δ 1 ( j ) a j 1 ] b 1 ( o 2 )
= max j ( 0.1 × 0.5 , 0.16 × 0.3 , 0.28 × 0.2 ) × 0.5 = 0.028 =\max\limits_j(0.1\times0.5, 0.16\times0.3, 0.28\times0.2)\times 0.5=0.028 = j max ( 0.1 × 0.5 , 0.16 × 0.3 , 0.28 × 0.2 ) × 0.5 = 0.028
ψ 2 ( 1 ) = 3 \psi_2(1)=3 ψ 2 ( 1 ) = 3
δ 2 ( 2 ) = 0.0504 \delta_2(2)=0.0504 δ 2 ( 2 ) = 0.0504 ψ 2 ( 2 ) = 3 \psi_2(2)=3 ψ 2 ( 2 ) = 3
δ 2 ( 3 ) = 0.042 \delta_2(3)=0.042 δ 2 ( 3 ) = 0.042 ψ 2 ( 3 ) = 3 \psi_2(3)=3 ψ 2 ( 3 ) = 3
同样,在 t = 3 t = 3 t = 3 时,
δ 3 ( i ) = max 1 ≤ j ≤ 3 [ δ 2 ( j ) α j i ] b i ( o 3 ) \delta_3(i)=\max\limits_{1\leq j \leq 3}[\delta_2(j)\alpha_{ji}]b_i(o_3) δ 3 ( i ) = 1 ≤ j ≤ 3 max [ δ 2 ( j ) α ji ] b i ( o 3 ) ψ 3 ( i ) = arg max 1 ≤ j ≤ 3 [ δ 2 ( j ) a j i ] \psi_3(i) = \arg\max\limits_{1\leq j \leq 3}[\delta_2(j)a_{ji}] ψ 3 ( i ) = arg 1 ≤ j ≤ 3 max [ δ 2 ( j ) a ji ]
δ 3 ( 1 ) = 0.00756 \delta_3(1) = 0.00756 δ 3 ( 1 ) = 0.00756 ψ 3 ( 1 ) = 2 \psi_3(1) = 2 ψ 3 ( 1 ) = 2
δ 3 ( 2 ) = 0.01008 \delta_3(2) = 0.01008 δ 3 ( 2 ) = 0.01008 ψ 3 ( 2 ) = 2 \psi_3(2) = 2 ψ 3 ( 2 ) = 2
δ 3 ( 3 ) = 0.0147 \delta_3(3) = 0.0147 δ 3 ( 3 ) = 0.0147 ψ 3 ( 3 ) = 3 \psi_3(3) = 3 ψ 3 ( 3 ) = 3
(3)以 P ∗ P^* P ∗ 表示最优路径的概率,则
P ∗ = max 1 ≤ i ≤ 3 δ 3 ( i ) = 0.0147 P^* = \max\limits_{1\leq i \leq 3}\delta_3(i)=0.0147 P ∗ = 1 ≤ i ≤ 3 max δ 3 ( i ) = 0.0147
最优路径的终点是 i 3 ∗ i_3^* i 3 ∗
i 3 ∗ = arg max i [ δ 3 ( i ) ] = 3 i_3^* = \arg\max\limits_i[\delta_3(i)]=3 i 3 ∗ = arg i max [ δ 3 ( i )] = 3
(4)由最优路径的终点 i 3 ∗ i_3^* i 3 ∗ ,逆向找到 i 2 ∗ , i 1 ∗ i_2^*,\ i_1^* i 2 ∗ , i 1 ∗
在 t = 2 t = 2 t = 2 时, i 2 ∗ = ψ 3 ( i 3 ∗ ) = ψ 3 ( 3 ) = 3 i_2^* = \psi_3(i_3^*)=\psi_3(3)=3 i 2 ∗ = ψ 3 ( i 3 ∗ ) = ψ 3 ( 3 ) = 3
在 t = 1 t = 1 t = 1 时, i 1 ∗ = ψ 2 ( i 2 ∗ ) = ψ 2 ( 3 ) = 3 i_1^* = \psi_2(i_2^*)=\psi_2(3)=3 i 1 ∗ = ψ 2 ( i 2 ∗ ) = ψ 2 ( 3 ) = 3
于是求得最优路径,即最优状态序列 I ∗ = ( i 1 ∗ , i 2 ∗ , i 3 ∗ ) = ( 3 , 3 , 3 ) I^* = (i_1^*,i_2^*,i_3^*)=(3,3,3) I ∗ = ( i 1 ∗ , i 2 ∗ , i 3 ∗ ) = ( 3 , 3 , 3 )
3、给定足够量的观测数据,如何估计隐马尔可夫模型的参数
使用鲍姆-韦尔奇(Baum-Welch)算法,也就是EM算法。在大多数现实应用中,人工指定模型参数已变得越来越不可行,如何根据训练样本学得最优的模型参数,正好就是本问题。
在利用隐马尔可夫模型解决实际问题中,需要先知道每个状态 s t s_t s t 产生相应输出符号 o t o_t o t 的概率 P ( o t ∣ s t ) P(o_t|s_t) P ( o t ∣ s t ) ,也称为生成概率;和转移概率,即从前一个状态 s t − 1 s_{t-1} s t − 1 进入当前状态 s t s_t s t 的概率 P ( s t ∣ s t − 1 ) P(s_t|s_{t-1}) P ( s t ∣ s t − 1 ) 。这些概率被称为马尔可夫模型的参数,而计算或者估计这些参数的过程称为模型的训练。
我们从条件概率的定义出发,知道:
P ( o t ∣ s t ) = P ( o t , s t ) P ( s t ) P(o_t|s_t) = \frac{P(o_t,s_t)}{P(s_t)} P ( o t ∣ s t ) = P ( s t ) P ( o t , s t )
P ( s t ∣ s t − 1 ) = P ( s t − 1 , s t ) P ( s t − 1 ) P(s_t|s_{t-1}) = \frac{P(s_{t-1},s_t)}{P(s_{t-1})} P ( s t ∣ s t − 1 ) = P ( s t − 1 ) P ( s t − 1 , s t )
对于上面第一个概率公式(生成概率),状态输出概率,如果有足够多人工标记的数据,知道经过状态 s t s_t s t 有多少次 # ( s t ) \#(s_t) # ( s t ) ,每经过这个状态时,分别产生的输出 o t o_t o t 是什么,而且分别有多少次 # ( o t , s t ) \#(o_t,s_t) # ( o t , s t ) 就可以算出(比如语音识别中,符号即每个词对应声波;中英翻译中,中文字为状态,英文字为输出符号)。上述第二个概率公式(转移概率),与前文提到的训练统计语言模型的条件概率完全相同,因此可以依照统计语言模型的训练方法,即数一下出现前一个词后出现这个词的次数(同上文例子,出现“联想”这个词后,出现“公司”的概率是多少,即数一下“联想”的次数,数一下“联想公司”的次数)
P ( o t ∣ s t ) ≈ # ( o t , s t ) # ( s t ) P(o_t|s_t) \approx \frac{\#(o_t,s_t)}{\#(s_t)} P ( o t ∣ s t ) ≈ # ( s t ) # ( o t , s t )
P ( w t ∣ w i − 1 ) ≈ # ( w i − 1 , w i ) # ( w i − 1 ) P(w_t|w_{i-1}) \approx \frac{\#(w_{i-1},w_i)}{\#(w_{i-1})} P ( w t ∣ w i − 1 ) ≈ # ( w i − 1 ) # ( w i − 1 , w i )
然而,像语音识别等这种应用大量人工标注不现实,所以这个方法只适用于一部分应用。因此,训练隐马尔可夫模型更实用的方法是仅仅通过大量观测到的信号 o 1 , o 2 , o 3 , ⋯ o_1,o_2,o_3,\cdots o 1 , o 2 , o 3 , ⋯ 就能推算模型参数的 P ( s t ∣ s t − 1 ) P(s_t|s_{t-1}) P ( s t ∣ s t − 1 ) 和 P ( o t ∣ s t ) P(o_t|s_t) P ( o t ∣ s t ) 的方法,主要是使用 鲍姆-韦尔奇算法
两个不同的隐马尔可夫模型可以产生同样的输出信号,因此,仅仅通过观察到的输出信号来倒推它的隐马尔可夫模型可能会得到多个合适的模型,但总会有一个模型 M θ 1 M_{\theta_1} M θ 1 比其他的 M θ 2 , M θ 3 , … M_{\theta_2}, M_{\theta_3},\dots M θ 2 , M θ 3 , … 更有可能产生观测到的输出,其中 θ \theta θ 是隐马尔科夫模型的参数(可理解为最大似然)。鲍姆-韦尔奇算法就是来寻找这个最可能的模型 M θ ^ M_{\hat{\theta}} M θ ^
鲍姆-韦尔奇算法思想:
鲍姆-韦尔奇算法使用的就是EM算法原理。首先找到一组能够产生输出序列 O O O 的模型参数(显然它们是一定存在的,因为转移概率 P P P 和输出概率 Q Q Q 为均匀分布时,模型可以产生任何输出,当然包括我们观测到的输出 O O O )现在,有了这样一个初始模型 M θ 0 M_{\theta_0} M θ 0 ,根据上文提到的P ( o t ∣ s t ) = P ( o t , s t ) P ( s t ) P(o_t|s_t) = \frac{P(o_t,s_t)}{P(s_t)} P ( o t ∣ s t ) = P ( s t ) P ( o t , s t ) 和P ( s t ∣ s t − 1 ) = P ( s t − 1 , s t ) P ( s t − 1 ) P(s_t|s_{t-1}) = \frac{P(s_{t-1},s_t)}{P(s_{t-1})} P ( s t ∣ s t − 1 ) = P ( s t − 1 ) P ( s t − 1 , s t ) 公式计算出一组新的模型参数 θ 1 \theta_1 θ 1 ,为一次迭代,可以证明 P ( O ∣ M θ 1 ) > P ( O ∣ M θ 0 ) P(O|M_{\theta_1})>P(O|M_{\theta_0}) P ( O ∣ M θ 1 ) > P ( O ∣ M θ 0 ) 。经过不断迭代 t t t 轮,直到模型的质量不再有显著提高,得到的 θ t \theta_t θ t 即我们所求参数。
Source