https://arxiv.org/abs/2506.06739

親愛的，我縮小了假設(shè)空間（通過邏輯預(yù)處理）

Honey, I shrunk the hypothesis space (through logical preprocessing)

歸納邏輯編程 （Inductive Logic Programming, ILP）是一種形式化的機(jī)器學(xué)習(xí)方法。其目標(biāo)是在假設(shè)空間中搜索一個能夠概括訓(xùn)練樣例和背景知識的假設(shè)。我們提出了一種在ILP系統(tǒng)搜索之前先縮小假設(shè)空間的方法。我們的方法利用背景知識來找出那些無論訓(xùn)練樣例如何都不可能出現(xiàn)在最優(yōu)假設(shè)中的規(guī)則。例如，我們的方法可以發(fā)現(xiàn)諸如“偶數(shù)不可能是奇數(shù)”以及“大于2的質(zhì)數(shù)一定是奇數(shù)”這樣的關(guān)系。然后從假設(shè)空間中移除違反這些規(guī)則的候選規(guī)則。

我們使用回答集編程 （Answer Set Programming, ASP）實現(xiàn)該方法，并將其用于縮減基于約束的ILP系統(tǒng)的假設(shè)空間。我們在多個領(lǐng)域進(jìn)行了實驗，包括視覺推理和游戲?qū)模Y(jié)果表明我們的方法可以顯著減少學(xué)習(xí)時間，同時保持預(yù)測準(zhǔn)確性。例如，僅用10秒的預(yù)處理時間，我們的方法就能將學(xué)習(xí)時間從超過10小時縮短到僅需2秒。

1 引言

歸納邏輯編程（ILP）[9, 51] 是一種邏輯機(jī)器學(xué)習(xí)的形式。其目標(biāo)是在假設(shè)空間中尋找一個能夠概括訓(xùn)練樣例和背景知識（BK）的假設(shè)。ILP 的顯著特點是使用邏輯規(guī)則來表示假設(shè)、樣例和背景知識。

與所有形式的機(jī)器學(xué)習(xí)一樣，ILP面臨的一個主要挑戰(zhàn)是如何在巨大的假設(shè)空間中進(jìn)行高效搜索。為了說明這一挑戰(zhàn)，考慮這樣一個學(xué)習(xí)任務(wù)：我們需要對一個任意關(guān)系 h 的樣例進(jìn)行泛化。假設(shè)我們可以使用一元關(guān)系 odd（奇數(shù)）、even（偶數(shù)）和 int（整數(shù)），以及二元關(guān)系 head（頭）、tail（尾）、len（長度）、lt（小于）和 succ（后繼）來構(gòu)建規(guī)則。那么規(guī)則空間（即所有可能規(guī)則的集合）中將包含如下規(guī)則：

假設(shè)空間是規(guī)則空間的冪集，因此它極其龐大。例如，在這個簡單的場景中，如果我們允許每條規(guī)則最多包含四個文字（literal）和四個變量，則可能存在超過3,183,545條不同的規(guī)則，從而產(chǎn)生 2^3,183,545 個可能的假設(shè)。

大多數(shù)研究通過開發(fā)高效的搜索技術(shù)來應(yīng)對這一挑戰(zhàn) [1, 3, 13, 52, 53, 57, 64, 70]。換句話說，大多數(shù)研究都假定假設(shè)空間是固定的，并專注于如何高效地在該空間中進(jìn)行搜索。

我們并未設(shè)計新的搜索算法，而是提出了一種方法：在將假設(shè)空間交給ILP系統(tǒng)之前先對其進(jìn)行縮減。其核心思想是利用給定的背景知識（BK），找出那些無論我們要學(xué)習(xí)什么概念都不可能出現(xiàn)在最優(yōu)假設(shè)中的規(guī)則，我們將這些規(guī)則稱為無意義規(guī)則 （pointless rules）。一個最優(yōu)假設(shè)是在訓(xùn)練數(shù)據(jù)上最小化某個代價函數(shù)的結(jié)果，例如找到能夠蘊(yùn)含所有正例而不蘊(yùn)含任何負(fù)例的最小假設(shè) [53]，或找到具有最小描述長度的假設(shè) [36]。

為了說明我們的思路，請考慮前面提到的場景。假設(shè)我們擁有的背景知識僅包含以下事實：

我們利用這些背景知識（BK）識別出四種類型的無意義規(guī)則：不可滿足規(guī)則 （unsatisfiable）、蘊(yùn)含可約規(guī)則（implication reducible）、召回可約規(guī)則 （recall reducible）和單例可約規(guī)則 （singleton reducible）。

不可滿足規(guī)則 是指無論我們要學(xué)習(xí)什么概念，它都不可能為真，也就是說，不論具體的訓(xùn)練樣例如何，它都無法被滿足。例如，在給定此背景知識的情況下，如果我們采用封閉世界假設(shè) [60]，由于不存在形式為 tail(A,A) 的事實，我們可以推斷出 tail/2 是一個反自反關(guān)系 （irreflexive），因此可以從規(guī)則空間中移除規(guī)則 r? 和 r?，因為它們的條件體（body）是不可滿足的。此時的規(guī)則空間變?yōu)椋?/p>

同樣地，我們可以推斷出 tail/2 是非對稱的 （asymmetric）和反傳遞的 （antitransitive），因此可以從規(guī)則空間中移除規(guī)則 r? 和 r?。此時的規(guī)則空間變?yōu)椋?/p>

最后，單例可約規(guī)則 （singleton reducible rule）是指包含一個始終為真 的文字（literal）的規(guī)則。例如，如果變量 始終是一個列表（list），那么規(guī)則 r? 中的文字 len(A,B) 就總是成立，因為每個列表都有長度，而變量 沒有受到任何限制。換句話說，由于變量 在這條規(guī)則中只出現(xiàn)一次，因此文字 len(A,B) 是冗余的，因為它沒有任何區(qū)分能力（no discriminatory power）。因此，我們可以從假設(shè)空間中移除規(guī)則 r?。此時的規(guī)則空間已為空。

正如我們在本文中所展示的那樣，我們可以自動識別并移除假設(shè)空間中所有四種類型的無意義規(guī)則，同時不會刪除最優(yōu)假設(shè)。如上述場景所示，在尚未查看任何訓(xùn)練樣例之前，移除這些無意義規(guī)則就可以大幅縮減假設(shè)空間。換句話說，我們的方法可以在搜索假設(shè)之前就先確定哪些地方是無需搜索的 。

為了識別不可滿足規(guī)則 和蘊(yùn)含可約規(guī)則 ，我們使用了回答集編程 （Answer Set Programming, ASP）[27]。具體來說，我們構(gòu)造一些小的規(guī)則，并利用 ASP 來判斷這些規(guī)則是否相對于背景知識（BK）是不可滿足的或蘊(yùn)含可約的。我們重復(fù)這一過程，直到達(dá)到用戶設(shè)定的超時時間為止。此階段的輸出是一組被判定為不可滿足或蘊(yùn)含可約的規(guī)則。

為了識別召回可約規(guī)則 （recall reducible rules），我們采用了一種類似于 Savnik 和 Flach [62] 提出的方法（用于在數(shù)據(jù)庫中發(fā)現(xiàn)函數(shù)依賴）以及 Struyf 和 Blockeel [66] 提出的方法（用于構(gòu)建高效查詢）的自底向上方式 。對于每一個背景關(guān)系及其參數(shù)的任意子序列，我們計算其可能產(chǎn)生的最大答案替換數(shù)量（answer substitutions）。例如，在上面給出的 BK 中，succ/2 最多只有三個實例化情況（ground instances），因此它最多有三個答案替換。同樣地，對于文字 succ(A,B)，如果變量 是已知的（ground），那么變量 最多只有一個答案替換。

此階段的輸出是一組被判定為召回可約的規(guī)則。

為了識別單例可約規(guī)則 ，我們使用 ASP 來判斷一個關(guān)系是部分函數(shù) （partial）還是全函數(shù) （total），并利用這些信息來推導(dǎo)出單例可約規(guī)則。此階段的輸出是一組被判定為單例可約的規(guī)則。

我們將所有這些無意義規(guī)則集合起來，用于縮減一個基于約束的 ILP 系統(tǒng) [13, 36] 的假設(shè)空間。例如，如果我們發(fā)現(xiàn) even（偶數(shù)）和 odd（奇數(shù)）是互斥的，我們會構(gòu)建相應(yīng)的約束，以移除那些在規(guī)則體中同時包含 odd(A) 和 even(A) 的規(guī)則。同樣地，如果我們發(fā)現(xiàn)文字 succ(B,C)、succ(C,D) 和 lt(B,D) 是蘊(yùn)含可約的，那么我們的約束將移除包含這些文字的規(guī)則。這些約束會從假設(shè)空間中移除非最優(yōu)的假設(shè)，從而確保系統(tǒng)在搜索假設(shè)時永遠(yuǎn)不會考慮它們。

我們的假設(shè)空間縮減方法具有諸多優(yōu)勢：

• 該方法與具體的 ILP 系統(tǒng)無關(guān)，可以被任何 ILP 系統(tǒng)所使用。例如，Aleph 的規(guī)則剪枝機(jī)制 [64] 也可以利用這些約束。

• 該方法是一個獨(dú)立的預(yù)處理步驟，不依賴于特定的學(xué)習(xí)算法或?qū)W習(xí)任務(wù)。

• 因此，我們可以將該方法作為預(yù)處理步驟，應(yīng)用于多個任務(wù)共享的一組背景知識（BK）之上。

其主要好處是顯著減少學(xué)習(xí)時間，而不會降低預(yù)測準(zhǔn)確性 。例如，在僅給予10秒的預(yù)處理時間的情況下，我們的方法可以將學(xué)習(xí)時間從超過10小時減少到僅僅幾秒鐘。

新穎性和貢獻(xiàn)

本文的核心創(chuàng)新在于提出了一種新的方法：作為一種預(yù)處理步驟，通過自動識別無意義規(guī)則，來自動縮減 ILP 系統(tǒng)的假設(shè)空間 。這種方法的影響是大幅減少學(xué)習(xí)時間 ，并在多個不同領(lǐng)域得到了驗證。例如，我們的方法可以將學(xué)習(xí)時間減少高達(dá)99%。

本文在我們早期工作 [12] 的基礎(chǔ)上進(jìn)行了實質(zhì)性擴(kuò)展。在初步工作中，我們首次提出了利用背景知識（BK）發(fā)現(xiàn)對假設(shè)的約束的想法，例如“一個數(shù)不能同時是偶數(shù)和奇數(shù)”。但當(dāng)時的工作依賴于人工提供的預(yù)定義屬性集合，如反傳遞性（antitransitivity）和非自反性（irreflexivity）。而在本文中，我們將這一思想推廣至四種任意類型的無意義規(guī)則，其中兩種（蘊(yùn)含可約和單例可約）是全新的概念，并且本文幾乎所有的內(nèi)容都是新增的。

總體而言，我們的主要貢獻(xiàn)包括：

• 提出假設(shè)空間縮減問題

  ：其目標(biāo)是找到原假設(shè)空間的一個子集，該子集仍然包含所有最優(yōu)假設(shè)。

• 定義無意義規(guī)則

  ：包括不可滿足規(guī)則、蘊(yùn)含可約規(guī)則、召回可約規(guī)則和單例可約規(guī)則。我們證明了包含無意義規(guī)則的假設(shè)不可能是最優(yōu)的（命題 2、4、6 和 9）。

• 描述一種假設(shè)空間縮減方法

  ，并實現(xiàn)為一個名為 shrinker 的系統(tǒng)。我們證明了 shrinker 只會從假設(shè)空間中移除非最優(yōu)假設(shè)（命題 10）。

• 使用 shrinker 啟動一個基于約束的 ILP 系統(tǒng)

  [13, 36]。

• 在多個領(lǐng)域進(jìn)行實驗驗證

  ：結(jié)果表明，在僅給予10秒預(yù)處理時間的情況下，shrinker 能夠顯著縮短 ILP 的學(xué)習(xí)時間，有時甚至可以從超過10小時縮短到僅需2秒。

程序綜合 （Program Synthesis）
歸納邏輯編程（ILP）是一種程序綜合的形式，其目標(biāo)是從示例中自動生成計算機(jī)程序。Gulwani 等人 [32] 認(rèn)為這是人工智能的“圣杯”問題，引起了廣泛的研究興趣 [21, 22]。雖然我們的方法可以應(yīng)用于任何形式的程序綜合，但它特別適合 ILP，因為 ILP 的邏輯表示形式天然地通過邏輯約束支持聲明性知識。

規(guī)則歸納 （Rule Induction）
ILP 方法從數(shù)據(jù)中歸納出規(guī)則，這與規(guī)則學(xué)習(xí)方法 [25] 類似。將 ILP 方法與最近的規(guī)則挖掘技術(shù)（如 AMIE+ [26] 和 RDFRules [69]）進(jìn)行比較是困難的。大多數(shù)規(guī)則挖掘方法僅限于一元和二元關(guān)系，并且需要以事實作為輸入。它們通常還在開放世界假設(shè) （open-world assumption）下運(yùn)行。相比之下，ILP 通常在封閉世界假設(shè) （closed-world assumption）下運(yùn)行，支持任意元數(shù)（arity）的關(guān)系，并且可以從確定性程序（definite programs）作為背景知識中進(jìn)行學(xué)習(xí)。

約束

許多系統(tǒng)使用約束來限制假設(shè)空間 [1, 7, 13, 37, 40, 42, 47, 63]。例如，Apperception 引擎 [23] 包含幾個內(nèi)置約束，如統(tǒng)一性條件（unity condition），要求對象必須通過二元關(guān)系鏈連接起來。相比之下，我們是在搜索假設(shè)之前自動發(fā)現(xiàn)約束條件 。

用戶可以向許多系統(tǒng)提供約束。例如，如果用戶知道兩個文字是不可滿足的，他們可以將這些信息作為元約束提供給 ilasp，或通過用戶定義的剪枝條件提供給 Aleph。但在這些情況下，用戶是將約束作為輸入提供給系統(tǒng)的。相比之下，我們的方法無需用戶干預(yù)即可自動發(fā)現(xiàn)此類約束 。

預(yù)處理

我們方法的一個關(guān)鍵特征是：在將假設(shè)空間交給 ILP 系統(tǒng)進(jìn)行搜索之前，我們就對其進(jìn)行縮減。因此，我們的方法可以被視為一個預(yù)處理步驟 ，這在人工智能領(lǐng)域已被廣泛研究，尤其是在縮小 SAT 實例規(guī)模方面 [20]。

ILP 中也有其他預(yù)處理工作的研究，特別是從 BK 中推導(dǎo)類型 [49, 54]。例如，McCreath 和 Sharma [49] 自動從 BK 中推導(dǎo)模式聲明（mode declarations），比如參數(shù)的類型以及哪些參數(shù)應(yīng)為 ground。我們不推導(dǎo)類型，而是從假設(shè)空間中移除不可滿足、蘊(yùn)含可約、召回可約和單例可約的規(guī)則。

此外，由于我們使用的是約束，我們能推理一些模式無法表達(dá)的性質(zhì)，如反傳遞性、互斥性和蘊(yùn)含關(guān)系。Bridewell 和 Todorovski [5] 在多任務(wù)設(shè)置下學(xué)習(xí)假設(shè)空間上的結(jié)構(gòu)約束。相比之下，我們在解決任何任務(wù)之前就發(fā)現(xiàn)了偏置。

其他 ILP 中的預(yù)處理方法側(cè)重于減小 BK 的規(guī)模 [18, 19] 或謂詞發(fā)明 [8, 35]。相比之下，我們是在 BK 中發(fā)現(xiàn)約束，以縮減假設(shè)空間。

作為一種預(yù)處理步驟，Struyf 和 Blockeel [66] 計算了給定背景關(guān)系的召回率，以對規(guī)則中的文字進(jìn)行排序，從而減少檢查規(guī)則與樣例和 BK 是否匹配所需的時間。我們使用了類似的算法，但不是對規(guī)則中的文字排序，而是利用召回率定義召回可約規(guī)則（Definition 11），并據(jù)此構(gòu)建約束，從而縮減假設(shè)空間。

人工智能中的冗余

Plotkin [55] 使用蘊(yùn)含 （subsumption）來判斷一個文字在一階子句 中是否是冗余的。
Joyner [41] 研究了同樣的問題，他稱之為子句壓縮 （clause condensation），其中子句 C的一個壓縮是指其最小基數(shù)的子集 C′?C，使得 C′?C。
Gottlob 和 Gottlob 與 Fermüller [31] 改進(jìn)了 Joyner 的算法，并證明了判斷一個子句是否已壓縮的問題是 coNP-完全 的。

檢測和消除冗余在計算機(jī)科學(xué)的許多領(lǐng)域都非常有用，并受到了定理證明社區(qū)的廣泛關(guān)注 [38, 43, 67]。
在 SAT 求解器社區(qū)中，諸如阻塞子句消去 （blocked clause elimination）[45] 等冗余消除技術(shù)在現(xiàn)代求解器中起著關(guān)鍵作用。
這些冗余消除方法的目標(biāo)與我們論文的目標(biāo)類似：安全地識別出推導(dǎo)無關(guān)的輸入 ，即 SAT 輸入中包含的文字總是歸結(jié)為重言式的子句。

3 問題設(shè)定

在本節(jié)中，我們將定義本文中使用的符號，簡要介紹 ILP，然后定義假設(shè)空間縮減問題，并定義四種類型的“無意義規(guī)則”——我們可以在不移除最優(yōu)假設(shè)的前提下將它們從假設(shè)空間中刪除。

3.1 預(yù)備知識

3.2 歸納邏輯編程（Inductive Logic Programming）

我們將我們的方法建立在 ILP 的“從蘊(yùn)含中學(xué)習(xí)”（learning from entailment）設(shè)定 [17] 上。我們定義一個 ILP 輸入如下:

我們將背景知識限制為 Datalog 程序。在本文其余部分中，我們假設(shè)假設(shè)中的規(guī)則的頭部文字不會出現(xiàn)在背景知識中規(guī)則的頭部。

我們定義一個代價函數(shù)如下：

3.3 假設(shè)空間縮減

我們的目標(biāo)是在不移除最優(yōu)假設(shè) 的前提下縮減假設(shè)空間：

定義 7（假設(shè)空間縮減問題）

給定一個 ILP 輸入 (E,B,H)，假設(shè)空間縮減問題的目標(biāo)是找到一個子集 H′?H，使得如果 h∈H是一個最優(yōu)假設(shè)，則 h∈H′。

在本文中，我們通過使用背景知識（BK）來識別那些不可能出現(xiàn)在最優(yōu)假設(shè)中的規(guī)則，從而縮減假設(shè)空間。我們考慮四種類型的規(guī)則：

• 不可滿足規(guī)則

  （unsatisfiable）

• 蘊(yùn)含可約規(guī)則

  （implication reducible）

• 召回可約規(guī)則

  （recall reducible）

• 單例可約規(guī)則

  （singleton reducible）

下面我們將依次描述這四種規(guī)則。

3.4 不可滿足規(guī)則

一個不可滿足規(guī)則 是指其體部（body）在給定背景知識（BK）的情況下永遠(yuǎn)無法為真 的規(guī)則。例如，考慮以下規(guī)則：

假設(shè) odd 和 even 這兩個關(guān)系是互斥的 ，那么這條規(guī)則是不可滿足的 ，因為它的體部（body）是不可滿足的。

作為第二個例子，考慮以下規(guī)則：

假設(shè)我們采用 succ/2 關(guān)系的標(biāo)準(zhǔn)定義，那么這條規(guī)則是不可滿足的，因為 succ/2 是反傳遞的（antitransitive）。

我們定義不可滿足規(guī)則如下：

定義 8（不可滿足規(guī)則）

設(shè) B為背景知識（BK），r是一條體部為 b的規(guī)則，并且 B∪{←b}沒有模型 （即不一致）。那么稱規(guī)則 r是不可滿足的 。

我們證明：一個不可滿足規(guī)則的特化規(guī)則 也是不可滿足的：

命題 1（特化的不可滿足性）

3.5 蘊(yùn)含可約規(guī)則

一個蘊(yùn)含可約規(guī)則 是指其體部中存在某個文字被其他體部文字所蘊(yùn)含。例如，考慮以下規(guī)則：

一個蘊(yùn)含可約規(guī)則的某些特化形式也是蘊(yùn)含可約的：

3.6 召回可約規(guī)則

一個召回可約規(guī)則 （recall reducible rule）包含一個由背景知識（BK）中可推導(dǎo)出的某個文字的實例數(shù)量 所決定的冗余文字 [9]。例如，考慮以下規(guī)則：

這條規(guī)則包含了一個冗余的文字（succ(A,B) 或 succ(A,C)），因為 succ/2 的第二個參數(shù)在函數(shù)上依賴于第一個參數(shù)。換句話說，如果 succ(A,B) 和 succ(A,C) 都為真，則必有 B = C。

作為第二個例子，考慮以下規(guī)則：

這條規(guī)則包含了一個冗余的文字（add(A,B,C) 或 add(A,B,D)），因為 add/3 的第三個參數(shù)在函數(shù)上依賴于前兩個參數(shù)。換句話說，如果 add(A,B,C) 和 add(A,B,D) 都為真，則必有 C = D。

作為第三個例子，考慮以下規(guī)則：

下面我們展示召回可約性如何應(yīng)用于一條規(guī)則：

3.7 單例可約規(guī)則

一個單例可約規(guī)則 是指其體部中包含一個始終為真 的文字。例如，考慮以下規(guī)則：

4 shrinker

前一節(jié)概述了我們可以從背景知識（BK）中推導(dǎo)出的四種類型的無意義規(guī)則。現(xiàn)在我們介紹 shrinker ，它是一個能夠自動識別這些無意義規(guī)則并將其從假設(shè)空間中移除的系統(tǒng)。

算法1 展示了該方法的高層算法。該算法將 BK 作為 Datalog 程序的形式輸入。為簡化起見，在本節(jié)其余部分中，我們假設(shè) BK 已被實例化為一組事實（facts）[39]。

shrinker 包含三個組件：

1. 第一個組件用于找出 不可滿足規(guī)則 和 蘊(yùn)含可約規(guī)則 （第3行）；

2. 第二個組件用于找出 召回可約規(guī)則 （第4行）；

3. 第三個組件用于找出 單例可約規(guī)則 （第5行）。

我們將依次描述這三個組件。然后，我們將說明 shrinker 如何利用這些無意義規(guī)則來縮減基于約束的 ILP 系統(tǒng)的假設(shè)空間。

4.1 尋找不可滿足規(guī)則與蘊(yùn)含可約規(guī)則

為了識別不可滿足規(guī)則 和蘊(yùn)含可約規(guī)則 ，shrinker 構(gòu)建一些小型的規(guī)則模板 （rule templates），并利用背景知識（BK）來檢查這些模板的實例是否是不可滿足的或蘊(yùn)含可約的。

一個模板 是一組二階文字 （second-order literals）。
例如，集合 {P(A,B), Q(B,A)} 就是一個模板，其中 P 和 Q 是二階變量，A 和 B 是一階變量。
一個模板的實例 是對這些二階變量進(jìn)行具體化（grounding）后的結(jié)果，例如：{succ(A,B), succ(B,A)}。

shrinker 按批次處理這些模板。由于可能的模板數(shù)量非常龐大，shrinker 使用一個超時機(jī)制 （timeout）來在限定時間內(nèi)盡可能多地發(fā)現(xiàn)不可滿足或蘊(yùn)含可約的規(guī)則。

算法2 展示了尋找不可滿足規(guī)則和蘊(yùn)含可約規(guī)則的具體流程。該算法的輸入包括：

• 背景知識（BK）

• 規(guī)則中允許的最大文字?jǐn)?shù)（max_size）

• 規(guī)則中允許的最大不同變量數(shù)（max_vars）

• 每次迭代中檢查的模板數(shù)量（batch_size）

• 時間限制（timeout）

該算法輸出一組無意義規(guī)則（pointless rules）。

算法2 的工作流程如下。函數(shù) build_templates（第2行）構(gòu)建所有可能的模板，這些模板最多包含 max_size 個文字和 max_vars 個變量，并按模板大小 （即文字?jǐn)?shù)量）升序返回這些模板。

第5至8行展示了在 BK 上測試模板 以找出不可滿足規(guī)則和蘊(yùn)含可約規(guī)則的循環(huán)過程。

• 函數(shù) select_templates （第6行）從尚未測試的模板中選擇 batch_size 個模板進(jìn)行測試。

• 函數(shù) find_pointless_rules （第8行）是關(guān)鍵函數(shù)。它接收 BK 和模板作為輸入，并返回發(fā)現(xiàn)的無意義規(guī)則。

我們使用自底向上 的方式并通過 ASP（Answer Set Programming，回答集編程） 來實現(xiàn) find_pointless_rules 函數(shù)。具體來說，我們?yōu)槊織l規(guī)則尋找一個反例，以證明它不是 不可滿足的或不是 蘊(yùn)含可約的。

例如：

• 要證明體部包含 p(A,B), p(B,C), p(A,C) 的所有規(guī)則都是不可滿足的，我們需要檢查是否存在這樣一個反例：在 BK 中，文字 p(A,B) 、 p(B,C) 和 p(A,C) 同時為真。

• 要證明體部包含 p(A), q(A) 的規(guī)則是蘊(yùn)含可約的，我們需要檢查是否存在這樣一個反例： p(A) 為真但 q(A) 為假，或者反過來。

我們使用 ASP 來執(zhí)行這些檢查。首先，我們構(gòu)建一個 ASP 編碼 P，其中包含了所有的 BK。在下文中，我們使用等寬字體表示 ASP 代碼。

對于 BK 中每個元數(shù)為 a的關(guān)系 p，我們在 P中添加如下規(guī)則：

4.1.3 推導(dǎo)不可滿足規(guī)則與蘊(yùn)含可約規(guī)則

我們使用 ASP 求解器 clingo [28] 來尋找 P的一個模型，從而識別出不可滿足規(guī)則 和蘊(yùn)含可約規(guī)則 。具體來說，我們利用 clingo 的多輪求解 （multi-shot solving）功能 [29]，在不重新接地（regrounding）BK 的前提下，逐步測試一批批模板。

shrinker 使用一個事實來表示一個無意義規(guī)則。例如，如果模板 {succ(A,B), succ(B,A)} 是不可滿足的，那么 shrinker 將其表示為事實 unsat_ab_ba(succ,succ)。

算法2最終返回一組這樣的事實，用以表示發(fā)現(xiàn)的無意義規(guī)則。

4.2 尋找回召可約規(guī)則

為了識別召回可約規(guī)則 ，我們采用了一種受 Struyf 和 Blockeel [66] 啟發(fā)的方法，他們提出通過對規(guī)則中的文字進(jìn)行排序以提高查詢效率（詳見第2節(jié)對該工作的介紹）。從高層次來看，對于任何一個背景關(guān)系，我們會確定其任意一組參數(shù)子集所能產(chǎn)生的最大答案替換 （ground instantiations，即實例化為具體常量的情況）數(shù)量。

我們使用標(biāo)準(zhǔn)的召回記號 [52] 來表示輸入/接地參數(shù)（用 + 表示）和輸出/非接地參數(shù)（用 - 表示）。為了說明這種記號，考慮以下事實：

對于 p(-,-) 的召回數(shù) （recall）是 3，因為在 BK 中只有 3 個 p/2 的事實。
對于 p(+,-) 的召回數(shù)是 1，因為對于任意一個已知的第一個參數(shù)，最多只有一個接地的第二個參數(shù)。
對于 q(+,-,-) 的召回數(shù)也是 1，因為對于任意一個已知的第一個參數(shù)，最多只有一對由第二和第三個參數(shù)組成的實例。
而對于 q(-,+,+) 的召回數(shù)是 2，因為對于任意一對由第二和第三個參數(shù)組成的已知值，在第一個位置上最多存在兩個非接地的參數(shù)。

算法3 展示了我們用于尋找召回可約規(guī)則 的算法。該算法以背景知識（BK）作為輸入，并返回一組表示關(guān)系在特定參數(shù)子集下的召回值的事實。

算法工作流程如下：

• 它遍歷 BK 中的每一個原子（第4行），并遍歷該原子的所有參數(shù)子集（第9行），這對應(yīng)于所有可能的召回組合。

• 例如，對于原子 succ(A,B) ，使用召回記號表示，其參數(shù)子集包括： succ(-,-) 、 succ(+,-) 和 succ(-,+） 。

• 我們忽略所有參數(shù)都為輸入/已知的情況（如 succ(+,+) ），因為此時召回數(shù)恒為1。

• 對于每一個參數(shù)子集，我們創(chuàng)建一個由輸入/已知參數(shù)構(gòu)成的鍵（key），以及一個由輸出/未知參數(shù)構(gòu)成的值（value）。

• 然后我們將這些鍵值對添加到一個哈希表中，這個哈希表是針對每個謂詞及其參數(shù)子集單獨(dú)維護(hù)的。

• 最后，對于每一個關(guān)系及其參數(shù)子集，我們利用這個哈希表來計算其最大答案替換數(shù)量（即召回值）。

該算法返回一組形式為 recall(pred_input_output_count) 的事實，其中：

• pred

  是一個謂詞符號，

• input

  是輸入變量的序列，

• output

  是輸出變量的序列，

• count

  是對應(yīng)的召回值。

例如：

• 對于召回值為 1 的 p(+,-) ，對應(yīng)的事實是 recall_p_a_b_1 ；

• 對于召回值為 1 的 p(-,+) ，對應(yīng)的事實是 recall_p_b_a_1 ；

• 對于召回值為 2 的 q(-,+,+) ，對應(yīng)的事實是 recall_q_bc_a_2 。

我們使用 ASP 來識別單例可約規(guī)則 。需要提醒的是，單例可約規(guī)則 是指包含一個始終為真 的文字的規(guī)則。例如，考慮以下規(guī)則：

假設(shè) length/2 具有合理的語義，那么文字 length(A,B) 始終為真，因為每個列表都有一個長度。換句話說，由于變量 B在這條規(guī)則中只出現(xiàn)一次，并且對于所有列表來說變量 A都為真，因此文字 length(A,B) 是冗余的，因為它沒有任何區(qū)分能力。

我們假設(shè)背景關(guān)系具有簡單的類型系統(tǒng) （關(guān)于類型的詳細(xì)說明請參見附錄6）。我們使用 ASP 來判斷某個關(guān)系是部分的 （partial）還是全函數(shù)性的 （total），并利用這些信息來推導(dǎo)出單例可約規(guī)則。

我們描述一下我們的 ASP 編碼 P：

• 我們將背景知識（BK）加入到 P 中。

• 對于 BK 中每個元數(shù)為 a 的關(guān)系 p ，我們在 P 中添加如下規(guī)則：

最后，我們通過判斷參數(shù)是否不是部分的 （partial），來推導(dǎo)出它們是否是全函數(shù)性的 （total）。我們使用 ASP 求解器來尋找 P的一個模型，從而識別出具有全函數(shù)性的文字。

然后，算法2返回一組事實，表示背景文字中哪些參數(shù)是全函數(shù)性的。例如：

• 對于 length/2 關(guān)系，如果其第一個參數(shù)是全函數(shù)性的，那么 shrinker 返回事實 total_length_b ；

• 對于 add/3 關(guān)系，如果任意兩個變量組合都是全函數(shù)性的，那么 shrinker 返回三個事實：
  total_add_ab 、 total_add_ac 和 total_add_bc 。

我們證明 shrinker 是正確的 ，即它能夠解決假設(shè)空間縮減問題 （定義 7）：

4.5 Popper

shrinker 的輸出（算法1）是一組無意義規(guī)則 ，具體來說是一組表示這些規(guī)則的事實。任何 ILP 系統(tǒng)都可以利用這些規(guī)則來剪枝假設(shè)空間，例如 Aleph 的規(guī)則剪枝機(jī)制 [64]。我們使用這些規(guī)則來縮減基于約束的 ILP 系統(tǒng) Popper [13] 的假設(shè)空間，它可以學(xué)習(xí)最優(yōu)且可遞歸的假設(shè)。

Popper 有許多變體，包括可以從噪聲數(shù)據(jù)中學(xué)習(xí)的版本 [36]、可以學(xué)習(xí)高階程序的版本 [56]，以及可以從概率數(shù)據(jù)中學(xué)習(xí)的版本 [33]。雖然 shrinker 可以縮減所有這些變體的假設(shè)空間，但我們在此描述最簡單的版本，因為它足以說明我們是如何將其與 shrinker 結(jié)合使用的。

Popper 接收以下輸入：

• 背景知識（BK）

• 訓(xùn)練樣例

• 假設(shè)的最大尺寸

它將假設(shè)學(xué)習(xí)為確定性程序（definite programs）。Popper 會搜索一個最優(yōu)假設(shè)，該假設(shè)能夠蘊(yùn)含所有正例、不蘊(yùn)含任何負(fù)例，并且具有最小的規(guī)模。

Popper 使用一個“生成—測試—合并—約束”循環(huán)（generate, test, combine, constrain loop）來尋找最優(yōu)假設(shè)。

Popper 從一個初始的 ASP 編碼 P開始。這個編碼可以被視為一個生成器 （generator），因為 P的每一個模型（即回答集）都代表一個假設(shè)。

編碼 P使用 head（head_literal/3）和 body（body_literal/3）文字來表示假設(shè)。每個文字的第一個參數(shù)是規(guī)則的 ID，第二個參數(shù)是謂詞符號，第三個參數(shù)是文字中的變量，其中 0 表示 A，1 表示 B，依此類推。

例如，考慮以下規(guī)則：

在生成階段 （generate stage），Popper 使用 ASP 求解器為一個固定的假設(shè)大小尋找 P的模型（通過限制 head 和 body 中文字?jǐn)?shù)量的基數(shù)約束來實現(xiàn)）。如果找不到模型，Popper 會增加假設(shè)大小并重新循環(huán)。如果存在模型，Popper 將其轉(zhuǎn)換為一個假設(shè) h。

在測試階段 （test stage），Popper 使用 Prolog 來測試 h在訓(xùn)練樣例和背景知識上的表現(xiàn)。如果 h能夠蘊(yùn)含至少一個正例且不蘊(yùn)含任何負(fù)例，則 Popper 將其保存為一個有希望的假設(shè)。

在合并階段 （combine stage），Popper 尋找一個能涵蓋所有正例且具有最小規(guī)模的有希望假設(shè)的組合（即它們的并集）。Popper 將搜索建模為一個組合優(yōu)化問題，具體來說是一個 ASP 優(yōu)化問題 [11]。如果找到了這樣的組合，Popper 將其作為目前為止的最佳假設(shè)，并更新最大假設(shè)大小。

在約束階段 （constrain stage），Popper 利用 h構(gòu)建約束，并將這些約束添加到 P中以剪枝模型，從而縮減假設(shè)空間。例如，如果 h沒有 蘊(yùn)含任何正例，那么 Popper 會添加一條約束來排除它的特化規(guī)則（specialisations），因為它們也一定不會蘊(yùn)含任何正例。

例如，以下約束會剪枝所有比規(guī)則 last(A,B) ← tail(A,C), head(C,B) 更具體的規(guī)則（即其超集）：

4.6 shrinker + Popper

我們在 Popper 開始搜索假設(shè)之前（即開始其循環(huán)之前），使用 shrinker 來縮減其假設(shè)空間。為此，我們允許 Popper 利用 shrinker 找到的以下四類無意義規(guī)則來進(jìn)行剪枝：

• 不可滿足規(guī)則

• 蘊(yùn)含可約規(guī)則

4.6.3 召回可約規(guī)則

我們使用 ASP 聚合約束 （aggregate constraints）來簡潔地表達(dá)召回約束。例如，如果 shrinker 發(fā)現(xiàn) succ/2 是函數(shù)性的（即對于任意一個已知的第一個參數(shù)，最多只有一個已知的第二個參數(shù)），它會將這一信息表示為事實 recall_succ_a_b_1。

基于這個事實，我們在 Popper 中添加如下約束：

這條約束會剪枝所有包含以下兩個文字的模型（從而也剪枝了對應(yīng)的假設(shè)）：

• body_literal(Rule, succ, (A, B))
• body_literal(Rule, succ, (A, C))

  ，其中 B != C

換句話說，這條約束會剪枝所有體部包含 succ(A,B) 和 succ(A,C) 且 B ≠ C 的規(guī)則。該約束適用于所有變量 A 和 B 的替換情況，以及所有規(guī)則 Rule。

例如，該約束會剪枝如下規(guī)則：

如果 shrinker 發(fā)現(xiàn) succ/2 是單射的 （即對于任意一個已知的第二個參數(shù)，恰好存在一個已知的第一個參數(shù)），它會將這一信息表示為事實 recall_succ_b_a_1。

基于這個事實，我們在 Popper 中添加如下約束：

4.6.4 單例可約規(guī)則

為了剪枝單例可約規(guī)則 ，我們向 Popper 的生成編碼（generate encoding）中添加如下 ASP 規(guī)則：

5 實驗

我們聲稱，shrinker 能夠在不剪枝最優(yōu)假設(shè)的前提下縮減假設(shè)空間 。命題10支持了這一說法，并表明 shrinker 不會剪枝最優(yōu)假設(shè)。然而，尚不清楚 shrinker 對學(xué)習(xí)時間會產(chǎn)生怎樣的影響。因此，我們的實驗旨在回答以下問題：

Q1：shrinker 是否能夠減少學(xué)習(xí)時間？

為了回答 Q1，我們將使用與不使用 shrinker 的 Popper 進(jìn)行學(xué)習(xí)時間的對比。

shrinker 從假設(shè)空間中移除了不可滿足規(guī)則、蘊(yùn)含可約規(guī)則、召回可約規(guī)則和單例可約規(guī)則。為了理解每種類型規(guī)則的影響，我們的實驗還旨在回答以下問題：

Q2：移除每種類型的無意義規(guī)則是否都能減少學(xué)習(xí)時間？

為了回答 Q2，我們在使用 shrinker 時僅移除一種類型的無意義規(guī)則，并比較 Popper 的學(xué)習(xí)時間。

shrinker 接收一個超時參數(shù) （timeout）。為了理解這個參數(shù)的影響，我們的實驗旨在回答以下問題：

Q3：更多的預(yù)處理時間是否能進(jìn)一步減少學(xué)習(xí)時間？

為了回答 Q3，我們比較使用 10 秒和 100 秒超時設(shè)置的 shrinker 所帶來的影響。

5.1 實驗設(shè)置 5.1.1 泛化誤差（Generalisation Error）

每個數(shù)據(jù)集中的每個任務(wù)都包含訓(xùn)練樣例和測試樣例。我們使用訓(xùn)練樣例來訓(xùn)練 ILP 系統(tǒng)以學(xué)習(xí)一個假設(shè)，并使用測試樣例來評估這些假設(shè)在未見數(shù)據(jù)上的泛化能力。

給定一個假設(shè) h、背景知識 B和一組樣例 E，我們定義如下指標(biāo)：

• 真陽性

  （True Positive）：被 h∪B 蘊(yùn)含的正例；

• 真陰性

  （True Negative）：未被 h∪B 蘊(yùn)含的負(fù)例；

我們將真陽性和真陰性的數(shù)量分別記作 tpE(h)和 tnE(h)。

我們使用平衡預(yù)測準(zhǔn)確率 （balanced predictive accuracy）來衡量泛化誤差。該指標(biāo)通過對正類和負(fù)類的平均表現(xiàn)進(jìn)行評估，從而適用于類別不平衡的數(shù)據(jù)：

平衡準(zhǔn)確率

當(dāng)假設(shè)在兩個類別上的表現(xiàn)相同，或者數(shù)據(jù)是平衡的時，平衡準(zhǔn)確率 等價于標(biāo)準(zhǔn)準(zhǔn)確率。

5.1.2 設(shè)置

我們使用 shrinker 的設(shè)置為：max_size=3、max_vars=6、batch_size=1000 和 timeout=10 秒，除非我們在回答 Q3 時使用 timeout=100 秒。我們允許 Popper 學(xué)習(xí)最多包含 6 個變量和最多 10 個體部文字的規(guī)則。我們使用 AWS m6a.16xlarge 實例運(yùn)行實驗，每個學(xué)習(xí)任務(wù)使用一個 CPU 核心。

5.1.3 方法

我們對每項任務(wù)設(shè)置了 60 分鐘的超時限制。Popper 是一種“隨時可用”的方法（anytime approach），我們使用 Popper 在最多 60 分鐘的學(xué)習(xí)時間內(nèi)找到的最佳假設(shè)。我們測量平均平衡準(zhǔn)確率和平均學(xué)習(xí)時間。我們將超過一秒的時間四舍五入到最接近的整秒。所有實驗重復(fù) 10 次，并繪制并報告 95% 置信區(qū)間。我們使用配對 t 檢驗或 Wilcoxon 符號秩檢驗（取決于差異是否符合正態(tài)分布）來確定結(jié)果差異的統(tǒng)計顯著性。換句話說，任何后續(xù)提到的顯著性檢驗都指的是這兩種測試之一。

5.1.4 數(shù)據(jù)集

我們使用了多個數(shù)據(jù)集：

• 1D-ARC

  ：該數(shù)據(jù)集 [68] 包含受抽象推理語料庫 [6] 啟發(fā)的視覺推理任務(wù)。

• Alzheimer

  ：這些真實世界任務(wù) [44] 涉及學(xué)習(xí)描述阿爾茨海默病藥物設(shè)計中四個理想性質(zhì)的規(guī)則。

• IGGP

  ：在歸納通用博弈（Inductive General Game Playing, IGGP）[10] 中，任務(wù)是從通用博弈競賽 [30] 的游戲軌跡中歸納出規(guī)則。

• IMDB

  ：我們使用了一個包含電影、演員和導(dǎo)演之間關(guān)系的真實世界數(shù)據(jù)集 [50]。

• List functions

  ：列表函數(shù)數(shù)據(jù)集 [61] 用于評估人類與機(jī)器的概念學(xué)習(xí)能力。每個任務(wù)的目標(biāo)是識別將輸入列表映射到輸出列表的函數(shù)，其中列表元素是自然數(shù)。我們使用了一個關(guān)系編碼 [34]。

• Trains

  ：目標(biāo)是找到一個能夠區(qū)分東向列車和西向列車的假設(shè) [46]。

• Zendo

  ：Zendo 是一個多玩家游戲，玩家必須通過構(gòu)建結(jié)構(gòu)來發(fā)現(xiàn)一個秘密規(guī)則 [12]。

圖1展示了使用 shrinker 后學(xué)習(xí)時間的改進(jìn)情況。顯著性檢驗確認(rèn)（ < 0.05），在 419 個任務(wù)中的 170 個（40%）任務(wù)上，shrinker 減少了學(xué)習(xí)時間；而在 3 個（0%）任務(wù)上增加了學(xué)習(xí)時間。其余任務(wù)上沒有顯著差異。平均而言，學(xué)習(xí)時間減少了 17 ± 3 分鐘；學(xué)習(xí)時間增加的平均值僅為 2 ± 0 秒。

這些只是最小幅度的改進(jìn)，因為不使用 shrinker 的 Popper 經(jīng)常在 60 分鐘后超時。如果使用更長的超時時間，我們可能會看到更大的改進(jìn)。

shrinker 可以大幅減少學(xué)習(xí)時間 。例如，在 list-function-043 任務(wù)中（目標(biāo)是學(xué)習(xí)如何將一個數(shù)字序列前置到列表中），shrinker 將學(xué)習(xí)時間從 60 ± 0 分鐘減少到 6 ± 0 分鐘，減少了 90%。在 iggp-duikoshi-next_control 任務(wù)中，shrinker 將學(xué)習(xí)時間從 60 ± 0 分鐘減少到 3 ± 0 秒，減少了 99%。

為了進(jìn)一步探索 shrinker 在減少學(xué)習(xí)時間方面的潛力，我們進(jìn)行了一組額外實驗，將部分任務(wù)的最大學(xué)習(xí)時間延長至 24 小時。在這一更長的超時設(shè)置下，對于 iggp-duikoshi-next_control 任務(wù)，shrinker 將學(xué)習(xí)時間從 6.5 ± 1 小時減少到 1 ± 0 秒；對于 iggp-horseshoe-terminal 任務(wù)，shrinker 將學(xué)習(xí)時間從 10 ± 0 小時減少到 33 ± 3 秒。

為了說明 shrinker 為何有效，我們考慮了 iggp-scissors_paper_stone-next_score 任務(wù)。該任務(wù)的目標(biāo)是從游戲觀察中學(xué)習(xí)“石頭剪刀布”游戲的規(guī)則。在這個任務(wù)中，shrinker 發(fā)現(xiàn)背景關(guān)系 succ/2 是非自反的（irreflexive）、反傳遞的 （antitransitive）、反三角的 （antitriangular）和非對稱的 （asymmetric），這些性質(zhì)被表示為不可滿足規(guī)則。shrinker 還發(fā)現(xiàn)了蘊(yùn)含可約規(guī)則，例如文字 succ(A,B), int_0(A), int_1(B) 是蘊(yùn)含可約的。此外，shrinker 還發(fā)現(xiàn) succ/2 關(guān)系是單射的和函數(shù)性的，這些都被表示為召回冗余規(guī)則。盡管 shrinker 僅用了 10 秒的預(yù)處理時間，但由此產(chǎn)生的約束卻將 Popper 的學(xué)習(xí)時間從 382 ± 19 秒減少到了 52 ± 1 秒，提升了 86%。

在 3 個任務(wù)中學(xué)習(xí)時間增加的原因是處理 shrinker 所發(fā)現(xiàn)約束的開銷，即 Clingo 處理這些約束所帶來的計算開銷。在這幾個任務(wù)中，平均學(xué)習(xí)時間僅增加了 2 ± 0 秒。

顯著性檢驗還確認(rèn)（ < 0.05），在 419 個任務(wù)中，shrinker 在 11 個（2%）任務(wù)上提高了預(yù)測準(zhǔn)確率，在 8 個（1%）任務(wù)上降低了準(zhǔn)確率。其他任務(wù)上沒有顯著差異。提高準(zhǔn)確率的主要原因是：在沒有 shrinker 的情況下，Popper 有時無法在時間限制內(nèi)找到一個好的假設(shè)。相比之下，由于 shrinker 縮減了假設(shè)空間，Popper 需要考慮的假設(shè)更少，因此有時能更快地找到更好的假設(shè)。此外，根據(jù)命題 10，shrinker 是最優(yōu)安全的（optimally sound），它保證得到一個原假設(shè)空間的子集，但仍包含最優(yōu)假設(shè)。根據(jù) Blumer 界限 [4]，給定兩個大小不同的假設(shè)空間，搜索較小的空間相比搜索較大的空間會帶來更高的預(yù)測準(zhǔn)確率，前提是好的假設(shè)同時存在于兩者之中。

準(zhǔn)確率下降的主要原因是 Popper 的實現(xiàn)問題。例如在 iggp-tiger_vs_dogs-goal 任務(wù)中，未使用 shrinker 的 Popper 學(xué)到了如下規(guī)則：

相比之下，使用 shrinker 的 Popper 無法學(xué)習(xí)到任何規(guī)則，因此其準(zhǔn)確率默認(rèn)為 50%。Popper 之所以無法學(xué)習(xí)到這條規(guī)則，是因為 shrinker 發(fā)現(xiàn) pos_3(A) 的最大召回率為 1 ，也就是說，它只對一個特定值（即 3）有效。

因此，shrinker 判斷該更準(zhǔn)確的規(guī)則是召回可約的 ，并將其從假設(shè)空間中剪枝了。

相比之下，在這個理想規(guī)則中，謂詞符號 pos_3 只在規(guī)則中出現(xiàn)一次，但變量 V4在文字 true_cell(V0,V4,V4,V3) 中出現(xiàn)了兩次。Popper 無法學(xué)習(xí)這條規(guī)則 ，因為出于歷史原因，它禁止一個變量在一個文字中重復(fù)出現(xiàn)。因此，未使用 shrinker 的 Popper 使用多個變量來學(xué)習(xí)一條邏輯上等價的規(guī)則。

總體而言，本節(jié)的結(jié)果表明 Q1 的答案是肯定的：shrinker 能夠大幅減少學(xué)習(xí)時間 。

5.2.2 Q2：移除每種類型的無意義規(guī)則是否都能減少學(xué)習(xí)時間？

圖2展示了僅移除不可滿足規(guī)則 時的學(xué)習(xí)時間變化情況。這樣做在 419 個任務(wù)中的 40 個（9%）任務(wù)上減少了學(xué)習(xí)時間，平均減少了 2 ± 0 分鐘；在 5 個（1%）任務(wù)上增加了學(xué)習(xí)時間，平均增加了 20 ± 13 秒。

圖3展示了僅移除蘊(yùn)含可約規(guī)則 時的學(xué)習(xí)時間變化情況。這樣做在 419 個任務(wù)中的 139 個（33%）任務(wù)上減少了學(xué)習(xí)時間，平均減少了 17 ± 3 分鐘；在 5 個（1%）任務(wù)上增加了學(xué)習(xí)時間，平均增加了 8 ± 5 秒。

圖4展示了僅移除召回可約規(guī)則 時的學(xué)習(xí)時間變化情況。這樣做在 419 個任務(wù)中的 64 個（15%）任務(wù)上減少了學(xué)習(xí)時間，平均減少了 3 ± 1 分鐘；在 4 個（0%）任務(wù)上增加了學(xué)習(xí)時間，平均增加了 1 ± 1 分鐘。學(xué)習(xí)時間增加的原因是，由于前面提到的“變量在一個文字中重復(fù)出現(xiàn)”的問題，使用 shrinker 的 Popper 有時需要學(xué)習(xí)更長的規(guī)則，因此耗時更多。

圖5展示了僅移除單例可約規(guī)則 時的學(xué)習(xí)時間變化情況。這樣做在 419 個任務(wù)中的 57 個（11%）任務(wù)上減少了學(xué)習(xí)時間，平均減少了 2 ± 0 分鐘；在 4 個（0%）任務(wù)上增加了學(xué)習(xí)時間，平均增加了 47 ± 29 秒。

再次強(qiáng)調(diào)，這些改進(jìn)只是最小幅度的，因為未使用 shrinker 的 Popper 經(jīng)常在 60 分鐘后超時。

總體而言，本節(jié)的結(jié)果表明 Q2 的答案是肯定的：移除每種類型的無意義規(guī)則都可以減少學(xué)習(xí)時間 ，但其中移除蘊(yùn)含可約規(guī)則帶來的影響最大 。

5.2.3 Q3：更多的 shrinker 時間是否能進(jìn)一步減少學(xué)習(xí)時間？

圖6展示了在使用 10 秒和 100 秒超時設(shè)置 的 shrinker 時的學(xué)習(xí)時間變化情況。顯著性檢驗確認(rèn)（ < 0.05），使用 100 秒超時設(shè)置在 419 個任務(wù)中的 28 個（7%）任務(wù)上減少了學(xué)習(xí)時間，在 14 個（3%）任務(wù)上增加了學(xué)習(xí)時間。平均減少時間為 46 ± 17 秒，平均增加時間為 28 ± 15 秒。

總體來看，本節(jié)結(jié)果表明 Q3 的答案是肯定的：更多的 shrinker 預(yù)處理時間可以提升性能 ，但提升幅度并不成比例，并且通常 10 秒的預(yù)處理時間已經(jīng)足夠 。

6 結(jié)論與局限性

我們提出了 shrinker ，這是一種通過預(yù)處理背景知識 來自動縮減 ILP 系統(tǒng)假設(shè)空間的方法。shrinker 能夠識別出四種類型的無意義規(guī)則 （pointless rules）：不可滿足規(guī)則 （unsatisfiable）、蘊(yùn)含可約規(guī)則 （implication reducible）、召回可約規(guī)則 （recall reducible）和單例可約規(guī)則 （singleton reducible）。

我們證明了：任何包含無意義規(guī)則的假設(shè)都不是最優(yōu)的 ，因此可以從假設(shè)空間中安全地移除這些規(guī)則（見命題 2、4、6 和 9）。

我們在多個領(lǐng)域進(jìn)行了實驗，結(jié)果表明 shrinker 能持續(xù)有效地減少 ILP 系統(tǒng)的學(xué)習(xí)時間 。例如，在僅給予 10 秒預(yù)處理時間的情況下，shrinker 可以將學(xué)習(xí)時間從超過 10 小時減少到僅需 2 秒。

局限性 有限的背景知識（Finite BK）

我們的假設(shè)空間縮減思想具有足夠的通用性，可以處理以確定性程序 （definite programs）形式表示的背景知識（BK）。然而，由于我們采用的是自底向上 （bottom-up）的實現(xiàn)方式并使用了 ASP，因此我們需要對 BK 進(jìn)行有限的實例化（grounding）。

這一限制意味著我們的實現(xiàn)無法處理具有無限實例化的背景知識，例如涉及連續(xù)值推理的情況。未來的工作應(yīng)解決這一局限性，例如通過使用自頂向下 （top-down）的方法來發(fā)現(xiàn)無意義規(guī)則。

封閉世界假設(shè)（Closed-world Assumption）

我們采用了封閉世界假設(shè) （CWA），以便從給定的背景知識中識別出無意義規(guī)則。例如，如果沒有將 odd(2)作為背景知識提供，我們就假設(shè)它不成立。

由于幾乎所有的 ILP 系統(tǒng)都基于 CWA，因此這一限制僅在將我們的方法用于那些不采用 CWA 的系統(tǒng) 時才適用，例如一些近期的規(guī)則挖掘算法 [69]。

含噪聲的背景知識（Noisy BK）

我們假設(shè)背景知識是無噪聲的 ，即如果某個事實（fact）在 BK 中為真，則它確實是應(yīng)該為真的。處理含噪聲的 BK 是一個尚未解決的挑戰(zhàn) [9]，超出了本文的研究范圍。

效率問題（Efficiency）

shrinker 使用暴力枚舉的方式構(gòu)建模板，以識別不可滿足和蘊(yùn)含可約規(guī)則。然而，我們認(rèn)為某些規(guī)則在縮減假設(shè)空間方面具有更大的影響。因此，未來的工作應(yīng)探索如何對模板進(jìn)行排序，從而優(yōu)先找到最具影響力的規(guī)則 ，提升預(yù)處理效率。

附錄 B

我們對命題5 的證明需要一個召回可約性 （recall reducible）的替代定義（定義22），然后證明該替代定義與原始定義（定義11）是等價的。這個替代定義使我們能夠?qū)?θ-蘊(yùn)含中隱含的替換轉(zhuǎn)化為等式文字 （equality literals）。這些等式文字隨后用于測試邏輯等價性。

上述構(gòu)造需要比較一組文字中的參數(shù)元組（argument tuples）：

正如我們將在定理1 中展示的那樣，召回可約性 （recall reducible，定義11）捕捉了我們對鴿巢原理 （pigeonhole principle）的一種改編形式。

考慮兩條規(guī)則 r1和 r2。根據(jù)定義，如果且這兩條規(guī)則在邏輯上是等價的，則 r1是召回可約的 。請注意，這通過 θ-蘊(yùn)含中隱含的替換關(guān)系實現(xiàn)了定義22中引入的不等式。

如上所述，召回可約性 （recall reducible）與鴿巢化 （pigeonholed）是兩個等價的概念。雖然“鴿巢化”通過引入不等式來形式化我們對鴿巢原理的改編，但“召回可約性”則利用了 θ-蘊(yùn)含中的隱式替換。

定理1 的證明 提供了相應(yīng)的構(gòu)造方法，使得我們可以在兩種概念之間進(jìn)行轉(zhuǎn)換。

https://arxiv.org/abs/2506.06739