LambdaLoss | Google排序?qū)W習(xí)優(yōu)化框架
今天分享一篇谷歌在CIKM'18上發(fā)表的排序?qū)W習(xí)listwise損失函數(shù)優(yōu)化的論文「LambdaLoss」[1]，可以認(rèn)為是沿襲著微軟早期代表性工作[2]的路線，即：，對learning2rank的一些模型做了一個比較系統(tǒng)性的一個解釋框架，從排序優(yōu)化度量指標(biāo)(metric)的視角提出了統(tǒng)一的優(yōu)化框架，通過EM算法，可以和家喻戶曉的listwise優(yōu)化方法Lambda梯度聯(lián)系起來，個人覺得非常有意思。
現(xiàn)狀
主流的排序算法中，不管是pointwise還是pairwise都不能直接優(yōu)化排序度量指標(biāo)，如NDCG等。在listwise中，我們通過定義「Lambda梯度」來優(yōu)化排序度量指標(biāo)，如LambdaRank和LambdaMART，然而Lambda梯度是一種經(jīng)驗性方法，缺乏理論指導(dǎo)。谷歌在CIKM'18上，提出了優(yōu)化排序度量指標(biāo)的概率模型框架，叫做「LambdaLoss」[2]，提供了一種EM算法來優(yōu)化Metric驅(qū)動的損失函數(shù)。文中提到LambdaRank中的Lambda梯度在LambdaLoss框架下，能夠通過定義一種良好、特殊設(shè)定的損失函數(shù)求解，提供了一定的理論指導(dǎo)。
傳統(tǒng)的pointwise或pairwise損失函數(shù)是平滑的凸函數(shù)，很容易進(jìn)行優(yōu)化。有些工作已經(jīng)證明「優(yōu)化這些損失」的結(jié)果是「真正排序度量指標(biāo)」的界，即實際回歸或分類損失函數(shù)是排序度量指標(biāo)誤差(度量指標(biāo)取相反數(shù))的上界[3]，不斷最小化損失函數(shù)這一上界，能夠達(dá)到最小化度量指標(biāo)誤差的目的，這個思想和ELBO (Evidence lower bound) 如出一轍。但是這個上界粒度比較粗，因為優(yōu)化不是metric指標(biāo)驅(qū)動的。很自然的想法是，如何得到一種更加逼近真正排序度量指標(biāo)誤差的損失函數(shù)。
然而，直接優(yōu)化排序指標(biāo)的挑戰(zhàn)在于，排序指標(biāo)依賴于列表的排序結(jié)果，而列表的排序結(jié)果又依賴于每個物品的得分，導(dǎo)致排序指標(biāo)曲線要么不是平坦的，要么不是連續(xù)的，即非平滑，也非凸。因此，梯度優(yōu)化方法不實用，盡管有些非梯度優(yōu)化方法可以用，但是時間復(fù)雜度高，難以規(guī)?；?。為了規(guī)模化，目前有3種途徑，
1.近似法，缺點是非凸，容易陷入局部最優(yōu)； 2.將排序問題轉(zhuǎn)成結(jié)構(gòu)化預(yù)測問題，在該方法中排序列表當(dāng)做最小單元來整體對待，損失定義為實際排序列表和最理想排序列表之間的距離，缺點是排序列表排列組合數(shù)量太大，復(fù)雜度高； 3.使用排序指標(biāo)在迭代過程中不斷調(diào)整樣本的權(quán)重分布(回顧下WRAP就是這種，LambdaRank也屬于這種，就可以看做是權(quán)重。這個方法優(yōu)點是既考慮了排序指標(biāo)，同時也是凸優(yōu)化問題。
本文的動機(jī)之一就是探索LambdaRank中提出的Lambda梯度真正優(yōu)化的損失函數(shù)是什么。文章通過提出LambdaLoss概率框架，來解釋LambdaRank可以通過EM算法優(yōu)化LambdaLoss得到。進(jìn)一步，可以在LambdaLoss框架下，定義基于排序和得分條件下，metric-driven的損失函數(shù)。
LambdaLoss框架
假定給定文檔集合下，不同文檔的模型預(yù)測得分確定了一個關(guān)于所有可能排序排列組合的分布，即，其中是其中一種排序列表結(jié)果。也就是說，模型可以得到多種排序結(jié)果，而每種排序結(jié)果下，文檔真實標(biāo)簽的似然是不同的（pairwise loss只和有關(guān)，而Lambda梯度不僅和有關(guān)，還和位置(即排序)有關(guān)）。我們將看做隱變量，則真實標(biāo)簽的似然關(guān)于該隱變量分布的期望如下：
我們的目標(biāo)是學(xué)習(xí)排序模型來最大化該期望（可以類比EM算法中的，我們這里的是EM中的，因為我們要最大化的是文檔的標(biāo)簽的似然值）。
則負(fù)對數(shù)似然為(考察了List-Level的損失)：
這個式子有兩個核心要素，1是排序分布，2是似然。這兩個核心要素取不同形式，會得到不同的損失函數(shù)。
似然不同形式：
Logistic: ，此時和沒關(guān)系，只和得分之間的相對關(guān)系有關(guān)。則，，故負(fù)對數(shù)似然求和公式中可以把該似然式子提到求和的外面(和沒關(guān)系)，則排序分布求和為1，可以約掉，則損失等價于Logistic Loss，，注意是參數(shù)。
generalized logistic: 。這是帶指數(shù)的廣義Logistic分布。此處使用了代表排序列表和(交換i和j)的NDCG值的差。下面會證明通過EM算法可以根據(jù)該式得到LambdaRank的損失函數(shù)。
借鑒上述的思想，可以得到如下「1個」文檔級別的訓(xùn)練樣本的損失函數(shù)：（我將其稱為 ranking-sensitive pairwise loss）,
至于排序分布，作者舉了上述LambdaLoss框架中，使用高斯分布作為排序分布時，等價于我們熟知的[4]方法，而使用Plackett-Luce作為排序分布時，等價于我們熟知的ListNet[5]算法。
使用EM算法優(yōu)化上述損失：
E步：根據(jù)當(dāng)前模型計算隱變量的分布. M步：固定，重新在complete數(shù)據(jù)集上最小化負(fù)對數(shù)似然，并優(yōu)化模型參數(shù)。其中，完整數(shù)據(jù)集為：。目標(biāo)是優(yōu)化如下?lián)p失：。
C是抽樣得到的所有的訓(xùn)練樣本（每個訓(xùn)練樣本都是文檔列表級別的，由構(gòu)成，也可以理解為E步會對每個原始文檔集合排序()，得到的所有文檔集合排序結(jié)果構(gòu)成M步的訓(xùn)練樣本），M步在C上求期望損失。
其中，
其中，是根據(jù)分布采樣得到的。
更特殊的，直接使用hard assignment distribution來表示。
其中，是按照得分降序排序得到的列表。（此時EM算法和K-means中的優(yōu)化方法一樣，可以將K-means中E步將樣本歸入到某個類別簇 類比為 此處對文檔列表排一個序，每種序?qū)?yīng)一個類別，類別是隱向量；將文檔按照得分降序得到唯一的序類比于K-means中將某個樣本硬性(hard)的歸入到一個具體的類。）
此時，可以通過推導(dǎo)下述負(fù)對數(shù)似然損失函數(shù)得到LambdaRank的損失函數(shù)：
E步：根據(jù)當(dāng)前模型計算所有文檔的得分，然后按照得分降序排序，得到排序結(jié)果。
M步：所有Complete的「文檔列表」的損失簡化為：
進(jìn)一步，代入generalized logistic可得到：
因此，上式是LambdaRank潛在的損失函數(shù)。
作者進(jìn)一步給出了定義Metric-driven Loss的方法：
LamdaLoss中一個最具吸引力的特性是，似然部分既考慮了得分，又考慮了排序。這提供了一個溝通依賴于得分的傳統(tǒng)損失函數(shù)(e.g., pairwise loss)和依賴于排序的排序度量指標(biāo)(e.g., NDCG)的橋梁。
作者給出一些常用的排序度量指標(biāo)的metric-driven Loss。主要利用0-1Loss的上界為Logistic Loss這一性質(zhì)。比如：Average Relevance Position指標(biāo)：
，ARP是cost-based function，越小越好。此時在LambdaLoss框架下的，相應(yīng)的損失函數(shù)為，:
「上述推導(dǎo)有2個技巧」：
1.把ranking中的position 轉(zhuǎn)成形式:
作者還推導(dǎo)了NDCG的LambdaLoss，由于NDCG是gain-based function，故先轉(zhuǎn)成Loss：
其中，，對于給定的文檔列表，是個常數(shù) (和排序無關(guān)，公式中分子只和標(biāo)簽有關(guān), 分母是最優(yōu)的DCG值，是個常數(shù)。所以可以直接加到損失函數(shù)中)；第二項其實就是NDCG（, ），這么定義是因為下文推導(dǎo)方便。
因為：，有：
同理可得，LmabdaLoss損失為：
上述問題是太大時，上界太松了。因此，作者又提出了另一種損失，利用了性質(zhì)（這個性質(zhì)有待證明）。最后可以推導(dǎo)出NDCG第二種形式的損失（「關(guān)鍵」）：
上式的好處在于，可以通過重新定義和來擴(kuò)展出很多NDCG-like metrics的LambdaLoss。也可以用來優(yōu)化binary情況下的，MRR-like metrics。
作者還推導(dǎo)出上述得到的LambdaRank Loss優(yōu)化結(jié)果實際上是優(yōu)化如下metric的上界，
可以證明，使用LambdaLoss優(yōu)化該metric得到的，即：LambaLoss優(yōu)化對應(yīng)的度量指標(biāo)誤差上界比LambdaRank優(yōu)化對應(yīng)的度量指標(biāo)誤差的上界更緊，因此LambdaLoss的優(yōu)化結(jié)果更逼近真實的NDCG指標(biāo)。
另外，上述討論都基于hard assignment 。作者也考慮了soft assignment，并作為下一步工作。
總結(jié)
非常有意思的文章，通過LambdaLoss框架，可以加深對Lambda梯度的理解。
可以發(fā)現(xiàn)lambdaRank的Lambda梯度的優(yōu)化方法可以通過EM來推導(dǎo)。 lambdaRank有沒有潛在的損失函數(shù)以及是如何和評價指標(biāo)NDCG關(guān)聯(lián)上的？lambdaRank的loss本質(zhì)上是優(yōu)化ndcg的一個較為粗糙的上界。如果純從逼近優(yōu)化ndcg的目標(biāo)，文中也推導(dǎo)出了ndcg-loss1和ndcg-loss2的表達(dá)式，其作為NDCG度量指標(biāo)誤差的上界，能夠比lambdaRank更緊。
最后，本篇文章中提到的LambdaLoss值得在搜索推薦等場景中嘗試。
參考
[1] CIKM18: The LambdaLoss Framework for Ranking Metric Optimization：https://storage.googleapis.com/pub-tools-public-publication-data/pdf/1e34e05e5e4bf2d12f41eb9ff29ac3da9fdb4de3.pdf
[2] From RankNet to LambdaRank toLambdaMART: An Overview：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.180.634&rep=rep1&type=pdf
[3] mcrank-learning-to-rank-using-multiple-classification-and-gradient-boosting：https://papers.nips.cc/paper/3270-mcrank-learning-to-rank-using-multiple-classification-and-gradient-boosting.pdf
[4] SoftRank：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.469.3608&rep=rep1&type=pdf
[5] ListNet：https://www.microsoft.com/en-us/research/publication/learning-to-rank-from-pairwise-approach-to-listwise-approach/?from=http%3A%2F%2Fresearch.microsoft.com%2Fapps%2Fpubs%2Fdefault.aspx%3Fid%3D70428