Learning Explanatory Rules from Noisy Data 閱讀筆記2

Background

Logic Programming

定義

如果右邊所有項都true則左邊為true，也就是

if α1==true and α2==true ... and αm==true then α==true

α稱為head atom，α1到αm稱為body atom，

α的集合為A

α可以看做一個函數，可以放參數的，如果沒有參數就是ground的

比如

表示X和Y有連接有兩種可能，X和Y有邊（也就是 有邊等價於有連接） 或者 X和Z有邊且Z和Y有連接

ground rule定義為 所有變數被替換成常量 的操作，比如

如果有替換

則結合上面可以得到

定義

R是rule

α[θ]是替換操作

根據上式定義

再定義T time step之後的

然後定義 R entails γ 為 R |= γ

Inductive Logic Programming (ILP)

一個tuple(B, P, N)的ground atoms

B是一個ground atoms的集合

P是正例集合，即target里要訓練的

N是負例集合，即target之外的

舉例來說，學習哪些數字是偶數的任務

給定

其中zero表示判斷是否為0的斷言，succ(0,1)表示0後面是1的連接斷言

（確實1在0後面，2在1後面，3在2後面）

然後正負例是

所以解法是

其中|=為entail的意思

歸納Induction 就是找到規則R的集合，使R應用到B時，得到想要的結果，即正例被entailed負例沒有被entailed的結果

對於上面的判斷為偶數例子來說，其中一種解法是

也就是0是偶數，連續2次succ操作之後，也就是從0到了2，然後2也是偶數

（有點類似

X=0while true then print X X=X+2end

的偽代碼）

推薦閱讀：