2018美团技术—算法系列

can发布于2019/02/22

注脚

展开查看详情

1.

2. 序 春节已近,年味渐浓。 又到了我们献上技术年货的时候。 不久前,我们已经给大家分享了技术沙龙大套餐,汇集了过去一年我们线上线下技术沙龙 99位讲师,85 个演讲,70+小时 分享。  今天出场的,同样重磅——技术博客全年大合集。 2018年,是美团技术团队官方博客第5个年头, 博客网站 全年独立访问用户累计超过300万,微信公众  号(meituantech)的关注数也超过了15万。 由衷地感谢大家一直以来对我们的鼓励和陪伴! 在2019年春节到来之际,我们再次精选了114篇技术干货,制作成一本厚达1200多页的电子书呈送给大 家。 这本电子书主要包括前端、后台、系统、算法、测试、运维、工程师成长等7个板块。疑义相与析,大家 在阅读中如果发现Bug、问题,欢迎扫描文末二维码,通过微信公众号与我们交流。 也欢迎大家转给有相同兴趣的同事、朋友,一起切磋,共同成长。 最后祝大家,新春快乐,阖家幸福。

3. 目录 - 算法篇 美团“猜你喜欢”深度学习排序模型实践 ...................................................................... 4 美团大脑:知识图谱的建模方法及其应用 ...................................................................... 16 深度学习在美团搜索广告排序的应用实践 ...................................................................... 37 美团深度学习系统的工程实践 ...................................................................... 47 美团餐饮娱乐知识图谱——美团大脑揭秘 ...................................................................... 56 美团在O2O场景下的广告营销 ...................................................................... 68 美团外卖骑手背后的AI技术 ...................................................................... 85 基于TensorFlow Serving的深度学习在线预估 ...................................................................... 102 强化学习在美团“猜你喜欢”的实践 ...................................................................... 112 深度学习在文本领域的应用 ...................................................................... 125 机器学习在美团配送系统的实践:用技术还原真实世界 ...................................................................... 143 如何基于深度学习实现图像的智能审核? ...................................................................... 154 深度学习在OCR中的应用 ...................................................................... 163 AI技术在智能海报设计中的应用 ...................................................................... 176

4. 美团“猜你喜欢”深度学习排序模型实践 - 美团技术团队 美团“猜你喜欢”深度学习排序模型实践 作者: 绍哲,刘锐 引言 推荐作为解决信息过载和挖掘用户潜在需求的技术手段,在美团点评这样业务丰富的生活服务电子商务平 台,发挥着重要的作用。在美团App里,首页的“猜你喜欢”、运营区、酒店旅游推荐等重要的业务场景, 都是推荐的用武之地。 图1 美团首页“猜你喜欢”场景 目前,深度学习模型凭借其强大的表达能力和灵活的网络结构在诸多领域取得了重大突破,美团平台拥有 海量的用户与商家数据,以及丰富的产品使用场景,也为深度学习的应用提供了必要的条件。本文将主要 介绍深度学习模型在美团平台推荐排序场景下的应用和探索。 深度学习模型的应用与探索 美团推荐场景中每天活跃着千万级别的用户,这些用户与产品交互产生了海量的真实行为数据,每天能够 提供十亿级别的有效训练样本。为处理大规模的训练样本和提高训练效率,我们基于PS-Lite研发了分布 式训练的DNN模型,并基于该框架进行了很多的优化尝试,在排序场景下取得了显著的效果提升。

5. 美团“猜你喜欢”深度学习排序模型实践 - 美团技术团队 图2 模型排序流程图 如上图所示,模型排序流程包括日志收集、训练数据生成、模型训练和线上打分等阶段。当推荐系统对浏 览推荐场景的用户进行推荐时,会记录当时的商品特征、用户状态与上下文信息,并收集本次推荐的用户 行为反馈。在经过标签匹配和特征处理流程后生成最终的训练数据。我们在离线运用PS-Lite框架对 Multi-task DNN模型进行分布式训练,通过离线评测指标选出效果较好的模型并加载到线上,用于线上 排序服务。 下面将着重介绍我们在特征处理和模型结构方面所做的优化与尝试。 特征处理 美团“猜你喜欢”场景接入了包括美食、酒店、旅游、外卖、民宿、交通等多种业务,这些业务各自有着 丰富的内涵和特点,同时各业务的供给、需求与天气、时间、地理位置等条件交织,构成了O2O生活服 务场景下特有的多样性和复杂性,这就给如何更高效地组织排序结果提出了更高的要求。构造更全面的特 征、更准确高效地利用样本一直是我们优化的重点方向。 特征种类 User特征:用户年龄,性别,婚否,有无孩子等 Item特征:价格,折扣,品类和品牌相关特征,短期和长期统计类特征等 Context特征:天气,时间,地理位置,温度等 用户行为:用户点击Item序列,下单Item序列等

6. 美团“猜你喜欢”深度学习排序模型实践 - 美团技术团队 除上述列举的几类特征外,我们还根据O2O领域的知识积累,对部分特征进行交叉,并针对学习效果对 特征进行了进一步处理。具体的样本和特征处理流程如下: 图3 训练数据处理流程 标签匹配 推荐后台日志会记录当前样本对应的User特征、Item特征与Context特征,Label日志会捕获用户对于推 荐项的行为反馈。我们把两份数据按照唯一ID拼接到一起,生成原始的训练日志。 等频归一化 通过对训练数据的分析,我们发现不同维度特征的取值分布、相同维度下特征值的差异都很大。例如距 离、价格等特征的数据服从长尾分布,体现为大部分样本的特征值都比较小,存在少量样本的特征值非常 大。常规的归一化方法(例如 min-max, z-score)都只是对数据的分布进行平移和拉伸,最后特征的 分布仍然是长尾分布,这就导致大部分样本的特征值都集中在非常小的取值范围内,使得样本特征的区分 度减小;与此同时,少量的大值特征可能造成训练时的波动,减缓收敛速度。此外也可以对特征值做对数 转化,但由于不同维度间特征的分布不同,这种特征值处理的方式并不一定适用于其他维度的特征。 在实践中,我们参考了Google的Wide & Deep Model[^6]中对于连续特征的处理方式,根据特征值在累 计分布函数中的位置进行归一化。即将特征进行等频分桶,保证每个桶里的样本量基本相等,假设总共分 了n个桶,而特征xi属于其中的第bi(bi ∈ {0, …, n - 1})个桶,则特征xi最终会归一化成 bi/n。这种方法保 证对于不同分布的特征都可以映射到近似均匀分布,从而保证样本间特征的区分度和数值的稳定性。 低频过滤 过多的极为稀疏的离散特征会在训练过程中造成过拟合问题,同时增加参数的储存数量。为避免该问题, 我们对离散特征进行了低频过滤处理,丢掉小于出现频次阈值的特征。 经过上述特征抽取、标签匹配、特征处理后,我们会给特征分配对应的域,并对离散特征进行Hash处 理,最终生成LIBFFM格式的数据,作为Multi-task DNN的训练样本。下面介绍针对业务目标所做的模型 方面的优化尝试。 模型优化与尝试

7. 美团“猜你喜欢”深度学习排序模型实践 - 美团技术团队 在模型方面,我们借鉴工业界的成功经验,在MLP模型的基础上,针对推荐场景进行模型结构方面的优 化。在深度学习中,很多方法和机制都具有通用性,比如Attention机制在机器翻译,图像标注等方向上 取得了显著的效果提升,但并不是所有具体的模型结构都能够直接迁移,这就需要结合实际业务问题,对 引入的模型网络结构进行了针对性调整,从而提高模型在具体场景中的效果。 Multi-task DNN 推荐场景上的优化目标要综合考虑用户的点击率和下单率。在过去我们使用XGBoost进行单目标训练的 时候,通过把点击的样本和下单的样本都作为正样本,并对下单的样本进行上采样或者加权,来平衡点击 率和下单率。但这种样本的加权方式也会有一些缺点,例如调整下单权重或者采样率的成本较高,每次调 整都需要重新训练,并且对于模型来说较难用同一套参数来表达这两种混合的样本分布。针对上述问题, 我们利用DNN灵活的网络结构引入了Multi-task训练。 根据业务目标,我们把点击率和下单率拆分出来,形成两个独立的训练目标,分别建立各自的Loss Function,作为对模型训练的监督和指导。DNN网络的前几层作为共享层,点击任务和下单任务共享其 表达,并在BP阶段根据两个任务算出的梯度共同进行参数更新。网络在最后一个全连接层进行拆分,单 独学习对应Loss的参数,从而更好地专注于拟合各自Label的分布。 图4 点击与下单多目标学习 Multi-task DNN的网络结构如上图所示。线上预测时,我们将Click-output和Pay-output做一个线性融 合。

8. 美团“猜你喜欢”深度学习排序模型实践 - 美团技术团队 在此结构的基础上,我们结合数据分布特点和业务目标进行了进一步的优化:针对特征缺失普遍存在的情 况我们提出Missing Value Layer,以用更合理的方式拟合线上数据分布;考虑将不同task的物理意义关 联起来,我们提出KL-divergence Bound,以减轻某单一目标的Noise的影响。下面我们就这两块工作做 具体介绍。 Missing Value Layer 通常在训练样本中难以避免地有部分连续特征存在缺失值,更好地处理缺失值会对训练的收敛和最终效果 都有一定帮助。通常处理连续特征缺失值的方式有:取零值,或者取该维特征的平均值。取零值会导致相 应权重无法进行更新,收敛速度减慢。而取平均值也略显武断,毕竟不同的特征缺失所表示的含义可能不 尽相同。一些非神经网络的模型能比较合理的处理缺失值,比如XGBoost会通过Loss的计算过程自适应 地判断特征缺失的样本被划分到左子树还是右子树更优。受此启发,我们希望神经网络也可以通过学习的 方式自适应地处理缺失值,而不是人为设置默认值。因此设计了如下的Layer来自适应的学习缺失值的权 重: 图5 Miss Value Layer 通过上述的Layer,缺失的特征可以根据对应特征的分布去自适应的学习出一个合理的取值。 通过离线调研,对于提升模型的训练效果,自适应学习特征缺失值的方法要远优于取零值、取均值的方 式,模型离线AUC随训练轮数的变化如下图所示:

9. 美团“猜你喜欢”深度学习排序模型实践 - 美团技术团队 图6 自适应学习特征缺失值与取0值和均值效果对比 AUC相对值提升如下表所示: 图7 自适应学习特征缺失值AUC相对值提升 KL-divergence Bound 我们同时考虑到,不同的标签会带有不同的Noise,如果能通过物理意义将有关系的Label关联起来,一 定程度上可以提高模型学习的鲁棒性,减少单独标签的Noise对训练的影响。例如,可以通过MTL同时学 习样本的点击率,下单率和转化率(下单/点击),三者满足p(点击) * p(转化) = p(下单)的意义。因此我们 又加入了一个KL散度的Bound,使得预测出来的p(点击) * p(转化)更接近于 p(下单)。但由于KL散度是非 对称的,即KL(p||q) != KL(q||p),因此真正使用的时候,优化的是 KL(p||q) + KL(q||p)。

10. 美团“猜你喜欢”深度学习排序模型实践 - 美团技术团队 图8 KL­divergence Bound 经过上述工作,Multi-tast DNN模型效果稳定超过XGBoost模型,目前已经在美团首页“猜你喜欢”场景 全量上线,在线上也取得了点击率的提升: 图9 线上CTR效果与基线对比图 线上CTR相对值提升如下表所示:

11. 美团“猜你喜欢”深度学习排序模型实践 - 美团技术团队 图10 线上CTR效果相对值提升 除了线上效果的提升,Multi-task训练方式也很好的提高了DNN模型的扩展性,模型训练时可以同时考虑 多个业务目标,方便我们加入业务约束。 更多探索 在Multi-task DNN模型上线后,为了进一步提升效果,我们利用DNN网络结构的灵活性,又做了多方面 的优化尝试。下面就NFM和用户兴趣向量的探索做具体介绍。 NFM 为了引入Low-order特征组合,我们在Multi-task DNN的基础上进行了加入NFM的尝试。各个域的离散 特征首先通过Embedding层学习得到相应的向量表达,作为NFM的输入,NFM通过Bi-Interaction Pooling的方式对输入向量对应的每一维进行2-order的特征组合,最终输出一个跟输入维度相同的向 量。我们把NFM学出的向量与DNN的隐层拼接在一起,作为样本的表达,进行后续的学习。 图11 NFM + DNN NFM的输出结果为向量形式,很方便和DNN的隐层进行融合。而且从调研的过程中发现,NFM能够加快 训练的收敛速度,从而更有利于Embedding层的学习。因为DNN部分的层数较多,在训练的BP阶段,当 梯度传到最底层的Embedding层时很容易出现梯度消失的问题,但NFM与DNN相比层数较浅,有利于梯 度的传递,从而加快Embedding层的学习。 通过离线调研,加入NFM后,虽然训练的收敛速度加快,但AUC并没有明显提升。分析原因是由于目前 加入NFM模型部分的特征还比较有限,限制了学习的效果。后续会尝试加入更多的特征域,以提供足够 的信息帮助NFM学出有用的表达,深挖NFM的潜力。

12. 美团“猜你喜欢”深度学习排序模型实践 - 美团技术团队 用户兴趣向量 用户兴趣作为重要的特征,通常体现在用户的历史行为中。通过引入用户历史行为序列,我们尝试了多种 方式对用户兴趣进行向量化表达。 1. Item的向量化表达:线上打印的用户行为序列中的Item是以ID的形式存在,所以首先需要对Item进行 Embedding获取其向量化的表达。最初我们尝试通过随机初始化Item Embedding向量,并在训练过 程中更新其参数的方式进行学习。但由于Item ID的稀疏性,上述随机初始化的方式很容易出现过拟 合。后来采用先生成item Embedding向量,用该向量进行初始化,并在训练过程中进行fine tuning 的方式进行训练。 2. 用户兴趣的向量化表达:为生成用户兴趣向量,我们对用户行为序列中的Item向量进行了包括 Average Pooling、 Max Pooling与Weighted Pooling三种方式的融合。其中Weighted Pooling参考 了DIN的实现,首先获取用户的行为序列,通过一层非线性网络(Attention Net)学出每个行为Item对 于当前要预测Item的权重(Align Vector),根据学出的权重,对行为序列进行Weighted Pooling,最 终生成用户的兴趣向量。计算过程如下图所示: 图12 Weighted Pooling 通过离线AUC对比,针对目前的训练数据,Average Pooling的效果为最优的。效果对比如下图所示: 图13 不同Pooling方式点击AUC对比

13. 美团“猜你喜欢”深度学习排序模型实践 - 美团技术团队 以上是我们在模型结构方面的优化经验和尝试,下面我们将介绍针对提高模型训练效率所做的框架性能优 化工作。 训练效率优化 经过对开源框架的广泛调研和选型,我们选择了PS-Lite作为DNN模型的训练框架。PS-Lite是DMLC开 源的Parameter Server实现,主要包含Server和Worker两种角色,其中Server端负责模型参数的存储与 更新,Worker端负责读取训练数据、构建网络结构和进行梯度计算。相较于其他开源框架,其显著优点 在于: PS框架:PS-Lite的设计中可以更好的利用特征的稀疏性,适用于推荐这种有大量离散特征的场景。 封装合理:通信框架和算法解耦,API强大且清晰,集成比较方便。 图14 Parameter Server 在开发过程中,我们也遇到并解决了一些性能优化问题: 1. 为了节约Worker的内存,通常不会将所有的数据储存在内存中,而是分Batch从硬盘中Pre-fetch数 据,但这个过程中存在大量的数据解析过程,一些元数据的重复计算(大量的key排序去重等),累计起 来也是比较可观的消耗。针对这个问题我们修改了数据的读取方式,将计算过的元数据也序列化到硬 盘中,并通过多线程提前将数据Pre-fetch到对应的数据结构里,避免了在此处浪费大量的时间来进 行重复计算。

14. 美团“猜你喜欢”深度学习排序模型实践 - 美团技术团队 2. 在训练过程中Worker的计算效率受到宿主机实时负载和硬件条件的影响,不同的Worker之间的执行 进度可能存在差异(如下图所示,对于实验测试数据,大部分Worker会在700秒完成一轮训练,而最 慢的Worker会耗时900秒)。而通常每当训练完一个Epoch之后,需要进行模型的Checkpoint、评测 指标计算等需要同步的流程,因此最慢的节点会拖慢整个训练的流程。考虑到Worker的执行效率是大 致服从高斯分布的,只有小部分的Worker是效率极低的,因此我们在训练流程中添加了一个中断机 制:当大部分的机器已经执行完当前Epoch的时候,剩余的Worker进行中断,牺牲少量Worker上的 部分训练数据来防止训练流程长时间的阻塞。而中断的Worker在下个Epoch开始时,会从中断时的 Batch开始继续训练,保证慢节点也能利用所有的训练数据。 图15 Worker耗时分布 总结与展望 深度学习模型落地到推荐场景后,对业务指标有了明显的提升,今后我们还将深化对业务场景的理解,做 进一步优化尝试。 在业务方面,我们将尝试对更多的业务规则进行抽象,以学习目标的方式加入到模型中。业务规则一般是 我们短期解决业务问题时提出的,但解决问题的方式一般不够平滑,规则也不会随着场景的变化进行自适 应。通过Multi-task方式,把业务的Bias抽象成学习目标,在训练过程中对模型的学习进行指导,从而可 以比较优雅的通过模型解决业务问题。 在特征方面,我们会继续对特征的挖掘和利用进行深入调研。不同于其他推荐场景,对于O2O业务, Context特征的作用非常显著,时间,地点,天气等因素都会影响用户的决策。今后会继续尝试挖掘多样 的Context特征,并利用特征工程或者模型进行特征的组合,用于优化对样本的表达。 在模型方面,我们将持续进行网络结构的探索,尝试新的模型特性,并针对场景的特点进行契合。学术界 和工业界的成功经验都很有价值,给我们提供了新的思路和方法,但由于面临的业务问题和场景积累的数 据不同,还是需要进行针对场景的适配,以达到业务目标的提升。 参考文献

15. 美团“猜你喜欢”深度学习排序模型实践 - 美团技术团队 [1]: Mu Li, David G. Andersen, Alexander Smola, and Kai Yu. Communication Efficient Distributed Machine Learning with the Parameter Server. NIPS, 2014b. [2]: Rich Caruana. Multitask Learning. Betascript Publishing, 1997. [3]: Xiangnan He and Tat-Seng Chua. Neural Factorization Machines for Sparse Predictive Analytics. Proceedings of the 40th International ACM SIGIR conference on Research and Development in Information Retrieval(2017). [4]: Guorui Zhou, Chengru Song, et al. Deep Interest Network for Click-Through Rate Prediction.arXiv preprint arXiv:1706.06978,2017. [5]: Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural Machine Translation by Jointly Learning to Align and Translate. ICLR ’15, May 2015. [6]: H.-T. Cheng, L. Koc, J. Harmsen, T. Shaked, T. Chandra, H. Aradhye, G. Anderson, G. Corrado, W. Chai, M. Ispir, et al. Wide & deep learning for recommender systems. arXiv preprint arXiv:1606.07792, 2016. 作者简介 绍哲,2015年校招入职原美团, 主要从事推荐排序模型相关的工作。 刘锐,先后在百度、阿里巴巴从事推荐业务相关工作,现就职于美团平台推荐技术中心,专注深度学习模型的研发工 作。 招聘 美团平台推荐技术中心负责美团首页“猜你喜欢”、运营区、酒店旅游推荐等公司重要的业务场景,长期 致力于推荐场景的深度优化,在挖掘用户吃喝玩乐需求的同时提供更好的产品体验。美团平台推荐技术中 心高端算法职位持续招聘中! 期待你的加入,与我们一起解决技术与业务问题,快乐工作,共同成长。 简历请投递至:caohao#meituan.com

16. 美团大脑:知识图谱的建模方法及其应用 - 美团技术团队 美团大脑:知识图谱的建模方法及其应用 作者: 仲远 作为人工智能时代最重要的知识表示方式之一,知识图谱能够打破不同场景下的数据隔离,为搜索、推 荐、问答、解释与决策等应用提供基础支撑。美团大脑围绕吃喝玩乐等多种场景,构建了生活娱乐领域超 大规模的知识图谱,为用户和商家建立起全方位的链接。我们美团希望能够通过对应用场景下的用户偏好 和商家定位进行更为深度的理解,进而为大众提供更好的智能化服务,帮大家吃得更好,生活更好。 近日,美团 AI 平台部 NLP 中心负责人、大众点评搜索智能中心负责人王仲远博士受邀在 AI 科技大本营 做了一期线上分享,为大家讲解了美团大脑的设计思路、构建过程、目前面临的挑战,以及在美团点评中 的具体应用与实践,其内容整理如下: 知识图谱的重要性 近年来,人工智能正在快速地改变人们的生活,可以看到各家科技公司都纷纷推出人工智能产品或者系 统,比如说在 2016 年,谷歌推出的 AlphaGo ,一问世便横扫整个围棋界,完胜了人类冠军。又比如亚 马逊推出的 Amazon Go 无人超市,用户只需下载一个 App,走进这家超市,就可以直接拿走商品,无 需排队结账便可离开,这是人工智能时代的“新零售”体验。又比如微软推出的 Skype Translator,它能 够帮助使用不同语言的人群进行实时的、无障碍的交流。再比如说苹果推出的 Siri 智能助理,它让每一 个用苹果手机的用户都能够非常便捷地完成各项任务。所有这些人工智能产品的出现都依赖于背后各个领 域技术突飞猛进的进展,包括机器学习、计算机视觉、语音识别、自然语言处理等等。

17. 美团大脑:知识图谱的建模方法及其应用 - 美团技术团队 作为全球领先的生活服务电子商务平台,美团点评在人工智能领域也在积极地进行布局。今年 2 月份, AI 平台部 NLP 中心正式成立,我们的愿景是用人工智能帮大家吃得更好,生活更好。语言是人类智慧的 结晶,而自然语言处理是人工智能中最为困难的问题之一,其核心是让机器能像人类一样理解和使用语 言。 我们希望在不久的将来,当用户发表一条评价的时候,能够让机器阅读这条评价,充分理解用户的喜怒哀 乐。当用户进入大众点评的一个商家页面时,面对成千上万条用户评论,我们希望机器能够代替用户快速 地阅读这些评论,总结商家的情况,供用户进行参考。未来,当用户有任何餐饮、娱乐方面的决策需求的 时候,美团点评能够提供人工智能助理服务,帮助用户快速的进行决策。 所有这一切,都依赖于人工智能背后两大技术驱动力:深度学习和知识图谱。我们可以将这两个技术进行 一个简单的比较: 我们将深度学习归纳为隐性的模型,它通常是面向某一个具体任务,比如说下围棋、识别猫、人脸识别、 语音识别等等。通常而言,在很多任务上它能够取得非常优秀的结果,同时它也有非常多的局限性,比如 说它需要海量的训练数据,以及非常强大的计算能力,难以进行任务上的迁移,而且可解释性比较差。

18. 美团大脑:知识图谱的建模方法及其应用 - 美团技术团队 另一方面,知识图谱是人工智能的另外一大技术驱动力,它能够广泛地适用于不同的任务。相比深度学 习,知识图谱中的知识可以沉淀,可解释性非常强,类似于人类的思考。 我们可以通过上面的例子,来观察深度学习技术和人类是如何识别猫的,以及它们的过程有哪些区别。 2012 年,Google X 实验室宣布使用深度学习技术,让机器成功识别了图片中的猫。它们使用了 1000 台 服务器,16000 个处理器,连接成一个 10 亿节点的人工智能大脑。这个系统阅读了 1000 万张从 YouTube 上抽取的图片,最终成功识别出这个图片中有没有猫。 我们再来看看人类是如何做的。对于一个 3 岁的小朋友,我们只需要给他看几张猫的图片,他就能够很 快识别出不同图片中的猫,而这背后其实就是大脑对于这些知识的推理。 2011 年,Science 上有一篇非常出名的论文叫《How to Grow a Mind》。这篇论文的作者来自于 MIT、 CMU、UC Berkeley、Stanford 等美国名校的教授。在这篇论文里,最重要的一个结论就是:如果我们 的思维能够跳出给定的数据,那么必须有 Another Source Of Information 来 Make Up The Difference。 这里的知识语言是什么?对于人类来讲,其实就是我们从小到大接受的学校教育,报纸上、电视上看到的 信息,通过社交媒体,通过与其他人交流,不断积累起来的知识。 近年来,不管是学术界还是工业界都纷纷构建自家的知识图谱,有面向全领域的知识图谱,也有面向垂直 领域的知识图谱。其实早在文艺复兴时期,培根就提出了“知识就是力量”,在当今人工智能时代,各大 科技公司更是纷纷提出:知识图谱就是人工智能的基础。

19. 美团大脑:知识图谱的建模方法及其应用 - 美团技术团队 全球的互联网公司都在积极布局知识图谱。早在 2010 年微软就开始构建知识图谱,包括 Satori 和 Probase。2012 年,Google 正式发布了 Google Knowledge Graph,现在规模已经达到 700 亿左右。 目前微软和 Google 拥有全世界最大的通用知识图谱,Facebook 拥有全世界最大的社交知识图谱,而阿 里巴巴和亚马逊则分别构建了商品知识图谱。 如果按照人类理解问题和回答问题这一过程来进行区分,我们可以将知识图谱分成两类。我们来看这样一 个例子,如果用户看到这样一个问题,“Who was the U.S. President when the Angels won the World Series?”相信所有的用户都能够理解这个问题,也就是当 Angels 队赢了 World Series 的时候,谁是美 国的总统? 这是一个问题理解的过程,它所需要的知识通常我们称之为 Common Sense Knowledge(常识性知 识)。另外一方面,很多网友可能回答不出这个问题,因为它需要另外一个百科全书式的知识。 因此,我们将知识图谱分成两大类,一类叫 Common Sense Knowledge Graph(常识知识图谱),另 外一类叫 Encyclopedia Knowledge Graph(百科全书知识图谱)。这两类知识图谱有很明显的区别。 针对 Common Sense Knowledge Graph,通常而言,我们会挖掘这些词之间的 Linguistic

20. 美团大脑:知识图谱的建模方法及其应用 - 美团技术团队 Knowledge;对于 Encyclopedia Knowledge Graph,我们通常会在乎它的 Entities 和这些 Entities 之 间的 Facts。 对于 Common Sense Knowledge Graph,一般而言我们比较在乎的 Relation 包括 isA Relation、 isPropertyOf Relation。对于 Encyclopedia Knowledge Graph,通常我们会预定义一些谓词,比如说 DayOfbirth、LocatedIn、SpouseOf 等等。 对于 Common Sense Knowledge Graph 通常带有一定的概率,但是 Encyclopedia Knowledge Graph 通常就是“非黑即白”,那么构建这种知识图谱时,我们在乎的就是 Precision(准确率)。 Common Sense Knowledge Graph 比较有代表性的工作包括 WordNet、KnowItAll、NELL 以及 Microsoft Concept Graph。而 Encyclopedia Knowledge Graph 则有 Freepase、Yago、Google Knowledge Graph 以及正在构建中的“美团大脑”。 这里跟大家介绍两个代表性工作:1)Common Sense Knowledge Graph:Probase;2)Encyclopedia Knowledge Graph:美团大脑。 常识性知识图谱(Common Sense Knowledge Graph) Microsoft Concept Graph 于 2016 年 11 月正式发布,但是它早在 2010 年就已经开始进行研究,是一 个非常大的图谱。在这个图谱里面有上百万个 Nodes(节点),这些 Nodes 有Concepts(概念),比 如说 Spanish Artists(西班牙艺术家);有 Entities(实体),比如说 Picasso(毕加索);有 Attributes(属性),比如 Birthday(生日);有 Verbs(动词),有 Adjectives(形容词),比如说 Eat、Sweet。也有很多很多的边,最重要的边,是这种 isA 边,比如说 Picasso,还有 isPropertyOf 边。对于其他的 Relation,我们会统称为 Co-occurance。

21. 美团大脑:知识图谱的建模方法及其应用 - 美团技术团队 这是我们在微软亚洲研究院期间对 Common Sense Knowledge Graph 的 Research Roadmap(研究路 线图)。当我们构建出 Common Sense Knowledge Graph 之后,重要的是在上面构建各种各样的模 型。我们提出了一些模型叫 Conceptualization(概念化模型),它能够支持 Term Similarity、Short Text Similarity 以及 Head-Modifier Detection,最终支持各种应用,比如 NER、文本标注、Ads、 Query Recommendation、Text Understanding 等等。 到底什么是 Short Text Understanding?常识怎么用在 Text Understanding 中?下面我们可以看一些具 体的例子: 当大家看到上面中间的文本时,相信所有人都能够认出这应该是一个日期,但是大家没办法知道这个日期 代表什么含义。但如果我们再多给一些上下文信息,比如 Picasso、Spanish等等,大家对这个日期就会 有一些常识性的推理。我们会猜测这个日期很可能是 Picasso 的出生日期,或者是去世日期,这就是常 识。

22. 美团大脑:知识图谱的建模方法及其应用 - 美团技术团队 比如说当我们给定 China 和 India 这两个 Entity 的时候,我们的大脑就会做出一些常识性的推理,我们 会认为这两个 Entity 在描述 Country。如果再多给一个 Entity:Brazil,这时候我们通常会想到 Emerging Market。如果再加上 Russia,大家可能就会想到“金砖四国”或者“金砖五国”。所有这一切就 是常识性的推理。 再比如,当我们看到 Engineer 和 Apple 的时候,我们会对 Apple 做一些推理,认为它就是一个 IT Company,但是如果再多给一些上下文信息,在这个句子里面由于 eating 的出现,我相信大家的大脑也 会一样地做出常识推理,认为这个 Apple 不再是代表 Company,而是代表 Fruit。

23. 美团大脑:知识图谱的建模方法及其应用 - 美团技术团队 所以,这就是我们提出来的 Conceptualization Model,它是一个 Explicit Representation。我们希望它 能够将 Text,尤其是 Short Text,映射到 Millions Concepts,这样的 Representation 能够比较容易让 用户进行理解,同时能够应用到不同场景当中。 在这一页 PPT 中,我们展示了 Conceptualization 的结果。当输入是 Pear 和 Apple 的时候,那么我们 会将这个 Apple 映射到 Fruit。但是如果是 iPad Apple 的时候,我们会将它映射到 Company,同时大 家注意这并不是唯一的结果,我们实际上是会被映射到一个 Concept Vector。这个 Concept Vector 有 多大?它是百万级维度的 Vector,同时也是一个非常 Sparse 的一个 Vector。

24. 美团大脑:知识图谱的建模方法及其应用 - 美团技术团队 通过这样的一个 Conceptualization Model,我们能够解决什么样的文本理解问题?我们可以看这样一个 例子。比如说给定一个非常短的一个文本 Python,它只是一个 Single Instance,那么我们会希望将它映 射到至少两大类的 Concept 上,一种可能是 Programming Language,另外一种是 Snake。当它有一 些 Context,比如说 Python Tutorial 的时候,那么这个时候 Python 指的应该是 Programming Language,如果当它有其他的 Adjective、Verb,比如有 Dangerous 时,这时候我们就会将 Python 理 解为 Snake。 同时如果在一个文本里面包含了多个的 Entity,比如说 DNN Tool、Python,那么我们希望能够检测出在 这个文本里面哪一个是比较重要的 Entity,哪一个是用来做限制的 Entity。 下面我们将简单地介绍一下,具体应该怎么去做。当我们在 Google 里搜一个 Single Instance 的时候, 通常在右侧会出现这个 Knowledge Panel。对于 Microsoft 这样一个 Instance,我们可以看到这个红色 框所框出来的 Concept,Microsoft 指向的是 Technology Company,这背后是怎么实现的?

25. 美团大脑:知识图谱的建模方法及其应用 - 美团技术团队 我们可以看到,Microsoft 实际上会指向非常非常多的 Concept,比如说 Company,Software Company,Technology Leader 等等。我们将它映射到哪一个 Concept 上最合适? 如果将它映射到 Company 这个 Concept 上,很显然它是对的,但是我们却没办法将 Microsoft 和 KFC、BMW 这样其他类型的产品区分开来。另外一方面,如果我们将 Microsoft 映射到 Largest Desktop OS Vendor 上,那么这是一个非常 Specific 的 Concept,这样也不太好,为什么?因为这个 Concept 太 Specific,太 Detail,它可能只包含了 Microsoft 这样一个 Entity,那么它就失去了 Concept 的这种抽象能力。 所以我们希望将 Microsoft 映射到一个既不是特别 General(抽象),又不是一个特别 Specific(具 体)的 Concept 上。在语言学上,我们将这种映射称之为 Basic-level,我们将整个映射过程命名为 Basic-level Conceptualization。 我们提出了一种计算 Basic-level Conceptualization 的方法,其实它非常简单而且非常有效。就是将两 种的 Typicality 做了一些融合,同时我们也证明了它们跟 PMI 和 Commute Time 之间的一些关联。并 且在一个大规模的数据集上,我们通过 Precision 和 NDCG 对它们进行了评价。最后证明,我们所提出

26. 美团大脑:知识图谱的建模方法及其应用 - 美团技术团队 来的 Scoring 方法,它在 NDCG 和 Precision 上都能达到比较好的结果。最重要的是,它在理论上是能 够对 Basic-Level 进行很好的解释。 下面我们来看一下,当 Instance 有了一些 Context 之后,我们应该怎么去进行处理。我们通过一个例 子,来简单地解释一下这背后最主要的思想。 比如说 iPad、Apple,其中 iPad 基本上是没有歧异的,它会映射到 Device、Product。但是对于 Apple 而言,它可能会映射到至少两类的 Concept 上,比如说 Fruit、Company。那么我们怎么用 iPad 对 Apple 做消歧呢? 方法其实也挺直观的。我们会通过大量的统计去发现像 iPad 这样的 Entity,通常会跟 Company、 Product 共同出现。比如说 iPad 有可能会跟三星共同出现,有可能会跟 Google 共同出现,那么我们就 发现它会经常跟 Brand、Company、Product共同出现。于是我们就利用新挖掘出来的 Knowledge 对 Apple 做消歧,这就是背后最主要的思想。

27. 美团大脑:知识图谱的建模方法及其应用 - 美团技术团队 除了刚才这样一个 General Context 以外,在很多时候这些 Text 可能还会包含很多一些特殊的类型,比 如说 Verb、Adjective。具体而言,我们希望在看到 Watch Harry Potter 时,能够知道 Harry Potter 是 Movie,当我们看到 Read Harry Potter 时,能够知道 Harry Potter 是 Book。同样的,Harry Potter 还 有可能是一个角色名称,或者是一个游戏名称。 那么我们来看一看应该怎样去解决这样一件事情。当我们看到 Watch Harry Potter 时,我们首先要知 道,Harry Potter 有可能是一本 Book,也有可能是一部 Movie。我们可以算出一个先验概率,这通常要 通过大规模的统计。同时我们要知道,Watch 它有可能是一个名词,同时它也有可能是一个动词,并且 我们还需要去挖掘,当 Watch 作为动词的时候,它和 Movie 有非常紧密的关联。 所以我们本质上是要去做一些概率上的推理,不仅要将条件概率做非常细粒度的分解,最后还要做概率计 算。 通过概率计算的方法,我们实际上就可以构建出一个非常大的离线知识图谱,那么我们在这个上面,就可 以有很多的 Term,以及它们所属的一些 Type,以及不同 Term 之间的一些关联。

28. 美团大脑:知识图谱的建模方法及其应用 - 美团技术团队 当我们用这样一个非常大的离线知识图谱来做 Text Understanding 的时候,我们可以首先将这个 Text 进行分割处理,在分割之后,我们实际上是可以从这个非常大的离线知识图谱中截取出它的一个子图。最 后我们使用了 Random Walk With Restart 的模型,来对这样一个在线的 Subgraph 进行分类。 我们再来看一下,如果一个文本里包含了 Multiple Entities,要怎样处理?我们需要做知识挖掘,怎么 做?首先我们可以得到非常多的 Query Log,然后我们也可以去预定一些 Pattern,通过这种 Pattern 的 定义,可以抽取出非常多 Entity 之间 Head 和 Modifier 这样的 Relation,那么在接下来我们可以将这些 Entity 映射到 Concept 上,之后得到一个 Pattern。

29. 美团大脑:知识图谱的建模方法及其应用 - 美团技术团队 在这个过程之中,我们要将 Entity 映射到 Concept 上,那么这就是前面所提到的 Conceptualization。 我们希望之后的映射不能太 General,避免 Concept Pattern 冲突。 但是它也不能太 Specific,因为如果太 Specific,可能就会缺少表达能力。最坏的情况,它有可能就会 退化到 Entity Level,而 Entity 至少都是百万的规模,那么整个 Concept Patterns 就有可能变成百万乘 以百万的级别,显然是不可用的。 所以我们就用到了前面介绍的 Basic-Level Conceptualization 的方法,将它映射到一个既不是特别 General,也不是特别 Specific 的 Concept 上。