2009-8-20 史忠植 高级人工智能 1
第六章 归纳学习 (2)
史忠植中科院计算所
2009-8-20 史忠植 高级人工智能 2
决策树发现概念描述空间一种特别有效的方法是形成决策树。
Hunt,Marin、和 Stone于 1966年研制了一个概念学习系统 CLS,
可以学习单个概念，并用此学到的概念分类新的实例。
Quinlan于 1983年研制了 ID3(1983)。
Schlimmer和 Fisher于 1986年构造了 ID4算法，允许递增式地构造决策树。
Utgoff于 1988年提出 ID5算法，它允许通过修改决策树来增加新的训练实例，而无需重建决策树
2009-8-20 史忠植 高级人工智能 3
决策树
2009-8-20 史忠植 高级人工智能 4
决策树
2009-8-20 史忠植 高级人工智能 5
Decision Trees
Tree structure
– Node = query on attribute
– Link = attribute value
– Leaf = class
Recursively separate data into sub-
populations
Prediction,Traverse path,yield most
probable class
2009-8-20 史忠植 高级人工智能 6
CLS算法
(1) 如果 C中全部实例为正例，则建立一个
YES结点，并且停止。如果 C中全部实例为反例，
则建立一个 NO结点，并且停止。否则选择一个属性 A,根据它的值 v1,…,vn 建立决策树。
(2) 根据值 V，将训练实例 $C$划分为子集
C1,…,Cn。
(3) 对每个集合 Ci递归地应用此算法。
2009-8-20 史忠植 高级人工智能 7
决策树
CLS算法可以产生所有可能的决策树，正确分类训练实例，并能选择最简单的决策树。但是，它的学习问题不能太大。为了克服这种限止,ID3采用训练实例的子集，即可以选择窗口来形成决策树。这种树可以正确分类窗口中的所有对象。然后，使用该树可以分类训练集中的所有其它对象。如果该树对所有对象给以正确的解答，那么，它对整个训练集是正确的，算法就结束。如果不是这样，选择一个例外加到窗口继续处理，直到发现正确的决策树为止。
2009-8-20 史忠植 高级人工智能 8
决策树
ID3采用信息论方法，减小对象分类的测试期望值。
属性选择是基于可能性假设，即决策树的复杂性与消息传递的信息量有关。设 C包括类 P的对象 p和类 N
的对象 n,假设：
(1) 任何 C的正确决策树，以 C中表示同样的比例将对象分类。
任何对象属于类 P的概率为 p/(p+n),
属于类 N的概率为 n/(p+n)。
2009-8-20 史忠植 高级人工智能 9
决策树
(2) 当用决策树进行分类时，返回一个类。作为消息源 `P' 或 `N'有关的决策树，产生这些消息所需的期望信息为：
I(p,n) = - p/p+n log2 (p/(p+n)) -
n/p+n log2 (n/(p+n))
2009-8-20 史忠植 高级人工智能 10
决策树决策树根的属性 A具有 A1,A2,…,Am，它将 C划分为
C1,C2,…,Cm,其中 Ci 包括 C中属性 A的值为 Ai的那些对象。设 Ci包括类 P的对象 pi和类 N的对象 ni。
子树 Ci所需的期望信息是 I(pi,ni)。以属性 A作为树根所要求的期望信息可以通过权值平均得到：
E(A) =? {pi + ni}/{p + n} I(pi,ni)
其中第 i个分支的权值是与 C中属于 Ci的对象成比例。
所以按 A分支的信息增益为：
gain(A) = I(p,n) - E(A)
)(AE
2009-8-20 史忠植 高级人工智能 11
决策树
ID3检查所有的候选属性，选择增益最大的属性 A作为根结点，形成树。然后，对子树 C1,C2,…,Cm以同样处理，递归地形成决策树。
2009-8-20 史忠植 高级人工智能 12
Golf Example (1)
Outlook Temperature Humidity Windy Play
Sunny 85 85 False Don’t Play
Sunny 80 90 True Don’t Play
Overcast 83 78 False Play
Rain 70 96 False Play
Rain 68 80 False Play
Rain 65 70 True Don’t Play
Overcast 64 65 True Play
Sunny 72 95 False Don’t Play
Sunny 69 70 False Play
Rain 75 80 False Play
Sunny 75 70 True Play
Overcast 72 90 True Play
Overcast 81 75 False Play
Rain 71 80 True Don’t Play
2009-8-20 史忠植 高级人工智能 13
Definitions
Informative
– Establishes Good decision trees
Entropy
– Measure how informative is a node
– Definition:
P=(p1,p2,…,pn)
Then Entropy of P is,
I(P)= -(p1*log(p1) + p2*log(p2) +…+ pn*log(pn) )
2009-8-20 史忠植 高级人工智能 14
Definitions (Cont.)
Entropy
– For example:
1,If P=(0.5,0.5)? I(P)=1
2,If P=(2/3,1/3)? I(P)=0.92
3,If P= (1,0)? I(P)=0
What do u see
– Entropy of previous golf example
I(P)=I(9/14,5/14)=-(9/14*log(9/14) + 5/14*log(5/14))
= 0.94
2009-8-20 史忠植 高级人工智能 15
Definitions (Cont.)
Entropy of an attribute
– For example:
I(Outlook,T)= 5/14 * I(2/5,3/5) +
4/14 * I(4/4,0) +
5/14 * I)(3/5,2/5)
= 0.694
While I(windy,T)=0.892
2009-8-20 史忠植 高级人工智能 16
Information Gain (2)
Information Gain
Gain(T,A) = I(T) – I(T,A)
I(T) = expected information for distinguishing classes
= -(p/(p+n)log2(p/(p+n))+n/(p+n)log2(n/(p+n)))
I(T,A) = expected information of tree with A as root
=?i(pi+ni)/(p+n)*I(Ti)
p,n,number of positive/negative training data
pi,ni,number of positive/negative training data in the
training data Ti partitioned by the attribute value Ai
Select an attribute with highest information gain
Prefer an attribute A with smallest I(T,A)
i.e.,Prefer the attribute that makes non-uniform distribution
2009-8-20 史忠植 高级人工智能 17
Golf Example (2)
The initial information
– I(T) = I(9/14,5/14) = 0.94
The information for Outlook attribute
– Sunny,Overcast,Rain
– I(T,Outlook) = 5/14*I(2/5,3/5) + 4/14*I(4/4,0/4) +
5/14*I(3/5,2/5) = 0.694
– Gain(T,Outlook) = 0.94-0.694 = 0.246
The information for Windy attribute
– True,False
– I(T,Windy) = 6/14*I(3/6,3/6) + 8/14*I(6/8,2/8) = 0.892
– Gain(T,Windy) = 0.94-0.892 = 0.048
select Outlook attribute for the first partition
2009-8-20 史忠植 高级人工智能 18
Definitions (Cont.)
Entropy of an attribute
– Definition of Gain()
Gain(X,T) = I(T) – I(X,T)
Gain(Outlook,T) = I(T) – I(Outlook,T)
= 0.94 – 0.694
= 0.246
Gain(Windy,T) = I(T) – I(Windy,T)
= 0.94 – 0.892
= 0.048
– We say,Outlook is more informative than Windy,
Why
2009-8-20 史忠植 高级人工智能 19
results of,c4.5 –f golf
2009-8-20 史忠植 高级人工智能 20
c4.5 –f golf decision tree represented graphically
2009-8-20 史忠植 高级人工智能 21
c4.5rules –f golf,induced rules
2009-8-20 史忠植 高级人工智能 22
ID3 算法
(1)选择给定训练实例的随机子集（称为窗口）。
(2)重复
(a) 形成一条规则解释当前窗口。
(b) 从其余实例中寻找该规则的例外。
(c) 由当前窗口和规则例外生成新的窗口。
直到该规则没有例外为止。
2009-8-20 史忠植 高级人工智能 23
决策树
ID3 Decision Tree Learning Algorithm
ID3(Examples,Target,Attributes)
Create a root node
If all Examples have the same Target value,give the root this label
Else if Attributes is empty label the root according to the most
common value
Else begin
Calculate the information gain for each attribute,according to
the average entropy formula
Select the attribute,A,with the lowest average entropy (highest
information gain) and make this the attribute tested at the root
end
2009-8-20 史忠植 高级人工智能 24
决策树
For each possible value,v,of this attribute
Add a new branch below the root,corresponding to
A = v
Let Examples(v) be those examples with A = v
If Examples(v) is empty,make the new branch a
leaf node labelled with the most common value
among Examples
Else let the new branch be the tree created by
ID3(Examples(v),Target,Attributes - {A})
end
2009-8-20 史忠植 高级人工智能 25
C4.5 Extensions
C4.5 is an extensions of ID3 accounts for
Depth-first strategy is used
Unavailable values
– Ex,only given Outlook to be Sunny
Continuous attribute value ranges
– Ex,humidity is greater than 75
Pruning of decision trees
Rule derivation
2009-8-20 史忠植 高级人工智能 26
Decision Trees,Training
[C4.5,Quinlan,1993]
Generate_tree(R,C,T)
// R,set of non-categorical attribute
// C,categorical attribute,T,training data
1,if T has the same categorical value then return a single node with the
value
2,if R={} then return a single node with most frequent categorical value
in T
3,A = attribute with highest information gain,Gain(T,A) among R
4,Let A1,A2,..,Am the attribute values of A
5,Let T1,T2,..,Tm the subsets of T partitioned by of Ai
6,return a node with A and m links as follows
7,for i = 1 to m do
1,Generate_tree(R-{A},C,Ti)
2009-8-20 史忠植 高级人工智能 27
Discrete vs,Continuous
Attributes
Suppose A is an attribute with continuous values
– e.g.,Humidity in Golf example
A1,A2,..,Am are the values in the training data,in
increasing order
For each Aj
– TL = Partition of training data whose A values are <= Aj
– TH = Partition of training data whose A values are > Aj
– Calculate Gain(T,A) or GainRaio(T,A)
Select the best partition
2009-8-20 史忠植 高级人工智能 28
Decision Trees – Advantages
Comprehensibility
Fast classification
Mature technology
– There are many systems
– C4.5 [Quinlan,1993]
– C5.0(See-5)
2009-8-20 史忠植 高级人工智能 29
Common Decision Tree / Rule-Induction Software:
c4.5
DOS-based decision tree and rule induction software
based on Ross Quinlan’s ID3 algorithm,(Free)
c5.0 / See-5
Windows-compatible version of c4.5,More flexible
analysis,Replaces ID3 with a better-performing,less
resource-intensive algorithm,Evaluation copy
(maximum 500 cases) is free,Non-case-limited
version is $475.
SPSS AnswerTree (UNICEF,financial firms)
Gives users the choice of several algorithms in
constructing trees,depending on type of data,
Impressive output,but very expensive,($1999)
2009-8-20 史忠植 高级人工智能 30
See 5
See 5 is very similar to c4.5,The basic interface displays the
data set currently in use,along with all the constituent files that
you have created and/or See 5 has computed
2009-8-20 史忠植 高级人工智能 31
决策树 ID4
1986,Schlimmer 和 Fisher 设计了 ID4学习算法,是一种递增式学习算法。他们修改 ID3算法，
在每个可能的决策树结点创建一系列表。每个表由全部未检测属性值和每个值的正例和反例数组成。
当处理一个新例时，每个属性值的正例或反例递增计量。
2009-8-20 史忠植 高级人工智能 32
决策树 ID4
输入,决策树，一个实例输出,决策树
(1) 若该实例是正例，正例数加 1，否则，反例数加 1。
(2) 如果实例全部为正例或反例，则返回决策树。
(3) 否则
(a) 计算期望信息分数。
(b) 实例中出现的每个属性、每个值，使之递增正例数或者反例数。
(c) 计算全部属性的信息分数。
2009-8-20 史忠植 高级人工智能 33
决策树 ID4
(d) 如果没有根，或者最大属性不在根结点，
则创建新树。
(i) 如果最大属性是 x2 依赖关系，那么用它作为这棵树的根结点。
(ii) 链接根到每个根属性的值
(e) 跳转到步骤 (1)，下面创建的子树链到该实例的根属性值。
2009-8-20 史忠植 高级人工智能 34
决策树 ID5
在 ID4的基础上 Utgoff提出了 ID5学习算法
(Utgoff 1988)。 ID5 与 ID4的差别在于检测属性。 ID5抛弃旧的检测属性下面的子树，从下面选出检测属性形成树。这种方法的优点是在树操纵时重新计算正例和反例的数，不要对实例重新处理。
2009-8-20 史忠植 高级人工智能 35
ID5算法
(1) 对结点每个可能的检测属性，修改属性的正例和反例数，以及修改该属性值观察值的正例数和反例数。
(2) 如果非检测属性的最低信息论测度低于当前的检测属性，则将该检测属性提上来，重新构造决策树。
(3) 在给定结点仅观察到正例或反例，那么保存其余训练实例。结束停止。
(4) 在实例描述中，对所希望检测属性值下面的决策树进行递归修改。
2009-8-20 史忠植 高级人工智能 36
ID5属性提升算法
(1) 递归地提升属性到最近子树的根结点。
(2) 对每个子树的分支值，将旧的检测属性推到新属性下，构造新的决策树。
这样，形成一组子树，每个根结点都是所希望的检测属性。
(3) 合并子树，形成决策树，其根结点是所希望的检测属性。
2009-8-20 史忠植 高级人工智能 37
决策树
Missing values
Multivalued attributes
Continuous valued attributes
2009-8-20 史忠植 高级人工智能 38
归纳学习的计算理论学习的计算理论主要研究学习算法样本复杂性计算复杂性。
2009-8-20 史忠植 高级人工智能 39
Gold学习理论在形式语言学习的上下文中,Gold引入收敛的概念，有效地处理了从实例学习的问题。
学习算法允许提出许多假设，无须知道什么时候它是正确的，只要确认某点它的计算是正确的假设。由于 Gold算法的复杂性很高
，因此这种风范并没有在实际学习中得到应用。
2009-8-20 史忠植 高级人工智能 40
Gold学习理论基于 Gold 学习框架,Shapiro 提出了模型推理算法研究形式语言与其解释之间的关系，也就是形式语言的语法与语义之间的关系。模型论把形式语言中的公式、句子理论和它们的解释 ─ 模型，当作数学对象进行研究。 Shapiro 模型推理算法只要输入有限的事实就可以得到一种理论输出 (Shapiro
1981)。
2009-8-20 史忠植 高级人工智能 41
Gold学习理论
Gold的语言学习理论研究引入两个基本概念，即极限辨识枚举辨识,
这对早期的归纳推理的理论研究起了非常重要的作用 (Gold 1967)。
2009-8-20 史忠植 高级人工智能 42
Gold学习理论极限辨识把归纳推理看作一种无限过程，归纳推理方法的最终或极限行为可以看作是它的成功标准。 假设 M是一种归纳推理方法，
它企图正确地描述未知规则 R。假设 M重复运行,R的实例集合则愈耒愈大，形成 M推测的无限序列 g1,g2,… 。如果存在某个数 m，
使得 gm 是 R的正确描述，
gm=gm＋ 1=gm＋ 2=…,
2009-8-20 史忠植 高级人工智能 43
Gold学习理论枚举辨识是第一种方法推测多项式序列的抽象，即对可能的规则空间进行系统搜索，直到发现与迄今为止的所有数据相一致的推测。
假设规定了规则的具体领域，有一个描述枚举，即 d1,d2,d3,…,
以致于领域中的每一条规则在枚举中有一种或多种描述。给定一条规则的某个实例集合，枚举辨识方法将通过这个表，找到第一个描述 d1，即与给定的实例相容，那么推测为 d1。这种方法不能确定是否会达到正确的极限辨识。如果实例表示和相容关系满足下面两个条件，那么枚举方法保证极限辨识该领域中的全部规则：
(1) 一个正确假设总是与给定的实例相容。
(2) 任何不正确的假设与实例足够大的集合或与全部集合不相容。
为了枚举方法是可计算的，枚举 d1,d2,d3,…
必须是可计算的，它必须能够计算给定的描述与给定的实例集合是相容的。
2009-8-20 史忠植 高级人工智能 44
枚举辨识算法枚举辨识算法。
输入：
一组表达式的集合 E = e1,e2,… 。
谕示 (oracle) TE提供足够的目标实例集。
排序信息的谕示 LE。
输出：
一系列假设断言 H1,H_2,…,每个假设 Hi都在 E中，并与第 i
个实例一致。
2009-8-20 史忠植 高级人工智能 45
枚举辨识算法过程：
1,初始化,i? 1;
2,examples? emptyset;
3,Loop:
3.1 调用 TE(),将 example 加到集合 examples;
3.2 While LE(ei,+x) = no,对正例集 +x,或者
LE(ei,-x) = yes,对反例集 -x,
i? i + 1;
4,输出 ei
2009-8-20 史忠植 高级人工智能 46
模型推理系统模型推理问题是科学家所面临的问题抽象，他们在具有固定概念框架的某种领域里工作，进行试验，试图找到一种理论可以解释他们的结果。在这种抽象中研究的领域是对给定的一阶语言 L某种未知模型 M的领域，实验是检测 M中 L语句的真值，目标是寻找一组正确假设，它们包含全部正确的可测试的句子。
L 语句分成两个子集：观测语言 Lo和假设语言 Lh 。假设
Lo? Lh? L‘
其中?是空语句。
2009-8-20 史忠植 高级人工智能 47
模型推理系统模型推理问题可以定义如下：假设给定一阶语言 $L
和两个子集：观测语言 Lo和假设语言 Lh。另外对 L
的未知模型 M给定一种处理机制 oracle。模型推理问题是寻找 M的一种有限的 Lo ─ 完备公理化。
求解模型推理问题的算法称为模型推理算法。
模型 M的枚举是一个无限序列 F1,F2,F3,…,
其中 Fi是关于 M的事实,Lo的每个语句发生在事实
Fi = <?,V>,i > 0 。模型推理算法一次读入给定观测语言 Lo的模型的一种枚举，一个事实，产生假设语言 Lh的语句的有限集称为算法的推测。
2009-8-20 史忠植 高级人工智能 48
模型推理系统
h 是整个递归函数。
设 Sfalse为?,Strue为 {},k 为 0。
repeat
读入下一个事实 Fn =<?,V>，
加到 Sv,
while? ∈Sfalse 以致于 Tkn?
或有一个?i ∈ Strue以致于
Tkni?i do
k = k+1，
输出 Tk
forever
2009-8-20 史忠植 高级人工智能 49
Valiant学习理论
Valiant 认为一个学习机必须具备下列性质：
(1) 机器能够证明地学习所有类的概念。
更进一步，这些类可以特征化。
(2) 对于通用知识概念类是合适的和不平常的。
(3) 机器演绎所希望的程序的计算过程要求在可行的步数内。
2009-8-20 史忠植 高级人工智能 50
Valiant学习理论学习机由学习协议和演绎过程组成。学习协议规定从外部获得信息的方法。演绎过程是一种机制，学习概念的正确识别算法是演绎的。从广义来看，研究学习的方法是规定一种可能的学习协议，使用这种协议研究概念类，识别程序可以在多项式时间内演绎。具体协议允许提供两类信息。
第一种是学习者对典型数据的访问，这些典型数据是概念的正例。要确切地说，假设这些正例本质上有一种任意确定的概率分布。调用子程序 EXAMPLES 产生一种这样的正例。产生不同例子的相对概率是分布确定的。第二个可用的信息源是 ORACLE。在最基本的版本中，当提交数据时，
它将告诉学习该数据是否是概念的正例示。
2009-8-20 史忠植 高级人工智能 51
Valiant学习理论假设 X是实例空间，一个概念是 X的一个子集。如果实例在概念中则为正例，否则为反例。概念表示是一种概念的描述，概念类是一组概念表示。学习模型是概念类的有效的可学习性。 Valiant 学习理论仅要求对目标概念的很好近似具有极高的概率。允许学习者产生的概念描述与目标概念有一个小的偏差?,它是学习算法的一个输入参数。
并且，允许学习者失败的概率为?,这也是一个输入参数。
两种概念之间的差别采用在实例空间 X的分布概率 D来评测：
diffD(c1,c2) =? D(x)
2009-8-20 史忠植 高级人工智能 52
Valiant学习理论根据协议，一个概念类 C是可学习的当且仅当有一种算法
A，使用协议，对所有的目标概念表示 c*? C 和全部分布 D，
(1) 执行时间是与 1/?,1/?,c* 数目和其它相关参数有关的多项式。
(2) 输出 C中的概念 c具有概率 1-?,
diffD(c,c*)<?
2009-8-20 史忠植 高级人工智能 53
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 54
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 55
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 56
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 57
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 58
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 59
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 60
Sn S*
经验风险置信区风险界限
h1 h* hn h
S1 S* Sn
结构风险最小归纳原理观察学习
2009-8-20 史忠植 高级人工智能 61
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 62
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 63
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 64
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 65
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 66
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 67
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 68
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 69
Support Vector Machine(SVM)
第六章 归纳学习 (2)
史忠植中科院计算所
2009-8-20 史忠植 高级人工智能 2
决策树发现概念描述空间一种特别有效的方法是形成决策树。
Hunt,Marin、和 Stone于 1966年研制了一个概念学习系统 CLS,
可以学习单个概念，并用此学到的概念分类新的实例。
Quinlan于 1983年研制了 ID3(1983)。
Schlimmer和 Fisher于 1986年构造了 ID4算法，允许递增式地构造决策树。
Utgoff于 1988年提出 ID5算法，它允许通过修改决策树来增加新的训练实例，而无需重建决策树
2009-8-20 史忠植 高级人工智能 3
决策树
2009-8-20 史忠植 高级人工智能 4
决策树
2009-8-20 史忠植 高级人工智能 5
Decision Trees
Tree structure
– Node = query on attribute
– Link = attribute value
– Leaf = class
Recursively separate data into sub-
populations
Prediction,Traverse path,yield most
probable class
2009-8-20 史忠植 高级人工智能 6
CLS算法
(1) 如果 C中全部实例为正例，则建立一个
YES结点，并且停止。如果 C中全部实例为反例，
则建立一个 NO结点，并且停止。否则选择一个属性 A,根据它的值 v1,…,vn 建立决策树。
(2) 根据值 V，将训练实例 $C$划分为子集
C1,…,Cn。
(3) 对每个集合 Ci递归地应用此算法。
2009-8-20 史忠植 高级人工智能 7
决策树
CLS算法可以产生所有可能的决策树，正确分类训练实例，并能选择最简单的决策树。但是，它的学习问题不能太大。为了克服这种限止,ID3采用训练实例的子集，即可以选择窗口来形成决策树。这种树可以正确分类窗口中的所有对象。然后，使用该树可以分类训练集中的所有其它对象。如果该树对所有对象给以正确的解答，那么，它对整个训练集是正确的，算法就结束。如果不是这样，选择一个例外加到窗口继续处理，直到发现正确的决策树为止。
2009-8-20 史忠植 高级人工智能 8
决策树
ID3采用信息论方法，减小对象分类的测试期望值。
属性选择是基于可能性假设，即决策树的复杂性与消息传递的信息量有关。设 C包括类 P的对象 p和类 N
的对象 n,假设：
(1) 任何 C的正确决策树，以 C中表示同样的比例将对象分类。
任何对象属于类 P的概率为 p/(p+n),
属于类 N的概率为 n/(p+n)。
2009-8-20 史忠植 高级人工智能 9
决策树
(2) 当用决策树进行分类时，返回一个类。作为消息源 `P' 或 `N'有关的决策树，产生这些消息所需的期望信息为：
I(p,n) = - p/p+n log2 (p/(p+n)) -
n/p+n log2 (n/(p+n))
2009-8-20 史忠植 高级人工智能 10
决策树决策树根的属性 A具有 A1,A2,…,Am，它将 C划分为
C1,C2,…,Cm,其中 Ci 包括 C中属性 A的值为 Ai的那些对象。设 Ci包括类 P的对象 pi和类 N的对象 ni。
子树 Ci所需的期望信息是 I(pi,ni)。以属性 A作为树根所要求的期望信息可以通过权值平均得到：
E(A) =? {pi + ni}/{p + n} I(pi,ni)
其中第 i个分支的权值是与 C中属于 Ci的对象成比例。
所以按 A分支的信息增益为：
gain(A) = I(p,n) - E(A)
)(AE
2009-8-20 史忠植 高级人工智能 11
决策树
ID3检查所有的候选属性，选择增益最大的属性 A作为根结点，形成树。然后，对子树 C1,C2,…,Cm以同样处理，递归地形成决策树。
2009-8-20 史忠植 高级人工智能 12
Golf Example (1)
Outlook Temperature Humidity Windy Play
Sunny 85 85 False Don’t Play
Sunny 80 90 True Don’t Play
Overcast 83 78 False Play
Rain 70 96 False Play
Rain 68 80 False Play
Rain 65 70 True Don’t Play
Overcast 64 65 True Play
Sunny 72 95 False Don’t Play
Sunny 69 70 False Play
Rain 75 80 False Play
Sunny 75 70 True Play
Overcast 72 90 True Play
Overcast 81 75 False Play
Rain 71 80 True Don’t Play
2009-8-20 史忠植 高级人工智能 13
Definitions
Informative
– Establishes Good decision trees
Entropy
– Measure how informative is a node
– Definition:
P=(p1,p2,…,pn)
Then Entropy of P is,
I(P)= -(p1*log(p1) + p2*log(p2) +…+ pn*log(pn) )
2009-8-20 史忠植 高级人工智能 14
Definitions (Cont.)
Entropy
– For example:
1,If P=(0.5,0.5)? I(P)=1
2,If P=(2/3,1/3)? I(P)=0.92
3,If P= (1,0)? I(P)=0
What do u see
– Entropy of previous golf example
I(P)=I(9/14,5/14)=-(9/14*log(9/14) + 5/14*log(5/14))
= 0.94
2009-8-20 史忠植 高级人工智能 15
Definitions (Cont.)
Entropy of an attribute
– For example:
I(Outlook,T)= 5/14 * I(2/5,3/5) +
4/14 * I(4/4,0) +
5/14 * I)(3/5,2/5)
= 0.694
While I(windy,T)=0.892
2009-8-20 史忠植 高级人工智能 16
Information Gain (2)
Information Gain
Gain(T,A) = I(T) – I(T,A)
I(T) = expected information for distinguishing classes
= -(p/(p+n)log2(p/(p+n))+n/(p+n)log2(n/(p+n)))
I(T,A) = expected information of tree with A as root
=?i(pi+ni)/(p+n)*I(Ti)
p,n,number of positive/negative training data
pi,ni,number of positive/negative training data in the
training data Ti partitioned by the attribute value Ai
Select an attribute with highest information gain
Prefer an attribute A with smallest I(T,A)
i.e.,Prefer the attribute that makes non-uniform distribution
2009-8-20 史忠植 高级人工智能 17
Golf Example (2)
The initial information
– I(T) = I(9/14,5/14) = 0.94
The information for Outlook attribute
– Sunny,Overcast,Rain
– I(T,Outlook) = 5/14*I(2/5,3/5) + 4/14*I(4/4,0/4) +
5/14*I(3/5,2/5) = 0.694
– Gain(T,Outlook) = 0.94-0.694 = 0.246
The information for Windy attribute
– True,False
– I(T,Windy) = 6/14*I(3/6,3/6) + 8/14*I(6/8,2/8) = 0.892
– Gain(T,Windy) = 0.94-0.892 = 0.048
select Outlook attribute for the first partition
2009-8-20 史忠植 高级人工智能 18
Definitions (Cont.)
Entropy of an attribute
– Definition of Gain()
Gain(X,T) = I(T) – I(X,T)
Gain(Outlook,T) = I(T) – I(Outlook,T)
= 0.94 – 0.694
= 0.246
Gain(Windy,T) = I(T) – I(Windy,T)
= 0.94 – 0.892
= 0.048
– We say,Outlook is more informative than Windy,
Why
2009-8-20 史忠植 高级人工智能 19
results of,c4.5 –f golf
2009-8-20 史忠植 高级人工智能 20
c4.5 –f golf decision tree represented graphically
2009-8-20 史忠植 高级人工智能 21
c4.5rules –f golf,induced rules
2009-8-20 史忠植 高级人工智能 22
ID3 算法
(1)选择给定训练实例的随机子集（称为窗口）。
(2)重复
(a) 形成一条规则解释当前窗口。
(b) 从其余实例中寻找该规则的例外。
(c) 由当前窗口和规则例外生成新的窗口。
直到该规则没有例外为止。
2009-8-20 史忠植 高级人工智能 23
决策树
ID3 Decision Tree Learning Algorithm
ID3(Examples,Target,Attributes)
Create a root node
If all Examples have the same Target value,give the root this label
Else if Attributes is empty label the root according to the most
common value
Else begin
Calculate the information gain for each attribute,according to
the average entropy formula
Select the attribute,A,with the lowest average entropy (highest
information gain) and make this the attribute tested at the root
end
2009-8-20 史忠植 高级人工智能 24
决策树
For each possible value,v,of this attribute
Add a new branch below the root,corresponding to
A = v
Let Examples(v) be those examples with A = v
If Examples(v) is empty,make the new branch a
leaf node labelled with the most common value
among Examples
Else let the new branch be the tree created by
ID3(Examples(v),Target,Attributes - {A})
end
2009-8-20 史忠植 高级人工智能 25
C4.5 Extensions
C4.5 is an extensions of ID3 accounts for
Depth-first strategy is used
Unavailable values
– Ex,only given Outlook to be Sunny
Continuous attribute value ranges
– Ex,humidity is greater than 75
Pruning of decision trees
Rule derivation
2009-8-20 史忠植 高级人工智能 26
Decision Trees,Training
[C4.5,Quinlan,1993]
Generate_tree(R,C,T)
// R,set of non-categorical attribute
// C,categorical attribute,T,training data
1,if T has the same categorical value then return a single node with the
value
2,if R={} then return a single node with most frequent categorical value
in T
3,A = attribute with highest information gain,Gain(T,A) among R
4,Let A1,A2,..,Am the attribute values of A
5,Let T1,T2,..,Tm the subsets of T partitioned by of Ai
6,return a node with A and m links as follows
7,for i = 1 to m do
1,Generate_tree(R-{A},C,Ti)
2009-8-20 史忠植 高级人工智能 27
Discrete vs,Continuous
Attributes
Suppose A is an attribute with continuous values
– e.g.,Humidity in Golf example
A1,A2,..,Am are the values in the training data,in
increasing order
For each Aj
– TL = Partition of training data whose A values are <= Aj
– TH = Partition of training data whose A values are > Aj
– Calculate Gain(T,A) or GainRaio(T,A)
Select the best partition
2009-8-20 史忠植 高级人工智能 28
Decision Trees – Advantages
Comprehensibility
Fast classification
Mature technology
– There are many systems
– C4.5 [Quinlan,1993]
– C5.0(See-5)
2009-8-20 史忠植 高级人工智能 29
Common Decision Tree / Rule-Induction Software:
c4.5
DOS-based decision tree and rule induction software
based on Ross Quinlan’s ID3 algorithm,(Free)
c5.0 / See-5
Windows-compatible version of c4.5,More flexible
analysis,Replaces ID3 with a better-performing,less
resource-intensive algorithm,Evaluation copy
(maximum 500 cases) is free,Non-case-limited
version is $475.
SPSS AnswerTree (UNICEF,financial firms)
Gives users the choice of several algorithms in
constructing trees,depending on type of data,
Impressive output,but very expensive,($1999)
2009-8-20 史忠植 高级人工智能 30
See 5
See 5 is very similar to c4.5,The basic interface displays the
data set currently in use,along with all the constituent files that
you have created and/or See 5 has computed
2009-8-20 史忠植 高级人工智能 31
决策树 ID4
1986,Schlimmer 和 Fisher 设计了 ID4学习算法,是一种递增式学习算法。他们修改 ID3算法，
在每个可能的决策树结点创建一系列表。每个表由全部未检测属性值和每个值的正例和反例数组成。
当处理一个新例时，每个属性值的正例或反例递增计量。
2009-8-20 史忠植 高级人工智能 32
决策树 ID4
输入,决策树，一个实例输出,决策树
(1) 若该实例是正例，正例数加 1，否则，反例数加 1。
(2) 如果实例全部为正例或反例，则返回决策树。
(3) 否则
(a) 计算期望信息分数。
(b) 实例中出现的每个属性、每个值，使之递增正例数或者反例数。
(c) 计算全部属性的信息分数。
2009-8-20 史忠植 高级人工智能 33
决策树 ID4
(d) 如果没有根，或者最大属性不在根结点，
则创建新树。
(i) 如果最大属性是 x2 依赖关系，那么用它作为这棵树的根结点。
(ii) 链接根到每个根属性的值
(e) 跳转到步骤 (1)，下面创建的子树链到该实例的根属性值。
2009-8-20 史忠植 高级人工智能 34
决策树 ID5
在 ID4的基础上 Utgoff提出了 ID5学习算法
(Utgoff 1988)。 ID5 与 ID4的差别在于检测属性。 ID5抛弃旧的检测属性下面的子树，从下面选出检测属性形成树。这种方法的优点是在树操纵时重新计算正例和反例的数，不要对实例重新处理。
2009-8-20 史忠植 高级人工智能 35
ID5算法
(1) 对结点每个可能的检测属性，修改属性的正例和反例数，以及修改该属性值观察值的正例数和反例数。
(2) 如果非检测属性的最低信息论测度低于当前的检测属性，则将该检测属性提上来，重新构造决策树。
(3) 在给定结点仅观察到正例或反例，那么保存其余训练实例。结束停止。
(4) 在实例描述中，对所希望检测属性值下面的决策树进行递归修改。
2009-8-20 史忠植 高级人工智能 36
ID5属性提升算法
(1) 递归地提升属性到最近子树的根结点。
(2) 对每个子树的分支值，将旧的检测属性推到新属性下，构造新的决策树。
这样，形成一组子树，每个根结点都是所希望的检测属性。
(3) 合并子树，形成决策树，其根结点是所希望的检测属性。
2009-8-20 史忠植 高级人工智能 37
决策树
Missing values
Multivalued attributes
Continuous valued attributes
2009-8-20 史忠植 高级人工智能 38
归纳学习的计算理论学习的计算理论主要研究学习算法样本复杂性计算复杂性。
2009-8-20 史忠植 高级人工智能 39
Gold学习理论在形式语言学习的上下文中,Gold引入收敛的概念，有效地处理了从实例学习的问题。
学习算法允许提出许多假设，无须知道什么时候它是正确的，只要确认某点它的计算是正确的假设。由于 Gold算法的复杂性很高
，因此这种风范并没有在实际学习中得到应用。
2009-8-20 史忠植 高级人工智能 40
Gold学习理论基于 Gold 学习框架,Shapiro 提出了模型推理算法研究形式语言与其解释之间的关系，也就是形式语言的语法与语义之间的关系。模型论把形式语言中的公式、句子理论和它们的解释 ─ 模型，当作数学对象进行研究。 Shapiro 模型推理算法只要输入有限的事实就可以得到一种理论输出 (Shapiro
1981)。
2009-8-20 史忠植 高级人工智能 41
Gold学习理论
Gold的语言学习理论研究引入两个基本概念，即极限辨识枚举辨识,
这对早期的归纳推理的理论研究起了非常重要的作用 (Gold 1967)。
2009-8-20 史忠植 高级人工智能 42
Gold学习理论极限辨识把归纳推理看作一种无限过程，归纳推理方法的最终或极限行为可以看作是它的成功标准。 假设 M是一种归纳推理方法，
它企图正确地描述未知规则 R。假设 M重复运行,R的实例集合则愈耒愈大，形成 M推测的无限序列 g1,g2,… 。如果存在某个数 m，
使得 gm 是 R的正确描述，
gm=gm＋ 1=gm＋ 2=…,
2009-8-20 史忠植 高级人工智能 43
Gold学习理论枚举辨识是第一种方法推测多项式序列的抽象，即对可能的规则空间进行系统搜索，直到发现与迄今为止的所有数据相一致的推测。
假设规定了规则的具体领域，有一个描述枚举，即 d1,d2,d3,…,
以致于领域中的每一条规则在枚举中有一种或多种描述。给定一条规则的某个实例集合，枚举辨识方法将通过这个表，找到第一个描述 d1，即与给定的实例相容，那么推测为 d1。这种方法不能确定是否会达到正确的极限辨识。如果实例表示和相容关系满足下面两个条件，那么枚举方法保证极限辨识该领域中的全部规则：
(1) 一个正确假设总是与给定的实例相容。
(2) 任何不正确的假设与实例足够大的集合或与全部集合不相容。
为了枚举方法是可计算的，枚举 d1,d2,d3,…
必须是可计算的，它必须能够计算给定的描述与给定的实例集合是相容的。
2009-8-20 史忠植 高级人工智能 44
枚举辨识算法枚举辨识算法。
输入：
一组表达式的集合 E = e1,e2,… 。
谕示 (oracle) TE提供足够的目标实例集。
排序信息的谕示 LE。
输出：
一系列假设断言 H1,H_2,…,每个假设 Hi都在 E中，并与第 i
个实例一致。
2009-8-20 史忠植 高级人工智能 45
枚举辨识算法过程：
1,初始化,i? 1;
2,examples? emptyset;
3,Loop:
3.1 调用 TE(),将 example 加到集合 examples;
3.2 While LE(ei,+x) = no,对正例集 +x,或者
LE(ei,-x) = yes,对反例集 -x,
i? i + 1;
4,输出 ei
2009-8-20 史忠植 高级人工智能 46
模型推理系统模型推理问题是科学家所面临的问题抽象，他们在具有固定概念框架的某种领域里工作，进行试验，试图找到一种理论可以解释他们的结果。在这种抽象中研究的领域是对给定的一阶语言 L某种未知模型 M的领域，实验是检测 M中 L语句的真值，目标是寻找一组正确假设，它们包含全部正确的可测试的句子。
L 语句分成两个子集：观测语言 Lo和假设语言 Lh 。假设
Lo? Lh? L‘
其中?是空语句。
2009-8-20 史忠植 高级人工智能 47
模型推理系统模型推理问题可以定义如下：假设给定一阶语言 $L
和两个子集：观测语言 Lo和假设语言 Lh。另外对 L
的未知模型 M给定一种处理机制 oracle。模型推理问题是寻找 M的一种有限的 Lo ─ 完备公理化。
求解模型推理问题的算法称为模型推理算法。
模型 M的枚举是一个无限序列 F1,F2,F3,…,
其中 Fi是关于 M的事实,Lo的每个语句发生在事实
Fi = <?,V>,i > 0 。模型推理算法一次读入给定观测语言 Lo的模型的一种枚举，一个事实，产生假设语言 Lh的语句的有限集称为算法的推测。
2009-8-20 史忠植 高级人工智能 48
模型推理系统
h 是整个递归函数。
设 Sfalse为?,Strue为 {},k 为 0。
repeat
读入下一个事实 Fn =<?,V>，
加到 Sv,
while? ∈Sfalse 以致于 Tkn?
或有一个?i ∈ Strue以致于
Tkni?i do
k = k+1，
输出 Tk
forever
2009-8-20 史忠植 高级人工智能 49
Valiant学习理论
Valiant 认为一个学习机必须具备下列性质：
(1) 机器能够证明地学习所有类的概念。
更进一步，这些类可以特征化。
(2) 对于通用知识概念类是合适的和不平常的。
(3) 机器演绎所希望的程序的计算过程要求在可行的步数内。
2009-8-20 史忠植 高级人工智能 50
Valiant学习理论学习机由学习协议和演绎过程组成。学习协议规定从外部获得信息的方法。演绎过程是一种机制，学习概念的正确识别算法是演绎的。从广义来看，研究学习的方法是规定一种可能的学习协议，使用这种协议研究概念类，识别程序可以在多项式时间内演绎。具体协议允许提供两类信息。
第一种是学习者对典型数据的访问，这些典型数据是概念的正例。要确切地说，假设这些正例本质上有一种任意确定的概率分布。调用子程序 EXAMPLES 产生一种这样的正例。产生不同例子的相对概率是分布确定的。第二个可用的信息源是 ORACLE。在最基本的版本中，当提交数据时，
它将告诉学习该数据是否是概念的正例示。
2009-8-20 史忠植 高级人工智能 51
Valiant学习理论假设 X是实例空间，一个概念是 X的一个子集。如果实例在概念中则为正例，否则为反例。概念表示是一种概念的描述，概念类是一组概念表示。学习模型是概念类的有效的可学习性。 Valiant 学习理论仅要求对目标概念的很好近似具有极高的概率。允许学习者产生的概念描述与目标概念有一个小的偏差?,它是学习算法的一个输入参数。
并且，允许学习者失败的概率为?,这也是一个输入参数。
两种概念之间的差别采用在实例空间 X的分布概率 D来评测：
diffD(c1,c2) =? D(x)
2009-8-20 史忠植 高级人工智能 52
Valiant学习理论根据协议，一个概念类 C是可学习的当且仅当有一种算法
A，使用协议，对所有的目标概念表示 c*? C 和全部分布 D，
(1) 执行时间是与 1/?,1/?,c* 数目和其它相关参数有关的多项式。
(2) 输出 C中的概念 c具有概率 1-?,
diffD(c,c*)<?
2009-8-20 史忠植 高级人工智能 53
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 54
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 55
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 56
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 57
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 58
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 59
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 60
Sn S*
经验风险置信区风险界限
h1 h* hn h
S1 S* Sn
结构风险最小归纳原理观察学习
2009-8-20 史忠植 高级人工智能 61
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 62
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 63
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 64
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 65
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 66
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 67
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 68
Support Vector Machine(SVM)
2009-8-20 史忠植 高级人工智能 69
Support Vector Machine(SVM)
