机器学习研究关系学习

中国科学院自动化研究所提纲什么是关系学习？关系学习中的一阶逻辑方法。关系学习中的概率方法。总结。中国科学院自动化研究所概述关系学习，译自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出现的地方是最零乱的地方。”发呆5分钟。。。做了一系列错误尝试。“原来是这样！”中国科学院自动化研究所启示人在解决问题时首先会对问题做表征，不同的表征会对应不同的解决策略，然后在“策略空间”搜索。计算机科学：人首先把问题做好表征，选好解决策略，交给计算机处理。机器学习：最好能由计算机根据数据性质选择解决策略。数据性质反映了数据的产生机理，与其对应的解决策略才能适应问题。中国科学院自动化研究所启示

空间的机器学习：数据的分布特性可由统计方法得知：线性或非线性？分布的性质？然后选择问题求解策略：线性回归？树？流形？相应于数据的kernel？可以看到，空间中的机器学习在逐渐把问题求解策略交给计算机来做，这样才是真正的机器学习。关系学习：我把这堆数据告诉你，你去搜吧！中国科学院自动化研究所启示因为没有通用的好的学习算法，因此需要让计算机根据数据选择模型（问题求解策略）。在空间模型选择问题已经得到了广泛深入的研究，相比之下，关系学习中几乎没有人去研究。原因：需要多种领域特异性知识。而空间中只有一种：几何。中国科学院自动化研究所在关系学习中，我们失去了与生俱来的直观，使得问题求解策略选择变为一个难题。如何对关系学习中的问题求解策略进行分类，并根据数据选择策略（如：中的线性，非线性）是这一领域发展的关键。否则关系学习将丧失理论价值，虽然很有实际意义。启示中国科学院自动化研究所总结本次讨论首先探讨了关系学习中存在的问题和难点，然后讨论了用于关系学习的逻辑方法和概率方法。如前所述，要较好地解决关系学习中的问题需要考虑到领域特异性知识，概率方法就是这样一种尝试，但是目前概率方法只是用来做参数学习，而结构学习才是这个问题的本质所在。不同的结构，不同的领域特异性知识如何整合在一起：Bongard问题，邻域填数字问题，分子性质预测问题……中国科学院自动化研究所总结传统机器学习无法解决的问题都丢给关系学习。因此关系学习只是一个很模糊的概念，其中涵盖了很多不同的问题。如