0
雷锋网 AI 科技评论按：推荐系统是现代互联网服务的重要组成部分之一，不管是 YouTube 和亚马逊，还是优酷和淘宝，都通过推荐系统向用户推荐他们可能感兴趣的内容，用户得以看到更多自己关心的内容、在页面上逗留更多时间，服务提供商和网购平台的商户们也由此获得更多的收入。
盖坤博士领导的阿里妈妈精准定向技术团队就在推荐系统方面有诸多研究成果。之前我们就介绍过一篇来自他们的论文，他们设计的深度兴趣网络（Deep Interest Network，DIN）能更好地利用用户历史行为数据，提升广告点击预测的准确率。
最近盖坤团队的一篇新论文《Learning Tree-based Model for Recommender Systems》也介绍了他们在推荐系统算法设计方面的新进展。雷锋网 AI 科技评论把论文内容介绍如下。
对于生产级别的推荐系统来说，语料库的大小其实是算法选择的一大限制。直观地来说，推荐系统需要从各项语料（商品或者视频）中挑出和用户最为匹配的条目作为推荐结果。当语料库较小时，各种方法都可以选用；但当语料库很大时，那些计算复杂度随语料数量线性增加的算法就是难以接受的了。
研究人员们早期提出的协同过滤推荐算法（collaborative filtering）就是一类能以相对小的计算能力处理大规模语料的算法，其中典型的基于物品的协同过滤算法 ItemCF 可以预先计算物品对之间的相似度，然后根据用户的历史行为选出最相似的物品。这种方法简单有效，而且已经可以为不同的用户提供个性化的推荐结果，但它最好情况下也只能推荐与用户看过的商品相似的其它商品，无法真正挖掘用户的兴趣，而且推荐结果也没有新颖性（对用户来说没有惊喜度）。
随着机器学习的兴起，「学出一个推荐系统模型」的想法被证明不仅可行，而且推荐结果也有明显的进步。理论上，学到的模型应当为每一对「用户 - 商品」对计算匹配度，然后把算出的匹配度排序，推荐排在前列的商品。学到的模型固然可以带来优秀的推荐质量，但这样的做法同时也会带来线性增加的计算复杂度，用户和商品数量大到一定程度就无法使用了。所以研究人员们也提出了一些替代方法，比如建立矩阵分解（matrix factorization）模型，把用户 - 商品对分解为用户向量和商品向量，然后把两个向量的内积或者距离作为匹配度。这样形式的推荐问题在有限时间内可以近似求解，比如用哈希或者量化方法近似寻找 k-最近邻，所以也在工业界得到了广泛应用。YouTube 介绍自己的推荐系统的论文《Deep Neural Networks for YouTube Recommendations》中就探索了使用两路多层网络分别产生用户向量和商品向量最后做内积计算的方法。
不过向量内积方法也仍然极大地限制了模型的能力。比如点击通过率（click through rate）预估中需要使用用户历史行为和商品的交叉特征，但大部分特征无法用内积的形式表示。甚至于，即便只是把固定的内积计算步骤换成一个多层前馈神经网络都能改善推荐结果。更强大、更自由的模型仍然大有可为。
在这样的背景下，盖坤团队希望通过新的匹配和推荐技术解开计算复杂度的枷锁，允许在大规模语料库上自由地使用各种模型。在论文中他们提出了新的基于树搜索的深度推荐模型（tree-based deep recommendation model，TDM）。
实际上，树形的层级化信息结构在各种领域都天然地存在，比如 iPhone 这个细分商品品类就可以归在“智能手机”这个粗粒度商品品类下面。文中提出的 TDM 就利用了这种层级化的信息结构，把推荐问题转化为一系列层级化分类问题。利用从粗到细的逐步分类过程，TDM 不仅提高了推荐准确率，而且可以把计算复杂度从关于语料数量线性增加降低到对数增加。
TDM 的关键设计可以分为新型树结构的设计、深度神经网络设计、树结构的学习三部分。
新型树结构降低计算复杂度、降低搜索难度
对于树结构，我们很容易想到熟悉的 hierarchical softmax 树，其中每次分支都是一次二分类。这一面导致从上向下搜索时不能保证一次就找到最优的叶子，仍然需要遍历整个树；另一面，在推荐系统的场景下其实我们希望找到多个相似的叶子，hierarchical softmax 就不是那么适合。
（雷锋网 AI 科技评论注：softmax 模型里每类的概率正比于类别自己的指数项，但具体计算一类的概率时需要用自己的指数项除以一个归一化项，这个归一化项是所有类别的指数项的加和。所以导致了对多类问题中，即使计算其中一个类别的概率，softmax 的计算复杂度也很高。Hierachical softmax 的动机和贡献是用树状连乘概率形式避免掉了归一化项的计算，节省了计算某一类的计算量。但对于寻优检索问题，它的连乘概率形式不保证每层进行贪婪搜索能找到全局最优，所以对大商品库下推荐最好商品这个寻优问题仍需要遍历全部商品进行计算。）
TDM 的关键是使用了一种新的类似最大堆（max-heap like）的树结构，如上图（图中示例是一个完全二叉树，实际中也可以不是）。设用户 u （包含用户身份、历史行为等）对第 j 层的节点 n 代表的商品品类感兴趣的概率为 P(j)(n|u) ，那么每个非叶子节点都满足： P(j)(n|u) 的真实值 = n 节点的所有子节点 ｛nc｝中最大的 P(j+1)(nc|u) 除以正则化项 α(j)；正则化项 α(j) 的作用是让第 j 层所有节点的概率的和为 1。
对于推荐系统而言，对这个树做搜索的目标是找到 k 个偏好概率最大的叶子。那么搜索时可以在每层中找到 k 个概率值最大的节点，然后只有这 k 个节点的子节点会继续向下搜索；最终找到概率值最高的 k 个叶子。根据这样的设计，搜索过程中可以不知道每个节点的概率的确切值，只需知道同一层节点之间的大小顺序就可以完成搜索。据此，作者们也根据用户的隐式反馈数据和神经网络来训练每个节点的辨别器，让它们可以对偏好概率排序。
在训练时，用户实际没有进行互动的节点也就可以随机选择一部分作为训练中的负例。这种随机选择作为负例的做法还有一个好处，相比 hierarchical softmax 树中训练模型分辨最优和次优节点，随机选择的负例会让每个节点的辨别器都成为当前层中的全局辨别器，即便当上一层的辨别器出了问题、选择了一些不好的子节点时，下一层的辨别器也有能力把所有这些子节点中好的那一部分挑出来。
通过这样的树结构设计，寻找节点的过程是从高向低、层层递进的。对于大小为 M 的语料库，最多只需要 2*k*log M 次分支就可以在完全二叉树中找到最终需要的 k 个推荐结果。缩减到对数级别的计算复杂度也意味着可以在其上使用更高级的概率二分类模型。层层递进中每一次只需要做一个简单分类问题的设计也比传统逐个搜索叶子节点的难度大大降低。
另外，树结构作为一种索引也是可以学习的，从而让其中的商品和概念可以被更快地提取到；这同时也有助于模型的训练。作者们也提出了一种树结构的学习方法，可以合并训练神经网络和树结构，见下文。
时间分片输入、带有注意力模块的深度神经网络
受到之前在点击通过率 CTR 模型方面研究的启发，作者们设计的深度神经网络模型（上图）可以从树中学到低维的嵌入，然后结合注意力模块寻找相关的用户行为，以便更好地表征用户。网络的输入也可以接收多个块，每个块中包含用户在不同时间窗口内的行为。借助注意力模块和后部的多层神经网络，这个模型的表现和容量得以大幅提高，同时也不再受到前文提到过的表示为向量和向量内积的限制。
树结构学习
根据前面的设计，学到一个好的树对整个推荐模型发挥出良好表现起着重要作用。直接参照现有数据库的一致性或者相似性构建树结构很可能导致不平衡，这对训练和节点检索都有负面影响。所以作者们也新设计了合理、可行的树构建和学习方法。
首先依据「相似的商品应当具有相近的位置」的思路对树结构进行初始化。初始树的构建利用了商品的类别分类信息，随机排序所有的类别后，以随机顺序把同一类的商品安排在一起；同时属于多个品类的商品会唯一地归为其中某一个类，从而得到一个商品的有序列表。然后反复对有序列表做二分割，直到让每个集中都只含有一个商品，这样就得到了接近完全的二叉树。这样基于品类的初始化方法比完全随机的初始化方法具有更好的层次性。
然后，深度神经网络在训练后可以为树中的每个叶子节点生成一个嵌入，那么这些嵌入向量也就可以用来聚类为一个新的树。K-means 聚类对于大规模语料库就是不错的选择。在实验中，单台服务器只花一个小时时间就可以完成大小为四百万的语料库的聚类成树。
最后，新生成的树还可以用来继续训练神经网络。通过交替生成新的树以及训练神经网络，两者得以合并训练，树结构和网络表现都得以继续优化。
作者们在 MovieLens-20M 数据集上，以及根据部分真实淘宝用户进行了测试。数据规模如下图。
参与对比的基准模型包括 FM 矩阵分解、BPR-MF 隐式反馈推荐矩阵分解、 ItemCF 基于物品的协同过滤算法、YouTube product-DNN。TDM 的变种则包括去掉注意力模块、使用和 YouTube product-DNN 同样的内积方法的 TDM product-DNN，仅去掉激活模块的 TDM DNN，以及使用 hierarchical softmax 树的 TDM attention-DNN-HS。
上图测试结果不仅反映出了所提的 TDM 模型的有效性，几个变体之间的对比也分别体现了注意力模块带来的 10% 的召回率提升和去掉内积限制的巨大作用。使用 hierarchical softmax 树的 TDM attention-DNN-HS 则带来的最差了表现，也表明了它不适合推荐任务。
前面我们也提到了推荐结果需要有一定的新颖性。上图的测试中限定了推荐结果必须来自用户没有行为过的类目下的商品，作为推荐准确率和新颖性的结合度量。TDM 的表现自然一骑绝尘。
针对树学习的单项测试也表明了它带来的可见提升。
作者们也在淘宝 app 的真实访问流量上进行了测试。对比的基准方法是通过逻辑回归挑选出用户有过互动的商品聚类，这是一个表现很好的基准线，而 TDM 模型的点击通过率及广告收入仍然有显著提升。这还仅仅是 TDM 的首个版本实现，后续相信还有不小提升空间。
最后，作者们也关注了模型的运行速度。对于淘宝的广告展示系统，TDM 的神经网络平均只需要 6 毫秒就可以完成一次推荐，不仅不构成整个推荐系统的性能瓶颈，甚至还比后续的点击通过率预测模型运行还快。
这篇论文中作者们首先探究了基于模型的系统应用于大规模语料推荐场景存在的问题，并提出了基于树结构的新的匹配与推荐算法范式，希望借此在推荐系统中应用任意的模型。作者们提出的树学习方法和 TDM 模型也在测试中获得了良好表现，召回率和新颖性都有大幅提高。盖坤博士表示：「虽然初期很令人兴奋，但我们深知这个技术并不完美，还有很多工作要做。并且解决匹配问题也不意味着解决推荐中的所有问题。欢迎更多人来探讨交流。」
论文地址：https://arxiv.org/abs/1801.02294
雷锋网 AI 科技评论编译，感谢盖坤博士的审阅指正。更多人工智能、机器学习前沿技术及应用，请继续关注雷锋网 AI 科技评论。
相关文章：
阿里巴巴WSDM Cup 2018夺得第二名，获奖论文全解读
雷峰网版权文章，未经授权禁止转载。详情见转载须知。
