智能决策理论与方法2课件

1、决策理论与方法(4) 智能决策理论与方法(2)合肥工业大学管理学院Monday, August 1, 2022智能决策理论与方法1、智能决策理论的形成背景2、知识发现3、机器学习4、不确定性理论决策理论与方法-智能决策理论与方法机器学习机器学习是从模拟人类的学习行为出发，研究客观世界和获取各种知识与技能的一些基本方法（如归纳、泛化、特化、类比等），并借助于计算机科学与技术原理建立各种学习模型，从根本上提高计算机智能和学习能力。研究内容是根据生理学、认知科学对人类学习机理的了解，建立人类学习的计算模型或认知模型；发展各种学习理论和学习方法，研究通用的学习算法并进行理论上的分析；建立面向任务且具有

2、特定应用的学习系统。决策理论与方法-智能决策理论与方法机器学习归纳学习：泛化归纳学习是指从给定的关于某个概念的一系列已知的正例和反例中归纳出一个通用的概念描述。泛化(Generalization)是用来扩展一假设的语义信息，使其能够包含更多的正例。泛化所得到的结论并不总是正确的。常用泛化方法：将常量转为变量规则：对于概念F(v)，如果v的某些取值a,b,使F(v)成立，则这些概念可被泛化为：对于v的所有值，F(v)均成立：决策理论与方法-智能决策理论与方法机器学习归纳学习：泛化消除条件规则：一个合取条件可看作是对满足此概念的可能实例集的一个约束。消除一个条件，则该概念被泛化。添加选项：通过添加

3、更多条件，使得有更多的实例满足概念而使该概念泛化。该规则特别有用的方式是通过扩展某个特定概念的取值范围而增加选项。将合取转为析取规则决策理论与方法-智能决策理论与方法机器学习归纳学习：泛化爬升概念树规则：通过爬升概念树，低层概念被较高层概念替代。设A表示信息系统中的某个属性如Animal，a,b,分别为对象u,v,在属性A上的取值，若s是概念树上a,b,的父结点，则基于概念树爬升的泛化规则表示为： Nick等人给出了一种面向属性的归纳算法。过度泛化问题当某个属性被爬升至过高的概念层会导致冲突的产生，这种现象称为过度泛化。克服过度泛化必须有相应的终止泛化算法的策略。决策理论与方法-智能决策理论与

4、方法机器学习归纳学习：泛化动物哺乳类鸟类企鹅食肉类蹄类飞禽类走禽类虎印度豹长颈鹿斑马信天翁鹰驼鸟第1层第2层第3层第4层决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树决策树学习是以实例为基础的归纳学习算法。所谓决策树是一个类似流程图的树结构，其中树的内结点对应属性或属性集，每个分枝表示检验结果(属性值)，树枝上的叶结点代表所关心的因变量的取值(类标签)，最顶端的结点称为根结点。决策树学习采用自顶向下的递归方式，在决策树的内部结点进行属性值比较并根据不同的属性值判断从该结点向下的分支，在叶结点得到结论。从根结点到每个叶结点都有唯一的一条路径，这条路径就是一条决策“规则”。当经过一批训

5、练实例集的训练产生一颗决策树，那么该决策树就可以根据属性的取值对一个未知实例集进行分类。所有的决策树都有一等价的ANN表示；也可用SVM实现相同的功能。决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树A0A1A2A3类0000-10001-10010-10011-101001010110110101111A0A1A2A3类1000-11001-11010-11011-111001110111110-11111-1A0A1A1A2-11-11-110010110决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树概念学习系统CLS(Hunt)：从一颗空的决策树出发，添加新的判定结

6、点来改善原来的决策树，直到该决策树能够正确地将训练实例分类为止。产生根节点T，T包含所有的训练样本；如果T中的所有样本都是正例，则产生一个标有“1”的节点作为T的子节点，并结束；如果T中的所有样本都是反例，则产生一个标有“-1”的节点作为T的子节点，并结束；选择一个属性A(如何选?)，根据该属性的不同取值v1,v2,vn将T中的训练集划分为n个子集，并根据这n个子集建立T的n个子节点T1,T2,Tn，并分别以A=vi作为从T到Ti的分支符号；以每个子节点Ti为根建立新的子树。决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树A0A1A1A2-11-11-110010110T2T1T11

7、T12T111T112T21T22T决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树ID3算法(Quinlan)：ID3算法对CLS做了两方面的改进：(1)增加窗口技术；(2)以信息熵的下降速度(信息增益)作为测试属性选择标准。窗口技术：对于训练集很大的情形可选择其某个子集(称为窗口)构造一棵决策树，如果该决策树对训练集中的其它样本的判决效果很差，则扩大窗口，选择不能被正确判别的样本加入到窗口中，再建立一个新的决策树，重复这个过程得到最终的决策树，显然不同的初始窗口会产生不同的决策树。决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树信息增益 ：设决策树根结点的样本数据为X=

8、x1,x2,xn，称X的两个训练子集PX(对应类标签为1)和NX (对应类标签为-1)为正例集和反例集，并记正例集和反例集的样本数分别为P和N，则样本空间的信息熵为 假设以随机变量A作为决策树根的测试属性，A具有k个不同的离散值v1,v2,vk，它将X划分为k个子集，且假设第j个子集中包含Pj个正例，Nj个反例，则第j个子集的信息熵为I(Pj,Nj)。决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树以A为测试属性的期望信息熵为以A为根节点的信息增益是：Gain(A)=I(P,N)-E(A)ID3的策略就是选择信息增益最大的属性作为测试属性。ID3的问题：测试属性的分支越多，信息增益值

9、越大，但输出分支多并不表示该测试属性有更好的预测效果。决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树A0A1A2A3类0000-10001-10010-10011-101001010110110101111A0A1A2A3类1000-11001-11010-11011-111001110111110-11111-1类似地，求出E(A1)，E(A2)，E(A3)。比较它们的大小，选择期望信息熵最小的属性作为根结点。依次构造子决策树，直至所有的训练样本均能够被正确分类。决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树信息增益率：其中： 目前一种比较流行的决策树算法C4.5算法

10、就是以信息增益率作为测试属性的选择条件。生成的决策树往往过大，不利于决策时的应用，需要对其剪枝(Pruning)，请参阅相关文献。决策理论与方法-智能决策理论与方法机器学习神经网络 神经网络(Artificial Neural Networks)是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应(T.Koholen)。神经网络分为前向型、反馈型、随机型以及自组织型。我们重点介绍一下前向型网络及其学习算法。决策理论与方法-智能决策理论与方法基本神经元及感知机模型：机器学习神经网络wj1wjiwjnyjf(iwijxi-j)x1xixn决策

11、理论与方法-智能决策理论与方法机器学习神经网络神经元函数f的选择线性函数：f(x)=x带限的线性函数：为最大输出。阈值型函数：sigmoid函数：决策理论与方法-智能决策理论与方法机器学习神经网络 感知机学习算法：(选取f为阈值函数，学习权值向量w)(1)初始化：将权值向量和阈值赋予随机量，t=0(2)连接权的修正：设训练样本的输入为x1,., xi,.,xn，期望输出为yj，进行如下计算：计算网络输出：y(t)= f(iwij(t)xi(t)-j(t)计算期望输出与实际输出的误差：e(t)=yj-y(t)若e=0，则说明当前样本输出正确，不必更新权值，否则更新权值和阈值 wij(t+1)=

12、wij(t)+yjxi(t)；j(t+1)=j(t)+yj t=t+1(为学习率)(3)返回(2)，重复所有的训练样本直到所有的样本输出正确。决策理论与方法-智能决策理论与方法机器学习神经网络多层前向神经网络：包括一个输入层、一个输出层以及多层隐单元。x1xixIy1ykyK输入层隐含层输出层u1uiuIv1vjvJwjiwkj决策理论与方法-智能决策理论与方法机器学习神经网络隐含层的接受与投射(以隐含层第j个神经元为例)：接受：第j个神经元的值来自于前一层网络(本例是输入层)输出值的加权和，即netj=iwjiui。投射：将第j个神经元的值经过变换f(netj)，作为下一层网络(本例是输出层

13、)的输入，一般f(x)=1/(1+e-x)。因此可得到yk=jwkjf(netj)。上述过程一直持续到所有的输出单元得到输出为止，最后一层的输出就是网络的输出。因此，神经网络是一个黑匣子。决策理论与方法-智能决策理论与方法机器学习神经网络BP算法：BP算法的核心是确定W的调节规则(学习规则)，使实际的输出Y1(t)尽可能接近期望的输出Y(t)。误差函数：对于每种输入模式特征矢量(x1,x2,xI),都有对应的输出矢量(y1,y2,yK)作为训练网络的输出参考基准。如果用符号Xp表示第p个输入模式特征矢量，用符号Yp表示对应的第p个输出基准矢量。在训练时，同时按输入输出矢量对(Xp,Yp)给出训

14、练集(p=1,P)。对于每个Xp，按照神经元的输入输出公式，一个个一层层地求出网络的实际输出Y1p，则误差函数定义为：决策理论与方法-智能决策理论与方法机器学习神经网络权重调节策略：学习的目标是使E最小或不大于规定的误差。从理论上可用求极值的方法获得权值调整的一种典型规则：其他最流行的网络结构：径向基函数(RBF)神经网络、自组织映射(SOM)、Hopfield网络等。Matlab提供了一套神经网络工具箱(Neural Networks Toolbox)，其中包含了一组new函数，用以创建各种类型的神经网络。决策理论与方法-智能决策理论与方法机器学习神经网络newcfcascade-forwa

15、rd backpropagation network.newelmElman backpropagation network.newfffeed-forward backpropagation network.newfftdfeed-forward input-delay backprop network.newgrnngeneralized regression neural network.newhopHopfield recurrent network.newlvqlearning vector quantization networknewpnnprobabilistic neural

16、 network.newrbradial basis network.newrbeexact radial basis network.newsomself-organizing map决策理论与方法-智能决策理论与方法机器学习神经网络MatLab工具箱之多层前向BP网络示例P = 0 1 2 3 4 5 6 7 8 9 10;&输入T = 0 1 2 3 4 3 2 1 2 3 4;&期望输出net=newcf(0 10,5 1,tansig purelin);创建一个BP网络，最小输入为0，最大输入为10，两隐含层，第一层神经元（5个神经元）函数为tansig函数，第二层神经元（1个神经元

17、）函数为purelin函数。Y = sim(net,P);&实际输出(未学习)plot(P,T,P,Y,o)net.trainParam.epochs = 50;&迭代次数net = train(net,P,T);&网络训练Y = sim(net,P);&实际输出(已学习)plot(P,T,P,Y,o)决策理论与方法-智能决策理论与方法机器学习神经网络决策理论与方法-智能决策理论与方法机器学习支持向量机提出的背景(针对神经网络的不足)1. 大量的控制参数。神经网络的结构、传输函数、损失函数、学习参数、训练算法以及训练代数都需要基于反复试验的方法获得。 2. 存在过度拟合问题。许多现实的数据包含

18、大量的噪声，如果神经网络规模太大，并且网络训练时间控制不适当，那么神经网络将不但获得数据中的有用信息而且会得到不希望的噪声。其结果它们只能记忆到训练数据点，而对训练数据以外的样本点泛化能力很差。决策理论与方法-智能决策理论与方法机器学习支持向量机3. 局部极小值问题。神经网络训练过程中主要使用梯度下降的算法，容易陷入局部极小值。4.收敛速度慢。神经网络主要采用基于梯度的BP学习算法，当用于大规模问题时收敛慢。5. 黑箱问题。神经网络没有明确的函数形式解释输入和输出变量之间的相互关系，很难解释从神经网络获得的结论。20世纪90年代Vapnik提出了支持向量机(Support Vector Mac

19、hines,SVM)，它被看作是高维空间函数表达的一般方法。使用SVM方法，人们可以在很高维的空间里构造好的分类规则。决策理论与方法-智能决策理论与方法机器学习支持向量机SVM提供了一种分类算法统一的理论框架，这是理论上的一个重要贡献。感知器只能解决线性分类问题；通过添加隐含层神经网络可以处理线性不可分问题，因而产生了BP网络。现已证明，当隐含层可以任意设置时，三层BP网络可以以任意精度逼近任一连续函数，但隐含层神经元的理论意义不清楚。SVM方法的出现，从理论上解释了隐含层的作用，即它是将输入样本集变换到高维空间，从而使样本可分性得到改善，即神经网络学习算法实际上是一种特殊的核技巧。另外，因为

20、支持向量通常仅为训练数据集的一小部分(解的稀疏性)，因而加快了训练过程的收敛速度。决策理论与方法-智能决策理论与方法机器学习支持向量机结构化风险最小化与经验风险最小化原则经验风险最小化原则 考虑分类问题。样本集为U=x1,x2,.,xl(m维空间中的l个向量)，每个向量对应一个类别，类别空间Y=+1,-1。记p(x,y)表示对象x为y类的概率分布。分类的任务就是寻找分类器f：UY且使期望风险最小。f的期望风险为： 在有限样本的情况下，p(x,y)是未知的，因此期望风险无法计算。常使用经验风险代替，且当l时两者相等。决策理论与方法-智能决策理论与方法机器学习支持向量机如果 成立，则称经验风险最小

21、化原则（Empirical Risk Minimization, ERM）具有一致性。结构风险最小化原则 Vapnik在1971年证明经验风险最小值未必收敛于期望风险最小值，即ERM不成立。因此提出了结构风险最小化原则(Structural Risk Minimization, SRM)，为小样本统计理论奠定了基础。决策理论与方法-智能决策理论与方法机器学习支持向量机Vapnik和 Chervonenkis通过研究，得出了期望风险和经验风险的如下关系以概率1-成立，即 l为样本点数目；参数01；h为函数f的维数，简称VC维。(在无法求得期望风险的情形下找到了它的一个上界)不等式右边与样本的具体

22、分布无关，即Vapnik的统计学习理论无需假设样本分布，克服了高维分布对样本点需求随维数而指数增长的问题。这是小样本统计理论与经典统计理论的本质区别，也是将Vapnik统计方法称之为小样本统计理论的原因。VC维置信度决策理论与方法-智能决策理论与方法机器学习支持向量机讨论：(1)如果l/h较大，则期望风险(实际风险)主要由经验风险来决定，因此对于大样本集经验风险经常能给出较好结果。(2)如果比值l/h较小(小样本集)，则小的经验风险并不能保证有小的期望风险值，必须同时考虑经验风险和置信范围(称之为VC维置信度)。VC维在其中起重要作用，实际上置信范围是h的增函数。在样本点数目l一定时，分类器越

23、复杂，即VC维越大，则置信范围越大，导致实际风险与经验风险的差别越大。结论：要想使实际风险最小不仅要使经验风险最小，还同时需要使分类器函数f的VC维h尽可能最小，这就是结构风险最小化原则。因此寻找最小属性集变得非常有意义。决策理论与方法-智能决策理论与方法机器学习支持向量机支持向量分类模型基本分类思想：支持向量机的核心思想是将结构风险最小化原则引入到分类问题中。从线性可分情况下的最优分类超平面发展而来的，其本质是在训练样本中找出具有最优分类超平面的支持向量。在数学上归结为一个求解不等式约束条件的二次规划问题。决策理论与方法-智能决策理论与方法机器学习支持向量机margin与支持向量： 设样本集

24、为U=x1,x2,.,xl(m维空间中的l个向量)，类别空间Y=+1,-1。xi为输入向量，对应的类标签为yi(+1或-1)。若样本集是线性可分的，则存在超平面H：wx+b=0使得 (1)当wxi+b1时，yi=+1 (2)当wxi+b-1时，yi=-1 其中，w为权值向量，b为偏离值。统一(1),(2)得：yi(wxi+b) 1 对于样本集的任一向量(点)xi，其到超平面H的距离为：决策理论与方法-智能决策理论与方法机器学习支持向量机那么，margin的大小可按下式计算：margin=d+d-d+=mindi|i1,2,.,l,yi=+1;d-=mindi|i1,2,.,l,yi=-1 若存

25、在样本点xi使得wxi+b=1，则称此向量xi为支持向量，此时，d+=d-=1/|w|2，margin=2/|w|2。分类模型：寻求最优超平面H，使得margin最大。因此分类问题转为二次凸规划问题：决策理论与方法-智能决策理论与方法机器学习支持向量机线性不可分：可引入核函数将线性不可分问题转换为高维空间的线性可分问题，常见核函数有： d次多项式函数 高斯径向基函数 神经网络核函数决策理论与方法-智能决策理论与方法机器学习遗传算法遗传算法(Genetic Algorithm, GA)是一种借鉴生物界自然选择和自然遗传机制的高度并行、随机、自适应搜索算法，它利用结构化的随机交换技术组合群体中各个

26、结构中最好的生存因素，形成最佳代码串并使之一代一代地进化，最终获得满意的优化结果。其基本构成要素有染色体编码、适应度函数、遗传算子(遗传、交叉、变异)以及相关的运行参数(种群规模：20-100；进化代数：100-500；交叉概率Pc：0.4-0.99；变异概率Pm：0.0001-0.1)决策理论与方法-智能决策理论与方法机器学习遗传算法遗传算法基本步骤(1)确定遗传算法的有关参数：群体规模N，最大代数M，交叉概率Pc，变异概率Pm，停机准则；初始化种群：随机产生N条表示可能方案集的染色体；(2)是否满足停机准则，若是，终止；(3)计算群体中每个个体的适应值；(4)复制：根据适应度函数进行选择生

27、成中间群体；(5)交叉：以概率Pc选择两个个体进行染色体交换形成新的个体，替代老个体插入群体中(6)变异：按概率Pm选择某条染色体的某一位进行改变形成新的个体，替代老个体插入群体中；(7)转到(2)。 决策理论与方法-智能决策理论与方法机器学习遗传算法遗传算法示例：基于GA的连续属性集离散化问题求解问题描述：基于GA的离散化思想：将连续属性离散化的分割点选择问题转化为分割点组合的寻优问题。首先对分割点空间进行遗传编码，以分割点编码构成染色体，用基于粗糙集理论的适应度函数来启发并指导进化，最终得到较优的能充分体现离散化效果的分割点组合代码串，从而找到离散化连续属性集的全部分割点。 3kiki-1

28、21决策理论与方法-智能决策理论与方法机器学习遗传算法遗传编码：用编码形式表示决策变量的初始解。把所有分割点表示成确定长度的二进制串，每个分割点与串中的一部分相联系。具体地，设连续属性集C=c1,c2,.,cm，对于任意ciC选择长度为l(i)的二进制编码表示分割点cij(j=1,2,.,ki-1)，则表示属性ci的所有分割点的串长为l(i)(ki-1)，分割点cij与长度为l(i)的二进制编码之间的值对应关系可由下式确定： 式中m(s)是长度为l(i)的二进制编码中第s位的编码值。si为连续属性ci的起点值，ei为其终点值 决策理论与方法-智能决策理论与方法机器学习遗传算法 对C中的所有属性

29、进行编码形成的二进制串长度为： 因此，连续属性集离散化问题的搜索空间规模为2l。l(i)的选择与样本的规模有关。 例如，若样本规模为200，连续属性集C=c1,c2,c3，k1=k2=4，k3=3。选择l(1)=l(2)=l(3)=5，则l=53+53+52=40，问题的搜索空间规模为2401012 00110 10010 11011 01100 10101 11101 00111 10011表示了分割点集的一条染色体。 决策理论与方法-智能决策理论与方法机器学习遗传算法适应度函数：体现决策目标的优化方向。从粗糙集理论的角度，离散化往往会破坏信息系统中原来的不可分辨关系，即原来两个可分辨的对象

30、可能变为不可分辨，这样等价类包含的对象数量增加，而等价类数量减少，分类能力可能减弱。因此使离散化后系统的分类能力最大是我们的优化目标，因此可用决策属性d对C的依赖度作为适应度函数：决策理论与方法-智能决策理论与方法机器学习遗传算法复制算子。把当前群体中的个体按与适应值成比例的概率复制到新的群体中，复制过程应用赌盘技术选择要被复制的串。复制算子的作用效果将提高群体的平均适应值。设种群数为N，则将赌盘分成N份，第i份的比例按如下值确定：决策理论与方法-智能决策理论与方法机器学习遗传算法s40.31s20.49s10.14s30.06决策理论与方法-智能决策理论与方法机器学习遗传算法交叉算子：按一定

31、的概率从交配池中任选2条染色体进行多点杂交(随机互换两个染色体某些位上的基因)。方法如下：挑选2个染色体串，按概率确定它们是否发生杂交，若未发生杂交，另取2个染色体串，否则，先产生m个随机数r(i)(ciC)，随机数的范围为1到l(i)(ki-1)-1，然后配对的2个串相互对应地交换从 到 的位段。 决策理论与方法-智能决策理论与方法机器学习遗传算法例：设染色体 s1= 00110 10010 11011 01100 10101 11101 00111 10011 s2= 10110 10100 01011 01101 00101 10101 10001 10101按箭头所指进行交叉，得到两条新的染色体。 s1= 00110 01011 11011 01100 01101 11101 10101 10011 s2= 10110 10100 10010 10101 00101 10101 10001 00111决策理论与方法-智能决策理论与方法机器学习遗传算法变异算子：以一个很小的概率随机改