文章目录

基于关键词的召回算法与系统

重要技术方向

方向	目标	主要工作	相关指标
查询理解	理解用户查询意图，优化召回与排序结果的相关性	1. Query分析：分词、词权重、纠错、成分分析； 2. Query理解：意图识别、类目识别、地址识别	1. 离线指标：在测试集上的准召率、F1 2. 线上指标：CTR 3. 关注指标：覆盖率、密度、RPS等；
召回模型	在保证相关性的前提下，提升召回结果	1. 查询改写：改写词召回； 2. 相关性校验：改写词排序； 3. 向量召回：双塔、Graph Embedding等； 4. 粗排：Q-P相关性	1. 离线指标：AUC； 2. 线上指标：召回率、覆盖率、密度； 3. 关注指标：CTR、RPS、访购率；
知识图谱	1. 保证准确的前提下，扩充广告node数量； 2. 保证相关性的前提下，提升召回结果	1. 实体词、标签词挖掘； 2. 同义、上下位关系挖掘	1. 离线指标：在测试集上的准召率、F1； 2. 线上指标：召回率、覆盖率、密度； 3. 线上指标：CTR、RPS、访购率；
创意优化	1. 通过优化图像、文本的质量，提升CTR	1. 图片召回：数据源、图片候选模型(pairwise、end2end)； 2. 图片排序：图片特征挖掘； 3. 按搜出图文：类目、标签体系与图文的关系挖掘；

召回算法系统综述
- 召回的数学模型
- 召回算法逻辑思路
查询理解
查询改写
- 改写词全局优化
索引挖掘
- 知识图谱
  - 索引词优化
召回匹配
向量召回
相关性与粗排
- 相关性模型
- 粗排模块
工程建设
- [索引建设]
- [向量索引]
- [case分析链路]

召回算法系统综述

召回的数学模型

召回就是给定用户Query（q），寻找后验概率最大（相关）的Item。

如果假设索引词node能表示广告（node-item相关性），给定query能召回某个node词（query-node相关性），则该过程可以用条件概率公式描述如下：

$$
P(i|q) = \sum_{k} P(n_k | q) \cdot P(i | n_k, q)
$$

如果概率分布已知，就可以进行参数估计。不过实际该过程会进行若干近似，以应对常见的分段式召回流程，即简单认为最大化$P(n_k|q)$相应的$P(i|n_k)$来最大化$P(i|q)$。分段式召回流程表示如下：

$$
\text{Query} \rightarrow
\underbrace{ \boxed{\text{Query Rewrite}}
}_{\color{red}{\text{Matching过程}\; P(n_k | q)}}
\rightarrow \text{Nodes} \rightarrow
\underbrace{
\overbrace{
\boxed{\text{Node-Ads}} }^{\color{red}{\text{Node挖掘}\; P(i|n_k)}}
\rightarrow \text{Ads Candidates} \rightarrow \boxed{粗排}
}_{\color{red}{\text{Recall Service}\; P(i|q)}} \quad \rightarrow \text{召回的Ads}
$$

这里涉及到召回算法两个重要的工作方向：查询改写和索引构建。

查询改写（Query Rewrite）

SMT（统计翻译模型）的原理如下：

$$
\hat{e} = \arg \max_{e} P(e|f) = \arg \max_{e} P(e) P(f|e)
$$

上式的物理意义是求使得$P(e|f)$最大化的$e$。其中，$P(f|e)$是翻译模型，可以用来求解$P(n|q)$。

索引构建

索引构建的主要工作是索引词挖掘（Node挖掘），索引的粒度可以分为Term粒度和Node粒度。

_Term粒度_

比如Query=日式烧烤，Term粒度词：{日式，烧烤}，得到两个词对应索引Item分别是：

$日式 \longrightarrow item1, item2, item3, \cdots, itemN$；
$烧烤 \longrightarrow item1, item3, item5, \cdots, itemN$；

最后得到的召回结果取交集并按照ecpm排序，记为：$item1, item3, \cdots, itemN$ (sorted by bid*score)。

优点：根据索引词即可完成相关性检索，可以利用复杂语法树完成多域查询，容易支持多模式匹配；

缺点：倒排链无法预先按照ecpm排序，因为bid粒度在node而非term；需要merge倒排链之后才能排序，如果改写词太多，会对性能有影响。

_Node粒度_

$日式烧烤 \longrightarrow item1, item3, \cdots, itemN$；(sorted by bid*score)

优点：倒排链可以直接按照ecpm排序，对长链很容易截断；

缺点：支持多模式匹配比较复杂，需要在业务层添加额外逻辑；对改写层要求比较高，需要精确改写到node词；

_索引词方案_

不同的索引粒度，本质上还是召回数量与质量之间的权衡。大多会是两种方式的种种，一般会构建多粒度索引，甚至是字粒度，以适应不同的改写方式。

分段式召回的问题

为了性能考虑，改写词会控制在几十个左右，如K=10。改写词的截断会损失一部分搜索空间，尤其在top query会愈加明显。

$$
P(i|q) = \sum_{k=1}^K P(n_k|q) P(i|n_k, q) + P(n_{K+1}|q) P(i|n_{K+1}, q) + \cdots
$$

索引层计算node-item score部分，条件独立假设item与query无关，仅与索引词node有关，即：

$$P(i|n_k) = P(i|n_k, q)$$

信息损失同样会影响部分准确率，倒排链的阶段会受到node-item score的影响。

以上分析的分段式召回的数学模型，下面分析另一种召回方法：端到端召回。

端到端召回

为了性能考虑，业界常见做法是借助最近邻搜索（如FAISS），需要计算向量的内积。公式表示：

$$
P(i|q) := softmax(\text{Vector}_{q} \cdot \text{Vector}_{i})
$$

业界常用的两种方案：

建模为超大规模多分类问题，如YoutubeNet。但$\text{Vector}_{i}$只是softmax矩阵的一维向量，难以引入更多的item特征；
建模为二分类问题，如利用FM，DSSM或RNN类模型，直接编码query和item侧的特征，即常见的双塔模型。

相比方法1，方法2对于item vector的刻画会更加精细化，重点是对于query和item encoder的设计，衍生出较多的模型，如《深度学习》第6章总结的Graph Embedding系列模型。(TODO 添加引用链接)

召回算法逻辑思路

召回算法逻辑思路可以归纳为：

召回思路	逻辑	特点
分段式召回	类bidword检索 $\rightarrow$ 索引词挖掘&&查询理解与改写 $\rightarrow$ 多种召回策略	长尾Query覆盖较弱
端到端召回	使用更多特征和相关性信息&&基于候选全集&&end2end架构统一优化	长尾Query覆盖较好

广告召回算法的主要目标是理解用户行为意图（实时行为分析或Query分析），从广告候选中召回相关性较高的广告集合，经过粗排截断后，给下游进行精排并最终排序。目前，搜索广告召回采用类bidword检索的传统召回方案，主要工作有两方面：

供给端-索引词挖掘：搜索广告场景，由于广告主通投，由平台主动挖掘bidword作为node索引词，建入倒排索引。涉及的技术主要有实体词、标签词挖掘，基于知识图谱的关系挖掘等；
需求端-查询理解和改写：通过query理解，改写出不同相关性的改写词，然后去倒排索引中检索出相关的广告。涉及的技术主要有Query分析、Query理解，查询改写，生成不同的改写策略等；

基于类bidword的检索方案优点：可解释性好，便于分模块优化。但是也存在一些问题，比如：

召回结果依赖于挖掘和改写两部分工作，它们各自的准确率和召回率，会影响到最终的触发效果；
信息利用不全。为了性能考虑，一般在粗排中只能使用简单的线性公式，难以表达query和ad的特征，并计算它们的相关性。

随着深度学习进展，以端到端的召回算法进一步扩展了传统分段式召回的边界。对比传统方案，端到端召回具备这样一些优势：

信息利用更充分。利用异构图可以把query、ad的更多特征以及它们之间的关系数据融入其中，更好的刻画多种相关性；
统一优化。可以在广告全集上end2end召回，在原先索引词挖掘和查询改写的两个模块上做统一的优化。

向量召回的具体方法可以有很多。原理上，只要能将ad和query表示成向量，并可计算相似度，就可以应用于向量召回，如SVD、FM等基于矩阵分解的模型，Word2Vec等词向量模型，或者以DSSM为代表的双塔结构DNN等，都可以应用到向量召回。但是以下它们存在以下问题：

这类建模方式只能应用在单一的训练数据上，信息表现不全。比如在搜索推荐系统中，相关性往往表现在许多层面，比如Query-Item的点击，多个Item的浏览/点击切换、同Session内的Query切换等等，但是上面这些经典模型面对如此多的数据类型和多种相关性定义则往往力不从心。

图结构可以表征丰富的信息，上面提到的这些相关性都可以通过多种节点和边类型进行异构图的描述。而Graph Embedding的兴起，也为在异构图上挖掘丰富的相关性信息提供了方法论及模型支持。

这个过程中，我们可以在向量建模方式、大规模训练工具、异构图构建、模型结构以及线上算法工程等方面进行探索和实践，并且争取较好的平衡召回率和相关性。

查询理解

参考：《高质量博客总结》广告召回技术梳理

Query分析

分析什么？目标是什么？怎么做？

Query理解

如何定义意图？

各种识别，多分类模型；

查询改写

改写词全局优化

通常，Query线上改写主要依赖于混合simrank++、word2vec、graphSage等多种改写策略的同义词表，改写词之间的优先级需要人工指定（MatchLevel），缺乏统一的排序准则。并且，随着改写策略的不断迭代，一个query对应的改写词也越来越多。

经统计，超过40% 的搜索请求，其改写词数量触发了截断策略。目前截断形式过于简单，直接取Top 20的改写词用于召回广告，在没有全局排序的情况下容易导致优质改写词被丢弃的现象。

为此，我们使用<Query, 索引词>相关性模型(同相关性匹配章节中的树模型)，对线上的改写词进行统一排序，以优化目前改写词截断策略，确保优质改写词优先召回广告。

根据业务特点，比如对应LBS场景，优先本地有召回的改写词（city粒度或商圈粒度）；
构建<Query, 索引词>相关性模型，优先选择高相关性的改写词。

用<Query, 索引词>相关性模型，对线上改写词统一排序，替换掉人工指定的优先级，确保高相关的改写词优先召回广告。

需要展开训练数据生成与模型训练，评估数据与离线auc/acc等指标具体工作。

Query=”画室体验”，通过相关性排序，实验组将低相关改写词（“体验”）排在后面，以确保高相关改写词（“绘画培训”）优先召回广告。

可以在改写词全局排序时，加入相关性控制，仅保留满足相关性要求的改写词，保证CTR。

要求相关性控制模型，不仅支持文本相关性判定，还要具体语义相关的改写词识别能力。

项目：《改写词全局排序优化》。可以放在Query改写策略线上落地后再推动该项目

索引挖掘

知识图谱

各种关系挖掘，建立实体、标签等关系，挖掘知识；

知识图谱应用

生成个性化推荐理由

在推荐结果中添加_个性化推荐理由_，可以增加搜索／推荐结果的解释性，提升用户体验，凸显Item亮点。可以用在创意模块。

推荐理由通常有两种做法：

UGC推荐理由：基于用户评论的抽取式理由；
图谱推荐理由：是一种基于业务图谱数据的路径推理（如增加“快驴智能助理”）；

前端展示的内容都需要“文字模版”，如“亮马桥／三元桥 [职场人士]想打卡的火锅店”，对应文字模版为：{user_worker_region} [${上班族}]想打卡的${modify}店

Query推荐：相似Query挖掘

某些品类场景属于低频业务，针对比较稀疏的Query挖掘一批相似的Query，试图修正因稀疏Query导致特征计算不准确的问题（如统计特征），同时可以起到降低case的目的。

_Query向量产生_：

用用户点击的POI构图，然后从图中采样序列，使用skipgram训练得到POI向量，有了POI向量后，针对每个具体的Query，找到被点击的POI集合，采样avg pooling的方式映射得到Query向量；

_Query聚类和特征挖掘_

相似Quuery聚类，不一定要用kmeans聚类方法，可以考虑使用局部敏感哈希（LSH）等离线计算好，输出每个query对应的topK相似Query的集合；

_输出_：

基于POI点击反馈的Query向量；
基于点击序列学习到的POI向量；

索引词优化

优化1：索引词相关性过滤

背景：

已有的索引挖掘流程中，对于不同索引源产生的索引词缺乏统一的相关性计算和过滤方式，导致部分相关性较差的索引词被保留，而部分强相关的索引词被错误过滤。目前的相关性过滤方法存在以下不足：

根据三级品类过滤时，对于提供跨品类服务的商家，其跨品类服务的相关索引可能被过滤；
基于点击统计进行过滤时，长尾数据过滤不准确，会有badcase引入。

本次实验主要优化索引词的相关性计算及过滤方法，期望达到以下目标：

给Doc下挂的索引词赋予统一且合理的相关性分数，比如对于“ 痘博士潍坊·全国连锁祛痘机构（胜利西街店）”商家，“祛痘”（0.99）具有较高的相关性分数，“美容美体”（0.90）次之，“修护”（0.32）分数较低，“水疗”（0.04）、“美容减肥”（0.02）等不相关的node分数最低；

利用相关性分数进行索引词过滤，替代目前的过滤规则，整体上达到减少不相关索引词，扩充相关索引词的效果。

<POI,索引词>相关性模型：

POI索引词可能包含多种类型，如品类词、品牌词、地址词、修饰词、商品词等。对于某个特定索引词，在判断其与doc的相关性时，对于doc各个特征的关注程度是不同的，比如商品词和修饰词更关注商品信息，品牌词更关注商家名称。

模型选用了类似阿里DIN（Deep Interest Network）的attention结构。DIN的主要思想为，对于推荐给用户的某一个商品，用户是否点击仅仅取决于历史行为数据中的一小部分，并且具有多峰分布的特性，即点击率预估模型更应该关注众多历史行为中的某一个或某几个。在poi-索引词相关性任务中，可以理解为，对于某一个索引词，相关性模型更应该关注poi众多特征中的某些部分。

特征提取：

node特征：node文本；
poi特征：商户名称，poi 1，2，3级品类名和id，团单文本（多个团单拼成一个文本）；

可以给出一个attention分布的示例，即某个索引词在doc各个特征上的attention scorer。

Doc下挂索引词过滤：

使用相关性分数（设定阈值）和历史点击统计进行过滤

离线效果评估：

对每个一级类目下的doc采样K个，评估实验组相对于基线删除的索引词和新增的索引词的相关性。分别对两部分进行相关/不相关/无新增进行打分，最后汇总。

优化2：POI-Node相关性模型

背景：

相关性标准更加严格，以前的标准认为3级类目相关可看作广告相关，新标准要求必须有相应的deal才算作广告相关。鉴于相关性标准的迭代和H2优化相关性的目标，我们对POI-Node相关性模型进行了相应优化。
由于【优化1】POI-Node相关性模型直接用输入了品类名称及id作为特征，对品类特征依赖较重，容易导致以下问题：

保留了与POI三级品类相关但是POI无此服务的品类词node，比如：“按摩足疗”品类的POI没有“拔罐”服务，但是“拔罐”node被保留；
过滤掉POI提供的跨三级品类服务的品类词node，比如：“美术”品类的POI包含“古筝培训”团单，但是“古筝培训”node被过滤。

本次优化希望通过弱化三级品类特征、充分利用团单和泛商品等信息，达到以下目标：

过滤三级品类相关但是POI无团单的node（预期降低不相关node词覆盖率，对ctr有正向影响）；
保留POI提供的次品类/跨品类团单的node（预期提升次品类node曝光）；

解决方案：

模型仍然采用DIN结构。主要是特征方面有较大改动，其中：

去除POI的1，2，3级品类名称和ID，将拼接成的团单文本展开成多个deal或泛商品信息，因此输入是（poi_name, deal1, deal2, …）；
统计node与poi的点击率和熵作为特征，与din层输出特征进行concat作为fc的输入，因此输入是（node, ctr, entropy）;

其中，poi/deal文本embedding首先经过字粒度的word embedding，然后用CNN进行句子粒度的sentence embedding。字粒度的embedding是使用word2vec预训练得到的，使用相同Session下的Query集合作为训练corpus；

召回匹配

TODO 召回匹配不同的分类方法：可以画一个二维表格图：横向为显性隐性方法，纵向为召回方式。

搜索（或广告）一般的召回触发方式有如下几种：

召回方式	做法	主要技术
检索召回	Query分析与变换，改写为检索关键词	查询改写，相关性校验
数据召回	通过数据挖掘或知识图谱得到优质的`<query, bidword>`数据，扩充查询改写	知识图谱、关联挖掘
模型召回	利用NMT模型和闭环数据，采用生成式方法进行关键词生成，关键是关键词对齐，难点是在线的生成式模型实现	NMT模型
向量召回	扩展召回边界，从全局item中直接检索	embedding学习（如双塔模型，类DSSM模型，Graph Embedding等）

end2end架构与向量索引建设（如FAISS) |

线上召回架构：

召回策略优先级通过matchLevel配置；

召回匹配的目标是建立Query（或其改写词）与索引词之间的联系。按照精准度划分，可分为精准匹配和相关性匹配。

精准匹配：可以保证召回的精准度，但是匹配率可能不高，同时对Query改写有了更高的要求（要求改写词精准命中索引词）;
相关性匹配：在Query（或其改写词）与索引词建立相关性模型（可以构造特征训练二分类模型），召回TopK个索引词。这样可以提升匹配率以及缓解Query改写的压力。

以上两种都是为了根据Query得到索引词，都属于索引匹配。

精确匹配

使用query的分词／同义词／纠错词／改写词等集合与索引词集合的求交集，交集即为精确匹配的结果。

端到端召回

端到端召回本质上是将Query和Item用向量表示，通过计算<Query, Item>的相关性，选择相关性最高的TopK个item。所以端到端召回又称为向量召回。

向量召回的特点

全局检索&&end2end学习
信息利用更全：Item特征，丰富的节点关系刻画（用户行为边，内容相似边）；

搜索广告向量召回难点

对召回ad的相关性要求较高，要求左塔的user网络结构能很好的提取关键词特征，保证召回相关性；
较强的LBS地域限制和品类差异，建模时需要考虑；
不能与所有的item计算相似度，这样复杂度太高，可以采用FAISS向量索引解决；

扩召回方式之一，做u2u／i2i相似推荐，或直接i2u推荐；

向量召回技术与落地

参考《深度学习》Chapter6 GraphEmbedding应用

主要步骤如下：

异构图构建；
样本生成（采样）；
图模型建模（encoder，decoder，loss）；
离线评估；
线上架构（向量索引，Query向量计算，相似度检索）；

参考资料见：印象笔记－学习－召回链接

相关性与粗排

模型结构	DSSM	CNN-DSSM	LSTM-DSSM
输入层	1. 英文：letter-trigram 2. 中文：单字	1. 英文：先word-trigram后letter-trigram 2. 中文：单字	同CNN_DSSM
表示层	pooling + fc(tanh)	卷积层＋Max pooling ＋ fc(tanh)	LSTM-引入了peep hole$(f,i,o)$计算时添加细胞态$C_{t-1},C_t$信息
匹配层	cosine + sigmoid + 极大似然估计	同DSSM	同DSSM

粗排模块

粗排作为召回截断的主要排序手段，直接影响到召回的质量以及召回内容的相关性，作为rerank的上游也对rerank整体的排序效果产生影响。因此，粗排的优化要考虑以下因素：

性能：因为召回数量很大，因此不能向做精排模型的思路一样去做粗排模型，特征模型均要求简单有效；
目标：既然是排序，一定要考虑到平台收益和用户体验，可以以$score^{power} \times bid$为主作为排序公式；
业务：结合业务特点，需要对排序公式做一些修正，比如强化距离因素等。

建模思路同精排模型，训练样本同样可以用点击曝光日志。

结合一个case聊粗排排序公式设计：粗排模型上线后，发现覆盖率下降，原因是机制距离门槛限制，此时可以在排序公式中添加_距离因子_，即：

$$
score = distScore^{distPower} \cdot ctr^{ctrPower} \cdot bid
$$

排序超参可以灵活配置（如ctrPower=1.2, distPower=1.1）

工程建设

索引系统

高性能索引系统（支持实时增删功能），相似度搜索，召回服务；

工具积累

可视化工具，如query画像；
case追踪工具；
指标监控工具：实时与天级别；

召回算法

Query $\xrightarrow[Query-索引相关性]{Query分析与改写;改写优化;索引召回;}$ 索引词 $\xrightarrow[索引-Doc相关性]{Retrivel服务}$ Doc

召回工程

Query $\xrightarrow{Matching服务}$ 索引词 $\xrightarrow{Retrivel服务}$ Doc

计算广告与机器学习

Computational Advertising and Machine Learning