1、探究LTR （學習排序）各方法的優劣性班級 12052311學號 12051238姓名XX2015.05.30前言隨著互聯網的快速發展，大數據時代的來臨，如何對數據進行高效的分類和 檢索成為了一個重要的研究課題。現如今，我們網上在尋找資料的時候，一定會 使用各式各樣的搜索引擎。一個好的搜索引擎，能夠讓用戶很方便快捷的找到需 要的答案。那么，影響搜索引擎搜索速度和準確度的關鍵點在哪呢？我們都知道, 搜索引擎的工作原理：先由網頁爬蟲抓取到足夠多的網頁；再處理這些網頁，例 如，提取關鍵字，建立索引庫和索引等；然后是根據用戶輸入的查詢條件，在索 引庫中快速的檢出文檔；最后是最關鍵的一步，搜索引擎中的評

2、分函數(ranking function)會對每一個檢出的文檔進行打分，然后根據打分的結果，對這些文檔 進行排序，最后呈現在用戶面前的，就是一個和查詢條件的相關性從高到底排列 的查詢結果。在最后一步中，排序的結果嚴重影響著用戶的查詢體驗。我們都使用過搜索 引擎，而且都會有一個習慣，對于搜索引擎返回的幾十頁數據，我們只會點開前 兒頁的搜索結果，而往往是這前兒頁的結果，凡乎完全決定著一個搜索引擎的好 壞。在搜索引擎的演變過程中，出現過很多排序方法，例如傳統的人工打分排序， 現在的Pointwise單文檔方法，Pairwise文檔對方法，Listwise文檔列表方法。 而在這些方法中，Listwis

3、e依靠它的高性能，成為了現代搜索引擎領域研究的主 流的排序方法。現如今，人們還在不斷尋找更好的模型和文檔評價標準，來進一 步提高Listwise方法的排序效率。那么到底是什么原因讓Listwise方法和較于 其他方法有如此高的先進性，以及該方法現在的瓶頸有哪些，下面，我便開始探 充。主題傳統的排序方法比較簡單，通過構造一個打分函數，該函數通過各個文檔和 用戶查詢的相關度差異，對文檔進行排序。而影響相關度的因素有很多，例如查 詢詞在文檔中的詞頻信息，查詢詞的IDF信息等等，而這些影響因數構成了打分 函數的參數，對于傳統的排序模型(人工標注訓練數據)，如果參數過多，會使 得經驗方法的調參非常困難。

4、既然人工不行，于是，人們很自然的想到用機器學 習來解決這個問題。因此，就產生了我們要討論的學習排序(Learning to Rank)。目前，學習排序方法分為3種：單文檔方法、文檔對方法和文檔列表方法。單文檔方法比較簡單，該方法就像是知道兩個點的坐標，確定一條直線的函 數關系式一樣。對于一條查詢query,與其相關的文檔集合為：dlfd2f 然后，對這n個(queiy, 4)查詢-文檔對抽取特征并表示成特征向量，這里用X,YZ 表示抽取出的3個特征向量。然后對于“曲線函數Score(q, d)= aX+bY+cZ+d, 我們可以規定Score大于一個閥值時，認為是相關的。帶入變量X,YZ,由這

5、些 訓練數據，可以確認出最優的常量a,b,c,cL到此，機器學習就結束了，打分函數 也確定了。以后，對于新的查詢和該查詢的相關文檔，我們就能用確定出來的打 分函數來判斷查詢和文檔的相關性。但是，這種方法有很大的局限性，因為對于不同的查詢，他們的查詢-文檔對 的特征向量可能相同，但他們的Score閥值卻是不同的，就像是一個點，它位于 兩條線的交點上，雖然兩條線上都能確定這個點，但是點在兩條線上的含義卻是 不一樣的。例如：點在a線上代表著年齡標準，而在b線上卻代表著身高標準。 所以，這種方法是有前提的，它假設所有的相關度是查詢無關的，但事實說明了， 并非如此。而且，對于Score相同的文檔，也無法

6、進行排序。文檔對方法則完全對同一個查詢里的文檔集生成訓練樣本，它的主要思想是 將Ranking問題形式化為二元分類問題。之所以被稱為文檔對方法，是因為這種 機器學習方法的訓練過程和訓練目標，是判斷任意兩個文檔組成的文檔對DOC1, D0C2是否滿足順序關系，即判斷是否D0C1應該排在D0C2的前面。根據人工 標注的相關性得分，我們可以按照得分大小順序得到相應的文檔對，將每個文檔 對的文檔轉換為特征向量后，就形成了一個具體的訓練實例。然后再由學習方法 對這些實例進行學習。具體的學習方法有很多，在此就不贅述了。雖然文檔對方法不對相關度做獨立假設，但這種方法仍存在功能上缺點：(1). 這種方法只考慮

7、了兩個文檔之間的相對位置，判斷誰在誰的前面，并不考慮文檔 在文檔列表上的位置。而在前言中我們說過，用戶只會對搜索結果的前兒頁數據 進行查看，這需要我們對文檔列表的前凡頁高相關性的文檔再做更好的區分。(2). 不同查詢的相關文檔集的大小也會影響排序模型的構建結果，例如，a查詢只有 10條相關文檔，而b查詢有10000條相關文檔，那么模型兒乎會忽略掉a的10條文 檔，使得模型對a查詢的區分度不高。還有一個重要的因素也會影響文檔對方法 的排序性能。以Ranking SVM為例，它優化的目標是使得正負樣本之間Margin最 大，而并非以排序性能為優化目標。就像BP神經網絡以訓練誤差為目標優化函 數，從

8、而使得它很容易過擬合。優化目標本身的差異將導致模型本身的功能偏置。 于是，基于這個特性，人們提出了文檔列表的方法。文檔列表方法和單文檔方法有些類似，但它的特別之處在于它是將一個查詢 對應的所有搜索結果列表整體作為一個訓練實例。該方法是根據n個訓練實例訓 練得到最優評分函數，對于一個新的查詢，函數會給每一個文檔打分，之后根據 打分結果排序。那么到底怎么樣才能獲得這個最優的打分函數呢？首先，我們根據人工打分的方式，對部分樣本集進行打分，得到一個“正確” 的打分函數g,那么我們要做的工作就是找到一個函數，使得該函數對搜索結果 的打分情況和函數g的打分情況相似，然后不斷迭代更新參數值，使得兩者的差 異

9、更小。接下來的問題就是如何來判斷兩個函數的打分情況的接近程度？ 一種方 法是抽取兩種排序的分值向量，求它們的余弦函數值，值越接近1,說明求得的 該函數的打分情況和函數g的打分情況越接近。另一種方式是ListNet算法使用的 正確排序與預測排序的排列概率分布之間的KL距離（交又炳）作為判定依據。那么Listwise方法現有的這些算法的問題出在哪呢？問題就在每次迭代更新 參數的時候。我們都知道，現在是一個大數據時代，算法每一次的迭代都要從第 一個查詢遍歷到最后一個查詢，這是很可怕的一件事情，這使得算法的運行時間 完全依賴于訓練集的大小。有的時候，數據會大到無法一次性讀入內存，這個時 候，該些算法就

10、不適用了。針對這個問題，我們可以尋找一個這樣的解決方案, 讓算法每次更新參數的時候不必遍歷整個訓練集。所以，我們可以尋找一個新的 算法模型例如SVM、神經網絡模型等，或者新的訓練算法來減少迭代遍歷的時間 或者次數。總結在這篇文章中，我大概地敘述了自己對現有的LTR方法的理解，描述了它們各 自的優缺點，以及在現有的LTR方法中，最具先進性的方法Listwise的改進方 向和意見。由于本人對各類算法的認知程度有限，無法更具體的談及如何改進, 希望在以后的學習中對此會有更深刻的認識。參考文獻.一種基于隨機梯度下降的ListNet排序算法（鄭悅浩）.漫談 Learning to Rank （Jiang Feng）.L