面向無標(biāo)記數(shù)據(jù)和相變的歸納邏輯程序設(shè)計(jì)學(xué)習(xí)算法.pdf

1、歸納邏輯程序設(shè)計(jì)(Inductive Logic Programming, ILP)是邏輯程序設(shè)計(jì)與機(jī)器學(xué)習(xí)相結(jié)合而產(chǎn)生的研究領(lǐng)域。ILP一方面繼承了邏輯程序設(shè)計(jì)穩(wěn)固的理論基礎(chǔ),另一方面繼承了機(jī)器學(xué)習(xí)面向應(yīng)用的特點(diǎn),采用比命題邏輯更具表達(dá)力的一階謂詞邏輯表示經(jīng)驗(yàn)數(shù)據(jù)和學(xué)習(xí)到的規(guī)則,而且可以非常自然地利用背景知識(shí),克服了傳統(tǒng)機(jī)器學(xué)習(xí)方法描述能力弱和無法利用背景知識(shí)的限制,為機(jī)器學(xué)習(xí)方法提供了更加深入的理論和方法,為人工智能的應(yīng)用領(lǐng)域提供了

2、強(qiáng)有力的技術(shù)支持,逐漸成為機(jī)器學(xué)習(xí)領(lǐng)域的前沿研究課題。
　　本文主要開展了ILP算法的研究。針對(duì)目前的ILP算法都屬于監(jiān)督學(xué)習(xí),要求有充分的訓(xùn)練數(shù)據(jù)保證泛化能力,而現(xiàn)實(shí)世界中容易得到的是無標(biāo)記數(shù)據(jù),研究了如何利用無標(biāo)記數(shù)據(jù)提高泛化能力。針對(duì)ILP的覆蓋測(cè)試問題是NP難題存在著相變現(xiàn)象,研究了相變框架下ILP算法的搜索寬度與學(xué)習(xí)成功率的關(guān)系,及根據(jù)相變理論初始化遺傳歸納邏輯程序設(shè)計(jì)算法的種群。本文的具體研究?jī)?nèi)容包括:
　　(1

3、)提出利用無標(biāo)記數(shù)據(jù)提高泛化能力的歸納邏輯程序設(shè)計(jì)算法
　　目前的ILP算法都屬于監(jiān)督學(xué)習(xí),需要大量的標(biāo)記數(shù)據(jù)以保證泛化能力,而在網(wǎng)頁分類等實(shí)際應(yīng)用中容易獲得的是無標(biāo)記數(shù)據(jù),本文提出利用無標(biāo)記數(shù)據(jù)提高泛化能力的 ILP算法—UDBILP。UDBILP首先利用初始標(biāo)記數(shù)據(jù)和背景知識(shí)初始化三個(gè)ILP分類器,然后迭代地用無標(biāo)記數(shù)據(jù)對(duì)三個(gè)分類器進(jìn)行精化,即如果兩個(gè)分類器對(duì)一個(gè)無標(biāo)記數(shù)據(jù)的標(biāo)記結(jié)果一致,則在一定條件下該數(shù)據(jù)將被標(biāo)記給另一個(gè)分

4、類器作為新的訓(xùn)練數(shù)據(jù)。標(biāo)準(zhǔn)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果表明UDBILP能夠利用無標(biāo)記數(shù)據(jù)提高泛化能力,并且算法最終分類錯(cuò)誤率低于NFOIL,KFOIL和ALEPH系統(tǒng)。網(wǎng)頁分類應(yīng)用實(shí)驗(yàn)結(jié)果表明UDBILP能夠利用無標(biāo)記網(wǎng)頁提高網(wǎng)頁分類性能,并且算法最終分類性能優(yōu)于Na?ve Bayes,Co-training和ICT-ILP。
　　(2)提出結(jié)合關(guān)系實(shí)例學(xué)習(xí)的歸納邏輯程序設(shè)計(jì)算法
　　同傳統(tǒng)半監(jiān)督學(xué)習(xí)算法一樣,UDBILP算法在利用無標(biāo)記

5、數(shù)據(jù)迭代學(xué)習(xí)過程中,可能存在誤標(biāo)記數(shù)據(jù),這些誤標(biāo)記數(shù)據(jù)影響泛化能力。本文進(jìn)一步提出結(jié)合關(guān)系實(shí)例學(xué)習(xí)(Relational Instance Based Learning, RIBL)和無標(biāo)記數(shù)據(jù)的歸納邏輯程序設(shè)計(jì)算法—RIBL_UDBILP。RIBL_UDBILP算法在UDBILP算法基礎(chǔ)上增加了自適應(yīng)的重新標(biāo)記過程。在重新標(biāo)記過程中,對(duì)每個(gè)新標(biāo)記的數(shù)據(jù),利用其他標(biāo)記數(shù)據(jù)訓(xùn)練RIBL后得到的分類器對(duì)其進(jìn)行重新標(biāo)記。選擇RIBL算法進(jìn)行重

6、新標(biāo)記的原因?yàn)镽IBL對(duì)噪聲數(shù)據(jù)和屬性值缺失數(shù)據(jù)是健壯的。在利用RIBL進(jìn)行重新標(biāo)記的過程中也可能引入誤標(biāo)記數(shù)據(jù),為此論文引入了兩個(gè)定量指標(biāo)來評(píng)價(jià)RIBL的正面和負(fù)面效應(yīng),并用自適應(yīng)策略控制是否執(zhí)行RIBL重新標(biāo)記過程,自適應(yīng)策略是一系列判定是否執(zhí)行RIBL重新標(biāo)記過程的充分條件的組合。各種情況下執(zhí)行RIBL重新標(biāo)記過程的充分條件在論文中以定理的形式給出,并且論文依據(jù)PAC學(xué)習(xí)理論證明了這些充分條件能夠保證分類錯(cuò)誤率迭代降低。標(biāo)準(zhǔn)數(shù)據(jù)集

7、實(shí)驗(yàn)結(jié)果表明RIBL_UDBILP具有更好的泛化能力。
　　(3)歸納邏輯程序設(shè)計(jì)算法搜索寬度與學(xué)習(xí)成功率關(guān)系研究
　　ILP算法依賴于覆蓋測(cè)試來評(píng)價(jià)一階規(guī)則的優(yōu)劣,覆蓋測(cè)試問題存在著相變現(xiàn)象。論文分析了相變對(duì)ILP算法學(xué)習(xí)成功率的影響,指出相變是導(dǎo)致ILP算法學(xué)習(xí)成功率低的根本原因,在相變框架下研究了搜索寬度與學(xué)習(xí)成功率關(guān)系。采用兩個(gè)具有代表性的ILP算法FOIL和KFOIL,將其搜索寬度參數(shù)分別設(shè)定為1,5,10,20,

8、30。在451個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),對(duì)每個(gè)數(shù)據(jù)集,分別計(jì)算ILP算法在不同搜索寬度下的學(xué)習(xí)成功率。實(shí)驗(yàn)結(jié)果表明增加搜索寬度并不能從本質(zhì)上提高ILP算法的學(xué)習(xí)成功率。最后,通過分析ILP系統(tǒng)迭代過程的相變現(xiàn)象給出了增加搜索寬度不能從本質(zhì)上提高學(xué)習(xí)成功率的內(nèi)在原因,從而進(jìn)一步驗(yàn)證了Botta提出的相變導(dǎo)致ILP系統(tǒng)學(xué)習(xí)成功率低的結(jié)論。
　　(4)基于遺傳算法的歸納邏輯程序設(shè)計(jì)算法
　　同傳統(tǒng)機(jī)器學(xué)習(xí)算法一樣,歸納邏輯程序設(shè)計(jì)算法也

9、可看作是一個(gè)搜索問題。采用遺傳算法搜索假設(shè)空間能夠克服確定性搜索算法容易陷入局部最優(yōu)的不足,本文提出基于遺傳算法的歸納邏輯程序設(shè)計(jì)算法—PT_NFF_GILP。PT_NFF_GILP在相變區(qū)域內(nèi)而不是在整個(gè)假設(shè)空間內(nèi)隨機(jī)生成初始種群,這是因?yàn)闅w納邏輯程序設(shè)計(jì)算法生成的假設(shè)總是在相變區(qū)域內(nèi)或附近。要在相變區(qū)域內(nèi)隨機(jī)生成初始種群必須要定量地確定相變的位置,本文采用統(tǒng)計(jì)分析的方法確定了相變的位置。PT_NFF_GILP的適應(yīng)度函數(shù)不僅考慮了規(guī)