規(guī)則學(xué)習(xí)
原理
15.1 基本概念
- 機(jī)器學(xué)習(xí)中的“規(guī)則”(rule)通常是指語義明確、能描述數(shù)據(jù)分布所隱含的客觀規(guī)律或領(lǐng)域概念、可寫成“若……，則……”形式的規(guī)則邏輯?！耙?guī)則學(xué)習(xí)”(rule learning)是從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)出一組能用于對未見示例進(jìn)行判別的規(guī)則。
- 與神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)這樣的“黑箱模型”相比，規(guī)則學(xué)習(xí)具有更好的可解釋性，能使用戶更直觀地對判別過程有所了解。另一方面，數(shù)理邏輯具有極強(qiáng)的表達(dá)能力，絕大多數(shù)人類知識都能通過梳理邏輯進(jìn)行簡潔的刻畫和表達(dá)。例如“父親的父親是爺爺”這樣的知識不易用函數(shù)式描述，而用一階邏輯可以方便地描述。因此，規(guī)則學(xué)習(xí)能更自然地在學(xué)習(xí)過程中引入領(lǐng)域知識。此外，邏輯規(guī)則的抽象描述能力在處理一些高度復(fù)雜的AI任務(wù)時(shí)具有顯著的優(yōu)勢，例如在問答系統(tǒng)中有時(shí)可能遇到非常多、甚至無窮種可能的答案，此時(shí)若能基于邏輯規(guī)則進(jìn)行抽象表述或者推理，則將帶來極大的便利。
- 規(guī)則集合中的每條規(guī)則都可看作一個(gè)子模型，規(guī)則集合是這些子模型的一個(gè)集成。當(dāng)同一個(gè)示例被判別結(jié)果不同的多條規(guī)則覆蓋時(shí)，稱發(fā)生了“沖突”(conflict)，解決沖突的辦法稱為“沖突消解”(conflict resolution)。常用的沖突消解策略有投票法、排序法、元規(guī)則法等。投票法是將判別相同的規(guī)則數(shù)最多的結(jié)果作為最終結(jié)果。排序法是在規(guī)則集合上定義一個(gè)順序，在發(fā)生沖突時(shí)使用排序最前的規(guī)則；相應(yīng)的規(guī)則學(xué)習(xí)過程稱為“帶序規(guī)則”(ordered rule)學(xué)習(xí)或“優(yōu)先級規(guī)則”(priority rule)學(xué)習(xí)。元規(guī)則法是根據(jù)領(lǐng)域知識事先設(shè)定一些“元規(guī)則”(meta-rule)，即關(guān)于規(guī)則的規(guī)則，例如“發(fā)生沖突時(shí)使用長度最小的規(guī)則”，然后根據(jù)元規(guī)則的知道來使用規(guī)則集。
- 此外，從訓(xùn)練集學(xué)得的規(guī)則集合也許不能覆蓋所有可能的未見示例。這種情況在屬性數(shù)目很多時(shí)常出現(xiàn)。因此，規(guī)則學(xué)習(xí)算法通常會設(shè)置一條“默認(rèn)規(guī)則”(default rule)，由它來處理規(guī)則集合未覆蓋的樣本；例如為 R 增加一條默認(rèn)規(guī)則：“未被規(guī)則1,2覆蓋的都不是好掛”。
- 從形式語言表達(dá)能力而言，規(guī)則可分為兩類：“命題規(guī)則”(propositional rule)和“一階規(guī)則”(first-order rule)。前者是由“原子命題”(propositional atom)和邏輯連接詞“與”、“或”、“非”和“蘊(yùn)含”(←)構(gòu)成的簡單陳述句；
- “一階規(guī)則”的基本成分是能描述事物的屬性或關(guān)系的“原子公式”(atomic formula)。從形式語言系統(tǒng)的角度看，命題規(guī)則是一階規(guī)則的特例，因此一階規(guī)則的學(xué)習(xí)比命題規(guī)則復(fù)雜得多。
15.2 序貫覆蓋
- 規(guī)則學(xué)習(xí)的目標(biāo)是產(chǎn)生一個(gè)能覆蓋盡可能多的樣例的規(guī)則集。最直接的做法是“序貫覆蓋”(sequential covering)，即逐條歸納：在訓(xùn)練集上每學(xué)到一條規(guī)則，就將該規(guī)則覆蓋的訓(xùn)練樣例去除，然后以剩下的訓(xùn)練樣例組成訓(xùn)練集重復(fù)上述過程。由于每次只處理一部分?jǐn)?shù)據(jù)，因此也被稱為“分治”(separate-and-conquer)策略。
- 基于窮盡搜索的做法在屬性和候選值較多時(shí)會由于組合爆炸而不可行?，F(xiàn)實(shí)任務(wù)中一般有兩種策略來產(chǎn)生規(guī)則：第一種是“自頂向下”(top-down)，即從比較一般的規(guī)則開始，逐漸添加新文字以縮小規(guī)則覆蓋范圍，直到滿足預(yù)定條件為止；亦稱為“生成-測試”(generate-then-test)法，是規(guī)則逐漸“特化”(specialization)的過程。第二種策略是“自底向上”(bottom-up)，即從比較特殊的規(guī)則開始，逐漸刪除文字以擴(kuò)大規(guī)則覆蓋范圍，直到滿足條件為止；亦稱為“數(shù)據(jù)驅(qū)動”(data-driven)法，是規(guī)則逐漸“泛化”(generalization)的過程。第一種策略是覆蓋范圍從大往小搜索規(guī)則，第二種策略則相反；前者通常更容易產(chǎn)生泛化性能較好的規(guī)則，而后者則更適合于訓(xùn)練樣本較少的情形，此外，前者對噪聲的魯棒性比后者要強(qiáng)得多。因此，在命題規(guī)則學(xué)習(xí)中通常使用一種策略，而第二種策略在一階規(guī)則學(xué)習(xí)這類假設(shè)空間非常復(fù)雜的任務(wù)上使用較多。
15.3 剪枝優(yōu)化
- 規(guī)則生成本質(zhì)上是一個(gè)貪心搜索過程，需有一定的機(jī)制來緩解過擬合的風(fēng)險(xiǎn)，最常見的做法是剪枝(pruning)。與決策樹相似，剪枝可發(fā)生在規(guī)則生長過程中，即“預(yù)剪枝”，也可以發(fā)生在規(guī)則產(chǎn)生后，即“后剪枝”。通常是基于某種性能度量指標(biāo)來評估增/刪邏輯文字前后的規(guī)則性能，或增/刪規(guī)則前后的規(guī)則集性能，從而判斷是否要進(jìn)行剪枝。
15.4 一階規(guī)則學(xué)習(xí)
- 受限于命題邏輯表達(dá)能力，命題規(guī)則學(xué)習(xí)難以處理對象之間的“關(guān)系”(relation)，而關(guān)系信息在很多任務(wù)中非常重要。例如顏色更深，觸感更硬。
- 一階規(guī)則學(xué)習(xí)能容易地引入領(lǐng)域知識，這是它相對于命題規(guī)則學(xué)習(xí)的另一大優(yōu)勢。在命題規(guī)則學(xué)習(xí)乃至一般的統(tǒng)計(jì)學(xué)習(xí)中，若欲引入領(lǐng)域知識，通常由兩種做法：在現(xiàn)有屬性的基礎(chǔ)上基于領(lǐng)域知識構(gòu)造出新屬性，或基于領(lǐng)域知識設(shè)計(jì)某種函數(shù)機(jī)制(例如正則化)來對假設(shè)空間加以約束。
- FOIL(First-Order Inductive Learner) 是著名的一階規(guī)則學(xué)習(xí)算法，它遵循序貫覆蓋框架且采用自頂向下的規(guī)則歸納策略。
15.5 歸納邏輯程序設(shè)計(jì)
- 歸納邏輯程序設(shè)計(jì) (Inductive Logic Programming, ILP) 在一階規(guī)則學(xué)習(xí)中引入了函數(shù)和邏輯表達(dá)式嵌套。一方面，這使得機(jī)器學(xué)習(xí)系統(tǒng)具備了更為強(qiáng)大的表達(dá)能力；另一方面，ILP 可看作用機(jī)器學(xué)習(xí)技術(shù)來解決基于背景知識的邏輯程序 (Logic program) 歸納，其學(xué)得的“規(guī)則”可被 PROLOG 等邏輯程序設(shè)計(jì)語言直接使用。
