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

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

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

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

文章中的成果有兩個(gè)：

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

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

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

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

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

Modeling

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

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

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

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

模型內(nèi)容

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

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

損失函數(shù)

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

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

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

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

針對以用戶點(diǎn)擊為正樣本時(shí)的負(fù)樣本選擇：

從文檔池隨機(jī)選取作為負(fù)樣本，即easy case；

同一次會話中的曝光未點(diǎn)擊文檔作為負(fù)樣本，即hard case。

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

針對正樣本的選擇策略：

用戶點(diǎn)擊為正樣本

曝光即為正樣本

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

評估指標(biāo)

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

特征工程

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

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

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

「社交Embedding特征」：基于Facebook的社交圖譜學(xué)習(xí)用戶和實(shí)體的Embedding。

線上服務(wù)

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

量化調(diào)優(yōu)

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

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

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

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

首先是每個(gè)向量y的量化結(jié)果：

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

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

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

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

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

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

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

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

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

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

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

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

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

全鏈路優(yōu)化

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

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

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

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

hard樣本挖掘

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

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

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

不過hard樣本作為easy樣本的補(bǔ)充比單獨(dú)使用hard樣本有更好的效果，因?yàn)榫€上實(shí)際召回的數(shù)據(jù)分布中還是easy樣本居多。

Embedding模型集成

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

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

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

總的來說，曝光未點(diǎn)擊作負(fù)樣本對排序是關(guān)鍵，而對召回并無太大用處。