第04讲-智能决策理论与方法-2解析课件

决策理论与方法决策理论与方法(4)智能决策理论与方法智能决策理论与方法(2)合肥工业大学管理学院合肥工业大学管理学院合肥工业大学管理学院合肥工业大学管理学院Sunday,June 16,2024Sunday,June 16,2024决策理论与方法(4)智能决智能决策理论与方法智能决策理论与方法1 1、智能决策理论的形成背景、智能决策理论的形成背景、智能决策理论的形成背景、智能决策理论的形成背景2 2、知识发现、知识发现、知识发现、知识发现3 3、机器学习、机器学习、机器学习、机器学习4 4、不确定性理论、不确定性理论、不确定性理论、不确定性理论决策理论与方法-智能决策理论与方法智能决策理论与方法1、智能决策理论的形成背景决策理论与方法-2机器学习机器学习vv机器学习机器学习机器学习机器学习是从模拟人类的学习行为出发，研究客观是从模拟人类的学习行为出发，研究客观是从模拟人类的学习行为出发，研究客观是从模拟人类的学习行为出发，研究客观世界和获取各种知识与技能的一些基本方法（如归世界和获取各种知识与技能的一些基本方法（如归世界和获取各种知识与技能的一些基本方法（如归世界和获取各种知识与技能的一些基本方法（如归纳、泛化、特化、类比等），并借助于计算机科学纳、泛化、特化、类比等），并借助于计算机科学纳、泛化、特化、类比等），并借助于计算机科学纳、泛化、特化、类比等），并借助于计算机科学与技术原理建立各种学习模型，从根本上提高计算与技术原理建立各种学习模型，从根本上提高计算与技术原理建立各种学习模型，从根本上提高计算与技术原理建立各种学习模型，从根本上提高计算机智能和学习能力。机智能和学习能力。机智能和学习能力。机智能和学习能力。研究内容研究内容研究内容研究内容是根据生理学、认知是根据生理学、认知是根据生理学、认知是根据生理学、认知科学对人类学习机理的了解，建立人类学习的计算科学对人类学习机理的了解，建立人类学习的计算科学对人类学习机理的了解，建立人类学习的计算科学对人类学习机理的了解，建立人类学习的计算模型或认知模型；发展各种学习理论和学习方法，模型或认知模型；发展各种学习理论和学习方法，模型或认知模型；发展各种学习理论和学习方法，模型或认知模型；发展各种学习理论和学习方法，研究通用的学习算法并进行理论上的分析；建立面研究通用的学习算法并进行理论上的分析；建立面研究通用的学习算法并进行理论上的分析；建立面研究通用的学习算法并进行理论上的分析；建立面向任务且具有特定应用的学习系统。向任务且具有特定应用的学习系统。向任务且具有特定应用的学习系统。向任务且具有特定应用的学习系统。决策理论与方法-智能决策理论与方法机器学习机器学习是从模拟人类的学习行为出发，研究客观世界和获3机器学习机器学习归纳学习：泛化归纳学习：泛化vv归纳学习归纳学习归纳学习归纳学习是指从给定的关于某个概念的一系列已知是指从给定的关于某个概念的一系列已知是指从给定的关于某个概念的一系列已知是指从给定的关于某个概念的一系列已知的正例和反例中归纳出一个通用的概念描述。的正例和反例中归纳出一个通用的概念描述。的正例和反例中归纳出一个通用的概念描述。的正例和反例中归纳出一个通用的概念描述。vv泛化泛化泛化泛化(Generalization)(Generalization)是用来扩展一假设的语义信是用来扩展一假设的语义信是用来扩展一假设的语义信是用来扩展一假设的语义信息，使其能够包含更多的正例。泛化所得到的结论息，使其能够包含更多的正例。泛化所得到的结论息，使其能够包含更多的正例。泛化所得到的结论息，使其能够包含更多的正例。泛化所得到的结论并不总是正确的。并不总是正确的。并不总是正确的。并不总是正确的。vv常用泛化方法常用泛化方法常用泛化方法常用泛化方法：将常量转为变量规则将常量转为变量规则将常量转为变量规则将常量转为变量规则：对于概念：对于概念：对于概念：对于概念F F(v v)，如果，如果，如果，如果v v的某些取值的某些取值的某些取值的某些取值a a,b b,使使使使F F(v v)成立，则这些概念可被泛化为：对于成立，则这些概念可被泛化为：对于成立，则这些概念可被泛化为：对于成立，则这些概念可被泛化为：对于v v的所有的所有的所有的所有值，值，值，值，F F(v v)均成立：均成立：均成立：均成立：决策理论与方法-智能决策理论与方法机器学习归纳学习：泛化归纳学习是指从给定的关于某个概念的一4机器学习机器学习归纳学习：泛化归纳学习：泛化消除条件规则消除条件规则消除条件规则消除条件规则：一个合取条件可看作是对满足此概念的：一个合取条件可看作是对满足此概念的：一个合取条件可看作是对满足此概念的：一个合取条件可看作是对满足此概念的可能实例集的一个约束。消除一个条件，则该概念被泛可能实例集的一个约束。消除一个条件，则该概念被泛可能实例集的一个约束。消除一个条件，则该概念被泛可能实例集的一个约束。消除一个条件，则该概念被泛化。化。化。化。添加选项添加选项添加选项添加选项：通过添加更多条件，使得有更多的实例满足：通过添加更多条件，使得有更多的实例满足：通过添加更多条件，使得有更多的实例满足：通过添加更多条件，使得有更多的实例满足概念而使该概念泛化。该规则特别有用的方式是通过扩概念而使该概念泛化。该规则特别有用的方式是通过扩概念而使该概念泛化。该规则特别有用的方式是通过扩概念而使该概念泛化。该规则特别有用的方式是通过扩展某个特定概念的取值范围而增加选项。展某个特定概念的取值范围而增加选项。展某个特定概念的取值范围而增加选项。展某个特定概念的取值范围而增加选项。将合取转为析取规则将合取转为析取规则将合取转为析取规则将合取转为析取规则决策理论与方法-智能决策理论与方法机器学习归纳学习：泛化消除条件规则：一个合取条件可看作是对5机器学习机器学习归纳学习：泛化归纳学习：泛化爬升概念树规则爬升概念树规则爬升概念树规则爬升概念树规则：通过爬升概念树，低层概念被较高层：通过爬升概念树，低层概念被较高层：通过爬升概念树，低层概念被较高层：通过爬升概念树，低层概念被较高层概念替代。设概念替代。设概念替代。设概念替代。设A A表示信息系统中的某个属性如表示信息系统中的某个属性如表示信息系统中的某个属性如表示信息系统中的某个属性如AnimalAnimal，a a,b b,分别为对象分别为对象分别为对象分别为对象u u,v v,在属性在属性在属性在属性A A上的取值，若上的取值，若上的取值，若上的取值，若s s是概念树是概念树是概念树是概念树上上上上a a,b b,的父结点，则基于概念树爬升的泛化规则表示为：的父结点，则基于概念树爬升的泛化规则表示为：的父结点，则基于概念树爬升的泛化规则表示为：的父结点，则基于概念树爬升的泛化规则表示为：Nick Nick等人给出了一种面向属性的归纳算法。等人给出了一种面向属性的归纳算法。等人给出了一种面向属性的归纳算法。等人给出了一种面向属性的归纳算法。vv过度泛化问题过度泛化问题过度泛化问题过度泛化问题当某个属性被爬升至过高的概念层会导致冲突的产生，当某个属性被爬升至过高的概念层会导致冲突的产生，当某个属性被爬升至过高的概念层会导致冲突的产生，当某个属性被爬升至过高的概念层会导致冲突的产生，这种现象称为过度泛化。克服过度泛化必须有相应的终这种现象称为过度泛化。克服过度泛化必须有相应的终这种现象称为过度泛化。克服过度泛化必须有相应的终这种现象称为过度泛化。克服过度泛化必须有相应的终止泛化算法的策略。止泛化算法的策略。止泛化算法的策略。止泛化算法的策略。决策理论与方法-智能决策理论与方法机器学习归纳学习：泛化爬升概念树规则：通过爬升概念树，低层6机器学习机器学习归纳学习：泛化归纳学习：泛化动物哺乳类鸟类企鹅食肉类蹄类飞禽类走禽类虎印度豹长颈鹿斑马信天翁鹰驼鸟第1层第2层第3层第4层决策理论与方法-智能决策理论与方法机器学习归纳学习：泛化动物哺乳类鸟类企鹅食肉类蹄类飞禽类走7机器学习机器学习归纳学习：决策树归纳学习：决策树vv决策树学习决策树学习决策树学习决策树学习是以实例为基础的归纳学习算法。是以实例为基础的归纳学习算法。是以实例为基础的归纳学习算法。是以实例为基础的归纳学习算法。所谓决策树是所谓决策树是所谓决策树是所谓决策树是一个类似流程图的树结构，其中树的内结点对应属性或属性一个类似流程图的树结构，其中树的内结点对应属性或属性一个类似流程图的树结构，其中树的内结点对应属性或属性一个类似流程图的树结构，其中树的内结点对应属性或属性集，每个分枝表示检验结果集，每个分枝表示检验结果集，每个分枝表示检验结果集，每个分枝表示检验结果(属性值属性值属性值属性值)，树枝上的叶结点代表，树枝上的叶结点代表，树枝上的叶结点代表，树枝上的叶结点代表所关心的因变量的取值所关心的因变量的取值所关心的因变量的取值所关心的因变量的取值(类标签类标签类标签类标签)，最顶端的结点称为根结点。，最顶端的结点称为根结点。，最顶端的结点称为根结点。，最顶端的结点称为根结点。vv决策树学习采用自顶向下的递归方式，在决策树的内部结点决策树学习采用自顶向下的递归方式，在决策树的内部结点决策树学习采用自顶向下的递归方式，在决策树的内部结点决策树学习采用自顶向下的递归方式，在决策树的内部结点进行属性值比较并根据不同的属性值判断从该结点向下的分进行属性值比较并根据不同的属性值判断从该结点向下的分进行属性值比较并根据不同的属性值判断从该结点向下的分进行属性值比较并根据不同的属性值判断从该结点向下的分支，在叶结点得到结论。支，在叶结点得到结论。支，在叶结点得到结论。支，在叶结点得到结论。从根结点到每个叶结点都有唯一的从根结点到每个叶结点都有唯一的从根结点到每个叶结点都有唯一的从根结点到每个叶结点都有唯一的一条路径，这条路径就是一条决策一条路径，这条路径就是一条决策一条路径，这条路径就是一条决策一条路径，这条路径就是一条决策“规则规则规则规则”。vv当经过一批训练实例集的训练产生一颗决策树，那么该决策当经过一批训练实例集的训练产生一颗决策树，那么该决策当经过一批训练实例集的训练产生一颗决策树，那么该决策当经过一批训练实例集的训练产生一颗决策树，那么该决策树就可以根据属性的取值对一个未知实例集进行分类。树就可以根据属性的取值对一个未知实例集进行分类。树就可以根据属性的取值对一个未知实例集进行分类。树就可以根据属性的取值对一个未知实例集进行分类。所有所有所有所有的决策树都有一等价的的决策树都有一等价的的决策树都有一等价的的决策树都有一等价的ANNANN表示；也可用表示；也可用表示；也可用表示；也可用SVMSVM实现相同的实现相同的实现相同的实现相同的功能。功能。功能。功能。决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树决策树学习是以实例为基础的归纳学习8机器学习机器学习归纳学习：决策树归纳学习：决策树A0A0 A1A1 A2A2 A3A3 类类类类0 00 00 00 0-1-10 00 00 01 1-1-10 00 01 10 0-1-10 00 01 11 1-1-10 01 10 00 01 10 01 10 01 11 10 01 11 10 01 10 01 11 11 11 1A0A0A1A1 A2A2 A3A3 类类类类1 10 00 00 0-1-11 10 00 01 1-1-11 10 01 10 0-1-11 10 01 11 1-1-11 11 10 00 01 11 11 10 01 11 11 11 11 10 0-1-11 11 11 11 1-1-1A0A1A1A2-11-11-110010110决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树A0A1A2A3类0000-1009机器学习机器学习归纳学习：决策树归纳学习：决策树vv概念学习系统概念学习系统概念学习系统概念学习系统CLS(Hunt)CLS(Hunt)：从一颗空的决策树出发，添加新：从一颗空的决策树出发，添加新：从一颗空的决策树出发，添加新：从一颗空的决策树出发，添加新的判定结点来改善原来的决策树，直到该决策树能够正确地的判定结点来改善原来的决策树，直到该决策树能够正确地的判定结点来改善原来的决策树，直到该决策树能够正确地的判定结点来改善原来的决策树，直到该决策树能够正确地将训练实例分类为止。将训练实例分类为止。将训练实例分类为止。将训练实例分类为止。产生根节点产生根节点产生根节点产生根节点T T，T T包含所有的训练样本；包含所有的训练样本；包含所有的训练样本；包含所有的训练样本；如果如果如果如果T T中的所有样本都是正例，则产生一个标有中的所有样本都是正例，则产生一个标有中的所有样本都是正例，则产生一个标有中的所有样本都是正例，则产生一个标有“1”“1”的节点作的节点作的节点作的节点作为为为为T T的子节点，并结束；的子节点，并结束；的子节点，并结束；的子节点，并结束；如果如果如果如果T T中的所有样本都是反例，则产生一个标有中的所有样本都是反例，则产生一个标有中的所有样本都是反例，则产生一个标有中的所有样本都是反例，则产生一个标有“-1”“-1”的节点作的节点作的节点作的节点作为为为为T T的子节点，并结束；的子节点，并结束；的子节点，并结束；的子节点，并结束；选择一个属性选择一个属性选择一个属性选择一个属性A A(如何选如何选如何选如何选?)?)，根据该属性的不同取值，根据该属性的不同取值，根据该属性的不同取值，根据该属性的不同取值v v1 1,v v2 2,v vn n将将将将T T中的训练集划分为中的训练集划分为中的训练集划分为中的训练集划分为n n个子集，并根据这个子集，并根据这个子集，并根据这个子集，并根据这n n个子集建立个子集建立个子集建立个子集建立T T的的的的n n个个个个子节点子节点子节点子节点T T1 1,T,T2 2,T,Tn n，并分别以，并分别以，并分别以，并分别以A=A=v vi i作为从作为从作为从作为从T T到到到到T Ti i的分支符号；的分支符号；的分支符号；的分支符号；以每个子节点以每个子节点以每个子节点以每个子节点T Ti i为根建立新的子树。为根建立新的子树。为根建立新的子树。为根建立新的子树。决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树概念学习系统CLS(Hunt)：从10机器学习机器学习归纳学习：决策树归纳学习：决策树A0A1A1A2-11-11-110010110T2T2T1T1T11T11T12T12T111T111T112T112T21T21T22T22T决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树A0A1A1A2-11-11-1111机器学习机器学习归纳学习：决策树归纳学习：决策树vvID3ID3算法算法算法算法(Quinlan)(Quinlan)：ID3ID3算法对算法对算法对算法对CLSCLS做了两方面的改进：做了两方面的改进：做了两方面的改进：做了两方面的改进：(1)(1)增加窗口技术；增加窗口技术；增加窗口技术；增加窗口技术；(2)(2)以信息熵的下降速度以信息熵的下降速度以信息熵的下降速度以信息熵的下降速度(信息增益信息增益信息增益信息增益)作为测作为测作为测作为测试属性选择标准。试属性选择标准。试属性选择标准。试属性选择标准。窗口技术窗口技术窗口技术窗口技术：对于训练集很大的情形可选择其某个子集：对于训练集很大的情形可选择其某个子集：对于训练集很大的情形可选择其某个子集：对于训练集很大的情形可选择其某个子集(称称称称为窗口为窗口为窗口为窗口)构造一棵决策树，如果该决策树对训练集中的其构造一棵决策树，如果该决策树对训练集中的其构造一棵决策树，如果该决策树对训练集中的其构造一棵决策树，如果该决策树对训练集中的其它样本的判决效果很差，则扩大窗口，选择不能被正确它样本的判决效果很差，则扩大窗口，选择不能被正确它样本的判决效果很差，则扩大窗口，选择不能被正确它样本的判决效果很差，则扩大窗口，选择不能被正确判别的样本加入到窗口中，再建立一个新的决策树，重判别的样本加入到窗口中，再建立一个新的决策树，重判别的样本加入到窗口中，再建立一个新的决策树，重判别的样本加入到窗口中，再建立一个新的决策树，重复这个过程得到最终的决策树，复这个过程得到最终的决策树，复这个过程得到最终的决策树，复这个过程得到最终的决策树，显然不同的初始窗口会显然不同的初始窗口会显然不同的初始窗口会显然不同的初始窗口会产生不同的决策树产生不同的决策树产生不同的决策树产生不同的决策树。决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树ID3算法(Quinlan)：ID12机器学习机器学习归纳学习：决策树归纳学习：决策树信息增益信息增益信息增益信息增益 ：设决策树根结点的样本数据为：设决策树根结点的样本数据为：设决策树根结点的样本数据为：设决策树根结点的样本数据为X X=x x1 1,x,x2 2,x,xn n，称，称，称，称X X的两个训练子集的两个训练子集的两个训练子集的两个训练子集PXPX(对应类标签为对应类标签为对应类标签为对应类标签为1)1)和和和和NX NX(对应类标签为对应类标签为对应类标签为对应类标签为-1)-1)为为为为正例集正例集正例集正例集和和和和反例集反例集反例集反例集，并记正例，并记正例，并记正例，并记正例集和反例集的样本数分别为集和反例集的样本数分别为集和反例集的样本数分别为集和反例集的样本数分别为P P和和和和N N，则样本空间的，则样本空间的，则样本空间的，则样本空间的信息熵信息熵信息熵信息熵为为为为 假设以随机变量假设以随机变量假设以随机变量假设以随机变量A A作为决策树根的测试属性，作为决策树根的测试属性，作为决策树根的测试属性，作为决策树根的测试属性，A A具有具有具有具有k k个个个个不同的离散值不同的离散值不同的离散值不同的离散值v v1 1,v v2 2,v vk k，它将，它将，它将，它将X X划分为划分为划分为划分为k k个子集，且假个子集，且假个子集，且假个子集，且假设第设第设第设第j j个子集中包含个子集中包含个子集中包含个子集中包含P Pj j个正例，个正例，个正例，个正例，N Nj j个反例，则第个反例，则第个反例，则第个反例，则第j j个子集的个子集的个子集的个子集的信息熵为信息熵为信息熵为信息熵为I I(P(Pj j,N,Nj j)。决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树信息增益：设决策树根结点的样本数13机器学习机器学习归纳学习：决策树归纳学习：决策树以以以以A A为测试属性的为测试属性的为测试属性的为测试属性的期望信息熵期望信息熵期望信息熵期望信息熵为为为为以以以以A A为根节点的为根节点的为根节点的为根节点的信息增益信息增益信息增益信息增益是：是：是：是：Gain(A)=Gain(A)=I I(P P,N N)-)-E E(A A)vvID3ID3的策略就是的策略就是的策略就是的策略就是选择信息增益最大的属性作为测试属性选择信息增益最大的属性作为测试属性选择信息增益最大的属性作为测试属性选择信息增益最大的属性作为测试属性。vvID3ID3的问题：测试属性的分支越多，信息增益值越大，但输的问题：测试属性的分支越多，信息增益值越大，但输的问题：测试属性的分支越多，信息增益值越大，但输的问题：测试属性的分支越多，信息增益值越大，但输出分支多并不表示该测试属性有更好的预测效果。出分支多并不表示该测试属性有更好的预测效果。出分支多并不表示该测试属性有更好的预测效果。出分支多并不表示该测试属性有更好的预测效果。决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树以A为测试属性的期望信息熵为决策理14机器学习机器学习归纳学习：决策树归纳学习：决策树A0A0 A1A1 A2A2 A3A3 类类类类0 00 00 00 0-1-10 00 00 01 1-1-10 00 01 10 0-1-10 00 01 11 1-1-10 01 10 00 01 10 01 10 01 11 10 01 11 10 01 10 01 11 11 11 1A0A0A1A1 A2A2 A3A3 类类类类1 10 00 00 0-1-11 10 00 01 1-1-11 10 01 10 0-1-11 10 01 11 1-1-11 11 10 00 01 11 11 10 01 11 11 11 11 10 0-1-11 11 11 11 1-1-1类似地，求出类似地，求出E(A1)，E(A2)，E(A3)。比较它们的大小，选择。比较它们的大小，选择期望信息熵最小的属性作为根结点。依次构造子决策树，直至期望信息熵最小的属性作为根结点。依次构造子决策树，直至所有的训练样本均能够被正确分类。所有的训练样本均能够被正确分类。决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树A0A1A2A3类0000-10015机器学习机器学习归纳学习：决策树归纳学习：决策树信息增益率信息增益率信息增益率信息增益率：其中：其中：其中：其中：目前一种比较流行的决策树算法目前一种比较流行的决策树算法目前一种比较流行的决策树算法目前一种比较流行的决策树算法C4.5C4.5算法算法算法算法就是以信息增就是以信息增就是以信息增就是以信息增益率作为测试属性的选择条件。益率作为测试属性的选择条件。益率作为测试属性的选择条件。益率作为测试属性的选择条件。vv生成的决策树往往过大，不利于决策时的应用，需要对其生成的决策树往往过大，不利于决策时的应用，需要对其生成的决策树往往过大，不利于决策时的应用，需要对其生成的决策树往往过大，不利于决策时的应用，需要对其剪剪剪剪枝枝枝枝(Pruning)(Pruning)，请参阅相关文献。，请参阅相关文献。，请参阅相关文献。，请参阅相关文献。决策理论与方法-智能决策理论与方法机器学习归纳学习：决策树信息增益率：决策理论与方法-智能决16机器学习机器学习神经网络神经网络 vv神经网络神经网络神经网络神经网络(Artificial Neural Networks)(Artificial Neural Networks)是由具有是由具有是由具有是由具有适应性的简单单元组成的广泛并行互连的网络，它适应性的简单单元组成的广泛并行互连的网络，它适应性的简单单元组成的广泛并行互连的网络，它适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作的组织能够模拟生物神经系统对真实世界物体所作的组织能够模拟生物神经系统对真实世界物体所作的组织能够模拟生物神经系统对真实世界物体所作出的交互反应出的交互反应出的交互反应出的交互反应(T.KoholenT.Koholen)。vv神经网络分为神经网络分为神经网络分为神经网络分为前向型、反馈型、随机型前向型、反馈型、随机型前向型、反馈型、随机型前向型、反馈型、随机型以及以及以及以及自组织自组织自组织自组织型型型型。我们重点介绍一下前向型网络及其学习算法。我们重点介绍一下前向型网络及其学习算法。我们重点介绍一下前向型网络及其学习算法。我们重点介绍一下前向型网络及其学习算法。决策理论与方法-智能决策理论与方法机器学习神经网络 神经网络(Artificial Neur17vv基本神经元及感知机模型基本神经元及感知机模型基本神经元及感知机模型基本神经元及感知机模型：机器学习机器学习神经网络神经网络wwj1j1wwji jiwwjnjny yj jf f(i iwwij ijx xi i-j j)x x1 1x xi ix xn n决策理论与方法-智能决策理论与方法基本神经元及感知机模型：机器学习神经网络wj1wjiwjn18机器学习机器学习神经网络神经网络神经元函数神经元函数神经元函数神经元函数f f的选择的选择的选择的选择线性函数：线性函数：线性函数：线性函数：f(x)=f(x)=x x带限的线性函数：带限的线性函数：带限的线性函数：带限的线性函数：为最大输出。为最大输出。为最大输出。为最大输出。阈值型函数：阈值型函数：阈值型函数：阈值型函数：sigmoidsigmoid函数：函数：函数：函数：决策理论与方法-智能决策理论与方法机器学习神经网络神经元函数f的选择决策理论与方法-智能决策19机器学习机器学习神经网络神经网络 感知机学习算法感知机学习算法感知机学习算法感知机学习算法：(选取选取选取选取f f为阈值函数为阈值函数为阈值函数为阈值函数，学习权值向量，学习权值向量，学习权值向量，学习权值向量w)w)(1)(1)初始化：将权值向量和阈值赋予随机量，初始化：将权值向量和阈值赋予随机量，初始化：将权值向量和阈值赋予随机量，初始化：将权值向量和阈值赋予随机量，t=0t=0(2)(2)连接权的修正：设训练样本的输入为连接权的修正：设训练样本的输入为连接权的修正：设训练样本的输入为连接权的修正：设训练样本的输入为x x1 1,.,.,x xi i,.,x,.,xn n，期望输出为，期望输出为，期望输出为，期望输出为y yj j，进行如下计算：，进行如下计算：，进行如下计算：，进行如下计算：计算网络输出：计算网络输出：计算网络输出：计算网络输出：y(t)=y(t)=f f(i iw wij ij(t)x(t)xi i(t)-(t)-j j(t)(t)计算期望输出与实际输出的误差：计算期望输出与实际输出的误差：计算期望输出与实际输出的误差：计算期望输出与实际输出的误差：e(t)=ye(t)=yj j-y(t)-y(t)若若若若e=0e=0，则说明当前样本输出正确，不必更新权值，则说明当前样本输出正确，不必更新权值，则说明当前样本输出正确，不必更新权值，则说明当前样本输出正确，不必更新权值，否则更新权值和阈值否则更新权值和阈值否则更新权值和阈值否则更新权值和阈值 w wij ij(t+1)=w(t+1)=wij ij(t)+(t)+y yj jx xi i(t)(t)；j j(t+1)=(t+1)=j j(t)+(t)+y yj j t=t+1(t=t+1(为学习率为学习率为学习率为学习率)(3)(3)返回返回返回返回(2)(2)，重复所有的训练样本直到所有的样本输出，重复所有的训练样本直到所有的样本输出，重复所有的训练样本直到所有的样本输出，重复所有的训练样本直到所有的样本输出正确。正确。正确。正确。决策理论与方法-智能决策理论与方法机器学习神经网络 感知机学习算法：(选取f为阈值函数，学习20机器学习机器学习神经网络神经网络vv多层前向神经网络多层前向神经网络多层前向神经网络多层前向神经网络：包括一个输入层、一个输出层：包括一个输入层、一个输出层：包括一个输入层、一个输出层：包括一个输入层、一个输出层以及多层隐单元。以及多层隐单元。以及多层隐单元。以及多层隐单元。x x1 1x xi ix xI Iy y1 1y yk ky yKK输入层输入层输入层输入层隐含层隐含层隐含层隐含层输出层输出层输出层输出层u u1 1u ui iu uI Iv v1 1v vj jv vJ Jw wji jiw wkjkj决策理论与方法-智能决策理论与方法机器学习神经网络多层前向神经网络：包括一个输入层、一个输出21机器学习机器学习神经网络神经网络vv隐含层的接受与投射隐含层的接受与投射隐含层的接受与投射隐含层的接受与投射(以隐含层第以隐含层第以隐含层第以隐含层第j j个神经元为例个神经元为例个神经元为例个神经元为例)：接受：第接受：第接受：第接受：第j j个神经元的值来自于前一层网络个神经元的值来自于前一层网络个神经元的值来自于前一层网络个神经元的值来自于前一层网络(本例是输入层本例是输入层本例是输入层本例是输入层)输出值的加权和，即输出值的加权和，即输出值的加权和，即输出值的加权和，即netnetj j=i iwwji jiu ui i。投射：将投射：将投射：将投射：将第第第第j j个神经元的值经过变换个神经元的值经过变换个神经元的值经过变换个神经元的值经过变换f(netf(netj j)，作为下一层，作为下一层，作为下一层，作为下一层网络网络网络网络(本例是输出层本例是输出层本例是输出层本例是输出层)的输入，的输入，的输入，的输入，一般一般一般一般f(x)=1/(1+ef(x)=1/(1+e-x-x)。因此。因此。因此。因此可得到可得到可得到可得到y yk k=j jwwkjkjf(netf(netj j)。上述过程一直持续到所有的输出单元得到输出为止，最上述过程一直持续到所有的输出单元得到输出为止，最上述过程一直持续到所有的输出单元得到输出为止，最上述过程一直持续到所有的输出单元得到输出为止，最后一层的输出就是网络的输出。后一层的输出就是网络的输出。后一层的输出就是网络的输出。后一层的输出就是网络的输出。vv因此，神经网络是一个因此，神经网络是一个因此，神经网络是一个因此，神经网络是一个黑匣子黑匣子黑匣子黑匣子。决策理论与方法-智能决策理论与方法机器学习神经网络隐含层的接受与投射(以隐含层第j个神经元为22机器学习机器学习神经网络神经网络vvBPBP算法算法算法算法：BPBP算法的核心是算法的核心是算法的核心是算法的核心是确定确定确定确定WW的调节规则的调节规则的调节规则的调节规则(学习规则学习规则学习规则学习规则)，使实际的输出使实际的输出使实际的输出使实际的输出Y Y1 1(t)(t)尽可能接近期望的输出尽可能接近期望的输出尽可能接近期望的输出尽可能接近期望的输出Y(t)Y(t)。误差函数误差函数误差函数误差函数：对于每种输入模式特征矢量：对于每种输入模式特征矢量：对于每种输入模式特征矢量：对于每种输入模式特征矢量(x(x1 1,x,x2 2,x,xI I),),都都都都有对应的输出矢量有对应的输出矢量有对应的输出矢量有对应的输出矢量(y(y1 1,y,y2 2,y,yK K)作为训练网络的输出参作为训练网络的输出参作为训练网络的输出参作为训练网络的输出参考基准。如果用符号考基准。如果用符号考基准。如果用符号考基准。如果用符号X Xp p表示第表示第表示第表示第p p个输入模式特征矢量，用个输入模式特征矢量，用个输入模式特征矢量，用个输入模式特征矢量，用符号符号符号符号Y Yp p表示对应的第表示对应的第表示对应的第表示对应的第p p个输出基准矢量。在训练时，同时个输出基准矢量。在训练时，同时个输出基准矢量。在训练时，同时个输出基准矢量。在训练时，同时按输入输出矢量对按输入输出矢量对按输入输出矢量对按输入输出矢量对(X(Xp p,Y,Yp p)给出训练集给出训练集给出训练集给出训练集(p=1,P)(p=1,P)。对于。对于。对于。对于每个每个每个每个X Xp p，按照神经元的输入输出公式，一个个一层层地，按照神经元的输入输出公式，一个个一层层地，按照神经元的输入输出公式，一个个一层层地，按照神经元的输入输出公式，一个个一层层地求出网络的实际输出求出网络的实际输出求出网络的实际输出求出网络的实际输出Y Y1 1p p，则误差函数定义为：，则误差函数定义为：，则误差函数定义为：，则误差函数定义为：决策理论与方法-智能决策理论与方法机器学习神经网络BP算法：BP算法的核心是确定W的调节规则23机器学习机器学习神经网络神经网络权重调节策略权重调节策略权重调节策略权重调节策略：学习的目标是使学习的目标是使学习的目标是使学习的目标是使E E最小或不大于规定的误最小或不大于规定的误最小或不大于规定的误最小或不大于规定的误差。从理论上可用求极值的方法获得权值调整的一种典差。从理论上可用求极值的方法获得权值调整的一种典差。从理论上可用求极值的方法获得权值调整的一种典差。从理论上可用求极值的方法获得权值调整的一种典型规则：型规则：型规则：型规则：vv其他最流行的网络结构：径向基函数其他最流行的网络结构：径向基函数其他最流行的网络结构：径向基函数其他最流行的网络结构：径向基函数(RBF)(RBF)神经网络、自组神经网络、自组神经网络、自组神经网络、自组织映射织映射织映射织映射(SOM)(SOM)、HopfieldHopfield网络等。网络等。网络等。网络等。vvMatlabMatlab提供了一套神经网络工具箱提供了一套神经网络工具箱提供了一套神经网络工具箱提供了一套神经网络工具箱(Neural Networks Neural Networks ToolboxToolbox)，其中包含了一组，其中包含了一组，其中包含了一组，其中包含了一组newnew函数，用以创建各种类型的函数，用以创建各种类型的函数，用以创建各种类型的函数，用以创建各种类型的神经网络。神经网络。神经网络。神经网络。决策理论与方法-智能决策理论与方法机器学习神经网络权重调节策略：学习的目标是使E最小或不大于24机器学习机器学习神经网络神经网络vvnewcfcascade-forward backpropagation network.newcfcascade-forward backpropagation network.vvnewelmElman backpropagation network.newelmElman backpropagation network.vvnewfffeed-forward backpropagation network.newfffeed-forward backpropagation network.vvnewfftdfeed-forward input-delay backprop network.newfftdfeed-forward input-delay backprop network.vvnewgrnngeneralized regression neural network.newgrnngeneralized regression neural network.vvnewhopHopfield recurrent network.newhopHopfield recurrent network.vvnewlvqlearning vector quantization networknewlvqlearning vector quantization networkvvnewpnnprobabilistic neural network.newpnnprobabilistic neural network.vvnewrbradial basis network.newrbradial basis network.vvnewrbeexact radial basis network.newrbeexact radial basis network.vvnewsomself-organizing mapnewsomself-organizing map决策理论与方法-智能决策理论与方法机器学习神经网络newcfcascade-forwar25机器学习机器学习神经网络神经网络vvMatLabMatLab工具箱之多层前向工具箱之多层前向工具箱之多层前向工具箱之多层前向BPBP网络示例网络示例网络示例网络示例P=0 1 2 3 4 5 6 7 8 9 10;&P=0 1 2 3 4 5 6 7 8 9 10;&输入输入输入输入T=0 1 2 3 4 3 2 1 2 3 4;&T=0 1 2 3 4 3 2 1 2 3 4;&期望输出期望输出期望输出期望输出net=net=newcfnewcf(0 10,5 1,tansig purelin);0 10,5 1,tansig purelin);创建一个创建一个创建一个创建一个BPBP网络，最小输入为网络，最小输入为网络，最小输入为网络，最小输入为0 0，最大输入为，最大输入为，最大输入为，最大输入为1010，两隐含层，第，两隐含层，第，两隐含层，第，两隐含层，第一层神经元（一层神经元（一层神经元（一层神经元（5 5个神经元）函数为个神经元）函数为个神经元）函数为个神经元）函数为tansigtansig函数，第二层神函数，第二层神函数，第二层神函数，第二层神经元（经元（经元（经元（1 1个神经元）函数为个神经元）函数为个神经元）函数为个神经元）函数为purelinpurelin函数。函数。函数。函数。Y=sim(net,P);&Y=sim(net,P);&实际输出实际输出实际输出实际输出(未学习未学习未学习未学习)plot(P,T,P,Y,o)plot(P,T,P,Y,o)net.trainParam.epochs=50;&net.trainParam.epochs=50;&迭代次数迭代次数迭代次数迭代次数net=train(net,P,T);&net=train(net,P,T);&网络训练网络训练网络训练网络训练Y=sim(net,P);&Y=sim(net,P);&实际输出实际输出实际输出实际输出(已学习已学习已学习已学习)plot(P,T,P,Y,o)plot(P,T,P,Y,o)决策理论与方法-智能决策理论与方法机器学习神经网络MatLab工具箱之多层前向BP网络示例决26机器学习机器学习神经网络神经网络决策理论与方法-智能决策理论与方法机器学习神经网络决策理论与方法-智能决策理论与方法27机器学习机器学习支持向量机支持向量机vv提出的背景提出的背景提出的背景提出的背景(针对神经网络的不足针对神经网络的不足针对神经网络的不足针对神经网络的不足)1.1.大量的控制参数。大量的控制参数。大量的控制参数。大量的控制参数。神经网络的结构、传输函数、损失函神经网络的结构、传输函数、损失函神经网络的结构、传输函数、损失函神经网络的结构、传输函数、损失函数、学习参数、训练算法以及训练代数都需要基于反复数、学习参数、训练算法以及训练代数都需要基于反复数、学习参数、训练算法以及训练代数都需要基于反复数、学习参数、训练算法以及训练代数都需要基于反复试验的方法获得。试验的方法获得。试验的方法获得。试验的方法获得。2.2.存在过度拟合问题存在过度拟合问题存在过度拟合问题存在过度拟合问题。许多现实的数据包含大量的噪声，。许多现实的数据包含大量的噪声，。许多现实的数据包含大量的噪声，。许多现实的数据包含大量的噪声，如果神经网络规模太大，并且网络训练时间控制不适当，如果神经网络规模太大，并且网络训练时间控制不适当，如果神经网络规模太大，并且网络训练时间控制不适当，如果神经网络规模太大，并且网络训练时间控制不适当，那么神经网络将不但获得数据中的有用信息而且会得到那么神经网络将不但获得数据中的有用信息而且会得到那么神经网络将不但获得数据中的有用信息而且会得到那么神经网络将不但获得数据中的有用信息而且会得到不希望的噪声。其结果它们只能记忆到训练数据点，而不希望的噪声。其结果它们只能记忆到训练数据点，而不希望的噪声。其结果它们只能记忆到训练数据点，而不希望的噪声。其结果它们只能记忆到训练数据点，而对训练数据以外的样本点泛化能力很差。对训练数据以外的样本点泛化能力很差。对训练数据以外的样本点泛化能力很差。对训练数据以外的样本点泛化能力很差。决策理论与方法-智能决策理论与方法机器学习支持向量机提出的背景(针对神经网络的不足)决策理论28机器学习机器学习支持向量机支持向量机3.3.局部极小值问题局部极小值问题局部极小值问题局部极小值问题。神经网络训练过程中主要使用梯度下。神经网络训练过程中主要使用梯度下。神经网络训练过程中主要使用梯度下。神经网络训练过程中主要使用梯度下降的算法，容易陷入局部极小值。降的算法，容易陷入局部极小值。降的算法，容易陷入局部极小值。降的算法，容易陷入局部极小值。4.4.收敛速度慢收敛速度慢收敛速度慢收敛速度慢。神经网络主要采用基于梯度的。神经网络主要采用基于梯度的。神经网络主要采用基于梯度的。神经网络主要采用基于梯度的BPBP学习算法，学习算法，学习算法，学习算法，当用于大规模问题时收敛慢。当用于大规模问题时收敛慢。当用于大规模问题时收敛慢。当用于大规模问题时收敛慢。5.5.黑箱问题黑箱问题黑箱问题黑箱问题。神经网络没有明确的函数形式解释输入和输。神经网络没有明确的函数形式解释输入和输。神经网络没有明确的函数形式解释输入和输。神经网络没有明确的函数形式解释输入和输出变量之间的相互关系，很难解释从神经网络获得的结出变量之间的相互关系，很难解释从神经网络获得的结出变量之间的相互关系，很难解释从神经网络获得的结出变量之间的相互关系，很难解释从神经网络获得的结论。论。论。论。vv2020世纪世纪世纪世纪9090年代年代年代年代VapnikVapnik提出了支持向量机提出了支持向量机提出了支持向量机提出了支持向量机(Support Vector(Support Vector Machines,SVM)Machines,SVM)，它被看作是高维空间函数表达的一般方，它被看作是高维空间函数表达的一般方，它被看作是高维空间函数表达的一般方，它被看作是高维空间函数表达的一般方法。使用法。使用法。使用法。使用SVMSVM方法，人们可以在很高维的空间里构造好的分方法，人们可以在很高维的空间里构造好的分方法，人们可以在很高维的空间里构造好的分方法，人们可以在很高维的空间里构造好的分类规则。类规则。类规则。类规则。决策理论与方法-智能决策理论与方法机器学习支持向量机3.局部极小值问题。神经网络训练过程中29机器学习机器学习支持向量机支持向量机vvSVMSVM提供了一种分类算法统一的理论框架，这是理论上的一提供了一种分类算法统一的理论框架，这是理论上的一提供了一种分类算法统一的理论框架，这是理论上的一提供了一种分类算法统一的理论框架，这是理论上的一个重要贡献。感知器只能解决线性分类问题；通过添加隐含个重要贡献。感知器只能解决线性分类问题；通过添加隐含个重要贡献。感知器只能解决线性分类问题；通过添加隐含个重要贡献。感知器只能解决线性分类问题；通过添加隐含层神经网络可以处理线性不可分问题，因而产生了层神经网络可以处理线性不可分问题，因而产生了层神经网络可以处理线性不可分问题，因而产生了层神经网络可以处理线性不可分问题，因而产生了BPBP网络。网络。网络。网络。现已证明，当隐含层可以任意设置时，三层现已证明，当隐含层可以任意设置时，三层现已证明，当隐含层可以任意设置时，三层现已证明，当隐含层可以任意设置时，三层BPBP网络可以以网络可以以网络可以以网络可以以任意精度逼近任一连续函数，但任意精度逼近任一连续函数，但任意精度逼近任一连续函数，但任意精度逼近任一连续函数，但隐含层神经元的理论意义不隐含层神经元的理论意义不隐含层神经元的理论意义不隐含层神经元的理论意义不清楚清楚清楚清楚。vvSVMSVM方法的出现，方法的出现，方法的出现，方法的出现，从理论上解释了隐含层的作用从理论上解释了隐含层的作用从理论上解释了隐含层的作用从理论上解释了隐含层的作用，即它是将，即它是将，即它是将，即它是将输入样本集变换到高维空间，从而使样本可分性得到改善，输入样本集变换到高维空间，从而使样本可分性得到改善，输入样本集变换到高维空间，从而使样本可分性得到改善，输入样本集变换到高维空间，从而使样本可分性得到改善，即神经网络学习算法实际上是一种即神经网络学习算法实际上是一种即神经网络学习算法实际上是一种即神经网络学习算法实际上是一种特殊的核技巧特殊的核技巧特殊的核技巧特殊的核技巧。vv另外，因为另外，因为另外，因为另外，因为支持向量支持向量支持向量支持向量通常仅为训练数据集的一小部分通常仅为训练数据集的一小部分通常仅为训练数据集的一小部分通常仅为训练数据集的一小部分(解的解的解的解的稀疏性稀疏性稀疏性稀疏性)，因而加快了训练过程的收敛速度。，因而加快了训练过程的收敛速度。，因而加快了训练过程的收敛速度。，因而加快了训练过程的收敛速度。决策理论与方法-智能决策理论与方法机器学习支持向量机SVM提供了一种分类算法统一的理论框架，30机器学习机器学习支持向量机支持向量机vv结构化风险最小化与经验风险最小化原则结构化风险最小化与经验风险最小化原则结构化风险最小化与经验风险最小化原则结构化风险最小化与经验风险最小化原则经验风险最小化原则经验风险最小化原则经验风险最小化原则经验风险最小化原则 考虑分类问题。样本集为考虑分类问题。样本集为考虑分类问题。样本集为考虑分类问题。样本集为U=xU=x1 1,x,x2 2,.,x,.,xl l(m(m维空间中的维空间中的维空间中的维空间中的l l个向量个向量个向量个向量)，每个向量对应一个类别，类别空间，每个向量对应一个类别，类别空间，每个向量对应一个类别，类别空间，每个向量对应一个类别，类别空间Y=+1,-1Y=+1,-1。记记记记p(x,y)p(x,y)表示对象表示对象表示对象表示对象x x为为为为y y类的概率分布。类的概率分布。类的概率分布。类的概率分布。分类的任务就是寻分类的任务就是寻分类的任务就是寻分类的任务就是寻找分类器找分类器找分类器找分类器f f：UYUY且使期望风险最小。且使期望风险最小。且使期望风险最小。且使期望风险最小。f f的期望风险为：的期望风险为：的期望风险为：的期望风险为：在有限样本的情况下，在有限样本的情况下，在有限样本的情况下，在有限样本的情况下，p(x,y)p(x,y)是未知的，因此期望风险无是未知的，因此期望风险无是未知的，因此期望风险无是未知的，因此期望风险无法计算。常使用经验风险代替，且当法计算。常使用经验风险代替，且当法计算。常使用经验风险代替，且当法计算。常使用经验风险代替，且当ll时两者相等。时两者相等。时两者相等。时两者相等。决策理论与方法-智能决策理论与方法机器学习支持向量机结构化风险最小化与经验风险最小化原则决策31机器学习机器学习支持向量机支持向量机如果如果如果如果 成立，则称经验风险最小化原则（成立，则称经验风险最小化原则（成立，则称经验风险最小化原则（成立，则称经验风险最小化原则（Empirical Risk Empirical Risk Minimization,ERMMinimization,ERM）具有一致性。）具有一致性。）具有一致性。）具有一致性。结构风险最小化原则结构风险最小化原则结构风险最小化原则结构风险最小化原则 Vapnik Vapnik在在在在19711971年证明经验风险最小值未必收敛于期望风年证明经验风险最小值未必收敛于期望风年证明经验风险最小值未必收敛于期望风年证明经验风险最小值未必收敛于期望风险最小值，即险最小值，即险最小值，即险最小值，即ERMERM不成立。因此提出了不成立。因此提出了不成立。因此提出了不成立。因此提出了结构风险最小化结构风险最小化结构风险最小化结构风险最小化原则原则原则原则(Structural Risk Minimization,SRM)(Structural Risk Minimization,SRM)，为小样本为小样本为小样本为小样本统计理论奠定了基础。统计理论奠定了基础。统计理论奠定了基础。统计理论奠定了基础。决策理论与方法-智能决策理论与方法机器学习支持向量机如果决策理论与方法-智能决策理论与方法32机器学习机器学习支持向量机支持向量机VapnikVapnik和和和和 Chervonenkis Chervonenkis通过研究，得出了期望风险和通过研究，得出了期望风险和通过研究，得出了期望风险和通过研究，得出了期望风险和经验风险的如下关系以概率经验风险的如下关系以概率经验风险的如下关系以概率经验风险的如下关系以概率1-1-成立，即成立，即成立，即成立，即 l l为样本点数目；参数为样本点数目；参数为样本点数目；参数为样本点数目；参数0 01 1；h h为函数为函数为函数为函数f f的维数，简称的维数，简称的维数，简称的维数，简称VCVC维。维。维。维。(在无法求得期望风险的情形下找到了它的一个上在无法求得期望风险的情形下找到了它的一个上在无法求得期望风险的情形下找