华人夺魁，「魔球」理论获奖：KDD 2019所有奖项出炉

2019 年 8 月 7 日 机器之心

机器之心报道

机器之心编辑部

国际数据挖掘顶会 KDD 2019 刚刚放出了最佳论文等奖项。最受瞩目的最佳论文奖由康奈尔大学 Kun Dong 等人，以及比利时鲁汶大学的 Tom Decroos 等人获得。除研究之外，大会举办的三大竞赛（KDD CUP）均由中国公司包揽。

第 25 届 ACM SIGKDD 知识发现和数据挖掘会议（KDD）已于今年 8 月 4 日在美国阿拉斯加州安克雷奇开幕。今年的大会奖项分为研究方向和应用数据科学方向。在今天公布的最佳论文中，康奈尔大学的《Network Density of States》获得了研究类最佳论文奖；而应用数据科学方向的最佳论文为《Actions Speak Louder than Goals: Valuing Player Actions in Soccer》，这是一篇有关足球技术分析方面的研究，来自比利时天主教鲁汶大学以及体育分析公司 SciSports。

为了提升论文接收的质量，KDD 2019 首次采用了双盲审查制度，本次大会也对研究的可复现性提出了新的要求，强调其为「论文审核过程中的一个重要因素」，只有包含两页可复现性内容附录的文章才有可能被评为 KDD 最佳论文。

KDD 对论文接收非常严格，每年的接收率均未超过 20%。本届大会在应用数据科学方向共收到大约 700 篇论文，其中 45 篇 oral 论文，约 100 篇被接收为 poster 论文；研究方向共收到约 1200 篇投稿，其中约 110 篇 oral 论文，60 篇 poster 论文，接收率仅为 14%。

研究方向最佳论文

论文：Network Density of States
作者：Kun Dong、Austin R. Benson、David Bindel（康奈尔大学）
链接：https://arxiv.org/pdf/1905.09758.pdf

谱分析将图结构与相关矩阵的特征值和特征向量联系在一起。许多谱图理论直接源于谱几何，即通过相关微分算子的谱研究可微流形。但从谱几何到谱图理论的转换主要集中在只涉及少数极端特征值及其相关特征值的结果上。与谱几何不同的是，通过特征值的总体分布（谱密度）来研究图很大程度上局限于简单的随机图模型。真实世界图谱的内部很大程度上还未被探索，所以难以计算和解释。

在本文中，研究者深入探索了真实世界图谱谱密度的核心。他们借用了凝聚态物理学中开发的工具，并添加了新的适应性来处理常见图形的谱特征。他们计算了单个计算节点上超过 10 亿个边的图的谱密度，证明所得到的方法非常高效。除了提供视觉上引人注目的图形指纹之外，研究者还展示了谱密度的估计如何简化许多常见的中心度量的计算，并使用谱密度估计关于图结构的有意义信息，这些信息不能仅从极值特征对推断出来。

谱理论是一种图理论、几何学和物理学中非常有效的分析工具。每个设定都遵循同样的步骤：

明确一个兴趣对象，比如一个图或者一个点集（manifolds）；
将对象和一个矩阵或运算器（operator）联系起来，通常是一个线性动态系统的生成器或对象上的函数平方的 Hessian 矩阵；

将矩阵或运算符的谱属性连接到原始对象的结构属性。

在每种情况下，完整的谱分解足以恢复原始对象；有趣的结果将结构与部分光谱信息联系起来。遗憾的是，由于缺乏可扩展算法，网络谱密度的分析受到限制。在本文中，作者展示了用于研究凝聚态物理中状态密度的方法如何用于研究网络中的谱密度。

研究方向亚军论文

论文：Optimizing Impression Counts for Outdoor Advertising
作者：Yipeng Zhang、Yuchen Li、Zhifeng Bao、Songsong Mo、Ping Zhang（皇家墨尔本理工大学、新加坡管理大学、武汉大学、华为）
链接：http://delivery.acm.org/10.1145/3340000/3330829/p1205-zhang.pdf

自 2017 年以来，户外广告市场规模每年增长 3%-4%，预计到 2021 年将达到 330 亿美元。其中 74% 的增长来自广告牌。广告牌的主要受众是沿途的行人。超过 80% 的司机在开车时会注意到广告牌。由于定位设备的普及，现在已经积累了大量的行人出行轨迹。那么，如何利用这些数据提升广告影响就成了研究者关心的问题。

在现实场景中，广告牌的数量和预算是固定的，因此研究人员提出通过提高户外广告的印象计数（ICOA）来提升广告效果，以此提高广告主的投资回报率。

给定一个广告牌数据库 U，其中每个广告牌都有一个位置和一个非均匀成本，一个轨迹数据库 T 和一个预算 B，它的目标是找到一组在预算范围内影响最大的广告牌。

要解决这一问题，研究人员人员必须克服两大挑战：

同一广告牌出现多少次能达到最佳效果（既给行人留下深刻印象又不浪费预算）；
第二个挑战是逻辑函数的性质。基于 logistic 函数的影响模型是非子模块的，这意味着简单的贪婪方法不能解决 ICOA 问题。更糟糕的是，不同广告牌的成本不统一，使得优化问题更加复杂。研究者表明，在任意常数因子下，逼近 ICOA 是 NP-hard 问题。

对于第一个问题，此前有研究表明，在一定范围内，广告牌出现的次数越多，给路人留下的印象越深刻，但超出这一范围之后效果会越来越差。

对于第二个问题，研究者提出了一种基于切线计算子模函数的算法来估计影响的上界。他们引入了一个带有θ-termination 条件的分支定界框架，实现 θ/2 × (1 − 1/e) 近似比。然而，当|U|很大时，这个框架非常耗时。因此，研究者利用渐进剪枝上限估计方法对其进行进一步优化，实现 θ/2 × (1 − 1/e − ϵ) 近似比例并显著降低了运行时间。他们在真实的广告牌和轨迹数据集上进行了实验，结果表明，该方法的有效性比基线高出 95%。此外，优化方法比原框架快两个数量级左右。

应用方向最佳论文

获得 KDD 2019 应用数据挖掘方向最佳论文的研究来自于比利时天主教鲁汶大学和体育分析公司 SciSports，研究有关使用新方法评价足球运动员的能力：球员在场上的动作比进球更有价值，这是一项颇具《Money Ball》风格的工作。

标题：Actions Speak Louder than Goals: Valuing Player Actions in Soccer
作者：Tom Decroos、Lotte Bransen、Jan Van Haaren、Jesse Davi
链接：https://arxiv.org/pdf/1802.07127.pdf

评估足球运动员比赛中个人行动所造成的影响是评估他们的重要指标。然而，大多数传统指标在解决此类任务时效果都不尽如人意，因为它们只关注整场比赛中仅有的几次特殊动作，比如射门和进球——而忽视了行动的背景。

研究人员提出的方法包括：

一种用于描述球场上各个球员动作的新语言；
基于它对比赛结果的影响来评估任何类型球员动作的框架，同时考虑了动作发生的背景。

2017 年 12 月 23 日西甲联赛第 17 轮巴塞罗那 3：0 皇家马德里的比赛中，比达尔最后一个进球时巴萨几名进攻队员的得分。

2017/18 赛季英超联赛进攻球员的排名与身价对比（出场时间至少为 900 分钟）。上表为进球+助攻数的排名，下表为使用新方法 VAEP 的排名。球员身价为 2019 年 2 月德国转会市场的估价。

通过评估足球运动员的动作「价值」，我们就可以量化他们对球队的总体进攻和防守贡献。研究人员展示了使用新方法如何找到传统球员评估方法忽略的信息，有关用例已在 2016/17 和 2017/18 赛季欧洲顶级联赛球探考察球员以及比赛风格描述工作中使用。

应用方向亚军论文

论文：Developing Measures of Cognitive Impairment in the Real World from Consumer-Grade Multimodal Sensor Streams
作者：Richard Chen、Filip Jankovic、Nikki Marinsek（苹果、Evidation Health、礼来公司、）
链接：http://alessiosignorini.com/articles/developing-measures-cognitive-impairment-multimodal-sensor-streams/paper.pdf

据估计，全球约有 4680 万人患有痴呆症。痴呆症的早期诊断是一项临床挑战，而且非常耗时。早期症状通常并不明显，而且长期潜伏，很容易被忽视为「正常老化」。

可穿戴消费设备、移动计算平台（智能手机、智能手表、平板电脑）和多种传感器模式的普及和进步，使得痴呆症高危人群或患者日常活动的持续监测成为可能。这些丰富的纵深信息可以用来挖掘认知障碍的生理和行为特征，从而为及时、经济、有效地检测轻度认知功能障碍（介于正常衰老和痴呆之间的一种中间状态）提供了新的途径。

在本文中，研究者提出了一个平台，可以利用消费级智能设备来远程监控认知障碍相关症状，并且不对用户生活造成明显影响。通过礼来公司一项为期 12 周的探索性数字评估研究，研究者监测了 31 名认知障碍患者和 82 名无认知障碍患者在自由生活条件下的情况，并利用该平台收集了 16TB 的数据。

研究者描述了如何谨慎地使用数据统一（data unification）、时间对齐（time alignment）和缺失值处理技术（imputation technique）来处理真实环境中固有的数据缺失率，并展示了这些数据的实用价值。

时间检验奖

今年的时间检验奖（test of time award）颁发给了卡耐基梅隆大学（CMU）和 Nielsen BuzzMetrics 在 2007 年的一项研究。

论文：Cost-effective outbreak detection in networks
作者：Jure Leskovec、Andreas Krause、Carlos Guestrin,Christos Faloutsos、Jeanne VanBriesen、Natalie Glance
链接：https://www.cs.cmu.edu/~jure/pubs/detect-kdd07.pdf

在该研究中，作者提出了一种可以最快速检测扩散信息的新方法，并证明了许多现实的爆发检测目标（例如检测可能性、受影响人群）表现出了「子模块性」的特性。利用子模块开发出的新算法可以扩展到更大的问题，实现接近最佳的配置，同时比简单的贪婪算法快 700 倍。此外，该方法易于扩展，并可以节省数个数量级的存储。

KDD CUP

今年的 KDD CUP 比赛共有超过 2800 支注册队伍参赛。这些队伍来自 39 个国家和地区，包括了 230 个学术和研究机构，参赛人员在 5000 人以上，总共提交了超过 17000 次结果。

今年的 KDD CUP 分为三个赛道，分别是：

常规机器学习竞赛（Regular Machine Learning Competition）
自动机器学习竞赛（Automated Machine Learning Competition）
「Research for Humanity」强化学习竞赛（「Research for Humanity」Reinforcement Learning Competition Track）

常规机器学习竞赛

常规机器学习竞赛由百度赞助，分为两个任务：

任务一：最适合的交通方式推荐
任务二：开放研究/应用挑战

任务一中，冠军团队成员为： Shiwen Cui、Changhua Meng、Can Yi、Weiqiang Wang、Xing Zhao、Long Guo，来自蚂蚁金服。亚军团队成员包括： Hengda Bao、Jie Zhang、Wenchao Xu、Qiang Wang、Jiayuan Xie、He Wang、Ceyuan Liang，来自上海微盟、趋势科技、滴滴、北京邮电大学、华南理工大学、京东等机构。

任务二中，获得冠军团队里有： Keiichi Ochiai、Tsukasa Demizu、Shin Ishiguro、Shohei Maruyama、Akihiro Kawana, 来自日本 NTT DOCOMO 公司。亚军团队成员： Yang Liu、Cheng Lyu、Zhiyuan Liu，来自东南大学。

百度同时设立了 PaddlePaddle 特别奖，获奖者为： Xianfeng Liang、Likang Wu、Joya Chen、Yang Liu、Runlong Yu、Min Hou、Han Wu、Yuyang Ye、Qi Liu、Enhong Chen，来自中国科学技术大学。

自动机器学习竞赛

自动机器学习竞赛由第四范式赞助，获得冠军的是： Zhipeng Luo、Jianqiang Huang、Mingjian Chen、Bohang Zheng，他们来自 DeepBlueAI 和北京大学。亚军团队则是： Chengxi Xue、Shu Yao、Zeyi Wen、Bingsheng He，来自新加坡国立大学。

「Research for Humanity」强化学习竞赛

而「Research for Humanity」强化学习竞赛由 IBM Africa 和 Hexagon-ML.com 赞助，获得冠军的是来自中国台湾国立成功大学的 Zi-Kuan Huang、Jing-Jing Xiao、Hung-Yu Kao，获得亚军的是 Lixin Zou、Long Xia、Zhuo Zhang、Dawei Yin，来自清华大学、京东和北京航空航天大学。

创业研究奖

KDD 于 2017 年设立了创业研究奖，旨在奖励创业公司在科技领域研究的贡献。今年的奖项由创业研究奖委员会在多家公司中选出。