本文首發于 vivo網際網路技術 微信公衆号 https://mp.weixin.qq.com/s/uWg3m5xIGBAKNqqDmxzw2Q作者：Doug Turnbull
譯者：林壽怡
目錄：
一、衡量搜尋的好壞
二、用機器學習生成 ranking 函數
三、單文檔 機器學習排序 (point-wise learning to rank)
四、文檔清單方法（LIST-WISE），文檔對方法（PAIR-WISE）
五、直接用 w/ListNet 優化清單
六、使用 RankSVM 優化文檔對方法
七、RankSVM 與 List-Wise 方法
八、結論
機器學習排序(Learning to rank)将搜尋轉化為機器學習問題，在本文中，我想找出搜尋與其他機器學習問題不同的原因，如何将搜尋排名作為機器學習或者是分類和回歸問題？我們将通過兩種方法，對機器學習排序方法的評估有個直覺的認識。
目标是搜尋和經典機器學習問題的根本差別，更具體地說，如何量化搜尋的好壞。例如股價預測系統的準确性，取決于我們有多少預測資料是來自真實的公司股價。如果我們預測亞馬遜的股價是123.57美元，實際上是125美元，我們會說這非常接近。假設按均值來說，我們的預測跟實際股價的誤差在1美元到2美元之間，我們可以認為系統預測的很好。
這種情況下的誤差我們稱之為殘差，即實際值與預測值之間的差異：實際值-預測值。（實際上，殘留^2才是最小化，但在這裡保持通俗易懂。）
訓練期間，回歸系統通過如何量化好壞來得到最優解。我們可以嘗試公司不同的量化特征，例如員勞工數、收入、手頭現金、或者其他任何有助于減少股價誤差的特征。它可能會使最小二乘回歸（least-squares regression）學習為線性公式，例如：股價= 0.01員勞工數+0.9收入+0.001*手頭現金，作為減少誤差的最佳方式。
搜尋結果的好壞（或介于兩者之間）卻完全不一樣。股價預測系統完全是為了減少實際值-預測值的誤差，但搜尋系統是盡量接近搜尋查詢的理想排序。換句話說，目标是減小理想排序到結果項集合的距離，排序的優先反映出搜尋者感覺搜尋的好壞。
例如，電子商務使用者搜尋“dress shoes”，我們定義一個粗略的理想排序：
- Best-selling dress shoes
- Low-performing dress shoes
- Other kinds of shoes
- Ladies dresses (if at all)
以此我們可以想象一些場景，并猜測他們距離理想結果有多遠。至少需要向“dress shoes”的搜尋者在展示衣服前優先展示一些鞋子 - 但這一點都不完美。這就像預測亞馬遜的股價是150美元而不是125美元：下面的結果接近嗎？
- A pair of tennis shoes
- Meh Dress Shoes
- A ladies dress
另一方面，優先于其他鞋子并在best-selling dress shoes前一個位置展示meh dress shoes，這樣可能會非常接近，但也并不完美。這可能與預測亞馬遜的股價為123美元相當：
- Meh pair of dress shoes
- Best-selling pair of dress shoes
- Tennis Shoes
正如你看到的搜尋，并不是實際值-預測值，而是盡可能接近每個使用者查詢的最佳排序。NDCG是一種衡量搜尋結果和理想排序差距的名額。其他一些名額衡量搜尋結果的好壞各有利弊，這些名額幾乎總是取值介于0（最差搜尋結果）至1（最好搜尋結果）。
此外，這些名額不能僅是純粹的差異或編輯距離類型的計算。由于使用者更關注頂部的搜尋結果，是以要擷取這些位置需具備優先權。是以，搜尋名額通常包括位置偏差，這意味着前幾個結果偏離理想時，比底部結果偏離更糟糕，NDCG内置了位置偏差。
雖然有一些可用的名額 ( 例如 ERR，MAP等 )，在本文中我隻把 “NDCG”作為真正相關性名額的縮寫。
二、用機器學習生成ranking函數
經典的回歸問題建構了一個用一組特征直接預測的函數 f。我們盡量減少實際股價- f（公司特征）。機器學習排序的目标是建構不直接預測的ranking函數。相反，它用于排序-我們提供一組理想的順序作為訓練資料，ranking函數需要兩個輸入，即query查詢和document文檔，并為每一個查詢正确排序的文檔配置設定一個分數。
重述以上一點更多内容：
股市：對于公司x，生成函數f(x)，使y - f(x)最小化
搜尋：對于檔案d，查詢q，生成函數f（d，q），當f（d，q）降序排序時，使所有文檔的NDCG最大化
我們來看一個粗略的例子，看看我們的意思。作為資料科學家/搜尋工程師，我們認為以下查詢/文檔的特征對我們的電子商務搜尋有幫助：
- 商品标題中關鍵字的TF * IDF分數：titleScore（d，q）
- 商品描述中關鍵字的TF * IDF分數：descScore（d，q）
- 商品的銷量：numSold（d）
機器學習過程可能會得到一個文檔評分公式，如：
f（d，q）= 10 titleScore（d，q）+ 2 descScore（d，q）+ 5 * numSold（d）
通過一組測試查詢（通過這樣的模型，我們可以得到盡可能接近使用者理想的排序）可以最大限度地提高NDCG。
大多數機器學習排序的複雜度通常來自于調整的問題，以便可以應用其他機器學習方法。這些往往分為三種：單文檔方法（point-wise），文檔對方法（ pair-wise）和文檔清單方法（list-wise），我們将在下面介紹。我們将簡要介紹幾種方法，并思考每種方法的利弊。
三、單文檔 機器學習排序(point-wise learning to rank)
搜尋的“訓練集”看起來有點像一般的機器學習訓練集。單文檔學習排名基于這種情況，是以讓我們簡要回顧一下搜尋訓練集的樣子。搜尋訓練集的形式為在某個查詢下帶得分的文檔，并稱為判斷清單，以下是一個判斷清單的例子：
得分，查詢，文檔
4，dress shoes，best_selling_dress_shoes
3，dress shoes，meh_dress_shoes
...
0，dress shoes，ladies_dress
0，dress shoes，toga_item
正如你所看到的，非常相關的文檔比如best_selling_dress_shoes的得分為4，而完全不相關的文檔（toga_item）得分為0。
單文檔學習排名不關注直接優化每個查詢的排名。相反，我們隻是嘗試預測相關性得分。我們使用某種回歸來建立包含文檔d，查詢q的排序函數f（d，q）。就像股價的例子一樣，我們試圖盡量減少殘差。我們希望f（toga_item，“dress shoes”）得分為0，和f（best_selling_dress_shoes，“dress shoes”）得分為4。
在訓練和評估期間，我們單純将殘差 y - f（d，q）最小化（這裡的y是d，q的得分）。在這種情況下，假設我們的排序函數f給出了上述0分的文檔為0.12分，4分的文檔為3.65分。隻看殘差的話這似乎做的很好。如果所有文檔得分平均不偏離0.5分以上，那麼我們認為每個查詢的NDCG也被最大化，也就是說，我們認為如果我們能夠建立一個隻傳回得分的排序函數，我們應該可以得到接近使用者期望的理想排序。
但表象可能是騙人的，單文檔學習排名的一個問題是獲得正确排序的頭部項通常比判斷清單尾部的模糊項更加重要。基本上所有認知和位置偏差在最大化度量（如NDCG）下都會被忽略。
實際上，一個經常交換精準相關項和不太相關項，但可以準确地預測第50頁較低的相關性等級的模型并不是很好。買家在前幾個結果中看了些勉強相關的項目且沒有被其打動時，是以他們離開了。
更為災難性的是，當你考慮僅發生在具體查詢中的關系時會出現另一個問題，單文檔方法會清除查詢分組，忽略這些查詢内的細微差别。例如，一個查詢與标題字段上的相關性得分有很強的相關，而另一個查詢與描述字段得分相關。或許某個查詢的“good”标題比對得分是5，而另一個查詢的“good”标題比對得分是15，這些情況是真實存在的：不同比對中文檔頻率不一緻可能導緻這些場景。
是以，一般來說，單文檔方法的執行效果不佳，我們将繼續研究那些不清除查詢分組，而是嘗試使用排序函數直接優化每個查詢的排序的方法。
單文檔學習排名以盡量減少理想與實際相關程度之間的差異。其他方法定義了不同的誤差了解，更接近直接優化每個查詢的理想順序。我們來看一下文檔清單（LIST-WISE）和文檔對方法（PAIR-WISE）機器學習排序解決方案的兩個例子，以便更接近于結合位置偏差和容納每個查詢細微差别的能力。
五、直接用w/ListNet優化清單
文檔清單學習感覺像最純粹的機器學習排序方式。它非常直接地定義錯誤：目前ranking函數的清單距離理想值的差距有多大？例如，這樣的一種方法是通過檢視給定順序的排列機率。 基本思想是定義一個函數，該函數計算按給定的相關性得分的排列是使用者真實尋找的機率。如果我們從判斷清單中将“得分”作為排序，第1個結果的得分高于第2個，這樣将獲得最高機率。然而，從判斷清單中擷取的相關性等級對于目前使用者目前的地點、時間、上下文有可能是不正确的。是以，單個較低分項在高分項上不可能成為完美的相關性排序，也許這才是使用者此時此刻實際想要的，最低相關性得分排第一個的重排清單是極不可能的，排列機率接近零。
相對于計算每個清單排序可能的錯誤，僅檢視排列中的第一個項對于搜尋是“最佳”的機率來近似排列優先級在計算上是更加可行的。這被稱為“第一”機率，它查找單個相關性分數以及查詢的每個其他相關性分數，以計算該項将是第一的機率。正如你所預料的那樣，較高的得分的相關性項将獲得更高的機率排在前面，較低的得分項在該使用者相同上下文時間地點下不太可能排在前面。
文檔清單方法ListNet提出最小化訓練集相關得分與神經網絡中權重之間的交叉熵。聽起來像胡言亂語，但真正重要的是通過最小化的error函數，開發一個直覺的例子來看看它如何工作，如下面的僞python所示：
def error():
error = 0
For each query
For each doc:
error -= TopOneP(doc.grade) * log( TopOneP(f(doc, query)))
這裡f是我們正在優化的ranking函數。 TopOneP是給定得分或分數排第一的機率。
首先，我們來看第一項TopOneP（doc.grade）。你想想這裡發生了什麼，假如第一名基于判斷清單得分的機率高，那麼第二項log（P ...）将增加更多權重，換句話說，第一項可以被認為是基于判斷清單中的得分該項的優先級。更高得分項有更多第一的機率：正是我們尋找的位置偏差！
現在看第二個，log（TopOneP ...）。回想一下， log（TopOneP = 1）為0，當TopOneP接近0時log（TopOneP <1）越來越負。是以，如果TopOneP接近于0，并且是以log越來越負，則整個項越來越負。負越多越不好，因為error-=(big negative number)使錯誤變成更大的正數。
綜上所述，當（1）該項在判斷清單很重要時（TopOneP（doc.grade）很高），并且當我們的rangking函數f的TopOneP很低時，會産生更多的誤差。顯然這是不好的：在判斷的基礎上，真正需要靠前的，應該用f把它排到前面。
ListNet中的目标是通過疊代更新f函數中的權重來最小化誤差。這裡我不想深入講解，因為上面的點更為重要。參閱這篇文章 獲得更多資訊以及如何使用誤差的定義來計算梯度（如何更改特征的權重）以盡量減少誤差。
六、使用RankSVM優化文檔對方法
文檔對機器學習排序（pair wise learning to rank）通過最小化在搜尋結果中亂序結果數， 一個具體名額：Kendall's Tau衡量了搜尋解決方案中有序對的比例。文檔對學習排序的一種形式是對查詢進行分類，使得項目“有序”或者“亂序”。例如，你可能會發現，當對特定的查詢集進行排序時，标題得分更高的其銷售事項總數反而比較低。
Thorsten Joachims在這篇文章 中介紹了一種流行的文檔對機器學習排序方法RankSVM，還在Fabian Pedregrosa的部落格文章中以Python方式實作，且樂意我在這篇文章借用他的圖。
想象一下我們有兩個查詢，或許以我們的“dress shoes”查詢，另一個是“t-shirt”。下面的圖表y軸為标題得分特征，而x軸可能是銷量。我們将“dress shoes”的每個判斷繪制為三角形，并将“t-shirt”的每個判斷繪制成圓形。顔色越深的形狀越相關。
我們的目标是發現一個類似于上面圖像中的w向量的函數，将最接近于正确的搜尋結果排序。
事實證明，這個任務與使一個項好于另一個項的分類問題是一樣的，适用于支援向量機（Support Vector Machine SVM）的二進制分類任務。如果dress_shoes比meh_dress_shoes更好，我們可以将該排序标記為“更好”或者“1”。類似地，meh_dress_shoes在dress_shoes之前标記為“更差”或“-1”。然後，我們可以建構一個分類器來預測一個項可能比另一個更好。
這個分類任務需要更多底層特征值，想想“更好“的含義是什麼，這意味着dress_shoes和meh_dress_shoes之間存在某些差異而将它歸類為更好。是以RankSVM在此增量：itemA的特征值減去itemB的特征值上進行分類。
作為一個例子，隻關注單一特征“銷量”，我們可能會看到dress_shoes銷售為5000，而meh_dress_shoes的銷售量隻有1000。是以産生的4000“差異”在訓練過程中将會是一個特征。我們将這個差異作為一個SVM訓練樣本：（1,4000）。這裡1是我們預測的“更好”的标簽，而4000是我們在SVM中用作特征的“銷量”增量。
在特征空間中繪制每個成對的差異來建立兩個分類，如下所示，可以使用SVM來找到兩個分類之間的适當判定邊界：
當然，我們不需要一個判定邊界。 我們需要一個方向向量表示這個方向“更相關”。 最終，與該判定邊界垂直的向量提供了ranking函數的線性權重比例：
這聽起來就像變成簡單的線性回歸，畢竟我們隻獲得特征權重和線性ranking函數。 但是如果你還記得單文檔方法的讨論，在單個查詢中你有時會具有查詢内依賴性/細微差别。 特征中的一個好的标題在“dress shoes”得分為“5”,相比在“t-shirts”的得分為“15”，“RankSVM” 所做的是通過關注單個查詢中指出“标題得分越高，對應查詢中相關性越高”的粗略的感官中的分類增量。
在圖形中，你可以看到，使用線性回歸運作上述相同的資料：
七、RankSVM與List-Wise方法
你可以看到， RankSVM似乎仍然建立一個直接的、線性的相關性。我們知道現實往往是非線性的。使用SVM，可以使用非線性核心，盡管線性核心往往是最受歡迎的。 RankSVM的另一個缺點是它隻考慮到文檔對的差異，而不考慮位置偏差。當RankSVM中的項無序時，無法優先保證頭部項正确的同時忽略底部項的不準确。
雖然文檔清單方法往往更準确，并且包含位置偏差，但訓練和評估的成本很高。雖然RankSVM往往不那麼準确，但該模型很容易訓練和使用。
由于其簡單性，RankSVM可以輕松地為特定使用者或部分查詢/使用者構模組化型。可以想象将查詢分類到不同的用例中。也許對于電子商務，有些查詢我們可以肯定地說是錯别字。而其他的是我們知道的廣泛的類目搜尋查詢（如“shoes”）。
如果我們相應地對查詢進行分類，我們可以為每種類型的用例分别構模組化型。我們甚至可以組合不同的SVM模型。例如，由于模型是一組線性權重集合，我們可以将模型綁定到特定的使用者Tom，并将其與Tom正在執行的查詢綁定的模型相加，搜“dress shoes”傳回dress shoes，我們覺得Tom會很喜歡。
主要的結論是無論選擇什麼樣的模型，明白該模型需要優化什麼，需要盡量減少什麼樣的誤差？
你了解了單文檔方法如何優化判斷的殘差，以及如何為不理想。 RankSVM執行一個更簡單的優化來消除無序對，但這也有問題，因為沒有考慮到位置偏差。有趣的是，ListNet的排列機率和第一機率給同樣有效的好答案留有餘地。我個人認為，如果這種方法用于多樣化搜尋結果，可以為目前使用者展示許多有效的假設。
當然，結束之刻，假如我們不選取正确的特征來訓練我們的模型，模型的類型可能不是很重要！特征選取，創作，生成和設計，往往才是最難的一部分，而非模型的選擇。
更多内容敬請關注 vivo 網際網路技術 微信公衆号