专栏 | 阿里KDD2017论文:基于大规模图计算的本地算法对展示广告的行为预测

机器之心专栏

作者:杨红霞(阿里集团)、Yada Zhu (IBM Watson)、Jingrui He (亚利桑那州立大学)

在 2017 国际知识发现与数据挖掘大会(KDD)全球论文投稿中,阿里集团和蚂蚁金服共有 5 篇论文被大会收录,本次被收录论文涵盖深度学习、大规模图计算、商品智能排序等多个研究领域,基于真实的业务场景或数据样本,文中部分方法结论已经在业务中运用。如深度学习语义建模研究中提出了一种新的文本语义编码算法 conv-RNN,该模型在参考了较为常用的文本语义编码模型循环神经网络与卷积神经网络的同时,进行了进一步的文本语义编码优化,实现更为精准的文本分类和问答匹配并已应用于阿里智能音响「天猫精灵」。

KDD 的英文全称是 Knowledge Discovery and Data Mining,即知识发现与数据挖掘,由美国计算机协会 ACM 下的数据挖掘分会举办,是国际数据挖掘领域的顶级会议。KDD 2017 共吸引全世界 1144 篇论文投递,收录 216 篇,包括清华、中科院、阿里在内的中国大陆学术界和工业界共被收录 25 篇。

本文介绍了阿里被 KDD 2017 接收的论文《Local Algorithm for User Action Prediction Towards Display》。

论文地址:https://drive.google.com/file/d/0B_QtfVz5m-4_MkZpd1VIRUZSWm8/view

我们解决的问题

用户行为建模在计算广告中是至关重要的,它通过跟踪用户的在线行为建立用户的产品,然后根据用户的兴趣和需求提供相关的广告。准确的模型将导致更高的定位精度,从而提高广告效果。直观上,类似的用户往往对展示的广告具有类似的行为(例如,展示,点击,转换)。

然而,据我们所知,以前的工作没有太多明确地调查各种类型的用户行为的相似之处,并且将它们纳入广告响应目标和预测中,主要是由于问题规模过大。为弥合这一差距,本文中,我们使用二分图来表示历史用户行为,其中包括用户节点和广告客户活动节点,以及过去反映各种类型的用户- 广告营销活动交互的边。

基于这种表示,我们研究了用户行为建模和动作预测的随机步行本地算法,其计算复杂度仅取决于输出群集的大小,而不是整个图形。我们的目标是通过利用历史用户-用户 (user-user),广告系列活动 (campaign- campaign) 和用户-活动 (user-campaign) 交互来改善行为预测。

特别地,我们提出了伴随 ADNI 算法的二分图 AdvUserGraph。ADNI 将 NIBBLE 算法扩展到 AdvUserGraph,并且能够将由感兴趣的用户组成的本地群集发现到特定的广告客户活动。我们还提出了 ADNI 的两个扩展,提高了效率。所提出的算法的性能表现在合成数据和世界领先的需求侧平台(Demand Side Platform),表明它们在预测极少数事件的有效性。

大规模图计算本地算法的意义

今天,存在无数的应用程序,需要对某些类型的大型图表进行分析,例如社交网络,蛋白质相互作用网络,共同作者网络等,甚至全球网络估计至少包含 47.4 亿页。因此,即使是中等大网络的分析也是数万个顶点的数量级,构成重大挑战。处理这些问题的一种方法是将这些网络划分成更小,更易管理的部件,并行处理。然而,在这些网络之一中建立最优聚类顶点的 NP 完整问题已经在十多年了。

分割大图确实是一个计算上的重要问题:存在很少的方法可以在接近甚至 O(n2) 或 O(m) 的时间内对 n 个顶点和 m 个边缘进行分割。近年来的一个突破是图形分割的局部方法的出现,实现了边缘数量接近线性的时间复杂性。这些方法中的第一种是通过称为 NIBBLE[1] 的局部聚类算法来实现的。NIBBLE 可以最大限度地减少无向未加权图的聚类质量公制切割电导。给定一个起始顶点,它可以证明在时间上靠近该顶点的簇 (O(2blog6m)/ϕ4),其与输出簇的大小成比例。寻找一个与其大小成正比的时间段是本身非常有价值的例程,作者展示了如何使用 NIBBLE 作为一个子例程,从大图中重复删除小簇,以获得近似线性的时间图分区算法。后来使用 PageRank 向量扩展了 NIBBLE,并且表明,通过单个 PageRank 向量的扫描可以得到具有 cut conductance 为ϕ的切割。

凸面优化已经成为不同领域的图形建模越来越流行的方式。然而,随着数据集越来越复杂,经典的凸优化通常由于缺乏可扩展性而失败。最近 [2] 提出了 Network Lasso,并开发了一个快速,可扩展和分布式的解算器,并在图形相关问题中看到几个成功的应用。NIBBLE 和 PageRank NIBBLE 都是本地算法,它可以找出包含或靠近给定顶点的解决方案,而无需查看整个图形。本地算法的运行时间,当查询非空本地簇时,输出簇的大小几乎是线性的。

模型的构成

我们首先把问题抽象成二分图: user nodes & adv/campaign nodes,

这二者边的建立,可以是 impression, click and/or conversion,一般情况下 impression 的数量远远大于 click,远远大于 conversion,但是这三者带来的价值却正好是相反的,及 value(impression)<value(click)<value(conversion)。基于这个问题,我们借鉴 tf-idf 的思想,我们假设节点之间的边是一个 document,三种不同种类的节点是三个独特的 term。假定 f(eij,di) 是 term eij 在 documentdi 出现的频次,我们使用以下 log 变换去定义 term 的频率 (tf):

Inverse document frequency (idf) 定义如下:

最终 tf-idf 的定义如下:

基于这个图定义,我们提出了 NIBBLE 算法的变形和两个延展,并证明了计算时间最多 O((k/γ−k+1)logm/ϵ)。

实验结果

在 AUC,CVR 和 ROI 的结果上,我们都大幅度的超过了之前的 state-of-arts,并为全球第二大的竞价平台带来了数以百万计的美金收益。

参考文献

[1] D. Spielman and S. Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal of Computation, 42:1–26, 2013.

[2] D. Hallac, J. Leskovec, and S. Boyd. Network lasso: Clustering and optimiza- tion in large graphs. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'15, pages 387–396, 2015.

本文为机器之心专栏,转载请联系本公众号获得授权。

原文发布于微信公众号 - 机器之心(almosthuman2014)

原文发表时间:2017-08-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI2ML人工智能to机器学习

Amazon Sage​Maker启示录

在“机器学习模型常见对比”我们聊了机器学习常见模型, 在“R语言和表数据分析”里面我们解读了数据处理一般流程。

16040
来自专栏AI研习社

学 AI 和机器学习的人必须关注的 6 个领域

近期热门的话题, 人们开始重新讨论这一基本定义----什么是人工智能(AI)。有些人将 AI 重新命名为「认知计算」或「机器智能」,而其他人则错误地将 AI ...

16320
来自专栏机器人网

一图了解人工智能之机器学习学习路径

1. 引言 也许你和这个叫『机器学习』的家伙一点也不熟,但是你举起iphone手机拍照的时候,早已习惯它帮你框出人脸;也自然而然点开今日头条推给你的新闻;也习惯...

472130
来自专栏大数据文摘

专访乔治亚理工宋乐教授:用强化学习为图论组合优化问题寻找“元算法”

50920
来自专栏新智元

【ICCV 13大不可错过的有趣项目】实时任意风格迁移、手机照片背景模糊……

来源:techcrunch 作者:Devin Coldewey 编译:马文 【新智元导读】计算机视觉领域顶会之一的 ICCV 结束不久,图像质量提升、从头创建...

41570
来自专栏IT派

量子机器学习入门科普:解读量子力学和机器学习的共生关系

IT派 - {技术青年圈} 持续关注互联网、大数据、人工智能领域 原作:Reena Shaw 安妮 编译自 KDnuggets 量子位 出品 | 公众号 Qb...

40760
来自专栏AI科技评论

干货 | 重温五条 AI 基础规律

AI 科技评论按:如果每个人都有足够的时间和热诚,并乐意去大学拿个 AI 学位,那你大概就不会读到这篇博客了。 虽说 AI 的工作方式挺神秘的,但在处理技术问题...

9320
来自专栏玉树芝兰

文科生用机器学习做论文,该写些什么?

从“价值、必要、讨论和工具”这四个角度,把一些容易踩的坑提示给你,助你顺利完成研究论文撰写。

12320
来自专栏新智元

【重磅】AI 自动研发机器学习系统,DeepMind 让算法学习强化学习(附论文)

【新智元导读】眼下,人工智能研发的一个大方向是用AI系统来自动化开发AI系统。虽然这一目标尚未实现,但目前的进展让已足够令人人震惊。本文介绍了最新的一些进展,包...

37980
来自专栏PPV课数据科学社区

学习攻略 | 机器学习 学习路线图

1. 引言 也许你和这个叫『机器学习』的家伙一点也不熟,但是你举起iphone手机拍照的时候,早已习惯它帮你框出人脸;也自然而然点开今日头条推给你的新闻;也习惯...

70680

扫码关注云+社区

领取腾讯云代金券