推荐系统中的核心是从海量的商品库挑选合适商品最终展示给用户。由于商品库数量巨大，因此常见的推荐系统一般分为两个阶段，即召回阶段和排序阶段。召回阶段主要是从全量的商品库中得到用户可能感兴趣的一小部分候选集，排序阶段则是将召回阶段得到的候选集进行精准排序，推荐给用户。
本篇我们来总结一下推荐系统中几种常用的召回策略。主要有协同过滤、向量化召回和阿里最近在Aicon中提到的深度树匹配模型。
1、协同过滤
协同过滤主要可以分为基于用户的协同过滤、 基于物品的协同过滤。当然还有基于模型的协同过滤，如矩阵分解等，本文不对这部分进行介绍。
1.1 基于用户的协同过滤
基于用户的协同过滤算法的基本思想是：当召回用户A的候选集时，可以先找到和他有相似兴趣的其他用户，然后把那些用户喜欢的、而用户A没有未交互的物品作为候选集。
因此，我们首先需要计算两个用户的兴趣相似度。给定用户u和用户v，令N(u)表示用户u曾经有过正反馈的物品集合，令N(v) 为用户v曾经有过正反馈的物品集合。那么我们可以通过以下两种方法计算用户的相似度：
余弦相似度为什么是上面这种写法呢，因为这里，我们并不是用的用户对物品的评分，而是用的0-1表示，所以对两个集合做交集，相当于进行了点乘。如果我们的矩阵是用户对物品的评分，那么计算余弦相似度的时候可以利用用户的具体评分而不是0-1值。
如果简单的基于余弦相似度，显得过于粗糙，以图书为例，如果两个用户都曾经买过《新华字典》，这丝毫不能说明他们兴趣相似， 因为绝大多数中国人小时候都买过《新华字典》。但如果两个用户都买过《数据挖掘导论》，那可 以认为他们的兴趣比较相似，因为只有研究数据挖掘的人才会买这本书。换句话说，两个用户对冷门物品采取过同样的行为更能说明他们兴趣的相似度，因此，我们可以基于物品的流行度对热门物品进行一定的惩罚：
得到用户之间的兴趣相似度后，UserCF算法会给用户推荐和他兴趣最相似的K个用户喜欢的 物品。如下的公式度量了UserCF算法中用户u对物品i的感兴趣程度:
其中，S(u, K)包含和用户u兴趣最接近的K个用户，N(i)是对物品i有过行为的用户集合，wuv是用户u和用户v的兴趣相似度，rvi代表用户v对物品i的兴趣.
1.2 基于物品的协同过滤
UserCF在一些网站(如Digg)中得到了应用，但该算法有一些缺点。首先， 随着网站的用户数目越来越大，计算用户兴趣相似度矩阵将越来越困难，其运算时间复杂度和空间复杂度的增长和用户数的增长近似于平方关系。其次，基于用户的协同过滤很难对推荐结果作出解释。因此，著名的电子商务公司亚马逊提出了另一个算法——基于物品的协同过滤算法。
基于物品的协同过滤算法(简称ItemCF)给用户推荐那些和他们之前喜欢的物品相似的物品。 比如，该算法会因为你购买过《数据挖掘导论》而给你推荐《机器学习》。不过，ItemCF算法并不利用物品的内容属性计算物品之间的相似度，它主要通过分析用户的行为记录计算物品之间的相似度。该算法认为，物品A和物品B具有很大的相似度是因为喜欢物品A的用户大都也喜欢物品 B。
基于物品的协同过滤算法主要分为两步。
(1) 计算物品之间的相似度。
(2) 根据物品的相似度和用户的历史行为给用户生成召回候选集。
ItemCF的第一步是计算物品之间的相似度，在网站中，我们经常看到这么一句话：Customers Who Bought This Item Also Bought，那么从这句话的定义出发，我们可以用下面的公式定义物品相似度：
这里，分母|N(i)|是喜欢物品i的用户数，而分子 N(i)N(j) 是同时喜欢物品i和物品j的用户数。因此，上述公式可以理解为喜欢物品i的用户中有多少比例的用户也喜欢物品j。但是却存在一个问题。如果物品j很热门，很多人都喜欢，那么Wij就会很大，接近1。因此，该公式会造成任何物品都会和热门的物品有很大的相似度，这 对于致力于挖掘长尾信息的推荐系统来说显然不是一个好的特性。为了避免推荐出热门的物品，可以用下面的公式:
这里由于还是0-1的原因，我们的余弦相似度可以写成上面的形式。但是，是不是每个用户的贡献都相同呢? 假设有这么一个用户，他是开书店的，并且买了当当网上80%的书准备用来自己卖。那么， 他的购物车里包含当当网80%的书。假设当当网有100万本书，也就是说他买了80万本。从前面 对ItemCF的讨论可以看到，这意味着因为存在这么一个用户，有80万本书两两之间就产生了相似度。这个用户虽然活跃，但是买这些书并非都是出于自身的兴趣，而且这些书覆 盖了当当网图书的很多领域，所以这个用户对于他所购买书的两两相似度的贡献应该远远小于一个只买了十几本自己喜欢的书的文学青年。因此，我们要对这样的用户进行一定的惩罚，John S. Breese在论文1中提出了一个称为IUF(Inverse User Frequence)，即用户活跃度对数的 倒数的参数，他也认为活跃用户对物品相似度的贡献应该小于不活跃的用户，他提出应该增加IUF参数来修正物品相似度的计算公式:
在得到物品之间的相似度后，ItemCF通过如下公式计算用户u对一个物品j的兴趣:
这里N(u)是用户喜欢的物品的集合，S(j,K)是和物品j最相似的K个物品的集合，wji是物品j和i 的相似度，rui是用户u对物品i的兴趣。
1.3 UserCF和ItemCF的比较
先说结论：新闻网站一般使用UserCF，而图书、电商网站一般使用ItemCF！
首先回顾一下UserCF算法和ItemCF算法的推荐原理。UserCF给用户推荐那些和他有共同兴 趣爱好的用户喜欢的物品，而ItemCF给用户推荐那些和他之前喜欢的物品类似的物品。从这个算 法的原理可以看到，UserCF的推荐结果着重于反映和用户兴趣相似的小群体的热点，而ItemCF 的推荐结果着重于维系用户的历史兴趣。换句话说，UserCF的推荐更社会化，反映了用户所在的小型兴趣群体中物品的热门程度，而ItemCF的推荐更加个性化，反映了用户自己的兴趣传承。
在新闻网站中，用户的兴趣不是特别细化，绝大多数用户都喜欢看热门的新闻。个性化新闻推荐更加强调抓住 新闻热点，热门程度和时效性是个性化新闻推荐的重点，而个性化相对于这两点略显次要。因 此，UserCF可以给用户推荐和他有相似爱好的一群其他用户今天都在看的新闻，这样在抓住热 点和时效性的同时，保证了一定程度的个性化。同时，在新闻网站中，物品的更新速度远远快于新用户的加入速度，而且 对于新用户，完全可以给他推荐最热门的新闻，因此UserCF显然是利大于弊。
但是，在图书、电子商务和电影网站，比如亚马逊、豆瓣、Netflix中，ItemCF则能极大地发 挥优势。首先，在这些网站中，用户的兴趣是比较固定和持久的。一个技术人员可能都是在购买 技术方面的书，而且他们对书的热门程度并不是那么敏感，事实上越是资深的技术人员，他们看 的书就越可能不热门。此外，这些系统中的用户大都不太需要流行度来辅助他们判断一个物品的 好坏，而是可以通过自己熟悉领域的知识自己判断物品的质量。因此，这些网站中个性化推荐的 任务是帮助用户发现和他研究领域相关的物品。因此，ItemCF算法成为了这些网站的首选算法。 此外，这些网站的物品更新速度不会特别快，一天一次更新物品相似度矩阵对它们来说不会造成 太大的损失，是可以接受的。同时，从技术上考虑，UserCF需要维护一个用户相似度的矩阵，而ItemCF需要维护一个物品 相似度矩阵。从存储的角度说，如果用户很多，那么维护用户兴趣相似度矩阵需要很大的空间， 同理，如果物品很多，那么维护物品相似度矩阵代价较大。
下表是对二者的一个全面的比较：
1.4 协同过滤总结
协同过滤方法通过在用户历史行为里面找相似的商品和用户，保证了基础的相关性。与此同时，因为只找相似的商品或相似用户的商品，所以系统屏蔽了大规模的计算，使整个召回的过程能够高效地完成。
但是协同过滤方法存在一定的弊端：在召回的时候，并不能真正的面向全量商品库来做检索，如itemCF方法，系统只能在用户历史行为过的商品里面找到侯选的相似商品来做召回，使得整个推荐结果的多样性和发现性比较差。这样做的结果就是，用户经常抱怨：为什么总给我推荐相同的东西！
2、向量化召回
向量化召回，主要通过模型来学习用户和物品的兴趣向量，并通过内积来计算用户和物品之间的相似性，从而得到最终的候选集。其中，比较经典的模型便是Youtube召回模型。在实际线上应用时，由于物品空间巨大，计算用户兴趣向量和所有物品兴趣向量的内积，耗时十分巨大，有时候会通过局部敏感Hash等方法来进行近似求解。
2.1 Youtube召回模型
Youtube召回模型的架构如下：
从模型结构可以看出，在离线训练阶段，将其视为一个分类问题。我们使用隐式反馈来进行学习，用户完整观看过一个视频，便视作一个正例。如果将视频库中的每一个视频当作一个类别，那么在时刻t，对于用户U和上下文C，用户会观看视频i的概率为：
其中，u是用户的embedding，这个embedding，是网络最后一个Relu激活函数的输出，vi是视频i的embedding。那么问题来了，输入时，每一个视频也有一个对应的embedding，这个embedding是不是计算softmax的embedding呢？个人认为是两组不同的embedding，输入层的embedding分别是用户空间和视频空间的向量，最终的输出层，二者通过一系列全联接层的线性变化，转换到了同一空间，所以对于用户和视频来说，输出层的embedding是同一空间，可以认为是兴趣空间，这样二者的内积可以代表相似性。
使用多分类问题的一个弊端是，我们有百万级别的classes，模型是非常难以训练的，因此在实际中，Youtube并使用负样本采样(negative sampling)的方法，将class的数量减小。
对于在线服务来说，有严格的性能要求，必须在几十毫秒内返回结果。因此，youtube没有重新跑一遍模型，而是通过保存用户兴趣embedding和视频兴趣embedding，通过最近邻搜索的方法得到top N的结果。该近似方法中的代表是局部敏感Hash方法。我们在下一节中进行介绍。
2.2 局部敏感哈希(Locality-Sensitive Hashing, LSH)
这里我们简单介绍一下局部敏感哈希(Locality-Sensitive Hashing, LSH)的基本思想，更加详细的介绍可以参考参考文献3。
LSH的基本思想如下：我们首先对原始数据空间中的向量进行hash映射，得到一个hash table，我们希望，原始数据空间中的两个相邻向量通过相同的hash变换后，被映射到同一个桶的概率很大，而不相邻的向量被映射到同一个桶的概率很小。因此，在召回阶段，我们便可以将所有的物品兴趣向量映射到不同的桶内，然后将用户兴趣向量映射到桶内，此时，只需要将用户向量跟该桶内的物品向量求内积即可。这样计算量被大大减小。
关键的问题是，如何确定hash-function？在LSH中，合适的hash-function需要满足下面两个条件：
1）如果d(x,y) ≤ d1， 则h(x) = h(y)的概率至少为p1；
2）如果d(x,y) ≥ d2， 则h(x) = h(y)的概率至多为p2；
其中d(x,y)表示x和y之间的距离， h(x)和h(y)分别表示对x和y进行hash变换。
满足以上两个条件的hash function称为(d1,d2,p1,p2)-sensitive。而通过一个或多个(d1,d2,p1,p2)-sensitive的hash function对原始数据集合进行hashing生成一个或多个hash table的过程称为Locality-sensitive Hashing。
2.3 向量化召回评价
向量化召回是目前推荐召回核心发展的一代技术，但是它对模型结构做了很大的限制，必须要求模型围绕着用户和向量的embedding展开，同时在顶层进行内积运算得到相似性。在深度学习领域其实模型结构层出不穷，百花齐放，但是这样一个特定的结构实际上对模型能力造成了很大的限制。
3、深度树匹配
上面两种方法，揭示了召回中两个比较关键的问题：全库搜索、先进模型。如果说向量化召回通过内积运算的方式打开了全库搜索的天花板，那么下一阶段应该是：能否设计一套全新的推荐算法框架，它允许容纳任意先进的模型而非限定内积形式，并且能够对全库进行更好的检索。深度树匹配，就是从这个视角出发做的技术探索。这里我们简单介绍一下深度树匹配（Tree-based Deep Match，TDM）技术，ppt和详细介绍参照文献5和6。
深度树匹配的核心是构造一棵兴趣树，其叶子结点是全量的物品，每一层代表一种细分的兴趣：
接下来，我们主要介绍三个方面的内容：
1）怎么基于树来实现高效的检索
2）怎么在树上面做兴趣建模
3）兴趣树是怎么构建的
3.1 怎么基于树来实现高效的检索
在这里，假设已经得到深度树的情况下，高效检索采用的是Beam-Search的方式：
3.2 怎么在树上面做兴趣建模
在已经得到深度树的情况下，一个新来的用户，我们怎么知道他对哪个分支的兴趣更大呢？我们首先需要将树建立为一棵最大堆树。
在实践中，构造最大堆树可以举个简单的例子，假设用户对叶子层 ITEM6 这样一个节点是感兴趣的，那么可以认为它的兴趣是 1，同层其他的节点兴趣为 0，从而也就可以认为 ITEM6 的这个节点上述的路径的父节点兴趣都为 1，那么这一层就是 SN3 的兴趣为 1，其他的为 0，这层就是 LN2 的兴趣为 1，其他为 0。如下图所示：
当建立起如上的树之后，我们就可以在每一层构建一定的正负样本，通过构建模型来学习用户对于每一层节点的兴趣偏好。注意的是，每层的偏好都要学习，也就是说每层都要构建一个模型。同时，模型只需要关心是否足够拟合样本就可以了，并没有要求模型一定要把用户特征和 item 特征转换为顶层向量内积的形式，这样就给了模型很大的自由度，只要去拟合好足够的样本，那么任意的模型都是 OK 的。下面是一个模型的示例：
3.3 兴趣树是怎么构建的
前面两个问题，都是在给定树结构的情况下来介绍的，那么怎么来构建一棵兴趣树呢？每层是怎么分叉的呢？
树的叶节点对应具体的 item，目标是构建一个好的树结构来优化我们的检索效果。通过前面的分析知道，在进行兴趣建模时，对于叶子层的样本我们通过用户行为反馈得到，而中间层的样本则通过树结构采样得到。所以树结构决定了中间层的样本。
在进行快速检索时，采用从顶向下的检索策略，利用的是对每一层节点兴趣建模进行快速剪枝。要保证最终的检索效果，就需要每一层的兴趣判别模型能力足够强。由于树结构负责我们中间层的样本生成，所以我们的思路是通过优化树结构影响样本生成进而提升模型能力。具体来说，通过树结构优化降低中间层的样本混淆度，让中间层样本尽可能可分。
所以，整个树结构的生成创建和优化的过程，实际上是围绕着怎么来生成更好的样本、帮助模型学习的视角进行的，而不是只是考虑相似、聚类这样的模式。那么这里的核心方案是什么呢？
方案总结来说，就是最小化用户行为序列中相近的item-pair在树上的距离。假设用户的行为序列为A-》B-》D-》C，那么我们希望(A,B),(B,D),(D,C)在树上的距离越近越好。两个叶子结点的距离通过其最近的公共祖先确定。
好了，到这里，对深度树匹配模型做一个简单的总结：
4、总结
本文介绍了推荐系统在召回阶段常用的模型，有协同过滤模型、向量化召回模型和深度树匹配算法。
协同过滤模型无法做到全局检索，而向量化模型对模型的结构进行了限制。深度树匹配模型解决了上述两个方面的限制，可以做到全局检索+使用先进模型。
参考文献
1、推荐系统理论(二) -- 利用用户行为数据进行推荐(协同过滤)：https://www.jianshu.com/p/8d90824d52c5
2、项亮：《推荐系统实践》
3、局部敏感hash：https://www.cnblogs.com/wt869054461/p/8148940.html
4、推荐系统遇上深度学习(三十四)--YouTube深度学习推荐系统：https://www.jianshu.com/p/8fa4dcbd5588
5、深度树匹配slide：https://myslide.cn/slides/10614
6、深度树匹配详解：http://www.6aiq.com/article/1554659383706
