下載客戶端

登錄

30年前的熱門研究，今獲經典論文獎，貝葉斯網絡之父舊論文“考古”

2020-08-11 17:00

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

機器之心報道

編輯：魔王、蛋醬、張倩

一篇 30 年前的論文，因為一次獲獎，又重新出現在世人眼前。

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

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

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

這篇影響深遠的論文介紹了用于定量時間推理的時間約束滿足問題（TCSP）。TCSP 及其特例——簡單時間問題（STP，可在多項式時間內解決）在規劃、調度等應用中得到廣泛使用。該論文中簡潔優雅的問題描述為后續多個方向的研究提供了啟發，包括時間不確定性、偏好和其他擴展問題。

論文內容簡介

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

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

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

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

研究貢獻

這篇論文提出了一種基于約束網絡形式的時間推理統一方法。使用約束網絡形式，該研究做出了以下幾點貢獻：

為相關的多種算法機制提供了形式化基礎，從而允許分析其復雜度和應用范圍；

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

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

示例詳解

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

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

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

下圖 2 展示了交集和組合運算：

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

假設示例 1.1 中 John 用汽車，Fred 用拼車，則我們可以得到一個 STP：

其距離圖如下圖 3 所示：

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

現在回到通用 TCSP 問題，關于這類問題，有如下定理：

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

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

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

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

在示例 1.1 中，當排序 d = (0, 1, 2, 3, 4) 時應用 DPC 算法，可以得到如下網絡：

Rina Dechte 與 Judea Pearl

AIJ 經典論文獎旨在表彰 15 年前（或更早）對 AI 領域產生重大影響的杰出論文，此次獲獎的論文甚至發表于 30 年前。當時，人工智能領域還沒有迎來第三次發展高潮，幾位獲獎者也是當之無愧的領域先驅人物。

「Deep Learning」概念提出者 Rina Dechter

這篇論文的一作 Rina Dechter 曾是 Judea Pearl 指導的博士生，她 1973 年在希伯來大學取得數學與統計學士學位，1985 年在加州大學洛杉磯分校取得計算機科學博士學位。研究領域為人工智能中的自動推理。

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

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

值得一提的是，Rina Dechter 被認為是提出術語「深度學習」的人。盡管多層感知器是在 1965 年發明的，1971 年也出現了一個 8 層神經網絡，但「深度學習」一詞是 Rina Dechter 于 1986 年率先在論文中使用的。

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

貝葉斯網絡之父、圖靈獎得主 Judea Pearl

比 Rina Dechter 更有聲望的，是她的導師 Judea Pearl。

提到 Judea Pearl，機器學習領域的讀者應該不會陌生。他是美國計算機科學家和哲學家，以倡導人工智能的概率方法和貝葉斯網絡的發展而聞名，建立了基于結構模型的因果和反事實推理理論。2011 年，Judea Pearl 獲得計算機科學最高獎項圖靈獎，獲獎理由是：「通過發展概率和因果推理的微積分對人工智能做出了重大貢獻」。

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

但在 Pearl 看來，人工智能領域已經陷入了概率關聯（probabilistic association）的泥潭。近幾年，新聞頭條吹捧機器學習和神經網絡的最新突破，比如計算機可以下圍棋和駕駛汽車。但 Pearl 對此感到膩味。在他看來，當今人工智能領域的最新技術僅僅是上一代機器所做事情的強化版：在大量數據中找到隱藏的規律。他曾表示：「所有令人印象深刻的深度學習成果都只是曲線擬合。」

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

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

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