国科大2013年秋季《现代信息检索》第二次作业(第六章到第十五章)
以下1-16每题6分，第17题3分，共计100分。
1. 习题 6-10 考虑图6-9中的3篇文档Doc1、Doc2、Doc3中几个词项的tf情况，采用图6-8中的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列中给出词项的出现频率，并计算出最后的相似度结果。
相似度结果=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从大变小看，中间有一个相等的情况，这时候召回率=正确率。
习题 8-8 [*] 考虑一个有4篇相关文档的信息需求，考察两个系统的前10个检索结果（左边的结果
R N R N N NNN R R N R N N R RR N NN
1 2
计算两个系统的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 DVDs extremelycheap CDs。用户查看了两篇文档d1
和d2，并对这两篇文档进行了判断：包含内容CDs cheap software cheap CDs的文档d1为相关文档，而内容为cheap thrills DVDs 的文档d2为不相关文档。假设直接使用词项的频率作为权重（不进行归一化也不加上文档频率因子），也不对向量进行长度归一化。采用公式（9-3）进行Rocchio相关反馈，请问修改后的查询向量是多少？其中α = 1，β = 0.75，γ = 0.25。
国科大2013年秋季《现代信息检索》第二次作业(第六章到第十五章)
以下1-16每题6分，第17题3分，共计100分。
1. 习题 6-10 考虑图6-9中的3篇文档Doc1、Doc2、Doc3中几个词项的tf情况，采用图6-8中的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列中给出词项的出现频率，并计算出最后的相似度结果。
相似度结果=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从大变小看，中间有一个相等的情况，这时候召回率=正确率。
习题 8-8 [*] 考虑一个有4篇相关文档的信息需求，考察两个系统的前10个检索结果（左边的结果
R N R N N NNN R R N R N N R RR N NN
1 2
计算两个系统的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 DVDs extremelycheap CDs。用户查看了两篇文档d1
和d2，并对这两篇文档进行了判断：包含内容CDs cheap software cheap CDs的文档d1为相关文档，而内容为cheap thrills DVDs 的文档d2为不相关文档。假设直接使用词项的频率作为权重（不进行归一化也不加上文档频率因子），也不对向量进行长度归一化。采用公式（9-3）进行Rocchio相关反馈，请问修改后的查询向量是多少？其中α = 1，β = 0.75，γ = 0.25。