華人奪魁，「魔球」理論獲獎：KDD 2019所有獎項出爐

機器之心報道

機器之心編輯部

國際數據挖掘頂會 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 年設立了創業研究獎，旨在獎勵創業公司在科技領域研究的貢獻。今年的獎項由創業研究獎委員會在多家公司中選出。

四家獲獎公司中，兩家來自英國，另兩家則是國內創業公司，其中包括清華大學 AI 研究院的創業公司 RealAI（瑞萊智慧）以及企業徵信機構天眼查。

本文為機器之心報道，轉載請聯繫本公眾號獲得授權。

------------------------------------------------

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！