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

国科大在2013年秋季第现代信息检索次工作(第6章至第15章)以下每1-16题6分，第17题3分，合计100分。考虑到图6-9的文档Doc1、Doc2和Doc3中的某些单词的tf状况，使用图6-8中的idf值来计算所有单词car、auto、insurance和best的tf-idf值。Doc1Doc2Doc3car公司27424自动(自动)3330insurance033329最好的14017图6-9练习6-10中使用的tf值在三个car文档中，tf-idf值为Doc2:4*1.65=6.6，其中Doc1:27*1.65=44.55； Doc3:24*1.65=39.6auto三个文档中的tf-idf值为33*2.08=68.64，其中Doc1:3*2.08=6.24； 0*2.08=0insurance三份文件的tf-idf值为33*1.62=53.46，其中Doc1:0*1.62=0； 29*1.62=46.98在best为3个文档中，tf-idf值分别为Doc1:14*1.5=21，即0*1.5=0； 17*1.5=25.52 .练习题6-15返回练习题6-10的tf-idf权重计算，尝试计算用欧几里得正则化方式处理的文本向量。 其中，每个向量有4维，每个维对应1个词句。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和视频cameras的向量空间相似度，并将结果填入表6-1的空栏。 假设n=10000，以对数形式计算查询和文档中的单词的权重(对应于wf的列)，以idf计算查询的权重，以及以馀弦相似度计算文档的归一化。 把and看作无效词。 请在tf列中给出单词的出现频率，计算最后的相似度结果。表6-1练习题6-19中馀弦相似度计算语言查询文件tf世界棒球锦标赛dfidfqi=wf-idftf世界棒球锦标赛di=标准化wf数字电视1110 00033110.521.56视频00100 00020110.520cameras公司1150 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 *件相关文件的信息需求，考察两个系统的前10件检索结果(左边的结果为上位)，相关判定的情况如下系统1 R N R N N N N N R R系统2NRNRNRNNa .计算两个系统的MAP值并比较大小。MAP (系统1)=(1/4)*(1/3/9/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.25r正解率只测定了正解率再现率曲线上的1点，经验证明与MAP有很高的相关性。 r正解率与MAP排序所得结果一致。8 .练习9-3假设用户的第一个查询是cheapcdscheapdvdsextremelycheapcds。 用户查看两个文档d1和d2以确定这两个文档。 包含内容CDs检查软件检查CDs的文档d1是相关文档，而包含内容cheap thrills DVDs的文档d2不是相关文档。 将单词项目的频度直接作为权重使用(既不标准化也不附加文件频度系数)，不标准化矢量的长度。 用公式(9-3)进行关于Rocchio的反馈，修改的查询向量是多少，其中=1，=0.75，=0.25。QM=Q01|dr|DJdrdj -1|dnr|DJdnrldj语句频率表语言原始查询d1.d1d2.d2CDs220cheap公司321DVDs101extremely100软件公司010惊险001如果向量的权重分量为负值，则修改后的查询向量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 *是表示语句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 *考虑从以下训练文本构建LMthemartianhaslandedonthelatinpopsensingrickymartin请问a .用mle估计的一维概率模型，P(the )和P(martian )分别是多少？P(the)=2/11=0。P(martian)=1/11=0b .用mle估计的二元概率模型中，p(sensitivation|pop )和P(pop|the )的概率是多少？p (感测| pop )=1P(pop|the)=011 .练习12-7假设某个文档集由以下四个文档组成文档ID文档文本1234clickgotheshearsboysclickclickclick键metalun梅塔西亚clickhere建立此文档集的查询似然性模型。 假设使用文档语言模型和文档集语言模型的混合模型的权重均为0.5。 用MLE估计两个一维模型。 查询click、shears和click shears计算每个文档模型的概率，并使用这些概率对返回的文档进行排序。 把这些概率记入下表。 查询click shears时，最后获得的文档顺序如何查询似然性模型：克里克go！ go！theshears男孩元这里型号11/21/81/81/81/800型号21000000型号3000001/21/2型号41/4001/401/41/4文档集模型7/161/161/162/161/162/162/16与每个文档模型相对应的概率如下：querydoc1doc2doc3doc4克里克shearsclick shears15/322/1615/25623/321/1623/5127/321/167/51211/323/1633/512搜索click shears的文档按doc4、doc1、doc2和doc3进行排序12 .对于练习题13-1表13-2，为什么大部分文本集合|C|V| |D|Lave成立？假设许多文档集的词条数超过100万，根据Heaps定律，词汇表尺寸v是文档集尺寸t的函数，V=K*Tb，典型的K=44，b=0.49，V=K*Tb=44*()0.5=44000|D|Ld=文档集中的词条数=，|C|V|=2*44000=88000因此，大多数文档集是|C|V|D|Ld13 .练习题13-2 *在表13-5的文档中，对于以下两个模型表示，哪个文档具有相同的模型表示？ 哪个文档的模型表达方式不同？ 对不同的表现进行记述。(I )贝努利模型。(ii )多项式模型。表13-5 NB独立性假设存在问题的几个文档示例(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)中只出现过2次London，文件(3)中只出现过1次London。14 .练习题13-5考虑Reuters-rcv 1资料前100万份文件中的4个单词在类别coffee中的出现频率。语句N00N01N10N11系列brazil公司98 0121021 83551council96 3321333 52520producers98 5241191 32334roadsted公司99 8241432310(I )根据(ii )相互信息以及(iii )频度的值，从上述4个单词中选出2个单词。(I )对于brazil :E1=n * p (t ) * p (c )=(511835 ) * (51102 )/=2.8856e00=n * (1- p (t ) ) * (1- p (c ) )=(98012 ) * (980121835 )/=97963.8856 )e01=n * (1- p (t ) ) * p (c )=(98012 ) * (51102 )/=150.1144E10=n * p (t ) * (1- p (c ) )=(1835 ) * (9898021835 )/1883.1144X2D，t，c=et 0，1 EC 0，1 (netec-ee