Google 如何管理龐大的搜索結果排序規則集合?

據微軟美國搜索技術中心的研究員說,現在Google的搜索結果排序是由大量人工干預形成的決策樹,而不是傳統的監督學習模型,這樣可以快速地調試和修正發現的badcase。google如何管理這些規則集合呢?或者說,google如何控制各個排序特徵對最終結果的影響?


Google的production系統並沒有採用Machine Learning Rank方法,而是使用手工調整的模型。關於這個問題的最早討論可能出現在Kosmix聯合創始人Anand Rajaraman的兩篇博文里[1,2]。Anand Rajaraman的消息則來源於Peter Norvig。Peter Norvig是Google的Director of Research,也是著名人工智慧教材Artificial Intelligence: A Modern Approach的第二作者。

我至今還沒有在任何一家搜索引擎公司工作過,本來不太適合回答這個問題。不過看了Anand Rajaraman那兩篇討論後,在發獃時它們偶爾會出現在我時空穿梭的思維中。下面記錄的就是時空穿梭中形成的一些思維碎片,歡迎對情況更了解的同學指正。

首先需要考慮的是,為什麼Google不採用Machine Learning Rank方法。Anand Rajaraman就此談了很多方面,但比較有說服力的有兩點:

1)多數機器學習模型都基於一個假設,生成數據的是一個穩定的隨機過程,或者說,和過去積累的訓練數據集和離線測試數據集相比,未來數據不會有什麼顯著變化。但搜索需要面對快速變化的互聯網,未來搜索引擎上用戶認可的結果以及可能出現的查詢都有可能和過去不同,並不符合上述的假設。在這種機器學習不可靠的狀態下,也許人肉學習更可信賴一點。

2)不管採用的數據集是用戶點擊形成的,還是領域專家標註形成的,以下這種情況都有可能大量出現:當把候選結果提交給用戶或領域專家時,最符合要求的查詢結果可能因為排位太后,總是得不到用戶點擊或領域專家標註,由此形成的數據集作訓練集訓練模型,會造成惡性循環,最好的結果永遠排不到前邊。這種情況下,讓工程師們人肉調整模型或許反而更可靠一點。

但是這兩點實際上也經不起仔細推敲。因為得到模型後,總得有個測試數據集來檢驗模型的效果,只要這個測試數據集包含上述的問題,不管是用機器學習方法,還是人肉調整模型,最終的效果都是一樣的。實際上,人肉的主要作用也許不在於模型的調整過程,而在於模型的評估過程。Google評價模型的優劣,應該不是只有一個標準,而是有幾個甚至幾十個標準,需要綜合平衡來決定選取哪個模型上線,由人工分析精心挑選的幾十個指標,應該能從很大程度上克服Anand Rajaraman提到的這兩個問題。而機器學習方法顯然更適合在單目標的情況下工作。

所以,整個的工作過程也許是先在整個參數空間搜索得到幾個或幾十個候選模型,然後用預設的幾個或幾十個指標人工對他們進行綜合分析評估。[3]中提供了一個參數空間搜索的方法,當然,它是以NDCG最優為目標搜索的,我們可以在幾十個指標中選取兩三個最重要的指標,以優化其中任意一個為目標來搜索,以減小搜索代價。

=====================================================================

看了駱逸的討論,以及前幾天在Quora上看到的類似問題的討論[4],需要修正一下我的討論。

首先,Google為什麼不採用Learning to Rank方法?對此我暫時還堅持上面的觀點。這個和駱逸以及Quora上的討論並無矛盾,並且可以相互補充。

其次,Google是如何手工調整參數的?Quora的討論明確指出Google工程師的確會手工修改參數的值。如果是這樣,我上面提到的[3]中的方法就不太符合,因為那很大程度上還是一個自動調參數的方法。綜合Quora上的解答以及本問題中提到的MS研究人員的說法,以及對Learning to Rank的了解,[5]中的方法也許最接近Google的排序方法,因為該方法: 1) 是基於規則的; 2) 是類似adaboost的ensemble learning方法,性能有保證; 3) 生成的模型有很好的可解釋性,便於工程人員理解與手工調整。

=====================================================================

[1] http://anand.typepad.com/datawocky/2008/05/are-human-experts-less-prone-to-catastrophic-errors-than-machine-learned-models.html

[2] http://anand.typepad.com/datawocky/2008/06/how-google-measures-search-quality.html

[3] http://portal.acm.org/citation.cfm?id=1183698

[4] http://www.quora.com/Why-is-machine-learning-used-heavily-for-Googles-ad-ranking-and-less-for-their-search-ranking

[5] http://arxiv.org/PS_cache/arxiv/pdf/0811/0811.1679v1.pdf


這個問題是Google的核心機密了。據我研究,Google的排序方法和問題中的描述並不一樣。恕不多說了。

對於Google使用手工構建排序規則而不是用機器學習,我的看法是:

  • 歷史原因:Google的Search Quality團隊在手工構建排序函數方面有多年的經驗,積累了一套行之有效的方法和數據。
  • 對於給定的query,搜索質量是相對靜態的、可以由人直觀評價和分析。手工構建評價函數是可行的。Web搜索排序最初都是用手工函數搞的。

  • 基於機器學習的排序方法在處理大量feature/signal方面有優勢,也可以在某些評測指標上超過手工函數。但是機器學習訓練出的模型在可解釋性和可調控性方面比較差。而Web搜索引擎的運營需要不斷的處理新情況和異常情況,需要不斷微調。在這點上手工函數就有很大的優勢。

事實上,現在所有web搜索引擎的排序系統都是混合式的:在基於手工規則的排序系統中會使用機器學習模型產生的feature/signal;而在基於機器學習的排序系統中,會有很多基於人工規則的feature/signal。


這就是演算法呀


推薦閱讀:

如何設計一個演算法實現商品的展示排序按照用戶的點擊量和發布時間綜合排序?
從損失函數的角度解釋為什麼lr做點擊率預測不如GBDT好???
你同意「數據比演算法重要」這個說法嗎?
進行數據挖掘時演算法需要學習到什麼樣的程度?
如何構造 n 個數使其最小公倍數(LCM)=其和?( n 個數互不相等)

TAG:演算法 | 谷歌Google | 決策樹 | 搜索引擎 |