中國科學院自動化研究所提綱什么是關系學習？關系學習中的一階邏輯方法。關系學習中的概率方法?？偨Y。中國科學院自動化研究所概述關系學習，譯自RelationalLearning.最近十年發展起來的一類機器學習問題及其方法的統稱。關系學習中同一樣本的各個屬性之間有著復雜的關系，或者不同樣本相互之間不獨立，這表明了樣本集上的某種結構．復雜內在結構的問題：文本數據挖掘，生物信息學，交通工程等。中國科學院自動化研究所譯作關系學習不妥。誤解：代數里的關系（甚至是二元關系）。RelationalLearning中的關系:一種關聯，用一階邏輯的語言就是謂詞。為方便起見仍稱為關系學習。概述中國科學院自動化研究所概述與其他能用屬性-值方式表示的機器學習問題不同，關系學習中的問題一般無法如此表示：a.每個樣本不僅由屬性描述，而且其中還要用關系描述b.屬性不等長。中國科學院自動化研究所CC土壤沉積物空氣水結構決定性質中國科學院自動化研究所屬性屬性之間的關系預測值單表中國科學院自動化研究所C(1)C(2)H(8)Cl(7)Cl(3)Cl(4)H(5)Cl(6)中國科學院自動化研究所中國科學院自動化研究所形式化描述中國科學院自動化研究所形式化描述中國科學院自動化研究所形式化描述中國科學院自動化研究所顧客類別預測中國科學院自動化研究所提綱中國科學院自動化研究所形式化描述中國科學院自動化研究所中國科學院自動化研究所

傳統機器學習不易融入背景知識樣本來自同一模型樣本之間i.i.d屬性順序固定屬性數目固定

實際問題易于融入背景知識樣本可以來自不同模型不一定i.i.d屬性順序不定屬性數目不定

引發困難效果差，可理解性差得到錯誤模型得到錯誤模型組合爆炸無法解決中國科學院自動化研究所關系學習中的一階邏輯方法中國科學院自動化研究所ILP（歸納邏輯程序）是關系學習領域的研究人員最先采用的解決方法。中國科學院自動化研究所中國科學院自動化研究所以下討論涉及到一階邏輯中的基本定義,請參閱《機器學習》(TomM.Mitchell)第204頁表10-3中國科學院自動化研究所每個良構的表達式由常量（如Joe,23),變量（如x），謂詞（如在Female(Mary)中的Female）和函數（age(Mary)中的age)組成。項（term）為任意常量，任意變量或任意應用到項集合上的函數，例如：Mary,x,age(Mary),age(x).文字（literal）是應用到項集合上的任意謂詞或其否定。例如：Female(Mary),~Female(x),Greater_than(age(Mary),20)基本文字（groundliteral）是不包含任何變量的文字（如，~Female(Joe)）負文字（negativeliteral）是包含任何否定謂詞的文字（如：～Female(Joe)）正文字（positiveliteral）是不包含否定符號的文字（如：Female(Joe)）一階邏輯中的基本定義中國科學院自動化研究所子句（clause）是多個文字的析取式，M1∨M2∨…∨Mn，其中的所有變量是全稱量化的。Horn子句是一個如下形式的表達式：H(L1∧L2∧…∧Ln),其中L1,L2,…Ln為正文字，可以等價地寫為析取式：

H∨~L1∨~L2∨…∨~Ln置換（substitution）是一個將某些變量替換為某些項的函數。例如：置換{x/3,y/z}把變量x替換為項3并把變量y替換為項z。給定一個置換

和一個文字L，使用L表示應用置換后的結果。邏輯程序（LogicProgram）：是一階邏輯的一個子集，邏輯程序由子句構成，即一系列的if/then規則ILP的任務便是通過歸納學習的方法學習到用邏輯程序表達的概念。中國科學院自動化研究所中國科學院自動化研究所學習規則集合學習能表示為if-then規則的集合。其中最重要的一種是學習包含變量的規則集合，或者稱為一階Horn子句集，由于該集合可被解釋為邏輯編程語言PROLOG中的程序，學習的過程常被稱為歸納邏輯程序（ILP）。PROLOG是一個與通用圖靈機等價的編程語言。學習規則集合的一種方法是學習決策樹，然后轉化為等價的規則集合；或者是遺傳算法中，用位串編碼每個規則集合，然后用遺傳搜索算子來探索整個假設空間。在一階規則學習中直接學習規則，如：

IFParent(x,y)THENAncestor(x,y)IFParent(x,z)andAncestor(z,y)THENAncestor(x,y)

以上兩條規則緊湊地描述了一個遞歸函數，很難用決策樹或者其他的命題方法表示，決策樹一般只能學到特殊的規則。中國科學院自動化研究所序列覆蓋算法該算法學習規則集的策略為：學習一個規則，移去它覆蓋的數據，再重復這一過程，被稱為序列覆蓋(sequentialcovering)算法。假設已有一個子程序LEARN-ONE-RULE,它的輸入為正例和反例，然后輸出單個規則，它能夠覆蓋許多正例而覆蓋很少的反例。要求有較高的精確度，但是不必有較高的覆蓋度。在所有可用訓練樣本上執行LEARN-ONE-RULE子程序，再移去由其學習到的規則覆蓋的正例，然后在剩余的訓練樣本上執行，學習第二個規則。該過程重復多次，直到最后學習到析取規則集。它們共同覆蓋正例，覆蓋程度達到所希望的比例。將學習析取規則集的問題化簡為一系列更簡單的問題，每個子問題只需要學習單個合取規則。貪婪搜索，沒有回溯，結果不一定最佳。中國科學院自動化研究所LEARN-ONE-RULE實現LEARN-ONE-RULE的一個有效途徑是將假設空加搜索過程設計成與ID3算法相似的方式，但是每一步只沿著最有希望的分支進行。搜索開始于最一般的規則前件，然后加入那些在訓練樣例上性能改進最大的屬性測試。然后重復該過程，貪婪地加入第二個屬性測試，依此類推。每個合取假設對應于待學習規則的候選前件集合，由其覆蓋的樣例的熵來評估。中國科學院自動化研究所FOIL(Quinlan,1990)

序列覆蓋和LEARN-ONE-RULE算法在一階表示上的自然擴展。FOIL學習的假設為一階規則集的子集，類似Horn子句，但有兩個不同：文字不允許含有函數符號（減小了假設空間搜索的復雜度）；規則體中的文字可為負文字。可以學習快速排序算法QUICKSORT的遞歸定義，以及學習從合法棋盤狀態中區分出非法狀態。FOIL算法由兩層循環構成，外層循環對應于序列覆蓋算法，每次學習一個新規則，將此規則覆蓋的正例移去，再學習下一規則。內層循環是LEARN-ONE-RULE的另一種形式。中國科學院自動化研究所中國科學院自動化研究所候選特化式的生成中國科學院自動化研究所編碼正例所需的最小位數,隨著規則越來越強,所需位數越來越少中國科學院自動化研究所空規則,對于一切x,y,都有daughter(x,y)成立中國科學院自動化研究所左圖是一個有向圖；下圖是在命題邏輯中表示“twonodesarelinkedtoEachother”的概念。中國科學院自動化研究所中國科學院自動化研究所中國科學院自動化研究所中國科學院自動化研究所＋中國科學院自動化研究所＋中國科學院自動化研究所＋注：到此已學習到所有正樣本，而且不覆蓋負樣本，算法結束。中國科學院自動化研究所FOIL的特點搜索子句的過程完全由數據驅動，不需要邏輯證明。采用貪婪搜索策略，且每次只考慮當前的一個最優解。可以使用遞歸定義，但會出現無限遞歸，無法徹底避免。采用function-freeHorn子句，限制了表達能力。無法假設新的謂詞，但INDUCE(Michalski,1980)和GIGOL(MuggletonandBuntine,1988)中有引入新謂詞的機制，當該謂詞對簡化定義有幫助時。中國科學院自動化研究所小結邏輯僅僅是一種表達語言，真正的人工智能必須能理解語義，我們在選擇背景知識，假設空間和搜索路徑時其實已經把語義隱含其中。ILP研究領域中的問題和我們目前碰到的問題不同，ILP中的數據形式復雜，但是規則相對簡單，往往可以加入領域知識，而且可以被人理解。中國科學院自動化研究所關系學習中的概率方法中國科學院自動化研究所領域知識已知時,往往可以確定結構,這時估計參數就可以了,但盡管如此,仍是一個NP難題,只能得到近似最優解中國科學院自動化研究所中國科學院自動化研究所血型M-染色體P-染色體污染血型M-染色體P-染色體血型M-染色體P-染色體結果人人人母親父親測試條件概率密度CPD中國科學院自動化研究所BayesianLogicPrograms

BLPs的構成：一個由Bayesian子句構成的有限集。每個Bayesian子句上都定義一個條件轉移概率。

properrandomvariables:LH(B).dependencygraph.CPDs.中國科學院自動化研究所BayesianLogicPrograms把每個基本原子映射成隨機變量，且該映射是一一的。分為參數學習和結構學習兩部分。輸入是數據和初始的貝葉斯網絡（需要細化）。以下是例子。中國科學院自動化研究所BayesianLogicPrograms

中國科學院自動化研究所BayesianLogicPrograms

中國科學院自動化研究所BayesianLogicPrograms

中國科學院自動化研究所BayesianLogicPrograms

中國科學院自動化研究所BayesianLogicPrograms

中國科學院自動化研究所BayesianLogicPrograms

中國科學院自動化研究所BayesianLogicPrograms

中國科學院自動化研究所總結中國科學院自動化研究所如：給出個樣本，每個樣本都由這六個量（對象，對象間的關系，類別）描述，此處假設了樣本長度相等。目標是學出,此處是映射，不是狹義上的函數。每個由一系列的屬性描述。關系學習問題的實質中國科學院自動化研究所假設樣本間滿足i.i.d.,則不會涉及到，所以很難直接應用關系代數。除了一些很特殊的問題，如：Bongard問題，其中每個樣本都具有形式：每個樣本的n不必相等，.

關系學習問題的實質中國科學院自動化研究所關系學習問題的實質一般的關系學習問題就是給出n個樣本，每個都由下式描述：每個由一些屬性描述：目標是找到映射關系。注意：是建立在對象上的，不是建立在對象的屬性上的，它們反映了對象的其他屬性。（請看下頁的例子）

中國科學院自動化研究所舉例：Bongard問題（分類）給定若干正負樣本，目標規則：如果有一個紅色的圓套在一個藍色的方形內，則該樣本是正樣本。中國科學院自動化研究所舉例：Bongard問題（分類）

注：沒有寫出的謂詞取值為False.

中國科學院自動化研究所舉例：Bongard問題（分類）

中國科學院自動化研究所舉例：Bongard問題（分類）

中國科學院自動化研究所舉例：Bongard問題（分類）

中國科學院自動化研究所舉例：Bongard問題（分類）

中國科學院自動化研究所舉例：Bongard問題（分類）

中國科學院自動化研究所Bongard問題的涵義

是建立在之間，但卻不是建立在的屬性（形狀，顏色）之間。其實是建立在一個“隱空間”上（坐標），這也正是為什么謂詞不能由函數替代。人類可以知道該空間是什么（根據我們的先驗知識），計算機卻無法理解，無法直接對計算，因此才需要引入一階邏輯（也就是謂詞）。中國科學院自動化研究所一階邏輯帶來了什么？便于人理解，從人的角度抓住了問題的本質，數據提供，結果解釋都很方便。適合人的不一定適合計算機，如上例中計算機無法真正理解的語義，因為要理解語義，就必須有“隱空間”，這正是我們無法提供的。人：難度低；計算機：難度高中國科學院自動化研究所提供“隱空間”？一般會變得更難。采用,我們其實是暗示給計算機解決問題的思路，否則它還得從數據中提取出類似于的一種表達（要耗費大量計算，而且不一定能成功）。而且結果不易解釋。人：難度高計算機：難度高中國科學院自動化研究所關鍵是否存在一種中間地帶，使得計算機和人類對問題的理解一致，讓計算機學會人處理問題的方式？人：難度低計算機：難度低中國科學院自動化研究所關系學習的難點認知心理學理論：有效解決問題往往需要加領域特異性知識。與空間中的機器學習相比，關系學習中不易加入領域特異性知識。中國科學院自動化研究所幾何－－空間的領域特異性知識在空間的機器學習問題中，我們可以充分利用幾何直觀，一切抽象方法都建立在幾何直觀的基礎上。（SVM，流形，統計方法，甚至是神經網絡）。由此來設計可以在計算機上運行的算法。幾何直觀也是一種領域特異性知識，因為我們生活在空間內，導致數學建立在空間上，所以我們沒有意識到這種特異性。

中國科學院自動化研究所關系學習的難點（續）但是在relationallearning中我們失去了先天的優勢（想象一下人來求解BongardProblem,當每個樣本中對象數目巨大時），只能無目的地搜索，又如何能去指導計算機？中國科學院自動化研究所人如何解決關系學習的問題？一個小游戲：紅色區域內的數字應該是幾？

中國科學院自動化研究所我是如何解決該問題的“一些多邊形，有凸有凹，莫非是多邊形邊數？”“不對。。。，想想也不會這么簡單”“5出現的地方是最零亂的地方?！卑l呆5分鐘。。。做了一系列錯誤嘗試?！霸瓉硎沁@樣！”中國科學院自動化研究所啟示人在解決問題時首先會對問題做表征，不同的表征會對應不同的解決策略，然后在“策略空間”搜索。計算機科學：人首先把問題做好表征，選好解決策略，交給計算機處理。機器學習：最好能由計算機根據數據性質選擇解決策略。數據性質反映了數據的產生機理，與其對應的解決策略才能適應問題。中國科學院自動化研究所啟示

空間的機器學習：數據的分布特性可由統計方法得知：線性或非線性？分布的性質？然后選擇問題求解策略：線性回歸？樹？流形？相應于數據的kernel？可以看到，空間中的機器學習在逐漸把問題求解策略交給計算機來做，這樣才是真正的機器學習。關系學習：我把這堆數據告訴你，你去搜吧！中國科學院自動化研究所啟示因為沒有通用的好的學習算法，因此需要讓計算機根據數據選擇模型（問題求解策略）。在空間模型選擇問題已經得到了廣泛深入的研究，相比之下，關系學習中幾乎沒有人去研究。原因：需要多種領域特異性知識。而空間中只有一種：幾何。中國科學院自動化研究所在關系學習中，我們失去了與生俱來的直觀，使得問題求解策略選擇變為一個難題。如何對關系學習中的問題求解策略進行分類，并根據數據選擇策略（如：中的線性，非線性）是這一領域發展的關鍵。否則關系學習將喪失理論價值，雖然很有實際意義。啟示中國科學院自動化研究所總結本次討論首先探討了關系學習中存在的問題和難點，然后討論了用于關系學習的邏輯方法和概率方法。如前所述，要較好地解決關系學習中的問題需要考慮到領域特異性知識，概率方法就是這樣一種嘗試，但是目前概率方法只是用來做參數學習，而結構學習才是這個問題的本質所在。不同的結構，不同的領域特異性知識如何整合在一起：Bongard問題，鄰域填數字問題，分子性質預測問題……中國科學院自動化研究所總結傳統機器學習無法解決的問題都丟給關系學習。因此關系學習只是一個很模糊的概念，其中涵蓋了很多不同的問題。如