下載客戶端

登錄

30年前的熱門研究，今獲經(jīng)典論文獎，貝葉斯網(wǎng)絡(luò)之父舊論文“考古”

2020-08-11 17:00

來源：澎湃新聞·澎湃號·湃客

機(jī)器之心報(bào)道

編輯：魔王、蛋醬、張倩

一篇 30 年前的論文，因?yàn)橐淮潍@獎，又重新出現(xiàn)在世人眼前。

近日，圖靈獎得主、貝葉斯網(wǎng)絡(luò)之父 Judea Pearl 在推特上提到，自己在三十年前與當(dāng)時(shí)的博士生 Rina Dechter、Itay Meiri 合著的論文《時(shí)間約束網(wǎng)絡(luò)（Temporal Constraint Networks）》，獲得了由人工智能頂級國際期刊 AIJ 頒發(fā)的 2020 年經(jīng)典論文獎。

這篇論文發(fā)表于 1991 年，涉及的主題是上世紀(jì)八十年代的熱門話題——時(shí)間約束。目前，該論文在谷歌學(xué)術(shù)上的被引用次數(shù)接近 2500。論文一作 Rina Dechter 被認(rèn)為是「深度學(xué)習(xí)」一詞的首倡者。

這篇論文的獲獎理由如下：

這篇影響深遠(yuǎn)的論文介紹了用于定量時(shí)間推理的時(shí)間約束滿足問題（TCSP）。TCSP 及其特例——簡單時(shí)間問題（STP，可在多項(xiàng)式時(shí)間內(nèi)解決）在規(guī)劃、調(diào)度等應(yīng)用中得到廣泛使用。該論文中簡潔優(yōu)雅的問題描述為后續(xù)多個方向的研究提供了啟發(fā)，包括時(shí)間不確定性、偏好和其他擴(kuò)展問題。

論文內(nèi)容簡介

論文鏈接：http://ftp.cs.ucla.edu/pub/stat_ser/r113-L-reprint.pdf

這篇論文將基于網(wǎng)絡(luò)的約束滿足方法進(jìn)行擴(kuò)展，使其包含連續(xù)變量，從而為處理時(shí)間約束提供了框架。在這個叫做時(shí)間約束滿足問題（TCSP）的框架中，代表時(shí)間點(diǎn)和時(shí)間信息的變量由一組一元和二元約束進(jìn)行表示，每一個指定一組時(shí)間間隔。該框架的獨(dú)特特征在于允許處理度量信息，即評估不同事件之間的時(shí)間差。

該論文展示了一些算法，它們可用于執(zhí)行以下推理任務(wù)：找到給定事件發(fā)生的所有合理時(shí)間；找到兩個給定事件之間的所有可能關(guān)系；生成與給定信息一致的一個或多個場景。

該論文對簡單時(shí)間問題（STP）和通用時(shí)間問題進(jìn)行區(qū)分，前者對任意一對時(shí)間點(diǎn)至多認(rèn)可一個間隔約束（interval constraint）。該研究表明，包含 Vilain 和 Kautz 點(diǎn)代數(shù)主要部分的 STP 可以在多項(xiàng)式時(shí)間內(nèi)解決。對于通用 TCSP，該研究展示了一種執(zhí)行三個推理任務(wù)的分解機(jī)制，并提出了多種能夠改善效率的技術(shù)。此外，這篇論文還研究了路徑相容算法在預(yù)處理時(shí)間問題上的適用性，展示了其終止，限制了其復(fù)雜度。

研究貢獻(xiàn)

這篇論文提出了一種基于約束網(wǎng)絡(luò)形式的時(shí)間推理統(tǒng)一方法。使用約束網(wǎng)絡(luò)形式，該研究做出了以下幾點(diǎn)貢獻(xiàn)：

為相關(guān)的多種算法機(jī)制提供了形式化基礎(chǔ)，從而允許分析其復(fù)雜度和應(yīng)用范圍；

提供了一種成本較低的表示——minimal network，它可以編碼成對事件點(diǎn)之間的所有時(shí)間關(guān)系，包括時(shí)間差的絕對界限；

提出了一種基于給定約束，高效生成特定時(shí)間場景的機(jī)制。

示例詳解

作者在論文中給出了一個例子，示例中出現(xiàn)了多個事件和時(shí)間點(diǎn)，并利用這個示例介紹了該研究的主要思想。具體示例如下所示：

二元約束網(wǎng)絡(luò)（二元 TCSP）包括一組變量 X_1 ..... X_n，和一組一元和二元約束。這樣的網(wǎng)絡(luò)可被表示為一個有向約束圖。同理，示例 1.1 也可表示為有向約束圖，如下圖 1 所示：

該研究對基于約束的二元運(yùn)算進(jìn)行了定義：并集（union）、交集（intersection）和組合（composition）。

下圖 2 展示了交集和組合運(yùn)算：

當(dāng) TCSP 中所有約束指定一個間隔時(shí)，這是一個簡單時(shí)間問題（STP）。該研究將 STP 和有向邊緣權(quán)重圖（directed edge-weighted graph）聯(lián)系起來，這類圖叫做距離圖（distance graph）。

假設(shè)示例 1.1 中 John 用汽車，F(xiàn)red 用拼車，則我們可以得到一個 STP：

其距離圖如下圖 3 所示：

基于圖 3，我們可以得到對應(yīng)的 minimal network，如下所示：

現(xiàn)在回到通用 TCSP 問題，關(guān)于這類問題，有如下定理：

一種解決通用 TCSP 的直接方式是：將其分解為多個 STP，然后各個擊破，最后再把結(jié)果組合起來。

示例 1.1 的 minimal network 參見下表 3：

此外，該論文介紹了路徑相容算法及其弱化版本——有向路徑相容在 TCSP 框架中的適用性。

給出一個 TCSP T，及其相關(guān)的約束圖 G = (V, E) 和排序 d，通過 DPC 算法可以實(shí)現(xiàn)有向路徑相容。

在示例 1.1 中，當(dāng)排序 d = (0, 1, 2, 3, 4) 時(shí)應(yīng)用 DPC 算法，可以得到如下網(wǎng)絡(luò)：

Rina Dechte 與 Judea Pearl

AIJ 經(jīng)典論文獎旨在表彰 15 年前（或更早）對 AI 領(lǐng)域產(chǎn)生重大影響的杰出論文，此次獲獎的論文甚至發(fā)表于 30 年前。當(dāng)時(shí)，人工智能領(lǐng)域還沒有迎來第三次發(fā)展高潮，幾位獲獎?wù)咭彩钱?dāng)之無愧的領(lǐng)域先驅(qū)人物。

「Deep Learning」概念提出者 Rina Dechter

這篇論文的一作 Rina Dechter 曾是 Judea Pearl 指導(dǎo)的博士生，她 1973 年在希伯來大學(xué)取得數(shù)學(xué)與統(tǒng)計(jì)學(xué)士學(xué)位，1985 年在加州大學(xué)洛杉磯分校取得計(jì)算機(jī)科學(xué)博士學(xué)位。研究領(lǐng)域?yàn)槿斯ぶ悄苤械淖詣油评怼?/p>

在論文《Temporal Constraint Networks》發(fā)表的同年，Rina Dechter 獲得了美國國家科學(xué)基金會頒發(fā)的總統(tǒng)青年研究者獎。

1996 年，Rina Dechter 成為加州大學(xué)歐文分校（UC Irvine）的正式教授，并工作至今。Rina Dechter 于 1994 年當(dāng)選為 AAAI Fellow，后又于 2013 年當(dāng)選為 ACM Fellow。2011 年到 2018 年間，她擔(dān)任 AIJ 雜志的聯(lián)合主編。

值得一提的是，Rina Dechter 被認(rèn)為是提出術(shù)語「深度學(xué)習(xí)」的人。盡管多層感知器是在 1965 年發(fā)明的，1971 年也出現(xiàn)了一個 8 層神經(jīng)網(wǎng)絡(luò)，但「深度學(xué)習(xí)」一詞是 Rina Dechter 于 1986 年率先在論文中使用的。

Rina Dechter 在 1986 年的論文《LEARNING WHILE SEARCHING IN CONSTRAINT-SATISFACTION-PROBLEMS》中首次提到「deep learning」。

貝葉斯網(wǎng)絡(luò)之父、圖靈獎得主 Judea Pearl

比 Rina Dechter 更有聲望的，是她的導(dǎo)師 Judea Pearl。

提到 Judea Pearl，機(jī)器學(xué)習(xí)領(lǐng)域的讀者應(yīng)該不會陌生。他是美國計(jì)算機(jī)科學(xué)家和哲學(xué)家，以倡導(dǎo)人工智能的概率方法和貝葉斯網(wǎng)絡(luò)的發(fā)展而聞名，建立了基于結(jié)構(gòu)模型的因果和反事實(shí)推理理論。2011 年，Judea Pearl 獲得計(jì)算機(jī)科學(xué)最高獎項(xiàng)圖靈獎，獲獎理由是：「通過發(fā)展概率和因果推理的微積分對人工智能做出了重大貢獻(xiàn)」。

30 年前，人工智能研究的一個主要挑戰(zhàn)是對機(jī)器進(jìn)行編程，以便將潛在的原因與一系列可觀察到的情況聯(lián)系起來。Pearl 用一種叫做「貝葉斯網(wǎng)絡(luò)」的方案來解決這個問題。貝葉斯網(wǎng)絡(luò)可以讓機(jī)器回答這樣一個問題——給出一個從非洲回來的發(fā)燒且身體疼痛的病人，他 / 她最有可能患上的是瘧疾。2011 年，Pearl 獲得圖靈獎，這很大程度上要?dú)w功于貝葉斯網(wǎng)絡(luò)。

但在 Pearl 看來，人工智能領(lǐng)域已經(jīng)陷入了概率關(guān)聯(lián)（probabilistic association）的泥潭。近幾年，新聞頭條吹捧機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)的最新突破，比如計(jì)算機(jī)可以下圍棋和駕駛汽車。但 Pearl 對此感到膩味。在他看來，當(dāng)今人工智能領(lǐng)域的最新技術(shù)僅僅是上一代機(jī)器所做事情的強(qiáng)化版：在大量數(shù)據(jù)中找到隱藏的規(guī)律。他曾表示：「所有令人印象深刻的深度學(xué)習(xí)成果都只是曲線擬合?！?/p>

那么，怎樣才能推動 AI 社區(qū)解決這一問題呢？在中，Pearl 認(rèn)為，我們需要一場「因果革命」。研究者應(yīng)該考慮采用因果推斷模型，從因果而非單純的數(shù)據(jù)角度進(jìn)行研究。他認(rèn)為，我們在過去一段時(shí)間錯過了對因果推斷的研究機(jī)會，這原本是科學(xué)研究的核心：尋找變量的因果關(guān)系。

在很長一段時(shí)間里，統(tǒng)計(jì)機(jī)器學(xué)習(xí)主要關(guān)注對表征的擬合，尋找的是變量之間的相關(guān)性，而非潛在的因果性。這樣的認(rèn)識使科學(xué)研究停留在較淺的關(guān)聯(lián)層面，導(dǎo)致模型的魯棒性和可解釋性喪失，阻斷了進(jìn)一步探究干預(yù)變量以及反事實(shí)推斷（即假設(shè)某一變量完全相反而其他變量不變時(shí)，該變量對結(jié)果的影響）的能力。Pearl 認(rèn)為，智能的機(jī)器應(yīng)該能夠彼此溝通交流，通過提出反事實(shí)對話（如「你應(yīng)該怎樣做」）而作出更好的表現(xiàn)。

基于此，Pearl 和他的同事在 2018 年完成了著作《》。Pearl 在書中詳細(xì)地闡述自己在這一領(lǐng)域的研究成果，希望能夠促進(jìn)人們反思當(dāng)前的研究方向。