条件随机场CRF

条件随机场CRF北京10月机器学习班邹博2014年12月14日2/87思考：给定文本标注词性他估算当前的赤字总额在9月份仅仅降低到18亿。NN、NNS、NNP、NNPS、PRP、DT、JJ分别代表普通名词单数形式、普通名词复数形式、专有名词单数形式、专有名词复数形式、代词、限定词、形容词3/87复习：MarkovBlanket一个结点的MarkovBlanket是一个集合，在这个集合中的结点都给定的条件下，该结点条件独立于其他所有结点。即：一个结点的MarkovBlanket是它的parents,children以及spouses(孩子的其他parent)4/87MarkovBlanket补充知识：SerumCalcium(血清钙浓度)高于2.75mmo1/L即为高钙血症。许多恶性肿瘤可并发高钙血症。以乳腺癌、骨肿瘤、肺癌、胃癌、卵巢癌、多发性骨髓瘤、急性淋巴细胞白血病等较为多见，其中乳腺癌约1/3可发生高钙血症。毒素5/87图像模型考察X8的马尔科夫毯(Markovblanket)6/87无向图模型有向图模型，又称作贝叶斯网络(DirectedGraphicalModels,DGM,BayesianNetwork)在有些情况下，强制对某些结点之间的边增加方向是不合适的。使用没有方向的无向边，形成了无向图模型(UndirectedGraphicalModel,UGM),又被称为马尔科夫随机场或者马尔科夫网络(MarkovRandomField,MRForMarkovnetwork)7/87条件随机场设X=(X1,X2…Xn)和Y=(Y1,Y2…Ym)都是联合随机变量，若随机变量Y构成一个无向图G=(V,E)表示的马尔科夫随机场(MRF)，则条件概率分布P(Y|X)称为条件随机场(ConditionalRandomField,CRF)注：大量文献将MRF和CRF混用，包括经典著作。后面将考察为何会有该混用。8/87DGM转换成UGM9/87DGM转换成UGM10/87条件独立的破坏靠考察是否有，则计算U的祖先图(ancestralgraph)：11/87MRF的性质成对马尔科夫性parewiseMarkovproperty局部马尔科夫性localMarkovproperty全局马尔科夫性globalMarkovproperty表述说明：随机变量Y=(Y1,Y2…Ym)构成无向图G=(V,E)，结点v对应的随机变量是Yv。12/87考察结点间的独立性13/87成对马尔科夫性设u和v是无向图G中任意两个没有边直接连接的结点，G中其他结点的集合记做O；则在给定随机变量Yo的条件下，随机变量Yu和Yv条件独立。即：P(Yu,Yv|Yo)=P(Yu|Yo)*P(Yv|Yo)14/87局部马尔科夫性设v是无向图G中任意一个结点，W是与v有边相连的所有结点，G中其他结点记做O；则在给定随机变量Yw的条件下，随机变量Yv和Yo条件独立。即：P(Yv,Yo|Yw)=P(Yv|Yw)*P(Yo|Yw)15/87全局马尔科夫性设结点集合A，B是在无向图G中被结点集合C分开的任意结点集合，则在给定随机变量YC的条件下，随机变量YA和YB条件独立。即：P(YA,YB|YC)=P(YA|YC)*P(YB|YC)16/87三个性质的等价性根据全局马尔科夫性，能够得到局部马尔科夫性；根据局部马尔科夫性，能够得到成对马尔科夫性；根据成对马尔科夫性，能够得到全局马尔科夫性；可以反向思考：满足这三个性质(或其一)的无向图，称为概率无向图模型。17/87复习：隐马尔科夫模型18/87HMM的确定HMM由初始概率分布π、状态转移概率分布A以及观测概率分布B确定。,,BA,,BA19/87HMM的参数Q是所有可能的状态的集合N是可能的状态数V是所有可能的观测的集合M是可能的观测数NqqqQ,,21MvvvV,,2120/87HMM的参数I是长度为T的状态序列，O是对应的观测序列A是状态转移概率矩阵其中aij是在时刻t处于状态qi的条件下时刻t+1转移到状态qj的概率。TiiiI,,21ToooO,,21NNijaAitjtijqiqiPa1TiiiI,,2121/87HMM的参数B是观测概率矩阵其中，bik是在时刻t处于状态qi的条件下生成观测vk的概率。π是初始状态概率向量：其中，πi是时刻t=1处于状态qi的概率。MNikbBitktikqivoPbiiiqiP122/87HMM的参数总结HMM由初始概率分布π、状态转移概率分布A以及观测概率分布B确定。π和A决定状态序列，B决定观测序列。因此，HMM可以用三元符号表示，称为HMM的三要素：,,BA,,BA23/87HMM的两个基本性质齐次假设：观测独立性假设：1112211,,,,tttttttiiPoioioiiPttTTTTtioPoioioioP1111,,,,24/87HMM的3个基本问题概率计算问题给定模型和观测序列，计算模型λ下观测序列O出现的概率P(O|λ)学习问题已知观测序列，估计模型的参数，使得在该模型下观测序列P(O|λ)最大预测问题即解码问题：已知模型和观测序列，求对给定观测序列条件概率P(I|O)最大的状态序列I,,BAToooO,,21,,BAToooO,,21,,BAToooO,,2125/87概率计算问题直接算法暴力算法前向算法后向算法这二者是理解HMM的算法重点26/87直接计算法按照概率公式，列举所有可能的长度为T的状态序列，求各个状态序列I与观测序列的联合概率P(O,I|λ)，然后对所有可能的状态序列求和，从而得到P(O|λ)ToooO,,21TiiiI,,2127/87直接计算法状态序列的概率是：对固定的状态序列I，观测序列O的概率是：TiiiI,,21TToioioibbbIOP2211,TTiiiiiiiaaaIP13221128/87直接计算法O和I同时出现的联合概率是：对所有可能的状态序列I求和，得到观测序列O的概率P(O|λ)TTTTTiiioiiioiiioiiIIbababIPIOPIOPOP,,2112221111,,TTTToiiioiiioiibababIPIOPIOP12221111,,29/87直接计算法对于最终式分析：加和符号中有2T个因子，I的遍历个数为NT，因此，时间复杂度为O(TNT)，过高。TTTTTiiioiiioiiioiiIIbababIPIOPIOPOP,,2112221111,,30/87前向算法定义：给定λ，定义到时刻t部分观测序列为o1,o2…ot且状态为qi的概率为前向概率，记做：可以递推的求得前向概率αt(i)及观测序列概率P(O|λ)itttqioooPi,,,2131/87前向算法初值：递推：对于t=1,2…T-1最终：111tioNjjittbajiNiTiOP111ioibi32/87后向算法定义：给定λ，定义到时刻t状态为qi的前提下，从t+1到T的部分观测序列为ot+1,ot+2…oT的概率为后向概率，记做：可以递推的求得后向概率βt(i)及观测序列概率P(O|λ),,,21itTtttqioooPi33/87后向算法初值：递推：对于t=T-1,T-2…,1最终：Njtjoijtjbait111NiioiibOP1111iT34/87后向算法的说明为了计算在时刻t状态为qi条件下时刻t+1之后的观测序列为ot+1,ot+2…oT的后向概率βt(i)，只需要考虑在时刻t+1所有可能的N个状态qj的转移概率(aij项)，以及在此状态下的观测ot+1的观测概率(bjot+1)项，然后考虑状态qj之后的观测序列的后向概率βt+1(j)35/87前向后向概率的关系根据定义，证明下列等式NittiiOP1iiOqiPttit,36/87单个状态的概率求给定模型λ和观测O，在时刻t处于状态qi的概率。记：,OqiPiitt37/87单个状态的概率根据前向后向概率的定义，iiOqiPttit,OPOqiPOqiPiititt,,NitttttttiiiiOPiii138/87γ的意义在每个时刻t选择在该时刻最有可能出现的状态it*，从而得到一个状态序列I*={i1*,i2*…iT*}，将它作为预测的结果。给定模型和观测序列，时刻t处于状态qi的概率为：NitttttttiiiiOPiii139/87两个状态的联合概率求给定模型λ和观测O，在时刻t处于状态qi并且时刻t+1处于状态qj的概率。,,,1OqiqiPjijtitt40/87两个状态的联合概率根据前向后向概率的定义，NiNjjtitjtitjtitjtittOqiqiPOqiqiPOPOqiqiPOqiqiPji111111,,,,,,,,,jbaiOqiqiPtjoijtjtitt111,,41/87期望在观测O下状态i出现的期望：在观测O下状态i转移到状态j的期望：Ttti111,Tttji42/87学习算法若训练数据包括观测序列和状态序列，则HMM的学习非常简单，是监督性学习；若训练数据只有观测序列，则HMM的学习需要使用EM算法，是非监督学习。43/87再次分析二项分布的参数估计极大似然估计简单的例子10次抛硬币的结果是：正正反正正正反反正正假设p是每次抛硬币结果为正的概率。则：得到这样的实验结果的概率是：371111ppppppppppppP44/87极大似然估计MLE目标函数：最优解是：p=0.7即：使用样本的均值可以作为全体的均值估计一般形式：37101maxmaxppPpxxppxpL是实验结果的分布模型是估计的概率分布xpxp45/87直接推广上述结论假设已给定训练数据包含S个长度相同的观测序列和对应的状态序列{(O1,I1),(O2,I2)…(Os,Is)}，那么，可以直接利用极大似然估计的上述结论，给出HMM的参数估计。46/87监督学习方法转移概率aij的估计：设样本中时刻t处于状态i时刻t+1转移到状态j的频数为Aij，则观测概率bik的估计：设样本中状态i并观测为k的频数为Bik，则初始状态概率πi的估计为S个样本中初始状态为qi的概率。NjijijijAAa1ˆMkikikikBBb1ˆ47/87Baum-Welch算法若训练数据只有观测序列，则HMM的学习需要使用EM算法，是非监督学习。48/87Baum-Welch算法所有观测数据写成O=(o1,o2…oT)，所有隐数据写成I=(i1,i2…iT)，完全数据是(O,I)=(o1,o2…oT,i1,i2…iT)，完全数据的对数似然函数是lnP(O,I|λ)假设是HMM参数的当前