第5章 机器学习§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 (乌鸦,黑色的羽毛))()()()()()(x ￣x ￣x x x ￣x x x 乌鸦黑黑乌鸦亦即，黑乌鸦→∀∨→∀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．某覆盖集合为空，DONE4．决策属性集已经全部挑完，但正反例集合非空：有NOISEF=A∧￣B ∨CF=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: 愿意排队等待Training Set and DT representation例附近地方大星期肚子饿人多菜价格正在预定饭店等待编还有 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 Yx2 Y N N Y Full low N N Thai 30-60 Nx3 N Y N N Some low N N Burger 0-10 Yx4 Y N Y Y Full low N N Thai 10-30 Yx5 Y N Y N Full high N Y French >60 Nx6 N Y N Y Some med Y Y Italian 0-10 Yx7 N Y N N None low Y N Burger 0-10 N x8 N N N Y Some med Y Y Thai 0-10 Yx9 N Y Y N Full low Y N Burger >60 Nx10 Y Y Y Y Full high N Y Italian 10-30 Nx11 N N N N None low N N Thai 0-10 Nx12 Y Y Y Y Full low N N Burger 30-60 Y从数据例子中提出有规律的假设,使其符合数据实例, 挖掘数据中的Pattern模式,规律Ockham‘s Razor: 最简单的是最好的.决策树的构成法: 首先挑选最重要的属性变量来划分数据集1.根据目标把数据集合划分为两个子集合, 肯定集 GOAL=YES和否定集GOAL=NO2.选择一个主要属性, 使得它的每一个取值分支, 所覆盖的肯定集 GOAL=YES 和否定集GOAL=NO 有存在空集的覆盖集合3.对它的每一个取值分支,所对应的GOAL肯定集和否定集,递归地重复以上第2步,直到某覆盖集合为空DONE 或决策属性集已经全部挑完，但正反例集合非空：有NOISE下面是另一个例子决策树划分和熵ENTROPY12个电影(电影实例集合),其中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.918383ss p p p entropy i i mi i i /;log(12=-=∑=实例划分）∑为 (4/12)*0 + (4/12)*(-1) + (4/12)*(-1)= -2/3 = -0.666667 gain=0.25172 )()(,(i mi i S Entropy S S S Entropy S gain ∙-=∑划分）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 ，64BIT]神经元的激励函数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,4alpha 是一个常数，被称为 学习比率，这是在假说空间{ （w1，w2，w3，w4）} 中的一种 沿曲面E 梯度下降 爬山搜索法；使得E 达到最小值由于 线性可分算子 在假设空间存在一个极值点，且仅仅存在一个极值点， 所以上述梯度下降的 爬山搜索法对于线性可分算子函数是一定收敛的。

对于非线性可分函数，以及一般函数的归纳学习问题，必须研究复杂结构的神经网络。

{为训练值kk k k k k y y y x x x x y x x x x ,...,,)},,,,(),....,,,,,(14321114131211尽可能小;,...1,),,,,,,,(43214321k i y w w w w x x x x f ii i i i =-∑=-=k i i i i i i y w w w w x x x x f E 1243214321]),,,,,,,([(21两层的神经网络：n 个刺激x 输入，m+1个神经元：两层 n=5，m=5输入n 个中间层（隐藏层hidden layer ，m 个神经元）输出层， 神经元一个)((),...,(10011∑==++∙∙∑=nk j k j k j m j n W W x W g W g x x fYi – fi 被称为 误差量，Yi 是训练值有下列记号：)())(())((010011j nk k j k j m j nk k j k j jW x W g W W x W g W g x f y W E ∑∑∑===+⋅⋅⋅++⋅⋅'⋅--=∂∂kj nk k j k j j m j nk k j k j jk x W x W g W W W x W g W g x f y W E ⋅+⋅'⋅∙++⋅⋅'⋅--=∂∂∑∑∑===)())(())((010011∑==++∙∙∑==n k j k j k j mj n W W x W g W g x x f x f 10011)((),...,()(献对输出神经元的输入贡=++⋅⋅=∑∑==0011)(W W x W g W in j m j nk k j k j ;:;:)()(;)()())((;;)(0101k j j k j k j j j j n k k j k j j j j k j k j j jk j jj nk k j k j x W W a W W W x W in in g W x x in g W W Ej k in g x f y a W EWj j j W x W g a ⋅∆⋅+=⋅∆⋅+=+⋅='⋅⋅∆=∆⋅∆-=⋅'⋅⋅∆-=∂∂'⋅-=∆⋅∆-=∂∂=+⋅=∑∑==αα则：以下为（权值）学习规以及其中的输出权到中间层神经元对于每一个输入神经元其中到输出的权元对于每一个中间层神经个神经元的输出中间层第因此，是学习比率人工神经网络学习和决策树学习的区别，单层网络和双层网络的不同表达能力单层前聩式神经网络：对于可分割函数seperable functions，学习过程是收敛的；但单层前聩式神经网络不能近似表达任意连续函数，必须使用双层神经网络，亦即需要引入隐层（中间层hidden layer），如果引入两层隐层，则可以表达任意非连续的函数。