热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

阿里TreebasedDeepMatch(TDM)学习笔记及技术发展回顾

本文介绍了阿里TreebasedDeepMatch(TDM)的学习笔记,同时回顾了工业界技术发展的几代演进。从基于统计的启发式规则方法到基于内积模型的向量检索方法,再到引入复杂深度学习模型的下一代匹配技术。文章详细解释了基于统计的启发式规则方法和基于内积模型的向量检索方法的原理和应用,并介绍了TDM的背景和优势。最后,文章提到了向量距离和基于向量聚类的索引结构对于加速匹配效率的作用。本文对于理解TDM的学习过程和了解匹配技术的发展具有重要意义。

阅读文献:https://zhuanlan.zhihu.com/p/35030348

参考文献:https://www.leiphone.com/news/201803/nlG3d4sZnRvgAqg9.html

 

阿里Tree-based Deep Match(TDM)

 

背景


工业界的技术发展也经历了几代的演进,从最初的基于统计的启发式规则方法,逐渐过渡到基于内积模型的向量检索方法。如何在匹配阶段的计算效率约束下引入更先进的复杂深度学习模型成为了下一代匹配技术发展的重要方向。



公式(1)



I)第一代——基于统计的启发式规则方法



经典代表就是Item-based Collaborative Filtering(以下简称Item-CF)。首先通过统计计算得到Item to Item(I2I)的相似关系,其次启发式地获取用户近期行为作为Trigger Item集合,用它们进行I2I扩展,最后以某种打分规则对扩展后的Item集合进行排序,截断得到TopK。



我们可以知道这种方法有效的控制了总体计算次数N,因为用户的Trigger Item集合是有限的,相似关系圈定的候选集合也是有限的。



II)第二代——基于内积模型的向量检索方法



以向量距离的方式衡量用户和商品兴趣度的方法,用户和商品被表示成向量形式,并以此为基础建立基于向量聚类的索引结构进一步加速衡量效率,于是这个计算问题变成了在有限时间内是可解的(近似求解),具体实现也落到了向量引擎的范畴。结合公式(1),T代表简单的向量内积计算时间,而N则通过建立向量索引结构从而控制在O(桶候选集规模)的较小范围内。



所以内积式模型和向量引擎成为了最近几年匹配领域技术革新的最重要技术(图像检索问题最早就是采用的这种方法)。尤其是去年Facebook的Faiss框架开源。



高阶深度学习大部分都不可划成内积形式,比如CTR预估里用户和商品特征交叉非常有用,大部分不可用内积表示。



在具体实践中,向量检索算法要求User和Item能够映射到统一的向量空间。User输入信息和Item输入信息一般并不同质,如何保证映射到统一目标向量空间下的检索精度对映射算法提出了严格的要求,换言之,统一的向量空间映射对运用向量检索来解决推荐问题带来了精度损失的风险。



III)下一代匹配和推荐技术

一种更通用的匹配和推荐算法框架,它允许容纳任意先进模型而非限定内积形式,并且能够对全量候选集进行更好的匹配。



技术方案



概率连乘树并不适用匹配问题:



第二代基于内积模型向量检索的方案,限定模型结构以实现检索效率的提升,因此要想进一步释放模型能力就必须使得整体检索结构的设计与模型结构的设计解耦(向量内积检索与内积模型即是一种强耦合关联)。面对一个复杂问题,人脑常有的一个思考方式是先从大的层面入手,确定大方向后具体细化。我们也从这个角度入手,思考是否可以有一种从粗到细的检索方式,逐步判断并细化,最后给出最优推荐。基于这个思考,我们把探索方向定位在了使用层次化树结构增加检索效率上。



一系列的问题要解决:1、树结构是如何构建的;2,如何基于树进行匹配建模;3、如何围绕树结构实现高效的兴趣计算和检索。



1)HS方法解决了给定上文进行节点概率快速计算的问题,即通过引入Hierarchical Structure避免了对全量候选集的逐一计算和归一化,直接计算得到节点概率。而任何贪心的检索方法如BeamSearch,都无法保证检索得到的TopK是全局最优的,即HS建模方式下每一层的最优连乘并不保证全局最优。



2)与此同时,HS方法在建树时往往会考虑将某种具有相似关系(语义、词频等)的节点靠近组成兄弟。而HS方法在计算路径概率时把每一个节点的概率计算看作是二分类问题,用于判断接下来选择哪个孩子节点继续走下去。在单层节点上,匹配和推荐要求的是该层上的全局序判别问题,而HS方法解决的是同一父亲下两个孩子节点谁更优的问题。



在采用HS方法进行匹配和推荐的实践中,包括YouTube团队在他们的内积模式向量检索做匹配的文章中提到了他们采用HS方法学习用户和候选Video的偏好关系,但是效果并不理想。而我们最先也在阿里妈妈广告测试集上进行了HS方法的尝试,效果也不如预期。



最大堆树的提出和构建:



假定全量候选集中的每一个商品都是一个叶子节点,当前用户对所有叶子节点背后都存在一个真实的兴趣度,用表示。我们并不知道其具体值,只有根据概率采样出来的样本(用户真实反馈)。因此我们创新性的提出了兴趣最大堆树(Max-heap like Tree)的概念,其定义树上节点的概率如下:

公式(2)

即用户对第j层父亲节点兴趣的偏好概率正比于用户对第j+1层孩子节点兴趣的偏好概率最大值。



对于任意一个用户有行为的叶子节点采样i,隐含了叶子层的序:。根据我们的树节点概率定义(最大堆性质),可以向上递归推出每层节点概率的序。根据这个序我们进行负样本采样,用深度学习模型基于这个采样去学习,以逼近最大堆树上每层的序。



全局分类器的设计理念:



在检索过程中,我们只需要每一层的节点概率序确定TopK即可,这里面需要特别说明的是虽然每一层的TopK候选集由上层父亲决定,但该层TopK的排序选取本身并不受父辈的影响,也即每一层的TopK排序都是独立的,父辈的排序分数不参与子辈的排序计算,这一点也是我们的方案区别与概率连乘树在计算形式上的不同。



以上的综合设计使得对全库TopK检索的计算次数限制在log(候选集规模)量级,有效控制了N的大小,而且单次计算并不要求限定于内积等简单形式,从而允许其容纳更先进的模型。



最大堆树背后的方法论:



最大堆树结构定义背后描述的直观意义是用户兴趣的层次结构,如果用户对具体的商品感兴趣,例如iPhone,那么用户对更高层的节点,例如iPhone所在的类别--手机,也是感兴趣的。用户的兴趣结构具有天然的层次性。



综上所述,从最大堆树结构定义出发,我们提出了Tree-based Deep Match(以下简称TDM)算法框架(图1)。TDM以淘宝商品体系为初始化依托,自顶向下构造从粗到细的兴趣层次树(Tree),并在此基础上应用深度学习网络进行用户兴趣的推荐建模,赋能单点计算上的复杂模型,运用层次检索方法实现全量候选上的用户TopK商品兴趣推荐。



 

方案细节



一,模型训练



我们需要在树的每一层建立一个全局分类器,计算该层节点概率的序,得到最优TopK个候选。我们选择负样本采样(Negative Sampling)的方式进行样本生成,以最大似然估计的方式对这些分类器进行训练。



 

相对应的,我们有损失函数为:


 

其中,代表用户u对节点n偏好的真实Label(0或1)。



在实际的样本构建中,我们采用了用户当天的行为叶子节点及其上溯路径上的祖先节点为正样本,而随机采样各个正样本节点的同层兄弟为负样本。在特征上我们使用了(0,8 * 24)小时的行为特征作为用户特征输入。



二,结果预测



层次检索算法:对于最终要求K个叶子目标推荐的情况下,选择当前层概率最高的K个节点,然后往下层扩展他们的孩子节点,对下层孩子节点进行概率估计,选取概率最高的K个,递归计算和选取直至所有路径都到达叶子层,最后从候选叶子集合(可能大于2K个)中取概率最高的K个返回即可。在TDM的实验中,层次TopK的检索被实验证明是有效的,甚至是优于平层暴力(Brute-force)检索的,这一点也侧面验证了兴趣树的层次结构可以有效促进检索的精度提升.


 

三,树联合训练



在实践中我们发现,基于淘宝商品体系为依托构造的树所得的TDM模型,在离线评估指标(召回率等)上会显著的优于随机构造的树所得的TDM模型,这一结果印证了树结构对TDM的巨大影响。我们在这基础上进行了树-模型联合训练的迭代实验,实验结果证明联合训练的模型可以取得比初始模型更优的效果提升(10%+),具体而言我们建立了如下的联合训练迭代方法:


 

图3具体展现了树联合训练在离线测试上的效果。

图3 联合训练树模型和初始树模型的测试结果对比



实验效果



我们在公开数据集MovieLens和阿里妈妈构建的广告数据集UserBehavior上进行了TDM的实验对比,评价指标包括精度、召回率、精度召回率调和F1和新颖性等方面。



一,召回率评估



对比效果中我们可以看出:



1)无论是MovieLens上还是UserBehavior上,带Attention的TDM在召回率上都显著超越了现有推荐匹配算法,包括YouTube向量检索方法和Item-CF统计规则方法;



2)在基础product-DNN版本上引入更复杂和先进的深度模型(节点Embedding进入输入层和引入Attention)可以进一步大幅提升召回率。



二,新颖性评估



可以看到,attention-DNN的TDM方案在全部的指标上都有极大提升,包括相对于广泛使用的Item-CF方案召回率提升292%,相对于业界主流YouTube方案召回率提升34%,而经过树联合训练后Learnt Tree TDM方案效果进一步得到提升,包括相对于广泛使用的Item-CF方案召回率提升355%,相对于业界主流YouTube方案召回率提升56%。



三,树结构对效果的促进


图4 树检索和暴力检索在每一层上的召回率对比



在实验中我们发现树的这种层次化结构可以更加促进效果的提升。从图4我们可以看到在树层数达到一定高度(9+)后TopK层次检索方法(图2)在召回率上会显著优于在该层上的暴力检索方法。究其原因,我们认为TDM的层次化树检索有效防止了上层差的节点对下层节点序计算的影响,将下层候选圈定在上层好的(TopK)节点的孩子中,相对于暴力检索大大降低了序计算的难度,使其具有更好的分类能力,实现召回效果的提升。



PS: 我们也对TDM进行了系统总结并撰写成了论文发表于arXiv上,请大家不吝指正! Learning Tree-based Deep Model for Recommender Systems https://arxiv.org/abs/1801.02294





推荐阅读
  • 推荐系统遇上深度学习(十七)详解推荐系统中的常用评测指标
    原创:石晓文小小挖掘机2018-06-18笔者是一个痴迷于挖掘数据中的价值的学习人,希望在平日的工作学习中,挖掘数据的价值, ... [详细]
  • 《数据结构》学习笔记3——串匹配算法性能评估
    本文主要讨论串匹配算法的性能评估,包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库,可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n),通过随机取出长度为m的子串作为模式P,在文本T中进行匹配,统计平均复杂度。对于成功和失败的匹配分别进行测试,分析其平均复杂度。详情请参考相关学习资源。 ... [详细]
  • 使用圣杯布局模式实现网站首页的内容布局
    本文介绍了使用圣杯布局模式实现网站首页的内容布局的方法,包括HTML部分代码和实例。同时还提供了公司新闻、最新产品、关于我们、联系我们等页面的布局示例。商品展示区包括了车里子和农家生态土鸡蛋等产品的价格信息。 ... [详细]
  • 本文整理了315道Python基础题目及答案,帮助读者检验学习成果。文章介绍了学习Python的途径、Python与其他编程语言的对比、解释型和编译型编程语言的简述、Python解释器的种类和特点、位和字节的关系、以及至少5个PEP8规范。对于想要检验自己学习成果的读者,这些题目将是一个不错的选择。请注意,答案在视频中,本文不提供答案。 ... [详细]
  • 本文介绍了如何在Jquery中通过元素的样式值获取元素,并将其赋值给一个变量。提供了5种解决方案供参考。 ... [详细]
  • 本文介绍了一种求解最小权匹配问题的方法,使用了拆点和KM算法。通过将机器拆成多个点,表示加工的顺序,然后使用KM算法求解最小权匹配,得到最优解。文章给出了具体的代码实现,并提供了一篇题解作为参考。 ... [详细]
  • web.py开发web 第八章 Formalchemy 服务端验证方法
    本文介绍了在web.py开发中使用Formalchemy进行服务端表单数据验证的方法。以User表单为例,详细说明了对各字段的验证要求,包括必填、长度限制、唯一性等。同时介绍了如何自定义验证方法来实现验证唯一性和两个密码是否相等的功能。该文提供了相关代码示例。 ... [详细]
  • 第四章高阶函数(参数传递、高阶函数、lambda表达式)(python进阶)的讲解和应用
    本文主要讲解了第四章高阶函数(参数传递、高阶函数、lambda表达式)的相关知识,包括函数参数传递机制和赋值机制、引用传递的概念和应用、默认参数的定义和使用等内容。同时介绍了高阶函数和lambda表达式的概念,并给出了一些实例代码进行演示。对于想要进一步提升python编程能力的读者来说,本文将是一个不错的学习资料。 ... [详细]
  • SpringBoot整合SpringSecurity+JWT实现单点登录
    SpringBoot整合SpringSecurity+JWT实现单点登录,Go语言社区,Golang程序员人脉社 ... [详细]
  • Explain如何助力SQL语句的优化及其分析方法
    本文介绍了Explain如何助力SQL语句的优化以及分析方法。Explain是一个数据库SQL语句的模拟器,通过对SQL语句的模拟返回一个性能分析表,从而帮助工程师了解程序运行缓慢的原因。文章还介绍了Explain运行方法以及如何分析Explain表格中各个字段的含义。MySQL 5.5开始支持Explain功能,但仅限于select语句,而MySQL 5.7逐渐支持对update、delete和insert语句的模拟和分析。 ... [详细]
  • 实现一个通讯录系统,可添加、删除、修改、查找、显示、清空、排序通讯录信息
    本文介绍了如何实现一个通讯录系统,该系统可以实现添加、删除、修改、查找、显示、清空、排序通讯录信息的功能。通过定义结构体LINK和PEOPLE来存储通讯录信息,使用相关函数来实现各项功能。详细介绍了每个功能的实现方法。 ... [详细]
  • 用Vue实现的Demo商品管理效果图及实现代码
    本文介绍了一个使用Vue实现的Demo商品管理的效果图及实现代码。 ... [详细]
  • 本文介绍了Foundation框架中一些常用的结构体和类,包括表示范围作用的NSRange结构体的创建方式,处理几何图形的数据类型NSPoint和NSSize,以及由点和大小复合而成的矩形数据类型NSRect。同时还介绍了创建这些数据类型的方法,以及字符串类NSString的使用方法。 ... [详细]
  • 本文介绍了在无法联网的情况下,通过下载rpm包离线安装zip和unzip的方法。详细介绍了如何搜索并下载合适的rpm包,以及如何使用rpm命令进行安装。 ... [详细]
  • 程序员如何选择机械键盘轴体?红轴和茶轴对比
    本文介绍了程序员如何选择机械键盘轴体,特别是红轴和茶轴的对比。同时还介绍了U盘安装Linux镜像的步骤,以及在Linux系统中安装软件的命令行操作。此外,还介绍了nodejs和npm的安装方法,以及在VSCode中安装和配置常用插件的方法。最后,还介绍了如何在GitHub上配置SSH密钥和git的基本配置。 ... [详细]
author-avatar
大航
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有