機器學習排序(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）
單文檔學習排名以儘量減少理想與實際相關程度之間的差異。其他方法定義了不同的誤差理解，更接近直接優化每個查詢的理想順序。我們來看一下文檔列表（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的排列概率和第一概率給同樣有效的好答案留有餘地。我個人認為，如果這種方法用於多樣化搜索結果，可以為當前用戶展示許多有效的假設。
當然，結束之刻，假如我們不選取正確的特徵來訓練我們的模型，模型的類型可能不是很重要！特徵選取，創作，生成和設計，往往才是最難的一部分，而非模型的選擇。