《国科大现代信息检索第二次作业》由会员分享，可在线阅读，更多相关《国科大现代信息检索第二次作业（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 中 的 文 档 中 ， 对 于 如 下 的 两 种 模 型 表 示 ， 哪 些 文 档 具 有 相 同 的 模 型 表 示 ？ 哪些 文档具有不同的模型表示？对于不同
