WSDM 2017精選論文解讀

人工智慧和機器學習領域的學術論文汗牛充棟。每年的各大頂級會議、研討班錄用好幾千篇論文，即便是親臨現場也很難追蹤到所有的前沿信息。在時間精力有限的情況下，選擇精讀哪些論文，學習哪些熱門技術就成為了AI學者和從業人員所頭痛的問題。這個欄目就是要幫助大家篩選出有意思的論文，解讀出論文的核心思想，為精讀提供閱讀指導。

數據挖掘和機器學習應用的頂級會議The Tenth ACM International Conference on Web Search and Data Mining （WSDM 2017）今年2月已經在英國劍橋圓滿舉行。正值WSDM十周年，會議上對WSDM的發展進行了回顧和展望。縱觀過去十年的發展，WSDM已經成長為學術圈和工業界都十分倚重的經典跨界會議。不像KDD、WWW或者SIGIR，WSDM因為從最開始就由不少工業界的學術領導人發起並且長期引領，所以十分重視工業界的學術成果的展現。有不少經典的工業界文章在過去十年裡，都是通過WSDM發表的。今年也不例外，因為WSDM的論文涵蓋非常廣泛的主題，而且一般的讀者很難從浩如煙海的文獻中即刻抓取到有用信息，這裡筆者從80篇會議文章中精選出5篇有代表性的文章，為讀者提供思路。

Learning-to-Rank with Biased Feedback

概要：這篇文章獲得了WSDM 2017最佳論文。在實際生產中，我們大量獲得的是 「有偏差」（Biased）的數據。那麼，如何從這些 「有偏差」的數據中，進行「無偏差」（Unbiased）的機器學習就成為了過去很長一段時間以來，實際生產中非常急迫解決的問題。本文探討了解決這個問題的一種思路。

這篇文章來自康奈爾大學的Thorsten Joachims以及他的學生。Thorsten在上一個十年的學術研究中，因為開發SVMLight而名聲顯赫。他也是最早思考如何利用用戶反饋數據進行排序模型（Ranking Model）訓練的學者。那麼，這篇獲獎論文主要是要解決一個什麼樣的問題？其實，這篇文章要嘗試解決的問題在學術和工業界的應用中非常普遍，可以說是一個困擾學者和普通的工程人員已久的問題。那就是，如何從「有偏差」用戶反饋數據中，訓練「無偏差」的排序模型。為什麼用戶反饋數據會「有偏差」？道理很簡單，用戶在和系統交互的時候，受到各方面因素的干擾，從而只對部分信息進行了反饋而忽略了其他信息。比如，在搜索引擎里，因為排版的因素，用戶可能僅僅對排名靠前的幾個文檔進行查看，而徹底忽略排名靠後的所有文檔，即便這些文檔其實可能是相關的。另外一個更加常見的「偏差」則是由現在的「作業系統」（Production System）引起的。「作業系統」往往根據現有的演算法或者模型選擇出了用戶可能最偏好的少部分文檔，而大多數文檔用戶則沒有可能見到，和前面情況一下，即便這些文檔有可能是十分相關的。於是，用戶的反饋就受到了現在系統的影響，而後面的機器學習很有可能僅能從現在系統偏好中改進，而有可能無法提升到全局最優的情況。傳統中，很多學者和從業人員已經意識到了直接使用用戶「有偏差」反饋的數據，特別是點擊數據，會產生問題。但是很長一段時間來，大家並沒有找到如何系統地解決這個問題。Thorsten首先在這篇文章中提出了基於Inverse Propensity Scoring（IPS）的Partial-Info Learning-to-Rank。這部分內容其實並沒有太多的新意，不過是把從Multi-armed Bandit領域用IPS來做Unbiased Offline Evaluation的思路借鑒過來。不過文章指出了一個核心問題，那就是如何來估計這些Propensity Probability，其實也就是當前系統選擇各個文檔的概率。傳統上，特別是以前的Unbiased Offline Evaluation基於隨機產生文檔順序，因此這些Propensity Probability都是Uniform分佈的。但這樣的設計在現實中是不可能的，因為Uniform分佈的文檔，用戶體驗會變得很差。那麼，這篇文章則是要直擊這個痛點。這篇文章採取了這樣一個思路，文章假設現在系統的「偏差」可以通過一個Position-based Click Model with Click Noise（PCMCN）來解釋。簡單說來PCMCN就是來對用戶查看一個排序文檔進行建模，從而達到可以Propensity Probability能夠被方便預測，這麼一個目的。為了能夠PCMCN，作者們還提出了一個基於交換兩個位置文檔的實驗方法，用於收集數據。值得肯定的是，僅僅交換兩個位置文檔的方法，相比於以前的Uniform的方法，要更加註重用戶體驗。文章的實驗部分展示了在人工數據以及真實系統中的表現。總體說來，能夠對「有偏差」的用戶數據建模，比直接利用這些數據，訓練的模型效果要來的好得多。這篇文章非常值得推薦系統、搜索引擎等方面的研究和工程人員精讀。

Real-Time Bidding by Reinforcement Learning in Display Advertising

摘要：傳統中，Real-Time Bidding（RTB）把Bidding考慮成為靜態的決策過程。這篇文章，則是把Reinforcement Learning（強化學習）引入到RTB的應用中，從而提高RTB的效率和整體效果。

這篇文章的作者團隊來自上海交大和倫敦大學學院（University College London）。此文是繼強化學習被應用到搜索和推薦領域之後，又一個把強化學習應用到一個重要領域的嘗試。與推薦和搜索不同的是，RTB因為其實時性，更加講究能夠對於一個決策過程進行動態調整，從而能夠提供最優的解決方案。目前大多數Bidding演算法或者是策略（Strategy）的核心問題，就是他們都是靜態的一個決策過程。那麼，這篇文章的主要思路就是用Markov Decision Process（MDP）來對RTB進行建模。MDP的一般建模，需要三個必備元素，那就是State、Action和Reward。這裡，State是一個（當前時間，剩餘預算，當前Feature Vector）三元組；Action則是以State為輸入，輸出一個少於當前預算的Bid；Reward在這篇文章里定義為在當前Feature Vector為輸入情況下的點擊率（CTR）或者是0（沒有贏得Auction的情況）。MDP除了這三個要素以外，一般還需要定義從每一個狀態跳轉另外狀態的轉移概率。文章中，轉移概率是一個Feature Vector的概率分佈和市場價格分佈的一個乘積。市場價格分佈取決於現在的Feature Vector和當前的Bid價格。整個MDP的布局設置好以後，RTB的問題就轉換成為了如何在MDP中找到最優Action的決策問題。和傳統的MDP一樣，文章介紹了通過Value Iteration的方式來找到最佳的Value函數，然後通過找到的Value函數，來找到最佳的Bidding策略。然而，這樣的方法，只適合在比較小規模的數據上，原因是第一個階段的得到最佳Value函數的步驟太過於耗時。文章介紹了一種在大規模數據上的思路，通過小數據來學習Value函數的表達，然後應用到大規模數據上。文章在兩個數據集上做了實驗，一個是PinYou的數據，另一個是YOYI的數據，數量都算是當前比較大的RTB數據集了。從實驗結果上來看，採用MDP的方法能夠比其他方法大幅度有效提高CTR，以及各項指標。除了在這兩個數據集上的結果以外，這篇文章還在Vlion DSP的線上系統進行了評測，在CTR基本和以前方法持平的情況下，CPM和eCPC都更加有效。總之，這篇文章對於希望探索強化學習在廣告或者是推薦以及搜索等領域的應用有著一定的借鑒意義。從目前的情況來看，演算法依然比較複雜，而且Value函數的逼近可能有不小的性能損失。另外，參考文獻部分十分詳盡，對於想了解RTB的朋友來說，是一個不可多得的言簡意賅的介紹。

摘要：在線A/B實驗最大的困擾就是所需要觀測的指標（Metric）常常需要很長時間觀測到統計意義的變化抑或需要很多的用戶數量。這篇文章就是要嘗試解決這麼一個問題，探討如何通過Variance Reduction的辦法來讓尋找到的Metrics能夠更加容易觀測，並且和用戶的指標相匹配。

這篇文章來自俄羅斯搜索引擎團隊Yandex。近幾年以來，Yandex的研究人員已經陸續發表了一系列的文章來推動在線A/B實驗的研究和實踐。這篇文章是要解決什麼問題呢？在A/B在線測試中，我們希望觀測到的指標有方向性，能夠告訴我們用戶的喜好變化；同時，我們也希望這個指標能夠很容易觀測，不需要大量的數據長時間觀察。文章提出了這麼一個假設，那就是我們能否通過數據以及歷史信息，學習到一組指標的組合，使得這個學習到的結果滿足上述條件？Yandex通過對8個關鍵指標的建模，使得學習到的指標達到了3.42倍的「敏感度」（Sensitivity），相比於之前的指標而言，也就是達到了約11倍的Sample Size的削減，可以說效果非常顯著。那麼，這篇文章的作者是如何做的呢？首先，每一個實驗單元（可以是一個用戶，一個Session或者一個Query）都被一個Feature Vector所描述。這裡的Feature Vector，有可能就是我們已知的指標本身。那麼，整個問題的設置就成為了，學習一個這些Feature Vector的線性組合，使得學習到的新指標對於未來的實驗，更加具有「敏感度」。文章中，作者討論了多種定義「敏感度」的方法，而最終採用的是通過z-score來衡量。這樣的選擇，非常接近普通的t-test的需要。也就使得這篇文章的實用度更加廣泛。如果來解這麼一個優化問題就成為了文章下一個重點。文章簡單介紹採用Geometric的方法來接這個優化問題的思路，並且也探討了一下這種方法和Linear Discriminant Analysis的聯繫。然而作者們認為這個思路並不適合大多數的情況，於是文章介紹了一個基於標準優化演算法的思路。也就是，利用定義的「敏感度」z-score，作為衡量兩個實驗結果的「距離函數」，最終的目標函數是包括這麼三個部分：1. 盡量讓已知A/B有效果的實驗里的距離不減少；2. 盡量讓已知的A/A實驗的結果不變化；3. 盡量分離已知A/B實驗效果不明顯的結果。當然，這個目標函數是Non-Convex的，不過文章依然使用了L-BFGS來解這個優化問題。從實驗來說，作者們用了118個歷史實驗數據來學習這個函數，得到的效果都是學習到的指標能夠更好地指導實驗的結果，同時採用學習到的指標能夠大幅度降低需要達到統計意義效果明顯（Statistically Significant）的數據量，這對於真實的工業環境來說是非常有意義的方法。這篇文章建議所有工業界的讀者精讀。

摘要：如何把深度學習和推薦系統相結合是最近一兩年來推薦系統領域學者比較關心的問題，這篇文章探討了如何把LSTM-Autoregression模型和推薦系統結合的例子，在真實的數據中達到了更好的效果。

這篇文章來自卡內基梅隆大學Alex Smola的實驗室以及Google研究院的Amr Ahmed，陣容可謂非常強大。從傳統的概率圖模型（Probabilistic Graphical Model）的角度來說，要想能夠對時間信息（Temporal）進行有效建模，則必須採用Sequential Monte Carlo等其他辦法。這些辦法往往計算非常複雜而且極易出錯。所以，這篇文章希望通過RNN來幫助這樣的建模場景。文章希望能夠用RNN來對現在的觀測值以及模型參數的時間變化進行統一建模。當然，另外一個比較好的選擇就是LSTM。這篇文章採用了LSTM。有了時間的變化以後，在單一時間的Rating Prediction，則是用戶方面信息和物品（文章中採用的是電影）信息的點積，非常類似傳統的矩陣分解模式。有一個小改動的地方來自於最後的預測結果是一個與時間有關的變化和與實踐無關變數的一個分解。這一點主要是為了讓不同時間段的變化都能夠被模型解釋。這樣看似簡單一個模型最大的問題其實是優化演算法，如果使用簡單的Back-propagation，計算量則會很大。這篇文章採用了一個叫Subspace Descent的方法，使得優化演算法本身能夠比較便捷。在實驗中，文章比較了TimeSVD++以及之前提出的AutoRec，在IMDB和Netflix的數據集上都有顯著的提高。當然，從比較大的角度來看，這篇文章的意義其實非常有限，主要是最近類似思路的文章其實已經有不少，並且從學術貢獻來看，這篇文章完全解答了如何用深度學習和推薦系統結合的更佳的根本問題，適合熟悉推薦系統的讀者快速閱讀。

Learning from User Interactions in Personal Search via Attribute Parameterization

這篇文章來自Google的個人搜索團隊，所有作者都是信息檢索界響噹噹的學者。Marc Najork之前來自微軟矽谷研究院，曾是《ACM Transaction on Web》的主編。微軟矽谷研究院解散之後來到Google。而Donald Metzler、Xuanhui Wang以及Michael Bendersky都是信息檢索界大牛W. Bruce Croft的得意門生。這篇文章是要解決所謂個人搜索（Personal Search）的問題。個人搜索，顧名思義，也就是對個人的文檔進行搜索（比如電子郵件、文本文件、圖片、資料等）。由於這樣特殊的產品需求，傳統的很多方法都不能夠直接適用。另外一個特殊的需求是，由於涉及到用戶的個人隱私，不能夠盲目把不同用戶的信息交互到一起。要解決這些問題，這篇文章提供了這樣一個基本思路，那就是把用戶的Query以及文檔都映射到一個Attribute的空間。在這個空間里，所有的信息都可以跨用戶橫向比較。那麼，下面的問題就是我們如何把這些信息給映射到這個Attribute的空間。作者們採用了構建一個圖（Graph）的做法。在這個圖上有四個類型的節點：文檔、Query、文檔的Attribute和Query的Attribute。兩種節點之間的鏈接是通過Feature Function來定義的。這一點很像Markov Random Field的構建。這也難怪作者之一的Donald Metzler曾經是提倡使用這類模型的主要推手。在定義Feature Graph之後，作者們提出了兩種思路來使用Feature Graph，一種就是直接用機器學習的方法；另一種則是手工方法和機器學習方法的混合。這篇文章採用了第二種方法，因為這樣在一個生產系統中可能更加穩定。從整體上來看，整個技術層面並不複雜，不過這裡的思路相對來說比較新穎。同時，作者還提到了如何從點擊數據中提取有效的訓練數據。在最後的實驗方面，作者們展示了提出的這種方法的有效性。不過，值得一提的是，因為數據集和整個問題的特殊性，這篇文章並沒法和很多其他方法進行公平比較。所以，文章值得對搜索和信息檢索研究有興趣的讀者泛讀。

作者簡介

洪亮劼，Etsy數據科學主管，前雅虎研究院高級經理。長期從事推薦系統、機器學習和人工智慧的研究工作，在國際頂級會議上發表論文20餘篇，長期擔任多個國際著名會議及期刊的評審委員會成員和審稿人。

責編：何永燦，歡迎人工智慧領域技術投稿、約稿、給文章糾錯，請發送郵件至[email protected]