p347 - p371
前幾天休刊了，今天回來了= =
進(jìn)入第15章
第15章 規(guī)則學(xué)習(xí)模型
15.1 基本概念
“規(guī)則”通常指語義明確，能描述數(shù)據(jù)分布隱含的客觀規(guī)律或領(lǐng)域概念，可寫成“若..則..”。
與其他黑箱模型相比，規(guī)則學(xué)習(xí)具有更好的可解釋性。
絕大多數(shù)人類知識(shí)都能通過數(shù)理邏輯來進(jìn)行刻畫，因此便于引進(jìn)領(lǐng)域知識(shí)。
符合一條規(guī)則的樣本稱為被該規(guī)則“覆蓋”。
當(dāng)同一個(gè)示例被判別結(jié)果不同的多條規(guī)則覆蓋時(shí)，稱發(fā)生了沖突。
解決沖突的方法稱為沖突消解，包括投票法、排序法、元規(guī)則法。
一般都要設(shè)置默認(rèn)規(guī)則，來處理規(guī)則集合未覆蓋的樣本。
命題規(guī)則VS一階規(guī)則（關(guān)系型規(guī)則） p348
15.2 序貫覆蓋
規(guī)則學(xué)習(xí)最直接的做法是“序貫覆蓋”，即逐條歸納。
每學(xué)到一條規(guī)則，就將該規(guī)則覆蓋的樣本去掉，以剩下的樣例繼續(xù)訓(xùn)練。
由于每次只處理一部分?jǐn)?shù)據(jù)，所以也被稱為“分治”策略。
基于窮盡搜索的做法
例子：p350。
但現(xiàn)實(shí)中會(huì)因?yàn)榻M合爆炸而不可行。
通常有兩種策略：
自頂向下（生成-測試） vs 自底向上（數(shù)據(jù)驅(qū)動(dòng)）
前者是從一般的規(guī)則開始，逐漸添加新文字，是規(guī)則逐漸“特化”的過程
更容易產(chǎn)生泛化性能較好的規(guī)則。
對(duì)噪聲魯棒性強(qiáng)。
例子p351-352。
可每次采用多個(gè)最優(yōu)文字來避免過于貪心。
后者是從特殊的規(guī)則開始，減少文字，是“泛化”的過程。
更適用于訓(xùn)練樣本較少。
15.3 剪枝優(yōu)化
規(guī)則生成本質(zhì)是一個(gè)貪心搜索過程，需要緩解過擬合。
最常見做法是剪枝
預(yù)剪枝 vs 后剪枝
CN2算法的預(yù)剪枝。借助了統(tǒng)計(jì)性檢驗(yàn)。
REP的后剪枝，O(m^4)。
IREP O(m log^2 m)
著名的規(guī)則學(xué)習(xí)算法 RIPPER 后處理機(jī)制，將R中所有規(guī)則再進(jìn)行一次優(yōu)化，就是通過全局的考慮來緩解了貪心算法的局部性。
15.4 一階規(guī)則學(xué)習(xí)
通常很難定義屬性值。
因此可以采用“色澤更深（2，1）、更好（2，1）”這樣的表述方式。
色澤更深 這樣的原子公式稱為“背景知識(shí)”
更好 這樣由樣本類別轉(zhuǎn)化而來的原子公式稱為“關(guān)系數(shù)據(jù)樣例”
一階學(xué)習(xí)能容易的引入領(lǐng)域知識(shí)，是相比命題學(xué)習(xí)的一大優(yōu)勢。
在命題規(guī)則學(xué)習(xí)乃至一般的統(tǒng)計(jì)學(xué)習(xí)中，引入領(lǐng)域知識(shí)通常有兩種做法：
1）通過領(lǐng)域知識(shí)構(gòu)造新屬性。
2）基于領(lǐng)域知識(shí)設(shè)計(jì)某種函數(shù)機(jī)制（如正則化）來對(duì)假設(shè)空間進(jìn)行約束。
FOIL算法：著名的一階規(guī)則學(xué)習(xí)算法。
遵循序貫覆蓋并采用自頂向下的歸納策略。
并采用后剪枝進(jìn)行優(yōu)化。
使用FOIL增益來選擇文字。
15.5 歸納邏輯程序設(shè)計(jì)（ILP）
在一階學(xué)習(xí)中引入了函數(shù)和邏輯表達(dá)式嵌套
容易看到這樣就不能自頂向上了，因?yàn)闊o法窮舉。
15.5.1 最小一般泛化（LGG）
ILP都采用自底向上的策略。
如何把特殊規(guī)則轉(zhuǎn)化為一般規(guī)則？
最基礎(chǔ)的技術(shù)是LGG
舉例：p358 - p359
15.5.2 逆歸結(jié)
歸結(jié)原理：一階謂詞演算中的演繹推理能用一條十分簡潔的規(guī)則描述。
可將復(fù)雜的邏輯規(guī)則和背景知識(shí)聯(lián)系起來化繁為簡
逆歸結(jié)：能基于背景知識(shí)來發(fā)明新的概念和關(guān)系
p360-p363 具體過程有些抽象
逆歸結(jié)的一大特點(diǎn)是可以自動(dòng)發(fā)明新謂詞，這些新謂詞可能對(duì)應(yīng)于一些新知識(shí)。
15.6 閱讀材料
規(guī)則學(xué)習(xí)是符號(hào)主義學(xué)習(xí)的主要代表。
