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

国科大2024年秋季《现代信息检索》第二次作业(第六章到第十五章)

以下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值。

图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.6

auto在三篇文档中的tf-idf值分别为：doc1:3*2.08=6.24；33*2.08=68.64；0*2.08=0

insurance在三篇文档中的tf-idf值分别为：doc1:0*1.62=0；33*1.62=53.46；29*1.62=46.98

best在三篇文档中的tf-idf值分别为：doc1:14*1.5=21；0*1.5=0；17*1.5=25.5

2. 习题 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=10000000，对查询及文档中的词项权重（wf对应的列）采用对数方法计算，查询的权重计算采用idf，而文档归一化采用余弦相似度计算。

将 and看成是停用词。请在tf列中给出词项的出现频率，并计算出最后的相似度结果。

表6-1 习题6-19中的余弦相似度计算。

相似度结果=1.56+1.558=3.118

4. 习题 7-1 图7-2中倒排记录表均按照静态得分g(d)的降序排列，为什么不采用升序排列？

一篇文档d的最后得分定义为g(d)和某个与查询相关的得分的某种组合，一些文档具有高的g(d)值更有可能具有较大的最后得分，降序排列有助于提高top-k检索的效率。在这种排序下，高分文档更可能在倒排记录表遍历的前期出现。在实际受限的应用当中（比如，任意搜索需要在50ms内返回结果），上述方式可以提前结束倒排记录表的遍历。

5. 习题 7-8 平面上的最近邻问题如下：在平面上给出n个数据点并将它们预处理成某种数据结构，给定查询点q，在n个点中寻找与q具有最短欧氏距离的点。

很显然，如果我们希望能够避免计算q和所有平面上的点的距离时，簇剪枝就能够作为最近邻问题的一种处理方法。请给出一个简单的例子来说明：如果只选择最近的两个先导者，那么簇剪枝方法可能会返回错误的结果（也就是说返回的不是离q最近的数据点）。

如图所示，黄色圈代表查询，离查询最近的两个先导者为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 nnn r r

系统2 n r n n r rr n nn

a. 计算两个系统的map值并比较大小。

map(系统1)=(1/4)*(1+2/3+3/9+4/10)=0.6

map(系统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.5

r正确率（系统2）=1/4=0.25

虽然r正确率只度量了正确率-召回率曲线上的一个点，但是经验上却证实它和map是高度相关的。按照r正确率和map排序得到的结果一致。

8. 习题 9-3 假定用户的初始查询是cheap cds cheap ***s extremelycheap cds。用户查看了两篇文档d1 和d2，并对这两篇文档进行了判断：

包含内容cds cheap software cheap cds的文档d1为相关文档，而内容为cheap thrills ***s 的文档d2为不相关文档。假设直接使用词项的频率作为权重（不进行归一化也不加上文档频率因子），也不对向量进行长度归一化。采用公式（9-3）进行rocchio相关反馈，请问修改后的查询向量是多少？

其中α =1，β 0.75，γ 0.25。

修改后的查询向量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是相关文档集，定义一个函数。

令，得到。10. 习题12-6 [*考虑从如下训练文本中构造lm：

themartian has landed on the latin pop sensation ricky martin

请问：a. 在采用mle估计的一元概率模型中，p(the)和p(martian)分别是多少？

p(the) =2/11 = 0.181818182

p(martian) =1/11 = 0.090909091

b. 在采用mle估计的二元概率模型中，p(sensation|pop)和p(pop|the)的概率是多少？

p(sensation|pop) =1

p(pop|the) =0

11. 习题12-7 [*假定某文档集由如下4篇文档组成：

为该文档集建立一个查询似然模型。假定采用文档语言模型和文档集语言模型的混合模型，权重均为0.5。

采用mle来估计两个一元模型。计算在查询click、shears以及click shears下每篇文档模型对应的概率，并利用这些概率来对返回的文档排序。将这些概率填在下表中。

对于查询 click shears来说，最后得到的文档次序如何？

查询似然模型：

每篇文档模型对应的概率为：

查询 click shears的文档排序为：doc4,doc1,doc2,doc3

12. 习题 13-1 对于表13-2，为什么在绝大部分文本集中| |v|

假设大多数文档集的词条数都大于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|ld

13. 习题 13-2[*]表13-5中的文档中，对于如下的两种模型表示，哪些文档具有相同的模型表示？哪些文档具有不同的模型表示？对于不同的表示进行描述。

i) 贝努利模型。

ii) 多项式模型。

表13-5 nb独立性假设存在问题的几个文档例子。

i) 贝努利模型：三个文档具有相同的模型表示。

ii) 多项式模型：文档(1)(2)相同，与文档3不同。文档(1)(2)中’london’都出现了两次，文档(3)中’london’只出现了一次。

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

信息检索第二次作业

信息检索第二次作业

网络信息检索第二次作业

其他用户还读了