《国科大现代信息检索第二次作业》由会员分享,可在线阅读,更多相关《国科大现代信息检索第二次作业(5页珍藏版)》请在金锄头文库上搜索。
1、国科大 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 值。Doc1 Doc2 Doc3car 27 4 24auto 3 33 0insurance 0 33 29best 14 0 17图 6-9习题 6-10 中所使用的 tf 值car 在三篇文档中的 tf-idf 值分别:Doc1:2
2、7*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 权 重 计 算 , 试 计 算 采 用 欧 氏
3、归 一 化 方 式 处 理 后 的 文 档 向 量 ,其 中 每个向量有 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. 习 题
4、6-19 计 算 查 询 digital cameras 及 文 档 digital cameras and video cameras 的 向 量 空 间 相 似 度并 将 结 果填入表 6-1 的空列中。假定 N=10 000 000,对查询及文档中的词项权重(wf 对应的列)采用对数方法计算,查询的权重计算采用 idf,而文档归一化采用余弦相似度计算。将 and 看成是停用词。请在 tf列中给出词项的出现频率,并计算出最后的相似度结果。表6-1习题6-19中的余弦相似度计算查询 文档词tf wf df idf qi=wf-idf tf wf di=归一化的wf iqddigital 1
5、1 10 000 3 3 1 1 0.52 1.56video 0 0 100 000 2 0 1 1 0.52 0cameras 1 1 50 000 2.301 2.301 2 1.301 0.677 1.558相似度结果=1.56+1.558=3.1184. 习题 7-1图 7-2 中倒排记录表均按照静态得分 g(d)的降序排列,为什么不采用升序排列?一篇文档 d 的最后得分定义为 g(d)和某个与查询相关的得分的某种组合,一些文档具有高的 g(d)值更有可能具有较大的最后得分,降序排列有助于提高 top-k 检索的效率。在这种排序下,高分文档更可能在倒排记录表遍历的前期出现。在实际受限
6、的应用当中(比如,任意搜索需要在 50ms 内返回结果) ,上述方式可以提前结束倒排记录表的遍历。5. 习题 7-8平 面 上 的 最 近 邻 问 题 如 下 : 在 平 面 上 给 出 N 个 数 据 点 并 将 它 们 预 处 理 成 某 种 数 据 结 构 ,给 定查询点 Q,在 N 个点中寻找与 Q 具有最短欧氏距离的点。很显然,如果我们希望能够避免计算 Q 和所有平面上的点的距离时,簇剪枝就能够作为最近邻问题的一种处理方法。请给出一个简单的例子来说明:如果只选择最近的两个先导者,那么簇剪枝方法可能会返回错误的结果(也就是说返回的不是离 Q 最近的数据点) 。如图所示,黄色圈代表查询,
7、离查询最近的两个先导者为 l1,l2,但是离查询最近的文档是红色圈代表的,不属于 l1,l2,属于离查询较远的先导者l3,因此离查询最近的文档不会被返回。3l1 l2l36. 习题 8-5 *正确率和召回率之间是否一定存在等值点?说明为什么一定存在或给出反例。如果返回的相关文档数(RR)=0,正确率=召回率=0。如果返回的不相关的文档( RN)=未返回的相关文档(NR),正确率也等于召回率。如果一篇文档都不返回,正确率 =1,召回率=0;如果返回全部的文档,正确率=相关文档数/总文档数,召回率 =1。假设返回的文档中排名靠前的都是相关文档,那么随着返回文档数的增加,RN 由 0 变为 N-相关
8、文档数,且中间每一个值都能取到,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.49
9、3由于只有一个查询,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 正确率只度量了正确率-召回率曲线上的一个点,但
10、是经验上却证实它和 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 相关反馈,请问修改后的查询
11、向量是多少?其中 = 1, = 0.75, = 0.25。=0+1| 1|词 原始查询 d1 d2CDs 2 2 0cheap 3 2 1DVDs 1 0 1extremely 1 0 0software 0 1 0词项频率表格thrills 0 0 1修改后的查询向量 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 在 文 档 中 出 现 与 否 的 随 机 变 量 。 假 定 文 档 集 中 有
12、 |R|篇 相 关 文 档 ,所 有 文档中有 s 篇文档包含词项 t,即在这 s 篇文档中 Xt=1。假定所观察到的数据就是这些 Xt在文档中的分布情况。请证明采用 MLE 估计方法对参数 进行估计的结果,即使得观察数据概(1|,)tpRq率最大化的参数值为 pt = s/ |R|。设 D 是相关文档集,定义一个函数 (=1)=(=1)=(1)|(|=1) =1(1)|(|)(1)|1令 ,得到(|=1) =0 =/|10. 习题 12-6 *考虑从如下训练文本中构造 LM: the martian has landed on the latin pop sensation ricky ma
13、rtin请问: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 click
14、metal heremetal shears click here为该文档集建立一个查询似然模型。假定采用文档语言模型和文档集语言模型的混合模型,权重均为0.5。采用 MLE 来估计两个一元模型。 计算在查询 click、s hears 以及 click shears 下每篇文档模型对应的概率,并利用这些概率来对返回的文档排序。将这些概率填在下表中。对于查询 click shears 来说,最后得到的文档次序如何?查询似然模型:click go the shears boys metal here模型1 1/2 1/8 1/8 1/8 1/8 0 0模型2 1 0 0 0 0 0 0模型3 0
15、 0 0 0 0 1/2 1/2模型4 1/4 0 0 1/4 0 1/4 1/4文档集模型 7/16 1/16 1/16 2/16 1/16 2/16 2/16每篇文档模型对应的概率为:query doc1 doc2 doc3 doc4clickshearsclick shears15/322/1615/25623/321/1623/5127/321/167/51211/323/1633/512查询 click shears 的文档排序为:doc4,doc1,doc2,doc312. 习题 13-1对于表 13-2,为什么在绝大部分文本集中|V | |Lave都成立?假设大多数文档集的词条数都大于 100 万,根据 Heaps 定律,词汇表大小 V 是文档集规模 T 的一个函数,V=K*Tb,典型的 K=44,b=0.49,V=K*T b=44*(1000000)0.5=44000|D|Ld=文档集中的词条数=1000000 ,|C|V|=2*44000=88000所以大多数文档集有|C|V|D|L d13. 习题 13-2 *表 13-5 中 的 文 档 中 , 对 于 如 下 的 两 种 模 型 表 示 , 哪 些 文 档 具 有 相 同 的 模 型 表 示 ? 哪些 文档具有不同的模型表示?对于不同