PPT《分类》

计算量相对来说不是很大;

可以处理连续和离散字段;

决策树可以清晰的显示哪些字段比较重要 不足之处 对连续性的字段比较难预测当类别太多时,错误可能会增加的比较快一般的算法分类的时候,只是根据一个属性来分类.不是全局最优. 举例:利用决策树进行文本分类 最大熵模型 熵定量的描述事物的不确定性设随机变量 ,它有A1,A2,…,An共n个可能的结局,每个结局出现的机率分别为p1,p2 ,...,pn,则 的不确定程度,即信息熵为: 熵越大,越不确定熵等于0,变量是确定的 最大熵思想 最大熵思想由来已久,Occam在他著名的Occam剃刀理论中即体现了这种思想,对最大熵理论的系统论述出现在上世纪50年代中期,由E.T. Jaynes提出,其原理的基本思想是:我们从全部相容的分布预测中挑选这样的预测,它是在某些约束条件下(通常是给定的某些随机变量的分布)使信息熵达到极大值.这是因为信息熵取得极大值时对应的一组概率分布出现的概率占绝对优势. 在自然语言中的应用 S.Pietra、V.Pietra等人提出了一种基于最大熵原理的单词聚类方法,首次将最大熵理论应用于自然语言处理.A.L.Berger、S.Pietra、V.Pietra等人比较详细地介绍了最大熵的理论框架,并介绍了其在基于统计的机器翻译领域的一些应用.S.Abney在统计属性--值文法(Attribute-value Grammars)中使用最大熵进行参数估计.李涓子、黄昌宁改进了最大熵的特征选择策略,并将其应用于汉语的词义消歧,取得了较好的效果A.Borthwick研究了基于最大熵的名实体(Named Entity)的识别 最大熵模型 已知训练样本集(x1,y1),(x2,y2),…,(xN,yN),其中x为输入,y为输出 指x出现的情况下,y的经验概率,也就是y在样本集中的概率.指x出现的情况下,y的实际概率.随机事件的不确定性可以用条件熵来衡量:特征指x与y之间存在的某种特定关系,可以用一个输出为0或1的特征函数表示. 最大熵模型 特征的经验概率为所有满足特征要求的(x,y)的验概率之和,即:特征的期望概率,也就是特征在我们所学习的随机事件中的真实分布为: 最大熵模型 选定的特征的重要性可通过下式体现:上 式表示,特征f的经验概率与期望概率一致,当样本足够多时,可信度高的特征的经验概率与期望概率是一致的 约束集 根据随机事件的情况,约束等式可以有多组,约束等式的集合叫约束集,可表示为 最大熵模型 最大熵模型,是满足约束集条件的所有模型中熵最大的模型,即: 其中p为满足约束集C条件的某一统计模型.因为约束集中的每一个特征的分布是最大似然估计,所以约束集中元素越多,统计模型从训练样本中学得的越多,其做出的预测也越依赖于样本集.选择特征较多时,满足约束集要求的统计模型个数较少,当把样本中的所有(x,y)都作为特征时,模型唯一,为用极大似然估计求p(y|x)所建立的模型. 最大熵模型求解 最大熵模型求解问题,实质是一个约束条件下求极值的问题.此类问题通常用拉格朗日乘子法确定.其中: 求导后变换得 其中最大值可通过求 没有解析解,Danroch 和Rateliff于1972年提出了一个称为GIS(Generalized Iterative Scaling Algorithm)算法[133].D.Pietra等改进了原有的最大熵模型求解算法,降低了求解算法的约束条件,提出了IIS(Improved Iterative Scaling Algorithm)算法,增加了算法的适用性,IIS算法是目前最大熵参数求解中的常用算法. IIS算法 IIS算法如下: 输入:约束集, x,y的经验概率分布 输出: