開一個系列，主題是推薦算法工程師成長路徑。目標是希望填補書本上的機器學習理論與業界推薦算法工程師知識體系上的gap，了解一些業界模塊的通用玩法。目標群體是針對以下用戶:
上一篇，我們講了做推薦算法需要的工程基礎。這一篇我們正式進入推薦系統，來講講召回是怎麼做的。
如果你是第一次了解推薦系統，我先來簡單解釋下。以新聞推薦為例，推薦系統的目標是從千萬甚至更多的新聞候選集中，挑選出用戶最可能感興趣的k篇新聞。(下文為了論述簡單，我會默認k=10)。出於平衡效果和延遲的原因，現在的推薦系統大多把它劃分為召回和排序兩個階段。
而整個過程，需要在非常短的時間，比如1s內，完成全部的計算。
所以，召回階段面臨的問題是，怎樣可以快速從海量內容中找到用戶最感興趣的Top k的候選。
有一些經典的推薦系統的算法，比如協同過濾，包括用戶協同過濾(和你相似愛好的人也看過什麼)和文章維度的協同過濾(看過你看過的文章的人還看過什麼)，這些算法也是可以用在召回階段的。這些算法在橫空出世的時候也是名噪一時無人能出其右。但是現在，這些算法在實際應用的問題中或多或少的會面臨一些問題，比如用戶協同過濾容易把人都相似到一些全局最活躍的用戶上，而文章協同過濾則沒有考慮到當前用戶的喜好。所以已經漸漸地被業界淘汰了。
目前在召回階段基本都是通過向量化召回找到用戶最感興趣的內容。而這個向量怎麼訓練和得到呢？我們來從經典的FM召回談起。
對於不熟悉FM這個算法的同學，我強烈建議你們補補課。這是推薦系統近十年來可以說最為劃時代意義的一種方法。後面你會發現，所謂深度學習的一套算法，只不過是在FM基礎上做了一些搭積木的工作。
談起FM(Factorization Machine)，如果要從理論上追根溯源的話，有點類似於LR(Logistic Regression)。
在推薦和廣告領域，預估的目標是二分類問題(用戶是否點擊)，特徵基本都是網絡上的屬性特徵——離散值比較多，而連續值比較少。在這種場景下使用LR做預估，通常的做法是要把離散特徵變成一個個虛擬變量，然後進行邏輯回歸。
在這種數學表達形式下，各個特徵都是獨立考慮的，並沒有考慮到特徵之間的相互關係。但實際上，特徵之間是有可能有相互關聯的，比如男性用戶一般會比較喜歡遊戲，而女性用戶一般會喜歡時尚。為了建模這種相關性，可以在模型中引入二階項
為了解決這個問題，FM引入了一個類似矩陣分解的思路，給每一個類別變量引入了一個向量
我們來想一下這個v的更新，還是女性用戶和Dota2的例子，女性用戶的所有樣本可以更新
至於v向量維度選擇的數學依據，其實矩陣分解有關，我們這裡就不提了。如果對此有疑問的同學，可以參考文末的參考文獻來學習。在實際的應用中，v的維度大多數情況下是一個實驗出來的超參數。
推薦系統中，最主要的問題其實是user和item的匹配問題。而最能體現每一個用戶或者物品獨一無二性的，其實是用戶側的user_id，和物品的item_id。如果一個推薦系統能夠很好的學習到user_id和item_id，那麼這個推薦系統一定是非常準確的。
所以我們來看一個最簡單的FM模型：只有user_id和item_id的模型。我們可以把user_id和item_id套入上面的FM公式，可以得到這樣一個變換：
所以一個FM模型的訓練結果的召回問題，就轉化成為一個內積運算找Top k的問題。而內積運算，可以很輕易的轉化為cos距離。這個問題就更加進一步的轉化為，給定一個user向量，找和它距離最近的Top k的item，也就是我們熟知的kNN問題。
這裡順帶說一句，FFM召回作為FM召回的變體，和FM召回實際上是相通的。
在把向量化召回的問題轉化為kNN的問題之後，其實我們已經把這個問題解了80%，剩下的就是看怎麼樣優雅的解決這個kNN問題。
當然kNN這個問題不僅局限於推薦的召回場景。更一般的場景是，比如在搜索中，針對給定的query，怎麼從海量候選中找到和這個query最相關的候選結果。
kNN是一種實踐和理論結合的典型問題：實際應用中有需要(解決大量候選的召回問題)，於是可以把這個問題抽象成一個具體的數學問題。然後設定benchmark，學術界和工業界一起不斷迭代優化，成為一個具體的研究方向。
首先暴力計算肯是不行的。暴力計算就是維護一個大小為k的堆，然後遍歷所有的候選，這樣的時間複雜度是O(Nlog(k))。當N非常大，比如千萬級別的候選，顯然查詢是非常慢的。
kd-tree: 這是最經典的kNN的查詢算法。基於坐標軸進行二叉樹分叉，這樣可以快速的把所有候選劃分到不同的超矩形中。進行查找時，根據二叉樹快速找到的二叉樹子節點。但是當向量維度比較高時，這種算法一般效果比較差。
ball-tree: 實際上是kd-tree的一種改進。不再局限於坐標軸的分叉，沿著一系列的hyper-spheres來分割數據，空間中可以用球來表示。每一個子節點中有一個代表中心的節點，以及一簇候選。進行查找時，先比較目標向量與眾多劃分出來的球型結構的中心節點的距離，找到最近的中心節點，然後再在這個球型結構的候選中找最近的k個候選。
HNSW: 先說NSW，先把候選根據距離構建成一個圖，構建時距離最近的點被連成了邊。進行查找時，先隨機選擇初始位置，然後沿著邊即可遞歸的找到所有的最相近的候選；HNSW是在NSW的基礎上，加入了層級信息，類似於引入了索引，加快了搜索的速度，以及落入奇怪連通分支的概率。
囿於篇幅，我們不展開說這幾種相似算法具體的實現細節了。感興趣的同學可以在文末的參考文獻找到這幾種方法的原始論文，看下實現細節。
不過需要注意的一點是，不管這三種的哪一種方法，都是需要離線計算的——不管是kd-tree的方形結構，還是ball-tree的球形結構，抑或者是HNSW的層級結構，都需要先在離線準備好這樣一個結構；才可以實現在線的快速計算。
具體在實現中哪個效果好，還是要結合自己的數據和實驗效果，進行取捨；同時還要方便測試和迭代，不同的應用場景肯定效果是不同的，沒法一概而論。
上文我們著重講了FM模型到向量化召回的由來。現在都是深度學習時代了，有沒有可能在召回側加一些深度學習的網絡呢？
需要注意的一點是，除了我們要訓練出一個各項指標優秀的模型之外，我們還需要儘可能的保留轉化為向量化召回的操作空間，否則等待我們的就是百萬候選集上的暴力計算。所以，一般意義上的Wide & Deep肯定是不行的。
所以，目前業界的一個比較通用的解決方案是: user側接一個塔，item側接一個塔，然後兩個tower的頂部，把兩個tower的結果做點積。這樣就是一個，接了深度網絡(保證效果)，同時在user側和item側分開計算(保證可以進行kNN運算)的召回模型了。
比如YouTube的這篇經典的論文，圖中展示的召回模型的所有特徵基本都是user側的feature，所以這個模型結構實際上是user側的tower。item側的特徵在這張圖裡沒有出現。
當模型變成雙塔後，進行向量化召回的item側塔的knn結構構建的時候，就不再是以item_id對應的embedding做構建了，而是需要把每一個item的特徵的原始值收集起來，先一起forward得到item側最終要和user側進行點積的embedding。然後再用這個embedding進行kNN相似結構的構建。
同樣，user側需要最終執行kNN相似計算的，只是user側最終的embedding，這意味著user側也可以在召回運算進行之前進行一些預計算，得到最終的user_embedding。這樣召回側的實際計算，依然也就變成了user_embedding * item_embedding的經典kNN問題了。
在YouTube的論文中，召回問題被看成了一個多分類問題。這篇論文中對於召回問題的解法，類似word2vec。在把目標換成了多分類問題後，損失函數自然變成了多分類的softmax。為了解決計算效率問題，採用了隨機負採樣和層次softmax來優化。這種解法更像是一個nlp領域的解法，並且softmax生成的embedding的用法與FM生成的embedding的用法基本類似。這裡就不在具體的說明了。
本文講述的只是FM召回的演化過程。實際應用中，除了這種召回可能還會有其他類型的召回，比如通過item2vec根據文章的相似性來召回，整體的思路與本文論述的FM召回大同小異。
YouTube論文: https://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/45530.pdf
FM論文: https://cseweb.ucsd.edu/classes/fa17/cse291-b/reading/Rendle2010FM.pdf
ball-tree: https://arxiv.org/pdf/1511.00628.pdf
hnsw: https://arxiv.org/pdf/1603.09320.pdf
有興趣的同學們也可以在公眾號內回復「召回論文」下載上述的四篇論文。最後總結一下這篇文章。這文章中我們講了基礎的FM模型，以及如何從FM模型發展成為一個向量化召回問題，最終深度化變成雙塔召回模型。
如果你對今天的內容有什麼思考與解讀，歡迎給我留言，我們一起討論。也歡迎在看轉發。
下一次我們將進入排序模塊，看下如何從召回的千級別候選中精挑細選出用戶最關心的那幾篇新聞。