第15章 規則學習

15.1 基本概念

規則學習(rule learning)是從訓練資料中學習出一組能用于對未見示例進行判别的規則。

一條規則形如

⨁ ⟵ f 1 ∧ f 2 … ∧ f L \bigoplus \longleftarrow f_{1} \land f_{2}\ldots \land f_{L} ⨁⟵f1​∧f2​…∧fL​

其中邏輯蘊含符号 ⟵ \longleftarrow ⟵右邊部分稱為規則體，表示該規則的前提，左邊部分稱為規則頭，表示該規則的結果。

規則體是由邏輯文字 f k f_{k} fk​組合的合取式，其中合取符号 ∧ \land ∧用來表示并且。

每個文字 f k f_{k} fk​都是對示例屬性進行檢驗的布爾表達式。

L L L是規則體中邏輯文字的個數，稱為規則的長度。

規則頭 ⨁ \bigoplus ⨁同樣是邏輯文字，一般用來表示規則所判定的目标類别或概念。

沖突(conflict)：當同一示例被判别結果不同的多條規則覆寫

沖突消解(conflict resolution)：解決沖突的辦法，常用的沖突消解政策由投票法、排序法、元規則法

投票法：将判别相同的規則數最多的結果作為最終結果

排序法：在規則集合上定義一個順序，在發生沖突時使用排序最前的規則；相應的規則學習過程稱為帶序規則(ordered rule)學習或優先級規則(priority rule)學習。

元規則法：根據領域知識事先設定一些元規則(meta-rule)，即關于規則的規則

量詞：用于限定變量的取值範圍， ∃ ， ∀ \exists，\forall ∃，∀分别表示存在和任意。

15.2 序貫覆寫

序貫覆寫(sequential covering)：在訓練集上每學到一條規則，就将該規則覆寫的訓練樣例去除，然後以剩下的訓練樣例組成訓練集重複上述過程。由于每次隻處理一部分資料，也被稱為分治(separate-and-conquer)政策

自頂向下：從比較一般的規則開始，逐漸添加新文字以縮小規則覆寫範圍，直到滿足預定條件為止；亦稱為生成-測試(generate-then-test)法，是規則逐漸特化的過程。

自底向上：從比較特殊的規則開始，逐漸删除文字以擴大規則覆寫範圍，直到滿足條件為止；亦稱資料驅動(data-driven)法，是規則逐漸泛化的過程。

集束搜尋：每輪保留最優的b個邏輯文字，在下一輪均用于建構候選集，再把候選集中最優的b個留待再下一輪使用。

15.3 剪枝優化

規則生成本質是一個貪心搜尋過程，需要有一定的機制來緩解過拟合的風險，最常用的做法是剪枝。通常是基于某種性能度量名額來評估增/閃邏輯文字前後的規則性能，或增/删規則前後的規則集性能，進而判斷是否要進行剪枝。

CN2算法

在預剪枝時，假設用規則集進行預測必須顯著優于直接基于訓練樣例集後驗機率分布進行預測。

令 m + , m − m_{+},m_{-} m+​,m−​分别表示訓練樣例集的正、反例數目， m ^ + , m ^ − {\hat{m}}_{+},{\hat{m}}_{-} m^+​,m^−​分别表示規則覆寫的正、反例數目。則有

L R S = 2 ∗ ( m ^ + ⁡ ( m ^ + m ^ + + m ^ − ) ( m + m + + m − ) + m ^ − ⁡ ( m ^ − m ^ + + m ^ − ) ( m − m + + m − ) ) LRS = 2*\left( {\hat{m}}_{+}\operatorname{}\frac{\left( \frac{{\hat{m}}_{+}}{{\hat{m}}_{+} + {\hat{m}}_{-}} \right)}{\left( \frac{m_{+}}{m_{+} + m_{-}} \right)} + {\hat{m}}_{-}\operatorname{}\frac{\left( \frac{{\hat{m}}_{-}}{{\hat{m}}_{+} + {\hat{m}}_{-}} \right)}{\left( \frac{m_{-}}{m_{+} + m_{-}} \right)} \right) LRS=2∗⎝⎛​m^+​(m+​+m−​m+​​)(m^+​+m^−​m^+​​)​+m^−​(m+​+m−​m−​​)(m^+​+m^−​m^−​​)​⎠⎞​

資訊量名額，衡量了規則覆寫樣例的分布與訓練集經驗分布的差别：LRS越大，說明采用規則進行預測與直接使用訓練集正、反例比率進行猜測的差别越大；LRS越小，說明規則的效果越可能僅是偶然現象。

減錯剪枝(Reduced Error Pruning, REP)

基本做法：将樣例集劃分為訓練集和驗證集，從訓練集上學得規則集R後進行多輪剪枝，在每一輪窮舉所有可能的剪枝操作，然後用驗證集對剪枝産生的所有候選規則集進行評估，保留最好的那個規則集進行下一輪剪枝，如此繼續，直到無法通過剪枝提高驗證集上的性能為止。

IREP(Incremental REP)

基本做法：在生成每條規則前，先将目前樣例集劃分為訓練集和驗證集，在訓練集上生成一條規則r，立即在驗證集上對其進行REP剪枝，得到規則 r ′ r' r′；将 r ′ r' r′覆寫的樣例去除，在更新後的樣例集上重複上述過程。

15.4 一階規則學習

關系資料(relational data)：資料直接描述樣例間的關系

一般規則學習能容易引入領域知識，這是它相對命題規則學習的另一大優勢。在現有屬性的基礎上基于領域知識構造出新屬性，或基于領域知識設定某種函數機制來對假設空間加以限制。

FOIL(First-Order Inductive Learned)

是一階規則學習算法，遵循序貫覆寫架構且采用自頂向下的規則歸納政策，使用FOIL增益來選擇文字：

F _ G a i n = m ^ + × ( ⁡ m ^ + m ^ + + m ^ − − ⁡ m + m + + m − ) F\_ Gain = {\hat{m}}_{+} \times \left( \operatorname{}{\frac{{\hat{m}}_{+}}{{\hat{m}}_{+} + {\hat{m}}_{-}} - \operatorname{}\frac{m_{+}}{m_{+} + m_{-}}} \right) F_Gain=m^+​×(m^+​+m^−​m^+​​−m+​+m−​m+​​)

其中 m ^ + , m ^ − {\hat{m}}_{+},{\hat{m}}_{-} m^+​,m^−​分别為增加候選文字後新規則所覆寫的正、反例數； m + , m − m_{+},m_{-} m+​,m−​原規則覆寫的正、反例數。

FOIL增益僅考慮正例的資訊量，并且用新規則覆寫的正例數作為權重。

15.5 歸納邏輯程式設計

歸納邏輯程式設計(Inductive Logic Programming,ILP)在一階規則學習中引入函數和邏輯表達式嵌套。

15.5.1 最小一般泛化

泛化操作可以是将規則中的常量替換為邏輯變量，也可以是删除規則中的某個文字

最小一般泛化(Least General Generalization, LGG)

給定一階公式 r 1 r_{1} r1​和 r 2 r_{2} r2​，LGG先找出涉及相同謂詞的文字，然後對文字中每個位置的常量逐一進行考察，若常量在兩個文字中相同則保持不變，記為 LGG ( t , t ) = t \text{LGG}\left( t,t \right) = t LGG(t,t)=t；否則将它們替換為同一個新變量，并将該替換應用于公式的所有其他位置：假定這兩個不同的常量分别是 s , t s,t s,t，新變量為 V V V，則記為 LGG ( s , t ) = V \text{LGG}\left( s,t \right) = V LGG(s,t)=V，并在以後所有出現 LGG ( s , t ) \text{LGG}\left( s,t \right) LGG(s,t)的位置用來代替。

15.5.2 逆歸結

一階謂詞演算直到演繹推理能用一條十分簡潔的規則描述，這就是數學中著名的歸結原理。

置換：用某些項來替換邏輯表達式中的變量

合一：用一種變量置換令兩個或多個邏輯表達式相等。