第十六章 统计语言模型及信息检索_new

第十六章 统计语言模型及信息检索_new 第十六章 统计语言模型及信息检索 学习目标 1. 了解什么是统计语言模型,常用的统计语言模型有哪些, 2. 模型估计的及原理,采用的平滑技术及原理, 3. 什么是信息检索,信息检索的三个基本问题是什么, 4. 信息检索常用的方法及其原理是什么, 5. 信息检索常用的模型有哪些,语言模型与其他模型相比有哪些优势, 16.1 概述 在互联网时代，网络信息呈爆炸式增长趋势。在众多类型的网络信息中，文本信息数量巨大。如何从海量的文本信息中准确而全面地获取所需知识，统计语言模型及信息检索技术是其中的关键。下面将对统计语言模型及信息检索技术予以详细介绍。 16.2 统计语言模型 16.2.1 统计语言模型概述 统计语言模型产生于基于统计方法的自然语言处理系统的研究中:如语音识别系统、字 a符识别系统以及机器自动系统等。对于一个语音识别系统，给定语音信号 和语言的 S句子集合，则系统需要解决的问题可以表示为 (16-1) ，，，，Ps|aargmaxs,S s即确定概率值最大的句子(由单词构成的序列)作为识别结果。根据Bayes ，，，，P(s|a),Ps|aPsP(a)argmaxargmax s,Ss,S (16-2) ，，，，PaPa|ss其中，信号波形的先验概率与的选择无关，可以不计算;表示句子与信号的对应关系(如在英语中，每个句子和它的声音波形的对应关系)，它由信号处理过程决定，称为采样模型;称为语言模型，在这里它表示语言中句子的分布概率。 ，，Ps 因此，统计语言模型就是表示语言基本单位(词、词组、句子等，一般将句子看作语言的基本单位) 的分布函数，它描述了该语言的基于统计的生成规则。一般来说，任何一个自然语言的单词量都非常大，而且句法复杂，构成的句子数目也将非常巨大，要表示出所有句子的概率就空间复杂性来说是不可能的。所以，一般都是将句子的概率分解为各个单词的条件概率的乘积，即 n ，，，，，，Ps,P,,,,？,,,,,P,|h,12,1nnii,1i (16-3) ，，h,,,,,？,,,,,i,1i12i,1ns其中:为句子的长度;句子中单词前面个单词构成的n ,n序列，称为单词的上下文。 ,,因此， 设语言的单词集合为V,,,,,？,,，所有上下文构成的集合为12n ,,X,,,,,？|w,V12iM，则一个语言模型就是要给出语言中的每个单词对于各种上 y,V，，Py|xx,Xx下文组合的条件概率，即:，其中，。本节中，称为上下文变量，y为预测变量。 评价统计语言模型性能的最直观的指标是在测试语料集上计算的交叉熵函数 ，，，，，，HP;P,,PslogPs,TMTMs,T (16-4) T其中:为测试语料集， 为测试语料集的真实语言模型，为从学习语料集T，，，，PsPsTM M上学习建立的语言模型。 交叉熵的值越大，则学习模型与真实模型的差别也越大，表明模型的效果越差。由于测试语料集的真实语言模型实际上无法获得，因此也常采用式(16-5)评价语言模型的性能 ,,，，，，HP;PlogPs|T|,,,,,TMMs,T,, (16-5) M另一个最常用的评价指标是模型 的分支均值 ，，perplexity H，，P;PTM，，PerplexityP,P,T,2TM (16-6) 该指标可以简单理解为，在模型M 所表示的语言中，等概率出现在一个单词后面的单词的平均数目。因此它既可以用来评价语言模型的质量(该值越小，模型越好)，也可以用来表示语言的复杂性(该值越大，该语言s复杂)。 本节介绍了应用很广的模型，给出了几种常用的平滑化方法，介绍了决策树n,gram 模型，分析了最大熵模型，最后指出了统计语言模型中几个有潜力的研究方向。 16.2.2 n-gram语言模型 Markovn,gram模型于1980年提出来，是一种应用很广的统计语言模型。它采用了假 n,1设，即认为每个预测变量只与长度为的上下文有关，即 ，，，，P,|,,,,？,,,P,|,,,,？,,m12m,1mm,，，，，n,1m,n,2m,1 (16-7) J,,,,,？sss，1J,1J如果用表示单词串，，，，，则上式可以简化表示为 m,1m,1，，，，P,|,,P,|,，，m1mm,n,1 (16-8) nn式(16-8)中参数称为模型的阶数，其取值决定了模型的精度和复杂性。试验表明值越大，则对单词之间的依赖关系的描述越准确。即模型的精度越高，但模型的复杂性也越高。 1,n,7n因此，合适的值是在模型的精度和复杂性之间的一种折衷。一般为。其中n,1,2,3，分别称为Unigram、Bigram及Trigram模型。 可以看出，模型描述的语言是一种有限状态的正则文法产生的语言。它与灵n,gram 活多变的自然语言之间存在着明显的差别。然而该模型在实际应用中却取得了较大的成功，原因就在于它成功地捕捉到了自然语言中存在的局部约束(local constraint)性质。如对包 [1]，，P"gates",0.00001含139,000,000个单词的语料库的统计中，，而，，，，P"gates"|"bill",0.004P"gates"|"chairman","bill",0.47，。可以看出，每增加一个限定词，其概率值就要提高两个数量级。也正因为这个原因，该模型无法表示语言中存在的远程约束(Remote Constraint)，这些约束大都源于句子结构、语义关系等。 基于训练语料集建立模型，一般采用最大似然法(Maximize Likehood)。 即 n,gram m,1m,1m,1，，，，，，P,|,,c,c,，，，，，，MLmm,n,1m,n,1m,n,1 (16-9) m,1m,1，，c,,，，，，m,n,1m,n,1式(16-9)中表示语料集中单词串的出现次数。 n然而，该方法存在一个问题，即可能存在某个(连续个单词构成的串)，它n,gram [2]在学习语料集中没有出现，而可能出现在测试语料集中。如在文献的实验中，对一个包含242,000,000 单词的语料库，采用最大似然法建立了一个基于60,000个单词的trigram模型。当将该模型用于实际的测试语料集时，发现测试集中只有69%的n,gram在学习集中出现的 n次数大于1次。该问题称为数据的稀疏问题。而且，阶数的值越大，该问题也越突出。如果简单地根据最大似然法，会得到该n,gram的概率值为0。这种判定明显过于武断，对模型的精度影响很大。一般来说，单纯地增加训练语料集的规模，无法解决该问题。因此寻找方法，为这些没有出现在学习语料中的n,gram估计一个不为0的值，就成为n,gram语言模型研究中的一个主要问题。 16.2.3 数据平滑方法 处理数据稀疏问题的技术统称为平滑化(Something)方法。这些方法可以分为两类:一类是直接对最大似然法的估计结果进行修整，包括插值法、折扣法以及回退法等;另一类是通过对单词的聚类减小模型空间来解决数据的稀疏问题，包括各种聚类算法。 Good-Turing方法，又称为折扣最大似然法，是一种应用比较广泛的折扣法。它通过对最大似然法的结果进行调整，可以在保证满足概率归一性质的条件下，估计出在训练语料中没有出现的的概率值。它分为两个步骤来完成。 n,gram 第一步是估计没有在学习语料中出现的的概率值。首先假设学习语料的单词n,gram NNrr数目为，且其中出现次的的数目为，则存在下面的等式 n,gram rN,N,rr (16-10) 对于没有出现在学习语料中的，采用如下的公式估计它们的概率值 n,gram n，，P,,NNGT11,nn，，,,c,,011 (16-11) 该估计的基本思想是:在所有的中，存在一个由大量的特殊的构成n,gramn,gram 的集合。该集合中的每一个在学习集中要么不出现，要么只出现一次。因此，可n,gram 以用学习集中出现的这部分占有的比例来估计该特殊集合在所有中的n,gramn,gram 比例。 根据最大似然估计法，对于所有出现次数为r的，它们的概率和为 n,gram rrrrNnrPw(),，，？，,,1MLnnNNNN,(),wcwr11 (16-12) 因此(对于所有的(包括出现次数 r=0)其概率和为 n,gram nnnnnn (16-13) P(w)，P(w)，P(w)，？,,,11ML1nnnnnnw,c(w),0w,c(w),1w,c(w),r111111 将式(16-11)和式(16-12)代入式(16-13)得 rN,rNNNrNNN2112r11R1,，，，？，，？,，,1，NNNNNNN (16-14) 这明显违背了概率的归一化性质。产生的原因是为那些没有出现n,gram的估计出了一个不为0的概率值(见公式16-11)。要解决该问题，只有减少那些出现了的n,gram的概率值，即 nn，，P,,,P(,)0,,,1GT1ML1 (16-15) ,称为折扣系数，这就是该方法称为折扣法的原因。简单的方法是对所有的概率做归其中 ,化处理，这样会平均减小所有的n,gram的概率值。而 Good-Turing 方法则是根据各个 ,rrn,gram的出现次数来确定折扣系数，即 ncwr,(r，1)N/Nr，1r (16-16) ncw,,r/rr (16-17) 可以证明，经过调整后，所有的概率和将满足归一化性质 n,gram n，1n,c，，n1,c，，，，，11nnnnnc，，,,，，cnn11，，，，P,P,，,,,,,,11GTrGTnnnnnnn，，cN,，，，，，，,,,,,,,,,,,,000ccc1111111 Nr，1r，1，，nNrNN，，，1rNrr，11,,,,1,,,rNNNr,0r,0 Good-turning方法的优点是它可以对训练语料中没有出现的直接估计出一个n,gram n概率值。因此在平滑化处理中被广泛使用。可以看出，随着模型阶数的增加，数据稀疏问题会越来越严重。因此，利用低阶的模型来近似计算高阶模型也是一类经常使用且比较直观的平滑化方法。 [4]n插值法就是通过插值技术，将一个模型表示为由l阶直到阶模型的线性组n,gram 合，即 nnnn，，，，，，，，，，P,,,P,，,P,，？，,P,，,P,LNT11ML12ML2n,1MLn,1nMLn (16-18) n ,,1,r,,r1r其中，参数满足条件。关于参数值的确定，一种是理论计算，做法是在测试语料集上计算模型的分支均值Per-plexlty(M)，并取使该值最小的参数值;另外一种方法是试验调整，对于具体的应用系统(如语音识别系统、字符识别系统等)，可以通过对测试集的反复侧试，确定使错误率最小的参数值。 [3]Kaze的回退法(Backoff)也是一种常用的平滑化方法。与插值法不同.它将每一个 模型表示为的非线性组合，其中m=1，2，„，n。对于每一个n,gramm,gramm,gram ,m(m,1),gram模型.由一个回退概率，表示由模型回退到模型的概率.也可m,gram (m,1),gram以理解为在学习语料集中，给定上下文，m,gram不出现的概率。因此存在如下的递推公式 n,1n,1n,1P,(,),P,(,)，,P(,,)Kn2GTn2n,1Kn3 n,1n,1n,1P,(,),P,(,)，,P(,,)Kn2GTn2n,1Kn3 ... ... (16-19) 其中P( )的表示采用Good-Turing法确定的概率值，给定学习语料库，它可以被预先计算出GT 来。因此.确定回退概率是该方法的主要任务。根据对回退概率的理解，包含两种情况: m1.如果一个出现在学习语料库中，即则回退概率应该为t;,,0m,gramc(,),0m1 m2.如果一个没有出现在学习语料库中，即d，则需要按照下式计算回退m,gramc(,),01 概率 mm,,v(w)/[1,,(w)]mii (16-20) mm,1mm,1v(w),P(ww),(w),P(ww),,1GTm11GTm2mmmmw,c(w),0w,c(w),0i111其中 ;。 16.2.4 决策树语言模型(Decision Tree Modeling) 分析可以看出，模型中存在两个相互矛盾的问题:一方面由于模型复杂性的n,gram 2~7制约，实际中一般只采用很短的上下文，长度n的值一般为。因此用于预测的上下文信息太少，可以称其为上下文有限问题。另一方面，在模型中，对于一个预测变n,gram 量，需要考虑长度为n-1的所有上下文的组合，然而在实际应用中，可能上下文中的某些单词对预测变量并没有关系。这些上下文的存在，会增加模型的存储复杂性，更重要的是可能会对预测变量的计算产生干扰。将此称为上下文过多问题。解决这两个问题的一个直接想法就是，如何对上下文信息进行简化，使其满足两个条件:1)尽可能地保留那些与预测变量相关的单词，而不管该单词到预测变量距离的远近;2)尽可能地从上下文中删除那些与预测量无关的单词，以减少造成的干扰。这就是决策树语言模型的基本思想。 ,,给定训练语料集T(可以整理成表示为一系列有序对(x，y)的出现次数，其中xX，yV)，建立在它上面的决策树模型是一个树形结构，它包括两类结点: 1)内结点:含有子结点的结点。每一个内结点切，包含有两部分(q，T)，q表示该结iii点对应问题;T表示该结点对应的训练子集。根结点是一个特别的内结点。它的训练子集就i 是训练集T。根据根结点对应问题的m个回答形成该结点的m个子结点，并将训练集T划分到m个结点。以此类推，可以获得每个结点对应的训练子集。 (P(yx),T)ii2)叶结点:是没有子结点的结点。在每个叶结点I，包含两部分(P(y|x), T)，T表示n iii该结点对应的训练子集，P(y|x)为该结点对应的概率函数，它是通过对该结点的训练T，学i 习得到的。 例如，通过在每个内结点设置问题:“前面的一个单词是什么?”，就可以将一个n,gram V模型对应地表示为一个决策树模型.如图16-1所示。该决策树模型的每个内结点包含个子结点，且决策树的高度为n-1。最后一层全部为叶结点，其上包含有每个预测变量在对应的 上下文条件下的概率。当然，该决策树是对模型的直接表示，它表示预测变量的n,gram 出现概率与且仅与所有长度为n-1的上下文相关.因此它并没有利用到决策树的优点。如果能够在每个节点设置一个“有效”的问题，那么就可以从所有的上下文中，只选出那些与预测变量相关的上下文，并且包括长度大于，n-1的上下文。这样就可以解决模型存在n,gram的上下文有限和过多的问题。 图16-1 模型可以表示为一个特殊的决策树 n,gram ,,q,q,,,,,q,,,,12i建立决策树语言模型的关键在于:1)如何选择适当的问题集合Q= 。2)给定了问题集合，如何确定“合适”的问题序列来建立决策树。由于决策树的目的是尽可能从上下文集合中只找出那些与预测变量y相关的上下文，因此一种最直观的思想就是，可以将建立决策树的过程看作是通过选择问题序列来降低变量y的熵过程。基于这种思想，给出 [5.6] 如下的决策树模型建立算法 算法1:决策树语言模型生成算法 ,,q,q,,,,,q,,,,12i输入:训练语料T及问题集合Q= 输出:决策树语言模型 过程: 根据对树递归定义的特点，对每个结点n(开始时为根结点)作如下的处理: 1.在结点的训练语料T中(对于根结点，训练语料为T)，如果所有的序对都满足如下的条件 ,,，y,Y:(x,y),T,y,yi 则定义该结点为一个叶结点。并计算出所有预测变量的概率值。算法结束。 Tq0i2.对于每一个问题，基于该结点的训练语料，计算变量y的条件熵:即H(Y|q)。并从中i选出条件熵最小的问题，假设为q。 i H(Yq)i3，如果条件熵没有降低，则该结点是一个叶点，并基于该结点的训练语料T估计该结点的概率分布。算法结束;否则利用根据对问题q的二个答案，为该结点生成m个i 子结点。并根据对问题q的答案，将训练语料T，划分到各个子结点的训练语料。 i 1~34.分别对每个子结点重复以上的过程。 确定问题集合Q对于建立决策树模型也非常重要。为了降低模型的复杂性，要求尽可能 选择那些答案数目比较少的问题。一般要求答案为“是与否”两种情况，从而建立的决策树是一个二又树结构。 决策树模型尽管部分克服了模型存在的上下文限制和上下文过多的问题，但n,gram 在决策树模型的建立过程中存在一个问题:随着决策树高度的增加.每个结点的训练语料的规模将越来越小。而训练语料越小，参数估计的精度就越低。该问题称为数据碎化(Data Fragmentation)题。可以看出，该问题在模型中也存在。只要增加上下文的长度，n,gram 就等于对数据增加了限制条件，必然会减少数据.因此该问题很难彻底解决，但可以通过前面介绍的平滑化方法减少它对参数精度的影响。 16.2.5 最大熵模型(Maximum Entropy Modeling) 最大熵模型(又称指数模型)可以解决数据碎化问题，是目前研究的一个热点模型。其基 [7.8]本思想源于将统计语言问题看作是一个求解受限的概率分布问题。 x,X,y,V给定训练语料T，建立统计语言模型就是要确定概率分布P(y?z).其中。 (x,y)可以通过描述中的特征，在(X，Y)空间上定义了一个等价类。比如要求上下文x的最后两个单词是“Chainman Bill"，并且y= "Gates"，就可以得到一个满足该条件的(x，y)的集合。该集合可以用一个定义在(X，Y)上的标志函数(0-1函数)来表示，称为特征函数 1x,y,R，，,f(x,y),，，k0x,y,R (16-21) f(x,y)Ekk利用给定的训练语料T，可以计算出特征函数的经验期望值(用表示)为 , E,P(x,y)f(x,y),kk(x,y) (16-22) 其中，--由训练语料T计算出的经验分布。 p(x,y) P(yx)根据该特征函数及其经验期望，可以对概率分布引人如下的约束条件 P(x,y)f(x,y),E,kk(,)xy (16-23) 即要求模型给出的特征函数的期望一定要等于经验期望值。由于只需要条件概率，而不是连和概率，因此该约束式可以重写为 , P(x)P(yx)f(x,y),E,kk(x,y) (16-24) , 其中，--根据训练语料T建立的经验分布。 P(x,y) P(yx)以此类推，可以设定多个特征函数来建立对概率分布的约束，从而将问题转化 P(yx)。根据最大熵理论，满足该约束条件的分布必为给定多个约束条件下求解概率分布 [8]须尽可能地接近一个均匀分布，也就是说，该分布的熵必须最大。可以证明;以下的指数 分布满足该条件 f(x,y)iP(yx),(u/z,ik(x)i (16-25) ,fxy(,)iiu,e,z(x),u,,i,iyi其中 该结果也可以用最大似然原理推导出来，即可以证明:在满足约束条件的所有概率分布 中，指数分布式(16-25)对于训练语料集T的似然函数值最大。 [7.8]算法2:最大熵模型学习算法 (f(x,y),K)ii输人:训练语料T;一批特征函数和经验期望值对。 P(yx),x,X,y,V输出:统计语言模型。 过程: 1.初始化:首先为模型指定参数，可以采用均匀分布。 2.反复进行如下的操作，直到模型收敛为止: 1)根据当前的参数值，计算每一个特征函数的期望值，即 ,new(old)K,P(x)P(yx)f(x,y),ii(x,y) (16-26) 2)将新的期望值与经验期望值进行比较并修正参数，即 (new)(old)(new)u,uK/Kiiii (16-27) 3)基于新的参数，重新估计概率函数的值，即 f(x,y)i(new)(u,i(new)i,P(yx)(new)Z(x), (16-28) 从算法2可以看出，最大熵模型的计算是在整个训练语料T上展开的，因此有效地避免了 以前模型中存在的数据碎化问题;而且，特征函数的定义非常灵活，它可以任意建立上文x 与预测变量y之间的关系，因此，可以通过引入一些揭示语义关系的特征函数，部分地实现基于语义的语言模型。可以看出，建立该模型的主要任务在于定义特征函数，因此如何自动定义特征函数是一个主要研究任务;另外.该模型学习算法是循环算法，其计算量相当大，因此，研究高效的收敛算法也是当前的一个主要研究任务。 总结分析统计语言模型的研究现状，可以看出，统计语言模型的研究目前正在、而且还 [10]将继续从以下几个方向展开: 1.结合语言知识的统计语言模型研究。从前面介绍的几个模型来看，几乎都没有涉及语言本身的知识，只是通过对单词之间的统计关系的挖掘，来表示语言模型。尽管这些模型在某些应用领域表现不错，但这种先天不足最终会表现出来。因此研究基于语言知识的统计模型将是一个必然的方向。这方面的模型如概率上下文无关文法模型，它基于传统的上下文无关文法，为每一个非终结符扩展式加上一个统计概率，来使其具有统计的特性。 2.提升语言模型的基本单位(模型粒度)。目前的模型一般都是通过分解，将一个句子的概率分解为单词的条件概率，因此，模型表示的最小单位是单词。知道，语言中的许多结构:如人称与动词的数的一致，语义相关等很难基于单词之间的概率关系来表示。因此，建立基于句子，甚至段落的语言模型，将是一个研究方向。 3.降维技术及高效降维算法的研究。在一般的语言模型中，由于没有考虑各个语言元素之间的归类关系，所以造成变量的维数很大。直觉告诉，这些语言元素之间完全可以进行归类。因此，如何引入聚类技术，来降低整个模型的维度，但又不降低模型精度，就是一个有意义的研究方向。试验表明，绝对聚类(即每个语言元素属于一个且只有一个特定的类)往往是以降低模型的精度为代价的。因此，认为研究基于概率或模糊逻辑的聚类算法，是可望取得突破的一个方向。 4.在模型中加入人的知识的研究。目前的模型大都是基于训练数据的分析来确定模型参数，可以称之为数据驱动的模型，因此不可避免地会出现数据不足的问题，而加入人的知识是克服该问题的一个可行方法。但人的知识往往表现得不够严谨，经常会出现一些例外情况，因此基于Bayes理论的修正系统是一个值得研究的方向。通过将人的知识表示为一个先验的概率，既可以避免数据不足造成的错误估计，也可以通过数据学习，对不够精确的人的知识进行修正。 16.2 信息检索 16.2.1信息检索概述 信息检索是将信息按一定的方式组织和存储起来，并根据用户的需要找出有关信息的过程，它涉及信息的表示、存储、组织和存取等多个环节。 检索的本质是用户的信息需求和信息集合的比较与选择，即匹配的过程。从用户需求出发，对一定的信息集合(系统)采用一定的技术手段，根据一定的线索和准则找出(命中)相关的信息的过程，就是检索。 文本信息检索泛指通过特定算法或模型从包含各种信息的文档集中查找所需要的信息或知识的过程，它是自然语言处理的一个重要应用子领域，其研究方法主要包括传统的基于统计的方法和近年来基于语义的方法两大类。基于统计的方法是应用某些统计的手段从被检索文档和高标注等级文档中查询与用户需求匹配程度最好的文档;而基于语义的方法则尝试对需求实现一定程度语法和语义的分析，即对用户输入的自然语言文本进行一定程度的理解并重新生成查询。 文本信息检索的记录可以是结构化、半结构化和非结构化的数据格式，也可以是它们的混合体。结构化的数据包含了各种可以命名的部分，并按照一定的结构对内容进行组织，如数据库中就包含了各种结构化的记录。由于数据库中有信息表，因此可以利用SQL语句等搜索工具很容易地进行检索。非结构化数据无法用固定的格式对其进行组织和定义，搜索工具也无法根据特定的语义通过SQL语句进行检索，如一本小说中的一段文字，一份报纸巾的一则广告等都属于非结构化数据。还有一些数据，尽管它们以文档的形式组织，但它们具有相同的结构和语义，文档内容按照固定条目要求进行编排，这样的数据称为半结构化数据。由 于有大体相同的检索条目，半结构化的数据检索相对于非结构化的数据检索方便了很多。 信息检索的过程本质上是信息资源与信息需求的匹配过程，通过特定的算法寻找信息资源与信息需求的交集的过程，其中信息需求即为用户的查询请求，而信息资源是信息检索的基础，可以是包括文本、图像、视频和音频等数据的原始文档集。文档可以是一个完整的逻辑单元，比如一本词典或一辆小汽车等。它也可以是其中的一部分，比如一个自然段或者一个汽车零件等。通常将文档看作是内容的载体，是信息检索过程中的检索单元。但对这些文档不能直接进行检索，需要从中抽取文档表示的逻辑视图，以支持信息检索。 图16-2显示了信息检索的基本流程。由图可见，用户首先详细说明信息需求，然后系统通过分析用户的查询请求，将用户信息需求转化成查询表达式，并对查询表达式进行分析和扩展，接下来的步骤就是在文档库中匹配出相关的文挡，并通过特定的排序算法对检索到的文档进行排序，并将最终的结果返回给用户。流程中的“相关性反馈”环节，可使用户按照其自身的信息需求，对结果文档集进行筛选，将筛选后的子集反馈给系统，系统可以再利用用户的选择，进行查询表达式的改进，比如通过文档中的词语对查询表达式进行扩展，以期 获得用户需求的最佳表达。 生 检索结果 文档库 用 相关性反馈 成 户 查 信 询 息 表 需 对检索表达式 达 文档表示 文档索引 匹配并检索 求 分析和扩展 式 图16-2 信息检索的基本流程 信息检索系统的主要功能包括: (1)用户检索的表达和扩展，根据用户的输入，生成 一个查询表达式，并对查询表达式进行分析和扩展，以适合检索的要求。 (2)文档索引，收集所要检索的半结构化或非结构化文档，整理文档并为这些文档建立索引。 (3)文档表示，就是文档的组织形式，即如何来存储文档和表示文档的内容，建立供检索用的文档库。 (4)匹配并检索，这是信息检索的核心部分，根据具体模型和算法从文档库中找出与用户需求相关的文挡。 (5)相关性反馈，即把检索的结果按照相关性反馈给用户，用户可以把自己对检索结果的意见反馈给系统，从而提高以后的检索质量。 16.2.1信息检索模型 信息检索模型是描述文档和用户查询的表示形式以及它们之间的关系的框架，按照理论 [11]基础的不同可以划分为布尔模型、向量空间模型、概率模型以及基于知识的模型等。 1.布尔模型 [,,,(,)]DQFRqdij布尔模型是最早提出的信息检索模型。在布尔模型中，四元组的定 QD义为:文档表示索引项的集合。用户查询表示索引项的布尔组合，用“与”、“或”、 F“非”连接起来，并用括弧指示优先次序。匹配定义为:当且仅当一个文档满足布尔查 Rqd(,)ijF询时，才将其检索出来，检索策略基于二值判定标准。检索算法根据匹配框架判 ddqqjjii定文档是否与查询相关，如相关，即文档满足用户查询的要求，便将该文档返回。 在布尔模型中，所有的索引项要么在文档中出现，要么不出现。据此，模型将所有索引 w,{0,1}dw,1kij,jij,i项的权值全部设定为二值参数，即，当索引项在文档中出现时，， w,0qij,i反之。用户的查询;本质上是一个常规的布尔表达式。为了便于计算文档和查询的相关度，通常可以将查询的布尔表达式表示成合取向量的析取。 wdsimdq(,)qij,jj在布尔模型中，所有索引项的权值变量和文档与查询的相关度都是 w,{0,1}simdq(,){0,1},qij,j二值的，即且。查询被表述成一个常规的布尔表达式，为 qqqdDNF方便计算查询与文档的相关度，一般将查询的布尔表达式转换成析取范式，用 pd()dqtijjFi来表示任意合取分量，用二值变量表示索引项是否在文档中出现的值，用二 simdq(,)pd()qtjiFFi值变量表示查询合取分量中索引项是否出现的值。那么定义为 1|()(,()())如果，,,,,qqqtpdpq,,FFDNFiijiFsimdq(,),,j0其他,, (16-28) simdq(,)1,dqjj如果，则文档与查询相关，否则不相关。 在布尔模型中，文档与查询是否相关是二值的，也就是说只存在相关和不相关两种情况，无法对文档和查询部分匹配的情况进行描述，这样的完全匹配方式会导致返回的文档要么量太多，要么量太少，并且无法对返回的文档按照相关度大小进行排序。即便如此，由于布尔模型简单且容易理解，经过某种训练的用户可以容易地写出布尔查询式并通过布尔查询式方便地控制查询结果，因而得到了广泛的应用，目前仍然是实际应用中最常用的信息检索模型。 2.向量空间模型 向是空间模型(vector space model)是近年来应用较多的信息检索模型之一，它是由Gerard Slaton等人在1958年提出的。这个模型对于查询与文档的相关度有较强的可计算性和可操作性， 并且已经被广泛地应用于文本检索、自动文摘、关键词自动提取、文本分类和搜索引擎等信息检索领域的各项应用中，取得了较好的效果。 n在向量空间模型中，文档和查询均被看成由索引项构成的向量。例如，对于有个不同 ddttt,(,,,)tkn(1),,jjn12k索引项的系统，文档可以表示成，其中，索引项常常被赋 wk予一个权值来表示它在文档中的重要程度，但这个权值并非像布尔模型的索引项权值那样是二值的，而是根据索引项对文档表示的贡献大小设定的一个大于零的值。在向量空间模 dwww,(,,,)win(1),,tjn12ii型中，一般用向量来表示文档，其中表示索引项的权值。索引项的权值大小是人为赋予的，主观性较强。为了比较客观地反映索引项对文档内容表示 wtfdftfidf,,，/kjkjkkjk的贡献大小，一个典型的确定该权值的方法是运用TF-IDF公式，即。 tfdtdfkjjkk其中，为索引项在文挡中出现的频率，称为索引项频率(term frequency); tdfidfkkk则是文档集D中出现索引项的文档数(document frequency);为的倒数，称为逆文档频率(inverted document frequency)。 尽管实词一般都可以作为索引项，但是众所周知，一个文档中的各个实词在表达文档的含义时，所起的作用是不尽相同的。因此，对一个模型来说，决定一个索引项对文档含义描述的-贡献程度是一个十分重要的问题，要从根本上解决这个问题是比较困难的。目前，人们主要用索引项的一些容易度量和评估的属性来评价其对文献的内容描述的贡献。这主要从两个方面来考量:第一是这个词对描述文档内容的能力大小，这一点在向量空间模型中表现tf为值的大小;其二是这个词区分其所在文档与其他文档的能力，这一点在向量空间模型 idfw中表现为值的大小。对于一个具有多篇文档的文档集，如果一个词在每篇文档中都出 w现，那么用词作索引项对文档与查询之间的相关度计算的贡献就不大，因为它不能体现 ww各个文档的差别。但是，当词只在文档集中很少的几篇中出现，那么用作为索引项就 w非常合适，因为利用它能很好地将包含词的几篇文挡与文档集中的其他文档区分开来。 除此之外，还需要考虑文档长度的影响。通常，长文档相比短文档来说更易被检索出，这将导致短文档被漏检，因而通常还要进行标准化处理。 综上所述，得到一种典型的经过标准化处理后的索引项权值的计算公式为 wtftfNidf,，，/max{}lg{}kjkjkjk (16-29) max()tfdjkjjN式中，表示文档集中的文档个数，是文档中出现频率最高的索引项的频率。 (,)tdij在经典模型中，假设索引项是独立的，或者说是正交的。也就是说，二元组的 ww(,)tdij,mn,mn权值与其他二元组的权值是没有关系的。这个假设极大地简化了索引项权值的计算过程，尽管这一假设有时不符合自然语言的实际情况，但是在这个假设下，计算权值的过程简单快捷，因而在目前很多实用的信息检索模型中被广泛采用。事实上，在自然语言中，有些索引项是相互关联的，比如当在一个文档中看到“计算机”时，就非常有可能同时看到“科学”;而当在一个文档中看到“土豆”时，看到“计算机”的可能性就很小。 在给定了文档和查询的描述后，接下来的问题便是如何看待文档和查询的相关度了。在向量空间模型中，由于查询式和文档都是向量，因而此模型用文档和查询两个向量的相似度来估计文档和查询的相关性。常见的相似度计算方法有内积法和余弦向量度量法等。 1)内积法 qwww,(,,,)1,2,,qqnq内积法是将查询和文档均看成向量时，即和dwww,(,,,)jjjnj1,2,,，可以使用两个向量内积的大小来近似地表示两个向量之间的相关程度，如下式所示 n simdqww(,)(),，,,,jkqkj,1k (16-30) wwdqkq,kj,jkk式中，是查询的第个索引项的权重，是文档的第个索引项的权重。在内积表示法中，向量空间模型直接根据文档向量和查询向量内积的大小对文档进行排序，内积越大，文档与查询的相关度越高。 2) 余弦向量度量法 用内积法表示查询向量和文档向量的相似度时，由于内积值没有界限，因此给相似度的表示和排序带来一定的麻烦，同时会导致在计算相似度时，长文档比短文档更具有优势。而实际上文档的长短与其是否与查询相关是没有必然联系的。为了尽可能减小文档长度这个与相似度无关的因素对相似度数值的影响，人们利用向量长度对内积进行归一化，得到用向量夹角的余弦表示相似度的模型，即余弦向量度量法。事实证明，这种方法比内积表示法的效 dsimdq(,)qjj果更好。在余弦向量度量法中，文档和查询的相似度定义为 n ()ww，,,,kqkj,1ksimdqdq(,)cos(,),,jjnn22ww，,,,,kqkj,,11kk (16-31) wwdqkq,kj,jkk式中，是查询的第个索引项的权重，是文档的第个索引项的权重。在余弦向量度量法中，向量空间模型根据文档向量与查询向量的夹角余弦的大小对文档进行排序，夹角余弦值越大，即两者之间夹角越小，就认为文档与查询相似度越高。 向量空间模型与布尔模型相比具有较大的优势，主要体现在以下方面 : (1)向量空间模型索引项权重的算法提高了检索的性能，改进了检索效果。 (2)向量空间模型采用了部分匹配的策略，使得模型能够检索出与用户查询要求接近的文档，检索的结果文档集更接近用户的检索需求。 (3)向量空间模型采用一定的相似度计算方法，可以根据结果文档与查询式的相似度进行排序，从而有效地控制了返回文档的数量和质量。 但向量空间模型的不足之处在于，在构建向量空间模型时，假设任意索引项之间是相互 wij,独立的，即在考虑索引项权重时并没有考虑其他索引项对它的影响，实际上不符合现实的语言环境。从这一点上来说，向量空间模型无法揭示索引项之间的关系，因而向量空间模型在理论上还是不够完善的。尽管如此，在实际应用中采用独立性假设计算索引项权值还是取得了不错的效果，并且计算量比较小。由于充分利用索引项之间的关联性来计算权值是很困难的，所以可通过查询扩展和相关性反馈等技术，改进查询和文档的表示，来进一步改善向量空间模型的效果。 3.概率模型 概率模型是在布尔逻辑模型的基础上为解决检索中存在的一些不确定性而引入的，它试图在概率论的框架下解决信息检索的问题。概率模型是信息检索的重要模型之一。信息检索过程中具有的不确定性是概率模型应用到信息检索中的重要前提。在概率模型的实际应用中，为了得到模型的参数，不同的模型会有不同的假设条件，通常还会与其他的方法相结合。 信息检索系统内存在很多的不确定性，如对某一信息需求既没有唯一的查询式，也没有明确的定义和判定标准，即文档与查询是否"相关"(文档是否能满足用户的需求)。基于上述原因，Maron和Kuhns在1960年提出了第一概率检索模型;1976年Robertson和Sparck Jones等在此基础上进行改进提出了第二概率检索模型;之后，Turtle、Fuhr和Roberston又提出了统一化模型，即第三概率检索模型，提高了文献的排序精度。 第二概率模型针对给定的一个用户查询，假设存在一个理想文挡集R，它只是包括完全相关的文档而不包括其他不相关的文档。这样，信息检索的过程可以被看成是描述理想文档集的过程，把查询处理看作是对理想结果文档集属性的处理。当然，并不能确切地知道这些属性到底是什么，只知道能够利用索引项来刻画这些属性。 dqj概率模型基于以下理论:给定一个用户的查询式和文档集合中的文档的概率模型 dqj来估计用户查询与文档相关的概率。同时，概率模型基于如下假设: dqj(1)文档与一个查询式的相关性和文档集合中的其他文档是没有关系的，这称为概率模型的相关性独立原则。 (2)在文档和查询中的索引项权重都是二元的。 (3)文挡相关性是二值的，即只有相关和不相关两种。也就是说，一篇文档要么属于理想文档集，要么不属于理想文档集。 正是由于这些假设，概率模型也称为二值独立检索模型(BIR，Binary Independent Retrivel)。 dsimdq(,)qjj下面给出概率模型的定义。将文档和查询式的相似度定义为文档与查 dsimdq(,)qjj询相关的概率和文档与查询不相关概率的比值。文档和查询式的相似度计算公式为 PRd(|)jsimdq(,),jPRd(|)j (16-32) PRd(|)dqjjR式中，R表示相关文档集合，表示不相关文挡的集合，表示文档与查询式相 PRd(|)dqjj关的概率，表示文档与查询式不相关的概率。 simdq(,)dqjj与其他模型类似，概率信息检索的目的是估计，即文档对检索式来说 被用户判断为相关的概率。基于概率模型的检索过程如下: dwww,{,,,}jjjnj1,2,,n首先，将文挡看成二值向量，即，其中是所有索引项的个数。 wwdtij,ij,ji如果文挡中出现相应索引项，则=1，反之=0。然后，针对每一篇文挡计算 PRd(|)PRd(|)PRd(|)qjjj和来决定它是否与查询相关。由于无法直接估计和 PRd(|)j的值，因此要用己知的量来进行估计。相关文档集合R可以由初始的猜测得到，则 PRd(|)PRd(|)PR()PR()jj概率模型中和以及和是可计算的，因此根据贝叶斯公式 PabPbaPaPb(|)(|)()/(),,可以得到 PdRPR(|)(),PdRPR(|)(),jj以及 PRd(|),PRd(|),jjPd()Pd()jj 将其带入式(16-32)得到 PdRPR(|)(),jsimdq(,),jPdRPR(|)(),j (16-33) PR()PR()式中，和表示从整个文档集合中随机选取一篇文档是否与查询相关的先验概率。 对于一个确定的文档集来说，这两个先验概率仅与查询有关，而与具体的文挡无关(即对 ,dPR()PR()qj，和均相同)，由于只关心所有文档与查询的相似度的相对大小，所以将 式(16-33))进一步简化可得 PdR(|)jsimdq(,),jPdR(|)j (16-34) 根据索引项之间的独立性假设，用每个词在相关文档集合和不相关文档集合的分布情况 dPdR(|)jjRR来计算它们的相关概率，从相关文档集合或中随机选取文档的概率 和 PdR(|)j的定义为 n()(1()),gdgdijijPdRPtRPtR(|)(|)(|),,jii,1i (16-35) n()(1()),gdgdijijPdRPtRPtR(|)(|)(|),,jii,1i (16-36) gdww(){0,1},，,ijijiq,,n式中，，为所有索引项的个数。式(16-35)和式(16-36)可以这 dgdww(){0,1},，,jijijiq,,样理解:当索引项在查询和文档中同时出现，即=1时，用索引tiR项在相关文档集合中的某篇文档中随机出现的概率来作为其对判断查询与文档是否相 dtjiR关的贡献;反之，索引项不同时出现在查询和文档中时，用索引项不在相关集合中出现的概率来作为其对判断查询和文档是否相关的贡献。将式(16-35)和式(16-36)代入式(16-34)可得 ngdgd()(1()),ijijPtRPtR(|)(|),iii,1,simdq(|)jngdgd()(1()),ijijPtRPtR(|)(|),iii,1 (16-37) PtR(|)PtRPtR(|)(|)，PtR(|)PtR(|)PtR(|)iiiiii以及的定义，有=1，相应地根据和由 PtRPtR(|)(|)1，,ii的定义有，将两者带入式(16-37)，并且两边取对数可以得到 nnPtRPtRPtR(|)(1(|))1(|),,,iiisimdqgd(,)()lglg,，,,jijPtRPtRPtR(|)(1(|))1(|),,,,,11iiiii (16-38) nn1(|),PtR1(|),PtRiilglg,,d1(|),PtR1(|),PtR,1,1jiiii在式(16-38)中，与文档无关，对所有文档来说，的值都是一样的，相似度排序只关心不同文档与查询相似度的相对大小，这样与文档无关的常量可以省略。因此，式(16-38)可以进一步简化为 nPtRPtR(|)(1(|)),,iisimdqgd(,)()lg,,jijPtRPtR(|)(1(|)),,,1iii (16-39) 这就是概率模型中用于计算文档和查询相似度的公式。 概率模型的优点主要包括: (1)有严格的数学理论基础。概率模型的文档与查询相似度值计算公式以严格的数学理论以及严格的推导为依据获得的，因此概率模型为人们提供了一种进行检索决策的数学理论基础。 (2)概率模型可以采用相关反馈原理，可开发出理论上更为可靠的方法。 (3)概率模型中没有用到对用户的查询技术要求比较高的布尔逻辑方法，同时可以将文档按照它们相关概率的递减顺序排序。 概率模型的缺点主要包括: (1)在模型中假设索引项的权值是二值的，没有考虑不同索引项在文档和查询中的不同权重，这个假设产生的问题在布尔模型中已经作了说明。 (2)需要在开始之前就将文档分成相关文档集合和不相关文档集合，这往往给用户带来 很大困难或者区分准确度很低。 4.扩展布尔模型 扩展布尔模型通过建立数学模型来表示布尔逻辑和通过加权机制改进索引项的权值两个方面对布尔模型进行改进。 1 )基本模糊集合模型 布尔模型的理论基础是布尔逻辑和经典集合论。扩展布尔模型的改进之一，就是采用模糊集合论作为理论基础，用函数计算代替布尔逻辑计算。 dw(01),,wttij,jij,ii令索引项在文档中的权值为 ，在查询中出现的索引项的权值wwwiq,iq,ij,为。在这个模型中，可以认为=。当索引项权值退化为0或1时，模糊检索模型与传统检索的布尔模型是完全兼容的。对于一个标准布尔系统，可以用赋值表来处理表达式;对于一个包含多个运算符的检索式，可先处理深层的检索子式，再逐层递归处理。布尔检索 dj的检索式与文档相似度计算公式如表16-1所示。 dj表16-1 布尔检索的检索式与文档相似度计算公式 布尔检索式 赋值公式 (d， and ) min{,}ww simttjmjnj,,mn ww, mjnj,, (d， or ) max{,}ww simttjmjnj,,mn wwww，,, mjnjmjnj,,,, (d， and not ) ww,,(1) simttjmjnj,,mn 2)扩展模糊集合模型 在基本模糊集合模型中，没有对查询式中的检索词赋予权值，而是假设查询中的索引项权值和文档中的索引项权值相等。扩展模糊集合模型针对这一点进行了改进，为文档中的词和检索式中的词赋予了不同的权值。 在向量空间模型中，查询和文档都采用同一种结构表示，所以没有必要区分查询索引项和文档索引项。但是在布尔模型和模糊模型中，查询的结构化要求区分查询索引项和文档索引项的赋值过程。在布尔模型中，给查询索引项赋权值，必须保留布尔模型的特性: (1)兼容性，指与查询索引项赋值为0或1时的结果兼容。 ttttttt1231323(2)一致性，指查询式(or) and 与查询式(or ) and (and)检索出相同的文档。 (3)独立性，指对查询式进行分段处理，不会影响整个查询式的检索结构。 一种有效的方式是将查询索引项的权值与文档索引项的权值相乘，即 wwsimdtww(,),，tid,iq,iidiq,,i，其中和分别表示索引项在文档和查询中的权值，simdt(,)tdii表示当查询只有索引项时，查询和文档的相似度。 5.统计语言模型 统计语言模型 (Statistical Language Mode，SLM)试图通过统计学和概率论理论对自然语言进行建摸，从而获取自然语言中的规律和特性，以解决语言信息处理中的特定问题。 语言(或者说文档)就是字母表上的某种概率分布，该分布反映了任何一个字母序列成为该语言的一个句子(或其他任何语言单元)的可能性，这个概率分布称为语言模型(language Ssss,,,,n12nmodel)。对于任何一个句子 (其中为句子的长度)，将生成句子的过程看成一个马尔可夫过程，则其在文档集合中出现的概率为 n PSPsssPssss()(,,,)(|,,),,,12121,iii,1i (16-40) 有了这个定义之后，如何根据给定的数据集(训练语料库)来估计概率Pssss(|,,)ii121,就成为统计语言模型中的关键问题。由于不可能有足够的数据来估计Pssss(|,,)ii121,，因此根据马尔可夫假设，可得到n元模型(n-gram模型)，即认为一个词的出现与否仅仅与其前面的n-l个词有关，即 PssssPssss(|,,,)(|,,),iiiiiin121121,,,,, (16-41) PssssPssPs(|,,,)(|)(),,niiiii121,当=1时，，这时的模型称为一元语言模型(unigram)。它假设各个词之间是相互独立的，即一个词出现的概率与其他词无关。 PssssPss(|,,,)(|),niiii1211,,当=2时，，这时的模型称为二元语言模型(bigram)。它假设索引项出现的概率仅与其前一个词出现的概率有关。 PssssPsss(|,,,)(|,),niiiii12112,,,当=3时，，这时的模型称为三元语言模型(trigram)。它假设索引项出现的概率仅与其前两个词出现的概率有关。 基于统计语言模型的检索模型的基本思想是对于每一篇观察到的文档，假设其对应着一个语言模型，并根据这篇观察到的文档估计这个语言模型。同时假设检索的过程就是由文档的语言模型产生查询的过程。在这个过程中，计算语言模型生成查询的概率成为基于语言模 PDQ(|)PDQ(|)型的检索模型的核心，即检索最感兴趣的文档，在上使用贝叶斯法则，并略去对文档排序不造成影响的因素，得到 PDQPQDPD(|)(|)(), (16-42) PD()PQD(|)QD式中，是一篇文档符合查询的先验概率，刻画了在给定文档时，查询生 QDD符合给定的查询的程度(即文档与给成的可能性。实际上这个概率也就揭示了文档 Q定的查询的相似度)。 PD()显示了利用先验概率来改善查询的效果的可行性，比如可以考虑从文档的内部结构、对文档在整个网络中所处的链接环境分析等获得先验概率的知识。假设这先验概率对文档集合中的所有文档都是相同的，于是得到的基于语言模型的检索模型为 ，，，，PDQ,PwD,w,Q (16-43) 从表面上看，基于统计语言模型的检索模型与传统的向盘空间模型非常不同它比较简单，仅仅利用了词的频率信息，然而在实验中确有很好的效果。 基于统计语言模型的信息检索模型的优缺点包括: 与传统的向量空间模型相比，基于统计语言模型的信息检索模型取得了较好的检索效果(基于统计语言模型的信息检索模型由于具备数 学理论基础坚实，概念模型简洁井且在实际测评中相对于传统的向量空间模 型也确实获得了更好 的检索效果等特点，近年 逐渐引起研究人员的注意。目前，基于统计语言模型的信息检索模型已经成为信息检索 研究的一个新方向。改进的基于统计语言模型的信息检索棋型也不断涌现，如触发语言 模型和基于主题语 言模型等(但其主流 的思想都是将 自然语言处理中的技术〈如词义消 歧、句法分析和指代消解等〉引入到统计语言模型中，以提高检索效果。 同时，统计语言模型也存在一些需要进一步研究与解决的问题。在统计语 言模型中， 由于将查询看作是由文档模型抽样生成的样本，因此，对于传统的信息检索模型中使用 的查询扩展技术，无法在该模型中找到充分的理论根据。 目前用于信息检索的统计语言模型基本上还只限于n-gram 的线性词汇统计棋型，这 只是单词级别上的检索。因此，利用加入了句法的结构化统计语言模型进行信息检索将 是一个可行的研究方向。 6.潜在语义索引模型 自然语言文本中的词汇〈术语〉具有一词多义(polysemy)和一义多词(synonmy )的特点。只用索引项来表示查询和文档时，由于一词多义， 基于精确匹配的检索算法会 返回许多与用户查询不相关的文档 :由于一义多词，基于精确匹配的检索算法又会遗漏 许多与用户查询相关的文档。 为解决上述问题，以Bellcore和Dumais为首的研究小组提出了一种称为潜在语义索 引(LSI，Latent Semantic Indexing)的模型，该模型试图绕过自然语言理解，用统计的办法达到既反映术语间内在的相关性又改善检索效果的目的。 LSI被证明是一种比在Salton的SMART系统中使用的传统向量空间技术性能更好的信息 检索向量空间技术。 潜在语义索引模型原理如下所述。 X首先，以索引项为行、文档为列形成一个大矩阵，设矩阵名为。 ddtX假设文档集合中索引项个数为 t，文档个数为为，则矩阵共有 行 列，矩阵 xxtdi,ji,jii为索引项在文档中出现的频度，有时还加入了索引项的权重。索引项的的元素 权重说明了所有索引项在语义空间中的重要性是不相同的。定义索引项权重的原则是，识别文档与语义能力强的索引项的权重高于识别能力弱的索引项，目前定义索引项权重的方法包 -idf方法、term熵(entropy)方法、微软提出的Okapi方法等。由于任意一个文括传统的tf X档总是由有限个词汇组成，不大可能会有文档集中出现所有t个索引项，所以必是一个稀 TDTSD0000X疏矩阵。根据奇异值分解定理，矩阵可以分解为三个矩阵、、 (的转置〉的积，即 TX,TSD000 (16-44) TDTSTDr，d0t，r0000r，r式中，为矩阵，为对角矩阵，为矩阵。其中和的列向量都是 Xr正交归一化的，是矩阵的秩。 S0,k,r0取正整数k，，在中，仅考虑其中值最大的k个奇异值〈即对表达文档含义 TDST000kkkk贡献最大的前个词〉，取中相应的阶对角矩阵、中相应的列、中相应的行， TSk，kk，dt，rDT最终得到新的矩阵(阵〉、(对角矩阵〉和(阵)。然后，进行奇异 , X值分解反运算，得到新矩阵，即 ,TX,TSD (16-45) ,, XXTD式中，即为经过优化的语义结构矩阵，为索引项矩阵，为文挡矩阵。奇妙的是， XT在最小二乘意义下是的最佳近似。这样，实际上得到了一个“降维”的途径。根据矩阵 SkDTD和，可以得到索引项及文挡在维语义空间内的坐标向量。下面要说明、、三个矩阵在文档检索中的重要应用价值。 XX给定矩阵，基于可以提出以下三类与文档检索密切相关的问题: ttji(1)索引项与有多相似,即索引项的类比和聚类问题。 ddji(2)文档与有多相似,即文挡的类比和聚类问题。 dtji(3)索引项与文档有多相似,即文档与索引项的匹配问题。 ,, XX得到后，可以用来进行这三类比较。下面说明具体的比较过程。 1)比较两个索引项 首先做“正向”乘法，即 ,,TTTT2XXTSDDSTTST，,，，，，，,，， (16-46) TjiD，D,I因为D是正交归一的，所以，所得新矩阵的第行第列元素值的大小表明了索ttii引项与文档的相似程度。 2)比较两个文件 做“逆向”乘法，即 ,,TTTT2XXDSTTSDDSD，,，，，，，,，， (16-47) TjiT，T,IT因为也是正交归一的，所以，所得新矩阵的第行第列元素值的大小表明了 ddji文档与的相似程度。 3)比较一个文件与一个索引项 ,jiX所有文档与索引项的相似度大小矩阵恰巧就是本身，它的第行第列元素值大小表 dtji明了索引项与文档的相似程度。 利用潜在语义索引模型进行信息检索的过程如下: q首先用户为了获得自己需要的文挡，提交查询。传统的基于关键词的用户查询必须是 分离的索引项序列，而潜在语义索引模型允许用户提交自然语言形式的查询。在处理查询时， 与对文档的处理一样，潜在语义索引根据用户查询式中各词汇的出现频率生成查询式向量 qqqii，中第个元素的数值表示第个索引项在查询中出现的次数。由于前面已经对索引 qX项一文档矩阵进行了截断奇异值分解，因此对于也要进行类似处理，使其可以与文档 qD矩阵进行比较。用下式对进行处理，即 T,1D,qTSq (16-48) Dqqk式中，即为查询式在维语义空间内的坐标向量。词汇、文本、查询式三者的坐标向 DqD量构成了所需的潜在语义空间。得到了查询式的坐标向量后，与文档矩阵的每一个行 ddjj向量进行比较。就可分别计算出每篇文档与查询式的相关程度，最简单常用的方法是计算两者之间的夹角余弦值，余弦值越大(即两个向量的夹角越小)，相似度就越大。将该相似度计算方法运用到LSI中，根据下式来计算每篇文档与查询式的相似度 k qt.,,iij,1i,,simdqCdq,,，，，，jjkk22qt，，，，,,,iij,,11ii (16-49) T，，dCdq，，q,q,...,qqj,jkk12k为查询向量在维空间内的坐标向量与某文档向量在式中， T(d,d,...,d)1,2,,jjkj维空间内的坐标向量之间的夹角余弦。 对所有丈档都计算与查询的相似度值〈即文档向量与查询向量的夹角余弦值)并进行排 SSminmin序之后，设定一个阈值，将所有相似度大于等于的文档返回，便可产生一个满足用户要求的检索结果文挡集。通过设置不同的阈值，可以调整返回文档的数量和文档与用户查询相似度的大小。 潜在语义索引模型的特点如下: (1)在潜在语义索引模型中，实际上是将高维语义空间中的文档向量(索引项向量)投影到低维语义空间的潜在语义空间中，达到将原来在高维语义空间中比较稀疏的向量压缩到潜在语义空间中不再稀疏的向量。即使两个文档原来没有共同索引项(或索引项完全不同)，在潜在语义索引模型中仍然可能找到它们之间比较有意义的关联值。 (2)潜在语义索引模型是一种全新的半智能型模型，相对于传统的索引项匹配法，它是对旧有信息检索模型的一种改革。目前，它仍处于发展阶段 ，国内外的许多学者都在研究、开发和改善它。潜在语义索引模型在专业领域的检索方法上的效果尤其突出，一些信息检索系统也己采用潜在语义索引模型进行工作，如互联网化学资源导航系统(ChIN，The Chemical Information Network，)等。 多数情况下，潜在语义索引模型的性能要好于向量空间模型，它适用于词汇异度较高的文档集合。然而，从应用的角度来说，潜在语义索引模型计算量太大，并且目前潜在语义索 k引模型的理论基础还不是很完善。例如，潜在语义空间维数的取值主要依靠人的经验和实际检验来确定，文档长度如何选取直接影响潜在语义提取以及再现语义的效果，目前也只能依赖经验而定。此外，由于中文信息的特殊性，潜在语义检索模型在中文信息检索中的效果不如在英文中的好，把潜在语义检索模型成功地应用于中文信息检索，还需要大量的研究。 16.4 统计语言模型在拼音输入法中的应用 进入新千年以后，诞生了许多“智能”拼音输入法，其特点主要是输入的基本单位从字跨越到词甚至到词组，这时拼音输入法突然变得“聪明”起来，输入很长的拼音串可以一次转换成型，而且错误较少，大大提高了中文使用者的工作效率。 照统计的方式，可以把输入法的数学模型表示为，输入一串拼音字符(py)，求得最按 大概率的汉字串(hz)，即 argmax(P(hz)|P(py)) 进一步用贝叶斯公式展开可以得到 argmax(P(hz)|P(py)),argmax(P(hz)*P(py|hz)) 其中，P(hz)的部分就是前文所描述的语言模型部分;而P(py|hz)由于汉字的词条多音现象非常有限，在一般意义上可以认为近似为1。这样拼音输入法实际上成为了一个纯粹的语言模型应用场景。理论上讲，只要把所有的词汇选择出来，之后使用N-gram模型来打分，选择出概率值最高的一条路径作为输出即可。 下面举例说明语言模型在输入法中的实际作用。 16.4.1解码器 从所有可能的组合中选择合适的组合方式，可以视为一种解码器的任务。拼音输入法也是一个解码器。 例如，当用户输入wohenfanganta时(很大的可能是要输入“我很反感他”)，输入法会将整个词汇网络构建出来(在此省略拼音网络拆分等环节)，如图1所示。 图1 输入法构建的词汇网络 音节的拆分是一个有限的集合，将整个拼音串横向的切分;而每个音节所能表达的字符串是有限集合，将每个音节纵向的扩展，这样就形成一张二维的网络。其中每条从起点到终 点的路径都可以视为解码器的一个解，而输入法所要做的是从中选择一条最符合语言概率模型的路径。 如果每条路径都是无差别的，那么就退化成为第一代拼音输入法，每个节点都挑选第一个词即可，而把挑选的任务交给用户，效率很低。 人们一般不会说“很×”这种话，按照统计的语言表达就是说“(很，方案)”这个二元组的出现概率相当低，可以在网络中给予一定程度的削弱;而“(很，反感)”这种二元组出现的概率很高，应当提升该条路径的权重。也就是每条路径权重的高低其实就代表着两个词之间的二元关系的强弱，把二元关系标注之后，整个网络如图2所示。 图2 二元关系标注后的网络 这样就将问题转化为带权有向图的最短路径求解问题。借助viterbi算法可以快速得出最优路径为“ 我-很-反感-他”。 最优路径选择越符合输入者意图，则越能体现输入法的智能性，也能根本反映背后语言模型的精确程度。因此输入法的准确率是语言模型好坏的一个天然指标。 16.4.2调频 按照局部约束的性质，每个当前输入都应该与其紧邻的上一个输入具有很大的相互关系。 例如，用户的daxue的音串，可以取得“大学”和“大雪”“打血”等多个解码串，在没有上文的条件下，这里倾向于利用一元模型给出“大学” 的首选项。而换一种环境，假设用户之前选择了“漫天”这个词条，那么此时的候选排序应当与“漫天”发生某种对应关系，可以使用二元模型来描述这种影响，即P(大学|漫天) 和 P(大雪|漫天)来做比较。很显然“漫天大雪”的可能性要高于“漫天大学”，因此在这种情况下倾向于“大雪”位于首选的位置。 目前，用户输入长度依然较短，对于单词、短语的调频需求还是很高，采用调频技术可以减少用户翻页选择的成本，提升工作效率。 16.4.3 N-gram模型的扩展 1.主题性假设 N-gram模型反映的是一种局部相关特性，但很多时候词汇也需要符合主体性的特征。 在一定的语境中，人们会反复输入一些主题词汇。比如在和朋友聊天的过程中，假设共 同关注的好友名叫“沃德”，那么在反复使用的过程中，在输入wode这个拼音串时，就期望“沃德”的排名能够高于通用的“我的”等词汇，这种需求单使用N-gram模型不好解释，这时引入Cache模型，即 P(hz),,P(hz)，(1,,)P(hz)mcache 其中，plm为之前介绍的语言模型;而pcache表示也是语言模型，但其采样的样本是用户近期输入的历史;λ为插值系数(λ?(0,1))。 这样虽然在通用模型的得分上“我的”高于“沃德”，但由于有cache模型的参与，使得“沃德”的unigram得分较高，从而可以得到一个调整。至于偏向于通用模型还是cache模型，则取决于用户输入的历史长度等方面的可靠性考虑，反映在模型上就是λ得分的高低。 2.长距离依存假设 任何语言都有一种固定搭配现象，如中文的“在……内”“除……之外”，这种语言现象反映的其实是一种句法结构。然而由于句法分析的准确性依然较低，直接利用句法分析的结果可行程度不高，而且非常耗时。可以发现这种句式结构虽然突破了局部性约束，但却符合高频的特征，因此依然采用N元模型的统计方法。由于统计的是具有跨越性质的二元对，姑且把这种二元对叫做触发对(trigger)，认为后一个词的出现不仅取决于前N-1个词条，也可能被前面较长距离的词条触发，由此将公式改变为 P(hz),,P(hz)，,P，,P(hz) bnbncachecachetriggertrigger 以式(2.1)不同的地方是加入了trigger模型的参与，其中各λ之和为1。 有了trigger模型，那么在输入“在”之后，会启动所有与“在”相关的触发对集合，一旦后面的词汇命中集合就会给予trigger模型的加分，从而得到较高的评分。 在不同的应用中，统计语言模型的变形还有很多种，以弥补N-gram局部约束性质的不足。 本章 1.了解什么是语言模型,常用的语言模型有哪些, 统计语言模型， 简称语言模型，来自于基于统计方法的自然语言处理系统的研究中，如语音识别系统、字符识别系统和机器翻译等。语言模型就是表示语言的基本单位(词、词组或句子等)的分布函数，它描述了该语言的基于统计的生成规则，常用的语言模型有n-gram模型、决策树语言模型(Decision Tree Model)和最大熵模型(Maximum Entropy Model)。。 2.模型估计的方法及原理,采用的平滑技术及原理, 在语言模型中最为重要的就是如何估计概率分布。假设文档为unigram模型，则 。估计的最简单的方法就是最大似然估计，即，，Pt|d，，，，PQ|D,d,Pt|dii,t,Qi 。然而由于数据稀疏问题，即查询词可能不包含在文档中时，最，，，，，，Pt|d,fttftMLii,t 大似然估计方法就无法处理。传统的解决办法是采取平滑技术，如Good-Turing，additive-smoothing，Katz-smoothing等等。信息检索经常采用的方法有Jelinek-Mercer、Dirichlet smoothing和Absolut discount smoothing，这些方法的基本思想都是利用文档集合估计的概率，来平滑最大似然估计。 3.什么是信息检索,信息检索的三个基本问题是什么, 信息检索一般可以看成由三个基本问题构成:用户需求表达，文档内容表达，用户需求和文档匹配方式。不同的模型对这三个问题有着不同的解决办法和侧重点，如布尔模型侧重于结构化查询， 向量空间模型侧重于权重计算，概率模型侧重于利用相关性文档估计权重。而基于语言模型的信息检索系统则在解决上述三个问题的同时，也将如结构化查询、语义查询扩展、相关性反馈等与信息检索相关的技术统一在一个理论框架下，这是其它检索模型无法比拟的。 4.信息检索常用的方法及其原理是什么, (1)布尔模型:布尔模型是信息检索中第一个被提出的模型，它主要侧重于结构化查询表达式，即通过AND、OR 和NOT构造查询表达式，反映用户的需求，并通过精确匹配来返回文档。 (2)概率模型:概率模型基于词在同查询相关文档集合和不相关文档集合中的分布是不同的这样一个前提。然而该模型在应用中遇到非常难以解决的问题，就是概率估计问题。概率模型在估计概率时需要有文档相关性的先验知识，而这往往很难得到，解决的方法是往往是人为地设定一个经验值作为初值，然后利用用户的相关性反馈来重新估计概率。 (3)向量空间模型:向量空间模型是目前最为流行的信息检索模型之一。该模型主要描述了如何定义特征词的权重和匹配方式。 (4)语言模型:来自于基于统计方法的自然语言处理系统的研究中，如语音识别系统、字符识别系统和机器翻译等。语言模型就是表示语言的基本单位(词、词组或句子等)的分布函数，它描述了该语言的基于统计的生成规则，常用的语言模型有N元模型(n-gram Model)、决策树语言模型(Decision Tree Model)和最大熵模型(Maximum Entropy Model) 16.6 习题与思考题 1.信息检索(IR)领域的模型有哪些,简述几种常用语言模型及应用, 2.信息检索的三个基本问题是() (A)用户需求表达，文档内容表达，文档内容的扩充 (B)用户需求表达，文档内容的扩充，用户需求和文档匹配方式 (C)用户需求表达，文档内容表达，用户需求和文档匹配方式 (D)文档内容表达，文档内容的扩充，用户需求和文档匹配方式 3.简述模型估计的方法、原理及平滑技术, 4.简述几种常用的检索模型及特点，比较语言模型与其他模型的优劣势, 参考文献 [1] Graff D，The 1996 broadcast news speech and language-model corpus.Slides from lecture at the 1997 DARPA Speech Recognition Workshop，Feb.1997 [2] Rosenfeld R，A maximum entropy approach to adaptive statistical language modeling，Computer Speech and Language，1996.10:187~228 [3] Katz S M，Estimation of probabilities from sparse data for the language model component of speech recognizes，IEEE Transaction on Acoustics，Speech and Signal Processing，1987.ASSP-35:400~401 [4] Jelinek F，Mercer R L，Interpolated estimation of Markov source parameters from sparse data，In;Proc， of the Workshop on Pat-tern Recognition in Practice，Amsterdam， The Netherlands:North-Holland，May 1980.381~397 [5] Magerman D M， Natural Language Pausing as Statistical Pattern Recognition; [ PhD Thesis]，Stanford University，1994 [6] Bahl L R.Brown P F，De Souza P V，Mercer R L，A tree-based statistical language model for natural language speech recognition，IEEE Transactions on Acoustics .Speech，and Signal Processing，1989，37(7):1001~1008 [7] Rosenfeld R， Adaptive Statistical Language Modeling;r1 Maxi-mum Entropy Approach:[PhD thesis，Carnegie Mellon University .1994， CMU Technical Report CMU-CS-94-138 [8] Darroch J，Ratcliff D，Generalized iterative scaling for log-linear models， The annals of Mathematical statistics 1972.I3:1470~1480 [9] Berger A L.Della Pietra S A，Della Pietra V J，A maximum entropy approach to natural language processing，Computational Linguistics 1996.22(1):39~71 [10] Rosenfeld R，Two decades of Statistical Language Modeling:Where Do We Go From Here? Proceedings of the IEEE，2000.88(8) [11] 刘挺，秦兵，张宇，等.信息检索系统导论[M].北京:机械工业出版社，2008.