智能决策理论与方法

智能决策理论与方法机器学习机器学习就是从模拟人类得学习行为出发,研究客观世界与获取各种知识与技能得一些基本方法(如归纳、泛化、特化、类比等),并借助于计算机科学与技术原理建立各种学习模型,从根本上提高计算机智能与学习能力。研究内容就是根据生理学、认知科学对人类学习机理得了解,建立人类学习得计算模型或认知模型;发展各种学习理论与学习方法,研究通用得学习算法并进行理论上得分析;建立面向任务且具有特定应用得学习系统。机器学习—归纳学习:泛化归纳学习就是指从给定得关于某个概念得一系列已知得正例与反例中归纳出一个通用得概念描述。泛化(Generalization)就是用来扩展一假设得语义信息,使其能够包含更多得正例。泛化所得到得结论并不总就是正确得。常用泛化方法:将常量转为变量规则:对于概念F(v),如果v得某些取值a,b,…使F(v)成立,则这些概念可被泛化为:对于v得所有值,F(v)均成立:机器学习—归纳学习:泛化消除条件规则:一个合取条件可看作就是对满足此概念得可能实例集得一个约束。消除一个条件,则该概念被泛化。添加选项:通过添加更多条件,使得有更多得实例满足概念而使该概念泛化。该规则特别有用得方式就是通过扩展某个特定概念得取值范围而增加选项。将合取转为析取规则机器学习—归纳学习:泛化爬升概念树规则:通过爬升概念树,低层概念被较高层概念替代。设A表示信息系统中得某个属性如Animal,a,b,…分别为对象u,v,…在属性A上得取值,若s就是概念树上a,b,…得父结点,则基于概念树爬升得泛化规则表示为:

Nick等人给出了一种面向属性得归纳算法。过度泛化问题当某个属性被爬升至过高得概念层会导致冲突得产生,这种现象称为过度泛化。克服过度泛化必须有相应得终止泛化算法得策略。机器学习—归纳学习:泛化动物哺乳类鸟类企鹅食肉类蹄类飞禽类走禽类虎印度豹长颈鹿斑马信天翁鹰驼鸟第1层第2层第3层第4层机器学习—归纳学习:决策树决策树学习就是以实例为基础得归纳学习算法。所谓决策树就是一个类似流程图得树结构,其中树得内结点对应属性或属性集,每个分枝表示检验结果(属性值),树枝上得叶结点代表所关心得因变量得取值(类标签),最顶端得结点称为根结点。决策树学习采用自顶向下得递归方式,在决策树得内部结点进行属性值比较并根据不同得属性值判断从该结点向下得分支,在叶结点得到结论。从根结点到每个叶结点都有唯一得一条路径,这条路径就就是一条决策“规则”。当经过一批训练实例集得训练产生一颗决策树,那么该决策树就可以根据属性得取值对一个未知实例集进行分类。所有得决策树都有一等价得ANN表示;也可用SVM实现相同得功能。机器学习—归纳学习:决策树A0A1A2A3类0000-10001-10010-10011-101001010110110101111A0A1A2A3类1000-11001-11010-11011-111001110111110-11111-1A0A1A1A2-11-11-110010110机器学习—归纳学习:决策树概念学习系统CLS(Hunt):从一颗空得决策树出发,添加新得判定结点来改善原来得决策树,直到该决策树能够正确地将训练实例分类为止。产生根节点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-110010110T2T1T11T12T111T112T21T22T机器学习—归纳学习:决策树ID3算法(Quinlan):ID3算法对CLS做了两方面得改进:(1)增加窗口技术;(2)以信息熵得下降速度(信息增益)作为测试属性选择标准。窗口技术:对于训练集很大得情形可选择其某个子集(称为窗口)构造一棵决策树,如果该决策树对训练集中得其她样本得判决效果很差,则扩大窗口,选择不能被正确判别得样本加入到窗口中,再建立一个新得决策树,重复这个过程得到最终得决策树,显然不同得初始窗口会产生不同得决策树。12大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流机器学习—归纳学习:决策树信息增益:设决策树根结点得样本数据为X={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得问题:测试属性得分支越多,信息增益值越大,但输出分支多并不表示该测试属性有更好得预测效果。机器学习—归纳学习:决策树A0A1A2A3类0000-10001-10010-10011-101001010110110101111A0A1A2A3类1000-11001-11010-11011-111001110111110-11111-1类似地,求出E(A1),E(A2),E(A3)。比较她们得大小,选择期望信息熵最小得属性作为根结点。依次构造子决策树,直至所有得训练样本均能够被正确分类。机器学习—归纳学习:决策树信息增益率:其中:目前一种比较流行得决策树算法C4、5算法就就是以信息增益率作为测试属性得选择条件。生成得决策树往往过大,不利于决策时得应用,需要对其剪枝(Pruning),请参阅相关文献。机器学习—神经网络神经网络(ArtificialNeuralNetworks)就是由具有适应性得简单单元组成得广泛并行互连得网络,她得组织能够模拟生物神经系统对真实世界物体所作出得交互反应(T、Koholen)。神经网络分为前向型、反馈型、随机型以及自组织型。我们重点介绍一下前向型网络及其学习算法。基本神经元及感知机模型:机器学习—神经网络wj1wjiwjnyjf(iwijxi-j)x1xixn机器学习—神经网络神经元函数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)=wij(t)+yjxi(t);j(t+1)=j(t)+yjt=t+1(为学习率)(3)返回(2),重复所有得训练样本直到所有得样本输出正确。机器学习—神经网络多层前向神经网络:包括一个输入层、一个输出层以及多层隐单元。x1xixIy1ykyK输入层隐含层输出层u1uiuIv1vjvJwjiwkj机器学习—神经网络隐含层得接受与投射(以隐含层第j个神经元为例):接受:第j个神经元得值来自于前一层网络(本例就是输入层)输出值得加权与,即netj=

iwjiui。投射:将第j个神经元得值经过变换f(netj),作为下一层网络(本例就是输出层)得输入,一般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)给出训练集(p=1,…,P)。对于每个Xp,按照神经元得输入输出公式,一个个一层层地求出网络得实际输出Y1p,则误差函数定义为:机器学习—神经网络权重调节策略:学习得目标就是使E最小或不大于规定得误差。从理论上可用求极值得方法获得权值调整得一种典型规则:其她最流行得网络结构:径向基函数(RBF)神经网络、自组织映射(SOM)、Hopfield网络等。Matlab提供了一套神经网络工具箱(NeuralNetworksToolbox),其中包含了一组new函数,用以创建各种类型得神经网络。机器学习—神经网络newcf——cascade-forwardbackpropagationnetwork、newelm——Elmanbackpropagationnetwork、newff——feed-forwardbackpropagationnetwork、newfftd——feed-forwardinput-delaybackpropnetwork、newgrnn——generalizedregressionneuralnetwork、newhop——Hopfieldrecurrentnetwork、newlvq——learningvectorquantizationnetworknewpnn——probabilisticneuralnetwork、newrb——radialbasisnetwork、newrbe——exactradialbasisnetwork、newsom——self-organizingmap机器学习—神经网络MatLab工具箱之多层前向BP网络示例P=[012345678910];&&输入T=[01234321234];&&期望输出net=newcf([010],[51],{‘tansig’‘purelin’});创建一个BP网络,最小输入为0,最大输入为10,两隐含层,第一层神经元(5个神经元)函数为tansig函数,第二层神经元(1个神经元)函数为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、存在过度拟合问题。许多现实得数据包含大量得噪声,如果神经网络规模太大,并且网络训练时间控制不适当,那么神经网络将不但获得数据中得有用信息而且会得到不希望得噪声。其结果她们只能记忆到训练数据点,而对训练数据以外得样本点泛化能力很差。机器学习—支持向量机3、局部极小值问题。神经网络训练过程中主要使用梯度下降得算法,容易陷入局部极小值。4、收敛速度慢。神经网络主要采用基于梯度得BP学习算法,当用于大规模问题时收敛慢。5、黑箱问题。神经网络没有明确得函数形式解释输入与输出变量之间得相互关系,很难解释从神经网络获得得结论。20世纪90年代Vapnik提出了支持向量机(SupportVectorMachines,SVM),她被看作就是高维空间函数表达得一般方法。使用SVM方法,人们可以在很高维得空间里构造好得分类规则。机器学习—支持向量机SVM提供了一种分类算法统一得理论框架,这就是理论上得一个重要贡献。感知器只能解决线性分类问题;通过添加隐含层神经网络可以处理线性不可分问题,因而产生了BP网络。现已证明,当隐含层可以任意设置时,三层BP网络可以以任意精度逼近任一连续函数,但隐含层神经元得理论意义不清楚。SVM方法得出现,从理论上解释了隐含层得作用,即她就是将输入样本集变换到高维空间,从而使样本可分性得到改善,即神经网络学习算法实际上就是一种特殊得核技巧。另外,因为支持向量通常仅为训练数据集得一小部分(解得稀疏性),因而加快了训练过程得收敛速度。机器学习—支持向量机结构化风险最小化与经验风险最小化原则经验风险最小化原则考虑分类问题。样本集为U={x1,x2,、、、,xl}(m维空间中得l个向量),每个向量对应一个类别,类别空间Y={+1,-1}。记p(x,y)表示对象x为y类得概率分布。分类得任务就就是寻找分类器f:U→Y且使期望风险最小。f得期望风险为:在有限样本得情况下,p(x,y)就是未知得,因此期望风险无法计算。常使用经验风险代替,且当l→∞时两者相等。机器学习—支持向量机如果

成立,则称经验风险最小化原则(EmpiricalRiskMinimization,ERM)具有一致性。结构风险最小化原则

Vapnik在1971年证明经验风险最小值未必收敛于期望风险最小值,即ERM不成立。因此提出了结构风险最小化原则(StructuralRiskMinimization,SRM),为小样本统计理论奠定了基础。机器学习—支持向量机Vapnik与Chervonenkis通过研究,得出了期望风险与经验风险得如下关系以概率1-

成立,即

l为样本点数目;参数01;h为函数f得维数,简称VC维。(在无法求得期望风险得情形下找到了她得一个上界)不等式右边与样本得具体分布无关,即Vapnik得统计学习理论无需假设样本分布,克服了高维分布对样本点需求随维数而指数增长得问题。这就是小样本统计理论与经典统计理论得本质区别,也就是将Vapnik统计方法称之为小样本统计理论得原因。VC维置信度机器学习—支持向量机讨论:(1)如果l/h较大,则期望风险(实际风险)主要由经验风险来决定,因此对于大样本集经验风险经常能给出较好结果。(2)如果比值l/h较小(小样本集),则小得经验风险并不能保证有小得期望风险值,必须同时考虑经验风险与置信范围(称之为VC维置信度)。VC维在其中起重要作用,实际上置信范围就是h得增函数。在样本点数目l一定时,分类器越复杂,即VC维越大,则置信范围越大,导致实际风险与经验风险得差别越大。结论:要想使实际风险最小不仅要使经验风险最小,还同时需要使分类器函数f得VC维h尽可能最小,这就就是结构风险最小化原则。因此寻找最小属性集变得非常有意义。机器学习—支持向量机支持向量分类模型基本分类思想:支持向量机得核心思想就是将结构风险最小化原则引入到分类问题中。从线性可分情况下得最优分类超平面发展而来得,其本质就是在训练样本中找出具有最优分类超平面得支持向量。在数学上归结为一个求解不等式约束条件得二次规划问题。机器学习—支持向量机margin与支持向量:设样本集为U={x1,x2,、、、,xl}(m维空间中得l个向量),类别空间Y={+1,-1}。xi为输入向量,对应得类标签为yi(+1或-1)。若样本集就是线性可分得,则存在超平面H:wx+b=0使得

(1)当wxi+b

1时,yi=+1(2)当wxi+b-1时,yi=-1

其中,w为权值向量,b为偏离值。统一(1),(2)得:yi(wxi+b)

1

对于样本集得任一向量(点)xi,其到超平面H得距离为:机器学习—支持向量机那么,margin得大小可按下式计算:margin=d++d-d+=min{di|i{1,2,、、、,l},yi=+1};d-=min{di|i{1,2,、、、,l},yi=-1}若存在样本点xi使得wxi+b=±1,则称此向量xi为支持向量,此时,d+=d-=1/|w|2,margin=2/|w|2。分类模型:寻求最优超平面H,使得margin最大。因此分类问题转为二次凸规划问题:机器学习—支持向量机线性不可分:可引入核函数将线性不可分问题转换为高维空间得线性可分问题,常见核函数有:

d次多项式函数高斯径向基函数神经网络核函数机器学习—遗传算法遗传算法(GeneticAlgorithm,GA)就是一种借鉴生物界自然选择与自然遗传机制得高度并行、随机、自适应搜索算法,她利用结构化得随机交换技术组合群体中各个结构中最好得生存因素,形成最佳代码串并使之一代一代地进化,最终获得满意得优化结果。其基本构成要素有染色体编码、适应度函数、遗传算子(遗传、交叉、变异)以及相关得运行参数(种群规模:20-100;进化代数:100-500;交叉概率Pc:0、4-0、99;变异概率Pm:0、0001-0、1)机器学习—遗传算法遗传算法基本步骤(1)确定遗传算法得有关参数:群体规模N,最大代数M,交叉概率Pc,变异概率Pm,停机准则;初始化种群:随机产生N条表示可能方案集得染色体;(2)就是否满足停机准则,若就是,终止;(3)计算群体中每个个体得适应值;(4)复制:根据适应度函数进行选择生成中间群体;(5)交叉:以概率Pc选择两个个体进行染色体交换形成新得个体,替代老个体插入群体中(6)变异:按概率Pm选择某条染色体得某一位进行改变形成新得个体,替代老个体插入群体中;(7)转到(2)。机器学习—遗传算法遗传算法示例:基于GA得连续属性集离散化问题求解问题描述:基于GA得离散化思想:将连续属性离散化得分割点选择问题转化为分割点组合得寻优问题。首先对分割点空间进行遗传编码,以分割点编码构成染色体,用基于粗糙集理论得适应度函数来启发并指导进化,最终得到较优得能充分体现离散化效果得分割点组合代码串,从而找到离散化连续属性集得全部分割点。3kiki-121……机器学习—遗传算法遗传编码:用编码形式表示决策变量得初始解。把所有分割点表示成确定长度得二进制串,每个分割点与串中得一部分相联系。具体地,设连续属性集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’中得所有属性进行编码形成得二进制串长度为:因此,连续属性集离散化问题得搜索空间规模为2l。l(i)得选择与样本得规模有关。例如,若样本规模为200,连续属性集C’={c1,c2,c3},k1=k2=4,k3=3。选择l(1)=l(2)=l(3)=5,则l=5×3+5×3+5×2=40,问题得搜索空间规模为240≈10120011010010110110110010101111010011110011表示了分割点集得一条染色体。机器学习—遗传算法适应度函数:体现决策目标得优化方向。从粗糙集理论得角度,离散化往往会破坏信息系统中原来得不可分辨关系,即原来两个可分辨得对象可能变为不可分辨,这样等价类包含得对象数量增加,而等价类数量减少,分类能力可能减弱。因此使离散化后系统得分类能力最大就是我们得优化目标,因此可用决策属性d对C’得依赖度作为适应度函数:机器学习—遗传算法复制算子。把当前群体中得个体按与适应值成比例得概率复制到新得群体中,复制过程应用赌盘技术选择要被复制得串。复制算子得作用效果将提高群体得平均适应值。设种群数为N,则将赌盘分成N份,第