1. Introduction

廣告主通常會基于用戶標(biāo)簽來圈定廣告的目標(biāo)人群，比如廣告主想投奧迪的廣告可能會選擇北方 25～44 歲男性；投奔馳可能會選擇江浙地區(qū) 25 ～55 歲男性。

但受限于廣告主的先驗(yàn)知識，其選出來的目標(biāo)人群通常非常小，不能滿足投放要求。比如說廣告主想投放 100w 人，但通過用戶標(biāo)簽只選出來 10w 用戶，那幺剩下來 90w 用戶該怎幺選擇？

如果把廣告主圈出來的那 10w 用戶稱為種子用戶（ 「seed users」 ），那幺我們可以把需要額外提供的一批相似的用戶稱之為 「look-alike users」 。我們把這種基于種子用戶進(jìn)行相似人群擴(kuò)展的過程稱之為 「look-alike modeling」 。所以，look-alike 并不是某種特定的算法，而是一類建模方法的統(tǒng)稱。

2. Look-alike

Look-alike 有多種類型，包括基于相似計算的 「Similarity-based」 ，基于回歸模型預(yù)測的 「Regression-based」 ，基于標(biāo)簽相似性的 「Approximation-based」 ，基于用戶相似網(wǎng)絡(luò)的 「Graph-based」 ，基于 attention 優(yōu)化的 「Attention-based」 等。

但這種劃分有些不太合理，所以打算直接這里介紹一些經(jīng)典的 look-alike 模型。

2.1 Turn Look-alike

Weighted Criteria-based Algorithm 是由廣告科技公司 Turn 構(gòu)建的一套 Approximation-based 算法，發(fā)表于 ACM 2015，該算法主要是通過計算相關(guān)標(biāo)簽進(jìn)行人群擴(kuò)散，其從相似性、新奇性和質(zhì)量分三個角度綜合評估標(biāo)簽對。

相似性的計算公式有：

為指示函數(shù)，有標(biāo)簽的則為 1，否則為 0；為用戶數(shù)量。

但這種相似性計算公式可能有兩個問題：1. 由于數(shù)據(jù)稀疏，大部分用戶都只有少部分標(biāo)簽，所以大部分標(biāo)簽間的相關(guān)性都比較高；2. 相關(guān)標(biāo)簽要幺與種子用戶的標(biāo)簽非常大要幺非常小，這樣的計算結(jié)果就顯得很冗余。

所以作者采用了第二種相似性的計算公式：

此時，也有了新奇性的計算公式：

此外，還要定義質(zhì)量分 q，其主要包括 CTR、CVR、ROI，這個可以自己的特定場景自己定義。

我們對上述三種指標(biāo)進(jìn)行加權(quán)相乘：

取 log，加上權(quán)重得到最終的評估結(jié)果：

然后我們便算出了標(biāo)簽之間的分?jǐn)?shù)，并可以利用相似標(biāo)簽進(jìn)行人群擴(kuò)展。

2.2 Yahoo Look-alike

Yahoo Look-alike Model 是 Graph-based，其結(jié)合了 Similartiy-based 和 Regression-based 方法，系統(tǒng)架構(gòu)如下：

主要包含四個部分：

基于用戶間相似度構(gòu)建用戶相似網(wǎng)絡(luò)，并利用 LSH 對用戶進(jìn)行分桶；

粗召回：將種子用戶在同一個桶的用戶作為候選用戶；

特征篩選：基于特征 IV 進(jìn)行特征篩選，挑出能代表種子用戶的正特征；

精排序：計算用戶得分并排序，返回得分最高的用戶集。

用戶相似性定義如下：

其中，表示用戶的特征向量，權(quán)重矩陣為單特征或者特征組合的線性相關(guān)性的重要程度，這塊可以基于用戶特征重要性進(jìn)行構(gòu)建。其時間復(fù)雜度為，搜索的時間復(fù)雜度為。Yahoo 采用了 MinHash 和 LSH 進(jìn)行優(yōu)化，對用戶進(jìn)行分桶。

然后系統(tǒng)基于種子用戶召回同一分桶內(nèi)的用戶作為候選集。

由于不同的廣告主所關(guān)心的用戶特征不一樣，比如說 K12 教育關(guān)注年齡，化妝品關(guān)注性別，所以需要事先進(jìn)行特征篩選。綜合考慮性能和可解釋性原因，Yahoo 采用 Information Value 作為特征篩選的方法，并構(gòu)建權(quán)重矩陣，

其中，S 為廣告主提供的種子用戶；U 為備選用戶集合，可以通過采樣獲得也可以是整個用戶集合；為正特征，表示此特征在種子用戶中比其他用戶更重要。

此時，用戶評分方法位：

其中，為特征重要性；為特征的二階度量。

Yahoo 系統(tǒng)主要用了一階，權(quán)重為 IV，所以某個廣告投放下的用戶分?jǐn)?shù)為：

注意，這個分?jǐn)?shù)的取值為實(shí)數(shù)，如果想算概率可以用 sogmoid 函數(shù)壓縮一下。

2.3 Linkedin Look-alike

Linkedin 在 KDD 16 上發(fā)表了他們的 look-alike 系統(tǒng)，其架構(gòu)如下圖所示：

大致分為線上和線下兩部分，分別稱為 「Campaign-Agnostic Expansion」 和 「Campaign-Aware Expansion」 。

「Campaign-Agnostic Expansion」框架主要是利用實(shí)體進(jìn)行擴(kuò)展，比如 Data Mining 可以擴(kuò)展到 Big Data 和 Machine Learning。該框架的算法是采用 LR 模型去從歷史交互數(shù)據(jù)中捕獲實(shí)體間的相似性，這種擴(kuò)展方法可以直接在系統(tǒng)中使用 （不需要再去額外計算）。

「Campaign-Aware Expansion」框架是采用近鄰搜索，基于用戶的屬性進(jìn)行相似用戶擴(kuò)展。

無論是線上線下都需要用到相似度計算，這塊簡單介紹一下。

Linkedin 將每個實(shí)體建模為一個多域的結(jié)構(gòu)化 doc（structured multi-fielded document），并提取四種類型的字段，包括：n-grams/詞典、標(biāo)準(zhǔn)化命名的數(shù)據(jù)類型（standardized，公司名、行業(yè)名等）、派生數(shù)據(jù)類型（derived，互聯(lián)網(wǎng)公司可以派生出網(wǎng)絡(luò)開發(fā)、軟件開發(fā)等）和相近實(shí)體（proximities，基于用戶和公司交互的網(wǎng)絡(luò)確定其他相關(guān)公司）。舉個例子：

實(shí)體的結(jié)構(gòu)化 doc 會被建立成倒排索引庫，doc 的每個域的屬性都有一個特征向量，doc 同一域之間的相似度用 cos 相似度進(jìn)行計算：

doc 間的相似度利用域的相似度進(jìn)行線性加權(quán)：

其中，s 為不同領(lǐng)域的相似度，w 為不同領(lǐng)域的權(quán)重。

Linkedin 將用戶和公司分別進(jìn)行上述實(shí)體建模，然后將用戶關(guān)注的公司作為正樣本，沒關(guān)注的公司作為負(fù)樣本，并用 LR 模型進(jìn)行訓(xùn)練。

PS：會不會出現(xiàn)極端情況，導(dǎo)致召回量不夠。

2.4 Tecent Look-alike

Realtime Attention-based Look-alike Model（RALM）是微信看一看團(tuán)隊(duì)提出的，其發(fā)表于 KDD19，其將 Attention 融入到 look-alike 方法中并用于實(shí)時資訊推薦，其系統(tǒng)架構(gòu)如下圖所示：

其大致分為： 「離線訓(xùn)練」 、 「在線實(shí)時預(yù)測」 和 「在線異步處理」 ，分別對應(yīng)上圖的下、中、上三個位置。

2.4.1 offline Learning

「離線訓(xùn)練」部分包括 User Representation Learning 和 Look-alike Learning，前者用于學(xué)習(xí)用戶的特征向量，后者是基于用戶特征向量計算相似分?jǐn)?shù)。

User Representation Learning 模塊是基于 Youtube DNN 模型進(jìn)行改進(jìn)，左側(cè)為用戶特征，并用 Attention 代替  concat，左側(cè)為 Item 特征，然后整體做 SCE Loss 或者多分類，預(yù)測用戶的下一個點(diǎn)擊，訓(xùn)練完成后左側(cè)取最后一層隱層作為用戶的特征向量，模型結(jié)構(gòu)如下圖所示：

Look-alike Learning 模塊采用雙塔結(jié)構(gòu)，左邊輸入所有種子用戶的特征向量，右邊輸入目標(biāo)用戶的特征向量，其結(jié)構(gòu)如下圖所示：

這也是 RALM 能實(shí)現(xiàn)實(shí)時計算的主要原因，其將種子用戶特征代替 Item 特征，從而將 User-Item 模型轉(zhuǎn)換成 User-Users 模型。

所以，Look-alike Learning 模塊的關(guān)鍵在于表達(dá)種子用戶群體。

假設(shè)用戶會存在自己的個性信息，同時也有群體共性信息，那幺種子群體可以表示為：個性信息+共性信息。作者為此分別建模 Local Attention 和 Global Attention 學(xué)習(xí)出兩種 embedding：

Local Attention 是將種子采用乘法 attention，提取種子用戶群體中與目標(biāo)用戶相關(guān)的信息，捕捉用戶的局部信息。

Global Attention 只與種子用戶群體有關(guān)，所有采用 self-attention 的方式，將種子用戶乘以矩陣轉(zhuǎn)換，再乘以種子用戶自己，用其捕捉用戶群體自身內(nèi)部的興趣分布；

得到的 Local & Global embedding 之后，對此進(jìn)行加權(quán)求和，這就是種子用戶群體的全部信息。

但我們知道的 Attention 本身計算量非常大，所以無法滿足模型線上部署的耗時要求。為此，作者將種子用戶通過 k-means 進(jìn)行聚類，從而減少 Key 的數(shù)量。

完成 Look-alike Learning 之后，我們可以把右側(cè)用戶過 FC 的特征向量存儲起來，提供給在線服務(wù)。

2.4.2 Online Asyncheonous

在線異步處理，主要是處理與線上請求無關(guān)的計算，如：

基于用戶點(diǎn)擊日志，更新 Item 的種子用戶列表；

計算種子用戶的聚類中心，并配送給推薦系統(tǒng)；

計算 Global Embedding。

這些所有的東西都是定時更新的，不需要進(jìn)行實(shí)時計算。

2.4.3 Online Service

在線服務(wù)這塊，主要是拉取種子用戶的聚類中心、Global Embedding 和用戶的 Embedding，線上實(shí)時計算 Local Embedding，并計算最終的相似度。

PS：RALM 因?yàn)橛芯垲?，種子用戶出現(xiàn)異常點(diǎn)可能會出現(xiàn)點(diǎn)問題（當(dāng)然，內(nèi)部大概率優(yōu)化過了）。

2.5 Pinterest Look-alike

Pinterest look-alike 于 KDD 19 發(fā)表了他們的 look-alike 模型，其大致分為兩部分基于 LR 的分類模型和基于 Embedding 的相似搜索的模型。

2.5.1 Classifier-based Approach

Pinterest 的baseline 是用 LR 模型去做個分類模型，種子樣本為正樣本，隨機(jī)選取非種子樣本為負(fù)樣本，然后訓(xùn)練一個分類模型去給所有用戶打分排序。

2.5.2 Embedding-based Approach

Pinterest 探索的新方法，大致分為兩塊：一塊是訓(xùn)練 Embedding ，另一塊是基于 Embedding 和 LSH 找相似用戶。

首先是計算用戶的特征向量，其基于 StarSpace 的方法進(jìn)行訓(xùn)練（Pair-wise）：

用戶：用戶作為 Piar A，concat 用戶的離散特征+歸一化后的連續(xù)特征，經(jīng)過一層線性激活函數(shù)的 Dense，輸出得到用戶特征向量；

Topic：Item 的 Topic 作為 Pair B，經(jīng)過 lookup 得到 Topic 的特征向量；

訓(xùn)練樣本：取與用戶交戶過的 Item，用 Item 的 Topic 作為 Pair B；其他隨機(jī)選取 k 個的 Topic 作為負(fù)樣本，與用戶組成樣本對；

訓(xùn)練集：與用戶交戶過的 Item 的 Topic 作為正樣本，隨機(jī)選取的 k 個 Topic 作為負(fù)樣本，損失函數(shù)為：

訓(xùn)練停止：由于模型最終會用于解決種子用戶擴(kuò)散的問題，所以作者取種子用戶和非種子用戶，其中 90% 的種子用戶組成集合 K，從剩下 10%的種子用戶中取出一個，非種子用戶取出一個。定義相似性：，則訓(xùn)練停止的評估標(biāo)準(zhǔn)為：

訓(xùn)練的 tensorboard 如下圖所示：

模型重訓(xùn)：使用模型的最新版本定期（較長的時間）重新計算用戶嵌入，主要是目的是希望所有用戶的興趣都在變換，以捕捉用戶的行為和用戶的漂移。（為啥？）

得到用戶特征向量后，利用 LSH 對用戶進(jìn)行映射，然后基于種子用戶的個數(shù)進(jìn)行投票選出哪些區(qū)域，并取區(qū)域內(nèi)用戶作為擴(kuò)展用戶。

當(dāng)然還要考慮每個區(qū)域的用戶數(shù)量不同，所以種子集合 s  在區(qū)域的修正得分為：

其中，為區(qū)域內(nèi)的所有人數(shù)，為平滑因子，且。

下表為各區(qū)域人數(shù)（綠色為種子用戶，紅色為非種子用戶）：

下表為投票得分和概率得分的區(qū)別，可以看到區(qū)域排名有所變化：

作者重復(fù) m 次映射，得到最終的的概率得分：，每個用戶的映射結(jié)果為，所以用戶最終得分為：。

然后，選取得分大的用戶作為擴(kuò)展用戶。

可視化結(jié)果如下圖所示：

2.5.3 End-To-End System

介紹下 Pinterest 的系統(tǒng)：

下方為離線計算：

首先，離線計算好用戶的特征向量；

然后，基于種子用戶 m 次映射結(jié)果，計算所有區(qū)域的得分；

再者，對最近訪問過 Pinterest 用戶計算得分，排序后卡一個閾值。（利用桶排序，閾值大小根據(jù)廣告主需求排定，滿足廣告投放需求即可）；

最后，組成 <user, adv> 進(jìn)行廣告投放；

作者在實(shí)驗(yàn)的時候發(fā)現(xiàn)，Classifier-based 和 Embedding-based 混合起來的 Blending-based 比較好用：

3. Conclusion

看的這幾篇都是工業(yè)界的論文，最大的感觸是非常實(shí)用，工業(yè)風(fēng)滿滿，特別是最后一篇 Pinterest 的 Look-alike，論文細(xì)節(jié)非常多，也非常的實(shí)用。

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機(jī)制的實(shí)時Look-alike推薦模型 (jianshu.com)