背景

在线广告中，Lookalike能够帮助广告主高效的找到潜在用户。广告主上传少量的种子用户，Lookalike系统利用机器学习拓展出与种子用户相似的用户。例如，某APP希望增加激活用户。它可将已有用户作为种子，进而计算出相似用户。为了最大限度的提高潜在用户的质量，不同公司做了大量尝试：

• Yahoo：A Sub-linear, Massive-scale Look-alike Audience Extension System
• LinkedIn：Audience Expansion for Online Social Network Advertising

接下来将分别介绍一下，上述工作。

A Sub-linear, Massive-scale Look-alike Audience Extension System

这篇文章详细介绍了Lookalike在Yahoo的应用。整篇文章没有什么高大上的技术，但涉及大量的practical lessons。

相似度计算

以微博Lookalike系统为例，上传种子用户从1000到100万不等。这些种子用户的数量相比于整个微博用户而言，显得九牛一毛，而且并不是所有微博用户都与种子用户相关。因此，在相似度计算中，存在大量的冗余计算。为了减少计算量，论文将整个Lookalike过程拆分成两部分：

• 粗排序（global graph construction）：找出可能相似的用户
• 精排序（campaign specific modeling）：挖掘潜在用户

粗排序（global graph construction）

在相似度计算中，将用户视为点，相似度视为边，进而构造出一张user-2-user的全局图，能够极大程度上加速发现相似用户的速度。然而，天下没有免费的午餐，构建这张全局图的时间复杂度为

O(N2)

O

(

N

2

)

$O(N^{2})$。为了解决这个问题，论文中使用了MiniHash+LSH1来简化计算，进而构建一张全局图。另外在构建全局图时，论文使用的相似度计算公式为