Last updated on 2018-8-6…
本篇为个人笔记，并且在关键部分作了注记。》原文链接
介绍
在具体实现中，由于在线业务对性能尤其是响应时间的严格要求，我们往往会把上述过程拆分为两个阶段：匹配（Match）+排序（Rank）。
- 匹配阶段的核心在于如何从全量商品（Item）中根据用户（User）信息召回合适的TopK候选集合
- 排序阶段则是对TopK候选集合进行精细化打分并排序输出最终展现的结果 可以看出匹配阶段产生的候选集的质量会成为最终效果的天花板，而排序阶段因为候选集小，可以引入诸如深度学习等非常复杂的模型来优化目标，达到最终效果（相关性、广告收益等）的提升。
匹配阶段
当候选集非常大的时候，要从全量候选集中挑选TopK集合，我们无法接受随着全量候选集大小而线性增长的时间复杂度，这使得一些学术界研究的需要计算全量 {User，Item} 兴趣度的方法并不能真正应用于实际推荐系统中的匹配阶段。
作为真实应用的推荐系统，其匹配阶段的计算时间需要被限制，简单用以该公式表示：TxN<=Bound
其中T表示单次计算的时间消耗，N可以认为是为单个用户召回TopK需要的总体计算次数。
在上述公式的约束下，围绕如何提升匹配效果，工业界的技术发展也经历了几代的演进。然而这些方法在技术选型上都在上述计算效率约束下对匹配效果进行了很大的牺牲。
如何在匹配阶段的计算效率约束下引入更先进的复杂深度学习模型成为了下一代匹配技术发展的重要方向。
基于统计的启发式规则方法
这一类方法的经典代表就是Item-based Collaborative Filtering，简称Item-CF，其算法原理是：首先通过统计计算得到Item to Item（I2I）的相似关系，其次启发式地获取用户近期行为作为Trigger Item集合，用它们进行I2I扩展，最后以某种打分规则对扩展后的Item集合进行排序，截断得到TopK作为候选集进行后续排序流程。
- 利：简单有效，应用广泛
- 弊：它限制了尝试推荐给用户未曾行为过但可能感兴趣的Item的可能性 尽管后续的排序环节可以引入复杂的机器学习方法，例如MLR（混合逻辑回归，阿里2011），FM（因子分解）或者深度学习，但它们都依赖于匹配给出的候选结果，所以无论如何复杂的模型都突破不了匹配给定的上限。
*注记*关于MLR：
- 模型：它把回归分为两层，第一层是聚类划分(Embedding)，第二层是内积（Inner Product）
- 学习方法：最速方向导数+拟牛顿加速，该文的亮点在于
“非凸非光滑优化问题的优化方法”。 - 》论文链接
基于内积模型的向量检索方法
基于模型的匹配方法理论上要衡量一个用户对所有商品的兴趣度，从而挑选出最优的推荐结果。这就带来了问题：对于大规模商品候选集的场景是计算不可行的。 研究人员提出了以向量距离的方式衡量用户和商品兴趣度的方法，用户和商品被表示成向量形式，所以内积式模型和向量引擎成为了最近几年匹配领域技术革新的最重要技术（图像检索问题最早就是采用的这种方法，去年Facebook开源了Faiss框架）。 然而问题是，这类方法并未实现充分利用机器学习解决匹配问题的初衷，对机器学习模型的限制太大。 高阶深度学习大部分都不可划成内积形式，比如CTR预估里用户和商品特征交叉非常有用，大部分不可用内积表示。 而在现有深度学习中内积模型的表达能力被证明是有限的，比如将内积模型中最后的内积运算直接换成多层感知机能大幅提升模型能力。 而多层PNN内外积神经网络 ，DIN（深层用户兴趣分布网络，阿里2016）等对用户兴趣更有洞察力的复杂模型效果被证明能极大的超越内积模型。
*注记*关于DIN：
- 关注问题：用户兴趣多样而单个向量表示能力受限。
- 提出：用户兴趣应该是多峰分布而非一个向量点；当用户浏览某个商品时，只有部分（通常一个）兴趣被激发。
- 设计：根据要预估的商品
反向挑选行为子序列去组成用户向量非参数多峰兴趣，从而表示的灵活性大大增加。 - 》论文链接
下一代匹配和推荐技术
结合上文的描述，匹配技术发展的核心点在于系统性能限制下尽可能提升兴趣的衡量精度（从规则算法到引入先进模型）和覆盖范围（从限定候选集到全量候选集）。 为此阿里尝试对下一代匹配和推荐技术进行研究，自主提出了一种更通用的匹配和推荐算法框架，它允许容纳任意先进模型而非限定内积形式，并且能够对全量候选集进行更好的匹配。 无论在公开数据集还是在阿里数据集上，新方法的召回率和新颖性对比前两代技术都有飞跃性的提高。
排序阶段
面对一个复杂问题，人脑常有的一个思考方式是先从大的层面入手，确定大方向后具体细化。 那么是否可以有一种从粗到细的检索方式，逐步判断并细化，最后给出最优推荐。 基于这个思考，阿里把探索方向定位在了使用层次化树结构增加检索效率上。
概率连乘树
在有了使用层次化树结构来增加检索效率的思路后，阿里首先尝试了概率连乘树的形式。 这个形式在Natural Language Processing（自然语言处理）中已经有了一些工作和探讨（例如Hierarchical Softmax，Word2Vec等）。 虽然最后不幸的发现，这个优美的概率形式并不能对匹配问题带来实质的帮助，但它对真正理清匹配问题的要点和难点从而提出真正可用的方法是很有帮助的。
*注记*关于Hierarchical Softmax：
- 模型：每一个叶子节点（词）都有到根节点编码唯一的一条路径，而给定前置上文，下一个词出现的概率被建模为编码路径上分类概率的连乘。
- 优：通过概率连乘树的方式，HS有效避免了在传统Softmax建模中需要遍历所有叶子节点计算分母归一化项的过程。
- 弊：HS方法在建树时往往会考虑将某种具有相似关系（语义、词频等）的节点靠近组成兄弟，而HS方法在计算路径概率时把每一个节点的概率计算看作是二分类问题，用于判断接下来选择哪个孩子节点继续走下去。这种判断优与次优的分类方法对于HS是适用和有效的，但对于匹配和推荐问题却是无法成立的，因为当两个孩子具有某种相似关系时，用户往往是同时喜欢或者同时不喜欢。也就说在单层节点上，匹配和推荐要求的是该层上的全局序判别问题，而HS方法解决的是同一父亲下两个孩子节点谁更优的问题。
最大堆树
推翻概率连乘树方法的思路，我们需要构建一套全新的方法体系来实现树结构的构建、基于树的训练采样和TopK检索、以及节点兴趣度计算的统一。 回到匹配问题本身，假定全量候选集中的每一个商品都是一个叶子节点，当前用户对所有叶子节点背后都存在一个真实的兴趣度。 最大堆树假设用户对第j层父亲节点兴趣的偏好概率正比于用户对第j+1层孩子节点兴趣的偏好概率最大值，这样就不需要在TopK时候遍历所有节点。
*注记*关于Tree-based Deep Match：
- 模型：TDM以淘宝商品体系为初始化依托，自顶向下构造从粗到细的兴趣层次树（Tree），并在此基础上应用深度学习网络进行用户兴趣的推荐建模，赋能单点计算上的复杂模型，运用层次检索方法实现全量候选上的用户TopK商品兴趣推荐。
- 最主要的利：在单独计算每个兴趣节点的偏好时，TDM不局限于特定的模型结构（如内积等），可以引入更加切合数据特性的复杂模型结构来优化预测结果，例如基于用户历史行为的Attention结构，树节点Embedding下沉到输入层，用户和树节点的历史交叉信息引入等等。
- 》论文链接
*注记*关于Advanced Model Server：
- 将参数分布式变成模型分布式，远端（client）为子模型，worker端（server）为主模型
- 检索匹配方面，文中将10亿的商品放在30层的树模型中，仅在当层最优节点继续向下检索
- 》论文链接
