向量空间模型课件.ppt

《向量空间模型课件.ppt》由会员分享，可在线阅读，更多相关《向量空间模型课件.ppt（67页珍藏版）》请在三一办公上搜索。

1、网络信息内容安全讲义/张华平/2010-10,向量空间模型,向量空间模型是最常用的检索模型（Salton等人，1975年）思想：文章的语义通过所使用的词语来表达方法:每一篇文档用一个向量来表达，查询用一个向量来表达，通过向量的方式来计算相似度。,网络信息内容安全讲义/张华平/2010-10,向量空间模型,网络信息内容安全讲义/张华平/2010-10,向量空间模型,主要涉及两方面的工作：（1）如何构建一个向量来表示文档中 的词项，构建另一个向量来表示查询中的词项.（2）如何来度量任意文档向量和查询向量的相似度,网络信息内容安全讲义/张华平/2010-10,向量空间模型 构建向量,对于文档集中每一

2、个不同的词项（或概念），我们在向量中只记录一个分量。当词项出现时，就在对应向量的分量处记1；如果词项未出现，就在对应的分量处记0。,网络信息内容安全讲义/张华平/2010-10,向量空间模型 构建向量,文档：,D1,D3,D2,Q,A,A,I,I,A,I,文档向量：,D2=,D3=,Q=,D1=,D1,Q,x,y,1,D2,D3,1,网络信息内容安全讲义/张华平/2010-10,二值表示方法并没有考虑一个词项在文档中出现的次数。通过扩展这种表示形式，我们将词项在文档中出现的频率作为向量中各个分量的值。在上例中，如果文档D2中A出现了两次，向量可以表示为。,向量空间模型 构建向量,网络信息内容安

3、全讲义/张华平/2010-10,除了简单地给出查询词列表外，用户通常还会给出权重，该权重表示一个词项比另外一个词项更重要。思想：不频繁出现的词的权重应该比频繁出现的词的权重更高。方法：人工赋值在初始查询中用户人工指定词 项权重来实现的。自动赋值通过基于词项在整个文档集中 出现的频率。,向量空间模型 构建向量,网络信息内容安全讲义/张华平/2010-10,向量空间模型 构建向量,我们采用稍大一些的例子来展示如何使用基于数据集频率的权重。t文档集中不同词项的个数。词项tj在文档Di中出现的次数，也就是词频。包含词项tj的文档的篇数。，其中d表示所有文档的篇数。这就是逆文档频率。,网络信息内容安全讲

4、义/张华平/2010-10,对于每一篇文档向量，都有n个分量。向量中的每个分量为在整个文档集中计算出来的每个词项的权重。在每篇文档中，词项权重基于词项在整个文档集中出现的频率情况以及词项在某一个特定文档中出现的频率自动赋值。,向量空间模型 构建向量,网络信息内容安全讲义/张华平/2010-10,向量空间模型 构建向量,对于文档中词项的权重因素，主要综合考虑词频和逆文档频率。文档i对应的向量中第j个词条的值：查询Q和文档Di的相似度可以简单地定义为两个向量的内积。,网络信息内容安全讲义/张华平/2010-10,Q：“gold silver truck”D1：“Shipment of gold d

5、amaged in a fire”D2：“Delivery of silver arrived in a silver truck”D3：“Shipment of gold arrived in a truck”在这个文档集中，d=3。lg(d/dfi)=lg(3/1)=0.477 lg(d/dfi)=lg(3/2)=0.176 lg(d/dfi)=lg(3/3)=0,向量空间模型 构建向量（举例）,网络信息内容安全讲义/张华平/2010-10,三篇文档的每个词项的IDF值如下所示：idfa=0 idfin=0 idfarrived=0.176 idfof=0 idfdamaged=0.477

6、 idfsilver=0.477 idfdelivery=0.477 Idfshipment=0.17615 idffire=0.477 idftruck=0.176 idfgold=0.176,向量空间模型 构建向量（举例）,网络信息内容安全讲义/张华平/2010-10,向量空间模型 构建向量（举例）,网络信息内容安全讲义/张华平/2010-10,向量空间模型 倒排索引,网络信息内容安全讲义/张华平/2010-10,向量空间模型 构建向量,新问题：在已知的查询和文档中，词频很高的匹配词项淹没了其他匹配词项的效果。为了避免这种现象，科研人员提出使用lg(tf)+1来缩小词频的范围。新的权重：,

7、网络信息内容安全讲义/张华平/2010-10,基于该思想的修订版本是在查询和文档中的词项使用不同的权重。lnc.ltc词项权重计算模式非常有效。标签lnc.ltc是如下形式：qqq.ddd，其中qqq指查询权重，ddd指文档权重。这三个字母：qqq或ddd是xyz的形式。,向量空间模型 构建向量,网络信息内容安全讲义/张华平/2010-10,向量空间模型 构建向量,第一个字母x可以是n、l或a。n表示原始词频或指tf。l表示通过取对数来降低权重，所以可以使用1+lg(tf)。a表示加强权重，所以权重为:第二个字母y表示是否使用idf。n表示不使用idf，t表示使用idf。第三个字母z表示是否使

8、用文档长度归一化。通过归一化文档长度，我们试着减小检索中文档长度的影响（见公式2-1）。在文献Singhal,1997中，n表示不使用归一化，c表示使用标准的余弦归一化，u表示使用临界点长度（pivoted length）归一化。,网络信息内容安全讲义/张华平/2010-10,向量空间模型 相似度,文档向量：查询向量：(1)内积（Inner Product）问题：通过内积方法，一个比较长的文档可能会得到一个比较高的分数，仅仅因为文档比较长，因此有更多的机会包含查询词并不一定因为文档是相关的。,网络信息内容安全讲义/张华平/2010-10,向量空间模型 相似度,(2)余弦(Cosine)条件假设

9、：余弦方法中假定文档长度对查询没有影响。余弦方法通过将向量内积除以文档向量的长度来实现不同文档长度的归一化。除以文档向量长度就是不考虑文档长度。,网络信息内容安全讲义/张华平/2010-10,向量空间模型 相似度,Dice系数：Jaccard系数：,网络信息内容安全讲义/张华平/2010-10,然而这种简单的假设是不正确的（至少对于TREC数据）。拿50个TREC查询集所有查找到的相关文档来说，Singhal发现实际上在长文档集中更多文档被判断为相关的Singhal，1997。原因可能是长文档仅仅是有更多的机会包含那些与给定查询确实相关的词项。,向量空间模型 相似度,网络信息内容安全讲义/张华

10、平/2010-10,向量空间模型 相似度,(3)临界点余弦（Pivoted Cosine）,网络信息内容安全讲义/张华平/2010-10,向量空间模型 相似度,相似度为：这种方法有两个变量：分别为斜率s和临界点p。我们也有可能将斜率s表示为临界点的函数。Singhal在纠正和调整相应的斜率之前，将整个文档集上统计计算出来的平均归一化因子选定为临界点。同时，将归一化因子除以(1.0-s)p。,网络信息内容安全讲义/张华平/2010-10,向量空间模型 相似度,计算相似度的等式如下：（2-1）其中avgn是在任何纠正前的平均文档归一化因子，s值凭经验得到。临界点模式对于短文档和中等长度的文档还算有

11、成效，但是与归一化前相比，整个算法会更有利于特别长的文档。,网络信息内容安全讲义/张华平/2010-10,向量空间模型 相似度,最后一种调整是针对在特别长文档中出现的词频特别高的情况。首先，使用1+lg来限制词频。为了应对长文档，将每个词项权重除以平均词项权重。新的权重dij为：使用新权重，并且除以调整因子的新公式如下：(2-2),网络信息内容安全讲义/张华平/2010-10,向量空间模型 相似度,然后我们计算给定文档集中每篇文档的词项的平均数量，并且将其作为临界点p。一旦计算完成，就可以使用文档集就上训练出一个很好的斜率。公式（2-2）被称为临界点唯一归一化（pivoted unique n

12、ormalization）。实验表明，在公式（2-1）临界点余弦归一化的基础上检索效果得到了提高。修改后的归一化因子使得更可能检索到长文档，并且对于TREC查询，性能可以提高10%。,网络信息内容安全讲义/张华平/2010-10,概率检索模型 Probabilistic Retrieval Model,网络信息内容安全讲义/张华平/2010-10,概率模型,概率模型通过计算文档与查询相关的概率来作为文档和查询的相似度。这就使相关性排序问题降为概率论应用问题。起源思想：基于一个词项分别在相关文档和不相关文档中出现的频率来估计该词项的权重。条件：独立性假设 词项间是独立的方法：查询中的词项可以看做

13、文档相关的指示器。经过观察，我们发现词项A同时在文档和查询中出现时，文档相关的概率为x%。这样我们就为词项A赋值这个概率。所有权重的乘积是文档相关的概率。,网络信息内容安全讲义/张华平/2010-10,简单词项权重,估计给定词项在相关文档中的概率假设D1和D2是相关文档，D3、D4和D5是非相关文档词项t1使文档Dj相关的概率：,网络信息内容安全讲义/张华平/2010-10,给定一篇文档di，它包含t个词项(w1,w2,wt)对于文档中一个已知的词项，它对估计整篇文档相关的贡献可以计算为：文档di相关的权重或者“可能性”基于文档中每个词项相关的概率。基于已知的独立性假设，我们可以将文档中每个词

14、项出现的概率相乘来得到文档相关的概率，最后将乘积取对数：,简单词项权重,网络信息内容安全讲义/张华平/2010-10,两个相互排斥的独立性假设：Robertson和Spark Jones，1976 I1：词项在相关文档中的分布是独立的并且在所有文档中的分布是独立的。I2：词项在相关文档中的分布是独立的并且它们在非相关文档中的分布也是独立的。排序原则：O1：相关的可能性仅仅基于文档中出现的查询词项。O2：相关的可能性基于文档中出现的查询词项和未出现的查询词项。,简单词项权重,网络信息内容安全讲义/张华平/2010-10,在不同的排序原则和独立性假设的组合下，可以得出4种权重。给出一个词项t，考虑

15、以下变量：N文档集中文档的数量；R对于已知查询q对应的相关文档的数量；n包含词项t的文档数目；r包含词项t的相关文档数目。选择I1和O1组合：,简单词项权重,网络信息内容安全讲义/张华平/2010-10,选择I2和O1组合：选择I1和O2组合：选择I2和O2组合：,简单词项权重,网络信息内容安全讲义/张华平/2010-10,当使用不完整的相关性信息时，由于估计相关性的不确实性，我们将权重都加0.5，新的权重公式为：,简单词项权重,网络信息内容安全讲义/张华平/2010-10,Q：“gold silver truck”D1：“Shipment of gold damaged in a fire.

16、”D2：“Delivery of silver arrived in a silver truck.”D3：“Shipment of gold arrived in a truck.”我们假定这三篇文档是训练数据，并且认为文档D2和文档D3与该查询相关。为了计算相似度，首先计算出查询词项的权重，然后计算出匹配词项的权重的和。,简单词项权重举例,网络信息内容安全讲义/张华平/2010-10,简单词项权重举例,每个查询词项的频率 使用以上公式进行计算，我们得出以下权重：gold：,网络信息内容安全讲义/张华平/2010-10,silver：truck：,简单词项权重举例,网络信息内容安全讲义/张华

17、平/2010-10,简单词项权重举例,词项权重 文档权重,网络信息内容安全讲义/张华平/2010-10,实验结果：第三种权重和第四种权重的性能相当，但是优于第一种权重和第二种权重。科研人员在UKCIS文档集（包含27 361篇文档）上研究第一种权重和第四种权重衡量方式上的不同Sparck Jones，1979a。研究发现，使用第四种权重性能提高很多。研究者还使用了其他两组对比实验。第一组只是简单地依据匹配词项的个数排序，第二组使用IDF来估计权重。实验表明，这些方法都次于这四种权重的任何一种，但是使用IDF比简单地使用匹配词项的频率要好一些。在所有的情况中，文档的排序为D2,D3,D1,简单词

18、项权重,网络信息内容安全讲义/张华平/2010-10,简单词项权重,问题：原始概率模型并没有引入词频和文档长度，其效果还不如向量空间模型。引入词频:在原始的概率模型中并没有使用词频。Croft和Harper在概率模型中引入了词频Croft和Harper，1979。相关度是通过词项在一篇给定文档中出现的概率来估计的，而不是简单地看词项在文章中出现与否。新的相似度:,网络信息内容安全讲义/张华平/2010-10,P(dij)表示词项i在文档j中出现的概率，并且可以只通过词项i在文档j中出现的频率来估计。归一化词频可以通过下式计算：引入词频后的效果：Croft和Harper在克兰菲尔德文档集和NPL

19、文档集的11 429篇文档上比较了归一化后的词频、未归一化的词频和一个未使用词频的对比系统。和对比系统相比，实验结果表明，使用归一化词频后的系统效果有统计性的显著提升。在大多数情况下，未归一化词频的系统比对比系统的效果还要差。,简单词项权重,网络信息内容安全讲义/张华平/2010-10,非二值独立模型（Non-Binary Independence Model）,思想：在词项权重计算中引入了词频和文档长度Yu等人，1989。一旦计算出词项权重，就可以使用向量空间模型计算内积来获得最终的相似度。方法：权重为词项在相关文档中出现tf次与词项在非相关文档中出现tf次的比率，公式如下：P(di|R)表

20、示相关文档中第i个词项的出现频率为di的概率，P(di|N)表示非相关文档中第i个词项的出现频率为di的概率。,网络信息内容安全讲义/张华平/2010-10,非二值独立模型举例,Q：“gold silver truck”D1：“Shipment of gold damaged in a fire.”D2：“Delivery of silver arrived in a silver truck.”D3：“Shipment of gold arrived in a truck.”词项到文档的映射表,网络信息内容安全讲义/张华平/2010-10,非二值独立模型举例,因此，我们有三篇文档和一个查询，

21、总共11个词.我们假设文档2和文档3是相关的，文档1是不相关的.通过文档长度进行归一化后，如下表：归一化文档长度,网络信息内容安全讲义/张华平/2010-10,我们没有对查询进行归一化。查询中出现的词项是：“gold”、“silver”和“truck”。对于文档D1,“gold”的权重是：对于D1中的“silver”，我们得到：我们可以通过这种方法来计算文档中每个词项的权重和已知词频的权重。我们可以构造出对应向量，然后以此计算查询和每个文档的相似度。,非二值独立模型举例,网络信息内容安全讲义/张华平/2010-10,泊松模型,Robertson和Walker研究出一种使用泊松分布来估计相关性概

22、率，并且引入了词频和文档长度的概率模型 Robertson和Walker，1994。我们使用ptf来引入词频。已知相关性下，ptf表示词频为tf的词出现的概率，qtf表示对应的非相关的概率。下标0表示未出现的词项。权重计算为：研究人员假定：词在文档中随机出现，且符合泊松分布：,网络信息内容安全讲义/张华平/2010-10,泊松模型,当前文档所阐述的语义内容是否与查询词所表示的概念相同？参数m随着不同的语义情况而变化。这导致权重计算如下：式中与词t有关的文档的泊松分布参数；与词t无关的文档的泊松分布参数；j；已知词t相关的文档是相关文档的概率；与已知词t无关的文档是不相关文档的概率。,网络信息内

23、容安全讲义/张华平/2010-10,这种权重计算的难点在于如何在实际中应用：实际应用中并没有关于4个参数、和 的直接依据。为了引入词频，我们使用以下函数：其中w是标准概率权重；k1是未知常量，它的值取决于文档集，并且通过实验获取。该模型同样考虑了文档长度。考虑文档长度因素最简单的方法是修改上式中的w，可以使用如下公式替换：,泊松模型,网络信息内容安全讲义/张华平/2010-10,式中d 文档长度；文档平均长度。这样计算w的公式变为：另外一个参数k3用来衡量查询词频的效果（qtf）。最后，我们引入另外一比例因子k2，可以更好地逼近二元泊松分布估计。k2如下所示：,泊松模型,网络信息内容安全讲义/

24、张华平/2010-10,其中k2是一个通过实验确定的常量，|Q|是查询词项的个数。这一项允许k2为很高的值来加强比平均长度短的文档的权重。将这些修改应用于相似度后，就是：式中 N 文档集中文档的数量；n 文档集中通过一个已知词索引的文档数量；R 对于查询相关的文档数量；r 给定词索引的相关文档数量；,泊松模型,网络信息内容安全讲义/张华平/2010-10,tfij文档i中词j的词频；qtfj查询Q中词j的词频；dli文档i中词的数量；|Q|查询中词的数量；平均文档长度；k1,k2,k3调节参数。问题1：k1和k3取较小的值可能会削弱文档词频和查询词频的影响。k1和k3取较大的值会明显削弱第一项

25、的大小。,泊松模型,网络信息内容安全讲义/张华平/2010-10,措施：分子中引入k1+1和k3+1的因子对全局排序并不起作用。然而这确实允许给k1和k3赋很大的值而不会削减第一项的权重。此外，这样可以归一化调节参数。其思想为：当词频为1时，就没有必要改变原始的权重。问题2：如果仅仅是因为文档长，它给出了关于主题更加具体的细节，那么这是明智的。在这种情况下，长文档的权重不应该比短文档的大。然而，文档长的原因可能是它讨论了更多无关的主题。在这种情况下，长文档就应该受到惩罚。措施：新的调节参数b可以基于文档集的性质调节查询。这个参数是在涉及tfij的因子通过用K代替k1引入的，那么：,泊松模型,网

26、络信息内容安全讲义/张华平/2010-10,泊松模型,引入调节参数b。并在分子上加入k1+1和k3+1后：在Robertson等人，1995的实验中，这些值分别为k1=1，k2=0，k3=8，b=0.6。,网络信息内容安全讲义/张华平/2010-10,同样使用前文中的例子，我们首先计算w4为：gold=-0.477 silver=0.477 truck=1.176 avgdl=22/3=7.33使用同样的参数k1，k2，k3，b，我们计算dli的值：dl1=7 dl2=8 dl3=7对于D1，唯一匹配查询的是“gold”，其出现的词频tf=1，因此D1的相似度仅仅是“gold”的值（D1的长度

27、dl是7）。,泊松模型,网络信息内容安全讲义/张华平/2010-10,泊松模型,对于文档D2，匹配查询的词项“silver”和“truck”的和为非零值。对于“silver”，tf12=2：,网络信息内容安全讲义/张华平/2010-10,泊松模型,对于“truck”，tf22=1：对于D3，dl=7，所以K=0.973（同D1）。两个词“gold”和“truck”都出现了一次。对于“gold”，tf13=1。,网络信息内容安全讲义/张华平/2010-10,对于“truck”，tf23=1。通过表2-7，我们再次对比考虑词频的相似度和不考虑词频的相似度，排序结果同样是D2,D3,D1。泊松模型：

28、最终的相似度,泊松模型,网络信息内容安全讲义/张华平/2010-10,文档片段,思想：一篇文档可以划分成多个段落，并且每一个段落都可以计算相似度。一旦计算完每一个段落的相似度，就需要有种方法来综合每个段落的相似度，从而对整篇文档排序。把给定片段的基本权重定义为片段相关的概率与片段无关的概率的比值，也就是：rak和sak可以通过以下三种方式的任意一种来计算。,网络信息内容安全讲义/张华平/2010-10,(1)使用自相关来初始化参数 一个片段与其自身相关，结果是：其中La是文档集中片段的数量，Fk是词项k在文档集中出现的次数。Nw是文档集中不同片段的个数。(2)逆文档集词频（ICTF）在整个文档

29、集中，词频比较低的词的sik值就比较小。假定rak的最初估值比较差，并且仅仅指定为常量p。使用常量rak导致整个权重大约等于sik。,文档片段,网络信息内容安全讲义/张华平/2010-10,文档片段,sik是从整个文档集的估计值中去除一篇相关文档dik后计算出来的。也就是通过使用与假定的“相关文档”相匹配的词的数量dik来计算。sik的计算公式如下：在我们的权重计算中，使用参数p得出下面的权重，这个权重与IDF非常接近：,网络信息内容安全讲义/张华平/2010-10,文档片段,(3)综合策略 以查询为中心时，查询是已知的，所有的权重都是以与查询的相关性计算的。在求出每一片段的权重后，使用几何平

30、均来计算。这就使权重变为：以文档为中心的计算方法是计算查询的每一个片段，然后分别计算与文档的相关性权重，再取平均值。计算如下：,网络信息内容安全讲义/张华平/2010-10,接下来我们考虑综合策略。综合策略只是以查询为中心的权重和以文档为中心的策略之和。公式如下：结果：片段理论与基于词项的查询效果相当，并且在相关反馈下效果更好。综合以查询为中心和以文档为中心的计算方法优于分别使用以查询为中心的计算方法和以文档为中心的计算方法。,文档片段,网络信息内容安全讲义/张华平/2010-10,概率模型的关键问题,通常，概率模型必须设法解决两个基本问题：参数估计和独立性假设。参数估计 系统中可以使用余弦值

31、来进行初始的排序，然后使用概率权重进行相关 反馈。我们假设（没有任何相关信息）每个词引起相关的概率是相等的。式中N 文档集中文档的数量；ni 词i索引的文档的数量；dij 若词i在文档j中出现，则该值为1；dij 若词i在文档j中未出现，则该值为0；qi 若词i在查询中出现；则该值为1；qi 若词i在查询中未出现，则该值为0。,网络信息内容安全讲义/张华平/2010-10,C是常量，可以根据检索的不同而调节。在大的文档集上，词项权重 非常接近逆文档频率（N取较大值）。因此，整个表达式 非常接近在向量空间模型中使用的tf-idf。结果：作者比较了这种方法计算的相似度，还有余弦系数和只通过每个词项

32、的IDF求和得到的权重系数。新的相似度的效果要更好，但是值得注意的是，作者仅仅是在较小的克兰菲尔德文档集上做的测试。问题：在某些情况下，Croft和Harper的权重计算模式将导致负权重。,概率模型的关键问题,网络信息内容安全讲义/张华平/2010-10,Robertson和Walker提出了新的公式：式中 R 相关文档的数量；r 通过已知词索引的相关文档数量；S 不相关的文档数量；s 包含已知词的不相关文档的数量；k4,k5,k6调节常量，其中k40。,概率模型的关键问题,网络信息内容安全讲义/张华平/2010-10,公式前两项给出了根据相关性信息计算的权重，后两项给出了根据非相关性信息计算的权重。k4的值表示查询词的优劣程度，k5和k6分别表示对相关性信息和非相关性信息的敏感度。2.独立性假设 通过简单地综合文档中的词项概率来计算整篇文档的相关概率的关键前提是词项的独立性假设。因为这是一个错误的假设，所以有研究人员认为这是一个“错误的理论”Cooper，1991。其实推理网络和逻辑回归法都是用来解决独立性假设问题的，这些将分别在2.4节和3.5节进行详细讨论。,概率模型的关键问题,网络信息内容安全讲义/张华平/2010-10,The endThank you!,