看谷歌團隊如何做位置偏差估計
作者｜洪亮劼
出處｜極客時間《AI 技術內參》專欄
編輯｜Emily
AI 前線導讀：WSDM（International Conference on Web Search and Data Mining，國際搜索和數據挖掘大會）是每年舉辦一次的搜索、數據挖掘以及機器學習的頂級會議，其從 2008 年開始舉辦，已經有 11 屆的歷史。
更多乾貨內容請關注微信公眾號「AI 前線」，（ID：ai-front）
儘管 WSDM 僅僅舉辦了 11 屆，在計算機科學領域算是一個非常年輕的會議。但是，WSDM 快速積累的影響力已經使其成為了數據挖掘領域的一個頂級會議。根據谷歌學術搜索公布的數據，目前 WSDM 已經是數據挖掘領域僅次於 KDD 的學術會議，而 KDD 已經舉辦了 20 多年。
WSDM 的一大特點就是有大量工業界的學者參與，不管是投稿和發表論文還是評審委員會或者大會組織委員會的成員，都有很多工業界背景的人員參加。這可能也是 WSDM 備受關注的一個原因，那就是大家對於工業界研究成果的重視，同時也希望能夠從中學習到最新的經驗。
2018 年的 WSDM 大會於 2 月 5 日到 9 日在的美國的洛杉磯舉行。今天，我們就來分享 WSDM 2018 上來自谷歌的一篇文章《無偏排序學習在個人搜索中的位置偏差估計》（Position Bias Estimation for Unbiased Learning to Rank in Personal Search）。這篇文章的核心內容是如何結合「因果推斷」（Causal Inference）和排序學習（Learning to Rank）來對用戶數據進行進一步無偏差的估計。
作者群信息介紹
這篇論文的所有作者都來自谷歌，我們這裡對作者群做一個簡單的介紹。
第一作者王選琿（Xuanhui Wang）2015 年起在谷歌工作。他之前在 Facebook 工作了三年，一直從事廣告系統的開發；再往前，是在雅虎擔任了兩年的科學家。王選琿於 2009 年畢業於伊利諾伊大學香檳分校，獲得計算機博士學位，他的博士生導師是信息檢索界著名的華人學者翟成祥（Chengxiang Zhai）。
第二作者納達夫?古爾班迪（Nadav Golbandi）於 2016 年加入谷歌，之前在雅虎研究院擔任了 8 年的主任級研究工程師（Principal Research Engineer），一直從事搜索方面的研發工作。在雅虎研究院之前，古爾班迪在以色列的 IBM 研究院工作了 6 年。他擁有以色列理工大學的計算機碩士學位。
第三作者邁克爾?本德斯基（Michael Bendersky）於 2012 年加入谷歌，一直從事個人以及企業信息系統（Google Drive）的研發工作。本德斯基於 2011 年從馬薩儲塞州阿姆赫斯特分校（University of Massachusetts Amherst）畢業，獲得計算機博士學位，他的導師是信息檢索界的學術權威布魯斯?誇夫特（Bruce Croft）。
第四作者唐納德?梅澤爾（Donald Metzler）也是 2012 年加入谷歌的，一直負責個人以及企業信息系統（Google Drive）搜索質量的研發工作。梅澤爾曾在雅虎研究院工作過兩年多，然後還在南加州大學（University of South California）擔任過教職。梅澤爾是 2007 年從馬薩儲塞州阿姆赫斯特分校計算機博士畢業，導師也是信息檢索界的學術權威布魯斯?誇夫特。
文章的最後一個作者是馬克?諾瓦克（Marc Najork）於 2014 年加入谷歌，目前擔任研發總監（Research Engineering Director）的職位。諾瓦克之前在微軟研究院矽谷分部工作了 13 年，再之前在 DEC 研究院工作了 8 年。諾瓦克是信息檢索和互聯網數據挖掘領域的學術權威，之前擔任過 ACM 頂級學術期刊 ACM Transactions on the Web 的主編。他發表過很多學術文章，引用數在七千以上。
論文的主要貢獻
按照我們閱讀論文的方法，首先來看這篇文章的主要貢獻，梳理清楚這篇文章主要解決了什麼場景下的問題。
眾所周知，所有的搜索系統都會有各種各樣的「偏差」（Bias），如何能夠更好地對這些偏差進行建模就成為了對搜索系統進行機器學習的一個重要的挑戰。
一種方式就是像傳統的信息檢索系統一樣，利用人工來獲得「相關度」（Relevance）的標籤，不需要通過通過人機交互來獲取相關度的信息。所以，也就更談不上估計偏差的問題。
第二種，文章中也有談到的，那就是利用傳統的「點擊模型」（Click Model）。點擊模型是一種專門用來同時估計相關度和偏差的概率圖模型，在過去 10 年左右的時間內已經發展得相對比較成熟。文章中也提到，大多數點擊模型的應用主要是提取相關度信息，而並不在乎對偏差的估計是否準確。
第三種，也是最近幾年興起的一個新的方向，那就是利用「因果推斷」（Causal Inference）和排序學習的結合直接對偏差進行建模。在 WSDM 2017 的最佳論文 [1] 中，已經讓我們見識了這個思路。然而，在去年的那篇文章里，並沒有詳細探討這個偏差的估計和點擊模型的關係。
簡言之，這篇論文主要是希望利用點擊模型中的一些思路來更加準確地估計偏差，從而能夠學習到更好的排序結果。同時，這篇文章還探討了如何能夠在較少使用隨機數據上來對偏差進行更好的估計。這裡，作者們提出了一種叫作「基於回歸的期望最大化」（Regression-based EM）演算法。
論文的核心方法
文章首先討論了如果已知「偏差值」（Propensity Score），也就是用戶看到每一個文檔或者物品時的概率，我們就可以構造「無偏差」的指標，比如「無偏差的精度」（Unbiased Precision）來衡量系統的好壞。
這裡，無偏差的效果主要是來自於重新對結果進行權重的調整。意思就是說，並不是每一個點擊都被認為是同樣的價值。總的來說，如果文檔位於比較高的位置上，那權重反而會比較低，反之，如果文檔位於比較低的位置上，權重反而較高。這裡的假設是一種「位置偏差」（Position Bias）假設。意思就是不管什麼文檔，相對來說，放在比較高的位置時都有可能獲得更多的點擊。因此，在較低位置的文檔被點擊就顯得更加難得。
這種情況下，一般都無法直接知道「偏差值」。因此，如何去估計偏差值就成了一個核心問題。
這篇文章在進行「偏差值」估計的方法上，首先利用了一個叫「位置偏差模型」（Position Bias Model）的經典點擊模型，對偏差值和相關度進行了建模。「位置偏差模型」的假設是用戶對於每一個查詢關鍵字的某一個位置上的文檔點擊概率，都可以分解為兩個概率的乘積，一個是用戶看到這個位置的概率，一個就是文檔本身相關度的概率。那麼，位置偏差模型的主要工作就是估計這兩個概率值。
如果我們能夠對每一個查詢關鍵字的結果進行隨機化，那麼，我們就不需要估計第一個概率，而可以直接利用文檔的點擊率來估計文檔的相關度。但是，作者們展示了，徹底的隨機化對於用戶體驗的影響。
另外一種方法，相對來說比較照顧用戶體驗，那就是不對所有的結果進行隨機化，而僅僅針對不同的「配對」之間進行隨機化。比如，排位第一的和第二的文檔位置隨機互換，然後第二的和第三的隨機互換等等。在這樣的結果下，作者們依然能夠對偏差和相關度進行估計，不過用戶的體驗就要比第一種完全隨機的要好。只不過，在現實中，這種方法依然會對用戶體驗有所損失。
於是，作者們提出了第三種方法，那就是直接對位置偏差模型進行參數估計。也就是說，不希望利用隨機化來完全消除其中的位置概率，而是估計位置概率和相關度概率。
這裡，因為有兩個概率變數需要估計，於是作者利用了傳統的「期望最大化」（EM）演算法，並且提出了一種叫做「基於回歸的期望最大化」的方法。為什麼這麼做呢？原因是在傳統的期望最大化中，作者們必須對每一個關鍵字和文檔的配對進行估計。然而在用戶數據中，這樣的配對其實可能非常有限，會陷入數據不足的情況。因此，作者們提出了利用一個回歸模型來估計文檔和查詢關鍵字的相關度。也就是說，藉助期望最大化來估計位置偏差，藉助回歸模型來估計相關度。
方法的實驗效果
這篇文章使用了谷歌的郵件和文件存儲的搜索數據，採用了 2017 年 4 月兩個星期的日誌。數據大約有四百萬個查詢關鍵字，每個關鍵字大約有五個結果。作者們在這個數據集上驗證了提出的方法能夠更加有效地捕捉文檔的偏差。利用了這種方法訓練的排序模型比沒有考慮偏差的模型要好出 1%～2%。
作者簡介
洪亮劼，電子商務平台 Etsy 的數據科學主管（Head of Data Science），AICon 演講嘉賓，前雅虎研究院（Yahoo Research）科學家、資深科學家和高級研發經理職位。長期擔任多個國際著名會議及期刊的評審委員會成員和審稿人，並且組織過多個關於推薦、搜索、用戶體驗優化的國際研討會。他擁有 3 項美國專利。
參考文獻
Thorsten Joachims, Adith Swaminathan, and Tobias Schnabel. Unbiased Learning-to-Rank with Biased Feedback. Proceedings of the Tenth ACM International Conference on Web Search and Data Mining (WSDM "17). ACM, New York, NY, USA, 781-789, 2017.
《AI 技術內參》專欄目錄
TAG:AI前線 |