人工智能(机器学习)

§5.2     神经网络学习

§5.3     因果信念网络学习

第5章    机器学习

什么是机器学习？

归纳学习

能够学习的程序S：

任务T，性能度量P，经验E，

S能够通过经验E，改善执行任务T的性能（用P来度量）

通过 实例集{（x1,y1）,…, (xk,yk)}    求函数y=f(x)使得y1  ≈ f(x1),

yi  ≈ f(xi), …,yk  ≈ f(xk)

§5.1      归纳式学习  Inductive Learning

什么是归纳学习？和演绎推理（保真）的比较

例子，训练实例集合:

       1.(乌鸦w1，羽毛黑); 2.(乌鸦w2，羽毛浅黑);

             3.(麻雀w3，羽毛灰);4.(鸽子w4，羽毛白);  

           5.( 乌鸦w1，羽毛白);6.(偶数8,两素数3,5之和)…

根据训练实例集合提出假说HYPOTHESIS:

GOAL (乌鸦,黑色的羽毛)

1.支持性正例;2.灰色支持的正例; 3. 支持性负例;4.支持性负例

5.否定性反例;6.无关实例

要求归纳得到简洁的规则, 并使得规则的可信度高

归纳的可信度:规则的可信度是0.99%其含义为,10000个乌鸦中大约可能有1个否定性

反例(非黑的乌鸦)

决策树学习。

从数据取样(Xi,Yi), 利用外推插值方法,求函数.

决策树学习,适用于 离散性样点(Xi,Yi), Xi∈离散集合,Yi∈离散集合

从数据例子中提出有规律的假设,使其符合数据实例, 挖掘数据中的Pattern模式,规律

 Ockham’s Razor:  最简单的是最好的.

决策树

F=F（A，B，C）

挑选主要分类属性，

1．分别挑选能够把F=0，1的肯定,或否定例集合  分开的决策属性C,  使C的某种取值覆盖F肯定集合或F否定集合 的大小  尽可能地小（方法:  布尔0，1合并法）

2．对C属性的每一种取值,列出它对F肯定集合或F否定集的覆盖集合(它们分别是F肯定集合和F否定集的子集合),  进一步从其他属性中挑选能够把正反例分开的属性(递归算法)；

直到

3．某覆盖集合为空，DONE

4．决策属性集已经全部挑完，但正反例集合非空：有NOISE

F=A∧￣B ∨C

F=TRUE的取值元组集合：

+正集合   {001,011,100,101,111}0&1,&01,&11,10&,1&1&&1,

因此，C是决策分类F=TRUE的第一侯选变量；

F=FALSE的取值元组：

-负集合  { 000，010，110}  0&0,&10

因此，￣A ￣C  或     B ￣C          是决策分类F=FALSE的第一侯选变量；

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

当C选定后, C=1把 F的肯定实例集合划分为覆盖集{001,011,101,111}       ( 和非覆盖集合{100})

                        C=1把F的否定集划分为{ }空集                  和( 和非覆盖集合{000，010，110})

C=0把 F的肯定实例集合划分为覆盖集{100}       ( 和非覆盖集合{001,011,101,111})

 C=0把F的否定集划分为{ 000，010，110}集                  和( 和非覆盖集合{}空集)

举例2 

学习目标:根据数据集,  总结出  影响客户愿意排队等待的因素

GOAL: 愿意排队等待

属性集合

例    附近 地方大    星期  肚子饿  人多  菜价格   正在   预定  饭店  等待  

编   还有                5，6                不多                下雨    位置    类型  时间      

号

Ex  Alt     Bar        Fri      Hun       Pat       Price    Rain     Res   Type      Est       Wait?

X1  Y      N            N        Y      Some         high    N     Y    French         0-10     Y

x2  Y      N             N       Y       Full            low    N     N    Thai           30-60     N

x3   N      Y            N       N       Some       low     N     N    Burger    0-10     Y

x4  Y       N          Y       Y      Full            low    N     N    Thai       10-30     Y

x5  Y       N          Y       N       Full        high   N     Y    French     >60       N

x6  N       Y          N       Y       Some           med     Y     Y    Italian    0-10      Y

x7  N       Y          N       N       None       low       Y     N     Burger    0-10       N

x8  N        N         N       Y       Some       med     Y     Y     Thai       0-10     Y

x9   N      Y         Y        N       Full        low       Y    N    Burger     >60        N

x10  Y       Y        Y        Y       Full         high    N    Y    Italian    10-30      N

x11  N       N        N        N       None         low      N    N     Thai          0-10       N

x12  Y       Y        Y        Y        Full        low      N    N    Burger     30-60     Y

 从数据例子中提出有规律的假设,使其符合数据实例, 挖掘数据中的Pattern模式,规律

 Ockham’s Razor:  最简单的是最好的.

决策树的构成法:  首先挑选最重要的属性变量来划分数据集

1.根据目标把数据集合划分为两个子集合,  肯定集 GOAL=YES

      和否定集GOAL=NO

2. 选择一个主要属性, 使得它的每一个取值分支, 所覆盖的肯定集 GOAL=YES      和否定集GOAL=NO   有存在空集的覆盖集合

3. 对它的每一个取值分支,所对应的GOAL肯定集 和否定集,递归地重复

          以上第2步,直到某覆盖集合为空DONE    或决策属性集已经全部挑完，

             但正反例集合非空：有NOISE

下面是另一个例子

决策树划分和熵ENTROPY

12个电影(电影实例集合),其中4个认为是正面的,8个是被认为反面的 ,这代表某种电影评价倾向.

现在想用:电影分类特性X:轻喜剧,恐怖,经典分类 ;来探讨该电影评价倾向所根据的特性是否和X电影分类特性一致?

对电影实例数据集合的划分,使得我们对电影评价问题认识深化;

熵ENTROPY 减少;系统从无序向有序过渡;

ENTROPY  的定义

|S|=12共12部电影; m=2正反两类电影;|S+|=4;|S-|=8;

Entropy(S)= -[(4/12)log(4/12)+(8/12)log(8/12)]=

1/3(log3)+2/3 (log3-1)=0.52835+0.39003=0.918383

∑为  (4/12)*0 + (4/12)*(-1) + (4/12)*(-1)= -2/3 = -0.666667

gain=0.25172

default 表示 没有实例描述,无法决定该属性取值

对 肯定或否定 电影实例分类有帮助.

YES分支 对 “肯定” 电影实例分类有帮助, 

NO分支 对 “否定” 电影实例分类有帮助.

决策树归纳式学习的不足:

1.仅仅对离散型取值变量有效,对连续型取值(例如钱)必须离散化,

       人工痕迹大

2.训练实例集合可能    有矛盾(相同的X,不同的Y); ---NOISE

例如饭馆排队的例子,如果有三个训练例子  ‘队很长 且听说要等>60分钟’则走人

但同时有1个训练例子  ‘队很长 且听说要等>60分钟’则不走继续等;

可以忽略后者.

3.决策树熵增益方法挑选属性的方法 偏向于取值集合大(值域宽)的变量, 熵增益容易增大.

4.OVERFITTING,牵强附会

归纳学习的一个大缺点是, OVERFITTING: 把一些和GOAL无关但训练集合出现的属性变量  表面地联系在一起.例如饭馆排队的例子,和菜价是否昂贵关系不大

熵增益很小.但小到多小就不于考虑呢?

统计学的理论告诉我们, 可以对GOAL和训练实例集合进行  无规律模式的统计学检验---χ^2分布表的标准检验,

*另一个方法是,把训练实例集合中,事先随意取出一个子集合,作为假说(归纳函数)

的检验集合,用统计学方法,可以计算得出该归纳假说的可信程度.

5.训练实例集合增大时,如何推广 或 缩窄 已经提出的假说

§5.2人工神经网络

大脑在  解决问题的健壮性（robustness,在意外情况下得出合理的解答）

    在  学习解决新问题等方面，它比计算机要高明得多；

但是计算机在精确计算方面，比人的大脑要高速得多；

dendrites树状神经突触（输入部）  可以分支接过多个外界synapse  树状分支末鞘

axon   神经轴突（输出轴突），synapse  树状分支末鞘

nucleur 神经元的细胞体，细胞核

人的大脑10^11个NEURON神经元，平均每一个神经元和10000个神经元相连，

神经元的开关时间约10^-3 秒；[CPU  1000    MHZ]

存储信息单元数量  10^14个 SYNAPSE突触，存储权重;[DISK 100 GBYTE]

通信带宽10^14—10^16  bit/s;  [10^4个CPU ，1000 MHZ ，BIT]

神经元 的激励函数activation function 表示了 输入X空间的 一种决策分割函数 ，线性分割算子

g(x)=sigmoid(x)有导数，是可微的,    g’(x)= g(x) * (1－g(x))

三维的线性 分割函数(算子)  f= 3 - 2*（x+y+z）

神经网络学习

给定上述人工神经网络， 以及 一组学习样本（k个）

目标是求假说空间{ （w1，w2，w3，w4）} 中的一个向量（权重向量）

使得   

从统计学来说，神经网络的归纳假说问题  属于 非线性回归研究；

学习机制：   wt  :=  wt +  alpha * xt * delta[ y – f ],  t=1,2,3,4

alpha是一个常数，被称为 学习比率，

这是在假说空间{ （w1，w2，w3，w4）} 中的一种 沿曲面E梯度下降 爬山搜索法；使得E达到最小值

由于 线性可分算子 在假设空间存在一个极值点，且仅仅存在一个极值点，

所以上述梯度下降的 爬山搜索法对于线性可分算子函数是一定收敛的。

对于非线性可分函数，以及一般函数的归纳学习问题，

必须研究复杂结构的神经网络。

两层的神经网络：n个刺激x输入，m+1个神经元：

两层     n=5，m=5

输入n个

中间层（隐藏层hidden layer，m个神经元）

输出层， 神经元一个

Yi – fi 被称为 误差量，Yi是训练值

有下列记号：

  是学习比率

人工神经网络学习和决策树学习的区别，单层网络和双层网络的不同表达能力

单层前聩式神经网络：对于可分割函数seperable functions，学习过程是收敛的；

        但单层前聩式神经网络不能近似表达任意连续函数，

        必须使用双层神经网络，亦即需要引入隐层（中间层hidden layer），

        如果引入两层隐层，则可以表达任意非连续的函数。

例子。对于餐馆等待问题（11个感知输入），决策树学习在使用10-80个训练样本达到90%以上检测正确率，而对于单个神经元学习，80训练样本仅仅达到60%左右的正确率；

反之，对另一个例子多数表决函数（11中取≥6）问题，单个神经元学习在使用80个训练样本达到98%检测正确率，而同样训练样本决策树学习，检测正确率仅仅达到70%左右

多层次分布式神经网络        例子，信件的邮政编码自动识别系统，

        256个（16×16）的输入接受神经元，3层隐层（768=12×，192，30个神经元），检测12个相对的0—9的数字特征，聩接10个分布式输出神经元（代表0—9数码），此神经网络总共有9760个权需要学习，经过7300训练样本学习，和2000个测试样本，识别正确

率达到99%

总结,     具有学习能力的行动AGENT 

[*analytical式学习（利用  领域知识 对训练实例进行分析，对目标概念  给出有效可操作的定义函数）]

[*监督式学习分类（决策树方法学习概念），和无监督式学习分类（学习建造函数，函数值未随实例给出，聚类算法）]

[*奖惩式reinforce学习;   学习生存和行动的策略，在遇到各种情况（situation,states）下，如何选择适当的行动；  有老师给出reward]；

[   学习环境(状态是否可完全感知) ;可否自动探测环境;]；[   行动的效果是   

 否有确定性;  是否所有环境状态都提供学习奖惩]

A.Supervised learning 

  concept learning 

*#Learning from examples 

*#Function learning 

*#Data is labeled 

B. Unsupervised learning 

*#Data is not labeled 

*#Data needs to be grouped, clustered 

*#Need distance metric 

*#Hard! 

C.Reinforcement learning 

*#Classification is not available 

*#Reward is available 

D.   Action selection learning ,Control learning 

 Based on the percepts from the environment, it needs to decide what action to take. 

         **Needs ``evaluation'' of percepts,and Environment: 

*#  accessible  : states can be identified with percepts 

*#  inacessible :  agent maintains and relies on internal state 

**Initial knowledge: 

*#  known model ?effects of actions in the environment are known 

*#  unknown model ?needs to learn effects of actions too 

**Reward: 

*#  only in a few, terminal states, or in any state 

 **Learner: 

*#  passive :observes the world and learns the utility of states;  no acting2explore 

*#  active :  passive + acting using the learned information

归纳学习和analytical(deductive)解析式学习;

归纳学习inductive learning的特点：

1.DATA-INTENSIVE；2。从多个实例中抽象提取出一般的概念定义（它的 重要性质取值）

演绎学习deductive learning  的特点

1．Knowledge intensive; 2.从单个例子中解释分析为什么这个例子是该概念  

 的代表；3。提出描述该概念的一个充分条件4。用于分析新的实例

实例The SAFE to STACK Example 

A.Input: 一个实例

target concept: SAFE-TO-STACK(x,y) 

only one training example: 

ON(OBJ1,OBJ2) 

ISA(OBJ1, BOX) ;ISA(OBJ2, ENDTABLE) 

COLOR(OBJ1, RED); COLOR(OBJ2, BLUE) 

VOLUME(OBJ1,1) ; DENSITY(OBJ1,0.1); ... 

B.   domain theory: 领域的逻辑理论

1. NOT(FRAGILE(y)) or LIGHTER(x,y)  

SAFE-TO-STACK(x,y) 

2. VOLUME(x,v) and DENSITY(x,d)  

WEIGHT(x,v*d) 

3. WEIGHT(x1,w1) and WEIGHT(x2,w2) and 

LESS(w1,w2)  LIGHTER(x1,x2) 

4. ISA(x,ENDTABLE)  WEIGHT(x,5) 

5. LESS(0.1,5) ;... 

C.operationality criterion: 

进行回归解释的操作准则，从什么方面入手进行解释？

          可以使用的术语，领域知识 和 普通常识

    learned description should be built of terms used to 

    describe examples directly, or other ``easily'' evaluated, 

     such as LESS. 

 做演绎逻辑推理，对目标概念进行“目标回归”

 Explain why obj1 is SAFE-TO-STACK on obj2. 

* Construct a proof. 

*Do Goal regression: regress target concept through 

              proof structure. 

 *Proof isolates relevant features. 

SAFE-TO-STACK(OBJ1,OBJ2) 

           LIGHTER(obj1,obj2) 

WEIGHT(obj1,0.1) ;    LESS-THAN(0.1,  5.0) ;      WEIGHT(obj2,  5) 

VOLUME(obj1,1) ; DENSITY(obj1,  0.1) ;             ISA(obj2, ENDTABLE) 

*如果想把积木A放在积木B之上，那么应该注意分析A，B的重量；

*积木重量是由体积和密度决定的

*积木重量也可以由它是否直接摆在桌子上来估计；

**比较重量的方法可以用减法；

用途？    基于领域知识的对实例解释学习的用途

EBL: A Deductive Learning Method 

#Why are examples needed? 

#Domain theory contains all the information: simply 

operationalize target concept. 

**Examples help to focus on the relevant 

operationalizations: characterize only examples that actually occur. 

Actual purpose of EBL: 

*not to ``learn'' more about target concept, 

* but to ``re璭xpress'' target concept in a more operational manner =efficiency). 

*control learning.

PRODIGY系统

(CONTROL-RULE  SELECT-OP-PUTDOWN-FOR-ARMEMPTY 

(if (and (current-goal   (arm-empty)) 

(true-in-state (holding ))))

(then  select operator  PUT-DOWN)) 

(CONTROL-RULE SELECT-BINDINGS-PUTDOWN 

(if (and  (current-ops (PUTDOWN)) 

(true-in-state (holding ))))

(then select bindings ((, ))))

PRODIGY系统

Learn control rules to prefer operators, bindings, and goals 

in domain璱independent fashion. 

 Learning is driven by failure, when current control strategy 

must be overridden. 

 If the quality metric changes, the learned knowledge 

is invalidated and re-learned. 

 Limited class of quality metrics. 

Tradeoffs in the quality factors lead to conflicts between rules.

非监督聚类学习

问题举例

要求把下列训练实例划分为两类，并符合下列要求的准则

1．不要排除任何例外实例

2．使sparseness=

                   1 － （X类包含的训练实例数目）/（X类的不同取值总数目）

3．分类所使用的属性描述应该尽可能简单（用来描述分类的属性个数少）

类一：X1≤1且X3≤1

类二：X1=2

§5.3  因果信念网络的BAYES学习方法

问题的提出:

已知因果信念网络结构, 通过训练样本学习条件概率.

  (1) 训练样本集合,和因果信念网络结构内的随机变量能够对应上

    (2) 训练样本集合 不包含某些随机变量H  (因果信念网络结构内的)

例如

(3)通过训练样本评估几个候选的因果信念网络结构

例子,  两个不同位置的天文台A,B,观测同一个太空区域, 

         计数估计其内含的星星总数   .   

         A,B分别测得两个数据Ma ,  Mb,   (带有粗心误差, M数字 1);

        他们的计数误差来自于(除 粗心误差外) 望远镜仪器调整不佳 (星星数误差3)

        设   仪器调整不佳随机事件   为Fa,Fb;   以及待估计未知的太空星数为N

训练样本

P(Fa),P(Fb)   <  0.01;

问:         左或右那一个因果网络图是更为恰当的?

Naive Bayes分类器

已知属性元组

NB分类器的任务是:

在已知训练样本集合

条件下进行分类:      对任意给定的一个新元组(a1,…an), 求它应归属的最合适类:

A PRIORI               先验,由已知原因推测其效果

A POSTERIORI     后验,由后果反推测其原因

最后一个式子需要有一定的性假定:  在已知归属类vj的条件下,  各个属性x1,…xn取值a1,..an的联合概率是各自取值条件概率的乘积;

通过训练样本和下列’概率的m-估计公式’,  可以求出以上公式中的各个概率.

概率的m-估计公式

概率估计=(nt + m*p)/(n + m)

其中nt为样本中命中某类t类的次数

       n  为样本总数

       m是母本空间大小和样本集大小n的比例

       p是先于这一元组(a1,…an)之前,对类t相对于其他类在母体中的频率估计

对于问题(1)型已知因果信念网络结构,

直接学习法

通过训练样本, 改进条件概率分布P( v | a1, …,an), 

               {v, a1, …,an}   训练样本的属性集.

1．收集足够大的样本集合H={ ( v, a1, …,an ) }

2．将样本集合H 分割为二  H = H1 + H2

3．对H2集合的每一个样本( v, a1, …,an )，进行下列循环计算

导致的后果:

1.暴风雨导致: 闪电, 或/和 帐棚火灾, 或/和 森林火灾

2.旅游团导致: 帐棚火灾

3.闪电导致:  雷鸣,和森林火灾

4.帐棚火灾导致: 森林火灾

引起的原因:

a.帐棚火灾的原因来自: 暴风雨和旅游团(strm= ,btour= ,campfire= ) 

b.森林火灾的原因来自: 帐棚火灾 和闪电 和暴风雨

     (campfire= ,lightng= ,strm= ,forstfire= )

c.闪电的原因来自: 暴风雨    (strm= ,lightng= )

d. 雷鸣的原因来自: 闪电     (lightng= ,thundr= )

当样本集的元组属性 取‘全部属性’形式，例如

(strm=yes ,btour= yes,campfire= no,lightng= no,thundr= no,

                                                       forstfire= yes)

 这时 对任意一个属性V（随机变量）和它的parents属性(A1,…,An)

由于这些属性它们都在样本属性集中出现，可以直接利用NB分类器算法.

用梯度下降法学习改进  因果条件概率表

训练样本集合 不包含某个或某些个随机变量U  (因果信念网络结构内的非样本  变量U)，  例如

梯度下降法学习条件概率wij

在样本集合D不能完全覆盖因果信念网络的随机变量集合时，学习改进网络中各个随机变量U和它的parents(Y)之间的条件概率表

对于上述条件概率表的每一个条件概率值wij[0，1]

做迭代修改，其中西格马（和号）遍历样本集合全部样本。

当变量组（Y,U）的条件概率表的各个wij学习更新的同时，必须注意

概率表wij的值需要进行归一化计算，使条件概率表每一列之和归一化为1

上述学习改进条件概率的公式来自于寻找目标函数概率P（ D| h）的极大值，

可以证明，求目标函数概率P（ D| h）的对数的导数，可以简化为下列公式：

其中h表示假说：因果信念网络的随机变量U和它的parents  Y取固定值ui,yj

除了以上使用“梯度上升法学习条件概率wij”的算法 以外，还有 其他利用更多统计学知识的算法，例如EM算法等