作者：桂洪冠

全球性的搜索引擎Google，看似簡單的搜索框背后隱藏的是極其復雜的系統(tǒng)架構和搜索算法，其中排序(以下統(tǒng)稱Ranking)的架構和算法更是關鍵部分。Google正是通過PageRank算法深刻改變搜索排序而一舉擊敗眾多競爭對手。本文將介紹有關搜索引擎排序的相關技術內(nèi)容。

Ranking是搜索引擎的核心技術，本文以搜索引擎的Ranking技術為切入點，從搜索引擎架構、檢索模型、機器學習算法、點擊模型、搜索效果評估等方面將達觀數(shù)據(jù)在搜索引擎Ranking的構建與優(yōu)化過程中的一些實踐經(jīng)驗與大家做分享。

1.經(jīng)典搜索排序架構

通常在線搜索引擎要求實時響應(毫秒級)用戶的搜索請求，使得在線對每個文檔進行基于模型的Ranking復雜計算不太現(xiàn)實，因而搜索的過程被分成兩個階段。

第一階段，是使用相對簡單的常用檢索模型對用戶query從索引中快速檢索出Top-k候選結果集。常用檢索模型主要有向量空間模型(Vector Space Model)、布爾模型(Boolean Model)、概率檢索模型BM25等，通常Top-k的候選集選取還結合離線計算質(zhì)量分高的文檔以排除掉文本相關但質(zhì)量分太低的文檔;

第二階段，則使用計算相對復雜的機器學習排序模型對Top-k候選結果集進行精確的重排序，因為Top-K的候選結果集數(shù)據(jù)量級一般不會很大，這一步計算可控。

圖1：一個經(jīng)典的搜索引擎排序架構

Ranking模型的訓練數(shù)據(jù)主要由query、文檔以及query與文檔的相關度組成，相關度可以標記成好、不好兩個級別或細粒度更高的Perfect、Excellent、Good、Fair、Bad五個級別。

訓練數(shù)據(jù)主要有兩種獲取方式：方式一是由搜索評測人員標記query與每個文檔的相關度進行手工的評測整理;方式二是通過自動分析搜索點擊日志生成。顯然，對于大規(guī)模機器學習排序模型的訓練數(shù)據(jù)人工標注的成本過高，而且人工也無法對模型進行相對實時的更新。我們(www.datagrand.com)主要通過方式二生成訓練數(shù)據(jù)，自動分析搜索點擊日志，分析用戶在同一個搜索session內(nèi)對query的各種變換、對搜索結果中不同位置的文檔的點擊行為以及后繼的篩選、翻頁等行為，綜合計算出一個可以標記訓練數(shù)據(jù)的搜索滿意度得分。

我們的搜索實踐表明，通過分析搜索點擊日志可以實現(xiàn)模型訓練數(shù)據(jù)的自動生成和實時更新，同時也可以達到比較滿意的搜索效果。

達觀搜索引擎架構

圖2 達觀搜索引擎架構

搜索引擎架構從底往上分別是分布式數(shù)據(jù)存儲層、索引構建與模型訓練層、索引數(shù)據(jù)與模型數(shù)據(jù)分發(fā)層、搜索核心層、開放接口層，同時系統(tǒng)架構還支持搜索引擎的索引配置和Ranking策略配置、以及搜索分析與效果評估。

搜索核心層是由query分析引擎、索引引擎、Ranking引擎構成。其中query分析引擎(QUERY ANALYSIS ENGINE)負責對用戶的query進行語義分析和意圖識別，包括query分詞、中心詞提取、query糾錯、query自動提示、query擴展等。索引引擎(INDEX ENGINE)執(zhí)行Top-k候選結果選取，這里我們綜合考慮了檢索模型的搜索相關性評分和文檔的靜態(tài)質(zhì)量分(離線計算)，另外在這一層還根據(jù)用戶的篩選條件以及業(yè)務層面的搜索結果配置進行了搜索結果的篩選和融合。排序引擎(RANKING ENGINE)利用機器學習模型對Top-k的候選集執(zhí)行第二輪的精確排序。RANKING ENGINE內(nèi)置一個算法插件框架，可以根據(jù)用戶配置的搜索排序策略加載相應的排序算法插件以及排序算法模型，同時還支持用戶對搜索流量劃分到不同的排序算法插件，以實現(xiàn)多個算法策略的同時在線A/B testing對比。

2.檢索模型的選擇

常見的檢索模型主要有布爾模型(Boolean Model)、向量空間模型(Vector Space Model)、概率檢索模型BM25與BM25F。

布爾模型

布爾(Boolean)模型是基于集合論和布爾代數(shù)的一種簡單檢索模型。它的特點是查找那些對于某個查詢詞返回為“真”的文檔。在該模型中，一個查詢詞就是一個布爾表達式，包括關鍵詞以及邏輯運算符。通過布爾表達式，可以表達用戶希望文檔所具有的特征。由于集合的定義是非常直觀的，Boolean模型提供了一個信息檢索系統(tǒng)用戶容易掌握的框架。查詢串通常以語義精確的布爾表達式的方式輸入。

布爾模型的主要優(yōu)點是直觀和簡單，缺陷在于完全匹配會導致被返回的結果文檔太多或者太少。

向量空間模型(Vector Space Model，VSM)

VSM概念簡單，即把對文本內(nèi)容的處理簡化為向量空間中的向量運算，并且它以空間上的相似度表達語義的相似度，直觀易懂。當文檔被表示為文檔空間的向量，就可以通過計算向量之間的相似性來度量文檔間的相似性。文本處理中最常用的相似性度量方式是余弦距離。

VSM的優(yōu)點：

1) 對term的權重的計算可以通過對term出現(xiàn)頻率的統(tǒng)計方法自動完成，使問題的復雜性大為降;

2) 支持部分匹配和近似匹配，并可以根據(jù)query和文檔之間的相似度對結果進行排序。

VSM缺點：

1) 基于term之間的獨立性假設，也即權重計算沒有考慮term之間的位置關系，也沒有考慮term的長度對權重的影響;

2) 計算量大。新文檔加入需要重新計算term的權重。

概率檢索模型

概率統(tǒng)計檢索模型(Probabilistic Retrieval Model)是另一種普遍使用的信息檢索算法模型，它應用文檔與查詢相關的概率來計算文檔與查詢的相似度。

二元獨立模型(BIM)

詞匯獨立性假設:文檔里面出現(xiàn)的詞沒有任何關聯(lián)，這樣一個文檔的出現(xiàn)就可以轉為各個單詞出現(xiàn)概率的乘積。

對于同時出現(xiàn)查詢qi以及文檔di的時候，對qi在di中出現(xiàn)的單詞進行“相關文檔/不相關文檔”統(tǒng)計，即可得到查詢與文檔的相關性估計值

N表示是文檔集中總的文檔數(shù);

R表示與query相關的文檔數(shù);

ri表示與query相關的文檔中含有的第i個term文檔個數(shù);

ni表示含有的第i個term文檔總數(shù);

0.5是平滑因子，避免出現(xiàn)log(0)。

BM25 模型

BM25 模型在BIM模型的基礎上考慮了查詢詞在Query以及Doc中的權重，并通過實驗引入了一些經(jīng)驗參數(shù)。BM25模型是目前最成功的內(nèi)容排序模型。

改進之后的 BM25 模型的擬合公式如下:

fi 表示term在D中的詞頻，K因子表示文檔長度的考慮，其計算公式為:

k1為經(jīng)驗參數(shù)， k1一般設置為1.2;

b為調(diào)節(jié)因子，將b設為0時，文檔長度因素將不起作用，經(jīng)驗表明一般b=0.75;

dl代表當前文檔的長度;

avdl代表所有文檔的平均長度;

qfi 表示在查詢中的詞頻，k2也為調(diào)節(jié)因子，因為在短查詢下這部分一般為1，為了放大這部分的差異，k2一般取值為 0~1000。

綜上所述，BM25模型結合了BIM因子、文檔長度、文檔詞頻和查詢詞頻進行公式融合，并利用k1，k2，b對各種因子進行權重的調(diào)整。

BM25F模型

BM25F模型對BM25模型的改進之處在于考慮了文檔不同區(qū)域的加權統(tǒng)計，例如文檔的標題和描述被賦予了不同的區(qū)域權重，在各個不同區(qū)域分別統(tǒng)計詞頻。

BM25F模型的計算公式為:

文檔D來自不同的u個域;

各個域對應的全總為Wk;

fui 表示詞頻;

Bu表示各個域的長度;

ulu 為域的實際長度，uvulu表示域的平均長度;

bu 為各個域長度的調(diào)節(jié)因子。

3.檢索模型總結

每種檢索模型各有千秋，適用不同的場景和應用。布爾模型、空間向量模型、概率模型等傳統(tǒng)檢索模型的排序方法一般通過構造相關性函數(shù)實現(xiàn)，然后按照相關性進行排序。檢索模型尤其概率模型比較適用于內(nèi)容相關性排序，但內(nèi)容相關性一般僅考慮query和doc的tf，idf，dl，avdl等因素，很難融合點擊反饋、文檔質(zhì)量分、點擊模型等更多的排序因素。一個大型搜索引擎排序因子往往多達數(shù)十個乃至上百個(Google搜索排序因子超過200個)，如果模型中參數(shù)過多，調(diào)參會變得非常困難，也很容易導致過擬合現(xiàn)象。

但正如前文所述，搜索引擎需要快速響應用戶搜索請求，無法在毫秒級時間內(nèi)對每一個召回結果進行精確的機器學習排序，業(yè)界的主流的做法是首先進行第一輪的Top-k選取再對Top-k結果進行第二輪的精確重排序。傳統(tǒng)檢索模型尤其概率模型比較適用于文本內(nèi)容相關性排序，能夠滿足快速獲取 Top-k候選結果集的需求。達觀數(shù)據(jù)(www.datagrand.com)搜索在第一輪Top-k選取中選用的是BM25F檢索模型。BM25F模型相比BM25模型考慮了文檔不同區(qū)域的加權統(tǒng)計，可以獲得更好的文本相關性，是目前最優(yōu)的文本檢索模型。

4.機器學習排序

機器學習排序(Machine Learning to rank)方法很容易融合多種特征，且有成熟深厚的數(shù)學理論基礎，通過迭代優(yōu)化參數(shù)，對于數(shù)據(jù)稀疏、過擬合等問題也有比較成熟的理論和實踐。

機器學習排序系統(tǒng)框架

機器學習排序系統(tǒng)一般分為離線學習系統(tǒng)和在線預測排序系統(tǒng)。離線系統(tǒng)的設計需要靠特征的選擇、訓練集的標注、MLR方法的選定、確定損失函數(shù)、以最小化損失函數(shù)為目標進行優(yōu)化，以獲取排序模型的相關參數(shù)。在線預測排序系統(tǒng)將待預測結果輸入到機器學習得到的排序模型，即可得到結果的相關性得分，進而依據(jù)相關性得分得到搜素結果的最終排序。

對于這個問題，我們在實踐中總結出了一個在線-近線-離線的三層系統(tǒng)架構，即Online-Nearline-Offline(在線-近線-離線)三層混合機制。離線系統(tǒng)負責day級全量訓練數(shù)據(jù)的學習、近線系統(tǒng)負責hour級模型的學習與更新、在線系統(tǒng)負責minut級的準實時反饋數(shù)據(jù)的學習與模型的更新。

特征選取與特征工程

特征是算法、模型的養(yǎng)料之源。特征選擇的好壞直接關系到算法訓練學習出的模型的效果。與傳統(tǒng)的文本分類不同，MLR輸出的是給定query的文檔集合的排序，不僅要考慮文檔自身的特征，還要考慮query與文檔關聯(lián)關系的特征。綜合來說，MLR需要考慮三個方面的特征：

1) 文檔本身的靜態(tài)特征，包括文檔的文本特征，如帶權重的詞向量，文檔不同域(主標題、段落標題、描述內(nèi)容、錨文本、URL鏈接等)的TF、IDF、BM25和其他語言模型得分，也包括文檔的質(zhì)量分、網(wǎng)頁文檔的PageRank等重要性得分。關于文檔的質(zhì)量分，達觀搜索根據(jù)不同的業(yè)務場景有不同的計算指標，比如電商相關的商品的質(zhì)量分計算除了要考慮商品本身的文本與圖片豐富度，更多的還要考慮商品的各種業(yè)務指標如銷量變化、收藏、價格、庫存、類別、上架時間、評論、商家信譽等級、是否作弊等，而媒體相關的文章的則需要考慮閱讀數(shù)、轉發(fā)數(shù)、贊數(shù)、收藏、評論、發(fā)文時間、主題類型等。

2) 文檔和query關聯(lián)的特征，比如query對應文檔的TD-IDF score， BM25 score等。

3) query本身的特征，比如文本特征，帶權重的詞向量，query長度，query所述的分類或主題，query的BM25的sum/avg/min/max/median分數(shù)，query上個月的熱度等。

在query與文檔的特征工程中，除了從詞法上分析，還需要從“被闡述”的詞法所“真正想表達”的語義即概念上進行分析提取。比如一詞多義，同義詞和近義詞，不同的場景下同一個詞表達不同的意思，不同場景下不同的詞也可能表達相同的意思。LSA(隱語義分析)是處理這類問題的著名技術，其主要思想是映射高維向量空間到低維的潛在語義空間或概念空間，也即進行降維。具體做法是將詞項文檔矩陣做奇異值分解(SVD)

C = U∑

其中:

C是以文檔為行，詞項terms為列的矩陣(假設M x N)，元素為term的tf-idf值。C被分解成3個小矩陣相乘;

U的每一列表示一個主題，其中的每個非零元素表示一個主題與一篇文章的相關性，數(shù)值越大越相關;

V表示keyword與所有term的相關性;

∑ 表示文章主題和keyword之間的相關性。

5.MLR算法的選擇

MLR一般來說有三類方法：單文檔方法(Pointwise)，文檔對方法(Pairwise)，文檔列表方法(Listwise)。

Pointwise方法

Pointwise把文檔當成單個的點分別進行計算，實際上把一個Ranking 問題轉化成二值分類問題、回歸問題或多值分類問題。Query與文檔之間的相關度作為label，label一般劃分為: {Perfect， Excellent， Good， Fair， Bad} 。

Pointwise方法主要包括：Pranking (NIPS 2002)， OAP-BPM (EMCL 2003)， Ranking with Large Margin Principles (NIPS 2002)， Constraint Ordinal Regression (ICML 2005)

Pointwise的不足之處：

Pointwise使用傳統(tǒng)的分類，回歸或者Ordinal Regression來對給定query下的單個文檔的相關度進行建模，沒有文檔位置對排序結果的影響，而回歸和分類的損失函數(shù)會盡量擬合所有的數(shù)據(jù)，算法為了整體損失最小，有可能把排在前面的文檔的損失變得更大，或者把排在后面的文檔的損失變得更小，從而導致排序難以取得良好的效果。

Pairwise方法

在Pairwise中query與文檔對<di， dj=””>結合，假設在同一Query下，di的相關性大于dj，那么我們可以把 di-dj標記為+1，dj-di標記為 -1，從而可以把原問題轉換為一個分類或回歸問題。

Pairwise的不足：

1) 文檔較多時，pair的數(shù)目是平方級增長的，計算量太大;

2) Pair對不同級別之間的區(qū)分度一致對待，沒有對排在前面的結果作更好的區(qū)分。對于搜索引擎而言，用戶更傾向于點擊前幾頁的結果;

3) 相關文檔集大小帶來模型的偏置。如果一個query下文檔遠多于另一query， 支持向量就會向該query偏置，導致分類器對后者區(qū)分不好。

Listwise方法

Listwise的輸入是query對應的一個文檔列表，計算每個query對應的文檔列表的得分。

Listwise有一種基于文檔排列的概率分布進行訓練的方法，通過對訓練實例的訓練找到一個最優(yōu)的打分函數(shù)f， 使得f對query的打分結果的概率分布與訓練數(shù)據(jù)的實際排序盡可能相同。損失是按照訓練數(shù)據(jù)的實際排序概率分布與模型輸出的概率分布之間的KL距離來度量的。

相比于Pointwise和Pairwise方法，Listwise方法直接優(yōu)化給定查詢下整個文檔集合的序列，所以比較好的解決了以上算法的缺陷。Listwise方法中的LambdaMART(是對RankNet和LambdaRank的改進)在Yahoo Learning to Rank Challenge表現(xiàn)出最好的性能。

我們在搜索排序中使用了一種position-aware ListMLE(p-ListMLE)的算法，ListMLE考慮了排序位置信息，但沒有對不同位置的重要程度進行區(qū)分。達觀搜索的實踐顯示同樣的條件下p-ListMLE的搜索效果指標nDCG要優(yōu)于ListMLE.

6.點擊模型

我們在排序實踐中還發(fā)現(xiàn)MLR無法充分利用用戶對搜索結果的點擊反饋。俗話說群眾的眼睛是雪亮的，用戶對不同位置的搜索結果的點擊行為直接反應了搜索結果的好壞。我們根據(jù)用戶的歷史點擊記錄生成了點擊模型，通過點擊模型對MLR的結果再進行一次調(diào)整。

點擊模型又稱為點擊調(diào)權，搜索引擎根據(jù)用戶對搜索結果的點擊，可以挖掘出哪些結果更符合查詢的需求。點擊模型基于如下基本假設：

1)用戶的瀏覽順序是從上至下的。

2)需求滿足好的結果，整體點擊率一定高。

3)同一個query下，用戶點擊的最后一個結果之后的結果，可以假設用戶已經(jīng)不會去查看了(一定程度上減弱了位置偏見)。

4)用戶進行了翻頁操作，或者有效的query變換，則可以認為前頁的結果用戶都瀏覽過，并且不太滿意。

5)用戶點擊的結果，如果引發(fā)后繼的轉化行為(比如電商搜索中的加購物車)，則更有可能是用戶滿意的結果。

點擊模型日志：

圖4 點擊模型(日志收集)

達觀搜索中MLR算法優(yōu)化+點擊模型對結果調(diào)權后搜索效果的顯著提升。

圖5 達觀數(shù)據(jù)搜索上線前后的效果對比

7.搜索排序效果評估

搜索引擎的排序是一個復雜的過程，特征的選擇、算法的變化、模型的更新都會導致排序結果的變化。那如何衡量一個排序結果的好壞呢? MLR是用機器學習的方法來進行排序，所以評價MLR效果的指標就是評價排序的指標，主要包括一下幾種：

1) WTA(Winners take all) 對于給定的查詢q，如果模型返回的結果列表中，第一個文檔是相關的，則WTA(q)=1，否則為0.

2) MRR(Mean Reciprocal Rank) 對于給定查詢q，如果第一個相關的文檔位置是R(q)，則MRR(q)=1/R(q)。

3) MAP(Mean Average Precision) 對于每個真實相關的文檔d，考慮其在模型排序結果中的位置P(d)，統(tǒng)計該位置之前文檔集合的分類準確率，取所有這些準確率的平均值。

4) NDCG(Normalized Discounted Cumulative Gain) 是一種綜合考慮模型排序結果和真實序列之間關系的一種指標，也是最常用的衡量排序結果指標，詳見Wikipedia。

評價指標的使用

使用評價指標主要有手工標注答案和自動化評估兩種。手工標注方式既費時費力，又無法及時進行評估效果反饋。自動化評估方式對提高評估效率十分重要。最常用的自動評估方法是A/B testing系統(tǒng)。

8.總結

本文從搜索引擎排序的架構、檢索模型、機器學習排序模型與算法到搜索效果評估，全面介紹了達觀搜索引擎排序實踐方面的一些經(jīng)驗。

End.

轉載請注明來自36大數(shù)據(jù)（36dsj.com)：36大數(shù)據(jù) » 一個可供參考的搜索引擎排序架構實踐案例