国科大现代信息检索第二次作业.docx

国科大2013年秋季现代信息检索第二次作业(第六章到第十五章)以下1-16每题6分，第17题3分，共计100分。1. 习题 6-10考虑图6-9中的3篇文档Doc1、Doc2、Doc3中几个词项的tf情况，采用图6-8中的idf值来计算所有词项car、auto、insurance及best的tf-idf值。Doc1Doc2Doc3car27424auto3330insurance033329best14017图6-9习题 6-10中所使用的tf值car在三篇文档中的tf-idf值分别：Doc1:27*1.65=44.55；Doc2:4*1.65=6.6；Doc3:24*1.65=39.6auto在三篇文档中的tf-idf值分别为：Doc1:3*2.08=6.24；33*2.08=68.64；0*2.08=0insurance在三篇文档中的tf-idf值分别为：Doc1:0*1.62=0；33*1.62=53.46；29*1.62=46.98best在三篇文档中的tf-idf值分别为：Doc1:14*1.5=21；0*1.5=0；17*1.5=25.52. 习题 6-15回到习题6-10中的tf-idf权重计算，试计算采用欧氏归一化方式处理后的文档向量，其中每个向量有4维，每维对应一个词项。Doc1=(44.55,6.24,0,21)， Len(Doc1)=49.6451对其长度归一化得到Doc1=（0.897，0.126，0，0.423）Doc2=（6.6,68.64,53.46,0），Len（Doc2）=87.2524对其长度归一化得到Doc2=（0.076，0.787，0.613，0）Doc3=（39.6,0,46.98,25.5），Len（Doc3）=66.5247对其长度归一化得到Doc3=（0.595，0，0.706，0.383）3. 习题 6-19计算查询digital cameras及文档digital cameras and video cameras的向量空间相似度并将结果填入表6-1的空列中。假定N=10 000 000，对查询及文档中的词项权重（wf对应的列）采用对数方法计算，查询的权重计算采用idf，而文档归一化采用余弦相似度计算。将 and 看成是停用词。请在tf列中给出词项的出现频率，并计算出最后的相似度结果。表6-1习题6-19中的余弦相似度计算词查询文档tfwfdfidfqi=wf-idftfwfdi=归一化的wfdigital1110 00033110.521.56video00100 00020110.520cameras1150 0002.3012.30121.3010.6771.558相似度结果=1.56+1.558=3.1184. 习题 7-1图7-2中倒排记录表均按照静态得分g(d)的降序排列，为什么不采用升序排列？一篇文档d的最后得分定义为g(d)和某个与查询相关的得分的某种组合，一些文档具有高的g(d)值更有可能具有较大的最后得分，降序排列有助于提高top-k检索的效率。在这种排序下，高分文档更可能在倒排记录表遍历的前期出现。在实际受限的应用当中（比如，任意搜索需要在50ms内返回结果），上述方式可以提前结束倒排记录表的遍历。5. 习题 7-8平面上的最近邻问题如下：在平面上给出N个数据点并将它们预处理成某种数据结构，给定查询点Q，在N个点中寻找与Q具有最短欧氏距离的点。很显然，如果我们希望能够避免计算Q和所有平面上的点的距离时，簇剪枝就能够作为最近邻问题的一种处理方法。请给出一个简单的例子来说明： 如果只选择最近的两个先导者，那么簇剪枝方法可能会返回错误的结果（也就是说返回的不是离Q最近的数据点）。l1l2l3如图所示，黄色圈代表查询，离查询最近的两个先导者为l1,l2，但是离查询最近的文档是红色圈代表的，不属于l1,l2，属于离查询较远的先导者l3，因此离查询最近的文档不会被返回。6. 习题 8-5 *正确率和召回率之间是否一定存在等值点？说明为什么一定存在或给出反例。如果返回的相关文档数（RR）=0，正确率=召回率=0。如果返回的不相关的文档（RN）=未返回的相关文档（NR），正确率也等于召回率。如果一篇文档都不返回，正确率=1，召回率=0；如果返回全部的文档，正确率=相关文档数/总文档数，召回率=1。假设返回的文档中排名靠前的都是相关文档，那么随着返回文档数的增加，RN由0变为N-相关文档数，且中间每一个值都能取到，NR由总共相关文档数变为0，同样能取到中间的每一个值。RN从小变大，NR从大变小看，中间有一个相等的情况，这时候召回率=正确率。7. 习题 8-8 *考虑一个有4篇相关文档的信息需求，考察两个系统的前10个检索结果（左边的结果排名靠前），相关性判定的情况如下所示：系统1 R N R N N N N N R R系统2 N R N N R R R N N Na. 计算两个系统的MAP值并比较大小。MAP(系统1)=(1/4)*(1+2/3+3/9+4/10)=0.6MAP(系统2)=(1/4)*(1/2+2/5+3/6+4/7)=0.493由于只有一个查询，MAP=AP。系统1的MAP值更大b. 上述结果直观上看有意义吗？能否从中得出启发如何才能获得高的MAP得分？系统1返回的相关文档位置较分离，有的在前面有的在后面，系统2返回的相关文档较集中的中间位置。系统1获得了较高的MAP值。排名前面位置的相关文档数对MAP值的影响较大，相关文档排在靠前的位置可以获得较高的MAP得分。c. 计算两个系统的R正确性值，并与a中按照MAP进行排序的结果进行对比。R正确率（系统1）=2/4=0.5R正确率（系统2）=1/4=0.25虽然R正确率只度量了正确率-召回率曲线上的一个点，但是经验上却证实它和MAP是高度相关的。按照R正确率和MAP排序得到的结果一致。8. 习题 9-3假定用户的初始查询是cheap CDs cheap DVDs extremely cheap CDs。用户查看了两篇文档d1 和 d2，并对这两篇文档进行了判断：包含内容CDs cheap software cheap CDs的文档d1为相关文档，而内容为cheap thrills DVDs 的文档d2为不相关文档。假设直接使用词项的频率作为权重 （不进行归一化也不加上文档频率因子），也不对向量进行长度归一化。采用公式（9-3）进行Rocchio相关反馈，请问修改后的查询向量是多少？其中 = 1， = 0.75， = 0.25。qm=q0+1|Dr|djDrdj-1|Dnr|djDnrdj词项频率表格词原始查询d1d2CDs220cheap321DVDs101extremely100software010thrills001修改后的查询向量q=(2.5,4.25,0.75,1,0.75,-0.25)，如果向量中权重分量为负值，那么该分量权重设为0。所以最终Rocchio向量为（2.5，4.25，0.75，1，0.75，0）9. 习题 11-3 *令Xt表示词项t在文档中出现与否的随机变量。假定文档集中有|R|篇相关文档，所有文档中有s篇文档包含词项t，即在这s篇文档中Xt=1。假定所观察到的数据就是这些Xt在文档中的分布情况。请证明采用MLE估计方法对参数进行估计的结果，即使得观察数据概率最大化的参数值为 pt = s/ |R|。设D是相关文档集，定义一个函数PDR=1=tDPdR=1=pts(1-pt)|R|-sP(D|R=1)pt=spts-1(1-pt)|R|-s-pts(R-s)(1-pt)|R|-s-1令P(D|R=1)pt=0，得到pt=s/|R|10. 习题12-6 *考虑从如下训练文本中构造LM： the martian has landed on the latin pop sensation ricky martin请问：a. 在采用MLE估计的一元概率模型中，P(the)和P(martian)分别是多少？P(the) = 2/11 = 0.181818182P(martian) = 1/11 = 0.090909091b. 在采用MLE估计的二元概率模型中，P(sensation|pop)和 P(pop|the)的概率是多少？P(sensation|pop) = 1P(pop|the) = 011. 习题 12-7 *假定某文档集由如下4篇文档组成：文档ID文档文本1234click go the shears boys click click clickclick clickmetal heremetal shears click here为该文档集建立一个查询似然模型。假定采用文档语言模型和文档集语言模型的混合模型，权重均为0.5。采用MLE来估计两个一元模型。 计算在查询click、shears以及click shears下每篇文档模型对应的概率，并利用这些概率来对返回的文档排序。将这些概率填在下表中。对于查询 click shears来说，最后得到的文档次序如何？查询似然模型：clickgotheshearsboysmetalhere模型11/21/81/81/81/800模型21000000模型3000001/21/2模型41/4001/401/41/4文档集模型7/161/161/162/161/162/162/16每篇文档模型对应的概率为：querydoc1doc2doc3doc4clickshearsclick shears15/322/1615/25623/321/1623/5127/321/167/51211/323/1633/512查询 click shears的文档排序为：doc4,doc1,doc2,doc312. 习题 13-1对于表13-2，为什么在绝大部分文本集中|C|V| |D|Lave都成立？假设大多数文档集的词条数都大于100万，根据Heaps定律，词汇表大小V是文档集规模T的一个函数，V=K*Tb，典型的K=44，b=0.49，V=K*Tb=44*(1000000)0.5=44000|D|Ld=文档集中的词条数=1000000，|C|V|=2*44000=88000所以大多数文档集有|C|V|D|Ld13. 习题 13-2 *表13-5中的文档中，对于如下的两种模型表示，哪些文档具有相同的模型表示？哪些文档具有不同的模型表示？对于不同的表示进行描述。(i) 贝努利模型。(ii) 多项式模型。 表13-5NB独立性假设存在问题的几个文档例子(1) He moved from London, Ontario, to London, England.(2) He moved from London, England, to London, Ontario.(3) He moved from England to London, Ontario.(i) 贝努利模型：三个文档具有相同的模型表示。(ii) 多项式模型：文档(1)(2)相同，与文档3不同。文档(1)(2)中London都出现了两次，文档(3)中London只出现了一次。14. 习题 13-5考虑Reuters-RCV1语料前100 000篇文档中4个词项在类别coffee中的出现频率。词项N00N01N10N11brazil98 0121021 83551council96 3321333 52520producers98 5241191 32334roasted99 8241432310根据(i) (ii) 互信息及 (iii) 频率的值，从上述4个词项中选出2个词项。(i) 对于brazil：E11=N*p(t)*p(c)=(51+1835)*(51+102)/100000=2.8856E00=N*(1-p(t)*(1-p(c)=(98012+102)*(98012+1835)/100000=97963.8856E01=N*(1-p(t)*p(c)=(98012+102)*(51+102)/100000=150.1144E10=N*p(t)*(1-p(c)=(1835+51)*(98012+1835)/100000=1883.1144X2D,t,c=et0,1ec0,1(Netec-Eetec)2Eetec =(98012-97963.8856)2/97963.8856 +(102-150.1144)2/150.1144 +(1835-1883.1144)2/1883.1144 +(51-2.8856)2/2.8856 =818.939对于council：X2(D,t,c)=40.336E00=(96332+133)*(96332+3525)/100000=96327.0551E01=(96332+133)*(133+20)/100000=147.5915E10=(3525+20)*(96332+3525)/100000=3539.9307E11=(133+20)*(3525+20)/100000=5.4239对于producers：X2D,t,c=N*(N11*N00-N01N10)2(N11+N01)(N11+N10)(N00+N01)(N00+N10)=498.375对于roasted：X2(D,t,c)=1964.293X2值越大意味着独立性假设不成立，选出brazil和roasted。(ii) 互信息brazil:IU;C=N11Nlog2NN11N1.N.1+N01Nlog2NN01N0.N.1+N10Nlog2NN10N1.N.0+N00Nlog2NN00N0.N.0 =0.0015537council:IU;C=96322100000log2100000*9632296322+13396322+3525+96322100000log2100000*9632296322+13396322+3525 + 96322100000log2100000*96322(96322+133)(96322+3525) +96322100000log2100000*96322(96322+133)(96322+3525) =0.0001774producers:I(U;C)=0.0009689roasted:I(U;C)=0.0006485互信息度量的是词项是否被类别包含所带来的信息量，选出brazil和producers。(iii)频率的值brazil:51/(51+102)=0.3333council:20/(20+133)=0.1307prodecers:34/(34+119)=0.2222roasted:10/(10+143)=0.0654选择在类别中频率较高的词项作为特征，选出brazil和producers。15. 习题 14-2*试举例说明，如果采用Rocchio分类方法对训练文档分类，那么分类结果有可能会不同于训练集上的结果。平面上有两类文档，一类分布于半径为1的圆圈内，另一类分布于半径为10的圆圈内，两个圆圈有交集。按照Rocchio分类方法，半径为10的圆圈中的文档将有很多被分类为半径为1的圆圈内。16. 习题 14-4试证明两个类别间的线性分类器的数目要么是无穷的，要么是0。如果存在一个线性分类器，那么把它沿着最近点对的方向移动一个很小的距离后仍然为一个线性分类器。17. 习题15-3 *安装某个SVM包，比如SVMlight （/），对例15-1建立一个SVM分类器。请确认程序会给出与文中一样的结果。对于SVMlight或者其他包来说，训练数据格式是一样的，它们的