对于一个 CPC 结算的竞价广告系统，需要得到广告候选集合，并计算每个候选的点击率。这对应着两个竞价广告关键的计算问题，即“广告检索”和“广告排序”。
搜索广告系统
查询扩展
需求方需要通过扩展关键词获得更多的流量，供给侧则需要借此来变现更多的流量和提高竞价的激烈程度。
相关的方法有很多，这里介绍三种主要的思路：
基于推荐的方法：
- 考虑用户的一个会话（$$s = {1, \cdots, M}$$）和一组关键词 $$w = {1, \cdots, N}$$ 对应的交互强度矩阵 $${x_{mn}}_{M \times N}$$，矩阵的值表示用户在这个会话中搜索对应关键词的次数。
- 推荐方法的基本任务：基于上述矩阵中的已知元素值，去预测填充矩阵中没有观测的单元。
- 协同过滤：这样的问题也被称为“协同过滤问题”（Collaborative Filtering，CF），即根据群体用户的选择关联性进行推荐的问题。
- 算法：协同过滤的推荐算法可以主要分为“基于内存的非参数方法”和“基于模型的参数化方法”，各种推荐问题的本质都是对交互强度矩阵进行平滑。
基于主题模型的方法：
基于历史效果的方法：
广告检索
布尔表达式检索
相关性检索
基于 DNN 的语义建模
最近邻语义检索
最近邻检索的工程效率是一个核心问题：
- 把“查询”和“文档”都通过上一节中基于 DNN 的相关性建模进行 Word-Embedding 表达后，检索最相关的 K 个文档的问题，就是在向量空间中计算查询 c 与所有候选文档 a 之间的 K 个最近邻问题。
- 加速最近邻检索算法称为 “ANN 查找 (Approximate Nearest Neighbor)”，有三类典型算法：哈希算法、向量量化算法、基于图的算法；
哈希算法，分为数据无关的轻量级算法、数据有关的算法（学习哈希、语义哈希、深度学习哈希等）。
最常见的是数据无关的“局部敏感哈希算法”（Local Sensitive Hashing, LSH）：
- 针对不同的距离度量方式，LSH 存在着不同的散列函数家族。比如 Jaccard 函数下为 min-hash 函数、余弦距离下为随机投影。
- 随机投影（random projection）：对于向量 $$\vec{x}$$，随机生成一个超平面 p，取哈希函数 $$h(\vec{x}) = \sin{(\vec{x} \cdot p)}$$；
- 随机投影的问题：一是有可能各个桶内的数据分布不均匀，二是不能保证召回率；
- 问题的解决方案：生成多组投影组成桶号，用空间换取召回率（LSH Forest）、用时间换取召回率（multi-probe LSH）；
向量量化（Vector Quantization, VQ）是一种对向量 $$\vec{x}$$ 做整体量化，将其映射到 K 个离散向量中的一个，从而实现压缩数据的算法。它通常由“码本生成阶段建立索引”，“码字搜索阶段查询索引”两个部分构成。
K 均值聚类算法可以看作是一种向量量化：
- 码本生成阶段：通过聚类产生 K 个质心的向量，将数据集中的所有数据映射为一个 K 维的稀疏编码的码向量；
- 码字搜索阶段：寻找与 x 距离最近的一个类别的质心来表达他；
乘积量化（Product Quantization, PQ）是一种常见的 K 均值改进算法，Facebook 的开源工具 faiss 由其高效的实现：