全方位解讀｜Facebook的搜索是怎么做的？

今天要和大家分享的論文是來自Facebook的『Embedding based Retrieval in Facebook Search』。

不得不說，F(xiàn)家的文章還是一如既往濃濃的工業(yè)風，這篇論文從工程角度講解了一個召回的全流程，不管是做語義信息檢索召回還是推薦召回都值得認真學習。有過前幾個月的embedding召回方向工作后，深覺這篇論文對于做召回的同學來說有非常多可以總結思考的地方。

社交網(wǎng)絡中的搜索除了要考慮傳統(tǒng)web搜索中的query文本，搜索人所處的上下文也是需要重點考慮的，其中Facebook搜索場景中特有的社交圖譜便是典型的一種上下文。盡管向量檢索(Embedding_based Retrieval,EBR)已經(jīng)廣泛應用于web搜索，但是Facebook的搜索還是沿用之前的布爾匹配。這篇論文也是從升級Facebook搜索系統(tǒng)開始，總結Facebook將Embedding技術應用到其搜索場景過程中的踩坑經(jīng)驗。

文章中的成果有兩個：

一個統(tǒng)一的Embedding框架用于構建個性化搜索中的語義Embedding

一個基于倒排索引執(zhí)行Embedding檢索的系統(tǒng)

在進行整個系統(tǒng)的端到端優(yōu)化過程中，積累了大量的工程優(yōu)化經(jīng)驗和技巧，如ANN調參，全棧優(yōu)化等，還有一些如召回模型樣本構建，特征工程方面的技巧。

通過引入Embedding技術，使用Embedding表示query和文檔，將檢索問題轉化為Embedding空間的最近鄰搜索問題。Facebook搜索中的EBR不僅面臨海量數(shù)據(jù)的問題，如數(shù)十億甚至上百億的文檔，而且需要同時兼容Embedding檢索和布爾檢索。Facebook搜索還有一個獨特的點是用戶的搜索意圖不僅跟query的文本內(nèi)容有關，還跟提問者及其所處的環(huán)境有關，這一點是比常規(guī)的信息檢索方向要復雜的多的。

文章從模型、線上服務、全棧優(yōu)化三個方面介紹了引入Embedding技術過程中遇到的種種問題。

Modeling

作者將搜索中的預取看成召回優(yōu)化問題，給定搜索的query，及其對應的目標集和模型返回的topK集合，最大化topK結果集中的召回率，其中目標集一般是根據(jù)用戶點擊或人工打分的相關文檔。

召回優(yōu)化問題又可以看成是根據(jù)文檔和query之間的距離排序的問題，使用cos相似度度量被神經(jīng)網(wǎng)絡編碼成稠密向量的query和文檔之間的距離，再使用triplet loss作為召回目標學習Embedding編碼模型。

但Facebook的搜索和通常的信息檢索不同的地方是除了要考慮文本信息外，還要考慮用戶的個性化信息以及用戶所處的上下文。因此，文章提出統(tǒng)一Embedding，將查詢的query文本和搜索人及其所處上下文融合到一個embedding中。

接下來從統(tǒng)一Embedding模型內(nèi)容，模型損失函數(shù)，訓練數(shù)據(jù)的挖掘和評估指標四個方面介紹Facebook的Embedding模型。

模型內(nèi)容

首先「模型內(nèi)容」方面，和雙塔結構一樣，統(tǒng)一Embedding模型由三部分組成：query編碼器生成query的Embedding，文檔編碼器生成文檔的Embedding，相似度計算函數(shù)生成文檔和query之間的打分。Facebook的模型中，query和文檔的編碼器是共享部分參數(shù)的獨立模型。使用Cosine相似度作為相似函數(shù)，實際的Cosine距離定義為。

編碼器模型的輸入包括query和文檔的文本內(nèi)容、社交和其他上下文特征。比如query側的搜索人位置及其社交連接，文檔側group搜索時用到的小組聚合地址和社交群。原始特征大多為高基類別特征，進入模型的方式都是通過Embedding層，跟普通深度模型一樣。

損失函數(shù)

其次是「損失函數(shù)」，基于盡量把正例和負例的距離控制到一個固定距離之上的想法，Embedding模型的損失函數(shù)使用triplet loss：

其中表示向量u和v之間的距離度量，m是正負樣本之間的最小距離，N是從訓練集中挑選的三元組數(shù)目。實驗中發(fā)現(xiàn)margin參數(shù)m會導致KNN召回率有5~10%的波動，不同訓練任務的最優(yōu)margin差別也比較大。作者還認為隨機采樣作為triplet loss的負樣本對可以近似召回優(yōu)化任務，原因是一個正樣本匹配n個負樣本時，模型會優(yōu)化n個召回池中選取top1時的召回率，假設放大到實際服務時的召回池規(guī)模為N，近似優(yōu)化的就是召回topK=N/n的召回率。

訓練數(shù)據(jù)

然后是「訓練數(shù)據(jù)」挖掘方面，F(xiàn)acebook基于召回指標驗證召回流程中不同正負樣本的選擇策略。

針對以用戶點擊為正樣本時的負樣本選擇：

從文檔池隨機選取作為負樣本，即easy case；

同一次會話中的曝光未點擊文檔作為負樣本，即hard case。

結果表明，曝光未點擊作為負樣本的召回率遠低于隨機負樣本，約55%的召回率退化。作者認為原因在于全部以hard case做負樣本的訓練數(shù)據(jù)和實際召回任務面對的數(shù)據(jù)分布不一致，實際索引中大多數(shù)是和用戶query差別很大的easy case。

針對正樣本的選擇策略：

用戶點擊為正樣本

曝光即為正樣本

實驗表明，用戶點擊和曝光分別作為正樣本的召回指標相差不多，添加曝光數(shù)據(jù)并不能增加額外價值，增大訓練數(shù)據(jù)規(guī)模也不能。

評估指標

最后是「評估指標」，為了減少線上實驗成本，快速評估模型效果并定位問題，文章提出基于索引后的Embedding執(zhí)行KNN搜索再統(tǒng)計recall K指標。

特征工程

統(tǒng)一Embedding模型的優(yōu)勢之一就是可以通過融合文本之外的特征提升模型。Facebook的統(tǒng)一Embedding模型相比只基于文本特征的模型，在事件搜索上的召回率可以提升18%，分組搜索的召回率提升16%。統(tǒng)一Embedding模型中用到的特征主要有Text文本特征、位置特征、社交Embedding特征。

「文本特征」：使用字符n元組（character n-gram），相比Word n-gram有兩個好處，詞表大小會比較小，訓練更有效，還有就是緩解query和文檔側的OOV問題。而且在character三元組的基礎上增加Word n-gram表示仍然能穩(wěn)定的額外提升1.5%的召回率。由于Word n-gram的基數(shù)超高（約352M），需要使用hash減小詞表大小，結果表明，盡管會有hash沖突，仍然可以有額外模型提升。Facebook中的實體可以是人、小組、頁面或事件。對于這些實體，名字或標題是文本特征的主要來源，在實體搜索中，基于文本的Embedding模型在模糊匹配和糾錯方面表現(xiàn)的都比布爾匹配更好。

「位置特征」：在本地廣告、小組或事件的搜索場景中，位置匹配是很重要的。query側增加搜索人的城市，地區(qū)，國家和語言。文檔側增加管理員打的小組地域標簽。再加上前面的文本特征，模型能順利學習到query和文檔間隱式的位置匹配效果。

「社交Embedding特征」：基于Facebook的社交圖譜學習用戶和實體的Embedding。

線上服務

說完離線建模，再說說線上serving。Facebook的線上服務采用基于ANN的倒排索引搜索，出于兩點考慮：Embedding量化后存儲需求更小，便于集成到現(xiàn)有召回系統(tǒng)的倒排索引中。使用Faiss庫索引向量，再在現(xiàn)有倒排索引表中做高效NN搜索。

量化調優(yōu)

這里先介紹一下Embedding量化的背景知識，在向量集合中查找與指定向量距離最短的k個最近鄰，暴力搜索的時間在海量規(guī)模下是不現(xiàn)實的，Embedding量化就是為了解決向量空間搜索的效率問題，具體來說就是將原有的無限的向量空間映射到一個有限的向量集合（codebook）中，通過映射后的向量近似代表原向量。Embedding量化有三種形式：

「聚類量化」：常用的是k-means聚類，使用聚類后的類簇中心向量近似表示原始向量，類簇個數(shù)即為codebook大小。量化后，每個向量都用類簇中心id表示，向量之間的距離用各自所在類簇的中心向量距離近似表示。對應Faiss中的IndexIVFlat。

「乘積量化」：PQ量化，由于向量不同部分的分布不同，考慮對向量分段量化。將向量分成m個不同的部分，對每個部分進行向量量化，如平均劃分維度。最終的codebook大小為每個部分量化codebook大小的乘積，分塊量化中的每個部分量化也可以采取聚類量化實現(xiàn)。乘積量化可以大幅降低空間占用，每個向量可以用m個分塊聚類簇中心表示。

「粗糙量化+殘差量化」：層次量化，即Faiss中PQ量化IndexIVFPQ的實現(xiàn)。粗糙量化使用聚類量化，再對殘差結果進行細粒度的乘積量化，具體來說就是，每個向量先進行粗糙量化劃分到某個粗糙聚類簇里，對應某個類簇標識id，然后計算殘差向量（向量-聚類簇中心向量），對殘差向量進行分塊，執(zhí)行細粒度分塊殘差量化，每個殘差向量m塊，對應m個類簇標識id。因為原始向量聚類后，不同類簇可能分布的比較分散，樣本數(shù)極度不平衡，而計算殘差可以縮小這種不平衡。層次量化對于每個doc生成兩個字段：粗糙量化id，殘差量化code，用于實時檢索使用。其中，向量距離計算過程如下：

首先是每個向量y的量化結果：

其中，是粗糙量化結果，是殘差量化結果。然后是計算查詢向量x和y之間的距離：

第一項是x和y的粗糙量化結果向量的歐式距離，第二第三項與查詢向量x無關，可以提前計算好，第四項是x和y的殘差量化結果的內(nèi)積。

Facebook的Embedding量化使用的是層次量化：粗糙量化加殘差的乘積量化。粗糙量化階段的參數(shù)有num_cluster和具體量化算法IMI和IVF。乘積量化階段是pq_bytes和不同的乘積量化變種PQ，OPQ，帶PCA的PQ。還有一個nprobe參數(shù)，表示查詢query向量可以屬于多少類簇，決定了查詢近鄰時需要計算多少個粗糙類簇向量。文章中也介紹了ANN調參過程中的一些經(jīng)驗技巧：

調試召回率的同時關注掃描的文檔數(shù)。相同num_cluster和nprobe的情況下，對比不同的粗糙量化算法，可以發(fā)現(xiàn)類簇是極度不平衡的，導致查詢時掃描的文檔數(shù)各不相同。因此增加掃描的文檔數(shù)作為調試指標。

模型效果有較大提升時需重新調試ANN參數(shù)：ANN的表現(xiàn)和模型特征有關聯(lián)。模型變化較大時需要重新調試

優(yōu)先嘗試OPQ算法。OPQ算法的表現(xiàn)總是優(yōu)于其他算法。但OPQ會對Embedding執(zhí)行翻轉，因此需要重新調試num_cluster和nprobe參數(shù)才能得到相似的文檔掃描數(shù)。

pq_bytes設置為。乘積量化將原本的d維向量壓縮成x個字節(jié)的編碼。x越大精度越高但內(nèi)存和延時也越高。經(jīng)驗表明，最佳。

在線調試nprobe、num_cluster、pq_bytes。線上部署多組參數(shù)，對比驗證。

系統(tǒng)實現(xiàn)

Facebook原本的檢索引擎支持的是布爾檢索，為了避免創(chuàng)建新的系統(tǒng)，擴展了現(xiàn)有引擎的embedding字段以支持nn查詢操作（nn<key>:radius<radius>）。索引階段，每個文檔的Embedding被量化成一項（粗糙類簇）和一個payload（量化后的殘差向量）。查詢階段，nn查詢操作會被改寫成一個or運算項，or的內(nèi)容是和查詢Embedding最近的nprobe個粗糙類簇，對于匹配到的文檔再使用payload驗證半徑限制。這里作者針對NN操作對比了半徑查詢模式和top-K查詢模式，發(fā)現(xiàn)半徑模式更能平衡系統(tǒng)性能和結果質量，作者給出的理由是半徑模式下是一個受限NN搜索而topK需要掃描全部索引。

混合召回，支持NN操作符后，在現(xiàn)有的檢索引擎中就可以隨意組合embedding和布爾項的查詢。

模型服務,查詢Embedding模型和文檔Embedding模型同時訓練，獨立服務。對于查詢，是在線實時推斷。對于文檔則是spark離線批量推斷，再建立前向索引，增加額外的量化和PQ生成倒排索引。

查詢與索引選擇，為了提升查詢效率和結果質量，避免過度觸發(fā)、海量空間占用、無用內(nèi)容堆積等問題，作者在響應過程中使用了一些規(guī)則過濾掉EBR會表現(xiàn)差的查詢，比如用戶搜索之前搜索過或點擊過的東西，或者搜索意圖完全不同于Embedding模型的訓練含義的，只針對月活用戶、最近的事件、比較流行的頁面和小組做索引選擇加快搜索速度。

全鏈路優(yōu)化

Facebook搜索排序是個復雜的多階段排序系統(tǒng)，每層都是對前一層的結果提取精華。檢索層是最底層，也是EBR應用的地方，其結果會被后續(xù)的排序層排序過濾。每一階段的模型都是根據(jù)前一層的結果數(shù)據(jù)分布來做優(yōu)化的。因此，當前的排序系統(tǒng)是根據(jù)當前的檢索層設計模型，會導致新的檢索結果不會得到最優(yōu)排序。文章提出兩個方法解決這個問題：

Embedding信息作為排序特征之一：既能幫助排序識別來自EBR的新結果，又能提供所有結果的通用相似度。文中對比了使用query和文檔Embedding的Cosine相似度，哈達瑪積和原始Embedding三種選項，Cosine相似度特征總是最優(yōu)的。

訓練數(shù)據(jù)反饋循環(huán)：為了解決EBR精確率低的問題，增加人工打標的流程，使用標記后的數(shù)據(jù)重新訓練模型，提升模型精確率。

為了進一步提升EBR的效果，文中嘗試了兩個方向：hard樣本挖掘和Embedding模型集成。

hard樣本挖掘

hard樣本的說法來自于CV的分類任務，搜索召回中沒有類別的概念，無法直接應用CV的hard樣本挖掘方法。FB嘗試了兩種hard樣本挖掘的方法：hard負樣本挖掘和hard正樣本挖掘。

「hard負樣本挖掘」：模型分析時發(fā)現(xiàn)Embedding搜索的topK結果，通常具有相同的名字，而且即使提供社交特征，模型也并不總能把目標結果排的更靠前。因此猜測模型并不能很好的利用社交特征，很有可能是因為隨機挑選的負樣本區(qū)分度太明顯了，名字大多都是不一樣的。因此需要挖掘一些和正樣本相似度比較高的負樣本。文中嘗試了在線和離線兩種生成hard負樣本的方法：在線是指在訓練過程中，把同一個batch內(nèi)部的其他正樣本作為當前樣本的負樣本，實驗證明這一方法能在所有指標上大幅提升模型質量，且每個正樣本生成兩個hard負樣本是最優(yōu)的，但這個方法會被batch內(nèi)的正樣本池限制，有可能足夠hard的樣本數(shù)不夠；離線的方式則是個迭代的過程，根據(jù)規(guī)則從每個query生成topK的結果中選擇hard負樣本生成新的訓練數(shù)據(jù)，重新訓練模型。

「hard正樣本挖掘」：從搜索行為日志中挖掘搜索失敗的會話的潛在正樣本作為hard正樣本。使用這樣的hard正樣本能夠只以4%的點擊數(shù)據(jù)規(guī)模就達到同樣的效果。聯(lián)合hard正樣本和曝光數(shù)據(jù)訓練還能進一步提升模型效果。

不過hard樣本作為easy樣本的補充比單獨使用hard樣本有更好的效果，因為線上實際召回的數(shù)據(jù)分布中還是easy樣本居多。

Embedding模型集成

首先是通過實驗發(fā)現(xiàn)，相比easy樣本有助于表示檢索空間，hard樣本能夠幫助提升模型精度。隨機負樣本訓練出的模型能模擬實際的檢索數(shù)據(jù)分布，優(yōu)化的是較大K時的topK召回率，當K比較小時，效果不佳。但如果以精度優(yōu)化模型，比如以曝光未點擊做負樣本或離線hard負樣本，都會使得模型擅長小數(shù)據(jù)集內(nèi)排序而不適合召回任務。因此作者考慮以多階段的方式融合針對不同難度的樣本訓練模型，即第一階段關注模型召回率，第二階段專注于區(qū)分第一階段中比較相似的結果。文中試驗了兩種模型集成方式：權重拼接和模型級聯(lián)，而且這兩種都證明是有效的方式。

「權重拼接」：不同模型可以并行訓練，針對每個query和文檔對，每個模型都會得到一個相似度分值，根據(jù)每個模型分配到的權重得到這些分值的加權和作為最終的相似度分值。實際系統(tǒng)中通過將query和文檔的embedding各自規(guī)范化之后，將模型的權重乘到query側或文檔側再按照正常累加的方式計算相似度。這里文中的對比實驗發(fā)現(xiàn)，曝光未點擊作負樣本的數(shù)據(jù)訓練到的模型與離線挖掘的hard負樣本訓練到的模型相集成后比單獨使用曝光未點擊更得到線上比較理想的召回率提升。

「模型級聯(lián)」：與權重拼接的并行方式不同，模型級聯(lián)是串行的，在第一階段的結果上執(zhí)行第二階段的模型。同樣，曝光未點擊做負樣本并不能得到理想的召回率提升。而離線hard負樣本雖然能明顯提升召回率，但依然不如權重拼接的表現(xiàn)。這里文中還嘗試了另外一種級聯(lián)方式：使用文本Embedding預篩選出結果再使用統(tǒng)一Embedding對結果排序，取topK后返回。結果表明這種級聯(lián)比單獨使用統(tǒng)一Embedding召回有明顯線上提升。

總的來說，曝光未點擊作負樣本對排序是關鍵，而對召回并無太大用處。