陳振宏，俞曉明，劉 悅，程學(xué)旗

(1. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190；2. 中國(guó)科學(xué)院大學(xué)，北京，100190)

查詢會(huì)話中帶時(shí)間因子的隱式負(fù)反饋研究

陳振宏1,2，俞曉明1，劉 悅1，程學(xué)旗1

(1. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190；2. 中國(guó)科學(xué)院大學(xué)，北京，100190)

隱式相關(guān)反饋常被用于提升檢索系統(tǒng)的性能，目前大部分工作集中在研究隱式正反饋。該文同時(shí)考慮隱式正負(fù)反饋，將查詢會(huì)話中被點(diǎn)擊網(wǎng)頁(yè)前的未被點(diǎn)擊網(wǎng)頁(yè)作為隱式負(fù)反饋信息，通過(guò)引入時(shí)間因子，估計(jì)用戶在未被點(diǎn)擊網(wǎng)頁(yè)的標(biāo)題和摘要上的停留時(shí)間，推斷隱式負(fù)反饋與用戶興趣和行為的關(guān)系，達(dá)到優(yōu)化檢索結(jié)果的目的。在TRECSession2011和2012數(shù)據(jù)集上的實(shí)驗(yàn)，驗(yàn)證了該文提出的帶時(shí)間因子的隱式正負(fù)反饋算法TIPNF的有效性。

查詢會(huì)話；隱式負(fù)反饋；時(shí)間因子；排序

1 引言

相關(guān)反饋技術(shù)是優(yōu)化檢索系統(tǒng)排序結(jié)果的重要方法之一，包括顯式相關(guān)反饋、隱式相關(guān)反饋和偽相關(guān)反饋三類。其中，隱式相關(guān)反饋利用用戶與檢索系統(tǒng)的交互信息推斷用戶偏好，達(dá)到優(yōu)化檢索效果的目的，交互信息包括用戶歷史查詢、點(diǎn)擊的結(jié)果網(wǎng)頁(yè)、在網(wǎng)頁(yè)上的停留時(shí)間等，這些信息往往容易獲取，而且信息量非常大。

當(dāng)前對(duì)隱式反饋的研究主要集中在隱式正反饋上，通過(guò)用戶點(diǎn)擊的網(wǎng)頁(yè)、用戶在網(wǎng)頁(yè)上的停留時(shí)間等信息，推斷用戶的興趣。例如，如果用戶點(diǎn)擊了某篇網(wǎng)頁(yè)，則認(rèn)為該網(wǎng)頁(yè)與用戶的查詢更相關(guān)，用戶在網(wǎng)頁(yè)上的瀏覽時(shí)間越長(zhǎng)，說(shuō)明該網(wǎng)頁(yè)的內(nèi)容更有價(jià)值。相對(duì)隱式正反饋，隱式負(fù)反饋不管在信息的獲取上還是使用上，都存在較大困難。目前對(duì)隱式負(fù)反饋的研究，一般是將其與正反饋一起構(gòu)造偏序關(guān)系作為排序?qū)W習(xí)等模型的輸入，通過(guò)訓(xùn)練得到的模型對(duì)檢索結(jié)果進(jìn)行優(yōu)化。而直接同時(shí)使用隱式正負(fù)反饋進(jìn)行檢索結(jié)果優(yōu)化的工作很少，因?yàn)殡[式反饋信息中存在較多的噪音，被當(dāng)作負(fù)反饋信息的內(nèi)容并不總是與查詢不相關(guān)的，如果直接將隱式負(fù)反饋信息作用到排序模型，可能導(dǎo)致檢索質(zhì)量與僅使用隱式正反饋相比反而下降的情況。在這個(gè)背景下，本文探究如何有效地使用隱式負(fù)反饋進(jìn)行檢索結(jié)果優(yōu)化，我們采用保守的方式獲取隱式負(fù)反饋信息，僅將被點(diǎn)擊網(wǎng)頁(yè)前的未被點(diǎn)擊網(wǎng)頁(yè)當(dāng)作負(fù)反饋信息，并通過(guò)隱式正反饋信息估計(jì)用戶在未被點(diǎn)擊網(wǎng)頁(yè)上的瀏覽時(shí)間，提出帶時(shí)間因子的隱式正負(fù)反饋排序算法，探討隱式負(fù)反饋的使用以及時(shí)間因子對(duì)負(fù)反饋信息使用的影響。

本文主要研究利用同一查詢會(huì)話中的隱式反饋信息對(duì)查詢會(huì)話下一個(gè)查詢的結(jié)果進(jìn)行優(yōu)化，查詢會(huì)話定義為用戶為滿足某個(gè)信息需求與檢索系統(tǒng)進(jìn)行的一系列交互過(guò)程。本文利用的隱式正負(fù)反饋信息特指查詢會(huì)話中被點(diǎn)擊的網(wǎng)頁(yè)和位于被點(diǎn)擊網(wǎng)頁(yè)前的未被點(diǎn)擊網(wǎng)頁(yè)。此外，我們還使用了用戶在被點(diǎn)擊網(wǎng)頁(yè)上的瀏覽時(shí)間以及用戶在未被點(diǎn)擊網(wǎng)頁(yè)上的可能停留時(shí)間?？紤]到隱式反饋信息自身存在的噪聲，并且基于檢索系統(tǒng)返回結(jié)果中位置越靠后的網(wǎng)頁(yè)越不相關(guān)的假設(shè)，我們僅使用被點(diǎn)擊網(wǎng)頁(yè)前的未被點(diǎn)擊網(wǎng)頁(yè)作為隱式負(fù)反饋信息；同時(shí)，根據(jù)用戶提交查詢的時(shí)刻、用戶點(diǎn)擊網(wǎng)頁(yè)的時(shí)刻和用戶離開網(wǎng)頁(yè)的時(shí)刻來(lái)估計(jì)用戶在未被點(diǎn)擊網(wǎng)頁(yè)上的瀏覽時(shí)間，提出統(tǒng)一的帶時(shí)間因子的隱式正負(fù)反饋排序算法。

本文的貢獻(xiàn)在于挖掘隱式負(fù)反饋信息，提出隱式負(fù)反饋信息的時(shí)間因子的計(jì)算方法，探究隱式負(fù)反饋信息的使用以及時(shí)間因子對(duì)負(fù)反饋信息的影響，并提出帶時(shí)間因子的隱式正負(fù)反饋排序算法。在TREC Session數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提算法的有效性，帶時(shí)間因子的隱式正負(fù)反饋排序算法相對(duì)原始查詢結(jié)果約有80%的提升，相對(duì)只考慮隱式正反饋信息的排序算法約有10%的提升。

本文余下章節(jié)組織如下，第二節(jié)介紹相關(guān)工作;第三節(jié)探究隱式正負(fù)反饋信息的提取以及其上時(shí)間因子的計(jì)算;第四節(jié)提出帶時(shí)間因子的隱式反饋排序算法;第五節(jié)介紹實(shí)驗(yàn)數(shù)據(jù)集、評(píng)價(jià)指標(biāo)選擇，并驗(yàn)證本文所提算法的有效性;第六節(jié)是對(duì)本文的總結(jié)及下一步研究的方向。

2 相關(guān)工作

常用的隱式反饋信息包括歷史查詢和點(diǎn)擊流數(shù)據(jù)，其中，點(diǎn)擊流數(shù)據(jù)已被多數(shù)研究人員使用并證實(shí)能夠很好的提升檢索結(jié)果的相關(guān)度。文獻(xiàn)[1]對(duì)用戶瀏覽行為進(jìn)行眼球運(yùn)動(dòng)追蹤，研究并分析用戶行為，得出點(diǎn)擊行為與網(wǎng)頁(yè)相關(guān)度有很強(qiáng)相關(guān)性等結(jié)論。文獻(xiàn)[2]驗(yàn)證點(diǎn)擊流數(shù)據(jù)作為隱式反饋信息能夠達(dá)到與顯式反饋信息相當(dāng)甚至更好的結(jié)果，它根據(jù)點(diǎn)擊流數(shù)據(jù)采用一定策略產(chǎn)生pairwise排序?qū)W習(xí)模型需要的網(wǎng)頁(yè)對(duì)，與直接使用人工標(biāo)注的網(wǎng)頁(yè)相關(guān)度學(xué)習(xí)得到的模型進(jìn)行對(duì)比，發(fā)現(xiàn)兩者效果相當(dāng)。

用戶在被點(diǎn)擊網(wǎng)頁(yè)上的瀏覽時(shí)間也被廣泛研究，然而對(duì)于瀏覽時(shí)間與網(wǎng)頁(yè)相關(guān)度的相關(guān)性卻頗有爭(zhēng)議。Kelly[3]指出網(wǎng)頁(yè)瀏覽(展示)時(shí)間與網(wǎng)頁(yè)相關(guān)度之間沒(méi)有普遍的直接關(guān)系，在他們的工作中，瀏覽時(shí)間表示為在同一話題下用戶的平均瀏覽時(shí)間。而Halabi[4]則指出對(duì)給定的用戶在某一查詢會(huì)話中，瀏覽時(shí)間反映著用戶對(duì)網(wǎng)頁(yè)的興趣，用戶在網(wǎng)頁(yè)上停留的時(shí)間越長(zhǎng)，說(shuō)明該網(wǎng)頁(yè)與用戶的需求可能更相關(guān)。鑒于他們對(duì)瀏覽時(shí)間的度量方式不同，我們并不認(rèn)為他們的結(jié)論存在沖突。由于我們的實(shí)驗(yàn)設(shè)置與Halabi的類似，都是研究給定用戶在查詢會(huì)話中的隱式反饋信息，因此我們假設(shè)用戶在網(wǎng)頁(yè)上停留的時(shí)間越長(zhǎng)，該網(wǎng)頁(yè)更相關(guān)。

在TREC Session 2011任務(wù)中，文獻(xiàn)[5]使用被點(diǎn)擊網(wǎng)頁(yè)的瀏覽時(shí)間以及待排序網(wǎng)頁(yè)與被點(diǎn)擊網(wǎng)頁(yè)的相似度預(yù)測(cè)用戶在待排序網(wǎng)頁(yè)上的瀏覽時(shí)間，進(jìn)而根據(jù)該時(shí)間進(jìn)行排序的算法取得了第一的好成績(jī)，其引用的方法來(lái)自SongHuaXu等在文獻(xiàn)[6]中提出的基于用戶瀏覽時(shí)間的網(wǎng)頁(yè)排序算法。然而文獻(xiàn)[5]和文獻(xiàn)[6]只使用了被點(diǎn)擊網(wǎng)頁(yè)的信息，本文在他們工作的基礎(chǔ)上進(jìn)一步考慮未被點(diǎn)擊網(wǎng)頁(yè)的信息，并估計(jì)其瀏覽時(shí)間，提出統(tǒng)一的帶時(shí)間因子的隱式正負(fù)反饋排序算法，更好的提升檢索結(jié)果的相關(guān)度。

另外，文獻(xiàn)[7]通過(guò)建模隱式反饋信息，得到一個(gè)決策樹模型用于判斷網(wǎng)頁(yè)的有效性，并將同一查詢會(huì)話中預(yù)測(cè)為有效網(wǎng)頁(yè)中詞頻最高的前15個(gè)詞和預(yù)測(cè)為無(wú)效網(wǎng)頁(yè)中詞頻最高的前十個(gè)詞作為查詢擴(kuò)展，添加到查詢會(huì)話的倒數(shù)第二個(gè)查詢。然而，他們的實(shí)驗(yàn)結(jié)果顯示添加了無(wú)效網(wǎng)頁(yè)信息的算法比單純使用有效網(wǎng)頁(yè)的算法效果更差。雖然對(duì)隱式負(fù)反饋信息的使用方法不同，本文在未考慮時(shí)間因子的情況下，單純使用隱式正負(fù)反饋信息的效果遠(yuǎn)差于只使用隱式正反饋信息的效果。但通過(guò)引入時(shí)間因子，檢索效果得到了顯著提升，在TREC Session 2011和2012數(shù)據(jù)集上的結(jié)果都驗(yàn)證了時(shí)間因子對(duì)排序結(jié)果的影響。

3 時(shí)間因子定義

本文利用同一查詢會(huì)話中的隱式正負(fù)反饋信息，即被點(diǎn)擊網(wǎng)頁(yè)與位于被點(diǎn)擊網(wǎng)頁(yè)前的未被點(diǎn)擊網(wǎng)頁(yè)，同時(shí)考慮用戶瀏覽時(shí)間，挖掘用戶在未被點(diǎn)擊網(wǎng)頁(yè)上的瀏覽時(shí)間，對(duì)查詢會(huì)話下一個(gè)查詢的結(jié)果進(jìn)行優(yōu)化。下面先簡(jiǎn)要介紹查詢會(huì)話包括的信息以及本文使用的隱式正負(fù)反饋信息，然后探討時(shí)間因子的表示與計(jì)算。

3.1 查詢會(huì)話構(gòu)成

查詢會(huì)話，定義為用戶為滿足某個(gè)信息需求與檢索系統(tǒng)進(jìn)行的一系列交互，每個(gè)交互包括用戶查詢、該查詢提交的時(shí)刻、檢索系統(tǒng)返回的網(wǎng)頁(yè)集、用戶點(diǎn)擊的網(wǎng)頁(yè)、用戶進(jìn)入被點(diǎn)擊網(wǎng)頁(yè)以及離開被點(diǎn)擊網(wǎng)頁(yè)的時(shí)刻等信息。

3.2 隱式正負(fù)反饋信息

隱式反饋技術(shù)利用用戶行為來(lái)理解用戶的興趣和偏好，本文研究的用戶行為包括用戶點(diǎn)擊了哪些網(wǎng)頁(yè)以及在網(wǎng)頁(yè)上的停留時(shí)間。我們假設(shè)用戶點(diǎn)擊的網(wǎng)頁(yè)比未被點(diǎn)擊的網(wǎng)頁(yè)更相關(guān)，即用戶在瀏覽檢索結(jié)果時(shí)，趨向于點(diǎn)擊他們感興趣的網(wǎng)頁(yè)，也就是與他們的信息需求相關(guān)的網(wǎng)頁(yè)。本文研究的隱式正反饋信息就是指用戶點(diǎn)擊的網(wǎng)頁(yè)。

我們假設(shè)用戶瀏覽結(jié)果網(wǎng)頁(yè)集時(shí)遵循自上而下的行為，于是，如果用戶點(diǎn)擊了第i+1個(gè)網(wǎng)頁(yè)卻沒(méi)有點(diǎn)擊第i個(gè)網(wǎng)頁(yè)，我們有理由相信第i個(gè)網(wǎng)頁(yè)的內(nèi)容很可能與用戶需求不符?；谶@個(gè)觀察，我們使用被點(diǎn)擊網(wǎng)頁(yè)前的未被點(diǎn)擊網(wǎng)頁(yè)作為隱式負(fù)相關(guān)反饋，與正反饋信息一起參與到排序計(jì)分。

當(dāng)然，選擇隱式負(fù)反饋信息的策略還有很多，例如選擇與被點(diǎn)擊網(wǎng)頁(yè)相似度小的未被點(diǎn)擊網(wǎng)頁(yè)，使用最后一個(gè)被點(diǎn)擊網(wǎng)頁(yè)前的所有網(wǎng)頁(yè)等?？紤]到隱式負(fù)反饋信息使用的難度(來(lái)自自身的噪聲)及其對(duì)檢索結(jié)果影響的不穩(wěn)定性，本文采用較為保守的策略，僅使用被點(diǎn)擊網(wǎng)頁(yè)前的一個(gè)未被點(diǎn)擊網(wǎng)頁(yè)作為隱式負(fù)反饋信息。例如，用戶點(diǎn)擊了第五和第八個(gè)網(wǎng)頁(yè)，此時(shí)我們選擇第四和第七個(gè)網(wǎng)頁(yè)作為負(fù)反饋信息；如果用戶點(diǎn)擊了第三和第四這兩個(gè)網(wǎng)頁(yè)，我們選擇第二個(gè)網(wǎng)頁(yè)作為負(fù)反饋信息。

3.3 時(shí)間因子計(jì)算

用戶點(diǎn)擊網(wǎng)頁(yè)后在其上的瀏覽時(shí)間，一定程度上反映了網(wǎng)頁(yè)內(nèi)容對(duì)用戶的吸引程度，于是，我們假設(shè)用戶在網(wǎng)頁(yè)上的瀏覽時(shí)間越長(zhǎng)，該網(wǎng)頁(yè)可能更相關(guān)。用戶在點(diǎn)擊網(wǎng)頁(yè)上的瀏覽時(shí)間一般比較容易得到，而在未被點(diǎn)擊網(wǎng)頁(yè)上的瀏覽時(shí)間很難顯示得到。本文提出估計(jì)用戶在未被點(diǎn)擊網(wǎng)頁(yè)上瀏覽時(shí)間的方法，挖掘隱式負(fù)反饋信息對(duì)用戶偏好的作用，統(tǒng)一了隱式正負(fù)反饋信息在檢索結(jié)果排序中的使用。

被點(diǎn)擊網(wǎng)頁(yè)的瀏覽時(shí)間從查詢會(huì)話的數(shù)據(jù)可以直接計(jì)算得到，式(1)使用用戶離開網(wǎng)頁(yè)的時(shí)刻與進(jìn)入網(wǎng)頁(yè)的時(shí)刻之差計(jì)算用戶在網(wǎng)頁(yè)上的停留時(shí)間，Cki表示第k次交互中被點(diǎn)擊的檢索結(jié)果排序?yàn)閕的網(wǎng)頁(yè)。

(1)

采用3.2節(jié)中隱式負(fù)反饋信息的提取策略，能夠很方便的估計(jì)用戶在未被點(diǎn)擊網(wǎng)頁(yè)上的瀏覽時(shí)間，這里估計(jì)的時(shí)間不是在網(wǎng)頁(yè)內(nèi)容頁(yè)面上的停留時(shí)間，而是在檢索系統(tǒng)展示的網(wǎng)頁(yè)的標(biāo)題跟摘要上的瀏覽時(shí)間，計(jì)算方法如式(2)所示，其中，Ik表示查詢會(huì)話中的第k個(gè)交互，Uki為第k個(gè)交互中檢索結(jié)果位置為i的未被點(diǎn)擊網(wǎng)頁(yè)。

(2)

另外，考慮網(wǎng)頁(yè)在檢索結(jié)果中的排序以及用戶瀏覽行為，位置越靠前的網(wǎng)頁(yè)與查詢?cè)谀承┬再|(zhì)上可能更相關(guān)，用戶也比較傾向于瀏覽位置靠前的網(wǎng)頁(yè)。于是，在用戶瀏覽時(shí)間的基礎(chǔ)上考慮網(wǎng)頁(yè)在結(jié)果集中位置的因素，得到最終的網(wǎng)頁(yè)時(shí)間因子計(jì)算如式(3)所示。

(3)

其中，γ、β、τ為參數(shù)，γ和β用來(lái)控制用戶瀏覽時(shí)間在時(shí)間因子上的比例，γ取正實(shí)數(shù)，β取負(fù)實(shí)數(shù)用于表示隱式正負(fù)反饋信息的不同作用。參數(shù)τ用于控制網(wǎng)頁(yè)序的影響。

4 帶時(shí)間因子的隱式反饋排序算法

本節(jié)研究如何利用第三節(jié)得到的隱式正負(fù)反饋信息和時(shí)間因子達(dá)到提高檢索結(jié)果質(zhì)量的目的。隱式反饋信息的使用一般有兩種，將隱式反饋信息獨(dú)立作用于檢索結(jié)果進(jìn)行重新排序，或者將隱式反饋信息直接集成到排序算法中。本文采用前一種方法，利用隱式反饋信息對(duì)查詢會(huì)話下一個(gè)查詢的結(jié)果進(jìn)行重排序。

4.1 帶時(shí)間因子的隱式正反饋算法

僅考慮隱式正反饋信息，使用與文獻(xiàn)[5-6]類似的排序算法，得到帶時(shí)間因子的隱式正反饋算法TIPF(TimedImplicitPositiveFeedback)，對(duì)查詢會(huì)話最后一個(gè)查詢的結(jié)果使用式(5)進(jìn)行重新排序。

(4)

(5)

4.2 帶時(shí)間因子的隱式正負(fù)反饋算法

在TIPF的基礎(chǔ)上，進(jìn)一步考慮隱式負(fù)反饋信息，得到TIPNF(TimedImplicitPositiveandNegativeFeedback)算法，最后按式(7)計(jì)算的分?jǐn)?shù)對(duì)初始結(jié)果進(jìn)行重新排序。其中TopkNScore(Qm,D)由集合NegativeScore(Qm,D)中數(shù)值最大的N個(gè)元素組成。

(6)

(7)

通過(guò)估計(jì)隱式負(fù)反饋信息上的時(shí)間因子，式(7)將正負(fù)反饋信息很好的統(tǒng)一了起來(lái)，TIPNF顯示了隱式負(fù)反饋信息使用的新方法。

通過(guò)取TopN篇網(wǎng)頁(yè)的和能從一定程度上降低數(shù)據(jù)噪聲對(duì)模型穩(wěn)定性的影響。例如，如果用戶在瀏覽某篇網(wǎng)頁(yè)時(shí)由于各種原因可能臨時(shí)離開，于是最后獲取到的瀏覽時(shí)間遠(yuǎn)大于實(shí)際值，導(dǎo)致取Top1進(jìn)行計(jì)算排序時(shí)可能把不相關(guān)的網(wǎng)頁(yè)排到很靠前的位置。實(shí)驗(yàn)結(jié)果也證實(shí)，取TopN時(shí)的效果比Top1好很多。

5 實(shí)驗(yàn)分析

我們使用TREC Session的數(shù)據(jù)，通過(guò)多組對(duì)比實(shí)驗(yàn)驗(yàn)證TIPNF算法的有效性，實(shí)驗(yàn)結(jié)果評(píng)價(jià)指標(biāo)用的是ERR[8](Expected Reciprocal Rank)，5.2節(jié)中我們將詳細(xì)討論選擇ERR作為最終評(píng)價(jià)指標(biāo)的原因。實(shí)驗(yàn)結(jié)果顯示TIPNF能有效地提高檢索結(jié)果的質(zhì)量。

5.1 測(cè)試數(shù)據(jù)集

TREC Session原始語(yǔ)料為clueweb09數(shù)據(jù)，我們使用其中的英語(yǔ)語(yǔ)料，共2TB的壓縮數(shù)據(jù)，10億篇網(wǎng)頁(yè)。我們分別在TRECSession 2011和TREC Session 2012年的數(shù)據(jù)上驗(yàn)證TIPNF算法的有效性。TREC Session 2011提供了76個(gè)會(huì)話信息，其中有12個(gè)會(huì)話沒(méi)有點(diǎn)擊信息，17個(gè)會(huì)話的被點(diǎn)擊網(wǎng)頁(yè)沒(méi)有對(duì)應(yīng)的未被點(diǎn)擊網(wǎng)頁(yè)，所以，最終用于實(shí)驗(yàn)的會(huì)話一共有47個(gè)。TREC Session 2012共有98個(gè)會(huì)話信息，其中有26個(gè)會(huì)話沒(méi)有點(diǎn)擊信息，26個(gè)會(huì)話的被點(diǎn)擊網(wǎng)頁(yè)沒(méi)有對(duì)應(yīng)的未被點(diǎn)擊網(wǎng)頁(yè)，最終用于實(shí)驗(yàn)的會(huì)話共有46個(gè)。

每個(gè)查詢會(huì)話有一個(gè)特定的任務(wù)，用戶根據(jù)該任務(wù)構(gòu)造查詢與檢索系統(tǒng)進(jìn)行一系列交互。TREC Session提供了每個(gè)交互中用戶提交查詢的時(shí)刻、檢索系統(tǒng)返回的網(wǎng)頁(yè)集、用戶進(jìn)入和離開網(wǎng)頁(yè)的時(shí)刻等信息。檢索結(jié)果采用五級(jí)相關(guān)度進(jìn)行評(píng)判，分別是-2,0,1,2,3，-2表示垃圾網(wǎng)頁(yè)，0表示不相關(guān)，1表示相關(guān)，2表示高度相關(guān)，3表示精確命中。

5.2 評(píng)價(jià)指標(biāo)

檢索系統(tǒng)常用的評(píng)價(jià)指標(biāo)有Precision、Recall、F-score、MAP、DCG[9]、ERR等，DCG和ERR常用于評(píng)價(jià)多級(jí)標(biāo)注結(jié)果。此次實(shí)驗(yàn)中我們采用ERR(Expected Reciprocal Rank)作為最終的評(píng)價(jià)指標(biāo)，下面先簡(jiǎn)單介紹ERR和DCG的區(qū)別，然后解釋選擇ERR的原因。

DCG(Discounted Cumulative Gain)的計(jì)算如式(8)所示，其中g(shù)i為第i個(gè)網(wǎng)頁(yè)的相關(guān)度。從式(8)可以看到，DCG對(duì)每個(gè)結(jié)果網(wǎng)頁(yè)采用疊加的方式計(jì)算最終檢索的質(zhì)量，這使得每個(gè)網(wǎng)頁(yè)對(duì)最終檢索質(zhì)量的貢獻(xiàn)僅與網(wǎng)頁(yè)本身的相關(guān)度以及網(wǎng)頁(yè)在檢索結(jié)果中的位置有關(guān)，而與位于該網(wǎng)頁(yè)之前的其他網(wǎng)頁(yè)的相關(guān)度無(wú)關(guān)。

(8)

然而，用戶實(shí)際瀏覽檢索結(jié)果時(shí)，如果第i-1個(gè)位置的網(wǎng)頁(yè)很相關(guān)，那么用戶的信息需求可能得到滿足，從而不會(huì)去查看第i個(gè)網(wǎng)頁(yè)。例如，在5.1節(jié)中描述的五級(jí)相關(guān)度下評(píng)價(jià)兩個(gè)檢索結(jié)果，第一個(gè)檢索結(jié)果為相關(guān)度均為1的20個(gè)網(wǎng)頁(yè)，第二個(gè)檢索結(jié)果中第一個(gè)網(wǎng)頁(yè)的相關(guān)度為3，剩余19個(gè)網(wǎng)頁(yè)的相關(guān)度均為-2，此時(shí)，DCG計(jì)算的結(jié)果認(rèn)為第一個(gè)檢索結(jié)果質(zhì)量更高。但是，第二個(gè)檢索結(jié)果中的第一個(gè)網(wǎng)頁(yè)已經(jīng)完全滿足了用戶的信息需求，用戶可能不會(huì)繼續(xù)往下瀏覽；而如果瀏覽第一個(gè)檢索結(jié)果，用戶可能需要在看完全部20個(gè)網(wǎng)頁(yè)后才能找到其需要的全部信息。

ERR則建模用戶的這種瀏覽行為，彌補(bǔ)了DCG的不足。ERR采用級(jí)聯(lián)瀏覽模型來(lái)描述用戶行為，用戶自上而下瀏覽檢索結(jié)果時(shí)，在第i篇網(wǎng)頁(yè)以概率R(i)得到滿足，以1-R(i)的概率繼續(xù)瀏覽下一篇網(wǎng)頁(yè)。其計(jì)算公式如式(11)所示。

(9)

(10)

(11)

其中，gi為檢索結(jié)果中第i個(gè)網(wǎng)頁(yè)的相關(guān)度，g為網(wǎng)頁(yè)的相關(guān)度，實(shí)驗(yàn)中使用TREC官方對(duì)檢索結(jié)果的多級(jí)標(biāo)注，分別是-2,0,1,2,3，式(9)中的gmax為多級(jí)標(biāo)注中的最大值，在本實(shí)驗(yàn)中，gmax取值為3。

本文提出的TIPNF算法使用的假設(shè)與ERR類似，TIPNF假設(shè)用戶自上而下瀏覽網(wǎng)頁(yè)，認(rèn)為被點(diǎn)擊網(wǎng)頁(yè)前的未被點(diǎn)擊網(wǎng)頁(yè)與查詢不相關(guān)，與用戶看了未被點(diǎn)擊網(wǎng)頁(yè)信息需求沒(méi)得到滿足繼續(xù)往下瀏覽的行為一致?；谏鲜鲈颍覀?cè)趯?shí)驗(yàn)中主要采用ERR評(píng)價(jià)所提出算法的有效性，當(dāng)然，我們也給出了nDGC@10的評(píng)價(jià)結(jié)果。

5.3 時(shí)間因子統(tǒng)計(jì)

本節(jié)我們以TRECSession2011為例分析用戶在點(diǎn)擊網(wǎng)頁(yè)上的瀏覽時(shí)間、在未點(diǎn)擊網(wǎng)頁(yè)上估計(jì)的瀏覽時(shí)間以及對(duì)應(yīng)的時(shí)間因子。

圖1是隱式正反饋信息即用戶在被點(diǎn)擊網(wǎng)頁(yè)上的瀏覽時(shí)間和按式(3)得到的時(shí)間因子的分布，被點(diǎn)擊網(wǎng)頁(yè)共151個(gè)。從圖1可以看到，大部分瀏覽時(shí)間在100秒以內(nèi)，少部分需要100到200秒，與我們實(shí)際使用搜索引擎時(shí)的瀏覽時(shí)間接近，其中只有少數(shù)幾個(gè)網(wǎng)頁(yè)的瀏覽時(shí)間超過(guò)300秒，我們仔細(xì)查看了這些網(wǎng)頁(yè)，發(fā)現(xiàn)這些網(wǎng)頁(yè)內(nèi)容的長(zhǎng)度與其他網(wǎng)頁(yè)差不多，據(jù)此判斷為噪聲點(diǎn)，原因可能是前文提到的用戶臨時(shí)有事離開導(dǎo)致時(shí)間記錄有偏差。由于只有極少數(shù)網(wǎng)頁(yè)的時(shí)間可能有偏差，實(shí)驗(yàn)中我們并不對(duì)其做特殊處理。實(shí)驗(yàn)時(shí)式(3)中的γ和τ分別取值0.1和0.2，由于隱式正反饋時(shí)間因子中網(wǎng)頁(yè)序部分只用來(lái)對(duì)時(shí)間因子進(jìn)行細(xì)微的調(diào)整，所以圖中被點(diǎn)擊網(wǎng)頁(yè)時(shí)間因子的分布和實(shí)際瀏覽時(shí)間的分布基本一致。

同樣的，我們?cè)趫D2中展示了隱式負(fù)反饋信息即未被點(diǎn)擊網(wǎng)頁(yè)的估計(jì)瀏覽時(shí)間和時(shí)間因子分布。滿足我們的隱式負(fù)反饋信息設(shè)定條件的網(wǎng)頁(yè)共90個(gè)，通過(guò)統(tǒng)計(jì)得到估計(jì)的瀏覽時(shí)間大部分集中在七秒左右，部分高達(dá)十幾秒，這相對(duì)用戶實(shí)際查看網(wǎng)頁(yè)結(jié)果的標(biāo)題和摘要的時(shí)間偏高?？赡茉蛴袃煞矫妫皇怯脕?lái)計(jì)算的起止時(shí)間包含系統(tǒng)響應(yīng)時(shí)間和頁(yè)面加載時(shí)間;另外一個(gè)是因?yàn)橛脩舫鲇趯?shí)驗(yàn)數(shù)據(jù)采集的目的特別仔細(xì)的瀏覽了每個(gè)結(jié)果網(wǎng)頁(yè)的標(biāo)題和摘要，同時(shí)思考需不需要點(diǎn)擊等，導(dǎo)致瀏覽時(shí)間整體偏高。我們通過(guò)對(duì)式(3)使用較小的β值來(lái)降低估計(jì)時(shí)間偏高的影響，TRECSession2011數(shù)據(jù)上β和τ分別取值-0.001和0.2。

5.4TIPNF算法效果

圖1 TREC Session 2011隱式正反饋時(shí)間分析

圖2 TREC Session 2011隱式負(fù)反饋時(shí)間分析

我們用查詢會(huì)話的下一個(gè)查詢與網(wǎng)頁(yè)的BM25得分作為基準(zhǔn)參照，同時(shí)比較隱式正負(fù)反饋算法在是否考慮時(shí)間因子條件下對(duì)檢索性能的影響，驗(yàn)證所提出算法的有效性。其中，TIPF算法是文獻(xiàn)[5]算法的改進(jìn)，文獻(xiàn)[5]使用的算法在TRECSession2011中取得了第一的成績(jī)。

只考慮隱式正反饋信息，針對(duì)式(3)，對(duì)是否使用時(shí)間因子，可以得到IPF(ImplicitPositive-Feedback)和TIPF(TimedImplicitPositiveFeedback)。同樣的，考慮隱式正負(fù)反饋信息時(shí)，可以得到IPNF(ImplicitPositiveandNegativeFeedback)和TIPNF(TimedImplicitPositiveandNegativeFeedback)。上述不同組合得到的算法在TRECSession2011和TRECSession2012數(shù)據(jù)集上檢索結(jié)果的ERR值如表1、表2所示。其中，BM25參數(shù)k1和b取值分別為0.8、0.25，本文算法參數(shù)γ、τ和N取值為0.1、0.2、5，TRECSession2011上參數(shù)β取值為-0.001，TRECSession2012上參數(shù)β取值為-0.28。

表1 TREC Session 2011數(shù)據(jù)測(cè)試結(jié)果

表2 TREC Session 2012數(shù)據(jù)測(cè)試結(jié)果

可以看到，隱式正反饋信息能很好的提升檢索的性能，這與大多數(shù)研究結(jié)果一致。比較IPF和TIPF，發(fā)現(xiàn)時(shí)間因子對(duì)隱式正反饋信息提升的效果不是很明顯，但它們?cè)诓煌笜?biāo)上的表現(xiàn)都很穩(wěn)定。比較IPF和IPNF算法，不考慮時(shí)間因子的情況下，IPNF雖然相對(duì)BM25有顯著的提高，卻比IPF低了不少，原因可能在于IPNF對(duì)隱式負(fù)反饋信息的使用比較粗糙，沒(méi)能很好利用隱式負(fù)反饋信息。對(duì)比TIPNF和其他算法，TIPNF在各個(gè)ERR指標(biāo)上都達(dá)到最大值，在評(píng)價(jià)指標(biāo)ERR上，TIPNF相對(duì)BM25提高了約80%，在TREC Session 2012數(shù)據(jù)集上相對(duì)TIPF提高了高達(dá)10%的性能。這驗(yàn)證了本文提出的帶時(shí)間因子的隱式正負(fù)反饋算法的有效性。

6 總結(jié)

本文研究了隱式負(fù)反饋信息在提高信息檢索結(jié)果質(zhì)量上的應(yīng)用，將查詢會(huì)話中被點(diǎn)擊網(wǎng)頁(yè)前的未被點(diǎn)擊網(wǎng)頁(yè)作為隱式負(fù)反饋信息，通過(guò)引入時(shí)間因子，估計(jì)用戶在未被點(diǎn)擊網(wǎng)頁(yè)的標(biāo)題和摘要上的瀏覽時(shí)間，推斷隱式負(fù)反饋信息與用戶興趣和行為的關(guān)系，從而優(yōu)化檢索結(jié)果的質(zhì)量。在TREC Session 2011和TREC Session 2012數(shù)據(jù)集上，我們驗(yàn)證了本文提出的帶時(shí)間因子的隱式正負(fù)反饋算法TIPNF的有效性。

本文度量網(wǎng)頁(yè)相似度時(shí)只嘗試了余弦相似度，而SongHuaXu等在文獻(xiàn)[6]中指出，在他們的工作中網(wǎng)頁(yè)相似度度量方式的選擇對(duì)結(jié)果有關(guān)鍵的影響，因此，在今后的工作中，我們會(huì)嘗試不同的網(wǎng)頁(yè)相似度度量方式，討論TIPNF算法的魯棒性。另外，我們將研究如何將隱式反饋信息融入到檢索排序模型中，而不是本文使用的直接對(duì)檢索結(jié)果進(jìn)行重新排序。最后，時(shí)間因子的估計(jì)和使用方式也是一個(gè)有待繼續(xù)探索的問(wèn)題。

[1] Kanoulas E, Carterette B, Hall M, et al. Session track 2011 overview[C]//Proceedings of the 20th Text REtrieval Conference Notebook Proceedings (TREC 2011). 2011.

[2] Liu T, Zhang C, Gao Y, et al. BUPT_WILDCAT at TREC 2011 Session Track[R].

[3] Dou Z, Song R, Yuan X, et al. Are click-through data adequate for learning web search rankings?[C]//Proceedings of the 17th ACM conference on Information and knowledge management, 2008: 73-82.

[4] Xu S, Zhu Y, Jiang H, et al. A user-oriented webpage ranking algorithm based on user attention time[C]//Proceedings of the AAAI, 2008： 1255-1260.

[5] Joachims T, Granka L, Pan B, et al. Accurately interpreting clickthrough data as implicit feedback[C]//Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, 2005： 154-161.

[6] Kubat M, Tapia M. Time spent on a web page is sufficient to infer a user’s interest[C]//Proceedings of the IASTED EuropeanConference on Proceedings of the IASTED European Conference: internet and multimedia systems and applications, 2007： 41-46.

[7] Liu C, Belkin N J, Cole M J. Personalization of search results using interaction behaviors in search sessions[C]//Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval, 2012： 205-214.

[8] Kelly D, Belkin N J. Display time as implicit feedback: understanding task effects[C]//Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, 2004： 377-384.

[9] Chapelle O, Metlzer D, Zhang Y, et al. Expected reciprocal rank for graded relevance[C]//Proceedings of the 18th ACM conference on Information and knowledge management, 2009： 621-630.

[10] J?rvelin K, Kek?l?inen J. IR evaluation methods for retrieving highly relevant documents[C]//Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, ACM, 2000： 41-48.

[11] Zhang B, Guan Y, Sun H, et al. Survey of user behaviors as implicit feedback[C]//Proceedings of the Computer, Mechatronics, Control and Electronic Engineering (CMCE), 2010 International Conference on IEEE, 2010: 345-348.

[12] 王斌.信息檢索導(dǎo)論[M]，北京：人民郵電出版社，2010: 1-2.

Exploration of Implicit Negative Feedback with Time Factorin Search Session

CHEN Zhenhong1,2, YU Xiaoming1, LIU Yue1, CHENG Xueqi1

(1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China; 2. University of Chinese Academy of Sciences, Beijing 100190, China)

Implicit relevance feedback has been used to improve the performance of the retrieve system. In Contrast to the recent, most of the related work focusing on implicit positive feedback, this paperinvestigated the usefulness of combining both implicit positive and negative feedback with time factor. The implicit negative feedback used in this paper is the unclicked document before the clicked document in the same search session. By estimating the time spent on the title and snippet of the unclicked document, the time factor is introduced to infer the relationships between user’s interest and behaviors. Thus, a unified time factor model called TIPNF is proposed to use both implicit positive and negative feedback to improve the performance of the retrieve system. Experiments on TREC Session 2011 and 2012 verify the effectiveness and stabilization of the TIPNF.

search session; implicit negative feedback; time factor; rank

陳振宏(1988—)，碩士，主要研究領(lǐng)域?yàn)榇笠?guī)模機(jī)器學(xué)習(xí)、分布式系統(tǒng)、社交網(wǎng)絡(luò)。E?mail：chenzhenhong@software．ict．a(chǎn)c．cn俞曉明(1977—)，博士，高級(jí)工程師，主要研究領(lǐng)域?yàn)榛ヂ?lián)網(wǎng)搜索與數(shù)據(jù)挖掘。E?mail：yuxiaoming@software．ict．a(chǎn)c．cn劉悅(1971—)，博士，副研究員，主要研究領(lǐng)域?yàn)槲谋就诰颉eb搜索、復(fù)雜網(wǎng)絡(luò)分析與社會(huì)計(jì)算。E?mail：liuyue@ict．a(chǎn)c．cn

1003-0077(2016)02-0113-08

2013-06-18 定稿日期： 2013-11-15

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973)(2012CB316303，2014CB340401)；國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863)(2014AA015204，2014AA015103)；國(guó)家自然科學(xué)基金(61232010)；國(guó)家杰出青年科學(xué)基金(61425016)；中國(guó)科學(xué)院重點(diǎn)部署項(xiàng)目(KGZD-EW-T03-2)

TP

A