Learning Explanatory Rules from Noisy Data 閱讀筆記3

ILP（Inductive Logic Programming） as a Satisfiability Problem

總體來說有ILP有兩種方式：自下向上 和 自上而下

自下而上：查看數據的特徵，從中抽取特殊clause，從特殊clause中生成程序

自上而下：從語言定義生成clause，然後在正例和負例上測試程序

自上而下的方法里，把 搜索clause 轉成一個 可滿足性的 問題，在這種 轉成可滿足性問題 的方法里，有用bool flag來標記哪些搜索空間需要搜索，也有 根據程序模板 生成一些大的clause集合 然後用bool flag決定哪些clause開和關

這篇文章使用自上而下的 生成-測試 的方法，也就是從語言模板生成clause。給每個生成的clause一個flag指示其開或關，現在 歸納（induction） 問題變成了 可滿足性（satisfiability

）問題：

選擇一個flag的賦值，這樣讓已經打開的clause 和背景fact一起 entail正例 而不entail負例

我們的方法：通過梯度下降學習哪些clause要開或關，甚至在給定雜訊或歧義數據的情況下。

Basic Concepts

一個語言框架L是

其中target是目標斷言，是我們想要訓練得到的斷言

Pe是一個擴展的斷言集合

arity_e是映射到數量的映射：

C是一個常量的集合

一個ILP問題是(L, B, P, N)

其中L是上面的語言框架

B是由Pe和C出來的ground atoms

P正例 N負例

比如在判斷為偶數的任務里P可以是{even(0), even(2), even(4), even(6)}

N可以是{even(1), even(3), even(5)}

規則模板 τ 即 (v, int)

其中 v ∈ N 是clause里合法的變數的數量

int ∈ {0, 1} 表示clause的body的atom，int=1表示這個atom可以用目標斷言，int=0表示只能用其他斷言

程序模板 Π 即

Pa是一種斷言的集合

arity_a是映射到數量的映射

rules是把每個斷言映射為規則模板

T ∈ N指前向鏈式推斷的最大步數

在我們的系統里，認為每個斷言（predicate）被2個clause定義

結合語言框架

和程序模板

得到一個語言：

其中

如果

然後G是所有ground atoms

Generating Clauses

有一個規則模板τ，我們能生成一個滿足這個規則模板的clause的集合cl(τ)

為了讓cl(τ)可管理，我們要加些限制

在附錄B提供了一個例子

Reducing Induction to Satisfiability

具體在附錄B講