達觀數據搜索引擎排序實踐
前言
隨著互聯網的深入發展，人類已然進入大數據時代。如何在浩瀚的數據海洋里高速有效的獲取有價值的信息，正是促使大數據技術具備走向眾多企業的潛力。搜索引擎作為獲取信息的有效入口，已然經歷了20多年的發展，並一直試圖理解用戶搜索意圖以及提升搜索的精準性。
Google是全球性的搜索引擎，看似簡單的搜索框背後隱藏的是極其複雜的系統架構和搜索演算法，其中排序（以下統稱Ranking）的架構和演算法更是關鍵部分。Google正是通過PageRank演算法深刻改變搜索排序而一舉擊敗眾多競爭對手。
Ranking是搜索引擎的核心技術，本文以搜索引擎的Ranking技術為切入點，從搜索引擎架構、檢索模型、機器學習演算法、點擊模型、搜索效果評估等方面將達觀數據（http://www.datagrand.com）在搜索引擎Ranking的構建與優化過程中的一些實踐經驗與大家做分享。
經典搜索排序架構
通常在線搜索引擎要求實時響應（毫秒級）用戶的搜索請求，使得在線對每個文檔進行基於模型的Ranking複雜計算不太現實，因而搜索的過程被分成兩個階段。階段一是使用相對簡單的常用檢索模型對用戶query從索引中快速檢索出Top-k候選結果集。常用檢索模型主要有向量空間模型(Vector Space Model)、布爾模型(Boolean Model)、概率檢索模型BM25等，通常Top-k的候選集選取還結合離線計算質量分高的文檔以排除掉文本相關但質量分太低的文檔；階段二則使用計算相對複雜的機器學習排序模型對Top-k候選結果集進行精確的重排序，因為Top-K的候選結果集數據量級一般不會很大，這一步計算可控。
圖1：一個經典的搜索引擎排序架構
Ranking模型的訓練數據主要由query、文檔以及query與文檔的相關度組成，相關度可以標記成好、不好兩個級別或細粒度更高的Perfect、Excellent、Good、Fair、Bad五個級別。訓練數據主要有兩種獲取方式：方式一是由搜索評測人員標記query與每個文檔的相關度進行手工的評測整理；方式二是通過自動分析搜索點擊日誌生成。顯然，對於大規模機器學習排序模型的訓練數據人工標註的成本過高，而且人工也無法對模型進行相對實時的更新。達觀數據（http://www.datagrand.com）主要通過方式二生成訓練數據，自動分析搜索點擊日誌，分析用戶在同一個搜索session內對query的各種變換、對搜索結果中不同位置的文檔的點擊行為以及後繼的篩選、翻頁等行為，綜合計算出一個可以標記訓練數據的搜索滿意度得分。
達觀搜索的實踐表明，通過分析搜索點擊日誌可以實現模型訓練數據的自動生成和實時更新，同時也可以達到比較滿意的搜索效果。
達觀搜索引擎架構
達觀搜索引擎架構從底往上分別是分散式數據存儲層、索引構建與模型訓練層、索引數據與模型數據分發層、搜索核心層、開放介面層，同時系統架構還支持搜索引擎的索引配置和Ranking策略配置、以及搜索分析與效果評估。
搜索核心層是由query分析引擎、索引引擎、Ranking引擎構成。其中query分析引擎（QUERY ANALYSIS ENGINE）負責對用戶的query進行語義分析和意圖識別，包括query分詞、中心詞提取、query糾錯、query自動提示、query擴展等。索引引擎（INDEX ENGINE）執行Top-k候選結果選取，這裡我們綜合考慮了檢索模型的搜索相關性評分和文檔的靜態質量分（離線計算），另外在這一層還根據用戶的篩選條件以及業務層面的搜索結果配置進行了搜索結果的篩選和融合。排序引擎（RANKING ENGINE）利用機器學習模型對Top-k的候選集執行第二輪的精確排序。RANKING ENGINE內置一個演算法插件框架，可以根據用戶配置的搜索排序策略載入相應的排序演算法插件以及排序演算法模型，同時還支持用戶對搜索流量劃分到不同的排序演算法插件，以實現多個演算法策略的同時在線A/B testing對比。
檢索模型的選擇
常見的檢索模型主要有布爾模型(Boolean Model)、向量空間模型(Vector Space Model)、概率檢索模型BM25與BM25F。
布爾模型
布爾（Boolean）模型是基於集合論和布爾代數的一種簡單檢索模型。它的特點是查找那些對於某個查詢詞返回為「真」的文檔。在該模型中，一個查詢詞就是一個布爾表達式，包括關鍵詞以及邏輯運算符。通過布爾表達式，可以表達用戶希望文檔所具有的特徵。由於集合的定義是非常直觀的，Boolean模型提供了一個信息檢索系統用戶容易掌握的框架。查詢串通常以語義精確的布爾表達式的方式輸入。
布爾模型的主要優點是直觀和簡單，缺陷在於完全匹配會導致被返回的結果文檔太多或者太少。
向量空間模型(Vector Space Model，VSM)
VSM概念簡單，即把對文本內容的處理簡化為向量空間中的向量運算，並且它以空間上的相似度表達語義的相似度，直觀易懂。當文檔被表示為文檔空間的向量，就可以通過計算向量之間的相似性來度量文檔間的相似性。文本處理中最常用的相似性度量方式是餘弦距離。
VSM的優點：
1）對term的權重的計算可以通過對term出現頻率的統計方法自動完成，使問題的複雜性大為降；
2）支持部分匹配和近似匹配，並可以根據query和文檔之間的相似度對結果進行排序。
VSM缺點：
1）基於term之間的獨立性假設，也即權重計算沒有考慮term之間的位置關係，也沒有考慮term的長度對權重的影響；
2）計算量大。新文檔加入需要重新計算term的權重。
概率檢索模型
概率統計檢索模型(Probabilistic Retrieval Model)是另一種普遍使用的信息檢索演算法模型，它應用文檔與查詢相關的概率來計算文檔與查詢的相似度。
二元獨立模型(BIM)
辭彙獨立性假設:文檔裡面出現的詞沒有任何關聯，這樣一個文檔的出現就可以轉為各個單詞出現概率的乘積。
對於同時出現查詢qi以及文檔di的時候，對qi在di中出現的單詞進行「相關文檔/不相關文檔」統計，即可得到查詢與文檔的相關性估計值
其中：
N表示是文檔集中總的文檔數；
R表示與query相關的文檔數；
ri表示與query相關的文檔中含有的第i個term文檔個數；
ni表示含有的第i個term文檔總數；
0.5是平滑因子，避免出現log(0)。
BM25 模型
BM25 模型在BIM模型的基礎上考慮了查詢詞在Query以及Doc中的權重，並通過實驗引入了一些經驗參數。BM25模型是目前最成功的內容排序模型。
改進之後的 BM25 模型的擬合公式如下:
fi 表示term在D中的詞頻，K因子表示文檔長度的考慮，其計算公式為:
其中：
k1為經驗參數， k1一般設置為1.2；
b為調節因子，將b設為0時，文檔長度因素將不起作用，經驗表明一般b=0.75；
dl代表當前文檔的長度；
avdl代表所有文檔的平均長度；
qfi 表示在查詢中的詞頻，k2也為調節因子，因為在短查詢下這部分一般為1，為了放大這部分的差異，k2一般取值為 0~1000。
綜上所述，BM25模型結合了BIM因子、文檔長度、文檔詞頻和查詢詞頻進行公式融合，並利用k1，k2，b對各種因子進行權重的調整。
BM25F模型
BM25F模型對BM25模型的改進之處在於考慮了文檔不同區域的加權統計，例如文檔的標題和描述被賦予了不同的區域權重，在各個不同區域分別統計詞頻。
BM25F模型的計算公式為:
其中：
文檔D來自不同的u個域；
各個域對應的全總為Wk；
fuin表示詞頻；
Bu表示各個域的長度；
ulu 為域的實際長度，uvulu表示域的平均長度；
bu 為各個域長度的調節因子。
檢索模型總結
每種檢索模型各有千秋，適用不同的場景和應用。布爾模型、空間向量模型、概率模型等傳統檢索模型的排序方法一般通過構造相關性函數實現，然後按照相關性進行排序。檢索模型尤其概率模型比較適用於內容相關性排序，但內容相關性一般僅考慮query和doc的tf，idf，dl，avdl等因素，很難融合點擊反饋、文檔質量分、點擊模型等更多的排序因素。一個大型搜索引擎排序因子往往多達數十個乃至上百個（Google搜索排序因子超過200個），如果模型中參數過多，調參會變得非常困難，也很容易導致過擬合現象。
但正如前文所述，搜索引擎需要快速響應用戶搜索請求，無法在毫秒級時間內對每一個召回結果進行精確的機器學習排序，業界的主流的做法是首先進行第一輪的Top-k選取再對Top-k結果進行第二輪的精確重排序。傳統檢索模型尤其概率模型比較適用於文本內容相關性排序，能夠滿足快速獲取 Top-k候選結果集的需求。達觀數據（http://www.datagrand.com）搜索在第一輪Top-k選取中選用的是BM25F檢索模型。BM25F模型相比BM25模型考慮了文檔不同區域的加權統計，可以獲得更好的文本相關性，是目前最優的文本檢索模型。
機器學習排序（Machine Learning to rank）方法很容易融合多種特徵，且有成熟深厚的數學理論基礎，通過迭代優化參數，對於數據稀疏、過擬合等問題也有比較成熟的理論和實踐。
機器學習排序（Machine Learning to rank， 簡稱MLR）
機器學習排序系統框架
機器學習排序系統一般分為離線學習系統和在線預測排序系統。離線系統的設計需要靠特徵的選擇、訓練集的標註、MLR方法的選定、確定損失函數、以最小化損失函數為目標進行優化，以獲取排序模型的相關參數。在線預測排序系統將待預測結果輸入到機器學習得到的排序模型，即可得到結果的相關性得分，進而依據相關性得分得到搜素結果的最終排序。
圖3 機器學習排序系統框架
排序模型的選擇直接影響在線預測的效果。在類似電商時效性強的應用場景中，業務上經常需要根據商品庫存、價格等變化及時調整排序結果，由於排序模型的高度複雜性，人工干預只能做局部小範圍的調整，更多的還是要對模型進行實時的自動化更新。
對於這個問題，達觀數據（http://www.datagrand.com）在實踐中總結出了一個在線-近線-離線的三層系統架構，即Online-Nearline-Offline（在線-近線-離線）三層混合機制。離線系統負責day級全量訓練數據的學習、近線系統負責hour級模型的學習與更新、在線系統負責minut級的准實時反饋數據的學習與模型的更新。
特徵選取與特徵工程
特徵是演算法、模型的養料之源。特徵選擇的好壞直接關係到演算法訓練學習出的模型的效果。與傳統的文本分類不同，MLR輸出的是給定query的文檔集合的排序，不僅要考慮文檔自身的特徵，還要考慮query與文檔關聯關係的特徵。綜合來說，MLR需要考慮三個方面的特徵：
1）文檔本身的靜態特徵，包括文檔的文本特徵，如帶權重的詞向量，文檔不同域（主標題、段落標題、描述內容、錨文本、URL鏈接等）的TF、IDF、BM25和其他語言模型得分，也包括文檔的質量分、網頁文檔的PageRank等重要性得分。關於文檔的質量分，達觀搜索根據不同的業務場景有不同的計算指標，比如電商相關的商品的質量分計算除了要考慮商品本身的文本與圖片豐富度，更多的還要考慮商品的各種業務指標如銷量變化、收藏、價格、庫存、類別、上架時間、評論、商家信譽等級、是否作弊等，而媒體相關的文章的則需要考慮閱讀數、轉發數、贊數、收藏、評論、發文時間、主題類型等。
2）文檔和query關聯的特徵，比如query對應文檔的TD-IDF score， BM25 score等。
3）query本身的特徵，比如文本特徵，帶權重的詞向量，query長度，query所述的分類或主題，query的BM25的sum/avg/min/max/median分數，query上個月的熱度等。
在query與文檔的特徵工程中，除了從詞法上分析，還需要從「被闡述」的詞法所「真正想表達」的語義即概念上進行分析提取。比如一詞多義，同義詞和近義詞，不同的場景下同一個詞表達不同的意思，不同場景下不同的詞也可能表達相同的意思。LSA（隱語義分析）是處理這類問題的著名技術，其主要思想是映射高維向量空間到低維的潛在語義空間或概念空間，也即進行降維。具體做法是將詞項文檔矩陣做奇異值分解（SVD）
其中:
C是以文檔為行，詞項terms為列的矩陣（假設M x N），元素為term的tf-idf值。C被分解成3個小矩陣相乘；
U的每一列表示一個主題，其中的每個非零元素表示一個主題與一篇文章的相關性，數值越大越相關；
V表示keyword與所有term的相關性；
∑ 表示文章主題和keyword之間的相關性。
MLR演算法的選擇
MLR一般來說有三類方法：單文檔方法（Pointwise），文檔對方法（Pairwise），文檔列表方法（Listwise）。
Pointwise方法
Pointwise把文檔當成單個的點分別進行計算，實際上把一個Ranking 問題轉化成二值分類問題、回歸問題或多值分類問題。Query與文檔之間的相關度作為label，label一般劃分為: {Perfect， Excellent， Good， Fair， Bad} 。
Pointwise方法主要包括：Pranking (NIPSn2002)， OAP-BPM (EMCL 2003)， Ranking with Large Margin Principles (NIPS 2002)， ConstraintnOrdinal Regression (ICML 2005)
Pointwise的不足之處：
Pointwise使用傳統的分類，回歸或者OrdinalnRegression來對給定query下的單個文檔的相關度進行建模，沒有文檔位置對排序結果的影響，而回歸和分類的損失函數會盡量擬合所有的數據，演算法為了整體損失最小，有可能把排在前面的文檔的損失變得更大，或者把排在後面的文檔的損失變得更小，從而導致排序難以取得良好的效果。
Pairwise方法
在Pairwise中query與文檔對<di， dj>結合，假設在同一Query下，di的相關性大於dj，那麼我們可以把 di-dj標記為+1，dj-di標記為 -1，從而可以把原問題轉換為一個分類或回歸問題。
Pairwise方法主要包括：Ranking SVMn(ICANN 1999)， RankBoost (JMLR 2003)， LDM (SIGIR 2005)， RankNet (ICML 2005)， Frank (SIGIR 2007)，nGBRank (SIGIR 2007)， QBRank (NIPS 2007)， MPRankn(ICML 2007)， IRSVM (SIGIR 2006) 。
Pairwise的不足：
1）文檔較多時，pair的數目是平方級增長的，計算量太大；
2）Pair對不同級別之間的區分度一致對待，沒有對排在前面的結果作更好的區分。對於搜索引擎而言，用戶更傾向於點擊前幾頁的結果；
3）相關文檔集大小帶來模型的偏置。如果一個query下文檔遠多於另一query，n支持向量就會向該query偏置，導致分類器對後者區分不好。
Listwise方法
Listwise的輸入是query對應的一個文檔列表，計算每個query對應的文檔列表的得分。
Listwise有一種基於文檔排列的概率分布進行訓練的方法，通過對訓練實例的訓練找到一個最優的打分函數f，n使得f對query的打分結果的概率分布與訓練數據的實際排序儘可能相同。損失是按照訓練數據的實際排序概率分布與模型輸出的概率分布之間的KL距離來度量的。
Listwise演算法主要包括：LambdaRankn(NIPS 2006)， AdaRank (SIGIR 2007)， SVM-MAP (SIGIR 2007)， SoftRank (LR4IR 2007)， GPRank (LR4IR 2007)， CCA (SIGIR 2007)， RankCosine (IP&M 2007)， ListNet (ICML 2007)， ListMLEn(ICML 2008)，p-ListMLE 。
相比於Pointwise和Pairwise方法，Listwise方法直接優化給定查詢下整個文檔集合的序列，所以比較好的解決了以上演算法的缺陷。Listwise方法中的LambdaMART(是對RankNet和LambdaRank的改進)在Yahoo Learning to Rank Challenge表現出最好的性能。
達觀數據（http://www.datagrand.com）在搜索排序中使用了一種position-aware ListMLE(p-ListMLE)的演算法，ListMLE考慮了排序位置信息，但沒有對不同位置的重要程度進行區分。達觀數據（http://www.datagrand.com）搜索的實踐顯示同樣的條件下p-ListMLE的搜索效果指標nDCG要優於ListMLE.
點擊模型
我們在排序實踐中還發現MLR無法充分利用用戶對搜索結果的點擊反饋。俗話說群眾的眼睛是雪亮的，用戶對不同位置的搜索結果的點擊行為直接反應了搜索結果的好壞。我們根據用戶的歷史點擊記錄生成了點擊模型，通過點擊模型對MLR的結果再進行一次調整。
點擊模型又稱為點擊調權，搜索引擎根據用戶對搜索結果的點擊，可以挖掘出哪些結果更符合查詢的需求。點擊模型基於如下基本假設：
1)用戶的瀏覽順序是從上至下的。
2)需求滿足好的結果，整體點擊率一定高。
3)同一個query下，用戶點擊的最後一個結果之後的結果，可以假設用戶已經不會去查看了(一定程度上減弱了位置偏見)。
4)用戶進行了翻頁操作，或者有效的query變換，則可以認為前頁的結果用戶都瀏覽過，並且不太滿意。
5)用戶點擊的結果，如果引發後繼的轉化行為（比如電商搜索中的加購物車），則更有可能是用戶滿意的結果。
點擊模型日誌：
達觀數據（http://www.datagrand.com）搜索中MLR演算法優化+點擊模型對結果調權後搜索效果的顯著提升。
搜索排序效果評估
搜索引擎的排序是一個複雜的過程，特徵的選擇、演算法的變化、模型的更新都會導致排序結果的變化。那如何衡量一個排序結果的好壞呢？nMLR是用機器學習的方法來進行排序，所以評價MLR效果的指標就是評價排序的指標，主要包括一下幾種：
1)nWTA(Winners take all) 對於給定的查詢q，如果模型返回的結果列表中，第一個文檔是相關的，則WTA(q)=1，否則為0.
2)nMRR(Mean Reciprocal Rank) 對於給定查詢q，如果第一個相關的文檔位置是R(q)，則MRR(q)=1/R(q)。
3)nMAP(Mean Average Precision) 對於每個真實相關的文檔d，考慮其在模型排序結果中的位置P(d)，統計該位置之前文檔集合的分類準確率，取所有這些準確率的平均值。
4)nNDCG(Normalized Discounted Cumulative Gain) 是一種綜合考慮模型排序結果和真實序列之間關係的一種指標，也是最常用的衡量排序結果指標，詳見Wikipedia。
評價指標的使用
使用評價指標主要有手工標註答案和自動化評估兩種。手工標註方式既費時費力，又無法及時進行評估效果反饋。自動化評估方式對提高評估效率十分重要。最常用的自動評估方法是A/B testing系統。
A/B testing系統將用戶的流量在演算法模型A/B之間進行分配，即將通過用戶的分組號(bucket id)將用戶流量分別導入不同的演算法分支，用戶在不同演算法分支的行為連同分組號被記錄下來，後台分析系統分析這些行為數據可以生成一系列對比指標，通過這些指標可以直觀的分析演算法模型優劣。
總結
本文從搜索引擎排序的架構、檢索模型、機器學習排序模型與演算法到搜索效果評估，全面介紹了達觀搜索引擎排序實踐方面的一些經驗。達觀數據（http://www.datagrand.com）搜索團隊長期致力於基於大數據的搜索演算法優化，經過多年的積極探索，目前在開放搜索引擎的系統研發和效果提升方面已經積累了豐富的經驗。隨著DT時代的到來和深度學習興起，達觀數據（http://www.datagrand.com）技術團隊將在基於大數據的深度挖掘方面不斷探索和嘗試以給用戶帶來更好的產品和服務。
作者介紹
桂洪冠，達觀數據（http://www.datagrand.com）聯合創始人&技術副總裁，中國計算機學會（CCF）會員。曾服務於阿里、盛大、騰訊幾家公司，任騰訊文學、盛大文學數據中心高級研究員、阿里搜索技術專家等職務，主要負責搜索與廣告團隊。
推薦閱讀：