五个工业风满满的 Look-alike 算法
1. Introduction
廣告主通常會基于用戶標簽來圈定廣告的目標人群，比如廣告主想投奧迪的廣告可能會選擇北方 25～44 歲男性；投奔馳可能會選擇江浙地區 25 ～55 歲男性。
但受限于廣告主的先驗知識，其選出來的目標人群通常非常小，不能滿足投放要求。比如說廣告主想投放 100w 人，但通過用戶標簽只選出來 10w 用戶，那么剩下來 90w 用戶該怎么選擇？
如果把廣告主圈出來的那 10w 用戶稱為種子用戶（「seed users」），那么我們可以把需要額外提供的一批相似的用戶稱之為 「look-alike users」。我們把這種基于種子用戶進行相似人群擴展的過程稱之為 「look-alike modeling」。所以，look-alike 并不是某種特定的算法，而是一類建模方法的統稱。
2. Look-alike
Look-alike 有多種類型，包括基于相似計算的 「Similarity-based」，基于回歸模型預測的 「Regression-based」，基于標簽相似性的 「Approximation-based」，基于用戶相似網絡的 「Graph-based」，基于 attention 優化的 「Attention-based」等。
但這種劃分有些不太合理，所以打算直接這里介紹一些經典的 look-alike 模型。
2.1 Turn Look-alike
Weighted Criteria-based Algorithm 是由廣告科技公司 Turn 構建的一套 Approximation-based 算法，發表于 ACM 2015，該算法主要是通過計算相關標簽進行人群擴散，其從相似性、新奇性和質量分三個角度綜合評估標簽對。
相似性的計算公式有：
為指示函數， 有 標簽的則為 1，否則為 0； 為用戶數量。
但這種相似性計算公式可能有兩個問題：1. 由于數據稀疏，大部分用戶都只有少部分標簽，所以大部分標簽間的相關性都比較高；2. 相關標簽要么與種子用戶的標簽非常大要么非常小，這樣的計算結果就顯得很冗余。
所以作者采用了第二種相似性的計算公式：
此時，也有了新奇性的計算公式：
此外，還要定義質量分 q，其主要包括 CTR、CVR、ROI，這個可以自己的特定場景自己定義。
我們對上述三種指標進行加權相乘：
取 log，加上權重得到最終的評估結果：
然后我們便算出了標簽之間的分數，并可以利用相似標簽進行人群擴展。
2.2 Yahoo Look-alike
Yahoo Look-alike Model 是 Graph-based，其結合了 Similartiy-based 和 Regression-based 方法，系統架構如下：
主要包含四個部分：
基于用戶間相似度構建用戶相似網絡，并利用 LSH 對用戶進行分桶；
粗召回：將種子用戶在同一個桶的用戶作為候選用戶；
特征篩選：基于特征 IV 進行特征篩選，挑出能代表種子用戶的正特征；
精排序：計算用戶得分并排序，返回得分最高的用戶集。
用戶相似性定義如下：
其中， 表示用戶 的特征向量，權重矩陣 為單特征或者特征組合的線性相關性的重要程度，這塊可以基于用戶特征重要性進行構建。其時間復雜度為 ，搜索的時間復雜度為 。Yahoo 采用了 MinHash 和 LSH 進行優化，對用戶進行分桶。
然后系統基于種子用戶召回同一分桶內的用戶作為候選集。
由于不同的廣告主所關心的用戶特征不一樣，比如說 K12 教育關注年齡，化妝品關注性別，所以需要事先進行特征篩選。綜合考慮性能和可解釋性原因，Yahoo 采用 Information Value 作為特征篩選的方法，并構建權重矩陣 ，
其中，S 為廣告主提供的種子用戶；U 為備選用戶集合，可以通過采樣獲得也可以是整個用戶集合； 為正特征，表示此特征在種子用戶中比其他用戶更重要。
此時，用戶評分方法位：
其中， 為特征重要性； 為特征的二階度量。
Yahoo 系統主要用了一階，權重為 IV，所以某個廣告投放下的用戶分數為：
注意，這個分數的取值為實數，如果想算概率可以用 sogmoid 函數壓縮一下。
2.3 Linkedin Look-alike
Linkedin 在 KDD 16 上發表了他們的 look-alike 系統，其架構如下圖所示：
大致分為線上和線下兩部分，分別稱為 「Campaign-Agnostic Expansion」 和 「Campaign-Aware Expansion」。
「Campaign-Agnostic Expansion」 框架主要是利用實體進行擴展，比如 Data Mining 可以擴展到 Big Data 和 Machine Learning。該框架的算法是采用 LR 模型去從歷史交互數據中捕獲實體間的相似性，這種擴展方法可以直接在系統中使用 （不需要再去額外計算）。
「Campaign-Aware Expansion」 框架是采用近鄰搜索，基于用戶的屬性進行相似用戶擴展。
無論是線上線下都需要用到相似度計算，這塊簡單介紹一下。
Linkedin 將每個實體建模為一個多域的結構化 doc（structured multi-fielded document），并提取四種類型的字段，包括：n-grams/詞典、標準化命名的數據類型（standardized，公司名、行業名等）、派生數據類型（derived，互聯網公司可以派生出網絡開發、軟件開發等）和相近實體（proximities，基于用戶和公司交互的網絡確定其他相關公司）。舉個例子：
實體的結構化 doc 會被建立成倒排索引庫，doc 的每個域的屬性都有一個特征向量，doc 同一域之間的相似度用 cos 相似度進行計算：
doc 間的相似度利用域的相似度進行線性加權：
其中，s 為不同領域的相似度，w 為不同領域的權重。
Linkedin 將用戶和公司分別進行上述實體建模，然后將用戶關注的公司作為正樣本，沒關注的公司作為負樣本，并用 LR 模型進行訓練。
PS：會不會出現極端情況，導致召回量不夠。
2.4 Tecent Look-alike
Realtime Attention-based Look-alike Model（RALM）是微信看一看團隊提出的，其發表于 KDD19，其將 Attention 融入到 look-alike 方法中并用于實時資訊推薦，其系統架構如下圖所示：
其大致分為：「離線訓練」、「在線實時預測」和「在線異步處理」，分別對應上圖的下、中、上三個位置。
2.4.1 offline Learning
「離線訓練」部分包括 User Representation Learning 和 Look-alike Learning，前者用于學習用戶的特征向量，后者是基于用戶特征向量計算相似分數。
User Representation Learning 模塊是基于 Youtube DNN 模型進行改進，左側為用戶特征，并用 Attention 代替 ?concat，左側為 Item 特征，然后整體做 SCE Loss 或者多分類，預測用戶的下一個點擊，訓練完成后左側取最后一層隱層作為用戶的特征向量，模型結構如下圖所示：
Look-alike Learning 模塊采用雙塔結構，左邊輸入所有種子用戶的特征向量，右邊輸入目標用戶的特征向量，其結構如下圖所示：
這也是 RALM 能實現實時計算的主要原因，其將種子用戶特征代替 Item 特征，從而將 User-Item 模型轉換成 User-Users 模型。
所以，Look-alike Learning 模塊的關鍵在于表達種子用戶群體。
假設用戶會存在自己的個性信息，同時也有群體共性信息，那么種子群體可以表示為：個性信息+共性信息。作者為此分別建模 Local Attention 和 Global Attention 學習出兩種 embedding：
Local Attention 是將種子采用乘法 attention，提取種子用戶群體中與目標用戶相關的信息，捕捉用戶的局部信息。
Global Attention 只與種子用戶群體有關，所有采用 self-attention 的方式，將種子用戶乘以矩陣轉換，再乘以種子用戶自己，用其捕捉用戶群體自身內部的興趣分布；
得到的 Local & Global embedding 之后，對此進行加權求和，這就是種子用戶群體的全部信息。
但我們知道的 Attention 本身計算量非常大，所以無法滿足模型線上部署的耗時要求。為此，作者將種子用戶通過 k-means 進行聚類，從而減少 Key 的數量。
完成 Look-alike Learning 之后，我們可以把右側用戶過 FC 的特征向量存儲起來，提供給在線服務。
2.4.2 Online Asyncheonous
在線異步處理，主要是處理與線上請求無關的計算，如：
基于用戶點擊日志，更新 Item 的種子用戶列表；
計算種子用戶的聚類中心，并配送給推薦系統；
計算 Global Embedding。
這些所有的東西都是定時更新的，不需要進行實時計算。
2.4.3 Online Service
在線服務這塊，主要是拉取種子用戶的聚類中心、Global Embedding 和用戶的 Embedding，線上實時計算 Local Embedding，并計算最終的相似度。
PS：RALM 因為有聚類，種子用戶出現異常點可能會出現點問題（當然，內部大概率優化過了）。
2.5 Pinterest Look-alike
Pinterest look-alike 于 KDD 19 發表了他們的 look-alike 模型，其大致分為兩部分基于 LR 的分類模型和基于 Embedding 的相似搜索的模型。
2.5.1 Classifier-based Approach
Pinterest 的baseline 是用 LR 模型去做個分類模型，種子樣本為正樣本，隨機選取非種子樣本為負樣本，然后訓練一個分類模型去給所有用戶打分排序。
2.5.2 Embedding-based Approach
Pinterest 探索的新方法，大致分為兩塊：一塊是訓練 Embedding ，另一塊是基于 Embedding 和 LSH 找相似用戶。
首先是計算用戶的特征向量，其基于 StarSpace 的方法進行訓練（Pair-wise）：
用戶：用戶作為 Piar A，concat 用戶的離散特征+歸一化后的連續特征，經過一層線性激活函數的 Dense，輸出得到用戶特征向量；
Topic：Item 的 Topic 作為 Pair B，經過 lookup 得到 Topic 的特征向量；
訓練樣本：取與用戶交戶過的 Item，用 Item 的 Topic 作為 Pair B；其他隨機選取 k 個的 Topic 作為負樣本，與用戶組成樣本對；
訓練集：與用戶交戶過的 Item 的 Topic 作為正樣本，隨機選取的 k 個 Topic 作為負樣本，損失函數為：
訓練停止：由于模型最終會用于解決種子用戶擴散的問題，所以作者取種子用戶和非種子用戶，其中 90% 的種子用戶組成集合 K，從剩下 10%的種子用戶中取出一個 ，非種子用戶取出一個 。定義相似性： ，則訓練停止的評估標準為：
訓練的 tensorboard 如下圖所示：
模型重訓：使用模型的最新版本定期（較長的時間）重新計算用戶嵌入，主要是目的是希望所有用戶的興趣都在變換，以捕捉用戶的行為和用戶的漂移。（為啥？）
得到用戶特征向量后，利用 LSH 對用戶進行映射，然后基于種子用戶的個數進行投票選出哪些區域，并取區域內用戶作為擴展用戶。
當然還要考慮每個區域的用戶數量不同，所以種子集合 s ?在區域 的修正得分為：
其中， 為區域內的所有人數，、 為平滑因子，且 。
下表為各區域人數（綠色為種子用戶，紅色為非種子用戶）：
下表為投票得分和概率得分的區別，可以看到區域排名有所變化：
作者重復 m 次映射，得到最終的 的概率得分：，每個用戶的映射結果為 ，所以用戶最終得分為：。
然后，選取得分大的用戶作為擴展用戶。
可視化結果如下圖所示：
2.5.3 End-To-End System
介紹下 Pinterest 的系統：
下方為離線計算：
首先，離線計算好用戶的特征向量；
然后，基于種子用戶 m 次映射結果，計算所有區域的得分；
再者，對最近訪問過 Pinterest 用戶計算得分，排序后卡一個閾值。（利用桶排序，閾值大小根據廣告主需求排定，滿足廣告投放需求即可）；
最后，組成 <user, adv> 進行廣告投放；
作者在實驗的時候發現，Classifier-based 和 Embedding-based 混合起來的 Blending-based 比較好用：
3. Conclusion
看的這幾篇都是工業界的論文，最大的感觸是非常實用，工業風滿滿，特別是最后一篇 Pinterest 的 Look-alike，論文細節非常多，也非常的實用。
4. Reference
《Effective Audience Extension in Online Advertising》
《A Sub-linear, Massive-scale Look-alike Audience Extension System》
《Audience Expansion for Online Social Network Advertising》
《Real-time Attention Based Look-alike Model for Recommender System》
《Finding Users Who Act Alike: Transfer Learning for Expanding Advertiser Audiences》
RALM：微信看一看中基于Attention機制的實時Look-alike推薦模型 (jianshu.com)
總結
以上是生活随笔為你收集整理的五个工业风满满的 Look-alike 算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Win7打印时文档被挂起的解决方法
- 下一篇： 腾讯视频如何设置主设备