国科大现代信息检索第二次作业Word格式文档下载.docx
《国科大现代信息检索第二次作业Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《国科大现代信息检索第二次作业Word格式文档下载.docx（5页珍藏版）》请在冰点文库上搜索。
0*1.62=0；
33*1.62=53.46；
29*1.62=46.98
best在三篇文档中的tf-idf值分别为：
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 计算查询digitalcameras及文档digitalcamerasandvideocameras的向量空间相似度并将结果填入表6-1的空列中。
假定N=10000000，对查询及文档中的词项权重（wf对应的列）采用对数方法计算，查询的权重计算采用idf，而文档归一化采用余弦相似度计算。
将and看成是停用词。
请在tf列中给出词项的出现频率，并计算出最后的相似度结果。
表6-1 习题6-19中的余弦相似度计算
词
查 询
文 档
tf
wf
df
idf
qi=wf-idf
di=归一化的wf
digital
1
10000
0.52
1.56
video
100000
2
cameras
50000
2.301
1.301
0.677
1.558
相似度结果=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
l3
如图所示，黄色圈代表查询，离查询最近的两个先导者为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 RNRNN NNNRR
系统2 NRNNR RRNNN
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 假定用户的初始查询是cheapCDscheapDVDsextremelycheapCDs。
用户查看了两篇文档d1和d2，并对这两篇文档进行了判断：
包含内容CDscheapsoftwarecheapCDs的文档d1为相关文档，而内容为cheapthrillsDVDs的文档d2为不相关文档。
假设直接使用词项的频率作为权重（不进行归一化也不加上文档频率因子），也不对向量进行长度归一化。
采用公式（9-3）进行Rocchio相关反馈，请问修改后的查询向量是多少？
其中α=1，β=0.75，γ=0.25。
qm=αq0+β1|Dr|dj∈Drdj-γ1|Dnr|dj∈Dnrdj
词项频率表格
原始查询
d1
d2
CDs
cheap
DVDs
extremely
software
thrills
修改后的查询向量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是相关文档集，定义一个函数PDR=1=t∈DPdR=1=pts（1-pt）|R|-s
∂P（D|R=1）∂pt=s×
pts-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[*] 考虑从如下训练文本中构造LM：
themartianhaslandedonthelatinpopsensationrickymartin
请问：
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篇文档组成：
文档ID
文档文本
clickgotheshearsboysclickclickclick
clickclick
metalhere
metalshearsclickhere
为该文档集建立一个查询似然模型。
假定采用文档语言模型和文档集语言模型的混合模型，权重均为0.5。
采用MLE来估计两个一元模型。
计算在查询click、shears以及clickshears下每篇文档模型对应的概率，并利用这些概率来对返回的文档排序。
将这些概率填在下表中。
对于查询clickshears来说，最后得到的文档次序如何？
查询似然模型：
click
go
the
shears
boys
metal
here
模型1
1/2
1/8
模型2
模型3
模型4
1/4
文档集模型
7/16
1/16
2/16
每篇文档模型对应的概率为：
query
doc1
doc2
doc3
doc4
clickshears
15/32
15/256
23/32
23/512
7/32
7/512
11/32
3/16
33/512
查询clickshears的文档排序为：
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*（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独立性假设存在问题的几个文档例子
（1）HemovedfromLondon,Ontario,toLondon,England.
（2）HemovedfromLondon,England,toLondon,Ontario.
（3）HemovedfromEnglandtoLondon,Ontario.
（i）贝努利模型：
三个文档具有相同的模型表示。
（ii）多项式模型：
文档
（1）
（2）相同，与文档3不同。
文档
（1）
（2）中’London’都出现了两次，文档（3）中’London’只出现了一次。
14.习题13-5 考虑Reuters-RCV1语料前100000篇文档中4个词项在类别coffee中的出现频率。
词项
N00
N01
N10
N11
brazil
98012
102
1835
51
council
96332
133
3525
20
producers
98524
119
1323
34
roasted
99824
143
23
10
根据（i）（ii）互信息及（iii）频率的值，从上述4个词项中选出2个词项。
（i）
对于brazil：
E11=N*p（t）*p（c）=（51+1835）*（51+102）/100000=2.8856
E00=N*（1-p（t））*（1-p（c））=（98012+102）*（98012+1835）/100000=97963.8856
E01=N*（1-p（t））*p（c）=（98012+102）*（51+102）/100000=150.1144
E10=N*p（t）*（1-p（c））=（1835+51）*（98012+1835）/100000=1883.1144
X2D,t,c=et∈{0,1}ec∈{0,1}（Netec-Eetec）2Eetec=（98012-97963.8856）2/97963.8856+（102-150.1144）2/150.1144+（1835-1883.1144）2/1883.1144+（51-2.8856）2/2.8856=818.939
对于council：
X2（D,t,c）=40.336
E00=（96332+133）*（96332+3525）/100000=96327.0551
E01=（96332+133）*（133+20）/100000=147.5915
E10=（3525+20）*（96332+3525）/100000=3539.9307
E11=（133+20）*（3525+20）/100000=5.4239
对于producers：
X2D,t,c=N*（N11*N00-N01N10）2（N11+N01）（N11+N10）（N00+N01）（N00+N10）=498.375
对于roasted：
X2（D,t,c）=1964.293
X2值越大意味着独立性假设不成立，选出brazil和roasted。
（ii）互信息
brazil:
IU;
C=N11Nlog2NN11N1.N.1+N01Nlog2NN01N0.N.1+N10Nlog2NN10N1.N.0+N00Nlog2NN00N0.N.0=0.0015537
council:
C=96322100000log2100000*9632296322+13396322+3525+96322100000log2100000*9632296322+13396322+3525
+96322100000log2100000*96322（96322+133）（96322+3525）+96322100000log2100000*96322（96322+133）（96322+3525）=0.0001774
producers:
I（U;
C）=0.0009689
roasted:
C）=0.0006485
互信息度量的是词项是否被类别包含所带来的信息量，选出brazil和producers。
（iii）频率的值
51/（51+102）=0.3333
20/（20+133）=0.1307
prodecers:
34/（34+119）=0.2222
10/（10+143）=0.0654
选择在类别中频率较高的词项作为特征，选出brazil和producers。
15.习题14-2[*] 试举例说明，如果采用Rocchio分类方法对训练文档分类，那么分类结果有可能会不同于训练集上的结果。
平面上有两类文档，一类分布于半径为1的圆圈内，另一类分布于半径为10的圆圈内，两个圆圈有交集。
按照Rocchio分类方法，半径为10的圆圈中的文档将有很多被分类为半径为1的圆圈内。
16.习题14-4 试证明两个类别间的线性分类器的数目要么是无穷的，要么是0。
如果存在一个线性分类器，那么把它沿着最近点对的方向移动一个很小的距离后仍然为一个线性分类器。
17.习题15-3[**] 安装某个SVM包，比如SVMlight（http:
//svmlight.joachims.org/），对例15-1建立一个SVM分类器。
请确认程序会给出与文中一样的结果。
对于SVMlight或者其他包来说，训练数据格式是一样的，它们的格式如下所示：
+11:
22:
−11:
12:
SVMlight的训练命令为
svmlearn-c1-aalphas.dattrain.datmodel.dat。
-c1选项是为了使用15.2.1节中将要讨论的松弛变量。
核对一下归一化后的权重向量，看看是否和例15-1一致。
检查一下最后输出的alphas.dat文件，看看αi是否和习题15-2的解答一致。
【给出运行截图】
model.dat中的结果是：
SVM-lightVersionV6.02
0#kerneltype
3#kernelparameter-d
1#kernelparameter-g
1#kernelparameter-s
1#kernelparameter-r
empty#kernelparameter-u
2#highestfeatureindex
3#numberoftrainingdocuments
3#numberofsupportvectorsplus1
2.2#thresholdb,eachfollowinglineisaSV（startingwithalpha*y）
-0.400000000000001471:
1#
0.400000000000000581:
3#
alphas.dat输出的结果是：
0.40000000000000058
-0
-0.40000000000000147
w=aiyixi=0.4*2,3-0.4*1,1=（0.4,0.8），最大间隔ρ=2w=5，与书上例15-1一致。
升级会员 