ch15規(guī)則學(xué)習(xí)-周志華

戴望州第十五章：規(guī)則學(xué)習(xí)大綱基本概念序貫覆蓋剪枝優(yōu)化一階規(guī)則學(xué)習(xí)歸納邏輯程序設(shè)計基本概念機(jī)器學(xué)習(xí)里的規(guī)則：若……，則…….回歸分類聚類……若，則若，則；若，則若，則邏輯規(guī)則規(guī)則集充分性與必要性沖突消解：順序規(guī)則、缺省規(guī)則、元規(guī)則基本概念規(guī)則頭規(guī)則體邏輯蘊(yùn)含符目標(biāo)概念（邏輯文字）邏輯文字邏輯“與”讀作：若（文字1且文字2且…），則（目標(biāo)概念）成立原子公式

基本概念命題邏輯命題規(guī)則原子命題：邏輯連詞：一階邏輯一階規(guī)則常量：變量：（n元）謂詞/函數(shù)：項：原子公式：邏輯連詞邏輯量詞：大綱基本概念序貫覆蓋剪枝優(yōu)化一階規(guī)則學(xué)習(xí)歸納邏輯程序設(shè)計序貫覆蓋+++++++++-+++++++++++-----------------------------------在訓(xùn)練集上每學(xué)到一條規(guī)則，就將改規(guī)則覆蓋的樣例去除，然后以剩下的樣例組成訓(xùn)練集重復(fù)上述過程（分治策略）。序貫覆蓋+++++++++-+++++++++++-----------------------------------序貫覆蓋+++++++++-++-----------------------------------Rule1序貫覆蓋+++++++++-++-----------------------------------Rule1序貫覆蓋++++-++-----------------------------------Rule1Rule2序貫覆蓋++++-++-----------------------------------Rule1Rule2序貫覆蓋------------------------------------Rule1Rule2Rule4Rule3大綱基本概念序貫覆蓋單條規(guī)則學(xué)習(xí)剪枝優(yōu)化一階規(guī)則學(xué)習(xí)歸納邏輯程序設(shè)計單條規(guī)則學(xué)習(xí)目標(biāo)：尋找一組最優(yōu)的邏輯文字來構(gòu)成規(guī)則體本質(zhì)：搜索問題搜索空間大，易造成組合爆炸方法：自頂向下：一般到特殊（泛化）自底向上：特殊到一般（特化）單條規(guī)則學(xué)習(xí)自頂向下策略：一般到特殊（特化）+++++++++-+++++++++++-----------------------------------單條規(guī)則學(xué)習(xí)自頂向下策略：一般到特殊（特化）+++++++++-+++++++++++-----------------------------------單條規(guī)則學(xué)習(xí)自頂向下策略：一般到特殊（特化）+++++++++-+++++++++++-----------------------------------Rule1單條規(guī)則學(xué)習(xí)自頂向下策略：一般到特殊（特化）+++++++++-+++++++++++-----------------------------------Rule1Rule2Rule3Rule4單條規(guī)則學(xué)習(xí)自底向上策略：特殊到一般（泛化）+++++++++-+++++++++++-----------------------------------單條規(guī)則學(xué)習(xí)自底向上策略：特殊到一般（泛化）+++++++++-+++++++++++-----------------------------------單條規(guī)則學(xué)習(xí)自底向上策略：特殊到一般（泛化）+++++++++-+++++++++++-----------------------------------Rule1單條規(guī)則學(xué)習(xí)規(guī)則評判：增加/刪除哪一個候選文字準(zhǔn)確率信息熵增益（率）基尼系數(shù)……規(guī)避局部最優(yōu)集束搜索：每次保留最優(yōu)的多個候選規(guī)則……大綱基本概念序貫覆蓋剪枝優(yōu)化一階規(guī)則學(xué)習(xí)歸納邏輯程序設(shè)計序貫覆蓋（非最優(yōu)）+++++++++-+++++++++++---------------------------------貪心算法導(dǎo)致的非最優(yōu)情況序貫覆蓋（非最優(yōu)）+++++++++-+++++++++++---------------------------------序貫覆蓋（非最優(yōu)）+++++++++-+++++++++++---------------------------------Rule1序貫覆蓋（非最優(yōu)）+++++++++-+++++++++++---------------------------------Rule1序貫覆蓋（非最優(yōu)）+++++++++-+++++++++++---------------------------------Rule1Rule2序貫覆蓋（非最優(yōu)）+++++++++-+++++++++++---------------------------------Rule1Rule2Rule3Rule4Rule5剪枝優(yōu)化預(yù)剪枝似然率統(tǒng)計量[ClarkandNiblett,1989]后剪枝減錯剪枝（REP）[BrunkandPazzani,1991]窮舉所有可能的剪枝操作（刪除文字，刪除規(guī)則），復(fù)雜度非常高用驗證集反復(fù)剪枝直到準(zhǔn)確率無法提高二者結(jié)合IREP[FürnkranzandWidmer,1994]每生成一條新規(guī)則即對其進(jìn)行REP剪枝IREP*[Cohen,1995]對IREP的改進(jìn)RIPPER[Cohen,1995]大綱基本概念序貫覆蓋剪枝優(yōu)化RIPPER一階規(guī)則學(xué)習(xí)歸納邏輯程序設(shè)計RIPPER[Cohen,1995]+++++++++-+++++++++++-----------------------------------Rule1Rule2Rule3Rule4IREP*生成規(guī)則集覆蓋了兩個負(fù)樣本！RIPPER[Cohen,1995]+++++++++-+++++++++++-----------------------------------IREP*生成規(guī)則集選取一條規(guī)則，找到其覆

蓋的樣例Rule2Rule3Rule4RIPPER[Cohen,1995]+++++++++-+++++++++++-----------------------------------IREP*生成規(guī)則集選取該規(guī)則，找到其覆

蓋的樣例重新生成規(guī)則Rule2Rule3Rule4RIPPER[Cohen,1995]+++++++++-+++++++++++-----------------------------------IREP*生成規(guī)則集選取該規(guī)則，找到其覆

蓋的樣例重新生成規(guī)則特化原規(guī)則再泛化Rule2Rule3Rule4RIPPER[Cohen,1995]+++++++++-+++++++++++-----------------------------------生成規(guī)則集選取一條規(guī)則，找到其覆

蓋的樣例重新生成規(guī)則特化原規(guī)則再泛化把原規(guī)則和新規(guī)則分別置

入規(guī)則集進(jìn)行評價，留下

最好的Rule2Rule3Rule4RIPPER[Cohen,1995]+++++++++-+++++++++++-----------------------------------生成規(guī)則集選取一條規(guī)則，找到其覆

蓋的樣例重新生成規(guī)則特化原規(guī)則再泛化把原規(guī)則和新規(guī)則分別置

入規(guī)則集進(jìn)行評價，留下

最好的。4.反復(fù)優(yōu)化直到無法進(jìn)步RIPPER將所有規(guī)則放在一起優(yōu)化，通過全局的考慮來緩解序貫覆蓋的局部性Rule3Rule4大綱基本概念序貫覆蓋剪枝優(yōu)化一階規(guī)則學(xué)習(xí)歸納邏輯程序設(shè)計一階規(guī)則學(xué)習(xí)“一階”的目的：描述一類物體的性質(zhì)、相互關(guān)系實際應(yīng)用中很難量化顏色、…、敲聲的屬性值一階規(guī)則學(xué)習(xí)利用一階關(guān)系來挑“更好的”瓜21一般情況下可以省略全稱量詞一階規(guī)則學(xué)習(xí)屬性-值(Attribute-value)數(shù)據(jù)【命題邏輯】關(guān)系型(Relational)數(shù)據(jù)【一階邏輯】背景知識樣例FOIL[Quinlan,1990]序貫覆蓋生成規(guī)則集自頂向下學(xué)習(xí)單條規(guī)則候選文字需考慮所有可能的選項規(guī)則生長的評判標(biāo)準(zhǔn)為FOIL增益后剪枝優(yōu)化規(guī)則集能否引入新變量？能否使用否定文字？能否允許遞歸？能否引入函數(shù)嵌套？：p(f(f…(f(X))))大綱基本概念序貫覆蓋剪枝優(yōu)化一階規(guī)則學(xué)習(xí)歸納邏輯程序設(shè)計歸納邏輯程序[Muggleton,1991]目標(biāo)：完備地學(xué)習(xí)一階規(guī)則（Horn子句）仍然以序貫覆蓋方法學(xué)習(xí)規(guī)則集一般采用自底向上策略學(xué)習(xí)單條規(guī)則不需要列舉所有可能的候選規(guī)則對目標(biāo)概念的搜索維持在樣例附近的局部區(qū)域自頂向下策略的搜索空間對于規(guī)則長度呈指數(shù)級增長最小一般泛化(LGG)[Plotkin,1970]“泛化”：將覆蓋率低的規(guī)則變換為覆蓋率高的規(guī)則“一般”：覆蓋率盡可能高“最小”：變換時對原規(guī)則的改動盡可能小尋找兩條規(guī)則LGG的步驟：找出兩條規(guī)則中涉及相同謂詞的文字考察謂詞后括號里的項：

s,t不是謂詞相同的項，則，V為任意未出現(xiàn)過的變量s,t為謂詞相同的項，遞歸考察其括號內(nèi)的項刪除沒有相同謂詞出現(xiàn)的文字最小一般泛化(LGG)[Plotkin,1970]最小一般泛化(LGG)[Plotkin,1970]其他基于LGG的ILP算法考慮否定文字不同的初始化選擇多條特殊規(guī)則考慮所有背景知識（RLGG）[Plotkin,1971]…歸納演繹逆歸結(jié)[MuggletonandBuntine,1988]演繹(deduction)VS歸納(induction)“……猜想是很不好的習(xí)慣，它有害于作邏輯的推理。你所以覺得奇怪，是因為你沒有了解我的思路，沒有注意到往往能推斷出大事來的那些細(xì)小問題（thesmallfacts

uponwhichlargeinferences

maydepend）。舉例來說吧，我開始時曾說你哥哥的行為很不謹(jǐn)慎。請看這只表，不僅下面邊緣上有凹痕兩處，整個表的上面還有無數(shù)的傷痕，這是因為慣于把表放在有錢幣、鑰匙一類硬東西的衣袋里的緣故。對一只價值五十多鎊的表這樣不經(jīng)心，說他生活不檢點，總不算是過分吧！……?！毙蹇恕じ柲λ寡堇[法研究（Thescienceofdeduction）——《四簽名》規(guī)則（一般）事實（特殊）目標(biāo)事實（特殊）歸結(jié)與逆歸結(jié)[MuggletonandBuntine,1988]演繹：歸結(jié)原理[Robinson,1965]歸納：逆歸結(jié)如何考慮帶變量的邏輯表達(dá)式？已成立的事實規(guī)則歸結(jié)掉（消去）已滿足的文字p.從此若需驗證r是否可滿足，只需驗證q是否成立.歸結(jié)項歸結(jié)商演繹：驗證邏輯表達(dá)式的可滿足性輸入輸出一階逆歸結(jié)置換：用項替換變量復(fù)合置換：逆置換：合一：通過置換讓兩個表達(dá)式相等最一般合一置換（MGU）：任意一個合一置換都是MGU的復(fù)合置換MGU一階逆歸結(jié)一階歸結(jié)：當(dāng)，一階逆歸結(jié)：例子（p.353）：找一個不在歸結(jié)項中的使存在一個解：使得逆歸結(jié)[MuggletonandBuntine,1988]四種完備的逆歸結(jié)操作逆歸結(jié)[MuggletonandBuntine,1988]吸收吸收#1吸收#2逆歸結(jié)[MuggletonandBuntine,1988]辨識逆歸結(jié)[MuggletonandBuntine,1988]內(nèi)構(gòu)逆歸結(jié)[MuggletonandBuntine,1988]內(nèi)構(gòu)逆歸結(jié)[MuggletonandBuntine,1988]互構(gòu)