650
排序學習實踐---ranknet方法
1 背景
隨著移動互聯網的崛起，越來越多的用戶開始習慣於從手機完成吃、喝、玩、樂、衣、食、住、行等各個方麵的需求。打開手機，點開手淘、美團等APP，商品玲玲滿目，而讓用戶將所有商品一頁頁看完已經不現實，通常情況下用戶也就查看前幾頁，如果找不到滿意的商品則退出，從而造成流單。因此如何對商品進行排序使得用戶能盡快完成購買流程已經成為這些平台的重要攻克方向。
圖1 手機淘寶、美團等app的商品排序示意
傳統的方法是找幾個特征比如評分、銷量等，然後找個打分函數如簡單的線性函數：F=w1*評分+w2*銷量+...，並通過手工調整權重值w並結合abtest實驗來達到排序的目的（分數越高排名越高）。
這種方法非常簡單，但麵臨著一些問題：1）每當增加一個特征都得調整所有特征的權重，並在線上進行abtest，費時費力；2）特征較多時（當引入個性化特征時），這種手工調整權重的方式已經不可能完成，很難找到一個較優解；3）隨著數據的不斷變化，每隔一段時間都需要人工重新調節權重。總體來講人工調參費時費力、效果也差！
為了避免人工調參，現在工業界主要采用排序學習方法。
2 排序學習簡介
排序學習的目的就是通過一些自動化的方法完成模型參數的訓練。根據不同類型的訓練數據可以將排序學習方法分為以下三類：a）單點標注（point wise）；b）兩兩標注（pair wise）；c）列表標注（list wise）。
2.1 point wise過程
下麵介紹如何使用point wise方法來完成排序學習。
排序學習最重要的工作就是構造訓練樣本，即得到一組（V1,V2,V3,..., Y），其中V是特征，Y是label，得到樣本之後帶入相應的機器學習模型即可完成訓練。
一般來說特征可分成以下幾類（根據業務不同可自行添加特征）：a）商品（文檔）本身特征如：評分、銷量、價格等；b）用戶本身特征如：性別、年齡、用戶的商品類型偏好等；c）用戶-商品關聯特征如：是否看過此商品、是否買過此商品、對此商品的曆史評價等；d）場景特征如：時間（早中晚）、與商品的距離、是否是節假日等。一般來說我們需要將這些特征進行歸一化，原因參見：為什麼一些機器學習模型需要對數據進行歸一化？
找到特征後需要定義label。我們認為給用戶展示過的商品label為1，用戶點擊過的商品label為3，用戶購買過的商品label為7。
通過對曆史日誌數據的清洗整理我們可以得到成千上萬的樣本（V1,V2,V3,..., Y）。
得到樣本之後我們可以將此排序問題轉換為多分類問題（樣本特征-類別標記）或者回歸問題（樣本特征-連續值）。如果轉換為多分類問題，我們模型最後的輸出隻能1、3或是7，往往導致在同一類中的文檔（比如兩個文檔輸入模型的得到的結果都是7）不好繼續排序，因此實際使用中往往將問題轉換為回歸問題，常常采用LR、GBDT等來解決。
2.2 point wise缺點
point wise方法很直觀，非常容易將問題轉換為我們所熟知的問題，但其缺點是完全從單文檔的分類角度計算，沒有考慮文檔之間的相對順序。
舉個例子。假設圖2左圖紅框為某一次用戶點擊的事件，這時候我們獲得一條樣本i (V1i,V2i,V3i,...,Xni, 3)。右圖紅框為某一次用戶點擊的事件，我們獲得一條樣本j (V1j,V2j,V3j,...,Vnj, 3)。按照pointwise的思想，我們認為這兩條樣本的label都是3。但在第二張圖包含更重要的信息，“用戶隻點了紅框內的酒店，而沒有點綠框內的酒店（綠框內的酒店和左圖點擊的酒店一致）”，即說明樣本j的label應該比樣本i的label大（樣本j排名比樣本i更靠前），而pointwise並沒有利用到這個信息。
圖2 point wise缺點示意圖
自然我們的問題就是：如何將文檔之間相對順序信息利用進去呢？
2.3 pair wise方法
在pairwise方法中，我們不再從從單文檔的分類角度來看待問題，而是從一個文檔對如<d1,d2>來看待問題，即如圖2右圖所示，用戶點擊了紅框的商品（d1）而沒有點擊綠框中的商品（d2），那這個時候認為d1的相關性大於d2，那麼我們可以把 d1-d2的label設置為+1，d2-d1的label設置為為 -1。按照這種方式，我們就得到了二元分類器訓練所需的樣本了。預測時，隻需要對所有pair進行分類，便可以得到文檔集的一個偏序關係，從而實現排序。Pairwise方法有很多的實現，比如SVM Rank、RankNet、FRank、RankBoost等。
下麵我們著重介紹下ranknet的原理以及應用。
3 ranknet
3.1 ranknet原理
假設有文檔i和j，其中文檔i的特征向量是Xi（1i, v2i, v3i, ..., vni），文檔j的特征向量是Xj（v1i, v2j, v3j, ..., vnj），我們要找一個打分函數F，假設F是線性函數，F(Xi)=W*Xi=w1*v1i + w1*v2i + ... + wn*vni，其中w表示權重係數，F(Xi)表示針對文檔Xi給出的得分。
我們希望找出這樣一個函數F（本質上是訓練得到這些權重w），當文檔X1比X2排名高時，我們希望F(Xi) > F(Xj)。
下麵我們需要定義損失函數了。首先定義概率Pij，用於表示Xi比Xj排名高的概率，直觀上可以設Pij=F(Xi)-F(Xj)，這樣F(Xi)-F(Xj)越大表示Xi比Xj排名高的概率越大，但這裏問題的關鍵是概率值是在[0,1]區間範圍內的，因此需要歸一化。可以參考邏輯斯蒂回歸的歸一化函數：
其中Oi=F(i)，Oij=F(i)-F(j)，這個函數有比較好的特質，當Oij=0時，Pij=0.5，當Oij>0時，Pij>0.5，並且當Oij趨向於無窮大時，Pij=1，反之當Oij<0時，Pij<0.5，當Oij趨向於無窮小時，Pij=0。
這個時候我們就可以定義損失函數了。損失函數常用有兩種類型：
1）平方損失函數
這是最常用的損失函數，但是現在由於已經做了歸一化邏輯映射，使得平方損失函數不再是一個凸函數，這給我們最優化求解造成了比較大的挑戰，因此實際常常使用另一種損失函數---交叉熵。
2）交叉熵
這裏插句題外話，為什麼非凸函數的最優解不好求？
如下圖所示一個非凸函數，要求最小值，我們常使用的梯度下降法或者牛頓迭代法往往限於局部最優解，很難找到全局最優解。
下麵看看交叉熵損失函數是否能滿足我們的需求。
得到了凸損失函數之後，就可以使用梯度下降方法求解最優化參數。
如果直接這麼訓練最終得到的是線性模型，不能學習特征之間的非線性關係，一般學習非線性關係有幾種方法：1）一種是對特征進行高維映射，例如svm的核方法；2）樹模型；3）帶有隱藏層的神經網絡。
3.2 基於神經網絡的ranknet
在實際使用中，ranknet采用神經網絡方法進行學習，一般采用的是帶有隱層的神經網絡。學習過程一般使用誤差反向傳播方法來訓練。
這裏的輸入層（最底部）的神經元代表了樣本的每一個特征，虛線的神經元代表隱藏層，最終輸出隻有一個神經元。
如何訓練呢？這裏提供了兩種思路：
1）取一個樣本對(Xi, Xj)，首先對Xi帶入神經網絡進行前向反饋，其次將Xj帶入神經網絡進行前向反饋，然後計算差分結果並進行誤差反向傳播，接著取下一個樣本對。。。
這種方法很直觀，缺點是收斂速度慢。
2）批量訓練。我們可以對同一個排序下的所有文檔pair全部帶入神經網絡進行前向反饋，然後計算總差分並進行誤差反向傳播，這樣將大大減少誤差反向傳播的次數，原理如下公式推導所示。
3.3 ranknet代碼實現
開源ranknet實現：https://people.cs.umass.edu/~vdang/ranklib.html
3.4 應用
我們輸入的樣本如下所示：相應的字段為：<target> qid:<qid> <feature>:<value> <feature>:<value> ... <feature>:<value> # <info>。其中target就是label，購買label=7，點擊label=3，展示label=1；qid代表一次排序的標識，feature就是特征，#後麵是注釋信息。
7 qid:1 1:1 2:1 3:0 4:0.2 5:0 # 1A
3 qid:1 1:0 2:0 3:1 4:0.1 5:1 # 1B
1 qid:1 1:0 2:1 3:0 4:0.4 5:0 # 1C
1 qid:1 1:0 2:0 3:1 4:0.3 5:0 # 1D
1 qid:2 1:0 2:0 3:1 4:0.2 5:0 # 2A
3 qid:2 1:1 2:0 3:1 4:0.4 5:0 # 2B
1 qid:2 1:0 2:0 3:1 4:0.1 5:0 # 2C
1 qid:2 1:0 2:0 3:1 4:0.2 5:0 # 2D
1 qid:3 1:0 2:0 3:1 4:0.1 5:1 # 3A
3 qid:3 1:1 2:1 3:0 4:0.3 5:0 # 3B
7 qid:3 1:1 2:0 3:0 4:0.4 5:1 # 3C
1 qid:3 1:0 2:1 3:1 4:0.5 5:0 # 3D
將樣本輸入到ranknet進行訓練，最終得到如下所示結果，其中我們特征為46個，即輸入層中神經元個數為46個，隱藏層隻設置了1層，隱藏層神經元個數設置為10個。
得到模型結果後，將此模型保存到緩存中。假設來一個線上請求，我們首先提取出各個文檔的特征向量（V1, V2, V3, ..., Vn），帶入此神經網絡模型得到各個文檔的評分，並按照評分進行排序。
4 小結
本文對排序學習做了一個簡單的介紹，並著重介紹了ranknet的原理以及應用，後麵會對其他pair wise方法、list wise方法做一些探討。
檢索實踐文章係列：
lucene如何通過docId快速查找field字段以及最近距離等信息？
最後更新：2017-04-01 13:37:08