一网打尽Google、Amazon、Microsoft、Facebook在今年KDD上的论文：神经网络、大规模计算是热点
本文针对国际工业界（以谷歌、亚马逊、微软、脸书为例）发表在数据挖掘顶级国际会议KDD上的相关论文,这些工作既包括理论性的研究也包括一些实际应用的研究工作。国内工业界：知道吗？BAT今年在KDD上作为第一单位发表了12篇文章！（内附每篇文章解读）“ 我们将于2019年1月发布《数据挖掘研究报告》敬请关注”下面以谷歌、亚马逊、微软、脸书为例简单介绍一下国际工业界在数据挖掘领域顶级国际会议KDD上发表的研究工作。文末可获取所有论文Google（谷歌）几乎每年谷歌都会发表一些让人惊艳的研究工作，包括之前的MapReduce、Word2Vec、BigTable，近期的BERT。数据挖掘是Google研究的一个重点领域。2018年Google全球不同研究中心在数据挖掘顶级国际会议KDD上一共发表了7篇全文（见下表，其中有三篇是与访问学生一起合作的）。下面简要解读一下这几篇文章。
《Q&R: A Two-Stage Approach toward Interactive Recommendation》该论文主要探讨交互式推荐问题，提出一个两阶段的交互推荐方法。传统的推荐一般都是首先分析用户兴趣，然后基于用户兴趣和推荐信息之间的匹配度进行推荐，然而这种方法很难精准捕获用户的实时兴趣以及用户查询场景的真实意图，交互式推荐是近年业界备受关注的问题。本质上这是一个Active Learning（主动学习）或者Online Learning（在线学习）问题。该文提出一个基于RNN的问题（话题）自动生成方法（第一阶段），也就是系统会根据用户兴趣自动生成话题，主动询问用户，然后在第二阶段根据用户反馈修正推荐结果，最后该方法在YouTube上进行了验证。基于深度学习的话题生成可以大大提高最终的推荐结果。图24给出了文章的主要思想和结果，其中左图是系统主动提问的界面；右上图是文章使用的基于RNN的话题自动生成模型（当然第二阶段还有一个混合模型）；右下图是针对自动生成话题的评估结果。
自左至右：系统主动提问界面；话题自动生成模型RNN；提问话题评估结果
《Collaborative Deep Metric Learning for Video Understanding》该论文提出了一个新的深度学习框架，大大提高了视频理解的精度。传统的视频分析的研究大多针对特定问题，比如视频分类、视频搜索、个性化推荐等；这篇文章提出一个新的表示学习方法，把传统的几个问题都归一化为统一表示的学习问题。最后在2亿多个YouTube视频数据上的实验表明，无论视频分类还是视频推荐都比传统方法好的多。本质上，这篇文章解决的视频理解的问题可以用下图的例子来解释。
视频推荐（左）和视频搜索（右）从方法论来看，这篇文章的方法其实很简单，首先对视频的内容进行表示学习，具体来说用的是Inception-v3 网络，另一方面对音频信息也进行表示学习，这里用了一个基于VGG的音频模型和ResNet-50的网络结构。学习的时候使用了排序的Triplet loss，也就是给定三个视频（Anchor、Positive、Negative），保证学习的时候Anchor视频和Positive更相似，和Negative更不相似（Negative可以随机选择一个）。学习的时候把刚才单独学习到的表示作为Triplet Loss function的输入，然后学习每个视频的混合表示（包括视频和音频）。混合策略可以有Early Fusion（右下图中的第一个混合策略），或者Late Fusion（右下图中的第一个混合策略）。
方法框架最后在视频推荐和视频检索方面的效果都很不错。下图是视频推荐的评测结果以及在YouTube-8M数据集上的视频检索的例子。
Comparison in NDCG for various feature size with quantization.We observe that 4 bits per value are enough to almost preserve end-to-end recommendation performance.
Demonstration of related video retrieval with You Tube-8M Dataset.The left-most column is the query video,and other videos in the same row are top 4 most relevant videos found by our model .We show You Tube thumbnail,title,and revelance score we computed (in red italie).
《Anatomy of a Privacy-Safe Large-Scale Information Extraction System Over Email》该论文也是一篇Applied Data Science Track的文章，这也是Google Gmail团队最近几年若干实用型文章中的一篇。KDD2010的时候他们团队就有一篇推荐相关收信人的文章，方法非常简单、实用，而且很快该方法就迅速上线到系统，目前已经成为Gmail的标配。这次发表的文章是从Gmail的邮件内容中抽取结构化信息，例如个人相关的账单信息，飞机行程信息等。和传统的信息抽取不同，这里的抽取更关键的是要保证规模以及抽取中可能遇到的隐私问题。下图是整个抽取系统的架构图。
The Juicer architecture.Details of the ML component are described in the text and depicted in Figure3.这个全新的抽取架构叫做Juicer，核心的技术方面一个是把传统的基于模板的方法进行了扩展，此外在抽取的时候加入了对隐私保护的考虑。例如具体抽取模板的时候使用了k-anonymity方法进行了匿名化，而且初始的标注数据是一个很小的由用户自愿拿出来的标注集。另外还有个很大的挑战是数据质量，由于训练数据比较少，所以数据的偏差性很大，系统通过一些观察，比如偏差主要是倾向资深用户，所以系统的训练主要是用老/资深用户的数据进行训练，这一定程度上纠正了偏差问题。最后在几个不同案例的抽取上，系统取得了很好的效果。
Precision on a sample of templates classified positive both for those templates that correspond to existing parsers and newly identified templates that do not correspond to existing parsers.
《Scalable k-Means Clustering via Lightweight Coresets》这篇论文基本思想就是做一个快速k-means算法或者说适用于大规模数据的k-means算法。具体思路是利用抽样的方法从原始数据中抽样出一个足够小的子集（称为Coresets），然后在这个Coresets上进行训练，最后得到的结果和在大规模数据上的结果相当。文章理论证明了保证精度的情况下Coreset大小和数据集的特征个数d以及聚类个数据k的乘积成正比。
由于是个理论文章，所以文章的实验相对比较简单，对比了两种方法，一种是随机抽样（Uniform），还有一种是Lucic等人提出的经典算法CS。几个数据集还行，都相对比较小，看来作者真的不想做实验室。最后的结果也表明作者提出的方法LWCS可以把误差降低到16%，并且同时保持两个数量级的加速度。下表给出了在这几个数据集（KDD—KDD CUP2004里面的一个匹配蛋白质序列的竞赛、CSN—手机加速传感器的数据、Song—预测音乐的年份、RNA—预测RNA的序列对）上的实验结果。
Relative error and speedup of different methods vs.FULL for k=100
《Optimal Distributed Submodular Optimization via Sketching》这篇论文提出了一个针对Submodular优化的分布式算法。Submodular是数学、数据挖掘、优化等很多领域中的一个共性问题，早先几年在社交网络、尤其是影响力最大化传播中使用非常多，当然传统的数学问题就是Set Cover。Submodular比较流行是因为它虽然是一个NP难问题，但能找到一个非常简单的贪婪算法，并且能够保证很好的最优效果的近似（大约54-66%）效果。这篇文章是提出一个分布式算法，算法保证了很好的空间复杂度、优化效果。下图给出了不同submodular问题下文章方法和传统方法在理论上的比较结果，这是一个非常有意思而且很Solid的结果。其中Dominating Set就是影响力最大化的基础问题。
《Sequences of Sets》论文提出一个随机模型，用于挖掘这种和时间相关的隐含模型，模型能否挖掘出两个方面的关联，一个是序列中相邻集合之间的关联关系；一个是最近参数模型（使得模型更好描述最近的信息）。其实论文研究的问题是数据挖掘里面一个非常基础的问题：给定一个集合序列，也就是序列中每个点都是一个集合，这个集合可以是比如社交网络中的用户行为，当然连续两个点的行为可能是一样的，也可能非常不同，Sequence of sets里面最重要的事情就是自动挖掘出里面隐含的模式。
《Modeling Task Relationships in Multi-task Learning with Multi-gate Mixture-of-Experts》该论文是一篇基于神经网络的多任务学习模型。本质上，这是个多任务学习的扩展，多任务学习在很多实习系统中都有应用，比如推荐。基于神经网络的多任务学习本质上就是在多个任务之间加一个共享表示层，从数学上可以证明这个共享表示层可以起到正则化的效果，提高模型的泛化能力，最简单的共享层就是如下图(a)所示。本文是提出一个多层共享表示层的模型，如下图(c)，MoE（Mixed of Experts），也就是在多个任务之间学习多个共享层，然后mixture起来。在mixture的时候可以加上单gate和多gate的学习机制。
最后在UCI的数据集上，这个方法相比传统方法有一定的提升。下图是一个实验结果。
Performance on the first group of UCI Censusincome dataset后来作者还在Google的大规模数据上进行了实验，也取得一定的提升。
Engagement performance on the real large-scale recommendation systemGoogle（谷歌）2018年发表于KDD的论文列表Q&R: A Two-Stage Approach toward Interactive Recommendation.收录会议：KDD’18Collaborative Deep Metric Learning for Video Understanding.收录会议：KDD’18Anatomy of a Privacy-Safe Large-Scale Information Extraction System Over Email.收录会议：KDD’18Scalable k-Means Clustering via Lightweight Coresets.收录会议：KDD’18Optimal Distributed Submodular Optimization via Sketching.收录会议：KDD’18Sequences of Sets.收录会议：KDD’18Modeling Task Relationships in Multi-task Learning with Multi-gate Mixture-of-Experts.收录会议：KDD’18Amazon亚马逊公司近几年发展势头超级猛，前几年华丽的转身：从一个网上商店公司变为云平台公司再转变到目前的人工智能公司，亚马逊也在数据挖掘领域开始占有一席，尤其是在人才网罗、开源、核心技术研发。2018年亚马逊在数据挖掘顶级国际会议KDD的Applied Data Science Track（应用数据科学Track）上一共发表了2篇全文（见下表），另外还有两个应用科学的邀请报告。下面简要解读一下这几篇文章。
《Buy It Again: Modeling Repeat Purchase Recommendations》这篇文章提出一个Poisson-Gamma模型（PG）以及他的扩展版本（MPG），后来在离线数据上得到了一定的提升。该论文是亚马逊总部Seattle研究院的工作，问题非常简单，就是研究网络用户的重复购买行为，传统研究一般是根据用户兴趣研究用户未来可能购买什么东西（大家骨子里的思维方式都是用户不会再购买已经买过的商品，比如电视机），然而事实上很多购买行为都是重复购买，比如买牙膏、或者买某些消费品，用户反而倾向于买已经买过的商品，作者把这个问题叫做Repeat Purchase。
Lift in precision,recall,andnDCG for the ATD,PG,and MPG models at rank m=3 as compared to the baseline RCP model.在真实的在线系统里面的A/B测试，该方法也得到了很好的提升。这里也能看出KDD的应用科学Track比较喜欢上线的工作。类似的工作在算法本身上可能新意并不大，但在实际系统中效果很好，并且帮助到实际系统了，往往比较容易在KDD的ADS Track上发表。
《Open Tag: Open Attribute Value Extraction from Product Profiles》这篇论文出用双向LSTM来学习特征，然后用CRF来提高抽取精度，然后又加上了一个Attention机制来提高可解释性，最后还加上了一个主动学习方法来降低标注工作量。这篇论文是亚马逊的实习生做的。做的是个老问题，就是从产品页面抽取产品描述的属性值，但不同的是这里抽取的属性值可能是之前没有出现（定义）过的。下图描述了整个模型框架。总的来说该架构很好的融合了现有的一些技术。
最后也取得不错的实验结果。
Performance comparison of different models on attribute extraction for different product profiles and datdsets.OpenTag outperforms other state-of-the-art NERsystems [11,13,15,17] based on BiLSTM-CRF.
《Challenges and Innovations in Building a Product Knowledge Graph》这个报告主要讲了产品知识图谱构建的挑战，包括概念抽取、知识集成、重要知识概念发现以及如何结合用户的知识图谱。该论文是亚马逊Xin Luna Dong的邀请报告。KDD每年ADS Track都会专门邀请一些工业界的讲者来做报告。Luna以前在Google做过Google的知识图谱，目前在亚马逊负责知识图谱项目。
《Algorithms, Data, Hardware and Tools - a Perfect Storm》这个报告主要讲了超大规模数据时代，统计机器学习面临的一系列来自算法复杂度、硬件的挑战以及未来的机遇。这篇报告是KDD的老熟人、原来CMU教授，现在亚马逊Web 服务部门负责机器学习的Alex Smola和Edo Liberty一起做的。他在KDD拿过多篇最佳论文，在机器学习方面很有独到的见解。Amazon2018年发表于KDD的论文列表Buy It Again: Modeling Repeat Purchase Recommendations.收录会议：KDD’18OpenTag: Open Attribute Value Extraction from Product Profiles.收录会议：KDD’18Challenges and Innovations in Building a Product Knowledge Graph.收录会议：KDD’18 应用科学邀请报告Algorithms, Data, Hardware and Tools - a Perfect Storm.收录会议：KDD’18 应用科学邀请报告Microsoft微软是老牌论文王国，一直以来都在学术界特别活跃，因此在KDD上每年和微软有关的论文非常多，因此这里只统计了微软作为第一作者的文章。2018年在数据挖掘顶级国际会议KDD上一共发表了6篇全文（见下表），另外还有一个应用科学的邀请报告，这些文章和报告都更多的从大数据的角度在思考如何更有效，更快速的分析。下面简要解读一下这几篇文章。
《Applying the Delta Method in Metric Analytics: A Practical Guide with Novel Ideas》该论文提出一个在大数据环境下如何做算法效果评估的Delta方法。该论文也是一篇Applied Data Science的文章，不过这篇文章的思想还是很有意思的。论文基本想法是基于大数定律，即中心极限定律：如果样本满足独立同分布，即每个样本有相同的均值和方差，则当样本个数趋于无穷大的时候，所有样本的均值偏差满足正态分布。
《Web-Scale Responsive Visual Search at Bing》该论文主要介绍了在Microsoft Bing里面上线的一个可视化搜索。如下图所示，给定一个图片（左图是桌面版），系统可以自动检测图片中的重要元素，用户也可以根据自己的喜好选择图片中的对象，系统则自动找出和对象相关的产品；下图右边是一个手机版。
该系统已经索引了数十亿图片，每个图片也预先抽取了上千特征，针对用户定制的可视化搜索可以做到200毫秒。算法则使用了DNN来抽取特征，然后用N-nearest方法进行匹配。从应用的角度，这还是一个很有意思的工作。
《BigIN4: Instant, Interactive Insight Identification for Multi-Dimensional Big Data》该论文介绍了一个从高维大数据中通过交互方式进行快速查询的方法，BigIN4可以在data cube中做到快速查询（比传统抽样方法快50倍）。该方法的本质是做了一个降维处理，见下图。第2个图则给出了BigIN4可能挖掘出来的Insights：包括Outstanding（就是某些数据模式和其他数据显著不同）；Dominance（某个因素对数据分布起着绝对性作用）；Top Two（某个维度的两个取值占了整个数据样本的大多数）；Outlier（时间序列上的显著差异）；Increase/Decrease（时间序列上的递增或者递减）。
《RapidScorer: Fast Tree Ensemble Evaluation by Maximizing Compactness in Data Level Parallelization》论文提出一个树状模型的集成算法，并将其应用于搜索引擎。论文的方法是在已有方法RapidScore的基础上进行扩展的，本质上就是决策树的模型合成。最后在两个公开数据集MSN合AdsCTR上进行了验证。效果比XGBoost等算法都要好。
《Recurrent Binary Embedding for GPU-Enabled Exhaustive Retrieval from Billion-Scale Semantic Vectors》该论文提出一个Recurrent Binary Embedding（RBE）方法来学习搜索场景下对象的低维表示，该方法最大的特色是可以增量的在二进制的表示中加入二进制残差向量。该模型可以很快速的在超大规模搜索系统中快速定位最相关的对象。RBE模型其实就是利用残差网络计算查询Query和关键词Keyword（例如广告商定义的关键词）之间的匹配度。下图给出了RBE模型的总体架构。RBE的二进制向量最大的有点就是存储比较小，可以把内存开销缩减一个数据级，这对于检索来说尤为重要，因为一般检索系统媒体需要服务的搜索次数非常多，如何提高检索效率非常重要。
《Efficient Attribute Recommendation with Probabilistic Guarantee》论文介绍了大数据分析里面一个非常基础的问题，就是给定两个数据集，如何找到这两个集合中，差异最大的属性。最简单的方法是直接遍历两个集合中所有的数据，然而这样的计算复杂度很高。这篇文章给出了一个近似算法，并且分析了算法的理论错误界。最后在真实数据上，该方法可以比传统方法速度提高一个数量级，误差接近0。
《Planet-Scale Land Cover Classification with FPGAs》论文主要介绍了微软利用卫星图片来做的大数据分析，建立了美国农业图像大数据库，从模型的角度实现了基于DNN的模型，在架构方面，比较有意思的是该工作使用了基于FPGAs的深度学习架构。本报告是一个受邀的工业界报告。报告人是微软商业智能部门的CTO Joseph Sirosh博士。Joseph Sirosh博士以前是Amazon的全球创新平台的副总裁。该工作可以实现10分钟内处理20T的高清图片，大约每秒40多万张图片。Microsoft2018年发表于KDD的论文列表Applying the Delta Method in Metric Analytics: A Practical Guide with Novel Ideas.收录会议：KDD’18Web-Scale Responsive Visual Search at Bing.收录会议：KDD’18BigIN4: Instant, Interactive Insight Identification for Multi-Dimensional Big Data.收录会议：KDD’18RapidScorer: Fast Tree Ensemble Evaluation by Maximizing Compactness in Data Level Parallelization.收录会议：KDD’18Recurrent Binary Embedding for GPU-Enabled Exhaustive Retrieval from Billion-Scale Semantic Vectors.收录会议：KDD’18Efficient Attribute Recommendation with Probabilistic Guarantee.收录会议：KDD’18Planet-Scale Land Cover Classification with FPGAs.收录会议：KDD’18 应用科学邀请报告FacebookFacebook 2018年在数据挖掘顶级国际会议KDD上一共发表了2篇文章（见下表），这两篇文章都是发表在KDD的Applied Data Science Track。下面简要解读一下这两篇文章。
《Rosetta: Large Scale System for Text Detection and Recognition in Images》这篇文章介绍了Facebook的图像文字识别OCR系统Rosetta。Facebook每天用户都上传大量图片，从这些图片中识别出文字可以帮助提高搜索和推荐效率。这里面的挑战主要是两个，一个是图片中的文字字体、文字语言多样，而且还可能有很多自定义词以及一些特殊的字符，例如网页链接等；另一个挑战是每天需要处理大量的图片。Rosetta的目标是做到实时处理（识别图片中的文字）用户上传的图片。从算法来说，Rosetta使用了一个两阶段的识别策略，第一阶段是用Faster-RCNN快速识别图片中包含文字的区域，第二阶段则是使用了一个全卷积网络进行文字识别。下图描述Rosetta的两阶段抽取架构。
《A Real-time Framework for Detecting Efficiency Regressions in a Globally Distributed Codebase》该论文探讨了一个Facebook非常实际的在线运营问题，当code改变的时候，哪些code改变会引起严重的系统效率问题。Facebook每月的月活用户超过20亿，而且在Facebook平台上运行了大量的复杂系统，包括应用程序等。因此，如何保证在线代码改变可能带来的效率下降成为一个挑战。从数据挖掘的角度，其本质问题是一个实时数据的异常检测问题，传统的实时数据异常检测包括三种方法：点异常检测（突发异常）、模式异常（一组点的连续异常）、持续点异常（异常点逐渐变化，导致最终差异较大）。这三个问题其实都有很多大量的研究，当然从异常点检测本身来说，其关键挑战是定义什么是异常。这篇文章主要描述了Facebook的持续点异常检测问题，其解决思路是使用了一个CUSUM算法进行持续点异常，最后进行了一个可扩展的实现。Facebook2018年发表于KDD的论文列表Rosetta: Large Scale System for Text Detection and Recognition in Images.收录会议：KDD’18A Real-time Framework for Detecting Efficiency Regressions in a Globally Distributed Codebase.收录会议：KDD’18