常用的用于分类的机器学习工具介绍

《常用的用于分类的机器学习工具介绍》由会员分享，可在线阅读，更多相关《常用的用于分类的机器学习工具介绍（64页珍藏版）》请在金锄头文库上搜索。

1、常用的用于分类的机器学习工 具介绍常用的机器学习分类模型 决策树模型、贝叶斯模型、HMM模型、最 大熵模型、支持向量机、条件随机场 我们今天简单介绍一下ME和CRFOutline 最大熵模型 Features Maximum Entropy Principle Maximum Likelihood Parameters Estimation Application 条件随机场介绍参考文献 Berger et al, A Maximum Entropy to Natural Language Processing Bergers ME tutorials: http:/www.cs.cmu.ed

2、u/berger/maxent.html Kleins ACL 2003 tutorials Adwait Ratnaparkhi的博士论文：ftp:/ftp.cis.upenn.edu/pub/ircs/tr/98-15/98-15.ps.gz分类问题 很多问题都可以表述为分类问题： (x1,y1),(x2,y2),(xn,yn) 这里xi是数据，yi是类别。 如在机器翻译的译词选择中，x表示原文单词及其 语境，y表示译文，则 （漂亮女孩，pretty)，（漂亮夫人，beautiful)，（漂亮男人，handsome)，. 又比如在文本分类中，xi是含有某个文本，yi就是 该文本的类别，如政

3、治、经济、科技等。随机过程 又比如在词性标注中，x表示待标注词的前 后文，y表示该词的标注，则（前一个词为modal, 这个词为verb）,（前一个词为det, 这个词为adj）, 把（x,y)作为一个随机过程，x的集合构成X ，y的集合构成Y. Y一般是离散的 （x,y)构成样本空间。给定一个训练样本， 我们感兴趣的概率模型是P(Y=y|X=x)，一 般写作 P(y|x)。如何建立该模型？样本概率分布 我们建立的模型，最好要符合训练样本， 也就是说，P(y|x) 满足样本概率分布 比如，在样本里，如果“漂亮”翻译成“pretty” 的概率为0.3，我们希望我们的模型的预测 结果也一样。当然，

4、最大似然估计不太好 。 我们引入特征函数的概念来更加细致地表 达样本的性质特征函数 引入布尔特征函数f(x,y)，取值0,1，如f(x,y)=1: if (x=漂亮，后面跟“男人”） do not pretend you know something you dont 模型p(y|x)的条件熵： p*=argmax p H(p)最大熵模型求解 问题：满足限制条件下的极值问题 采用拉格朗日乘子法拉格朗日乘子法带约束的优化问题不带约束的优化问题方程原问题的解拉格朗日法 -求偏导数法 -解方程 - 熵是凸函数，解唯一 其中，Z(x) 称为 normalization factor，也称为partit

5、ion function 模型具有指数形式。求对数：log(p*)= i i f i(x,y) log(Z(x) 因此也叫 log-linear model 上述求解过程假设 i 不变。 如何求解 i?对偶定律 鞍点（saddle point）,对任意(x,y)(X,Y)有 F(x*,y)F(x*,y*)F(x,y*),称(x*,y*)为鞍 点。 根据Kuhn-Tucker定律，使最小化的*使L(p*, *)最大： *=argmin L(p*, ) 定义（）L(p*, )，我们求其最大值最大似然 给定一个条件概率模型，其训练样本的概 率为我们可以忽略L(p,)最后一项 恰好是样本的似然率！ 使

6、样本概率最大的模型是满足受限条件的最大 熵模型！ 最大熵最大似然！ 这说明了最大熵模型的合理性。（回想：最大 熵是满足约束条件的！）关于的说明 技术上，是拉格朗日乘子 实际 上，表示特征的权重 0，无用特征 ，最佳分类特征（就是它！） ，反向分类特征（肯定不是它！） 我们前面提到，不需要实数特征函数，因 为可以用来体现MaxEnt和Naive Bayes参数估计 GIS IIS 梯度法 有限内存拟牛顿法参数估计 最大似然：找出使下列最大的值Generalized Iterative Scaling 算法 GIS算法可以求出模型中特征的权重i G.I.S. needs, in order to

7、work, “x,y Si=1N fi(x,y) = C to fulfill, define additional constraint:fN+1(x,y) = Cmax - Si=1N fi(x,y), where Cmax = maxx,y Si=1N fi(x,y) Ep(fi) = Sx,yp(x,y)fi(x,y) 1/|T| St=1TSyYp(y|xt)fi(xt,y) algorithm 1. Initialize i(1) (any values, e.g. 0), compute di=E(fi(y,x), i=1N+1 2. Set iteration number n

8、 to 1. 3. Compute current model distribution expected values of all the constraint expectations Ep(n)(fi) (based on p(n)(y|xt) 4. Update i(n+1) = i(n) + (1/C) log(di/Ep(n)(fi) i 5. Repeat 3.,4. until convergence.Improved Iterative Scaling （ Berger) 求i满足Ep(n)(fi) =Sxyp(x)p(n) (y|x)fi(x,y)exp(if#(x,y)

9、 = E(fi(x,y)=di Update i(n+1) = i(n) + i最大熵的问题 最大熵模型不假设模型服从什么分布，但 是要求模型在训练数据上对每个特征的期 望值符合训练数据，会导致过度拟合（ overfitting）这使得对于新数据缺乏适应性 。这正如最大似然估计不是最好的概率函 数。 如果知道训练数据符合某种分布，如高斯 分布、指数分布，我们可以利用贝叶斯先 验分布来减少这种overfittingExponential PriorJoshua Goodman ： Exponential Priors for Maximum Entropy Models (2004) 特征选择问

10、题 MaxEnt的优点是可以任意选择你认为有用 的特征 虽然可以自动选择特征权重，但是太多的 特征导致效率降低 贪心算法选择特征(Berger)：初识特征集为 空，每次增加使训练样本的log-likelihood增 加最大的特征。算法步骤 有效特征集合E=，令p为均匀分布 计算熵H(p)。 对以下步骤循环K次： 对每个不在E里面的特征fi，把E+fi作为有效 特征，计算熵Hi(pi)； 假设Hm(pm)最小，则： E=E+fm。数据稀疏 出现次数很少的特征可靠吗？ 难说 为了压缩模型，倒是可以采用count cutoff 的办法最大熵模型的应用 词性标注（ Ratnaparkhi 1996）

11、句法分析（ Ratnaparkhi 1999） WSD (Gaustad 2004) 命名实体识别（Klein 2003) 机器翻译（Och 2002）MaxEnt features 对词性标注而言，环境x为每个词wi周围的上下文 。如设 xi = (wi, wi+1,wi+2,wi-1,wi-2,ti-1, ti-2) (ti表示词wi的词性） 特征函数如 f(xi, ti) = 1 if suffix(wi)=ing 1, 2, . . .) from training data D = (x(i), y(i) with empirical distribution p(x, y).CRF

12、 Estimation And we return to the log-likelihood maximization problem, this time we need to find that maximizes the conditional log-likelihood:CRF Estimation From now on we assume that the dependencies of Y, conditioned on X, form a chain. To simplify some expressions, we add special start and stop s

13、tates Y0 = start and Yn+1 = stop. CRF Estimation Suppose that p(Y|X) is a CRF. For each position i in the observation sequence X, we define the |Y|*|Y| matrix random variable Mi(x) = Mi(y, y|x) by:ei is the edge with labels (Yi-1,Yi) and vi is the vertex with label YiCRF Estimation The normalization

14、 function Z(x) is The conditional probability of a label sequence y is written asParameter Estimation for CRFs The parameter vector that maximizes the log- likelihood is found using a iterative scaling algorithm. We define standard HMM-like forward and backward vectors and , which allow polynomial c

15、alculations. For example:Experimental Results Set 1Set 1: modeling label bias Data was generated from a simple HMM which encodes a noisy version of the finite-state network (“rib/ rob”) Each state emits its designated symbol with probability 29/32 and any of the other symbols with probability 1/32 We train both an MEMM and a CRF The observation features are simply the identity of the observation symbols. 2, 000 training and 500 test samples were used Results: CRF error: 4.6% MEMM error: 42% Conclusion: MEMM