北邮郭军web搜索chapter5

1、Web 搜索搜索郭军郭军北京邮电大学 第第5 5章章 信息过滤信息过滤n基本方法基本方法n模型学习模型学习n垃圾邮件及垃圾短信过滤垃圾邮件及垃圾短信过滤n话题检测与追踪系统话题检测与追踪系统引言引言n信息过滤的本质是“流环境”下的二元分类u流环境：过滤系统处于信息持续新生的环境之中，新的数据源源不断地流经过滤系统u二元分类：一类是需要筛选出来的，一类是系统不关心的 n以模式分类模式分类为技术核心，高效高精度地处理数据流IR被检索的文档相对稳定 用户查询需求不同 IF信息资源动态变化 用户需求相对固定IF的研究重点n分类器的选择u针对特定的应用环境选择分类器模型u目前研究较多的是朴素Bayes模

2、型、向量相似度(模板匹配)模型、SVM、k-NN等n分类器的学习及优化u生成式算法、区分式算法u计算效率，类别模型的增量学习和自动演进，半监督学习、特征降维技术基本方法基本方法n信息过滤系统中常用的分类器uBayes分类器u向量距离分类器uk近邻分类器uSVMn系统性能评价Bayes分类器分类器nBayes分类器将分类问题看作统计决策问题，以最小错误率为目标进行分类u前提：事先获得各个类别的似然函数，决策时利用Bayes公式计算给定样本特征值条件下各类别的后验概率n设随机变量xRd, 各类别的似然函数为P(x|ci)，对于某确定样本t, 根据Bayes公式：( ) ()()( )iiiP c

3、PcP cPttt分类方法n计算得到各个P(ci|t)后，将样本t分到类别ck中，其中1argmax()jj mkP c t举例：随机选取100封邮件，进行人工标注，其中有30封垃圾邮件和70封非垃圾邮件，对于词“培训”，垃圾邮件中有21封含有该词，非垃圾邮件中有28封含有该词，假定过滤系统只采用该词判别是否为垃圾邮件，问若一封新邮件含有该词，则过滤系统认为该邮件是否是垃圾邮件？对于多个词，如何判别？似然比Rln二元分类问题可以根据似然比Rl来决定t的归属 对数似然比：假设x的各维数据之间相互独立； 朴素Bayes分类器 111222(| )( ) ( |)(| )() ( |)lP cP c

4、 PcRP cP c Pctttt111221( )(|)()(|)djjldjjP cP tcRP cP tc121211lnln( )ln()ln (|)ln (|)ddljjjjRP cP cP tcP tc向量距离分类器向量距离分类器n向量距离分类器可以看作是Bayes分类器的简化，它用各类别数据的均值向量、方差向量、协方差矩阵等参数近似描述它们的分布特性，利用向量之间的各种距离进行分类，常用的距离尺度有:21()dgjijjDt1|dcjijjDt1()()TmiiiDtt221() /dsjijijjDtk近邻分类器近邻分类器n也称k-NN分类器(k-Nearest Neighbo

5、r)n最大特点是不需要训练类别模型，而是按某种合理的比例从各类别中抽取样本，用所有抽出的样本构成分类器的总体特征样本n对于一个给定的样本t，首先按照某种距离测度找出与其最接近的k个样本，然后根据这k个样本所属类别进行投票SVMnSVM是一种以结构风险最小化为目标的二元分类器，在寻找最优分类超平面时不但要求将两类数据隔离，而且要求两类数据距超平面的平均距离最大n设线性可分数据集为nD维空间中线性判别函数的一般形式为n分类超平面方程为1(,)niiiyDxdRx1, 1y ( )gbxw x0bw x系统性能评价系统性能评价n评价指标主要包括分类器的精度和速度u速度取决于分类器算法的复杂程度，在实

6、际应用中与计算机的硬件性能关系很大u精度通过与人工标注结果(ground truth)进行比较来计算n对于二元分类问题，常用的精度指标有u准确率u召回率uF-measureubreak-even点 精度指标标注标注为为L类类标注为标注为非非L类类判别为判别为L类类ab判别为非判别为非L类类cd分类与标注对应关系的频次分类与标注对应关系的频次 aPabaRaci) 准确率准确率(Precision)表示所有被分类器分到类L的数据中正确的所占的比例ii) 召回率召回率(Recall)表示所有实际属于L的数据被分类器分到L中的比例iii) 平衡点平衡点BEP(Break-even Point): P

7、和R值是互相影响的: P会随着R的升高而降低，反之亦然。因此，为了更全面地反映分类器的性能，一种做法是选取P和R相等时的值来表征系统性能，这个值叫BEPiv) F值值一种把准确率和召回率综合考虑的评价方法，定义如下：22(1) P RFPR12 P RFPR模型学习模型学习n生成式学习u典型应用：利用EM算法对GMM的参数进行估计u共同特征：每个类模型只用本类的样本进行估计，估计的准则是使模型产生训练样本的可能性最大(最大似然)u早期的模型学习主要采用生成式算法n区分式学习u典型应用: SVM的学习u共同特征: 由需要相互区分的各类样本共同构成一个模型，通过多类样本的“角力”形成不偏不依的分类

8、面降维变换降维变换n需要进行学习的降维变换是指变换核（基函数）随被处理数据集变化以获得最佳变换效果的变换(自适应变换)u主成分分析PCA(Principal Component Analysis)u独立成分分析ICA(Independent Component Analysis)u线性鉴别分析LDA(Linear Discriminative Analysis)u希尔伯特黄变换Hilbert-Huangu自适应变换也存在生成式和区分式之分PCA dRxN1iixX11NxiiNx 11)NtxixixiN (x)(x 设随机变量，存在一个样本集，则其均值可估计如下：协方差矩阵可估计如下：xii

9、a1 ,.,dAaa()xtAyx 求解按降序排列的d个特征值和对应的特征向量，并构成矩阵称为x的PCA变换(也称K-L变换)，则式PCA的性质的性质yx tAAxyx1yd PCA变换后的变量y是零均值的随机变量，其协方差矩阵为：由于A是列为的特征向量的正交矩阵，所以是对角阵且对角线元素为的特征值，即：由于y的非对角元素都是零，所以随机变量y的各维之间是不相关的LDA nLDA的思想是找一个投影方向，使得投影后在低维空间里样本的类间散度较大，类内散度较小 x1x2xLDA的定义的定义(1/3)1cwiiSS()()itiiCSixxmxmdRx1()()ctbiiiinSmm mmm设Ci为

10、第i类样本的集合，共有c类样本，则样本类内散度矩阵定义为：其中，mi为第i类样本的均值，样本类间散度矩阵定义为：其中为样本集的总体均值向量LDA的定义的定义(2/3)t Wyx:将d维的随机变量x变换到c-1维11()() ()()ySSiccttwiibiiiiCinymymmm mm SW S WSW S Wttwwbb定义在变换空间中样本的类内和类间散度矩阵：容易证明LDA的定义的定义(3/3)定义如下的准则函数：()argmaxargmaxTbbTwwJoptWWSW S WWW S WS(1,2,)biiwiic 1S wS w， -1wbS S1S S WWwb 121 ,cdia

11、g 容易证明，使J(.)最大化的变换矩阵W的列向量由下列等式中的最大特征值对应的特征向量组成：这是一个广义特征值问题，如果Sw是非奇异的，W的列向量就是由矩阵的特征向量组成其中LDA的奇异性的奇异性nLDA是信息过滤中数据降维的核心算法之一n在应用中常遇到类内分散度矩阵Sw奇异的问题u当数据维数很高时，能够获得的样本数常常相对不足，使得独立的训练样本数N小于数据维数d，而这将导致Sw为奇异矩阵u信息过滤所处理的文本、图像、音频等一般都是在高维数据空间中表达的u解决LDA奇异性问题时，常先用某种生成式算法对数据进行降维LDA奇异性的解决奇异性的解决n 主要方法: u正则化正则化LDAuPCA+L

12、DAuPCA+NULL空间空间uLDA/QRuLDA/GSVD 正则化正则化LDA（RLDA）n一种简单的解决Sw矩阵奇异的方法是利用正则化思想在Sw上加一个扰动量，数学表达为其中 0，I为一个单位矩阵 这种方法的主要问题在于扰动量的选取有难度。如果扰动量太小可能不足以解决奇异问题，太大又会使Sw内包含的判决信息丢失wwSSIPCA+LDAn首先用PCA对数据降维，使Sw成为非奇异矩阵，然后再进行LDAn将生成式变换与区分式变换结合nPCA变换使数据中的信息被 “忠实地”保留，同时数据维数得到了压缩，以便消除使Sw奇异的条件n难点：没有明确的理论指导PCA降维的维数选择u如果PCA维数太低，会

13、丢失过多的鉴别信息u如果维数太高，相对来说训练样本会仍显不足，这样即使能解决Sw的奇异问题，也难免会出现过拟合的现象LDA/QRn对Hb进行QR分解，得到一个正交矩阵Q和一个上三角矩阵R，然后在Q张成的低维子空间内进行鉴别分析n算法分两步完成：bd rRQbrcRR, TTbbwwSQ S QSQ S Q, bwSS第一步，对Hb进行QR分解，Hb = QR的正交列张成了Hb的秩空间是上三角矩阵第二步，在上运用LDA然后定义:LDA/GSVD n通过广义奇异值分解GSVD，用Hb和Hw代替Sb和Swn根据GSVD理论，正交矩阵YRc*c，ZRn*n，以及非奇异矩阵XRd*d满足如下关系：因此有

14、, , TTbbTTwwY H X 0Z H X0IIDDOObwbwbwbw1(,)twbbrrrdiagD1(,)twbwrrrdiagD221iiTTbbww IX的列向量就是矩阵对Hb,Hw对应的广义奇异向量，并将其作为基于GSVD的鉴别特征子空间RDMnRDM的特点主要有两方面u1）将LDA问题转化为同时对角化类内和类间散度矩阵问题u2）通过能量适应准则来近似估计 12, ,Twndiag SI0对类内散度矩阵Sw进行对角化，得：在对角矩阵上加上一个小的扰动量进行正则化，即（）的选择11*,()min( )miimnmiiJ mmE其中RDM将Sw的能量谱用作选择的标准J(m)通过前

15、m个特征值在总能量谱中所占的比例来确定m的值半监督学习半监督学习n问题：样本不足 / 标注样本不足u找到有效的方法，使得只需手工标注少数数据，就能较准确地对全部数据进行自动标注n三类算法u在聚类过程中利用已标注的数据来引导聚类u在对标注样本进行学习之后，首先处理那些有较高置信度的未标注样本，然后迭代地把这些估计加入到标注样本集中u将数据看作图上的结点，将数据间的(已知的)相似性看作结点间的初始边长(权重)，应用图的理论对数据进行聚类半监督学习的形式定义半监督学习的形式定义1,lxx1 CiRy1,ll uxx标注样本集合L =标注样本的类别向量用yij = 1 and yiq = 0 (qj)

16、表示xi点属于第j类，C为类别数用fi表示，fi是元素值为0或1的C维向量用Y表示已标注样本集的真实类别矩阵用F表示数据集的类别指示矩阵，其类别指示向量设未标注样本集合U = 半监督学习:在已知数据集L、U和Y的情况下估计F基于图的算法基于图的算法n在图中估计样本的类别函数f，使其满足两个条件：u1) 对于已标注样本，其真实类别和通过f得到的结果越接近越好u2) 对于整个样本集，f 足够平滑n这两个条件可以通过正则化方法得到满足，即在求解的过程中用先验知识对求解过程加以约束，从而获得有意义的解n类别估计函数 f 一般由两项组成，一项是损失函数，用来评价条件1的满足度；另一项是正则化，保证条件2

17、得到满足基于随机场的半监督学习基于随机场的半监督学习 n首先在图上定义一个连续的随机场，然后根据能量函数最小化时调和函数的特性获得聚类结果 2,1( ) ( )( )2iji jEwijfff()1( )EpeZffexp( )llZEdffYf基于相似点应属于相同类别，得到二次能量函数：式中W=wij是图的权值矩阵，代表结点间的相似性通过已标注数据，可以获得部分f(i)的取值即，如果xiL ，则f(i)由yi确定另，利用Gauss随机场赋予f一个概率分布其中为常数，Z为配分函数Diiijjw DW2,1( ) ( )( )2Tiji jEwijfffff1( )TpeZfff令D为一个对角矩

18、阵,，表示点i的度, 则定义由此，能量函数可以改写为：Gauss随机场可以改写为：的定义:组合Laplace矩阵基于基于Gauss随机场的学习随机场的学习(1/2) 1( )( ) Dijj iiiiwjffllluuluuWWWWW111()()uuuuuulluuulluuull fDWW ffIPP f上式中的含义与图中的平滑概念是一致的 (f(i)取周围点的均值)将权重矩阵W写成分4块的分块矩阵调和函数的解是在满足fl = yl的条件下使 f = 0其中P为图的转移概率矩阵，P=D-1W在能量函数达到最小的条件下，未标注样本点满足基于基于Gauss随机场的学习随机场的学习(2/2) 基

19、于局部一致和全局平滑的学习基于局部一致和全局平滑的学习222 ()()0 ijikjjkiijeifNNwotherwisexxxxxx2,11ijiji jiijjwffDD用一个加权图来描述数据集，在满足与标注信息一致的条件下使样本集的类别平滑变化定义图G = V,W，wij的计算方法如下根据相似度越大类别越可能一致的原则，定义目标函数是数据集中每个点与其近邻点间的差异度，越小越好优化目标函数优化目标函数A Fb1,TTTTlA00yy11,TTTTTllnfFfff2,11min. .ijiji jiijjwstYDDA Fbff聚类结果必须满足已标注的真实类别信息将这些信息表示为等式：

20、A为Cn的系数矩阵，yi为已标注样本i的真实类别向量(行向量)F为nC的类别指示矩阵b是CC的对角矩阵，bjj等于标注样本中属于第j类的样本个数最优的类别估计结果就是当xiL时，fi =yi因此，半监督学习问题就转化为了如下的最优化问题优化问题的求解优化问题的求解1122CID WDmin. .TtracestYF CFAFb令矩阵，上述优化问题可转化为(, )()TLtraceFF CFAFb(, )0(, )0TLL FFCFAFAFb将F取0/1值的条件进行松弛，使其取实数值将优化问题变为标准的二次规划问题，定义Lagrange函数令可求得类别指示向量F的最优实数解为TFR b111()

21、TRACAAC其中演进式学习演进式学习n演进式学习演进式学习分类模型随着信息环境的变化而自动演进u随机过程(而不是随机变量)动态描述数据分布，使分类模型随着分布的变化而自动演进u分类模型永远是动态的，系统通过应用环境中的样本对模型不断进行修正u不再试图估计静态的“总体分布”，而只考虑当前时刻随机变量的分布如何从上一时刻的分布演进出来u演进学习通过小样本完成，因而可以提高学习效率演进式学习的流程演进式学习的流程n不断地从应用环境中获取新样本进行模型的演进u增加自动采集新样本、接收识别(分类)模块的样本反馈、以及演进式模型学习和更新分类模型等过程n类别标注样本库中存放从应用环境中自动采集的数据样本

22、和分类器识别后反馈的样本，作为模型演进的数据源模型的演进方法模型的演进方法u假设S(ti)是随机过程X(t)在ti时刻的一个学习样本集相邻时刻学习样本集的关系是: S(ti) = S(ti-1) E(ti) A(ti)即，S(ti)可以通过从S(ti-1) 中剔除样本集E(ti)后添加样本集A(ti)的方法获得u模型演进的关键问题：u获得A(ti)和E(ti)的方法u利用A(ti)和E(ti)对ti-1时刻的模型进行演进，获得ti时刻的模型|A(ti)|和|E(ti)|的变化规律n在t0时刻用N0个样本初始化，演进初期|A(ti)| |E(ti)|n随着系统的成熟，|A(ti)|和| E(t)

23、|逐步接近ntc是系统性能达到设计要求进入常态的时刻，交换的训练样本数为dnd的大小与演进周期(ti - ti-1)成正比n在演进周期(ti - ti-1)比较短的情况下，|A(ti)|和|E(ti)|都远小于|S(ti-1)|。q性能指标影响因素：q系统进入常态的时刻qdA(ti)和E(ti)的获得nti时刻以随机的方式从采集的样本和反馈的识别样本中选出一个集合N(ti)，从中选出|A(ti)|个识别得分最低的样本组成A(ti)，在S(ti-1)中选出|E(ti)|个识别得分最低的样本组成E(ti)n|S(ti)| = | S(ti-1)| + |A(ti)| - |E(ti)|n物理意义是

24、通过更换边缘样本来移动学习样本集的类中心。 模型演进模型演进 n对于生成式模型，采用ML准则下的增量式EM算法n对于区分式模型；可采用基于自适应特征分布变化的adaboost算法n需要注意的是，由于自动采集和识别反馈的样本的类别标注是有错误率的，因此在没有人工校对的情况下S(ti)是含噪的垃圾邮件及垃圾短信过滤垃圾邮件及垃圾短信过滤n 垃圾邮件垃圾邮件(spam)过滤系统过滤系统uTREC Spam评测的技术是基于内容识别的，这不同于目前在市场上普遍应用的技术，如黑白名单过滤、基于地址分析及跟踪的启发式过滤等u文本分类器是TREC Spam技术的核心，统计学习算法是研究的重点过滤器的性能过滤器

25、的性能n两个指标：uHam错分百分比错分百分比hm%：被错分到Spam目录中的ham占ham总数的百分比uSpam错分百分比错分百分比sm%：被错分到Ham目录中的spam占spam总数的百分比n系统根据邮件为spam的可能性进行过滤u若可能性大于阈值t，则将其投入spam目录，否则投入ham目录u提高t有利于降低hm%，但会升高sm%；反之，降低t有利于降低sm%，但会升高hm%u给出每封邮件的score，可以通过改变t值获得sm%相对hm%的函数关系，这种函数关系的图形表示就是著名的ROC(Receiver Operating Characteristic)曲线Spam过滤器过滤器n最常见

26、的是SVM和朴素BayesnBrat 05创新性地将动态数据压缩中的局部匹配预测PPM(Prediction by Partial Matching)用于Spam过滤nPPM是一种自适应概率编码压缩技术u每处理被压缩数据的一个符号，PPM的概率模型P(x|context)都会随之更新u每处理完一个符号，都会得到一个新的P(x|context)u系统根据P(x|context)获得一个熵编码方案u编码方案随着context的演变而自适应调整PPMn通过训练数据获得PPM的两个概率模型P(x|context-spam)和P(x|context-ham)n与常见的方法的差别：uPPM假设信源产生符号

27、的过程符合k阶Markov过程uPPM模型会随着处理的进行而自动演进，这恰好应对了Spam特征的演进性n在PPM中，通常约定用-1阶模式指出系统的字符集A，并且假定所有字符以相同的概率1/|A|出现n未出现过的转移模式用Esc表示例例:“abracadabra”的的2阶阶PPM模型模型 垃圾短信的过滤垃圾短信的过滤n短信的基本特点：u长度短，最长不能超过140个ASCII字符或70个汉字u不完整(省略、指代、简化等)、不规范(用词另类、语法随意等) n短信分类不统一u运营商：订阅（由SP提供的）/ 手写（由手机用户手工输入的）u用户：私人 / 广告u安全部门：合法 / 非法 u发送形式：SPM

28、U / U U / U MUu发送内容：普通短信 / 垃圾短信 / 异常短信 u细分类：聊天短信、问候短信、祝福短信、娱乐短信、新闻短信、理财短信 基于正则表达式的分类基于正则表达式的分类n正则表达式(Regular Expression) u由数学家Stephen Kleene于1956年提出 u在许多脚本语言中得到支持，如Perl、PHP、JavaScript， 已经被国际组织ISO和Open Group标准化u正则表达式由模式修正符、元字符、子模式、量词和断言等元素组成，通过一系列模式对字符串进行匹配u快速地分析大量的文本以找到特定的字符模式，提取、编辑、替换或删除字符串基于统计的分类基

29、于统计的分类n特征抽取主要采用VSM和n-gram模型u构造一个词的集合来很好覆盖短信中出现的词汇u分词u词集合的选择是短信特征抽取的关键u简便的方法是以字为单位进行处理n基于单字特征的Bayes分类器1212argmax(|,.,)argmax() (,.,|)MAPini Linii LHP Cw wwP C P w wwCargmax()(|)NBikii LkHP CP wCTDT系统系统nTopic: 特指在特定时间特定地点发生的事件，而非一般意义的事件类u例：“汶川地震”VS“地震”n一个话题或事件，会有多个相关的报道(story)nTDT的任务u报道分割t将一个连续的文本流划分为

30、一个个报道u事件检测t回顾式检测 / 在线式检测u事件跟踪t将新产生的报道与系统已知的事件联系起来t给定目标事件的条件下判断每个后续报道是否在讨论这个目标事件报道分割报道分割n算法的评价u一方面是直接评价其对报道边界定位的准确性u另一方面是间接评价其对事件追踪的支持能力n基于HMM进行报道分割u基于话题转换的概率进行分割n基于局部语境分析LCA进行报道分割u将句子转换为LCA词，对其索引后判断报道边界 n将视频分割应用于报道分割 基于LCA方法的关键要素n基于内容的特征: 一对语言模型，用于帮助判断话题是否大幅改变u在线自适应语言模型 VS 离线静态语言模型n表示局部语境的语言学和结构特征的词汇特征u使用各个词的位置偏移量对词的特征进行编码u以更精细的粒度对与分割边界相关的词进行判断 n增量式地选择最佳的词汇特征的学习算法，并将词汇特征与语言模型相结合形成统一的统计模型u增量式地构建一个越来越详细的模型，对分割边界设置的正确性进行概率估计事件检测事件检测n在新闻流中标识出新的或是以前没有标识的事件n本质：无监督的学习任务n模式：回顾式/