搜索
自然语言处理研究中常用的机器学习技术常宝宝北京大学计算语言学研究所chbb@pku.edu.cn概要最大熵模型条件马尔可夫模型条件随机场模型统计建模问题某随机现象，概率分布未知。但拥有该随机现象的一组样本数据(训练数据)，或者拥有该数据的部分知识。人们可以基于样本数据或部分知识对随机现象所服从的概率分布进行推断，并求解这个概率分布。----------------------------------------------------------利用所得到概率分布对随机现象的未来行为进行预测。----------------------------------------------------------最大熵方法就是这样一种统计建模技术例子满足条件的概率分布有无数多个例子在众多的概率分布中如何做出选择?不增加任何未知的约束信息，在符合已知约束条件的前提下，尽可能选择均匀分布。最大熵原则(PrincipleofMaximumEntropy)熵描述了随机变量的不确定性，熵值越大表明该随机变量的不确定性越大，该随机变量也就越接近均匀分布。因此，在只掌握关于未知分布的部分知识时，应该选取符合这些知识但熵值最大的概率分布。这就是最大熵原则。按照最大熵原则进行统计建模，是人们可以作出的唯一不偏不倚的选择，任何其它的选择都意味着人们增加了额外的约束和假设，这些约束和假设根据人们掌握的信息无法作出。最大熵原则(PrincipleofMaximumEntropy)最大熵原则是由E.T.Jaynes在1957年提出的，在许多领域都有着广泛的应用，在自然语言处理研究中也是如此。基于最大熵原则构建的统计模型称为最大熵模型，利用最大熵原则进行统计建模的方法称为最大熵方法。按照最大熵原则，对于前面的例子进行建模，即为求解下面的问题：最大熵原则(PrincipleofMaximumEntropy)最大熵方法的一般陈述：对于很多复杂的问题，利用最大熵原则进行建模不存在解析的方法。最大熵方法中的特征表示最大熵方法通过特征表示样本数据中的已知知识。特征在训练样本中出现的期望频率最大熵方法中约束表达特征f(x,y)的模型期望可表示为：最大熵方法认为，为了使模型分布符合样本中的统计证据，特征的模型期望应该与特征的观察期望值一致，即：若共有k个特征，则最大熵方法中约束表达通过约束使特征的模型期望与观察期望保持一致，最大熵方法保证所得到模型分布符合样本数据中的已知统计证据。满足所有约束条件的分布通常不止一个。若用P表示所有满足特征约束条件的分布，则：求解最大熵模型就成为一个约束最优化问题。求解最大熵分布求解下列约束最优化问题运用拉格朗日乘数法，构建拉格朗日函数:其中L=(l1,l2,...,lk)求解最大熵分布对拉格朗日函数针对p求微分，并令其为0，有：上述分布即为符合最大熵原则的概率分布形式。最大熵模型是一种对数线性模型，其中指数部分表述为特征的一种线性加权组合，特征fi对分布的影响通过拉格朗日乘数li来体现。条件最大熵分布在计算语言学领域，人们需要的常常是条件模型，需要估算的是p(y|x)，此时优化的目标是分布的条件熵由于p(x,y)未知，条件熵可做如下近似条件最大熵分布特征的样本期望特征的模型期望(近似计算)仍是一个约束最优化问题条件最大熵分布条件最大熵分布的描述求解该约束最优化问题，得到条件最大熵分布的一般形式最大熵方法的优点利用最大熵方法进行统计建模时，人们只需要根据具体问题的要求，集中精力选择特征，无需花费精力考虑如何使用这些特征，并且选择特征可以很灵活，无需考虑特征之间是否独立，特征的类型和特征的数量都可以随时进行调整。利用最大熵建模，参数平滑甚至可以通过特征选择的方式加以考虑，每个特征对概率分布的贡献由参数li决定最大熵方法的模型训练可以采用数值最优化算法，两种考虑方式以样本数据的熵值最大化作为优化目标以样本数据的概率值最大化作为优化目标进行最大似然估计二者训练结果是一致的，即有：目前提出的用于训练最大熵模型的算法有(迭代)GIS算法(GeneralizedIterativeScaling)IIS算法(ImprovedIterativeScaling)[收敛速度快]梯度下降法、拟牛顿法等最优化算法也可用于训练最大熵模型，例如L-BFGS算法。特征选择对于样本数据，可以设计出成千上万的特征，并非所有特征的样本期望值都是可靠的，很多特征的样本期望值带有偶然性，与特征的真实期望并不一致，引入这样的特征无益于统计建模工作。需要特征选择策略设置一个截止频率某特征只有在训练样本中的出现频率大于截止频率，才会被包括在最终的特征集合中。采用特征选择算法从所有特征集合F中选择对建模有益的特征S评价准则：好的特征集能引起样本数据的概率值增大词类标注中最大熵方法的应用词性标注是一个分类问题，序列分类当前标记词的环境描述特征举例概要最大熵模型条件马尔可夫模型条件随机场模型图模型(GraphicalModel)条件马尔可夫模型、条件随机场模型是图模型图模型常用来为若干随机变量的联合分布进行统计建模，用以将联合分布进行适当的分解依据链式规则，N个随机变量的联合分布可做如下形式的分解若已知随机变量之间的依赖关系，上述分解式中条件分布可略去和变量xi独立的变量。图模型(GraphicalModel)图模型用图结构描述随机变量之间的依赖关系结点---随机变量边---随机变量之间的依赖关系图结构可以是有向图和无向图，分别针对有向图模型无向图模型有向图模型可以用一个无环有向图G=(X,E)来表示(1)X={X1,X2,...,XN}是结点集，代表随机变量(2)E={(Xi,Xj)}代表有向边的集合，Xi是父结点，Xj是子结点，代表Xj依赖Xi有向图模型对应下面的分解形式有向图模型举例对应联合分布的分解式有向图模型举例HMM模型是有向图模型对应的分解式无向图模型无向图模型对应着另外一种将联合分布进行分解的方式。无向图模型可表示为一个无向图G=(X,E)，其中：(1)X={X1,X2,...,XN}代表结点集，对应着随机变量。(2)E={(Xi,Xj):i≠j}代表无向边的集合。对应随机变量间的依赖关系。在无向图中，任何一个全连通的子图称作一个团(clique)。不能被其它团所包含的团称为最大团(maximalclique)。无向图模型举例上图中的团上图中的最大团无向图模型团上的势函数(potentialfunction)无向图模型以团为单位将联合概率分布分解为势函数的乘积，无向图模型描述了如下形式的概率分布无向图模型无向图模型之所以需要归一化，是因为势函数并非是概率分布，因此它们的乘积不是合法的概率分布，归一化因子计算方式通常采用指数势函数无向图模型可表示为有向图模型与无向图模型的对比共同之处将复杂的联合分布分解为多个因子的乘积不同之处有向图模型因子是概率分布、无需全局归一无向图模型因子是势函数，需要全局归一优缺点无向图模型中势函数设计不受概率分布约束，设计灵活，但全局归一代价高有向图模型无需全局归一、训练相对高效判别模型和生成模型计算语言学常常处理序列标注问题，为给定的观察序列标注标记序列令o和s分别代表观察序列和标记序列为此需要基于训练数据，对o和s进行统计建模判别模型和生成模型对o和s进行统计建模，通常有两种方式(1)生成模型着眼于构建o和s的联合分布p(s,o)(2)判别模型着眼于构建o和s的条件分布p(s|o)判别模型与序列标记问题有较好的对应性在利用生成模型进行序列标注时，理论上需要判别模型和生成模型对比训练时，二者优化准则不同生成模型优化训练数据的联合分布判别模型优化训练数据的条件分布对于观察序列的处理不同生成模型中，观察序列作为模型的一部分判别模型中，观察序列只作为条件，因此可以针对观察序列设计灵活的特征训练复杂度不同判别模型训练复杂度较高是否支持无指导训练生成模型支持无指导训练判别模型和生成模型HMM模型是生成模型训练时优化的目标是p(s,o)可以采用Baum-Welch算法训练参数过强的独立性假设限制了模型的改进，无法使用关于观察值的多重特征以及不相互独立的特征模型训练使用联合分布、标注使用条件分布，对性能造成负面影响条件马尔可夫模型(ConditionalMarkovModel)针对HMM的缺陷，提出条件马尔可夫模型条件马尔可夫模型是判别模型、有向图模型条件马尔可夫模型的图结构条件马尔可夫模型的分解式条件马尔可夫模型条件马尔可夫模型中因子是条件分布，无需进行全局归一化观察序列在因子中作为条件出现，使得建模特征无需考虑特征间的独立性对标记转移分布，通常采用最大熵的建模原则条件马尔可夫模型最大熵马尔可夫模型(MEMM)是一种简化了的条件马尔可夫模型(已被应用于NLP)条件马尔可夫模型的训练采用最大似然估计法仍属数值最优化问题，可采用梯度法等相关算法条件马尔可夫模型缺陷对于条件马尔可夫模型，解码仍是Viterbi算法条件马尔可夫模型的缺陷是标记偏执问题(LabelBiasproblem)标记偏执的例子条件马尔可夫模型标记转移分布熵值低的情况，都会有标记偏执问题。标记偏执的原因在于局部归一标记偏执问题给条件马尔可夫模型的应用性能造成很大负面影响解决的办法是取消局部归一，代之以全局归一概要最大熵模型条件马尔可夫模型条件随机场模型条件随机场模型(ConditionalRandomFields)条件随机场模型2001年由Lafferty提出，解决了标记偏执问题，目前广泛应用于自然语言处理的各种任务条件随机场模型是判别模型(特征设计灵活)无向图模型(无需局部归一，代之全局归一)条件随机场模型链式条件随机场模型的图结构条件随机场模型的分解式链式条件随机场模型图结构中的团条件随机场模型基于最大熵原则进行建模，定义样本条件熵以团为单位定义特征约束特征的样本期望与模型期望相同另有条件随机场模型运用拉格朗日乘数法，求解出条件随机场的分布形式如下：对数线性模型条件随机场模型训练条件随机场模型原理与其它前述模型类似，可以采用GIS、IIS算法以及其他数值优化算法基于条件随机场模型进行标注采用Viterbi算法条件随机场模型理论上较为完善的序列标记模型兼具判别模型和无向图模型的优点特征设计灵活、无需考虑特征独立性没有标记偏执问题条件随机场模型训练代价大、复杂度高除链式图结构外，还可以设计其他图结构，如针对网页的链接结构有开源代码，有兴趣可了解