作者 | 陳彩嫻、王曄

編輯 | 王曄

8月19日到26日，IJCAI 2021 在線上召開，昨天又公布了兩大獎(jiǎng)項(xiàng)，分別是 AIJ 杰出論文獎(jiǎng)（AIJ Prominent Paper Award 2021）與 AIJ 經(jīng)典論文獎(jiǎng)（Classic AIJ Paper Award）！

AIJ 的全稱為“Artificial Intelligence Journal”，即《人工智能期刊》，始建于 1970 年，是人工智能研究領(lǐng)域的頂級學(xué)術(shù)期刊，具有公認(rèn)的權(quán)威性與知名性。

上個(gè)月，IJCAI 2021 在開幕前已頒布三大獎(jiǎng)項(xiàng)，其中，“強(qiáng)化學(xué)習(xí)之父”、阿爾伯塔大學(xué)計(jì)算科學(xué)系教授 Richard Sutton 獲得“卓越研究獎(jiǎng)”，卡內(nèi)基梅隆大學(xué)計(jì)算機(jī)學(xué)院軟件研究所助理教授方飛獲得計(jì)算機(jī)與思想獎(jiǎng)，卡內(nèi)基梅隆大學(xué) Angel Jordan 計(jì)算機(jī)科學(xué)教授 Tuomas Sandholm 則獲得約翰麥卡錫獎(jiǎng)。

那么，IJCAI 最新頒布的兩大獎(jiǎng)項(xiàng)又花落誰家？AI 科技評論為你揭曉。

1

AIJ 杰出論文獎(jiǎng)

今年，IJCAI 杰出論文獎(jiǎng)的獲得者是 Frank Hutter、Lin Xu、Holger Hoos 與 Kevin Leyton-Brown，獲獎(jiǎng)?wù)撐臑?2014 年發(fā)表在《人工智能期刊》上的工作“Algorithm runtime prediction: Methods & evaluation”。

在這篇工作中，作者團(tuán)隊(duì)提出了處理算法參數(shù)的新方法。

他們提到，用機(jī)器學(xué)習(xí)技術(shù)將算法運(yùn)行時(shí)間的模型構(gòu)建成一個(gè)具備特定問題實(shí)例特征的函數(shù)，然后預(yù)測算法在完全陌生的輸入上所需的運(yùn)行時(shí)間，也許聽起來很荒謬，但實(shí)現(xiàn)的可能性極高。而且，這類模型在算法分析、組合算法選擇與參數(shù)化算法自動配置上具有重要應(yīng)用。

針對這類模型，作者團(tuán)隊(duì)介紹了新的拓展與改進(jìn)方式；更重要的是，他們提出將算法參數(shù)作為模型輸入，進(jìn)行了更徹底的處理。此外，他們還全面描述了預(yù)測命題可滿足性（SAT）、旅行商（TSP）和混合整數(shù)規(guī)劃（MIP）問題的算法運(yùn)行時(shí)間的已有特征與新特征。

作者團(tuán)隊(duì)通過大量的實(shí)驗(yàn)分析對這些創(chuàng)新進(jìn)行了評估，并與大量研究運(yùn)行時(shí)間建模的工作進(jìn)行了比較。在實(shí)驗(yàn)中，他們考慮了11種算法與35種實(shí)例分類，涵蓋了大量 SAT、MIP 與 TSP 實(shí)例，包括隨機(jī)生成的結(jié)構(gòu)化程度最低的案例，已經(jīng)從現(xiàn)實(shí)工業(yè)應(yīng)用中產(chǎn)生的結(jié)構(gòu)化程度最高的案例。

總的來說，這篇工作所提出的新模型被證明，在遇到全新輸入、全新問題等等時(shí)能夠更好地預(yù)測算法的運(yùn)行時(shí)間。

論文鏈接：https://www.sciencedirect.com/science/article/pii/S0004370213001082

作者團(tuán)隊(duì)：

Frank Hutter，現(xiàn)任德國弗萊堡大學(xué)工程學(xué)院計(jì)算機(jī)科學(xué)系教授，機(jī)器學(xué)習(xí)組負(fù)責(zé)人。2004年碩士畢業(yè)于德國達(dá)姆施塔特工業(yè)大學(xué)（Darmstadt University），2009年博士畢業(yè)于不列顛哥倫比亞大學(xué)（UBC），主要研究興趣是統(tǒng)計(jì)機(jī)器學(xué)習(xí)、自動問題求解、自動學(xué)習(xí)軟件系統(tǒng)、不確定情況下的序列決策與科學(xué)實(shí)驗(yàn)，目前的研究課題主要是圍繞貝葉斯優(yōu)化、自動機(jī)器學(xué)習(xí)、深度學(xué)習(xí)與自動算法設(shè)計(jì)。

個(gè)人主頁：https://ml.informatik.uni-freiburg.de/profile/hutter/

Holger Hoos，AAAI Fellow，荷蘭萊頓大學(xué)萊頓高級計(jì)算機(jī)科學(xué)研究所（LIACS）機(jī)器學(xué)習(xí)教授，同時(shí)在加拿大不列顛哥倫比亞大學(xué)（UBC）計(jì)算機(jī)系擔(dān)任兼職教授。1998年在德國達(dá)姆施塔特工業(yè)大學(xué)獲得博士學(xué)位，主要研究興趣是人工智能、經(jīng)驗(yàn)算法、生物信息學(xué)等，在隨機(jī)局部搜索的算法設(shè)計(jì)上取得了卓越成就，也是自動化機(jī)器學(xué)習(xí)（AutoML）改變的開山鼻祖之一。

個(gè)人主頁：https://www.universiteitleiden.nl/en/staffmembers/holger-hoos#tab-1

Kevin Leyton-Brown，AAAI Fellow，加拿大不列顛哥倫比亞大學(xué)教授，1998年本科畢業(yè)于加拿大麥克馬斯特大學(xué)（McMaster University），碩士與博士則分別于2001年、2003年畢業(yè)于斯坦福大學(xué)，主要研究內(nèi)容是機(jī)器學(xué)習(xí)與電子市場設(shè)計(jì)和操作的交叉，以及機(jī)器學(xué)習(xí)與啟發(fā)式算法的設(shè)計(jì)交叉，曾憑借 SAT 求解器 SATzilla在國際SAT求解器競賽中獲得許多獎(jiǎng)牌。

個(gè)人主頁：https://www.cs.ubc.ca/~kevinlb/

注：Lin Xu 資料不詳，故未作介紹。

2

AIJ 經(jīng)典論文獎(jiǎng)

此外，今年 IJCAI 經(jīng)典論文獎(jiǎng)的獲得者是 Leslie Pack Kaelbling、Michael Littman與 Anthony Cassandra，獲獎(jiǎng)?wù)撐臑?1998 年發(fā)表在《人工智能期刊》上的工作“Planning and acting in partially observable stochastic domains”。

在這篇工作中，作者團(tuán)隊(duì)將運(yùn)籌研究技巧應(yīng)用于解決在部分可觀察的隨機(jī)域中選擇最佳動作的問題。

他們首先介紹了馬爾可夫決策過程（mdps）與部分可觀察MDP（pomdps），然后提出了一種可以離線解決 pomdps 的新算法，并展示了 POMDP 解決方案在某些情況下可以如何提取出內(nèi)存有限的控制器。

最后，他們將這篇工作與以往的研究作對比，探討了尋找準(zhǔn)確解決 pomdps 方法的復(fù)雜程度，以及尋找近似解的可能性。

論文鏈接：https://www.sciencedirect.com/science/article/pii/S000437029800023X

作者團(tuán)隊(duì)：

Leslie Pack Kaelbling，AAAI Fellow，現(xiàn)任麻省理工學(xué)院 EECS 教授，在情景智能體設(shè)計(jì)、移動機(jī)器人、強(qiáng)化學(xué)習(xí)與決策理論規(guī)劃等方面進(jìn)行了大量研究。1983年本科畢業(yè)于斯坦福大學(xué)哲學(xué)系，1990年在斯坦福大學(xué)獲得計(jì)算機(jī)科學(xué)博士學(xué)位。

個(gè)人主頁：https://www.csail.mit.edu/person/leslie-kaelbling

Michael Littman，AAAI Fellow 與 ACM Fellow，布朗大學(xué)計(jì)算機(jī)系Royce Family教授，主要研究機(jī)器學(xué)習(xí)與不確定性決策，在強(qiáng)化學(xué)習(xí)、概率規(guī)劃與自動填字猜謎等方面的研究獲得了三個(gè)最佳論文獎(jiǎng)與兩個(gè)有影響力的論文獎(jiǎng)。

前兩個(gè)月，他在 ACM 通訊上發(fā)文痛斥論文作者和審稿人串通欺騙盲審的現(xiàn)象。

個(gè)人主頁：https://www.littmania.com/

Anthony Cassandra，又稱“Tony Cassandra”，1998年博士畢業(yè)于布朗大學(xué)，目前是 RVshare 的技術(shù) VP，主要研究軟件設(shè)計(jì)與管理。

個(gè)人主頁：https://tonycassandra.com/

3

杰出論文獎(jiǎng)

今年，IJCAI杰出論文獎(jiǎng)共有三篇，榮譽(yù)提名一篇。

第一篇獲獎(jiǎng)?wù)撐臑椤禠earning GeneralizedUnsolvability Heuristics for Classical Planning》。作者：Simon St?hlberg (Link?ping University), Guillem Francès (UniversitatPompeu Fabra), Jendrik Seipp (Link?ping University)。

論文摘要：

近些年來經(jīng)典規(guī)劃方面的研究提出了一些專用方法來檢測無法解決的狀態(tài)，即無法達(dá)到目標(biāo)狀態(tài)的狀態(tài)。在本篇獲獎(jiǎng)?wù)撐闹?，研究者從廣義規(guī)劃的角度處理問題，并學(xué)習(xí)描述整個(gè)規(guī)劃領(lǐng)域不可解的一階公式。此外，該研究還展示了如何將這個(gè)問題轉(zhuǎn)換為一個(gè)自監(jiān)督分類任務(wù)。

本文使用到的訓(xùn)練數(shù)據(jù)是通過對每個(gè)域的小實(shí)例進(jìn)行詳盡地探索而自動生成和標(biāo)記的，候選特征是根據(jù)用于定義域的判斷自動計(jì)算出來的。研究者研究了三種具有不同屬性的學(xué)習(xí)算法，并將它們與文獻(xiàn)中的啟發(fā)式算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，本文所提出的方法能夠捕獲重要的不可解狀態(tài)類別，并具有較高的分類準(zhǔn)確率。此外，啟發(fā)式的邏輯形式使它們易于解釋和推理，并且可用于表明在某些域中學(xué)習(xí)的特征準(zhǔn)確地捕獲了該域的所有無法解決的狀態(tài)。

論文鏈接：https://www.ijcai.org/proceedings/2021/0574.pdf

作者團(tuán)隊(duì)：

Simon St?hlberg 是林雪平大學(xué)(Link?ping University)計(jì)算機(jī)與信息科學(xué)系博士后，主要研究人工智能和集成計(jì)算機(jī)系統(tǒng)（AIICS）。

個(gè)人主頁：https://liu.se/en/employee/simst50

Guillem Francès是西班牙巴塞羅那加泰羅尼亞理工大學(xué)(Universitat Pompeu Fabra)博士后研究員，論文研究重點(diǎn)是開發(fā)有效的方法來利用獨(dú)立于領(lǐng)域的經(jīng)典規(guī)劃語言中的表達(dá)建模結(jié)構(gòu)。

個(gè)人主頁：https://www.upf.edu/web/ai-ml/entry/-/-/31934/adscripcion/guillem-franc%C3%A8s

Jendrik Seipp是林雪平大學(xué)(Link?ping University)計(jì)算機(jī)與信息科學(xué)系人工智能助理教授。與 Hector Geffner 和 Ulf Nilsson 一起領(lǐng)導(dǎo) AIICS 部門的"Representation, Learning and Planning"實(shí)驗(yàn)室。

個(gè)人主頁：https://liu.se/en/employee/jense56

第二篇獲獎(jiǎng)?wù)撐臑椤禣nthe Relation Between Approximation Fixpoint Theory and Justification Theory》。作者：Simon Marynissen (KU Leuven), Bart Bogaerts (Vrije UniversiteitBrussel), Marc Denecker (KU Leuven)。

論文摘要：

AFT（Approximation FixpointTheory ）和 JT（JustificationTheory ）是兩個(gè)統(tǒng)一邏輯形式的框架。AFT 用lattice 算子的不動點(diǎn)來研究語義，JT 則解釋了為什么某些事實(shí)在模型中成立或不成立。雖然方法不同，但是這兩種框架在設(shè)計(jì)時(shí)考慮了相似的目標(biāo)，即研究非單調(diào)邏輯中出現(xiàn)的不同語義。本篇獲獎(jiǎng)?wù)撐牡牡谝粋€(gè)貢獻(xiàn)是為兩個(gè)框架之間提供了一個(gè)正式的聯(lián)系。準(zhǔn)確地說，該研究表明每個(gè) justification 框架都引入了一個(gè)逼近器（approximator），并且這種從 JT 到 AFT 的映射保留了所有的主要語義。第二個(gè)貢獻(xiàn)是利用這種對應(yīng)關(guān)系用一類新的語義來擴(kuò)展 JT，即終極語義（ultimate semantic）：終極語義可以通過 justification 框架上的句法轉(zhuǎn)換在 JT 中獲得，本質(zhì)上是對規(guī)則執(zhí)行某種解析。

論文鏈接：https://www.ijcai.org/proceedings/2021/0272.pdf

作者團(tuán)隊(duì)：

Simon Marynissen 是魯汶大學(xué)(KU Leuven)博士研究員，主要研究聲明式語言和人工智能 (DTAI)。

個(gè)人主頁：https://www.kuleuven.be/wieiswie/en/person/00117394

Bart Bogaerts 是布魯塞爾自由大學(xué)(Vrije Universiteit Brussel)人工智能實(shí)驗(yàn)室的助理教授。他的研究興趣遍及知識表示領(lǐng)域。

個(gè)人主頁：https://ai.vub.ac.be/team/bart-bogaerts/?utm_source

Marc Denecker 是魯汶大學(xué)(KU Leuven)研究員，負(fù)責(zé)知識表示和推理研究小組。

個(gè)人主頁：https://people.cs.kuleuven.be/~marc.denecker/

第三篇獲獎(jiǎng)?wù)撐臑椤禟eepYour Distance: Land Division With Separation》。作者：EdithElkind (University of Oxford), Erel Segal-Halevi (Ariel University), WarutSuksompong (National University of Singapore) 。

論文摘要：

本篇獲獎(jiǎng)?wù)撐耐ㄟ^研究處理現(xiàn)實(shí)生活中的應(yīng)用需求，讓公平劃分理論更接近于實(shí)際。該研究關(guān)注 landestates 的兩個(gè)需求：（1）每個(gè)智能體都應(yīng)該獲得一個(gè)可用幾何形狀的地塊；（2）不同智能體的地塊必須在物理上分開。有了這兩點(diǎn)要求，按比例來劃分的經(jīng)典公平概念是不切實(shí)際的，因?yàn)榭赡軣o法對其進(jìn)行乘法近似。相比之下，Budish 在 2011 年提出的序列最大值共享近似（the ordinal maximin share approximation）則提供了更有意義的公平保證。當(dāng)可用形狀為正方形、矩形或任意軸對齊矩形時(shí)，本篇獲獎(jiǎng)?wù)撐淖C明了可實(shí)現(xiàn)的最大共享保證的上限和下限，并探索了在此設(shè)置下找到公平劃分的算法和查詢復(fù)雜度。

論文鏈接：https://arxiv.org/pdf/2105.06669.pdf

Edith Elkind 是牛津大學(xué)(University of Oxford)計(jì)算機(jī)學(xué)教授、非教程研究員。Elkind博士于 2013 年加入牛津計(jì)算機(jī)科學(xué)系。在來到牛津之前，她是南洋理工大學(xué)的助理教授，她的研究得到了國家研究基金會 (NRF) 獎(jiǎng)學(xué)金的支持。

個(gè)人主頁：https://www.cs.ox.ac.uk/people/edith.elkind/

Erel Segal-Halevi是Ariel 大學(xué)(Ariel University)計(jì)算機(jī)科學(xué)系的終身講師。主要研究目標(biāo)是開發(fā)算法使人類社會更美好、更公平。

個(gè)人主頁：http://tora.us.fm/erelsgl/

Warut Suksompong 是新加坡國立大學(xué)(National University of Singapore)計(jì)算機(jī)學(xué)院助理教授。此前是牛津大學(xué)計(jì)算機(jī)科學(xué)博士后研究員。

個(gè)人主頁：https://www.comp.nus.edu.sg/~warut/

獲榮譽(yù)提名的論文是《Actively Learning Concepts and Conjunctive Queries under ELdr-Ontologies》。作者：Maurice Funk (University of Bremen), Jean Christoph Jung (Universityof Hildesheim), Carsten Lutz (University of Bremen)。

論文摘要：

本文考慮在存在描述邏輯制定的本體情況下學(xué)習(xí)一個(gè)概念或查詢的問題，在 Angluin 的主動學(xué)習(xí)框架下，允許學(xué)習(xí)算法交互地查詢 oracle（如領(lǐng)域?qū)＜遥１疚谋砻?，以下?nèi)容可以在多項(xiàng)式時(shí)間內(nèi)學(xué)會。(1)概念，(2)無對稱性的概念，(3)和弦性的、無對稱性的、有界算數(shù)的聯(lián)合查詢（CQ）。在所有的情況下，學(xué)習(xí)者都可以向 oracle 提出基于 ABoxes 的成員查詢和等價(jià)查詢，詢問所考慮的類中的給定概念/查詢是否與目標(biāo)等價(jià)。當(dāng)我們在等價(jià)查詢中承認(rèn)不受限制的 CQ 時(shí)，可以消除（3）中對有界元數(shù)的限制。本文還表明，概念不是在 本體存在的情況下能夠?qū)W習(xí)到的多項(xiàng)式查詢。

論文地址：https://arxiv.org/pdf/2105.08326.pdf

注：Maurice Funk 圖片資料不詳，故未做介紹。

Maurice Funk 是不來梅大學(xué)(University of Bremen)人工智能理論組的博士生。目前，在CODA項(xiàng)目工作。

 JeanChristoph Jung 是希爾德斯海姆大學(xué)(University of Hildesheim)理論計(jì)算機(jī)科學(xué)的臨時(shí)教授。

個(gè)人主頁：http://www.informatik.uni-bremen.de/~jeanjung/

Carsten Lutz 是不來梅大學(xué)(University of Bremen)教授。

個(gè)人主頁：https://www.informatik.uni-bremen.de/~clu/

雷鋒網(wǎng)雷鋒網(wǎng)雷鋒網(wǎng)

雷峰網(wǎng)特約稿件，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。