面向無標記數據和相變的歸納邏輯程序設計學習算法.pdf

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

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

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

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

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

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

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

8、30。在451個數據集上進行實驗,對每個數據集,分別計算ILP算法在不同搜索寬度下的學習成功率。實驗結果表明增加搜索寬度并不能從本質上提高ILP算法的學習成功率。最后,通過分析ILP系統迭代過程的相變現象給出了增加搜索寬度不能從本質上提高學習成功率的內在原因,從而進一步驗證了Botta提出的相變導致ILP系統學習成功率低的結論。
　　(4)基于遺傳算法的歸納邏輯程序設計算法
　　同傳統機器學習算法一樣,歸納邏輯程序設計算法也

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