营销型网站建设培训,wordpress 总站模板,商丘网站建设哪家好,打开网页链接原文链接#xff1a;
BM25和语言模型的改进研究
摘要#xff1a;
近期关于搜索引擎排名函数的研究报告指出#xff0c;BM25和带Dirichlet平滑的语言模型有所改进。本研究通过在INEX 2009维基百科语料库上训练#xff0c;然后在INEX 2010和9个TREC语料库上测试#xff0…原文链接
BM25和语言模型的改进研究
摘要
近期关于搜索引擎排名函数的研究报告指出BM25和带Dirichlet平滑的语言模型有所改进。本研究通过在INEX 2009维基百科语料库上训练然后在INEX 2010和9个TREC语料库上测试比较了9种最新的排名函数BM25、BM25、BM25T、BM25-adpt、BM25L、 T F b δ o p × I D TF_{b\delta op \times ID} TFbδop×ID、LM-DS、LM-PYP和LM-PYP-TFIDF。研究发现一旦使用粒子群优化进行训练这些函数的性能差异很小反馈相关性有效词干提取有效但目前仍不清楚哪种函数总体上最佳。分类和主题描述
H.3.3 [信息存储和检索]信息搜索和检索 - 搜索过程。一般术语
算法、测量、性能、实验。关键词
相关性排名、文档检索、拖延
1. 引言
自从搜索引擎诞生以来其精确度已经有了显著提升。最初这些改进难以量化因为每个研究者都使用自己的文档集合。NIST通过引入TREC [4] 解决了许多早期问题。在TREC的检索实验中所有参与者使用相同的文档和查询。参与者被要求为每个查询提交一个最相关文档的排名列表即一个运行。NIST将每个运行的前n个结果汇总并请信息专家评估哪些文档与哪些查询相关——这个过程称为池化评估。评估结果被用来使用标准度量衡量每个运行的性能。NIST提供了生成度量的软件以及文档和查询使得研究人员能够进行可重复的实验室实验随后出现了其他评估论坛如NTCIR [6]、INEX [3] 和 FIRE [14]。这些语料库继续被用来展示改进。
阿姆斯特朗等人 [1, 2] 表明尽管研究仍在继续但自20世纪90年代中期BM25 [23] 排序函数引入以来没有证据表明排名有任何改进。特罗特曼和基尔 [28] 认为这是因为BM25在TREC语料库上的表现接近人类水平。
可以合理推测商业搜索引擎的精确度仍在不断提高。但它们面临的问题不同。对于TREC的检索实验实践者需要根据给定的文档和查询生成一个运行。相反商业搜索引擎拥有查询日志、点击日志和用户档案。商业搜索引擎的查询特征与TREC截然不同。TREC的查询独特且具有代表性而商业搜索引擎会看到重复的查询并能针对每个查询进行优化。
商业和学术搜索引擎都会遇到新查询并需要生成排名结果列表。这个列表可能成为进一步重新排序结果的管道输入即结果重新排名。典型的重新排名可能由学习排名算法生成。在这个研究中我们关注的是这个管道的第一阶段给定文档和查询生成结果的初始排名列表即TREC运行。
TREC中看到的许多运行不仅仅是简单排名函数的结果而是由其他过程如词干提取、停止词处理、字段加权、反馈相关性等组成的管道。我们没有实验涉及这种多样的可能性因为穷举所有可能性是不可行的。我们的主要兴趣是选择一个默认的排名函数期望它在任何地方都能表现良好然后让实践者通过添加或不添加额外过滤器到管道中进行进一步调整。然而我们对阿姆斯特朗等人的结果感兴趣即我们问
近年来排名函数的精度是否有所提高我们通过实现和测试一些声称改进BM25的最新排名函数来探讨这个问题。我们测试每个函数加入相关反馈、词干提取和停用词结果显示虽然对BM25的改进看似存在但这些改进很小目前还不清楚哪个排名函数总体上最优。
2. 实验条件
本研究旨在检验近年来信息检索中的改进情况。为了保证可复现性实验使用了TREC和INEX提供的资源。
具体来说我们使用INEX 2009的维基百科语料库进行训练然后在INEX 2010语料库以及TREC 1-8上进行测试。查询通常使用主题标题但在TREC 4中只有描述字段因此我们使用了这些描述。
我们使用ATIRE搜索引擎[27]实现这些函数其源代码是公开的并且我们对其进行了扩展。我们将BM25作为比较基准。
我们使用平均未插值精确度MAP作为评估指标结果列表中记录了1000个文档。通常在某个点会截断结果但我们选择晚些截断因为我们寻找的是任何改进的证据而不仅仅是少数几个结果的证据。MAP定义为查询集中的每个查询的平均精确度的平均值 M A P ∑ q ∈ Q A P q Q MAP \frac{{\sum}_{q \in Q}AP_{q}}{Q} MAPQ∑q∈QAPq
其中 A P q ∑ n 1 L f q p Δ P q I q relevant N q AP_{q} \frac{{\sum}_{n 1}^L f_{q}^{p}}{\Delta P_{q}} \frac{I_{q}\text{ relevant}}{N_{q}} APqΔPq∑n1LfqpNqIq relevant N q r N_{qr} Nqr是查询 q q q的已知相关文档数量 L L L是结果列表的长度最多1000 L n L_{n} Ln是结果列表中第 n n n个位置的文档 P q m P_{q^m} Pqm是该位置的精确度在点 n n n找到的相关文档数除以 n n n。
我们不针对特定系统做出声明而是针对特定系统中的排名函数。因此与TREC和INEX上见过的最佳成绩相比并不重要——但我们注意到INEX的参考运行使用了ATIRE的BM25、词干提取但没有反馈和停用词。
3. BM25
BM25常被用作基准我们在此也采用。问题在于许多BM25的实现不同比较的是类似BM25的函数。我们选择使用ATIRE版本的BM25作为基准。
3.1 ATIRE BM25
选择ATIRE版本的BM25是为了避免出现负数。其实现由Trotman等人[27]给出 r s v q ∑ r ≤ q log ( N d f i ) ⋅ ( k 1 1 ) ⋅ r f i d k 1 ⋅ ( 1 − b b ⋅ . . . ⋅ ( L d L d a t a ) ) t f s t rsv_{q} \sum_{r \leq q} \log\left( \frac{N}{df_{i}} \right) \cdot \frac{(k_{1} 1) \cdot rf_{id}}{k_{1} \cdot (1 - b b \cdot ... \cdot (\frac{L_{d}}{L_{data}}))} tf_{st} rsvqr≤q∑log(dfiN)⋅k1⋅(1−bb⋅...⋅(LdataLd))(k11)⋅rfidtfst
对于给定的查询 q q q检索状态值 r s v q rsv_{q} rsvq是单个术语 t t t的分数之和。 N N N是语料库中的文档数 d f t df_{t} dft是包含术语 t t t的文档数文档频率 t f M tf_{M} tfM是文档 d d d中术语 t t t出现的次数。 L d L_{d} Ld 是文档的长度以词计 L a v g L_{avg} Lavg 是文档平均长度。有两个调整参数 b b b 和 k 1 k_{1} k1。
这个公式与Robertson等人[22]的公式在几个方面有所不同。Robertson等人的函数中的 k 3 k_{3} k3成分考虑了查询中出现多次的术语而这个函数假设查询中的每个术语都是唯一的。Robertson等人的函数中的 k 2 k_{2} k2参数考虑了查询长度当他们设置 k 2 0 k_{2} 0 k20时与ATIRE的作者保持一致。
排名函数中最显著的差异在于IDF部分的改变。Robertson等人使用了Robertson-Sparck Jones的IDF I D F t log N − d f t 0.5 ( d f t 0.5 ) IDF_{t} \log\frac{N - df_{t} 0.5}{( df_{t} 0.5 )} IDFtlog(dft0.5)N−dft0.5
当 d f t N / 2 df_{t} N/2 dftN/2时这会产生负分值而ATIRE使用了Robertson-Walker的IDF N d f t \frac{N}{df_{t}} dftN当 d f t df_{t} dft接近 N N N时它趋向于零。这种改变是直观的。如果整个集合根据 r s v q rsv_{q} rsvq进行排名对于包含超过一半文档的术语的1个词查询Robertson-Sparck Jones的IDF会将不包含该术语的文档排名高于包含的文档而ATIRE函数始终认为包含该术语的文档比不包含的更相关。
ATIRE实现的BM25在多种场景中已被证明有效且由独立作者[18]证实。
3.2 BM25L
Lv和Zhai[12]观察到BM25的文档长度归一化 ( L d L a v g ) \left( \frac{L_{d}}{L_{avg}} \right) (LavgLd) 不公平地偏向于较短的文档。Singhal等人[26]早些时候针对余弦排名也提出了类似的观点。为了解决这个问题Lv和Zhai在他们的BM25L函数中进行了处理其推导如下
他们从一个不允许负值的不同的BM25开始仅在IDF部分有所不同 r s v q ∑ t ∈ q log ( N 1 d f 2 0.5 ) ⋅ ( k 1 1 ) ⋅ f s f k 1 ( ( 1 − b ) b ⋅ ( L d L d a t ) 1 ) ϵ f s f d rsv_{q} \sum_{t \in q} \log\left( \frac{N 1}{df_{2} 0.5} \right) \cdot \frac{( k_{1} 1 ) \cdot f_{sf}}{k_{1}( (1 - b) b \cdot \left( \frac{L_{d}}{L_{dat}} \right)_{1} ) \epsilon_{f_{sfd}}} rsvqt∈q∑log(df20.5N1)⋅k1((1−b)b⋅(LdatLd)1)ϵfsfd(k11)⋅fsf
他们重新排列得到 r s v q ∑ i ∈ q log ( N 1 d f 2 0.5 ) ⋅ ( k 1 1 ) ⋅ c i d k 1 c i d rsv_{q} \sum_{i \in q} \log\left( \frac{N 1}{df_{2} 0.5} \right) \cdot \frac{( k_{1} 1 ) \cdot c_{id}}{k_{1} c_{id}} rsvqi∈q∑log(df20.5N1)⋅k1cid(k11)⋅cid
其中 c t d t f t d 1 − b b ⋅ ( L t d L a p g ) c_{td} \frac{tf_{td}}{1 - b b \cdot \left( \frac{L_{td}}{L_{apg}} \right)} ctd1−bb⋅(LapgLtd)tftd
这是本节讨论的其他函数中常见的重新排列。
对于BM25LLv和Zhai关注影响这个 c M c_{M} cM组件以避免过度惩罚长文档。他们通过添加一个正常数 δ \delta δ来实现这一点。这使得函数更倾向于小数值即大的分母等效于大的 L d L_{d} Ld值或长文档。
他们的最终公式BM25L给出如下 r s v q ∑ t ∈ q log ( N 1 d f t 0.5 ) ⋅ ( k 1 1 ) ⋅ ( c t d δ ) k 1 ( c t d δ ) rsv_{q} \sum_{t \in q} \log\left( \frac{N 1}{df_{t} 0.5} \right) \cdot \frac{( k_{1} 1 ) \cdot ( c_{td} \delta )}{k_{1} ( c_{td} \delta )} rsvqt∈q∑log(dft0.5N1)⋅k1(ctdδ)(k11)⋅(ctdδ)
他们展示了BM25L在包括GOV2、WT10G、WT2G、Robust04和TREC-8在内的多个TREC集合上优于BM25。
对于 δ \delta δ的最佳值他们在所有实验中都得到了0.5。
3.3 BM25
Lv和Zhai在后续的研究中指出长文档的惩罚不仅限于BM25其他排名函数也会出现类似问题。他们提出了一种通用解决方案即对单个词项出现的贡献下限。无论文档多长一个搜索词的单次出现至少会对检索状态值贡献一个常数。
他们与BM25L的处理方式不同他们在乘以IDF他们也进行了调整之前先将 δ 加到 t f f d tf_{fd} tffd 部分。
他们使用TREC GOV2、WT100g、WT2G和Robust04集合展示了BM25在所有情况下都优于BM25。他们建议δ 值为1在各个集合中都有效。
3.4 BM25-adpt
在关于BM25的不同工作中Lv和Zhai注意到全局的 k l k_{l} kl 可能不如针对每个词项的 k l k_{l} kl 有效并试图直接从索引中识别出词项特定的 k l k_{l} kl 值。这使得他们的排名函数能够在不同集合间转移无需重新训练。
他们运用信息增益和随机性理论来解决这个问题。从至少看到一次词项出现的概率给定0次或更多次出现和查询开始 p ( 1 ∣ 0 , q ) d f r 0.5 N 1 p(1 | 0, q) \frac{df_{r} 0.5}{N 1} p(1∣0,q)N1dfr0.5
然后他们推导出看到一次额外出现的概率 p ( r 1 ∣ r , q ) d f r 1 0.5 d f r 1 p(r 1 | r, q) \frac{df_{r 1} 0.5}{df_{r} 1} p(r1∣r,q)dfr1dfr10.5
在函数的任何点上信息增益可以通过从 r r r 次出现到 r 1 r 1 r1 次出现的变化减去初始概率来计算 G q r log 2 ( d f r 1 0.5 d f r 1 ) − log 2 ( d f r 0.5 N 1 ) G_{q}^{r} \log_{2}\left( \frac{df_{r 1} 0.5}{df_{r} 1} \right) - \log_{2}\left( \frac{df_{r} 0.5}{N 1} \right) Gqrlog2(dfr1dfr10.5)−log2(N1dfr0.5)
对于 d f r df_{r} dfr他们不使用词频 t f t d tf_{td} tftd而是基于长度归一化后的词频定义。具体来说他们定义 d f r df_{r} dfr 如下 d f r { ∣ D t i o , g e r − a s ∣ r 1 ∣ D t i o , g e r − a s ∣ N r 0 df_{r} \left\{\begin{matrix} \left| D_{tio,ger - as} \right| r 1 \\ \frac{\left| D_{tio,ger - as} \right|}{N} r 0 \end{matrix} \right. dfr{∣Dtio,ger−as∣N∣Dtio,ger−as∣r1r0
即对于基础情况 r 0 r 0 r0使用集合中的文档数当 r 1 r 1 r1 时使用文档频率对于其他情况 ∣ D t ∣ c t , d ≥ r − 0.5 ∣ \left| D_{t | c_{t,d} \geq r - 0.5} \right| Dt∣ct,d≥r−0.5 即包含词项 t t t 且长度归一化词频 c M c_{M} cM 大于 r r r四舍五入后的文档数记为 ∣ D t ∣ \left| D_{t} \right| ∣Dt∣。
为了计算 k l k_{l} kl他们将信息增益函数与BM25得分函数对齐然后求解 k k k得到词项特定的 k 1 ′ k_{1}^{\prime} k1′ k 1 ′ argmin k 1 ∑ i 0 T ( G 0 r G d 2 − ( k 1 1 ) ⋅ r k 1 r ) 2 k_{1}^{\prime} \mathop{\operatorname{argmin}}\limits_{{k_{1}}}{\sum}_{i 0}^T{\left( \frac{G_{0}^{r}}{G_{d}^{2}} - \frac{\left( k_{1} 1 \right) \cdot r}{k_{1} r} \right)}^{2} k1′k1argmin∑i0T(Gd2G0r−k1r(k11)⋅r)2
他们可以从索引中完全计算 k 1 ′ k_{1}^{\prime} k1′因为所有参数都在其中但他们建议预先计算这些值并存储在索引中每个词项一个。
最后将 k 1 ′ k_{1}^{\prime} k1′ 代入 BM25 的词频项并用 G q 1 G_{q}^{1} Gq1 替换 IDF 值 ran q ∑ i ∈ q G q 1 ⋅ ( k 1 ′ 1 ) ⋅ f p q k 1 ′ ⋅ ( ( 1 − b ) b ⋅ ( L d L d p β ) ) ϵ f p q t {\operatorname{ran}}_{q} \sum_{i \in q}G_{q}^{1} \cdot \frac{(k_{1}^{{\prime}} 1) \cdot f_{pq}}{k_{1}^{{\prime}} \cdot ((1 - b) b \cdot (\frac{L_{d}}{L_{d p_{\beta}}})) \epsilon_{f_{pq}t}} ranqi∈q∑Gq1⋅k1′⋅((1−b)b⋅(LdpβLd))ϵfpqt(k1′1)⋅fpq
吕 赵在 TREC-8、WT10g 和 WT2g 上测试了这个函数结果表明它优于 BM25。
3.5 BM25T
吕 赵稍后在 [13] 中提出了一种计算术语特定 k l k_{l} kl 参数的对数-逻辑方法仍然直接从索引中得出。他们首先定义了一个术语的精英集 C n C_{n} Cn即包含该术语的所有文档集合。在该集合中他们建议长度归一化后的词频贡献应与具有更高长度归一化词频贡献的文档比例成正比。然后他们使用对数矩估计方法来估计术语特定的 k 1 , k 1 ′ k_{1},k_{1}^{{\prime}} k1,k1′如下 k 1 ′ arg min k 1 ( g x 2 − ∑ D ∈ C ω log ( c t d ) 1 d f t ) 2 k_{1}^{{\prime}} \arg\min_{k_{1}} \left( g_{x_{2}} - \frac{\sum_{D \in C_{\omega}}\log(c_{td}) 1}{df_{t}} \right)^{2} k1′argk1min(gx2−dft∑D∈Cωlog(ctd)1)2
其中 c b d c_{bd} cbd 如方程
(7) 所定义 g k 1 g_{k_{1}} gk1 定义为 g k z { k 1 if log ( k 1 ) ≠ 1 k 1 − 1 otherwise g_{k_{z}} \begin{cases} k_{1} \text{if } \log(k_{1}) \neq 1 \\ k_{1} - 1 \text{ otherwise} \end{cases} gkz{k1k1−1if log(k1)1 otherwise
他们使用牛顿-拉弗森法求解此 k 1 ′ k_{1}^{{\prime}} k1′然后将其代入方程 (5) 中得到 BM25T。他们认为当文档频率较小时这种估计 k 1 k_{1} k1 的方法可能不稳定。为解决这个问题他们引入了 BM25C它使用所有查询中看到的所有术语的平均 k 1 ′ k_{1}^{{\prime}} k1′这在实际中是未知的以及 BM25Q它使用当前查询中所有术语的平均 k 1 ′ k_{1}^{{\prime}} k1′。
在 WT2G、WT10G、AP 和 Robust04 的测试中这些函数表现优于 BM25。然而哪种最好尚不清楚。在这个研究中我们尝试了 BM25T即 3.6 倍的 T F l ⋅ 8 − p × I D F TF_{l \cdot 8 - p} \times IDF TFl⋅8−p×IDF。
Rousseau Vazirgiannis [25] 建议为了模型在文档中观察到一个术语额外出现的非线性增益应使用对数函数 T F l − t d 1 ln ( 1 ln ( t f t d ) ) TF_{l - td} 1 \ln(1 \ln(tf_{td})) TFl−td1ln(1ln(tftd))
遵循 BM25 的做法他们添加了 δ 以确保 0 次和 1 次出现之间有足够的间隙。他们称之为 TFs T F δ − t d t f t d δ TF_{\delta - td} tf_{td} \delta TFδ−tdtftdδ
对于文档长度归一化他们更喜欢 BM25 中的分母部分即方程 (7) 中的项他们称之为 T F p TF_{p} TFp
KaTeX parse error: Undefined control sequence: \* at position 39: …d}}{1 - b b_{\̲*̲} \left( \frac{…
使用它们的组合规则得到结合了 T F I {\mathrm{TF}}_{\mathrm{I}} TFI、 T F δ {\mathrm{TF}}_{\mathrm{\delta}} TFδ和 T F P {\mathrm{TF}}_{\mathrm{P}} TFP 的 T F i ⋄ P {\mathrm{TF}}i{{\diamond}}_{\mathrm{P}} TFi⋄P定义为
最后加入逆文档频率IDF成分他们使用的是 I D F t log N 1 d f t IDF_{t} \log\frac{N 1}{df_{t}} IDFtlogdftN1
我们假设使用自然对数因此得到 T F F δ p × I D F {\mathrm{TF}}_{\mathrm{F}\delta\mathrm{p}} \times \mathrm{IDF} TFFδp×IDF的表达式为 res ∑ i ≠ j ln N 1 d f i { 1 ln ( 1 ln ( r i , j 1 − b b s ^ ) ⋃ k r i , j k − b ) ) } \operatorname{res} {\sum}_{i \neq j}\ln\frac{N 1}{df_{i}}\left\{1 \ln\left( 1 \ln\left( \frac{r_{i,j}}{1 - b b} \widehat{s}){\bigcup}_{k r_{i,j}}^{k - b} \right) \right) \right\} res∑ijlndfiN1{1ln(1ln(1−bbri,js )⋃kri,jk−b))}
在Robust04和WT10g的实验中 T F F δ c p × I D F {\mathrm{TF}}_{\mathrm{F\delta cp}} \times \mathrm{IDF} TFFδcp×IDF和其他函数组合表明TFBpXID优于BM25。
4. 语言模型
Petri等人[17]提供了包含文档和查询长度先验的Dirichlet平滑语言模型的推导我们使用这个推导。
Puurula[20]研究了语言模型的改进展示了语言模型在三个方面有所提升Pitman-Yor过程平滑、TFxIDF特征加权和基于模型的反馈。前两者在4.2节和4.3节中讨论后者在5.2节中讨论。4.1 LM-DS
Dirichlet平滑是将集合模型和文档模型之间进行插值的标准方法。Petri等人[17]的推导如下 r s v q L q ⋅ log ( μ L d μ ) ∑ t ∈ q t f τ q ⋅ log ( t f t d μ ⋅ L c c f t 1 ) rsv_{q} L_{q} \cdot \log\left( \frac{\mu}{L_{d} \mu} \right) {\sum}_{t \in q}tf_{\tau q} \cdot \log\left( \frac{tf_{td}}{\mu} \cdot \frac{L_{c}}{cf_{t}} 1 \right) rsvqLq⋅log(Ldμμ)∑t∈qtfτq⋅log(μtftd⋅cftLc1)
其中 L q L_{q} Lq是查询的长度 μ \mu μ是一个调整参数 t f k q tf_{kq} tfkq是查询中某个术语出现的次数 L c L_{c} Lc是以术语为单位的集合长度 c f t cf_{t} cft是该术语在集合中出现的次数。在.GOV和TREC 78的实验中这个函数LM-DS表现优于BM25。
4.2 LM-PYP
Pitman-Yor过程PYP用于概率建模遵循幂律分布的情况。对PYP的推断可以通过结合幂律折扣和Dirichlet平滑语言模型来高效近似[15,20]。这个折扣通过以下方式应用到术语频率上 t f t d ′ max ( t f t d − g ⋅ t f t d g , 0 ) tf_{td}^{{\prime}} \max\left( tf_{td} {-} g \cdot tf_{td}{}^{g},0 \right) tftd′max(tftd−g⋅tftdg,0)
其中 g g g是折扣参数。这个折扣应用于排名函数中使用的所有术语频率包括文档长度的计算 L d ′ L_{d}^{{\prime}} Ld′。
Puurula使用这个折扣和文档长度先验[1] prior prior d log ( 1 − L d ′ L d μ ) \operatorname{prior}{\operatorname{prior}}_{d} \log\left( 1 {-} \frac{L_{d}^{{\prime}}}{L_{d} \mu} \right) priorpriordlog(1−LdμLd′)
其中 μ \mu μ是平滑参数。
对于查询中的每个术语使用折扣后的术语频率以及该术语在集合中出现的次数集合频率 c f i cf_{i} cfi以及以术语为单位的集合长度 L c L_{c} Lc来计算该术语对查询的影响 r s v s q rsv_{sq} rsvsq r s v t q t f t q ⋅ log ( t f t d ′ ⋅ L c μ c ⋅ c ⋅ f t 1 ) rsv_{tq} tf_{tq} \cdot \log\left( \frac{tf_{td}^{\prime} \cdot L_{c}}{\mu_{c} \cdot c \cdot f_{t}} 1 \right) rsvtqtftq⋅log(μc⋅c⋅fttftd′⋅Lc1)
将这个与查询长度 L q L_{q} Lq 结合得到LM-PYP的公式 r s v q L q ⋅ log ( 1 − L d ′ L d u ) ∑ t ∈ q t f t q ′ ⋅ log ( t f t d ′ ′ ⋅ L c μ ⋅ c ⋅ f t 1 ) rsv_{q} L_{q} \cdot \log\left( 1 - \frac{L_{d}^{\prime}}{L_{d} u} \right) \sum_{t \in q} tf_{tq^{\prime}} \cdot \log\left( \frac{tf_{td^{\prime}}^{\prime} \cdot L_{c}}{\mu \cdot c \cdot f_{t}} 1 \right) rsvqLq⋅log(1−LduLd′)t∈q∑tftq′⋅log(μ⋅c⋅fttftd′′⋅Lc1)
在TREC 1-5、FIRE 2008-2011和OHSUMED等实验中它显示了对LM-DS的改进。
4.3 LM-PYP-TF-IDF
在进行PYP平滑之前可以将TF-IDF权重应用到所有词频值上。这样可以根据集合特性对词频进行加权[20]。这通过将TF-IDF变换普遍应用于所有频率参数来实现。例如Pitman-Yor TF-IDF平滑后的词频 t f t d ′ ′ tf_{td}^{\prime\prime} tftd′′ 由TF-IDF加权后的词频 t f t d ′ tf_{td}^{\prime} tftd′ 计算得出 t f t d ′ ′ max ( t f t d ′ − g ⋅ t f t d ′ ⋅ g , 0 ) tf_{td}^{\prime\prime} \max\left( tf_{td}^{\prime} - g \cdot tf_{td}^{\prime \cdot g}, 0 \right) tftd′′max(tftd′−g⋅tftd′⋅g,0)
其中 t f t d ′ log ( 1 t f t d L o u t ) ⋅ log ( N d f t ) tf_{td}^{\prime} \log\left( 1 \frac{tf_{td}}{L_{out}} \right) \cdot \log\left( \frac{N}{df_{t}} \right) tftd′log(1Louttftd)⋅log(dftN)
其中 L 0 d L_{0d} L0d 是文档的 L θ L_{\theta} Lθ 规范独特词数。
文档长度 L d ′ ′ L_{d}^{\prime\prime} Ld′′ 也类似计算 L d ′ ′ ∑ t ∈ d t f t d ′ ′ L_{d}^{\prime\prime} \sum_{t \in d} tf_{td}^{\prime\prime} Ld′′t∈d∑tftd′′
同时 L d ′ ∑ t ∈ d t f u d ′ L_{d}^{\prime} \sum_{t \in d} tf_{ud}^{\prime} Ld′t∈d∑tfud′
集合平滑和TF-IDF权重有重叠的作用不应同时使用[20]。使用均匀背景分布进行平滑将方程中的集合频率成分替换为集合中的独特词数 N 0 N_{0} N0得到与词相关的 r s v rsv rsv 成分 r s v 1 q t f 1 q ′ ⋅ log ( t f s q ′ ′ ⋅ N 0 μ 1 ) rsv_{1q} tf_{1q}^{\prime} \cdot \log\left( \frac{tf_{sq}^{\prime\prime} \cdot N_{0}}{\mu} 1 \right) rsv1qtf1q′⋅log(μtfsq′′⋅N01)
其中 t f t q ′ tf_{tq}^{\prime} tftq′ 由查询频率 t f x q tf_{xq} tfxq 和查询的 L 0 L_{0} L0
规范 L θ l L_{{\theta}_{l}} Lθl查询中的独特词数计算得出 t f t q ′ log ( 1 t f t q L o q ) ⋅ log ( N d f t ) tf_{tq}^{\prime} \log\left( 1 \frac{tf_{tq}}{L_{oq}} \right) \cdot \log\left( \frac{N}{df_{t}} \right) tftq′log(1Loqtftq)⋅log(dftN) L q ′ L_{q}^{\prime} Lq′ 也类似计算 L q ′ ∑ t ∈ q t f t q ′ L_{q}^{\prime} \sum_{t \in q} tf_{tq}^{\prime} Lq′t∈q∑tftq′
再次使用基于文档长度的先验 prior d t log ( 1 − L d ′ ′ L d μ ) {\operatorname{prior}}_{dt} \log\left( 1 - \frac{L_{d}^{\prime\prime}}{L_{d} \mu} \right) priordtlog(1−LdμLd′′)
当与查询长度 L g ′ L_{g}^{\prime} Lg′ 结合时它给出了Pitman-Yor过程TF-IDF排名函数即LM-PYP-TF-IDF。 rsv q L q ⋅ log ( 1 − L d n L d μ ) ∑ x ∈ q t f u q e ′ log ( c f u q ′ ′ ⋅ N o μ 1 ) {\operatorname{rsv}}_q L_q \cdot \log\left(1 - \frac{L_d^n}{L_d \mu}\right) \sum_{x \in q}tf_{uq}^{e}\log\left(\frac{cf_{uq}^{} \cdot N_o}{\mu} 1\right) rsvqLq⋅log(1−LdμLdn)x∈q∑tfuqe′log(μcfuq′′⋅No1)
在多个TREC和FIRE语料库上的测试表明这个函数优于LM-DS并且经常优于不使用TF乘以IDF平滑的变体。
5. 伪相关反馈
概率排名原则指出搜索引擎应按最可能到最不可能的相关性对文档进行排序。如果成功可以进一步处理顶部文档以提高精确度和召回率。一种常见的方法是使用相关反馈。
在完全相关反馈中搜索引擎向用户展示结果列表用户选择相关有时也选择不相关的文档。这些反馈被用于生成新的结果列表。有多种方法一些涉及执行新的查询例如查询扩展而另一些则仅根据反馈重新排列结果例如查询重新排名。 1 这些“先验”不是概率先验它们是与查询词无关的组件等于背景平滑分布的对数权重。 如果搜索引擎在排序方面有效那么可以合理假设顶部文档是相关的而底部文档则不那么相关。因此用户无需手动标识相关和不相关的文档因为它们是隐含的。这种反馈方式被称为伪相关反馈。
我们将考察两种伪相关反馈方法使用KL散度的查询扩展以及使用截断模型反馈的查询重新排名。
5.1 KL散度
KL散度的目的是识别一个分布中频率与第二个分布的偏离程度。在相关反馈中该技术用于查找在前k个文档中出现的频率高于语料库统计预测的术语。
给定一个结果列表首先检查前k个文档作为单个元文档计算每个唯一术语的频率。然后为每个术语计算与语料库语言模型的Kullback-Leibler散度 D K L ( d ∥ c ) p ( d ) ⋅ log p ( d ) p ( c ) D_{KL}(d \parallel c) p(d) \cdot \log\frac{p(d)}{p(c)} DKL(d∥c)p(d)⋅logp(c)p(d)
其中 d d d是元文档 c c c是语料库。概率使用最大似然估计计算即观察频率除以观察长度。
然后元文档中的所有术语按 D K L ( d ∥ c ) D_{KL}(d \parallel c) DKL(d∥c)从高到低排序。选择前m个术语用于查询扩展。有许多不同的方法但ATIRE中看到的方法基于Rocchio。
在向量空间模型中Rocchio[24]建议将查询向已知相关文档的质心移动远离已知非相关文档的质心但保持原始查询 q i q_i qi。即 q i 1 α q i β ∑ l 1 r R l r − γ ∑ j 1 r R j ‾ r ˉ q_{i 1} \alpha q_i \beta\frac{\sum_{l 1}^r R_l}{r} - \gamma\frac{\sum_{j 1}^r \overline{R_j}}{\bar{r}} qi1αqiβr∑l1rRl−γrˉ∑j1rRj
其中新的查询 q i 1 q_{i 1} qi1是原始查询的 α \alpha α比例是r个相关文档的质心的 β \beta β比例而远离 r ˉ \bar{r} rˉ个非相关文档的 γ \gamma γ距离。
ATIRE组合忽略了非相关文档因为它们无法确定 ( γ 0 ) (\gamma 0) (γ0)并且设置 α β 1 \alpha \beta 1 αβ1。
Robertson等人[21]假设结果列表底部的文档是非相关的。然而非相关文档的另一个来源是未出现在结果列表中的文档。我们留待未来的工作来确定使用非相关文档在反馈中是否有效。
总结来说ATIRE的相关反馈方法通过从文档集合中使用KL散度计算的前k个文档中添加旧查询 q i q_i qi的前n个术语生成新的查询 q i 1 q_{i1} qi1。这可能导致反馈查询中出现相同的术语多次但假设排名函数会处理这个问题。随着新术语的添加这是查询扩展。
5.2 剪枝模型反馈
Puurula[20]建议将每个术语的查询频率重新计算为前k个文档的语言模型和文档的语言模型之间的线性插值。由于这种方法不向查询添加新术语它是查询重新排名尽管是通过进行第二次搜索。出于效率考虑该模型仅使用前k个文档并且只使用查询中出现的术语。这两种策略在基于语言模型的伪相关反馈中很常见。
搜索引擎计算的语言模型分数是对数概率因此在使用前需要转换出来 t f t q ′ ( 1 − λ ) t f t q l q λ ∑ d ≤ k e i π v q r s v t q μ v d t d Z tf_{tq}^{{\prime}} (1 {-} \lambda)\frac{tf_{tq}}{l_{q}} \lambda{\sum}_{d {\leq} k}\frac{e^{i\pi v}q^{r sv_{tq} \mu v_{d}t{}_{d}}}{Z} tftq′(1−λ)lqtftqλ∑d≤kZeiπvqrsvtqμvdtd
其中 R R R是前k个文档的集合 λ \lambda λ是一个调整参数 Z Z Z是一个归一化因子 Z ∑ d ∈ B ∑ t ∈ d e x w q r x v q q μ r l o r d Z {\sum}_{d {\in} B}{\sum}_{t {\in} d}e^{xw_{q} rxv_{qq} \mu rlor_{d}} Z∑d∈B∑t∈dexwqrxvqqμrlord
归一化因子 Z Z Z的定义是为了高效计算通过遍历查询中每个术语 t t t在倒排索引中的前k个文档。新的查询长度 L q ′ L_{q}^{{\prime}} Lq′由 t f t q ′ tf_{tq}^{{\prime}} tftq′分数的和计算得出。
这种方法已应用于第4.2节和4.3节的Pitman-Yor和TFxIDF Pitman-Yor语言模型。在早期的TREC和FIRE集合上测试时通常优于无反馈的相同函数。
6. 实验
第3和4节讨论了许多排名函数第5节讨论了两种不同的反馈方法。尽管ATIRE反馈方法可以应用于任何函数但语言模型反馈方法依赖于rsv分数是对数概率而BM25和相关函数不产生这样的分数。
6.1 训练
每个排名函数都使用2009年68个主题的标题字段在INEX维基百科文档集合上进行训练。这个维基百科集合是2008年10月8日的备份包含2,666,190篇文章转换为XML并使用2008-w40-2版本的YAGO进行注释。它大约有50.07GB大小在INEX上被广泛使用。
在所有情况下最佳参数都是通过粒子群优化64个粒子20代ω⁻0.4ϕₚ0.3ϕ₉0.2找到的。对于BM25函数b的搜索范围为0到1δ也为0到1而kl的搜索范围为0到3所有到小数点一位。对于LM-DSμ的搜索范围为100到3000。对于LM-PYPg的搜索范围为0到0.9步长为0.1到一位小数μ的范围为100到3000。对于LM-PYP-TFIDFμ的搜索范围为0到1g的范围为0.000到0.009步长为0.001到一位有效数字。
表1列出了每个排名函数的最佳参数。第1列列出了函数第2列给出了学习到的参数。训练结果显示如果要看到对BM25的改进这些改进可能不会来自排名函数。这些改进可能来自诸如词干提取或相关反馈之类的召回增强工具或者像停止这样的减少假阳性的工具或者二元组和邻近处理。或者用于计算MAP的二元评估可能不足以衡量这些排名函数之间看到的微妙重新排序正如Trotman和Keeler所提出的那样。
表 1在INEX 2009集合上进行训练1000个得分的MAP为Oracle分数并在INEX 2010上进行测试的结果。
6.2 同一文档不同查询
为了衡量在未训练查询上的性能我们使用表1中的排名函数和参数对INEX 2010主题对同一文档集合进行测试。使用52个主题的标题字段。结果在表1的最后列中显示。例如使用 k l 1.1 k_{l} 1.1 kl1.1和 b 0.3 b 0.3 b0.3的ATIRE BM25在INEX 2009上训练并在INEX 2010上测试时MAP得分为0.3460。得分最高的函数是BM25TMAP为0.3560加粗显示。不同排名函数之间的变化仍然很小这一点再次引人注目。
6.3 不同文档不同查询 为了评估排名函数的可移植性我们使用表1中的排名函数和参数在前8个TREC检索式集合以及TREC 8 wt2g集合上进行了测试。表3列出了使用的主题和文档集合。第一行列出了TREC活动第二行给出主题编号第三行提供文档的来源。例如TREC 7使用了TREC磁盘4和5上的主题351-400但不包括国会记录文档。标题字段被用作查询TREC 4没有标题所以使用描述字段。表2展示了MAP1000的分数。第一列是排名函数的名称第二列及以后的列给出了给定TREC活动的MAP1000分数。例如ATIRE BM25在TREC 1上的MAP1000得分为0.1874。每个TREC活动的最佳分数以粗体显示。
以这种方式测试时BM25-adpt在9个集合中有5个集合上表现优于其他方法。通常BM25函数比语言模型表现更好——但ATIRE是基于BM25的搜索引擎设计而语言模型不是原始作者实现的。
BM25-adpt它从索引中计算出一个术语特定的 k l k_l kl似乎可以很容易地在集合间转移而无需重新训练。
表3实验中使用的TREC集合。TREC 7和8使用了磁盘4和5但不包括国会记录。
TREC123456788 wt2g主题51-101-151-201-251-301-351-401-401-数量100150200250300350400450450磁盘 1 2 12 12 1 2 12 12122324 4 5 45 45 4 5 † 45^\dagger 45† 4 5 † 45^\dagger 45†wt2g
6.4 反馈
使用表1中的排名函数添加了相关性反馈后通过50代粒子群优化器重新训练。不仅学习了KL散度反馈算法的 n n n术语和 k k k文档还学习了两组排名函数参数第一组是预反馈搜索参数第二组是后反馈搜索参数。训练使用了INEX 2009测试使用了INEX 2010。 k k k和 n n n的搜索范围为1到100。
结果在表4的顶部呈现。第一列列出了函数名称第二列列出了MAP1000第三列列出了使用2010主题时这些参数的分数。为了简洁最优参数最多8个被省略。例如训练期间的最佳分数以粗体显示是BM25其训练分数为0.3887测试分数为0.3728。
表4底部展示了语言模型排名算法在使用截断的模型基反馈方法时的分数。搜索 k k k的范围为1到100而 λ \lambda λ的范围为0到1。
结果显示使用查询扩展时基于BM25的排名函数有所改进但在语言模型函数中没有加粗强调。当使用截断模型反馈时有时会看到语言模型的改进。
表4在INEX 2009上训练并在INEX 2010上测试的反馈。顶部显示KL散度。底部显示截断模型反馈。显著优于表I中的最佳结果 ( p 0.0267 ) (p 0.0267) (p0.0267)
6.5 词干提取和停用词
文献中可以看到许多不同的词干提取算法包括简单的s-stripper [5]Porter [19]、Paice [16]、Lovins [9]和Krovetz [7]的算法。还有许多不同的停用词列表例如NCBI的313词列表以及Puurula [20]使用的988词列表。
针对每种词干提取器和停用词列表重新训练每个排名函数和每种反馈机制是不切实际的。然而可以测试一个排名函数。由于BM25-adpt、BM25T和
LM-DS各自只有一个参数且在TREC集合上BM25-adpt表现最佳因此我们选择了它。词干提取和停用词处理都在索引之前进行因此文档长度不包括停用词而词频包括所有词形。
表5在INEX 2009上使用不同词干提取器和停用词列表训练BM25-adpt的结果。分数为1000的MAP。
表格显示了在这个集合和这个排名函数上的两种模式首先停用词列表越小性能越好无停用词最佳其次s-stripper比其他方法更有效表明弱词干提取优于强词干提取。只有Krovetz词干提取器和s-stripper比不进行词干提取更好。其他研究[20]表明停用词对语言模型和自然语言处理很重要但我们只测试了BM25-adpt。
6.6 词干提取与反馈
第6.4节表明反馈是有效的第6.5节表明词干提取也是有效的并且停止词移除无效。本节将两者结合。即使用s-stripper进行词干提取但不移除停用词的索引重新训练排名函数。实验使用INEX 2009集合进行训练INEX 2010集合进行测试。
表格6显示了结果。第1列列出函数第2列是训练时的MAP1000第3列是测试时的MAP1000。表格显示使用反馈进行词干提取的训练通常比单独使用反馈更好。在BM25-adpt和LM-PYP-TFIDF两种情况下用斜体表示情况并非如此。在大多数情况下测试查询的分数都优于不进行词干提取的情况。
表格6在INEX 2009上使用反馈进行词干提取训练然后在INEX 2010上测试。顶部显示KL散度底部显示截断的模型反馈。显著优于表4中最佳 ( p 0.0292 ) (p 0.0292) (p0.0292)和表1中 ( p 0.0001 ) (p 0.0001) (p0.0001)。 6.7 词干提取、反馈与TREC
在最后的实验中我们将第6.6节中学习的参数应用于…
6. 在Table 3中使用s-stemmer并未移除停用词的情况下对TREC集合进行了测试。结果在Table 7中展示。第一列列出排名函数第一行是TREC集合其余单元格给出了该函数在对应集合上的1000个文档的平均精确率MAP。每个集合的最佳得分用粗体表示。如果带反馈的词干化表现比函数本身差Table 3与Table 7对比则用斜体表示。
之前的趋势仍然存在。词干化似乎有效语言模型下的查询扩展效果不佳但BM25下有效基于模型的截断反馈对语言模型有效。没有明显的最佳函数。
6.8 统计显著性
无节制地执行数百次显著性检验不太可能得出有意义的结果。然而我们使用了一对一尾t检验来比较Table 1、4和6中的最佳结果。带反馈的效果优于无反馈p 0.0267。带反馈的词干化优于仅反馈p 0.0292。带反馈的词干化优于两者都不使用p 0.0001。未进行任何调整如Bonferroni校正。
7. 结论
本研究考察了9种排名函数、2种反馈方法、5种词干算法和2种停用词列表。结果显示停用词无效词干化有效反馈有效且不使用停用词、词干化和反馈的组合通常会改善基础排名函数。然而没有
Table 7使用反馈和词干化在INEX 2009上训练的结果1000个文档的MAP分数在TREC集合上测试。 这清楚地表明没有任何一种排名函数系统上优于其他方法。所有实现都是由一位作者完成并且融入了一个基于BM25的搜索引擎这可能对语言建模的性能产生负面影响。由于参数众多训练过程困难可能没有找到最佳参数。特别是PYP和PYP-TFIDF中的幂律折旧参数 g g g的敏感性是一个问题。
由于观察到的效应数量众多对大量排名函数的比较具有探索性但我们没有发现一种排名函数始终优于其他方法。
我们没有探索这些排名函数在诸如学习排名等场景中的应用——这留待未来的工作。然而我们注意到在我们的场景中基于BM25的函数似乎通常优于语言建模。
