論文貢獻
- 設(shè)計了一個貪婪的多樣性搜索策略；
- 設(shè)計了新的用于衡量多樣性指標的metrics；
細節(jié)內(nèi)容
多樣性搜索策略
假設(shè)搜索詞存在語言多樣性的時候，多樣性的搜索策略可以提高Recall。這種情形在推薦場景下會顯得更加重要。
問題定義如下：
圖1:問題定義
其中，V(d|q,c)可以理解為文檔d滿足“帶有真實目的為c的q”的滿意度概率，那么(1-V(d|q,c))就是不滿意的概率。
根據(jù)貝葉斯公式：P(S|q) = \sum_c{P(c|q)P(S|c,q)}，因此P(S|c,q)等于上圖中的右邊括號部分，意思就是返回的結(jié)果里面至少有一個以上滿足用戶搜索意圖的概率。
這個問題定義有兩個需要注意的地方：
- 目標沒有要求盡量的多樣；
- 目前沒有對返回結(jié)果的順序作要求。
但是，后面給的IA貪婪算法卻是對順序有保障的。另外，因為該問題具有很強的子問題結(jié)構(gòu)信息，所以可以采用動態(tài)規(guī)劃的思路進行貪婪搜索。該方法并不能保證一定能夠得到最優(yōu)解，但是卻有一個最壞結(jié)果的error bound。
圖2:貪婪IA算法
其中，參數(shù)的含義分別如下：
- C(q)是query可能存在的語義集合
- R(q)是query搜索返回的結(jié)果集合
- C(d)是document的語義集合
- P(c|q)是query的語義概率
- V(d|q,c)是帶有語義c的q查詢時，d滿足要求的概率
- U(c|q,S)是圖1中公式(1)的右邊括弧中的相乘部分，也就是集合S不滿足“q的語義c”的概率。
注意：需要試驗測試一下原文的正確性，從公式來推導(dǎo)，應(yīng)該取argmin，而不是argmax。
多樣性評價metrics
傳統(tǒng)的檢索評估指標，比如NDCG，多是用來衡量檢索結(jié)果與搜索詞的語義相關(guān)性來進行評估的。但是當搜索詞的語義存在多樣性的時候，那么NDCG就不適用了，需要新的指標來進行評估。
該文假設(shè)檢索結(jié)果與檢索詞的相關(guān)度是和檢索詞的語義條件獨立的，并根據(jù)該假設(shè)求的NDCG在不同語義上的期望得到NDCG-IA結(jié)果作為評價指標。
圖3:NDCG-IA
