今天給自己加班 量產(chǎn)兩篇 堅(jiān)持輸出yeap!
這是寫西瓜書系列的最后一章啦！
————————

規(guī)則學(xué)習(xí)

基本概念：機(jī)器學(xué)習(xí)中的規(guī)則通常指語義明確、能描述數(shù)據(jù)分布所隱含的客觀規(guī)律或領(lǐng)域概念、可寫成“若…，則…”形式的邏輯規(guī)則。
規(guī)則學(xué)習(xí)：從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)出一組能用于對(duì)未見示例進(jìn)行判別的規(guī)則。
規(guī)則的基本表達(dá)形式如下圖：

舉個(gè)例子：

采用規(guī)則學(xué)習(xí)的優(yōu)勢(shì)：
（1）規(guī)則學(xué)習(xí)具有更好的可解釋性，能使用戶更直觀地對(duì)判別過程有所了解；
（2）規(guī)則學(xué)習(xí)能更自然地在學(xué)習(xí)過程中引入領(lǐng)域知識(shí)；
（3）邏輯規(guī)則的抽象描述能力在處理一些高度復(fù)雜的AI任務(wù)時(shí)具有顯著的優(yōu)勢(shì)。

沖突與沖突消解：

規(guī)則集合中的每條規(guī)則都可看作一個(gè)子模型，規(guī)則集合是這些子模型的一個(gè)集成。當(dāng)同一個(gè)示例被判別結(jié)果不同的多條規(guī)則覆蓋時(shí)，稱“沖突”.
消解的方法如下：

命題規(guī)則VS一階規(guī)則

從形式語言系統(tǒng)的角度看，命題規(guī)則是一階規(guī)則的特例，一階規(guī)則的學(xué)習(xí)要比命題規(guī)則復(fù)雜。

序貫覆蓋

基本概念：序貫覆蓋”，即逐條歸納，在訓(xùn)練集上每學(xué)到一條規(guī)則，就將該規(guī)則覆蓋的訓(xùn)練樣例去除，然后以剩下的訓(xùn)練樣例組成訓(xùn)練集重復(fù)上述過程，由于每次只處理一部分?jǐn)?shù)據(jù)，也被稱為“分治”策略。
關(guān)鍵：如何從訓(xùn)練集學(xué)出單條規(guī)則。
對(duì)規(guī)則學(xué)習(xí)目標(biāo)⊕，產(chǎn)生一條規(guī)則就是尋找最優(yōu)的一組邏輯文字來構(gòu)成規(guī)則體，這是一個(gè)搜索問題。
簡(jiǎn)單的做法是從空規(guī)則“⊕←”開始，將正例類別作為規(guī)則頭，再逐個(gè)遍歷訓(xùn)練集中的每個(gè)屬性及取值，嘗試將其作為邏輯文字增加到規(guī)則體中，若能使當(dāng)前規(guī)則體僅覆蓋正例,則由此產(chǎn)生一條規(guī)則，然后去除已被覆蓋的正例并基于剩余樣本嘗試生成下一條規(guī)則。
那么問題來了，這種基于窮盡搜索的做法在屬性和候選值較多時(shí)會(huì)由于組合爆炸而不可行。

因而有了自頂向下和自底向上兩種搜索方法。
1.自頂向下，從比較一般的規(guī)則開始，逐漸增加新文字以縮小規(guī)則覆蓋范圍，直到滿足預(yù)定條件，也稱生成-測(cè)試法，是規(guī)則逐漸特化的過程，從一般到特殊

如上圖所示，自頂向下，覆蓋范圍從大往小搜索規(guī)則，更容易產(chǎn)生泛化性能較好的規(guī)則。

2.自底向上，從比較特殊的規(guī)則開始，逐漸刪除文字以擴(kuò)大覆蓋范圍，直到滿足條件；也稱數(shù)據(jù)驅(qū)動(dòng)法，是規(guī)則逐漸泛化的過程，從特殊到一般的過程。

如上圖所示，自底向上，覆蓋范圍從小往大搜索規(guī)則，適合于訓(xùn)練樣本較少的情形。
這兩種方法，前者對(duì)噪聲的魯棒性比后者要強(qiáng)得多。因此，在命題規(guī)則學(xué)習(xí)中通常使用第一種策略,而第二種策略在一階規(guī)則學(xué)習(xí)這類假設(shè)空間非常復(fù)雜的任務(wù)上實(shí)用得多。

下面以西瓜集為例（采用自頂向下的方式）

從空規(guī)則“好瓜”開始，逐一將“屬性=取值”作為原子命題加入空規(guī)則。n/m 表示加入某命題后新規(guī)則在訓(xùn)練集的準(zhǔn)確率（m覆蓋的樣例總數(shù)，n為覆蓋的正例數(shù)）

從上圖可以看到，第一輪候選集中，色澤=烏黑、 臍部=凹陷都是3/4，于是選擇屬性次序靠前的加入空規(guī)則，也就是好瓜←（色澤=烏黑）加入規(guī)則。然后對(duì)上面這條規(guī)則覆蓋的樣例通過第二輪評(píng)估，都能達(dá)到100%，我們將覆蓋樣例最多，且屬性次序最靠前的根蒂=蜷縮加入規(guī)則，最終得到結(jié)果。

注意：（因?yàn)樽皂斚蛳轮?，若每次僅考慮一個(gè)最優(yōu)文字，過于貪心，易陷入局部最優(yōu)，通常采取集束搜索，即每輪保留最優(yōu)的b個(gè)邏輯文字，在下一輪均用于構(gòu)建候選集，再把候選集中最優(yōu)的b個(gè)留待下一輪使用。）

剪枝優(yōu)化

規(guī)則生成本質(zhì)上是一個(gè)貪心搜索過程，需要一定的機(jī)制來緩解過擬合的風(fēng)險(xiǎn)，最常見的做法是剪枝
剪枝可發(fā)生在規(guī)則生長(zhǎng)過程中，即預(yù)剪枝；發(fā)生在規(guī)則產(chǎn)生后，即后剪枝。
通常是基于某種性能度量指標(biāo)來評(píng)估增/刪邏輯文字前后的規(guī)則性能，或增/刪規(guī)則前后的規(guī)則集性能，從而判斷是否要進(jìn)行剪枝。

預(yù)剪枝

預(yù)剪枝可以借助統(tǒng)計(jì)顯著性檢驗(yàn)
CN2算法
CN2算法在預(yù)剪枝時(shí)，假設(shè)用規(guī)則集進(jìn)行預(yù)測(cè)必須顯著優(yōu)于直接基于訓(xùn)練樣例集后驗(yàn)概率分布進(jìn)行預(yù)測(cè)。CN2使用了似然率統(tǒng)計(jì)量(LRS).

信息量指標(biāo)，衡量了規(guī)則(集)覆蓋樣例的分布與訓(xùn)練集經(jīng)驗(yàn)分布的差別：
LRS越大，說明采用規(guī)則(集)進(jìn)行預(yù)測(cè)與直接使用訓(xùn)練集正、反例比率進(jìn)行猜測(cè)的差別越大；
LRS越小，說明規(guī)則(集)的效果越可能僅是偶然現(xiàn)象。
在數(shù)據(jù)量比較大的任務(wù)中，通常設(shè)置為在LRS很大(例如0.99)時(shí)CN2算法才停止規(guī)則(集)生長(zhǎng)

后剪枝

減錯(cuò)剪枝(簡(jiǎn)稱REP)：
將樣例集劃分為訓(xùn)練集和驗(yàn)證集，從訓(xùn)練集上學(xué)得規(guī)則集R后進(jìn)行多輪剪枝，在每一輪窮舉所有可能的剪枝操作，包括刪除規(guī)則中某個(gè)文字、刪除規(guī)則結(jié)尾文字、刪除規(guī)則尾部多個(gè)文字、刪除整條規(guī)則等，然后用驗(yàn)證集對(duì)剪枝產(chǎn)生的所有候選規(guī)則集進(jìn)行評(píng)估保留最好的那個(gè)規(guī)則集進(jìn)行下一輪剪枝，直到無法通過剪枝提高驗(yàn)證集上的性能為止。
REP：復(fù)雜度是O(m^4)
IREP ：復(fù)雜度O(mlog2m)
在生成每條規(guī)則前，先將當(dāng)前樣例集劃分為訓(xùn)練集和驗(yàn)證集，在訓(xùn)練集上生成一條規(guī)則r，立即在驗(yàn)證集上對(duì)其進(jìn)行REP剪枝，得到規(guī)則r，將r覆蓋的樣例去除，在更新后的樣例集上重復(fù)上述過程。
REP針對(duì)規(guī)則集進(jìn)行剪枝，而IREP僅對(duì)單條規(guī)則進(jìn)行剪枝，后者比前者更高效。
二者結(jié)合的RIPPER算法

RIPPER中的后處理機(jī)制是為了在剪枝的基礎(chǔ)上進(jìn)一步提升性能，對(duì)R中的每條規(guī)則ri，RIPPER為它產(chǎn)生兩個(gè)變體：

RIPPER有效在通過將規(guī)則集中所有規(guī)則放在一起重新優(yōu)化，通過全局的考慮緩解了貪心算法的局部性。

一階規(guī)則學(xué)習(xí)

受限于命題邏輯表達(dá)能力，命題規(guī)則學(xué)習(xí)難以處理對(duì)象之間的關(guān)系，而關(guān)系信息再很多任務(wù)中是很重要的，要用一階邏輯表示，使用一階規(guī)則學(xué)習(xí)。
一階的目的是描述一類物體的性質(zhì)和相互關(guān)系.
同樣的以西瓜集為例子，我們?cè)诂F(xiàn)實(shí)生活中，很難去量化色澤、敲聲等屬性值，所以采用一階規(guī)則學(xué)習(xí)來判斷好瓜。下圖表格是通過西瓜集轉(zhuǎn)換得到的。

如上圖，更好、更蜷 、更凹 是規(guī)則中關(guān)系描述對(duì)應(yīng)的謂詞，而個(gè)體對(duì)象瓜1 瓜2 被邏輯變量X \Y 替換。一階學(xué)習(xí)能容易的引入領(lǐng)域知識(shí)，是相比命題學(xué)習(xí)的一大優(yōu)勢(shì)。

FOIL算法

1.遵循序貫覆蓋
2.采用后剪枝(自頂向下)進(jìn)行優(yōu)化。
3.使用FOIL增益來選擇文字。

舉例：

歸納邏輯程序設(shè)計(jì)(ILP)

ILP的目標(biāo)是完備地學(xué)習(xí)一階規(guī)則。
我們之前所舉的例子的規(guī)則大都是只對(duì)應(yīng)了特殊的關(guān)系數(shù)據(jù)的樣例，難以具有泛化能力。如果我們需要把特殊規(guī)則變?yōu)楦话憔托枰?strong>最小一般泛化（LGG）。舉個(gè)例子：

其中，第一步先比較更好（1,10）和更好（1,15），由于文字中常量10不等于15，因此替換為Y，并在r1和r2中將其余位置上成對(duì)出現(xiàn)的10 和15 都替換為Y

逆歸結(jié)

歸結(jié)

image.png

——————————
參考鏈接：ch15規(guī)則學(xué)習(xí)-周志華
西瓜書學(xué)習(xí)筆記 | 第15章 規(guī)則學(xué)習(xí)
————————————
搬磚結(jié)束 喜迎周末！