p347 - p371
前幾天休刊了痒钝，今天回來了= =
進入第15章
第15章 規(guī)則學習模型
15.1 基本概念
“規(guī)則”通常指語義明確，能描述數(shù)據分布隱含的客觀規(guī)律或領域概念筹我，可寫成“若..則..”赂苗。
與其他黑箱模型相比，規(guī)則學習具有更好的可解釋性渗蟹。
絕大多數(shù)人類知識都能通過數(shù)理邏輯來進行刻畫块饺，因此便于引進領域知識耻陕。
符合一條規(guī)則的樣本稱為被該規(guī)則“覆蓋”。
當同一個示例被判別結果不同的多條規(guī)則覆蓋時刨沦，稱發(fā)生了沖突。
解決沖突的方法稱為沖突消解膘怕，包括投票法想诅、排序法、元規(guī)則法岛心。
一般都要設置默認規(guī)則来破，來處理規(guī)則集合未覆蓋的樣本。
命題規(guī)則VS一階規(guī)則（關系型規(guī)則） p348
15.2 序貫覆蓋
規(guī)則學習最直接的做法是“序貫覆蓋”忘古，即逐條歸納徘禁。
每學到一條規(guī)則，就將該規(guī)則覆蓋的樣本去掉髓堪，以剩下的樣例繼續(xù)訓練送朱。
由于每次只處理一部分數(shù)據，所以也被稱為“分治”策略干旁。
基于窮盡搜索的做法
例子：p350驶沼。
但現(xiàn)實中會因為組合爆炸而不可行。
通常有兩種策略：
自頂向下（生成-測試） vs 自底向上（數(shù)據驅動）
前者是從一般的規(guī)則開始争群，逐漸添加新文字回怜，是規(guī)則逐漸“特化”的過程
更容易產生泛化性能較好的規(guī)則。
對噪聲魯棒性強换薄。
例子p351-352玉雾。
可每次采用多個最優(yōu)文字來避免過于貪心。
后者是從特殊的規(guī)則開始轻要，減少文字复旬，是“泛化”的過程。
更適用于訓練樣本較少冲泥。
15.3 剪枝優(yōu)化
規(guī)則生成本質是一個貪心搜索過程赢底，需要緩解過擬合。
最常見做法是剪枝
預剪枝 vs 后剪枝
CN2算法的預剪枝柏蘑。借助了統(tǒng)計性檢驗幸冻。
REP的后剪枝，O(m^4)咳焚。
IREP O(m log^2 m)
著名的規(guī)則學習算法 RIPPER 后處理機制洽损，將R中所有規(guī)則再進行一次優(yōu)化，就是通過全局的考慮來緩解了貪心算法的局部性革半。
15.4 一階規(guī)則學習
通常很難定義屬性值。
因此可以采用“色澤更深（2虾攻，1）行施、更好（2，1）”這樣的表述方式漫试。
色澤更深 這樣的原子公式稱為“背景知識”
更好 這樣由樣本類別轉化而來的原子公式稱為“關系數(shù)據樣例”
一階學習能容易的引入領域知識，是相比命題學習的一大優(yōu)勢碘赖。
在命題規(guī)則學習乃至一般的統(tǒng)計學習中驾荣，引入領域知識通常有兩種做法：
1）通過領域知識構造新屬性。
2）基于領域知識設計某種函數(shù)機制（如正則化）來對假設空間進行約束普泡。
FOIL算法：著名的一階規(guī)則學習算法播掷。
遵循序貫覆蓋并采用自頂向下的歸納策略。
并采用后剪枝進行優(yōu)化撼班。
使用FOIL增益來選擇文字歧匈。
15.5 歸納邏輯程序設計（ILP）
在一階學習中引入了函數(shù)和邏輯表達式嵌套
容易看到這樣就不能自頂向上了，因為無法窮舉砰嘁。
15.5.1 最小一般泛化（LGG）
ILP都采用自底向上的策略件炉。
如何把特殊規(guī)則轉化為一般規(guī)則？
最基礎的技術是LGG
舉例：p358 - p359
15.5.2 逆歸結
歸結原理：一階謂詞演算中的演繹推理能用一條十分簡潔的規(guī)則描述矮湘。
可將復雜的邏輯規(guī)則和背景知識聯(lián)系起來化繁為簡
逆歸結：能基于背景知識來發(fā)明新的概念和關系
p360-p363 具體過程有些抽象
逆歸結的一大特點是可以自動發(fā)明新謂詞妻率，這些新謂詞可能對應于一些新知識。
15.6 閱讀材料
規(guī)則學習是符號主義學習的主要代表板祝。
