歸納邏輯程式設計的發展論文

機器學習試圖利用計算機來模擬人類的學習行為，進而利用計算機的技術優勢給人類的生活帶來便利。歸納邏輯程式設計(Inductive Logic Programming，簡寫為ILP)是機器學習和邏輯程式設計的交叉研究領域。它在子句邏輯的框架下，通過讓計算機考察具體的事例，然後學習出能夠刻畫這些事例特有屬性的一般性規則。具體來說，計算機進行操作時，根據背景知識在限定的歸納假設空間中不斷地搜尋，最後得出一個理論(也即滿足某種語言偏向的子句集)，使得所有的正例都能被理論覆蓋，而負例項不被覆蓋。ILP作為機器學習的重要方法，已經在生物資訊學、自然語言處理、軟體工程等應用領域取得成功。

一、歸納邏輯程式設計的研究現狀

近年來，ILP得到很大的發展，其應用領域也不斷拓寬。一般說來，ILP最重要的應用領域之一是生物資訊學(Bioinformatics)。ILP之所以能適用於生物資訊學的任務，是因為它會將背景知識和結構資料考慮在內，學習產生人類能理解的知識。在學習蛋白質結構的摺疊的過程中，由於對其結構的學習很重要，所以需要找到能夠清晰描述其結構的語言。傳統的屬性-值方法無法描述物件問的關係，因而也就無法合理地表示蛋白質分子的三維結構，ILP的一階邏輯工具—子句邏輯是非常適合描述這種關係的語言，它在預測蛋白質結構資訊和蛋白質次級結構生成中發揮了很大作用。同時，在預測化合物誘變問題上，ILP也解決了傳統方法無法解決的結構關係問題。

機器學習一個非常獨特的應用領域是自然語言處理，它的主要任務在於建立各種自然語言處理系統，如文字自動識別系統、語音自動識別系統、機器翻譯系統、自然語言資訊檢索系統、自動索引系統等。在自然語言處理中，ILP的方法可以從文字中抽取複雜的關係資料，這是ILP優於其他機器學習技術的特點之一。ILP系統還常常為工程學、環境監控、軟體分析、模式學習和關係發現等領域的資料構造預測模型。雖然ILP與其他機器學習方法相比有一定的優勢，然而隨著科學技術發展和需求的增加，ILP在應用中也面臨許多挑戰:

首先，相比其他的機器學習系統來說，ILP系統對時問和空間有更高的要求，這使得ILP很難去處理大的資料集。因此，ILP應該努力尋求與隨機搜尋和並行處理技術等方法結合以處理結構複雜的資料集。

其次，隱馬爾科夫模型、動態貝葉斯網路、雙連詞和三連詞等技術都能充分表達任務中的內在概率，而ILP系統很少有表達、處理概率的能力，這也是ILP的重大不足之一。

最後，當背景知識和資料集用一階邏輯清晰表達出來時，ILP可以執行良好。但是當資料集是無法通過一階邏輯清晰表達的影象、視訊、音訊時，ILP就無能為力。就這一問題來說，ILP需要從約束邏輯程式設計中借鑑經驗，學習處理特殊資料格式的技術。

二、歸納邏輯程式設計的發展展望

ILP應用過程中所顯現出來的不足之處，使得ILP必須與其他研究領域的技術相結合，來提高它解決問題的能力。為了使ILP更好地完成歸納學習任務，戴維·培基提出了ILP未來發展的五個研究方向。

1 和貝葉斯網路

目前在人工智慧中，貝葉斯網路是處理不確定資訊和進行概率推理的最有力工具，它在很大程度上取代了傳統的基於規則的專家系統。人工智慧的研究者已經意識到概率的重要性，例如在醫療診斷中，幾乎沒有普遍真的醫學規律存在，也很少有完全正確的實驗可被利用。取而代之的是，概率被用來刻畫任務本身內在的不確定性。貝葉斯網路被特別設計出來去表達一些可能的概率分佈，並且嘗試對這些概率分佈進行推理。它已經在醫療診斷、拼寫糾錯、故障診斷等領域得到應用，也成為了國內外研究的新寵兒。

雖然貝葉斯網路有如此良好的應用，然而它本質上是命題的:變數集是確定且有限的，並且每個變數都有其確定的可能值域。這個事實限制了貝葉斯網路的應用。此外，當一個貝葉斯網用一個圖表表示時，圖表能夠刻畫的唯一關係是概率、或然性之間的條件依賴關係，它不能表達關係結構。要想使貝葉斯網路更好地為人類服務，必須試圖去拓展貝葉斯網路的'表達力，並且試圖用一個拓展的表達來進行歸納學習。實踐證明，這個拓展的表達結果是複雜的，還降低了一階邏輯的表達力。ILP研究者嘗試學習新增概率的子句，來拓展貝葉斯網的表達力，在一定程度上可以解決這一問題。目前，學者已經提出幾種可供選擇的子句表達方式，其中包括概率邏輯程式設計，隨機邏輯程式設計和概率約束邏輯程式設計。庫塞斯著手研究隨機邏輯程式設計的演算法和應用，而恩格和哈達維則研究貝葉斯網路的一階表達。一般說來，ILP和貝葉斯網路學習是正交的。ILP擅長處理關係域，而貝葉斯網路對概率處理的很好。因此，設想一個能夠具有貝葉斯網路學習和ILP二者優點的學習演算法的存在和應用是合理的，嘗試將貝葉斯網路學習和ILP結合的領域也應該是一個有前途、有希望的研究領域。

2 和隨機搜尋

隨著計算機技術的發展，人類收集資料、儲存資料的能力有了很大提高，對這些資料施以演算法搜尋處理，就能滿足人類不同的需求。隨機搜尋是指在目標位置基本服從均勻分佈的條件下，搜尋軌跡隨機且均勻散佈在目標分佈區域內的一種搜尋方式。常用的隨機搜尋演算法主要包括模擬退火演算法、進化策略、遺傳演算法。這些演算法求解時搜尋過程是非確定性的，演算法對約束函式及目標函式有限制，因而可以解決大規模複雜問題。

大部分ILP演算法搜尋由假設而定的一個子句格。它們尋找這樣一個子句—即能夠使子句覆蓋範圍的函式達到最大化的子句。根據它們如何搜尋這個子句格，這些ILP演算法被分為(基於最小一般泛化腳自底向上演算法和(基於求精的自頂向下演算法。演算法又根據它們是否利用貪婪搜尋、定向搜尋、接受搜尋來進行進一步劃分。在幾乎所有演算法中，以上這些搜尋方法都是確定性搜尋。然而，對於其他ILP之外的具有挑戰性的邏輯或人工智慧任務，隨機搜尋常常勝過確定性搜尋。1992年，考茨、塞爾曼、維斯克、米切爾以及其他學者對區域性搜尋演算法諸如LSAT, WSAT的可滿足性問題的研究，已經證實了隨機搜尋更具優勢。塞巴格和羅維洛從事於隨機匹配和定理證明，並且在誘變性研究上超越PROGOL程式，同時並沒有犧牲預測準確性和理解力。由此可以看出，隨機搜尋是ILP中一個有前途的研究方向。ILP可以嘗試與隨機搜尋演算法結合，利用隨機搜尋可選擇的形式去檢測子句格，嘗試解決不確定搜尋問題。

3 和約束邏輯程式設計

機器學習中廣為人知的成功理論之一是約束邏輯程式設計。這個理論成功的原因在於它整合邏輯和特殊目的的推理者或約束解決者的能力。前面提到的在ILP中加入概率的方法也可以理解為特殊目的推理者在貝葉斯網路片段形式中訴諸約束。關於約束問題，斯里尼瓦森和卡馬喬使用線性迴歸去構建一個約束，而克萊文和斯拉特利的工作是用樸素貝葉斯技術去構造一個約束。值得注意的是，除了在演繹過程中所需要的約束直譯器外，ILP還需要一個像類似線性迴歸一樣的“約束建構函式”。一般情況下，採用一個數據庫的標準邏輯解釋，這裡每一個關係是一個謂詞，並且關係中每一元組是由那個謂詞建立而來的一個基原子公式。現在假設資料庫中包含一些複雜資料的格式諸如影像，簡單的邏輯相似性就不能夠刻畫一系列影像的重要特徵，這時就需要基於特殊目的的影像處理技術。我們將ILP運用於處理電影時，首先需要構造特殊目的的約束直譯器，再用ILP技術對其進行處理。關於如何將約束加入到ILP研究中，需要關注阿蘭·弗裡希的工作。令人遺憾的是，他的工作沒有涉及如何確保歸納學習系統的效率，以及如何去設計約束直譯器的正確型別。這些問題正是留給我們去思考的，阿蘭·弗裡希至少給我們提供了一種考慮問題的思路。ILP確實需要從約束邏輯程式設計中借鑑經驗，學習處理特殊資料格式的技術，提高其處理問題和解決問題的能力。

4 和人類專家的交流

在從遠端通訊、分子生物學、製藥學等領域的資料庫中發現新知識的過程中，如果一個機器學習系統和人類專家能夠以團隊的形式合作，充分利用計算機的速度優勢及人類專家的知識和技術優勢，那麼在很大程度上會提高機器學習的效率和工作水平，促進新知識的發現。ILP系統的三個特性使得它在知識發現中能夠很自然地與人類專家進行合作:首先，ILP系統能夠利用可宣告的背景知識去構造假設，這就使得ILP和領域專家之間能夠展開合作。其次，基於特徵的學習系統要求使用者從描述創造例項的特徵開始，ILP系統允許結構例項根據組成它的物件以及這些物件之間的關係一起自然地被描述。一個分子的二維結構可以將它的原子作為物件，將原子之間的聯絡作為關係，這樣直接表示出來。三維結構可以通過新增距離關係而被表示。最後，ILP系統和命題邏輯學習者一樣，都具有輸出使用者可以理解的規則的能力，一些ILP系統甚至可以用英語返回規則。

儘管ILP系統呈現瞭如此多的有用特性，它在知識發現中作為人類的合作者，仍然還有許多缺點和不足。首先，大多數ILP系統在探試程式基礎上返回單一理論，因此丟掉了對一些領域專家來說有意義的子句。其次，ILP系統不能用人類合作者所使用的那種方式來回答人類專家的問題。它們用簡單的成批處理模式操作，採用一個數據庫作為輸入，並且在此基礎上返回一個假設。再次，ILP系統不會像人類合作者那樣對輸入的資料進行質疑。最後，人類專家能夠為假設提供知識豐富的辯護形式，例如將一個新的假設與現有的信念聯絡起來，ILP系統做不到這一點，它僅僅能提供正確的判斷。在知識發現和知識獲取的人機合作中，要克服ILP的不足，不僅需要邏輯和人工智慧的技術，還需要對邏輯主體進行研究，只有二者結合才能使機器與人類專家進行良好溝通。

5 和並行處理技術

面對今天覆雜的科學計算、各式各樣的圖象處理以及大量的訊號等問題，提高計算機的執行速度和縮短程式的執行時問至關重要。ILP系統對時問和空間有很高的要求，這使得ILP很難去處理大的資料集。並行處理技術的出現，為ILP處理大資料集提供瞭解決思路。並行處理系統由多個處理單元組成，通過特定方法可以將一個任務分成若干個子任務，分別由各處理單元完成。目前並行處理技術最顯著的是“貝奧武夫簇群技術”的普遍應用，以及個人計算機、工作站、智慧終端並行處理技術的使用。大衛·斯基利康在大容量同步並行模型之下發展了一個PROGOL的並行實施技術。艾倫·韋德在貝奧武夫簇群技術基礎上，再次進行自上而下的ILP研究。

並行處理技術的理想是在處理時問上的一個縮減，這裡處理時問是處理程式所用數量的一個線性函式，斜率接近於1。由於程式之間的管理自檢和資源的競爭，這個理想很難達到。一個好的並行策略，要求程式之間儘可能地相對獨立，儘量使得程式之間擁有較少的交流或資源共享。在測試資料時，在不同的處理器之間派發假設空間。更詳細地說，對一個完備的搜尋，一個並行ILP方案能夠產生一個戶主—使用者模式，這裡戶主將不同分段的假設空間指派給使用者，然後使用者用假設對資料進行測試。使用者反饋給戶主的所有假設在資料上達到一個預先最小評估值。當用戶完成自己的任務時，戶主繼續指派時空的新程式段，直到整個空間被開發。在使用者和戶主交流過程中，要考慮每次交流產生資料的成本，還要考慮戶主所花費的時問和戶主—使用者交流的時問。在相對較大的論域中，完備性搜尋期望使用者和戶主之間有儘量少的假設交流。如果戶主面對如此快速增長的假設空間片段，能夠以這樣一個方式將這些片段與使用者簡潔地交流是可能的;那麼整體開銷將是低的，處理時問也會縮減，這樣也就接近理想的並行處理模式。

三、結語

人類有對宇宙本源、生命本質、自我本體的好奇，對“機器如何模擬人類思維進行學習和思考”這一問題的探討，給機器學習添加了自然科學色彩。本文總結了歸納邏輯程式設計的發展現狀，對目前ILP發展過程存在的問題進行了詳細地闡述。雖然ILP已經在軟體工程、計算機網路、生物資訊學等眾多領域發揮作用，然而應用領域的迫切需求使得ILP仍需與貝葉斯網路、隨機搜尋、並行處理等技術結合，進一步推動科技的發展，進而為人類的生活帶來便利。