中国科学院研究生院 2006年6月27日 机器学习研究 第五讲：关系学习 韩彦军 中国科学院自动化研究所.

Presentation on theme: "中国科学院研究生院 2006年6月27日 机器学习研究 第五讲：关系学习 韩彦军 中国科学院自动化研究所."— Presentation transcript:

1 中国科学院研究生院 2006年6月27日 机器学习研究 第五讲：关系学习 韩彦军 中国科学院自动化研究所

2 提纲 中国科学院自动化研究所 什么是关系学习？ 关系学习中的一阶逻辑方法。 关系学习中的概率方法。 总结。

3 概述 关系学习，译自Relational Learning.最近十年发展起来的一类机器学习问题及其方法的统称。
中国科学院自动化研究所 概述 关系学习，译自Relational Learning.最近十年发展起来的一类机器学习问题及其方法的统称。 关系学习中同一样本的各个属性之间有着 复杂的关系 ，或者不同样本相互之间不独 立，这表明了样本集上的某种结构． 复杂内在结构的问题：文本数据挖掘，生物信息学，交通工程等。

4 概述 译作关系学习不妥。 误解：代数里的关系（甚至是二元关系） 。
中国科学院自动化研究所 概述 译作关系学习不妥。 误解：代数里的关系（甚至是二元关系） 。 Relational Learning中的关系 :一种关联，用一阶逻辑的语言就是谓词。 为方便起见仍称为关系学习。

5 中国科学院自动化研究所 概述 与其他能用属性-值方式表示的机器学习问题不同，关系学习中的问题一般无法如此表示：a.每个样本不仅由属性描述，而且其中还要用关系描述 b.属性不等长。

6 空气 结构决定性质 中国科学院自动化研究所 水 沉积物 土壤 C C

7 中国科学院自动化研究所 单表 属性 属性之间的关系 预测值

8 Cl(4) Cl(6) 中国科学院自动化研究所 C(1) C(2) H(8) H(5) Cl(3) Cl(7)

9 中国科学院自动化研究所

10 中国科学院自动化研究所 形式化描述

11 中国科学院自动化研究所 形式化描述

12 中国科学院自动化研究所 形式化描述

13 中国科学院自动化研究所 顾客类别预测

14 中国科学院自动化研究所 提纲

15 中国科学院自动化研究所 形式化描述

16 中国科学院自动化研究所

17 中国科学院自动化研究所 传统机器学习 实际问题 引发困难 属性顺序固定 属性顺序不定 组合爆炸 属性数目固定 属性数目不定 无法解决 不易融入 背景知识 易于融入 背景知识 效果差， 可理解性差 样本之间i.i.d 不一定i.i.d 得到错误模型 样本来自 同一模型 样本可以来自 不同模型 得到错误模型

18 中国科学院自动化研究所 关系学习中的一阶逻辑方法

19 中国科学院自动化研究所 ILP（归纳逻辑程序）是关系学习领域的研究人员最先采用的解决方法。

20 中国科学院自动化研究所

21 中国科学院自动化研究所 以下讨论涉及到一阶逻辑中的基本定义, 请参阅《机器学习》(Tom M.Mitchell) 第204页表10-3

22 一阶逻辑中的基本定义 中国科学院自动化研究所
每个良构的表达式由常量（如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) 基本文字（ground literal）是不包含任何变量的文字（如，~Female(Joe)） 负文字（negative literal）是包含任何否定谓词的文字（如：～Female(Joe)） 正文字（positive literal）是不包含否定符号的文字（如：Female(Joe)）

23 中国科学院自动化研究所 子句（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 表示应用置换后的结果。 逻辑程序（Logic Program）：是一阶逻辑的一个子集，逻辑程序由子句构成，即一系列的if/then规则 ILP的任务便是通过归纳学习的方法学习到用逻辑程序表达的概念。 中国科学院自动化研究所

24 中国科学院自动化研究所

25 学习规则集合 中国科学院自动化研究所 学习能表示为if-then规则的集合。
其中最重要的一种是学习包含变量的规则集合，或者称为一阶Horn子句集，由于该集合可被解释为逻辑编程语言PROLOG中的程序，学习的过程常被称为归纳逻辑程序（ILP）。 PROLOG是一个与通用图灵机等价的编程语言。 学习规则集合的一种方法是学习决策树，然后转化为等价的规则集合；或者是遗传算法中，用位串编码每个规则集合，然后用遗传搜索算子来探索整个假设空间。 在一阶规则学习中直接学习规则，如： IF Parent(x,y) THEN Ancestor(x,y) IF Parent(x,z) and Ancestor(z,y) THEN Ancestor(x,y) 以上两条规则紧凑地描述了一个递归函数，很难用决策树或者其他的命题方法表示，决策树一般只能学到特殊的规则。

26 序列覆盖算法 中国科学院自动化研究所 该算法学习规则集的策略为：学习一个规则，移去它覆盖的数据，再重复这一过程，被称为序列覆盖(sequential covering)算法。 假设已有一个子程序LEARN-ONE-RULE,它的输入为正例和反例，然后输出单个规则，它能够覆盖许多正例而覆盖很少的反例。要求有较高的精确度，但是不必有较高的覆盖度。 在所有可用训练样本上执行LEARN-ONE-RULE子程序，再移去由其学习到的规则覆盖的正例，然后在剩余的训练样本上执行，学习第二个规则。 该过程重复多次，直到最后学习到析取规则集。它们共同覆盖正例，覆盖程度达到所希望的比例。 将学习析取规则集的问题化简为一系列更简单的问题，每个子问题只需要学习单个合取规则。贪婪搜索，没有回溯，结果不一定最佳。

27 LEARN-ONE-RULE 中国科学院自动化研究所
实现LEARN-ONE-RULE的一个有效途径是将假设空加搜索过程设计成与ID3算法相似的方式，但是每一步只沿着最有希望的分支进行。 搜索开始于最一般的规则前件，然后加入那些在训练样例上性能改进最大的属性测试。然后重复该过程，贪婪地加入第二个属性测试，依此类推。 每个合取假设对应于待学习规则的候选前件集合，由其覆盖的样例的熵来评估。

28 FOIL(Quinlan,1990) 中国科学院自动化研究所 序列覆盖和LEARN-ONE-RULE算法在一阶表示上的自然扩展。
FOIL学习的假设为一阶规则集的子集，类似Horn子句，但有两个不同：文字不允许含有函数符号（减小了假设空间搜索的复杂度）；规则体中的文字可为负文字。 可以学习快速排序算法QUICKSORT的递归定义，以及学习从合法棋盘状态中区分出非法状态。 FOIL算法由两层循环构成，外层循环对应于序列覆盖算法，每次学习一个新规则，将此规则覆盖的正例移去，再学习下一规则。内层循环是LEARN-ONE-RULE的另一种形式。

29 中国科学院自动化研究所

30 候选特化式的生成 中国科学院自动化研究所

31 中国科学院自动化研究所 编码正例所需的最小位数,随着规则越来越强,所需位数越来越少

32 空规则,对于一切x,y,都有daughter(x,y)成立
中国科学院自动化研究所

33 中国科学院自动化研究所 左图是一个有向图； 下图是在命题逻辑中表示 “two nodes are linked
to Each other”的概念。

34 中国科学院自动化研究所

35 中国科学院自动化研究所

36 中国科学院自动化研究所

37 ＋ 中国科学院自动化研究所

38 ＋ 中国科学院自动化研究所

39 ＋ 中国科学院自动化研究所 注：到此已 学习到所有 正样本，而 且不覆盖负 样本，算法 结束。

40 FOIL的特点 中国科学院自动化研究所 搜索子句的过程完全由数据驱动，不需要逻辑证明。 采用贪婪搜索策略，且每次只考虑当前的一个最优解。
可以使用递归定义，但会出现无限递归，无法彻底避免。 采用function-free Horn 子句，限制了表达能力。 无法假设新的谓词，但INDUCE(Michalski,1980)和GIGOL (Muggleton and Buntine,1988)中有引入新谓词的机制，当该谓词对简化定义有帮助时。

41 小结 中国科学院自动化研究所 逻辑仅仅是一种表达语言，真正的人工智能必须能理解语义，我们在选择背景知识，假设空间和搜索路径时其实已经把语义隐含其中。 ILP研究领域中的问题和我们目前碰到的问题不同，ILP中的数据形式复杂，但是规则相对简单，往往可以加入领域知识，而且可以被人理解。

42 中国科学院自动化研究所 关系学习中的概率方法

43 中国科学院自动化研究所 领域知识已知时,往往可以确定 结构,这时估计参数就可以了,但 尽管如此,仍是一个NP难题,只能 得到近似最优解

44 中国科学院自动化研究所

45 中国科学院自动化研究所 血型 人 血型 人 P-染色体 P-染色体 M-染色体 M-染色体 父亲 母亲 人 P-染色体 条件概率密度 CPD M-染色体 血型 污染 结果 测试

46 Bayesian Logic Programs
中国科学院自动化研究所 BLPs的构成： 一个由Bayesian子句构成的有限集。 每个Bayesian子句上都定义一个条件转移概率。 proper random variables: LH(B). dependency graph. CPDs.

47 Bayesian Logic Programs
中国科学院自动化研究所 把每个基本原子映射成随机变量，且该映射是一一的。 分为参数学习和结构学习两部分。 输入是数据和初始的贝叶斯网络（需要细化）。 以下是例子。

48 Bayesian Logic Programs
中国科学院自动化研究所

49 Bayesian Logic Programs
中国科学院自动化研究所

50 Bayesian Logic Programs
中国科学院自动化研究所

51 Bayesian Logic Programs
中国科学院自动化研究所

52 Bayesian Logic Programs
中国科学院自动化研究所

53 Bayesian Logic Programs
中国科学院自动化研究所

54 Bayesian Logic Programs
中国科学院自动化研究所

55 中国科学院自动化研究所 总结

56 关系学习问题的实质 中国科学院自动化研究所 如：
给出 个样本，每个样本都由这六个量（对象，对象间的关系，类别）描述，此处假设了样本长度相等。 目标是学出 ,此处 是映射，不是狭义上的函数。 每个 由一系列的属性 描述。

57 关系学习问题的实质 中国科学院自动化研究所 假设样本间满足i.i.d., 则不会涉及到 ，所以很难直接应用关系代数。
除了一些很特殊的问题，如：Bongard问题， 其中每个样本都具有形式： 每个样本的n不必相等，

58 关系学习问题的实质 中国科学院自动化研究所 一般的关系学习问题就是给出n个样本，每个都由下式描述： 每个 由一些属性描述：
每个 由一些属性描述： 目标是找到映射关系。 注意： 是建立在对象上的，不是建立在对象的属性上的，它们反映了对象的其他属性。（请看下页的例子）

59 举例：Bongard问题（分类） 中国科学院自动化研究所
给定若干正负样本，目标规则：如果有一个红色的圆套在一个蓝色的方形内，则该样本是正样本。

60 举例：Bongard问题（分类） 中国科学院自动化研究所 注：没有写出的谓词取值为False.

61 举例：Bongard问题（分类） 中国科学院自动化研究所

62 举例：Bongard问题（分类） 中国科学院自动化研究所

63 举例：Bongard问题（分类） 中国科学院自动化研究所

64 举例：Bongard问题（分类） 中国科学院自动化研究所

65 举例：Bongard问题（分类） 中国科学院自动化研究所

66 Bongard问题的涵义 中国科学院自动化研究所 是建立在 之间，但却不是建立在 的属性（形状，颜色）之间。
是建立在 之间，但却不是建立在 的属性（形状，颜色）之间。 其实是建立在一个“隐空间”上（坐标），这也正是为什么谓词不能由函数替代 。 人类可以知道该空间是什么（根据我们的先验知识），计算机却无法理解，无法直接对 计算，因此才需要引入一阶逻辑（也就是谓词）。

67 一阶逻辑带来了什么？ 中国科学院自动化研究所 便于人理解，从人的角度抓住了问题的本质，数据提供，结果解释都很方便。
适合人的不一定适合计算机，如上例中计算机无法真正理解 的语义，因为要理解语义，就必须有“隐空间”，这正是我们无法提供的。 人：难度低；计算机：难度高

68 提供“隐空间”？ 中国科学院自动化研究所 一般会变得更难。 采用 ,我们其实是暗示给计算机解决问题的思路，否则它还得从数据中提取出类似于
采用 ,我们其实是暗示给计算机解决问题的思路，否则它还得从数据中提取出类似于 的一种表达（要耗费大量计算，而且不一定能成功）。而且结果不易解释。 人：难度高 计算机：难度高

69 关键 中国科学院自动化研究所 是否存在一种中间地带，使得计算机和人类对问题的理解一致，让计算机学会人处理问题的方式？
人：难度低 计算机：难度低

70 关系学习的难点 中国科学院自动化研究所 认知心理学理论：有效解决问题往往需要加领域特异性知识。
与 空间中的机器学习相比，关系学习中不易加入领域特异性知识。

71 几何－－ 空间的领域特异性知识 中国科学院自动化研究所
几何－－ 空间的领域特异性知识 中国科学院自动化研究所 在 空间的机器学习问题中，我们可以充分利用几何直观，一切抽象方法都建立在几何直观的基础上。（SVM，流形，统计方法，甚至是神经网络）。由此来设计可以在计算机上运行的算法。 几何直观也是一种领域特异性知识，因为我们生活在 空间内，导致数学建立在 空间上，所以我们没有意识到这种特异性。

72 关系学习的难点（续） 中国科学院自动化研究所
但是在relational learning中我们失去了先天的优势（想象一下人来求解Bongard Problem,当每个样本中对象数目巨大时），只能无目的地搜索，又如何能去指导计算机？

73 人如何解决关系学习的问题？ 中国科学院自动化研究所 一个小游戏：红色区域内的数字应该是几？

74 我是如何解决该问题的 中国科学院自动化研究所 “一些多边形，有凸有凹，莫非是多边形边数？” “不对。。。，想想也不会这么简单”
“5出现的地方是最零乱的地方。” 发呆5分钟。。。 做了一系列错误尝试。 “原来是这样！”

75 启示 中国科学院自动化研究所 人在解决问题时首先会对问题做表征，不同的表征会对应不同的解决策略，然后在“策略空间”搜索。
计算机科学：人首先把问题做好表征，选好解决策略，交给计算机处理。 机器学习：最好能由计算机根据数据性质选择解决策略。数据性质反映了数据的产生机理，与其对应的解决策略才能适应问题。

76 启示 中国科学院自动化研究所 空间的机器学习：数据的分布特性可由统计方法得知：线性或非线性？分布的性质？然后选择问题求解策略：线性回归？树？流形？相应于数据的kernel？ 可以看到， 空间中的机器学习在逐渐把问题求解策略交给计算机来做，这样才是真正的机器学习。 关系学习：我把这堆数据告诉你，你去搜吧！

77 启示 中国科学院自动化研究所 因为没有通用的好的学习算法，因此需要让计算机根据数据选择模型（问题求解策略）。
在 空间模型选择问题已经得到了广泛深入的研究，相比之下，关系学习中几乎没有人去研究。原因：需要多种领域特异性知识。而 空间中只有一种：几何。

78 启示 中国科学院自动化研究所 在关系学习中，我们失去了与生俱来的直观，使得问题求解策略选择变为一个难题。
如何对关系学习中的问题求解策略进行分类，并根据数据选择策略（如： 中的线性，非线性） 是这一领域发展的关键。否则关系学习将丧失理论价值，虽然很有实际意义。

79 总结 中国科学院自动化研究所 本次讨论首先探讨了关系学习中存在的问题和难点，然后讨论了用于关系学习的逻辑方法和概率方法。
如前所述，要较好地解决关系学习中的问题需要考虑到领域特异性知识，概率方法就是这样一种尝试，但是目前概率方法只是用来做参数学习，而结构学习才是这个问题的本质所在。 不同的结构，不同的领域特异性知识如何整合在一起：Bongard问题，邻域填数字问题，分子性质预测问题……

80 总结 中国科学院自动化研究所 传统机器学习无法解决的问题都丢给关系学习。因此关系学习只是一个很模糊的概念，其中涵盖了很多不同的问题。如果要下手研究，必须要瞅准一个问题。 目前的逻辑和概率方法都试图用统一的一个方法解决所有关系学习问题，实不可取。

81 总结 中国科学院自动化研究所 另外两个研究方向因为时间所限没有介绍，即：把问题命题化；把命题方法一阶逻辑化。请参阅参考文献[1]。

82 中国科学院自动化研究所

83 中国科学院自动化研究所

84 最新进展---理论研究 改进ILP方法的效率 [Hendrik Blockeel, Luc Dehaspe, et al. ,2002] Propositionalization [Krogel ,et al.,2003;Pfahringer&Holmes,2003] 泛化 [Nicola Fanizzi, Stefano Ferilli ,2002] 复杂性 [Maloberti et.al ,2004] 概率方法 [Luc De Raedt,2004] 中国科学院自动化研究所

85 中国科学院自动化研究所 最新进展---与其他方法的融合 Relational Markov Networks (RMNs) [Taskar et al. 2002] Relational dependency networks (RDNs) [Neville et.al, 2003, 2004] Autocorrelation & feature selection [Jensen et.al 2002,2003]

86 中国科学院自动化研究所 最新进展---Statistical Relational learning

87 中国科学院自动化研究所

88 中国科学院自动化研究所

89 中国科学院自动化研究所 谢谢大家，欢迎交流