規(guī)則學(xué)習(xí)
原理
15.1 基本概念
- 機器學(xué)習(xí)中的“規(guī)則”(rule)通常是指語義明確骗随、能描述數(shù)據(jù)分布所隱含的客觀規(guī)律或領(lǐng)域概念硫椰、可寫成“若……环壤，則……”形式的規(guī)則邏輯磁餐∽愉觯“規(guī)則學(xué)習(xí)”(rule learning)是從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)出一組能用于對未見示例進行判別的規(guī)則。
- 與神經(jīng)網(wǎng)絡(luò)舆蝴、支持向量機這樣的“黑箱模型”相比，規(guī)則學(xué)習(xí)具有更好的可解釋性题诵，能使用戶更直觀地對判別過程有所了解洁仗。另一方面，數(shù)理邏輯具有極強的表達能力性锭，絕大多數(shù)人類知識都能通過梳理邏輯進行簡潔的刻畫和表達赠潦。例如“父親的父親是爺爺”這樣的知識不易用函數(shù)式描述，而用一階邏輯可以方便地描述草冈。因此她奥，規(guī)則學(xué)習(xí)能更自然地在學(xué)習(xí)過程中引入領(lǐng)域知識。此外怎棱，邏輯規(guī)則的抽象描述能力在處理一些高度復(fù)雜的AI任務(wù)時具有顯著的優(yōu)勢哩俭，例如在問答系統(tǒng)中有時可能遇到非常多、甚至無窮種可能的答案拳恋，此時若能基于邏輯規(guī)則進行抽象表述或者推理凡资，則將帶來極大的便利。
- 規(guī)則集合中的每條規(guī)則都可看作一個子模型谬运，規(guī)則集合是這些子模型的一個集成隙赁。當(dāng)同一個示例被判別結(jié)果不同的多條規(guī)則覆蓋時，稱發(fā)生了“沖突”(conflict)梆暖，解決沖突的辦法稱為“沖突消解”(conflict resolution)伞访。常用的沖突消解策略有投票法、排序法轰驳、元規(guī)則法等厚掷。投票法是將判別相同的規(guī)則數(shù)最多的結(jié)果作為最終結(jié)果弟灼。排序法是在規(guī)則集合上定義一個順序，在發(fā)生沖突時使用排序最前的規(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ā)生沖突時使用長度最小的規(guī)則”辛馆，然后根據(jù)元規(guī)則的知道來使用規(guī)則集。
- 此外豁延，從訓(xùn)練集學(xué)得的規(guī)則集合也許不能覆蓋所有可能的未見示例昙篙。這種情況在屬性數(shù)目很多時常出現(xiàn)。因此诱咏，規(guī)則學(xué)習(xí)算法通常會設(shè)置一條“默認規(guī)則”(default rule)苔可，由它來處理規(guī)則集合未覆蓋的樣本；例如為 R 增加一條默認規(guī)則：“未被規(guī)則1,2覆蓋的都不是好掛”袋狞。
- 從形式語言表達能力而言焚辅，規(guī)則可分為兩類：“命題規(guī)則”(propositional rule)和“一階規(guī)則”(first-order rule)。前者是由“原子命題”(propositional atom)和邏輯連接詞“與”苟鸯、“或”同蜻、“非”和“蘊含”(←)構(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)生一個能覆蓋盡可能多的樣例的規(guī)則集默责。最直接的做法是“序貫覆蓋”(sequential covering)，即逐條歸納：在訓(xùn)練集上每學(xué)到一條規(guī)則咸包，就將該規(guī)則覆蓋的訓(xùn)練樣例去除桃序，然后以剩下的訓(xùn)練樣例組成訓(xùn)練集重復(fù)上述過程。由于每次只處理一部分數(shù)據(jù)烂瘫，因此也被稱為“分治”(separate-and-conquer)策略葡缰。
- 基于窮盡搜索的做法在屬性和候選值較多時會由于組合爆炸而不可行。現(xiàn)實任務(wù)中一般有兩種策略來產(chǎn)生規(guī)則：第一種是“自頂向下”(top-down)忱反，即從比較一般的規(guī)則開始泛释，逐漸添加新文字以縮小規(guī)則覆蓋范圍，直到滿足預(yù)定條件為止温算；亦稱為“生成-測試”(generate-then-test)法怜校，是規(guī)則逐漸“特化”(specialization)的過程。第二種策略是“自底向上”(bottom-up)注竿，即從比較特殊的規(guī)則開始茄茁，逐漸刪除文字以擴大規(guī)則覆蓋范圍魂贬，直到滿足條件為止；亦稱為“數(shù)據(jù)驅(qū)動”(data-driven)法裙顽，是規(guī)則逐漸“泛化”(generalization)的過程付燥。第一種策略是覆蓋范圍從大往小搜索規(guī)則，第二種策略則相反愈犹；前者通常更容易產(chǎn)生泛化性能較好的規(guī)則键科，而后者則更適合于訓(xùn)練樣本較少的情形，此外漩怎，前者對噪聲的魯棒性比后者要強得多勋颖。因此，在命題規(guī)則學(xué)習(xí)中通常使用一種策略勋锤，而第二種策略在一階規(guī)則學(xué)習(xí)這類假設(shè)空間非常復(fù)雜的任務(wù)上使用較多饭玲。
15.3 剪枝優(yōu)化
- 規(guī)則生成本質(zhì)上是一個貪心搜索過程，需有一定的機制來緩解過擬合的風(fēng)險叁执，最常見的做法是剪枝(pruning)茄厘。與決策樹相似，剪枝可發(fā)生在規(guī)則生長過程中谈宛，即“預(yù)剪枝”次哈，也可以發(fā)生在規(guī)則產(chǎn)生后，即“后剪枝”入挣。通常是基于某種性能度量指標(biāo)來評估增/刪邏輯文字前后的規(guī)則性能，或增/刪規(guī)則前后的規(guī)則集性能硝拧，從而判斷是否要進行剪枝径筏。
15.4 一階規(guī)則學(xué)習(xí)
- 受限于命題邏輯表達能力，命題規(guī)則學(xué)習(xí)難以處理對象之間的“關(guān)系”(relation)障陶，而關(guān)系信息在很多任務(wù)中非常重要滋恬。例如顏色更深，觸感更硬抱究。
- 一階規(guī)則學(xué)習(xí)能容易地引入領(lǐng)域知識恢氯，這是它相對于命題規(guī)則學(xué)習(xí)的另一大優(yōu)勢。在命題規(guī)則學(xué)習(xí)乃至一般的統(tǒng)計學(xué)習(xí)中鼓寺，若欲引入領(lǐng)域知識勋拟，通常由兩種做法：在現(xiàn)有屬性的基礎(chǔ)上基于領(lǐng)域知識構(gòu)造出新屬性，或基于領(lǐng)域知識設(shè)計某種函數(shù)機制(例如正則化)來對假設(shè)空間加以約束妈候。
- FOIL(First-Order Inductive Learner) 是著名的一階規(guī)則學(xué)習(xí)算法敢靡，它遵循序貫覆蓋框架且采用自頂向下的規(guī)則歸納策略。
15.5 歸納邏輯程序設(shè)計
- 歸納邏輯程序設(shè)計 (Inductive Logic Programming, ILP) 在一階規(guī)則學(xué)習(xí)中引入了函數(shù)和邏輯表達式嵌套苦银。一方面啸胧，這使得機器學(xué)習(xí)系統(tǒng)具備了更為強大的表達能力赶站；另一方面，ILP 可看作用機器學(xué)習(xí)技術(shù)來解決基于背景知識的邏輯程序 (Logic program) 歸納纺念，其學(xué)得的“規(guī)則”可被 PROLOG 等邏輯程序設(shè)計語言直接使用贝椿。
