走過近30年，這個(gè)用邏輯程序表示數(shù)據(jù)的ML算法值得深入了解

歸納邏輯程序設(shè)計(jì)已「走過」近 30 年的歷程?；仡欉@ 30 年來的發(fā)展軌跡，似乎很少有人提起這種算法，我們用到更多是深度學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)等熱門算法。其實(shí)作為一門相對(duì)冷門的算法，歸納邏輯程序設(shè)計(jì)卻在某些方面優(yōu)于 ML。在這種算法即將迎來 30 周年之際，來自牛津大學(xué)與魯汶大學(xué)的研究者用一篇超長(zhǎng)論文詳細(xì)解讀了歸納邏輯程序設(shè)計(jì)的相關(guān)內(nèi)容。

歸納邏輯程序設(shè)計(jì)（Inductive Logic Programming, ILP）是機(jī)器學(xué)習(xí)的一種形式。與基于統(tǒng)計(jì)的機(jī)器學(xué)習(xí)類似，ILP 也是需要給定一些例子作為訓(xùn)練樣本。所不同的是，基于統(tǒng)計(jì)的機(jī)器學(xué)習(xí)輸出的是一個(gè)統(tǒng)計(jì)學(xué)的分類模型，而 ILP 輸出的是一個(gè)邏輯程序。

近日，來自牛津大學(xué)與魯汶大學(xué)的研究者發(fā)表了一篇論文，該論文介紹了必要的邏輯符號(hào)和主要的 ILP 學(xué)習(xí)設(shè)置。此外還介紹了 ILP 系統(tǒng)的主要組成部分。他們?cè)趲追N維度上比較了幾個(gè) ILP 系統(tǒng)，并詳細(xì)介紹了 Aleph、TILDE、ASPAL 和 Metagol 等四個(gè)系統(tǒng)。最后，研究者還將 ILP 與其他形式的機(jī)器學(xué)習(xí)進(jìn)行對(duì)比，并總結(jié)了 ILP 當(dāng)前的局限性以及未來研究的新方向。

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

因?yàn)樵撜撐妮^長(zhǎng)且還在完善的過程中，本文就先摘取了其中的核心內(nèi)容進(jìn)行介紹。

我們首先來了解下論文的核心結(jié)構(gòu)，該論文主要由以下 9 個(gè)部分組成：

·  ILP 發(fā)展史（第 1 節(jié)）；

·  描述 ILP 必要的邏輯程序設(shè)計(jì)符號(hào)（第 2 節(jié)）；

·  定義了標(biāo)準(zhǔn)的 ILP 學(xué)習(xí)設(shè)置（從蘊(yùn)含中學(xué)習(xí)、從解釋中學(xué)習(xí)和從滿足性中學(xué)習(xí)）（第 3 節(jié)）；

·  描述構(gòu)建 ILP 系統(tǒng)所需的基本假設(shè)（第 4 節(jié)）；

·  比較了多個(gè) ILP 系統(tǒng)并描述了它們所支持的特征（第 5 節(jié)）；

·  描述了四個(gè) ILP 系統(tǒng)（Aleph、TILDE、ASPAL、和 Metagol）（第 6 節(jié)）；

·  描述了 ILP 應(yīng)用層面（第 7 節(jié)）；

·  將 ILP 與其他形式的 ML 進(jìn)行比較（第 8 節(jié)）；

·  概述未來的研究方向（第 9 節(jié)）。

以下內(nèi)容將重點(diǎn)介紹 ILP 的基礎(chǔ)知識(shí)、選擇 ILP 的理由以及 ILP 的工作方式。

ILP 簡(jiǎn)介

人類智慧的一項(xiàng)非凡成就是擁有學(xué)習(xí)新知識(shí)的能力。歸納法就是一種主要的學(xué)習(xí)類型：從特定觀察（示例）形成通用規(guī)則（假設(shè)）的過程。例如，假設(shè)你從一個(gè)袋子中抽出 10 個(gè)紅色的球，那么你可能會(huì)得出一個(gè)假設(shè)（一個(gè)規(guī)則），即袋子中的所有球都是紅色的。得出此假設(shè)后，你就可以預(yù)測(cè)出袋子中下一個(gè)球的顏色。

機(jī)器學(xué)習(xí)（ML）的目標(biāo)是自動(dòng)化歸納過程。換句話說，機(jī)器學(xué)習(xí)的目標(biāo)是產(chǎn)生一個(gè)能夠泛化訓(xùn)練示例（觀察）的假設(shè)（也稱為模型）。例如，給定帶有標(biāo)簽的貓和狗的圖像，目標(biāo)則是得出一個(gè)預(yù)測(cè)未標(biāo)記圖像是貓還是狗的假設(shè)。

ILP 是 ML 的一種形式。與其他形式的 ML 一樣，ILP 的目標(biāo)是得出一個(gè)可以泛化訓(xùn)練示例的假設(shè)。雖然大多數(shù)形式的 ML 使用表格來表示數(shù)據(jù)（示例和假設(shè)），但 ILP 使用邏輯程序（邏輯規(guī)則集）來表示數(shù)據(jù)。

下表 1 說明使用 ML 與 ILP 的區(qū)別所在：

大多數(shù)形式的 ML 采用標(biāo)準(zhǔn)表格表示來描述 ML 任務(wù)。

ILP 使用邏輯程序來表示數(shù)據(jù)，由三個(gè)集合組成 (B，E+， E-)，其中 B 集合表示背景知識(shí) (BK)，其與特征類似，但可以包含與示例間接關(guān)聯(lián)的關(guān)系和信息；E + 和 E - 分別表示正面例子與負(fù)面例子。

為什么選擇 ILP

ILP 與大多數(shù) ML 方法的根本不同在于，大多數(shù)機(jī)器學(xué)習(xí)方法，如支持向量機(jī)和神經(jīng)網(wǎng)絡(luò)，都依賴于統(tǒng)計(jì)推理。相比之下，ILP 依賴邏輯推理。下表 2 展示了 ILP 和統(tǒng)計(jì) ML 方法之間的不同之處：

由上表可以得出，ML 與 ILP 的主要區(qū)別表現(xiàn)在用例、數(shù)據(jù)、假設(shè)、泛化、可解釋性和知識(shí)遷移 6 個(gè)方面：

·  用例方面：眾所周知，許多形式的 ML 都非常需要數(shù)據(jù)。相比之下，ILP 系統(tǒng)可以基于少量示例進(jìn)行歸納，通常是從單個(gè)示例就能歸納；

·  數(shù)據(jù)方面：與大多數(shù) ML 形式相反，ILP 使用表示為邏輯程序的 BK 進(jìn)行學(xué)習(xí)。使用邏輯程序表示數(shù)據(jù)可以使 ILP 學(xué)習(xí)復(fù)雜的關(guān)系信息，并可以輕松集成專家知識(shí)；

·  假設(shè)：使用邏輯程序表示假設(shè)有很多好處。因?yàn)樗鼈兣c關(guān)系數(shù)據(jù)庫密切相關(guān)，所以邏輯程序自然支持關(guān)系數(shù)據(jù)，例如圖表；

·  泛化能力：ILP 得出的歸納假設(shè)超出了訓(xùn)練數(shù)據(jù)的范圍。相比之下，許多其他形式的 ML 因無法從少量訓(xùn)練示例中進(jìn)行歸納而名聲不佳（尤其是深度學(xué)習(xí)）；

·  可解釋性：由于邏輯與自然語言的相似性，因此人類可以輕松閱讀邏輯程序，這對(duì)于可解釋的 AI 和超強(qiáng)的 ML 至關(guān)重要；

·  知識(shí)遷移：大多數(shù)機(jī)器學(xué)習(xí)算法都是單任務(wù)學(xué)習(xí)，無法重用學(xué)到的知識(shí)。相比之下，由于 ILP 具有符號(hào)表示，它自然支持終身學(xué)習(xí)和遷移學(xué)習(xí)，對(duì)于 AI 來說至關(guān)重要。

ILP 工作方式

ILP 問題通常由三個(gè)集合構(gòu)成：B（背景知識(shí)）、E+（正面例子）和 E-（負(fù)面例子）。ILP 問題是誘導(dǎo)一個(gè)假設(shè) H，其中用 B 來解釋 E + 和 E-。

ILP 主要有三種學(xué)習(xí)設(shè)置：從蘊(yùn)含中學(xué)習(xí)（learning from entailment, LFE）、從解釋行中學(xué)習(xí)（learning from interpretation, LFI）和從可滿足性中學(xué)習(xí)（learning from satisfiability, LFS）。LFE 和 LFI 是目前最流行的學(xué)習(xí)設(shè)置，所以這里著重討論這兩種。

從蘊(yùn)含中學(xué)習(xí)（LFE）

定義 1：對(duì)于給定一個(gè)元組 (B， E + , E ? )：

LFE 的目標(biāo)是返回一個(gè)假設(shè) H，使得：

可以從以下示例中獲得直觀感受，考慮從蘊(yùn)含元組學(xué)習(xí)：

同時(shí)假定存在假設(shè)空間：

那么可以考慮 ILP 系統(tǒng)應(yīng)該返回哪些假設(shè)：

根據(jù)定義 1，一個(gè)假設(shè)必須包含每一個(gè)正面示例（完整的）而不需要負(fù)面示例（一致的）。然而，訓(xùn)練示例往往是混雜的，所以很難找到一個(gè)既完整又一致的假設(shè)。因此，大多數(shù)方法都放寬了這一定義，并試圖找到一個(gè)包含盡可能多的正面示例和盡可能少的負(fù)面示例的假設(shè)。

從解釋中學(xué)習(xí)（LFI）

第二受歡迎的學(xué)習(xí)設(shè)置是 LFI。

定義 2（從解釋中學(xué)習(xí)）：給定元組（B，E+，E?），其中：

LFI 的目標(biāo)是返回一個(gè)假設(shè) H，使得：

示例 2，為了說明 LFI，該論文重用 Law（2018）的示例。考慮以下輸入元組：

同時(shí)假定存在有假設(shè)空間：

要找到一個(gè)解決 LFI 問題（定義 2）的假設(shè) H，必須首先對(duì)每個(gè)示例計(jì)算 B 的最小模型，即：

問題是要找到一個(gè)假設(shè) H，使 M_1 和 M_1 都是 H 的模型，而 M_3 不是。假設(shè) h_1 不是解，因?yàn)?M_1 不是 B∪h_1 的模型；假設(shè) h_1 不是解，因?yàn)?M_1 不是 B∪h_2 的模型；假設(shè) h_3 是一個(gè)解，因?yàn)?M_1 和 M_2 都是 B∪h_3 的模型而 M_# 不是 B∪h_3 的模型。

總體而言，ILP 相關(guān)設(shè)計(jì)架構(gòu)如下：正面示例 + 負(fù)面示例 + 背景知識(shí)?假設(shè)。ILP 所學(xué)模型基于一階邏輯符號(hào)規(guī)則，而非難以理解的黑箱模型。學(xué)習(xí)得到的模型可基于個(gè)體間的關(guān)系建模，而非只對(duì)個(gè)體的標(biāo)記進(jìn)行預(yù)測(cè)。如果你想了解更多細(xì)節(jié)內(nèi)容，請(qǐng)參考該論文。

參考鏈接：https://hyper.ai/wiki/4863