王超，劉奕群，馬少平

(清華大學(xué) 計(jì)算機(jī)系，北京 100084)

搜索引擎點(diǎn)擊模型綜述

王超，劉奕群，馬少平

(清華大學(xué) 計(jì)算機(jī)系，北京 100084)

搜索引擎用戶在與搜索引擎的交互過(guò)程中反映出的隱性反饋信息(主要是點(diǎn)擊行為信息)是搜索引擎用來(lái)改進(jìn)結(jié)果排序的重要影響因素。然而,由于結(jié)果位置、展現(xiàn)形式等各種因素的影響,將反饋信息直接應(yīng)用于搜索排序任務(wù)往往難以取得較好的效果。針對(duì)這一問(wèn)題,研究人員提出了構(gòu)建描述用戶點(diǎn)擊行為的點(diǎn)擊模型,并基于不同的點(diǎn)擊模型估計(jì)用戶對(duì)展現(xiàn)結(jié)果的瀏覽概率,進(jìn)而嘗試去除結(jié)果展現(xiàn)位置等因素對(duì)用戶行為的偏置性影響,以達(dá)到更好利用隱性反饋信息的目的。作為一種用戶交互信息的有效利用方法,點(diǎn)擊模型在學(xué)術(shù)界得到了充分關(guān)注, 并在工業(yè)界得到了廣泛的應(yīng)用。本文是一篇針對(duì)點(diǎn)擊模型發(fā)展過(guò)程的綜述性文章，對(duì)點(diǎn)擊模型發(fā)展過(guò)程中有代表性的多種模型進(jìn)行了介紹。

搜索引擎；信息檢索；結(jié)果排序；用戶行為分析；點(diǎn)擊模型

在這個(gè)信息爆炸的時(shí)代，搜索引擎已成為人們?cè)诨ヂ?lián)網(wǎng)的數(shù)據(jù)海洋中遨游不可或缺的工具。無(wú)論是查找信息、獲取資源還是尋求幫助、發(fā)現(xiàn)機(jī)遇，都離不開搜索引擎的指引與參考?？梢哉f(shuō)，搜索引擎已經(jīng)成為了互聯(lián)網(wǎng)中的“基礎(chǔ)設(shè)施”。根據(jù)CNNIC中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告顯示，截至 2016 年 1 月,已有82.3%的互聯(lián)網(wǎng)用戶使用搜索引擎,在互聯(lián)網(wǎng)網(wǎng)絡(luò)應(yīng)用中排名第二;而在移動(dòng)端也有 77.1% 的用戶使用移動(dòng)端搜索引擎,在移動(dòng)應(yīng)用中排名第三。由此可見,搜索引擎已成為大多數(shù)互聯(lián)網(wǎng)用戶必不可少的應(yīng)用之一,因此搜索引擎所提供的搜索結(jié)果質(zhì)量對(duì)于用戶體驗(yàn)有著極為重要的影響。

在搜索引擎對(duì)于不同搜索結(jié)果的質(zhì)量(結(jié)果相關(guān)性)進(jìn)行判斷(預(yù)測(cè))時(shí)，最為傳統(tǒng)的方法是基于結(jié)果內(nèi)容的相關(guān)性預(yù)測(cè)方法[1]，該方法通過(guò)對(duì)搜索時(shí)用戶提交的查詢?cè)~以及所有結(jié)果的文本內(nèi)容進(jìn)行處理，從中提取出有效的衡量結(jié)果相關(guān)性的特征(例如TF-IDF[2]、BM25[3]等)，從而利用上述特征或指標(biāo)來(lái)衡量不同搜索結(jié)果與查詢?cè)~之間的相關(guān)性，進(jìn)而對(duì)所有結(jié)果進(jìn)行篩選和排序。這些方法為搜索引擎系統(tǒng)快速并準(zhǔn)確地從大量結(jié)果中篩選出符合用戶真實(shí)搜索需求的結(jié)果列表提供了最為基礎(chǔ)有效的解決方案，成為了當(dāng)前搜索引擎架構(gòu)中基礎(chǔ)的模塊之一。然而上述方法并不能完美解決搜索結(jié)果相關(guān)性預(yù)測(cè)及排序等問(wèn)題，例如Lv等[4]指出，當(dāng)結(jié)果內(nèi)容信息很長(zhǎng)時(shí)，BM25指標(biāo)會(huì)變得不能正確衡量結(jié)果的相關(guān)性。因此，除了結(jié)果的內(nèi)容信息外，搜索引擎有必要引入更多的信息去更好地衡量搜索結(jié)果的相關(guān)性，從而為搜索用戶提供更好的結(jié)果排序。

由于互聯(lián)網(wǎng)網(wǎng)頁(yè)中往往包含大量超鏈接，這些超鏈接使互聯(lián)網(wǎng)網(wǎng)頁(yè)得以互相連接，從而組成了不同的網(wǎng)絡(luò)結(jié)構(gòu)。因此，一個(gè)簡(jiǎn)單的推斷是在該網(wǎng)絡(luò)結(jié)構(gòu)中，不同位置的節(jié)點(diǎn)其具有的重要性程度可能不同。所以第2種方法是利用互聯(lián)網(wǎng)網(wǎng)頁(yè)的鏈接結(jié)構(gòu)推斷不同結(jié)果的重要性[5]、可靠性[6]等，從而對(duì)不同結(jié)果的相關(guān)性有更好地估計(jì)。上述方法為搜索引擎結(jié)果相關(guān)性估計(jì)和結(jié)果排序起到了進(jìn)一步改進(jìn)的作用，同樣成為了搜索引擎的重要模塊之一。

除了上述方法外，近年來(lái)，利用互聯(lián)網(wǎng)群體智慧[7]來(lái)改善搜索結(jié)果相關(guān)性估計(jì)[8]的方法開始受到關(guān)注，并成為另一種提升搜索引擎結(jié)果相關(guān)性估計(jì)和改進(jìn)搜索引擎排序的重要方法。由于每天都有大量的用戶與搜索引擎進(jìn)行交互，這些搜索引擎用戶在與搜索引擎的交互過(guò)程中反映出的隱性反饋信息(主要是點(diǎn)擊行為信息)也是搜索引擎改進(jìn)結(jié)果排序的重要影響因素。直觀來(lái)說(shuō)，如果很多的搜索用戶在搜索同一個(gè)查詢時(shí)點(diǎn)擊了某個(gè)搜索結(jié)果，那么該搜索結(jié)果就有可能是一個(gè)相關(guān)的結(jié)果。由于每天搜索引擎都可以收集到海量的用戶隱性反饋信息，如果我們能從這些信息中挖掘出用戶對(duì)于搜索結(jié)果的真實(shí)相關(guān)性反饋，那么就可以利用上述信息對(duì)搜索引擎的相關(guān)性預(yù)測(cè)進(jìn)行更好地改進(jìn)。

然而，用戶在搜索過(guò)程中的點(diǎn)擊行為可能會(huì)受到多種因素的影響。研究表明，由于搜索用戶受到結(jié)果位置[9-10]、展現(xiàn)形式[11]、可信度[12]等各種因素的影響，將反饋信息直接應(yīng)用于結(jié)果相關(guān)性估計(jì)任務(wù)往往難以取得較好的效果。針對(duì)這一問(wèn)題，研究人員提出了構(gòu)建描述用戶點(diǎn)擊行為的點(diǎn)擊模型[13-15]來(lái)嘗試解決上述問(wèn)題。點(diǎn)擊模型是用來(lái)描述用戶從開始搜索到搜索結(jié)束過(guò)程中點(diǎn)擊行為的發(fā)生過(guò)程的模型，不同的模型會(huì)嘗試描述用戶在搜索過(guò)程中受到的不同因素的影響，以及這些影響之間的相互關(guān)聯(lián)(例如，不同的點(diǎn)擊模型會(huì)對(duì)用戶檢驗(yàn)不同位置的搜索結(jié)果的概率有不同的估計(jì)，進(jìn)而嘗試去除結(jié)果展現(xiàn)位置等因素對(duì)用戶行為的偏置性影響)，最終利用大規(guī)模的用戶點(diǎn)擊信息去推測(cè)模型中的不同影響因素所發(fā)揮的作用程度，從而更為準(zhǔn)確地估計(jì)結(jié)果的真實(shí)相關(guān)性和新頁(yè)面下用戶的點(diǎn)擊概率，達(dá)到更好利用隱性反饋信息的目的。

作為一種用戶交互信息的有效利用方法，點(diǎn)擊模型在學(xué)術(shù)界得到了充分關(guān)注，并在工業(yè)界得到了廣泛的應(yīng)用。傳統(tǒng)的點(diǎn)擊模型主要針對(duì)于傳統(tǒng)同質(zhì)化的搜索頁(yè)面(搜索頁(yè)面中的結(jié)果均采用相近的文本形式展現(xiàn)，結(jié)果之間除了文字內(nèi)容不同外并沒(méi)有明顯的展現(xiàn)形式差異)進(jìn)行設(shè)計(jì)。隨著Web2.0時(shí)代的到來(lái)，富媒體展現(xiàn)形式被越來(lái)越多地應(yīng)用于搜索交互界面，搜索結(jié)果也變得越來(lái)越異質(zhì)化[16]，這些變化使得用戶的檢驗(yàn)行為(注意力分布偏好、瀏覽順序等)發(fā)生了明顯的改變[17]，傳統(tǒng)的點(diǎn)擊模型已經(jīng)不能正確地描述用戶的真實(shí)行為，相應(yīng)的排序方法也難以取得較優(yōu)的效果。因此研究人員開始提出針對(duì)于垂直搜索結(jié)果的點(diǎn)擊模型以及針對(duì)非順序檢驗(yàn)行為的點(diǎn)擊模型。

1 基于位置的點(diǎn)擊模型

主流的點(diǎn)擊模型大都基于點(diǎn)擊模型方面最基礎(chǔ)的研究[9]，認(rèn)為用戶在瀏覽搜索引擎時(shí)采用的是沿著搜索結(jié)果列表從上到下依次瀏覽的方式，根據(jù)這個(gè)假設(shè)，用戶的瀏覽順序與搜索結(jié)果的位置順序是一致的。因此大多數(shù)的點(diǎn)擊模型都是基于位置的構(gòu)建方式(我們稱作基于位置的點(diǎn)擊模型)。另外，由于點(diǎn)擊模型中最主要的信息來(lái)源為用戶的交互信息(主要是點(diǎn)擊信息)，因此模型對(duì)于用戶行為以及結(jié)果相關(guān)性的推斷都來(lái)源于點(diǎn)擊行為。因此大多數(shù)的點(diǎn)擊模型都假設(shè)搜索頁(yè)面中的所有結(jié)果是同質(zhì)的(所有具有類似的形式,僅在內(nèi)容上有所區(qū)別，對(duì)應(yīng)到模型中即為僅在結(jié)果相關(guān)性上有所區(qū)別)，在排除結(jié)果相關(guān)性影響之后這些結(jié)果對(duì)于用戶的行為不構(gòu)成影響。

上述兩條假設(shè)成為了主流點(diǎn)擊模型的基礎(chǔ)假設(shè)，因此本部分的相關(guān)工作介紹主要介紹這些點(diǎn)擊模型相關(guān)內(nèi)容,其他的與之有所區(qū)別的點(diǎn)擊模型會(huì)在本工作與這些工作相關(guān)的章節(jié)進(jìn)行介紹。

大多數(shù)的點(diǎn)擊模型利用名為檢驗(yàn)假設(shè)(examination hypothesis)[9]的用戶行為假設(shè)來(lái)對(duì)用戶的點(diǎn)擊行為和其中蘊(yùn)含的結(jié)果反饋之間的關(guān)聯(lián)進(jìn)行建模，其具體描述為給定一個(gè)查詢?cè)~q和對(duì)應(yīng)的搜索結(jié)果列表D=通常為 10，即頁(yè)面中包含10條搜索結(jié)果。對(duì)于其中第i個(gè)結(jié)果di，該結(jié)果是否被點(diǎn)擊(Ci=1)當(dāng)且僅當(dāng)這個(gè)結(jié)果被用戶檢驗(yàn)(Ei=1)，并且這個(gè)結(jié)果是一個(gè)相關(guān)的結(jié)果(Ai=1),而相關(guān)與檢驗(yàn)則是兩個(gè)獨(dú)立的變量。

根據(jù)以上假設(shè)，一個(gè)搜索結(jié)果被點(diǎn)擊的概率可以用式(1)表示：

(1)

這樣我們?cè)谥烙脩舻狞c(diǎn)擊信息之后，通過(guò)推斷用戶的檢驗(yàn)信息，就能推斷出每個(gè)結(jié)果的真實(shí)相關(guān)性信息。圖1為檢驗(yàn)假設(shè)的模型示意圖。

圖1 檢驗(yàn)假設(shè)示意圖Fig.1 Graphical representation of the examination hypothesis

1.1 級(jí)聯(lián)模型

級(jí)聯(lián)模型[9]假設(shè)用戶的瀏覽行為是沿著搜索結(jié)果列表從上到下依次檢驗(yàn)的，當(dāng)且僅當(dāng)用戶檢驗(yàn)了某個(gè)結(jié)果并且該用戶沒(méi)有做出點(diǎn)擊該結(jié)果的行為，該用戶才會(huì)繼續(xù)檢驗(yàn)排在該結(jié)果后一位的搜索結(jié)果。其模型的示意圖如圖2所示。針對(duì)該結(jié)果的公式為

圖2 級(jí)聯(lián)模型示意圖Fig.2 Graphical representation of the cascade model (fragment)

1.2 DCM模型

由級(jí)聯(lián)模型的假設(shè)可知，該模型只能描述用戶僅有一次點(diǎn)擊的搜索情況，而實(shí)際的用戶行為中，用戶可能會(huì)發(fā)生多次點(diǎn)擊，因此Guo等[13]提出了dependency click model (DCM)模型，該模型沿用了用戶順次向下檢驗(yàn)的行為假設(shè)，同時(shí)假設(shè)當(dāng)用戶點(diǎn)擊之后仍然有一定的概率繼續(xù)下一步的瀏覽行為，其瀏覽行為描述公式為

1.3 UBM模型

接下來(lái)，Dupret等[14]提出了user browsing model (UBM)模型,如圖3所示。他們通過(guò)實(shí)驗(yàn)研究發(fā)現(xiàn)用戶檢驗(yàn)?zāi)硞€(gè)位置的結(jié)果的概率不僅和當(dāng)前該結(jié)果所處的位置相關(guān)，同時(shí)還和該結(jié)果與用戶上一次點(diǎn)擊的結(jié)果的距離有著非常重要的關(guān)聯(lián)，因此他們的模型假設(shè)：

式中：ri表示當(dāng)前該結(jié)果的位置，而di表示當(dāng)前結(jié)果和上次點(diǎn)擊的結(jié)果的位置距離。

1.4DBN模型

Chapelle等[15]提出了dynamicBayesiannetwork(DBN)模型，如圖4。該模型首次將用戶的瀏覽過(guò)程中的滿意度行為引入模型描述中。該模型假設(shè)用戶每點(diǎn)擊一條結(jié)果之后都會(huì)有一定的滿意度改變，而一旦用戶在某次點(diǎn)擊之后達(dá)到了滿意的程度，那么他/她就會(huì)停止檢驗(yàn)后續(xù)的結(jié)果并結(jié)束這次查詢：

式中：Si表示用戶點(diǎn)擊了第i個(gè)結(jié)果之后的滿意程度，λ表示了用戶不滿意的情況下繼續(xù)檢驗(yàn)后續(xù)結(jié)果的概率。

圖4 DBN模型示意圖Fig.4 Graphical representation of the dynamic Bayesian network model (fragment)

除了上述模型之外，Guo等[23]提出了clickchainmodel(CCM)模型描述用戶可能存在的略過(guò)行為；Hu等[24]嘗試區(qū)分不同查詢意圖下用戶瀏覽行為的區(qū)別，從而對(duì)已有的點(diǎn)擊模型進(jìn)行改進(jìn)；Chen等[25]提出了noise-awareclickmodel(NCM)嘗試從所有的點(diǎn)擊信息中區(qū)分哪些是用戶真實(shí)的結(jié)果相關(guān)性判斷，哪些是由于其他原因造成的不可信的點(diǎn)擊。

可以看到，以上的一系列的點(diǎn)擊模型都是基于用戶的檢驗(yàn)順序嚴(yán)格從上到下進(jìn)行一遍以及所有結(jié)果具有同質(zhì)屬性這兩個(gè)基本的假設(shè)進(jìn)行研究的。

2 針對(duì)垂直搜索結(jié)果的點(diǎn)擊模型

隨著Web2.0時(shí)代的快速發(fā)展，搜索引擎頁(yè)面正在變得越來(lái)越異質(zhì)化，大量的包含富文本信息的搜索結(jié)果被引入搜索頁(yè)面。這些搜索結(jié)果來(lái)自于搜索引擎的多個(gè)具有特定搜索目標(biāo)的子引擎，通常被稱為垂直搜索引擎。這些來(lái)自垂直搜索引擎的垂直搜索結(jié)果(例如圖片搜索引擎得到的圖片結(jié)果)往往與傳統(tǒng)的結(jié)果具有不同的展現(xiàn)形式，因此現(xiàn)今的搜索頁(yè)面上的搜索結(jié)果正在變得非常異質(zhì)化，這也使得用戶的瀏覽行為習(xí)慣和偏好可能產(chǎn)生比較大的變化。

Wang等[11]對(duì)一家中文商業(yè)搜索引擎的大規(guī)模搜索日志進(jìn)行了分析(詳細(xì)分析結(jié)果請(qǐng)見2.1小節(jié))，發(fā)現(xiàn)當(dāng)前中文搜索環(huán)境下超過(guò)80%的搜索結(jié)果頁(yè)面包含有垂直結(jié)果，并且不同展現(xiàn)形式的垂直結(jié)果對(duì)用戶的行為產(chǎn)生了很大的影響，包括對(duì)于垂直結(jié)果本身(局部影響)和對(duì)整個(gè)搜索頁(yè)面(全局影響)。因此，對(duì)于現(xiàn)今的搜索引擎來(lái)說(shuō)，考慮不同垂直結(jié)果是非常重要的因素。

他們根據(jù)中文搜索引擎常見的搜索結(jié)果對(duì)結(jié)果展現(xiàn)形式進(jìn)行了分類，如圖5所示：

1)普通結(jié)果：非垂直結(jié)果，最常見的搜索結(jié)果展現(xiàn)形式，由一條超鏈接標(biāo)題和一段文本摘要組成。

2)文本類垂直結(jié)果：由一段文本摘要和多條超鏈接標(biāo)題組成，例如新聞?lì)惢蛘甙倏祁愃阉鹘Y(jié)果。

3)多媒體類垂直結(jié)果：主要由一組多媒體組件(通常為一組圖片)組成，如視頻、圖片類搜索結(jié)果。

4)應(yīng)用類垂直結(jié)果：由嵌入搜索頁(yè)面的一組組件組成，用戶可以通過(guò)與組件交互直接得到搜索結(jié)果，例如計(jì)算匯率兌換的計(jì)算器。

圖5 不同類型垂直結(jié)果示意圖Fig.5 Different types of vertical results

2.1FCM模型

Chen等[16]最早提出了針對(duì)垂直結(jié)果的點(diǎn)擊模型，他們分析了部分垂直結(jié)果對(duì)用戶點(diǎn)擊的影響，提出了federatedclickmodel(FCM)模型，該模型假設(shè)用戶的檢驗(yàn)概率可能會(huì)受到最近的上一個(gè)垂直結(jié)果的影響(吸引假設(shè))：

式中：A表示用戶是否被垂直結(jié)果所吸引，如果用戶被垂直結(jié)果吸引A=1，那么該用戶的檢驗(yàn)其他普通結(jié)果的概率會(huì)受到一定的影響。

2.2VCM模型

Wang等[11]利用眼動(dòng)追蹤設(shè)備對(duì)用戶的搜索瀏覽行為進(jìn)行了深入的分析，他們發(fā)現(xiàn)不同展現(xiàn)類型的垂直結(jié)果對(duì)用戶的視線注視行為有著很大的影響,如圖6所示。

(a) 不含垂直結(jié)果 (b)包含多媒體垂直結(jié)果圖6 多媒體垂直結(jié)果對(duì)用戶的前兩秒視覺注視行為的影響Fig.6 The impact of multimedia vertical results on user’s first two seconds’ fixation

圖6左側(cè)為不含垂直結(jié)果的頁(yè)面，右側(cè)為包含多媒體垂直結(jié)果的頁(yè)面，熱度圖越暖色表示用戶的視覺注視越多?？梢钥吹?，當(dāng)多媒體垂直結(jié)果加入頁(yè)面后，用戶的視線被很大程度吸引，從而不再像左圖一樣自上而下遞減分布。

Wang等[11]針對(duì)用戶的瀏覽行為變化進(jìn)行了深入的分析，最終總結(jié)了4個(gè)用戶行為偏置假設(shè)：

1)吸引力偏置假設(shè)：如果有一個(gè)垂直結(jié)果在搜索結(jié)果頁(yè)面中出現(xiàn)，那么用戶有一定的概率首先檢驗(yàn)該垂直結(jié)果。

2)全局影響偏置假設(shè)：如果有一個(gè)垂直結(jié)果在搜索結(jié)果頁(yè)面中出現(xiàn)，并且用戶首先檢驗(yàn)了該垂直結(jié)果，那么用戶會(huì)對(duì)整個(gè)頁(yè)面有一個(gè)全局印象，該印象會(huì)使得用戶對(duì)普通搜索結(jié)果的檢驗(yàn)和點(diǎn)擊偏好產(chǎn)生影響。

3)首位偏置影響假設(shè)：如果有一個(gè)垂直結(jié)果在搜索結(jié)果頁(yè)面中出現(xiàn)，并且該垂直結(jié)果被排在了第1位，那么用戶就可能會(huì)更多地點(diǎn)擊該垂直結(jié)果而較少點(diǎn)擊其他結(jié)果。

4)瀏覽順序偏置影響假設(shè)：如果有一個(gè)垂直結(jié)果在搜索結(jié)果頁(yè)面中出現(xiàn)，并且用戶首先檢驗(yàn)了該垂直結(jié)果，那么用戶會(huì)在接下來(lái)回看垂直結(jié)果之前的搜索結(jié)果，回看的路徑或者回到頂端自上而下瀏覽，或者沿著自下而上的順序反序?yàn)g覽。

相應(yīng)的點(diǎn)擊模型描述為

其描述的用戶瀏覽行為決策過(guò)程可以用圖7表示。用戶在開始瀏覽時(shí)，他會(huì)有一定的機(jī)率決定是否首先去檢驗(yàn)垂直結(jié)果，如果首先檢驗(yàn)了垂直結(jié)果，那么用戶會(huì)繼續(xù)約定是否回到頁(yè)面頂端自上而下瀏覽，亦或是自下而上反序?yàn)g覽。

3 基于點(diǎn)擊順序的點(diǎn)擊模型

已有的眼動(dòng)追蹤實(shí)驗(yàn)研究工作[18]表明，搜索引擎用戶的瀏覽習(xí)慣可以分為兩種類型：深度優(yōu)先策略和寬度優(yōu)先策略。其中深度優(yōu)先策略描述用戶的檢驗(yàn)順序是順著搜索結(jié)果列表的結(jié)果序列自上而下瀏覽搜索結(jié)果并在瀏覽每個(gè)搜索結(jié)果的同時(shí)決定是否點(diǎn)擊。而寬度優(yōu)先策略則是另一種類型，它描述用戶在點(diǎn)擊搜索結(jié)果之前會(huì)預(yù)先檢驗(yàn)一系列的搜索結(jié)果，然后再在其中選擇自己最中意的若干結(jié)果點(diǎn)擊。由于根據(jù)深度優(yōu)先假設(shè)，用戶點(diǎn)擊時(shí)受到的很重要的位置偏執(zhí)影響能夠很容易被模型所考慮進(jìn)去，因此大多數(shù)的點(diǎn)擊模型[13-15]都遵從深度優(yōu)先假設(shè)，也就是用戶自上而下瀏覽一遍搜索結(jié)果列表。

圖7 VCM模型流程Fig.7 Graphical representation of the vertical click model

然而，眼動(dòng)視線追蹤實(shí)驗(yàn)研究[19]表明，僅有34%的搜索用戶的瀏覽序列是順序(自上而下)的，而有50%以上的查詢會(huì)話中用戶會(huì)發(fā)生回訪行為(自下而上的瀏覽搜索結(jié)果)或者略過(guò)的行為。因此研究人員有必要對(duì)用戶的非順序?yàn)g覽(點(diǎn)擊和檢驗(yàn))行為進(jìn)行研究。

3.1TCM模型

Xu等最先提出了名為temporalclickmodel(TCM)[20]的模型在廣告搜索中描述用戶的點(diǎn)擊行為。這個(gè)模型嘗試將所有可能的檢驗(yàn)序列全部計(jì)算出現(xiàn)概率，因此只能描述僅包含兩個(gè)結(jié)果(廣告)的頁(yè)面，所描述的非順序點(diǎn)擊行為為：用戶首先點(diǎn)擊了第2個(gè)搜索結(jié)果，然后再點(diǎn)擊了第1個(gè)搜索結(jié)果。因此這個(gè)工作很難像其他點(diǎn)擊模型一樣擴(kuò)展到描述整個(gè)搜索結(jié)果列表。

3.2POM模型

Wang等提出了名為partiallyobservableMarkovmodel(POM)[21]的點(diǎn)擊模型來(lái)描述用戶的任意瀏覽行為。POM模型將用戶的檢驗(yàn)事件當(dāng)做一個(gè)部分可觀測(cè)的隨機(jī)過(guò)程來(lái)進(jìn)行描述。其流程示意圖如圖8所示，對(duì)于一個(gè)可以觀測(cè)的點(diǎn)擊行為序列，該模型會(huì)試圖尋找所有可能的檢驗(yàn)序列并分別計(jì)算各種檢驗(yàn)序列的可能性。

(a) 觀測(cè)序列O

(b)假設(shè)序列Q1

(c)假設(shè)序列Q2)圖8 POM模型流程示意圖Fig.8 Graphical representation of the vertical click model

盡管這個(gè)模型能夠描述用戶的非順序檢驗(yàn)行為，但模型僅考慮了用戶在不同位置之間的檢驗(yàn)跳轉(zhuǎn)概率(也就是說(shuō)，不同用戶，不同查詢，不同搜索結(jié)果下用戶的檢驗(yàn)跳轉(zhuǎn)行為是一致的)，因此該模型并不能針對(duì)具體的查詢和結(jié)果給出點(diǎn)擊概率預(yù)測(cè)和結(jié)果相關(guān)性預(yù)測(cè)，并且難以在實(shí)際環(huán)境中應(yīng)用，并和已有的點(diǎn)擊模型進(jìn)行比較。

3.3PSCM模型

Wang等[22]利用眼動(dòng)視線追蹤設(shè)備對(duì)用戶的非順序?yàn)g覽行為進(jìn)行了深入的分析，在總結(jié)了用戶瀏覽行為的一般規(guī)律后提出了如下兩個(gè)用戶非順序?yàn)g覽行為假設(shè)。

1)局部檢驗(yàn)線性假設(shè)：在兩次點(diǎn)擊之間，用戶傾向于沿著點(diǎn)擊方向檢驗(yàn)結(jié)果而不再改變檢驗(yàn)方向，無(wú)論用戶的點(diǎn)擊方向是向上還是向下。

2)非一階檢驗(yàn)假設(shè)：盡管用戶在兩次點(diǎn)擊之間的檢驗(yàn)行為是局部線性有序的，但用戶并不是一個(gè)挨著一個(gè)檢驗(yàn)搜索結(jié)果，而是會(huì)略過(guò)一些搜索結(jié)果。

相應(yīng)的模型示意圖如圖9所示，點(diǎn)擊行為首先根據(jù)時(shí)間信息記錄為時(shí)間序列，接下來(lái)對(duì)于每一個(gè)點(diǎn)擊對(duì)，根據(jù)局部檢驗(yàn)線性假設(shè)，用戶在點(diǎn)擊對(duì)之間是線性的瀏覽行為，因此可以用一個(gè)基于位置點(diǎn)擊模型的子模塊來(lái)描述這個(gè)點(diǎn)擊對(duì)之間的用戶瀏覽行為。而由于用戶可能會(huì)略過(guò)一些結(jié)果，因此點(diǎn)擊對(duì)之間的所有搜索結(jié)果并不是都被用戶檢驗(yàn)，而是需要模型推斷用戶檢驗(yàn)了哪些搜索結(jié)果。

圖9 PSCM模型流程示意圖Fig.9 Graphical representation of the partially sequential click model

4 點(diǎn)擊模型開源工具及數(shù)據(jù)集

由于點(diǎn)擊模型具有很強(qiáng)的實(shí)用性，因此很多搜索引擎公司都有部分模型的內(nèi)部實(shí)現(xiàn)方案，而研究人員也針對(duì)點(diǎn)擊模型開發(fā)了一系列的開源工具實(shí)現(xiàn)：

1)ClickModelProject(https://github.com/varepsilon/clickmodels)是一個(gè)基于Python的開源點(diǎn)擊模型項(xiàng)目，本文中介紹的DCM、UBM、DBN等模型在該開源項(xiàng)目中均有實(shí)現(xiàn)。

2)PyClick(https://github.com/markovi/PyClick)是一個(gè)基于Python的開源點(diǎn)擊模型項(xiàng)目，本文中介紹的FCM、VCM等模型在該開源項(xiàng)目中均有實(shí)現(xiàn)。

3)THUIRClick(https://github.com/THUIR/PSCMModel)是一個(gè)基于Python的開源點(diǎn)擊模型項(xiàng)目，本文中介紹的TCM、POM、PSCM等模型在該開源項(xiàng)目中均有實(shí)現(xiàn)。

除了開源工具之外，業(yè)界搜索引擎公司也公布了一批公開的搜索日志資源：

1)Yandex(https://www.kaggle.com/c/yandex-personalized-web-search-challenge)是一家俄文和英文搜索引擎公司，其公布了2012年某一個(gè)月的搜索日志。

2)Sogou(http://www.sogou.com/labs/dl/q-e.html)是一家中文搜索引擎公司，其公布了2012年部分時(shí)段的搜索日志。

3)Microsoft(http://research.microsoft.com/en-us/um/people/nickcr/wscd09/)公布了2006年MSN的某一個(gè)月的搜索日志。

5 結(jié)束語(yǔ)

點(diǎn)擊模型作為一種用戶交互信息的有效利用方法，在學(xué)術(shù)界得到了充分關(guān)注，并在工業(yè)界得到了廣泛的應(yīng)用。本文主要介紹了點(diǎn)擊模型的發(fā)展過(guò)程以及不同點(diǎn)擊模型的功能。同時(shí)介紹了部分點(diǎn)擊模型研究中可用的資源。隨著大數(shù)據(jù)時(shí)代的不斷推進(jìn)，點(diǎn)擊模型作為一種有效利用搜索引擎海量用戶交互數(shù)據(jù)的方法，必將在學(xué)術(shù)界得到更為全面的研究，也將在工業(yè)界得到更為深入的應(yīng)用。

[1]ROBERTSONS,ZARAGOZAH.Theprobabilisticrelevanceframework:BM25andbeyond[M].Hanover,MA:NowPublishersInc, 2009.

[2]SPARCKJONESK.Astatisticalinterpretationoftermspecificityanditsapplicationinretrieval[J].Journalofdocumentation, 1972, 28(1): 11-21.

[3]ROBERTSONSE,WALKERS,JONESS,etal.Okapiattrec-3[Z].NistSpecialPublicationSp, 1995, 109: 109.

[4]LVY,ZHAIC.Whendocumentsareverylong,bm25fails! [C]//Proceedingsofthe34thInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.NewYork:ACM, 2011: 1103-1104.

[5]PAGEL,BRINS,MOTWANIR,etal.Thepagerankcitationranking:bringingordertotheweb[Z].Stanford:StanfordUniversity, 1999.

[6]GYONGYIZ,GARCIA-MOLINAH,PEDERSENJ.Combatingwebspamwithtrustrank[C]//Proceedingsofthe30thInternationalConferenceonVeryLargeDataBases.Toronto,Canada:VLDBEndowment, 2004: 576-587.

[7]SUROWIECKIJ.Thewisdomofcrowds[Z].Anchor, 2005.

[8]AGICHTEINE,BRILLE,DUMAISS,etal.Learninguserinteractionmodelsforpredictingwebsearchresultpreferences[C]//Proceedingsofthe29thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.NewYork,NY,USA:ACM, 2006： 3-10.

[9]CRASWELLN,ZOETERO,TAYLORM,etal.Anexperimentalcomparisonofclickposition-biasmodels[C]//Proceedingsofthe2008InternationalConferenceonWebSearchandDataMining.NewYork,NY,USA:ACM, 2008: 87-94.

[10]JOACHIMST,GRANKAL,PANB,etal.Accuratelyinterpretingclickthroughdataasimplicitfeedback[C]//Proceedingsofthe28thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.NewYork,NY,USA:ACM, 2005: 154-161.

[11]WANGC,LIUY,ZHANGM,etal.Incorporatingverticalresultsintosearchclickmodels[C]//Proceedingsofthe36thinternationalACMSIGIRconferenceonResearchanddevelopmentininformationretrieval.NewYork,NY,USA:ACM, 2013: 503-512.

[12]YUEYS,PATELR,ROEHRIGH.Beyondpositionbias:Examiningresultattractivenessasasourceofpresentationbiasinclickthroughdata[C]//Proceedingsofthe19thInternationalConferenceonWorldWideWeb.NewYork,NY,USA:ACM, 2010: 1011-1018.

[13]GUOF,LIUC,WANGYM.Efficientmultiple-clickmodelsinwebsearch[C]//ProceedingsoftheSecondACMInternationalConferenceonWebSearchandDataMining.NewYork,NY,USA:ACM, 2009: 124-131.

[14]DUPRETGE,PIWOWARSKIB.Auserbrowsingmodeltopredictsearchengineclickdatafrompastobservations[C]//Proceedingsofthe31stAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.NewYork,NY,USA:ACM, 2008: 331-338.

[15]CHAPELLEO,ZHANGY.Adynamicbayesiannetworkclickmodelforwebsearchranking[C]//Proceedingsofthe18thInternationalConferenceonWorldWideWeb.NewYork,NY,USA:ACM, 2009: 1-10.

[16]CHENDQ,CHENWZ,WANGHX,etal.Beyondtenbluelinks:enablinguserclickmodelinginfederatedwebsearch[C]//Proceedingsofthe5thACMInternationalConferenceonWebSearchandDataMining.NewYork,NY,USA:ACM, 2012: 463-472.

[17]LIUZY,LIUYQ,ZHOUK,etal.Influenceofverticalresultinwebsearchexamination[C]//Proceedingsofthe38thInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.NewYork,NY,USA:ACM, 2015: 193-202.

[18]KL?CKNERK,WIRSCHUMN,JAMESONA.Depth-andbreadth-firstprocessingofsearchresultlists[C]//CHI'04ExtendedAbstractsonHumanFactorsinComputing.NewYork,NY,USA:ACM, 2004: 1539.

[19]LORIGOL,PANB,HEMBROOKEH,etal.Theinfluenceoftaskandgenderonsearchandevaluationbehaviorusinggoogle[J].Informationprocessing&management, 2006, 42(4): 1123-1131.

[20]XUWH,MANAVOGLUE,CANTU-PAZE.Temporalclickmodelforsponsoredsearch[C]//Proceedingsofthe33rdInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.NewYork,NY,USA:ACM, 2010: 106-113.

[21]WANGKS,GLOYN,LIXL.InferringsearchbehaviorsusingpartiallyobservableMarkov(POM)model[C]//ProceedingsofthethirdACMInternationalConferenceonWebSearchandDataMining.NewYork,NY,USA:ACM, 2010: 211-220.

[22]WANGC,LIUYQ,WANGM,etal.Incorporatingnon-sequentialbehaviorintoclickmodels[C]//Proceedingsofthe38thInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.NewYork,NY,USA:ACM, 2015: 283-292.

[23]GUOF,LIUC,KANNANA,etal.Clickchainmodelinwebsearch[C]//Proceedingsofthe18thInternationalConferenceonWorldWideWeb.NewYork,NY,USA:ACM, 2009: 11-20.

[24]HUBT,ZHANGYC,CHENWZ,etal.Characterizingsearchintentdiversityintoclickmodels[C]//Proceedingsofthe20thInternationalConferenceonWorldWideWeb.NewYork,NY,USA:ACM, 2011: 17-26.

[25]CHENWZ,WANGD,ZHANGYC,etal.Anoise-awareclickmodelforwebsearch[C]//Proceedingsofthe5thACMInternationalConferenceonWebSearchandDataMining.NewYork,NY,USA:ACM, 2012: 313-322.

王超，男，1989年生，博士，主要研究方向?yàn)榛ヂ?lián)網(wǎng)搜索結(jié)果排序和用戶行為建模方面的研究，發(fā)表學(xué)術(shù)論文多篇，獲得SIGIR2015最佳論文提名獎(jiǎng)。

劉奕群，男，1981年生，副教授、博士生導(dǎo)師中國(guó)人工智能學(xué)會(huì)理事，知識(shí)工程與分布智能專委會(huì)委員，中國(guó)中文信息學(xué)會(huì)信息檢索與內(nèi)容安全專委會(huì)委員。主要研究方向?yàn)樾畔z索與互聯(lián)網(wǎng)搜索技術(shù)。2016年獲得國(guó)家自然基金委優(yōu)秀青年科學(xué)基金資助。發(fā)表學(xué)術(shù)論文30余篇，獲得SIGIR(CCFA類)最佳論文提名獎(jiǎng)。據(jù)GoogleScholar統(tǒng)計(jì)，論文被引用1700余次。

馬少平，男，1961年生，教授、博士生導(dǎo)師，中國(guó)人工智能學(xué)會(huì)副理事長(zhǎng)，知識(shí)工程與分布式智能專委會(huì)主任，中國(guó)中文信息學(xué)會(huì)常務(wù)理事，信息檢索與內(nèi)容安全專委會(huì)副主任。主要研究方向?yàn)橹悄苄畔⑻幚?，模式識(shí)別、文本信息檢索、中文古籍的數(shù)字化與檢索。作為項(xiàng)目負(fù)責(zé)人先后承擔(dān)“973”、“863”、自然科學(xué)基金項(xiàng)目等多項(xiàng)課題。所領(lǐng)導(dǎo)的文本信息檢索小組，從2002年開始，在國(guó)際上著名的TREC(文本檢索國(guó)際會(huì)議)文本檢索標(biāo)準(zhǔn)評(píng)測(cè)中，多次取得第一名的好成績(jī)，發(fā)表學(xué)術(shù)論文多篇。

A survey of click models for Web browsing

WANG Chao， LIU Yiqun， MA Shaoping

(State Key Lab of Intelligent Technology and Systems， Tsinghua University, Beijing 100084， China)

The implicit feedback information contained in a user’s search interaction process makes an important contribution to the improvement of search ranking. However, since user behavior is affected by several factors (or biases) caused by the ranked positions of the results, presentation styles, etc., it is difficult to directly adopt click information as a relevant feedback mechanism of the search sequence task. To shed light on this research question, researchers have proposed several click models to describe how users examine and click on results from the search engine result pages (SERPs). Based on these models, it is possible to estimate the examination probability of search results and thus reduce the influence of behavior biases to obtain a justified estimation of the result’s relevance. Much attention has been paid to the click model in recent years because it helps commercial search engines to improve ranking performance. In this paper, recent efforts made in constructing click models were investigated and their differences were compared in both performance and application scenarios.

search engine； information retrieval； result ranking； user behavior analysis； click model

10.11992/tis.201605023

http://www.cnki.net/kcms/detail/23.1538.TP.20170111.1619.004.html

2016-05-26.

國(guó)家自然科學(xué)基金項(xiàng)目(61532011, 61672311).

馬少平. E-mail：msp@tsinghua.edu.cn.

TP391

A

1673-4785(2016)06-0711-08

王超，劉奕群，馬少平. 搜索引擎點(diǎn)擊模型綜述[J]. 智能系統(tǒng)學(xué)報(bào)， 2016, 11(6): 711-718.

英文引用格式：WANG Chao， LIU Yiqun， MA Shaoping. A survey of click models for Web browsing[J]. CAAI Transactions on Intelligent Systems, 2016, 11(6): 711-718.