支持向量机及排序机器学习.pptx

《支持向量机及排序机器学习.pptx》由会员分享，可在线阅读，更多相关《支持向量机及排序机器学习.pptx（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Introduction to Information Retrieval 现代信息检索现代信息检索中科院研究生院2011年秋季课程现代信息检索 更新时间：Modern Information Retrieval授课人：王斌http:/ introduction to Information retrieval”网上公开的课件，地址 http:/nlp.stanford.edu/IR-book/第15讲 支持向量机及排序机器学习SVM&Learning to Rank12011/11/18提纲2上一讲回顾支持向量机文本分类中的问题基于布尔权重的学习基于实数权重的学习基于序回归的排序学习提纲3上

2、一讲回顾支持向量机文本分类中的问题基于布尔权重的学习基于实数权重的学习基于序回归的排序学习现代信息检索 4特征选择文本分类中，通常要将文本表示在一个高维空间下，每一维对应一个词项本讲义中，我们不特意区分不同的概念:每个坐标轴=维=词语=词项=特征许多维上对应是罕见词罕见词可能会误导分类器这些会误导分类器的罕见词被称为噪音特征（noise feature）去掉这些噪音特征会同时提高文本分类的效率和效果上述过程称为特征选择（feature selection）现代信息检索 5Reuters 语料中poultry/EXPORT的MI计算现代信息检索 6向量空间分类同前面一样，训练集包含一系列文档，每

3、篇都标记着它的类别在向量空间分类中，该集合对应着空间中一系列标记的点或向量。假设 1:同一类中的文档会构成一片连续区域（contiguous region）假设2:来自不同类别的文档没有交集接下来我们定义直线、平面、超平面来将上述不同区域分开现代信息检索 7Rocchio算法示意图:a1=a2,b1=b2,c1=c2现代信息检索 8 kNN算法对于 对应的文档，在1NN和 3NN下，分别应该属于哪个类？现代信息检索 9线性分类器定义：线性分类器计算特征值的一个线性加权和决策规则：其中，是一个参数首先，我们仅考虑二元分类器从几何上说，二元分类器相当于二维平面上的一条直线、三维空间中的一个平面或者

4、更高维下的超平面，称为分类面基于训练集来寻找该分类面寻找分类面的方法：感知机(Perceptron)、Rocchio,Nave Bayes 我们将解释为什么后两种方法也是二元分类器假设：分类是线性可分的现代信息检索 10 一维下的线性分类器一维下的分类器是方程 w1d1=对应的点点的位置是/w1那些满足w1d1 的点d1 属于类别c而那些w1d1 的点d1 属于类别 现代信息检索 11 二维平面下的线性分类器二维下的分类器是方程 w1d1+w2d2=对应的直线那些满足w1d1+w2d2 的点(d1 d2)属于类别c那些满足w1d1+w2d2 的点(d1 d2)属于类别现代信息检索 12 三维空

5、间下的线性分类器三维空间下的分类器是方程w1d1+w2d2+w3d3=对应的平面那些满足w1d1+w2d2+w3d3 的点(d1 d2 d3)属于类别c那些满足w1d1+w2d2+w3d3 的点(d1 d2 d3)属于类别现代信息检索 13应该选哪个超平面?现代信息检索 14本讲内容支持向量机线性可分：最大间隔非线性可分：最大间隔+最小错误空间转换：核函数及核技巧排序机器学习基于基于布尔权重的学习基于基于实数权重的学习基于序回归的排序学习14提纲15上一讲回顾支持向量机文本分类中的问题基于布尔权重的学习基于实数权重的学习基于序回归的排序学习现代信息检索 16支持向量机2-类训练数据决策面 线性

6、分类面准则:离任何数据点最远 确定分类器 间隔间隔(margin)线性分类面的位置基于支持向量(support vector)来定义16现代信息检索 17为什么要使间隔最大化？分界面附近的点代表了不确定的分类决策，分类器会以两边各50%的概率做出决策具有很大分类间隔的分类器不会做出确定性很低的决策，它给出了一个分类的安全间隔度量中的微小错误和文档中的轻微变化不会导致错误分类17现代信息检索 18为什么要使间隔最大化？SVM 分类器：在决策面周围有大的间隔与放置(无穷的)决策超平面相比，如果要在类别间放置一个宽间隔，那么选择会少很多减少记忆容量增加测试文档分类泛化能力18现代信息检索 19SVM

7、的形式化19超平面(Hyperplane)n维超平面(n=1时对应点，n=2时对应直线，n=3时对应普通平面)决策超平面定义为:截距 b 法向量 w(权重向量权重向量)，它与超平面正交所有超平面上的点 x 满足:(1)现代信息检索 20SVM形式化20预备知识考虑一个二类分类问题：xi 是输入向量 yi 是相应的标签线性分类器定义为：(2)结果为1 表示属于一个类，为+1 表示属于另一个类 xi 代表的是一系列带标签点，称为输入空间对于SVM，两类的标签分别用+1 和 1来标记，截距用b来代表现代信息检索 21函数间隔(Functional Margin)21函数间隔第i个样例 xi 到超平面

8、的距离为：yi(wTxi+b)对于决策平面来说，某个数据集的函数间隔是数据集点中最小函数间隔的2倍2倍这个因子来自对整个间隔宽度的计算如果某个点远离决策分类面，那么可以确信该点的类别归属但是，我们可以通过放大w 和b来获得我们所需要的任意函数间隔，因此，我们需要对向量 w 的大小加以限制现代信息检索 22几何间隔(Geometric margin)分类器的几何间隔分类器的几何间隔:中间空白带的最大宽度，该空白带可以用于将两类支持向量分开 (3)很显然，不管参数w和b如何缩放，几何间隔总是一个不变量。比如，即使将w和b分别替换成5w和5b，其几何间隔仍然保持不变，这是因为它已经基于w的长度做了归

9、一化处理。22现代信息检索 23线性SVM的数学推导规范化距离：假定所有数据到分类面的距离至少是1 (4)每个点到分类面的距离为 ，几何间隔为：我们的目标就是最大化 ，也就是说在满足的条件下，寻找w和b，使得 最大23现代信息检索 24线性 SVM的数学推导最大化 相当于最小化 ，于是可以将SVM求解过程转化为如下的一个求最小化的问题：上述问题实际上是在线性约束条件下的二次函数优化问题。该问题是数学中的基本问题之一，存在很多解决算法(比如，有一些二次规划库)问题：寻找 w 及b 使得：最小 (因为 )且所有数据点满足 ,and24现代信息检索 25线性 SVM的结果形式25线性SVM的结果分类

10、器为：其中上式中的求和只对支持向量求和，也就是说，对于新来的文档向量 ，与所有支持向量求内积之后加权求和，然后与阈值-b进行比较，最后根据结果的符号判断文档的类别。现代信息检索 26SVM要点重述给定训练数据集该数据集定义了最佳的分类超平面基于该数据集，通过二次优化过程寻找该超平面 ：对于待分类的新数据点 ，分类函数计算该点到超平面法向量的投影上述函数的符号决定了该数据点类别的归属如果该点在分类器的间隔之内，分类器可以在原来的两个类之外，返回“类别未知”的值可以转化为一个分类概率26现代信息检索 27软间隔(Soft margin)分类如果数据不线性可分？标准做法：允许在宽间隔条件下犯少许错误

11、某些点、离群点或者噪音点可以在间隔之内或者在间隔的错误一方计算每个错误点的代价，具体的计算它们到分类面的距离。松弛变量 i:允许点 不满足间隔要求，但是其错误代价正比于i 优化问题：在间隔的宽度 和 那些需要在计算间隔时去掉的点数之间折中i 的和给出了所有训练错误的上界软间隔SVM主要在最小化训练错误和最大化间隔之间折中27现代信息检索 28支持软间隔的 SVM的数学推导引入软间隔，可以将SVM求解过程转化为如下的一个求最小化的问题：C是加权系数，上述问题仍然是在线性约束条件下的二次函数优化问题，同样可以求解。问题：寻找 w 及b 使得：+C i最小 且所有数据点满足28现代信息检索 29非线

12、性SVM通过空间映射将原始空间映射到新空间，为避免显式的映射函数，引入核函数(定义在原始空间下但是结果是新空间下的内积函数)常用核函数多项式核径向基核29现代信息检索 30支持多类的支持向量机SVMs:是一个天生的二类分类器实际中存在一些常用的技巧：构造|C|个一对多(one-versus-rest 或one-versus-all或OVA)的二类分类器，选择那个在测试数据上具有最大间隔的分类器所给出的类别另一种方法：建立一系列一对一（one-versus-one）的分类器，选择这些分类器中给出的最多的那个类别。虽然包含|C|(|C|1)/2 个分类器的构建过程，但是分类器的训练时间可能实际上会

13、降低，这是因为每个分类器训练的语料都小很多30现代信息检索 31SVM用于支持多类问题更好的解决方法：结构化SVM将分类问题一般化为如下问题：类别不再只是多个独立的类别标签集合，而可以是相互之间具有关系定义的任意结构化对象的集合。在基于机器学习的排序中将进一步介绍该方法31现代信息检索 32一个SVM的例子几何上看:最大间隔权重向量将和两类中距离最短的那条线段(直线)平行，即与连接点(1,1)和(2,3)的直线平行，这可以得到权重向量(1,2).最优的分类直线与上述线段垂直并相交与其中点(中垂线)，因此它经过点(1.5,2).于是，可以求得SVM的决策直线方程为：y=x1+2x2 5.532现

14、代信息检索 33一个SVM的例子（续）代数法求解:在约束条件 下，寻找最小的 我们知道解的形式为：于是有：a+2a+b=1,2a+6a+b=1解得，a=2/5 及 b=11/5 因此，最优超平面的参数为：b=11/5.此时间隔为：33提纲34上一讲回顾支持向量机文本分类中的问题基于布尔权重的学习基于实数权重的学习基于序回归的排序学习现代信息检索 35文本分类许多商业应用“能够基于内容对文档进行自动分类的商业价值毋庸置疑，在公司内网、政府机构及互联网出版等机构或领域中存在大量的潜在应用”采用领域相关的文本特征在性能上会比采用新的机器学习方法获得更大的提升“对数据的理解是分类成功的关键之一，然而这

15、又是大部分分类工具供应商非常不擅长的领域。市场上很多所谓的通用分类工具并没有在不同类型的内容上进行广泛的测试。”35现代信息检索 36分类器的选择当面对一个建立分类器的需求时，第一个要问的问题就是：训练数据有多少？一点都没有?很少?挺多?量很大，而且每天都在增长?实际中的挑战:建立或获取足够的训练语料为了获得高性能的分类器，每个类都需要成百上千的训练文档，而且现实当中的类别体系也非常庞大36现代信息检索 37如果没有任何训练数据采用人工撰写规则的方法实际中的规则要比这个例子长很多，并且可以采用更复杂的表示方式。经过精心调整（也就是说，人们可以在开发集上调整规则）之后，利用这些规则分类的精度可以

16、非常高。然而，要构造非常好的人工规则需要做大量的工作。一个基本合理的估计数字是每个类别需要两天的时间，由于类别中的文档内容会发生漂移，所以必须还要利用很多额外的时间去维护规则。例子IF(wheat OR grain)AND NOT(whole OR bread)THENc=grain37现代信息检索 38如果拥有较少的训练数据，又希望训练一个有监督的分类器如何尽快地获得更多的标注数据最佳方法：将自己也放入到标注的过程中去，在这个过程中人们自愿为你标注数据，并且这也是他们正常工作的一部分。例子很多情况下，人们会根据需要整理或者过滤邮件数据，这些动作能够提供类别相关的信息38主动学习(Active

17、 Learning)建立一个系统来确定应该标注的那些文档。通常情况下，这些文档主要指那些分类器不确定能否正确分类的文档。现代信息检索 39如果拥有训练数据39拥有极大规模的标注数据分类器的选择也许对最后的结果没有什么影响，目前我们还不清楚是否有最佳的选择方法。也许最好的方法是基于训练的规模扩展性或运行效率来选择。为达到这个目的，需要极大规模的数据。一个通用的经验法则是，训练数据规模每增加一倍，那么分类器的效果将得到线性的提高。但是对于极大规模的数据来说，效果提高的幅度会降低成亚线性。拥有适量的标注数据能够使用我们在前面所介绍的任何文本分类技术通常优先考虑混合方法现代信息检索 40大规模高难度分

18、类体系如果文本分类问题仅包含少量具有区分度的类别，那么很多分类算法都可能取得很好的结果。但是实际的文本分类问题往往包含大量非常类似的类别。对大量相近的类别进行精确分类是一个固有的难题例子Web目录（如Yahoo!目录或ODP（Open Directory Project）目录）、图书馆分类机制（杜威十进制分类法或美国国会图书馆分类法），或者用于法律和医学领域的分类机制。40提纲41上一讲回顾支持向量机文本分类中的问题基于布尔权重的学习基于实数权重的学习基于序回归的排序学习现代信息检索 42 基本思路词项权重(如tfidf)的目标是为了度量词项的重要性将一篇文档中所有词项的权重加起来便可以计算文

19、档和查询的相关度，基于该相关度可以对所有文档排序上述过程可以想象成一个文本分类问题词项权重可以从已判定的训练集合中学习得到上述研究方法被归入一类称为机器学习的相关度(machine learned relevance)或排序学习(learning to rank)42现代信息检索 43权重学习主要方法：给定训练样例集合，每个样例表示为三元组最简单的情况：相关性判定结果R(d,q)要么为1(相关)，要么为0（不相关）更复杂的情况：多级相关从上述样例中学习权重，使得学到的评分接近训练集中的相关性判定结果。下面以域加权评分(Weighted zone scoring)为例来介绍43现代信息检索 44

20、域加权评分给定查询以及具有3个域(author、title、body)的文档集合域加权评分对每个域都有个独立的权重，比如 g1,g2,g3并非所有域的重要性都完全一样:比如：author title body g1=0.2,g2=0.3,g3=0.5(系数总和为1)如果查询词项出现在某个域中，那么该域上的得分为1，否则为0(布尔权重)例子查询词项仅仅在title和body域中出现于是文档得分为：(0.3 1)+(0.5 1)=0.8.44现代信息检索 45域加权评分的一般化给定 q 和 d,域加权评分方法通过计算所有文档域得分的线性组合，赋予(q,d)一个0,1内的得分考虑一系列文档，每篇文档

21、包含 l 个域令 g1,.,gl 0,1,且有 gi=1对于 1 i l，令 si 为q和文档第i个域的 布尔匹配得比如，si可以是将域当中查询词项出现与否映射为0或1的任意布尔函数。域加权评分也称为排序式布尔检索 gisi45现代信息检索 46域加权评分及权重学习域加权评分可以看成基于布尔匹配值的线性函数学习，每个布尔匹配值对应一个域坏消息：权重学习需要训练集，而人工产生训练集中的相关性判断费时费力特别是在动态语料库环境下(比如Web)好消息：将权重gi的学习简化为一个简单的优化问题46现代信息检索 47域加权评分中的权重学习最简单的情况：每篇文档有两个域-title,body域加权评分的公

22、式如下：gisi (2)给定 q,d,要根据d的不同域与查询q的匹配情况计算 sT(d,q)及sB(d,q)利用 sT(d,q)、sB(d,q)及常数 g 0,1我们可以得到(q,d)的得分：score(d,q)=g sT(d,q)+(1 g)sB(d,q)(3)47现代信息检索 48基于训练样例学习权重g训练样例:三元组形式 j=(dj,qj,r(dj,qj)给定训练文档 dj 和训练查询qj，通过人工判定得到r(dj,qj)(要么相关要么不相关)例子48现代信息检索 49基于训练样例学习权重g对每个训练样例 j ，我们有布尔值 sT(dj,qj)和sB(dj,qj)，利用这些布尔值可以计算

23、：score(dj,qj)=g sT(dj,qj)+(1 g)sB(dj,qj)(4)样例49现代信息检索 50权重学习比较该得分和人工判定结果的差异人工判定结果中，相关记为1，不相关记为0评分函数的错误定义为：(g,j)=(r(dj,qj)score(dj,qj)2 (5)于是，整个训练集上的总错误为：(g,j)(6)权重g的学习归结为选择使得上述总错误率最小的那个g50现代信息检索 51课堂练习:寻找使总错误 最小的g值相关记为 1，不相关记为0计算得分:score(dj,qj)=g sT(dj,qj)+(1 g)sB(dj,qj)计算总错误:j (g,j)，其中(g,j)=(r(dj,q

24、j)score(dj,qj)2选择使得总错误最小的g值51训练样例现代信息检索 52习题解答计算评分 score(dj,qj)score(d1,q1)=g 1+(1 g)1=g+1 g=1score(d2,q2)=g 0+(1 g)1=0+1 g=1 gscore(d3,q3)=g 0+(1 g)1=0+1 g=1 gscore(d4,q4)=g 0+(1 g)0=0+0=0score(d5,q5)=g 1+(1 g)1=g+1 g=1score(d6,q6)=g 0+(1 g)1=0+1 g=1 gscore(d7,q7)=g 1+(1 g)0=g+0=g 计算总错误 j (g,j)(1 1

25、)2+(0 1+g)2+(1 1+g)2+(0 0)2+(1 1)2+(1 1+g)2+(0 g)2=3g2+(1-g)2=4g2-2g+1 选择使得总错误最小的g值求解g=0.2552提纲53上一讲回顾支持向量机文本分类中的问题基于布尔权重的学习基于实数权重的学习基于序回归的排序学习现代信息检索 54一个简单的机器学习评分的例子迄今为止，我们都是考虑一种非常简单的情况，即我们考虑的是布尔相关值的组合现在考虑更一般的情况54现代信息检索 55一个简单的机器学习评分的例子设置:评分函数是两个因子的线性组合:1 查询和文档的向量空间相似度评分(记为)2 查询词项在文档中存在的最小窗口宽度(记为)查

26、询词项的邻近度(proximity)往往对文档的主题相关性具有很强的指示作用查询词项的邻近度给出了隐式短语的实现因此，我们的一个因子取决于查询词项在文档中的词袋统计量，另一个因子取决于邻近度权重55现代信息检索 56一个简单的机器学习评分的例子给定训练集，对每个样例计算向量空间余弦相似度 窗口宽度 上述结果构成训练集，与前面不同的是，我们引入的是两个实数特征因子(,)例子56现代信息检索 572-D 平面上的图展示57现代信息检索 58一个简单的机器学习评分的例子同样，相关记为1，不相关记为0我们的目标是寻找一个评分函数，该函数能够组合特征因子的值，并尽量接近0或1希望该函数的结果尽量与训练集

27、上的结果保持一致不失一般性，线性分类器可以采用下列通用形式：Score(d,q)=Score(,)=a+b+c,(7)公式中的系数 a,b,c 可以从训练语料中学到58现代信息检索 59一个简单的机器学习评分的例子函数Score(,)可以看成悬挂在右图上空的一个平面理想情况下，该平面在R表示的点之上的函数值接近于1，而在N表示的点之上的函数值接近于059现代信息检索 60一个简单的机器学习评分的例子引入阈值 如果Score(,),则认为文档相关，否则认为不相关从上面的 SVM我们可以知道,Score(,)=的点构成一条直线(图中虚线)它能将相关和不相关文档线性地分开60现代信息检索 61一个简

28、单的机器学习评分的例子因此，给定训练集情况下判定相关/不相关的问题就转变成一个学习问题，如前面提到，相当于学习一条能够将训练集中相关文档和不相关文档分开的虚线在-平面上,该直线可以写成基于 和(分别表示斜率和截距)的一个方程前面已经介绍选择直线的线性分类方法如果能够构建大规模训练样例，那么就可以避免手动去调节评分中的参数瓶颈：维护一个合适的有代表性的训练样例需要较大的卡西开销，而且这些样例的相关性判定需要专家来进行61现代信息检索 62基于机器学习的检索结果排序上面的例子可以很容易地推广到包含多个变量的函数除余弦相似度及查询词项窗口之外，存在大量其他的相关性度量方法，如 PageRank之类的

29、指标、文档时间、域贡献、文档长度等等如果训练文档集中的这些指标可以计算出来，加上相关性判定，就可以利用任意数目的指标来学习分类器。62现代信息检索 63Microsoft Research 在2010.6.16公布的134个特征Zones:body,anchor,title,url,whole documentFeatures:query term number,query term ratio,stream length,idf,sum of term frequency,min of term frequency,max of termfrequency,mean of term freq

30、uency,variance of term frequency,sum of stream length normalized term frequency,min of streamlength normalized term frequency,max of stream lengthnormalized term frequency,mean of stream length normalized termfrequency,variance of stream length normalized term frequency,sum of tf*idf,min of tf*idf,m

31、ax of tf*idf,mean of tf*idf,varianceof tf*idf,boolean model,vector space model,BM25,LMIR.ABS,LMIR.DIR,LMIR.JM,number of slash in url,length of url,inlinknumber,outlink number,PageRank,SiteRank,QualityScore,QualityScore2,query-url click count,url click count,url dwell time.63现代信息检索 64基于机器学习的检索结果排序然而，

32、利用上述方法来进行IR的排序未必是正确的问题处理方法统计学家通常将问题分成分类问题(预测一个类别型变量)和回归问题(预测一个实数型变量)在这两者之间，有一个特别的称为序回归(ordinal regression)的领域，其目标是预测一个序的领域，其目标是预测一个序基于机器学习的Ad hoc检索可以看成是一个序回归问题，这是因为检索的目标是，给定q的情况下，对所有的文档进行排序64提纲65上一讲回顾支持向量机文本分类中的问题基于布尔权重的学习基于实数权重的学习基于序回归的排序学习现代信息检索 66将IR排序问题看成序回归为什么将IR排序问题看成一个序回归问题？对于同一查询，文档之间可以按照相对得

33、分排序即可，并不一定要求每篇文档有一个全局的绝对得分因此，只需要一个排序，而不要得到相关度的绝对得分，问题空间可以减小这对于Web检索来说特别重要，Web检索中排名最高的一些结果非常重要利用结构化SVM 进行IR排序利用结构化SVM框架可以处理IR排序问题，对于一个查询，预测的类别是结果的排序66现代信息检索 67排序SVM的构建给定一些已经判定的查询对训练集中的每条查询q,我们都有针对该查询的一系列文档集合，这些文档已经由人工按照其与查询的相关度排序对每个文档、查询对，构造特征向量 j=(dj,q)，这里的特征可以采用前面讨论的特征对于两篇文档di 和dj，可以计算特征向量之间的差异向量：:

34、(di,dj,q)=(di,q)(dj,q)(8)67现代信息检索 68排序SVM的构建依据假设，di、dj 中的一个更相关如果 di 比 dj更相关，记为di dj(在检索结果中，di 应该出现在 dj 前面),那么分配给(di,dj,q)向量的类别为 yijq=+1，否则为 1学习的目标是建立一个分类器，满足：wT(di,dj,q)0 iff di dj(9)68现代信息检索 69排序SVM(Ranking SVM)该方法已经被用于构建排序函数，在标准数据集的IR评测中表现的性能优于普通的人工排序函数参考信息检索导论第239页的一些参考文献69现代信息检索 70注意:线性 vs.非线性权重

35、计算前面介绍的方法也代表当前研究中的主要做法，即将特征进行线性组合但是很多传统IR方法中还包括对基本量的非线性放缩方法，比如对词项频率或IDF取对数当前来说，机器学习方法很擅长对线性组合的权重进行优化，但是并不擅长基本量的非线性放缩处理。该领域仍然存在大量人工特征工程的方法70现代信息检索 71本讲内容支持向量机线性可分：最大间隔非线性可分：最大间隔+最小错误空间转换：核函数及核技巧排序机器学习基于基于布尔权重的学习基于基于实数权重的学习基于序回归的排序学习71现代信息检索 72参考资料信息检索导论第15章http:/ifnlp.org/ir72 现代信息检索课后练习习题15-2习题15-373