人工智能大学ppt课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,2.3 谓词逻辑法,一.谓词逻辑的简要回顾,1.命题与谓词,命题: 表示客观事实的语句,李明是个工人,LIWORKER,或,L,把谓语部分提出,WORKER(LI),WORKER(WANG),引入变量、函数和量词,(,x) (HUMAN(x) -NEED-STUDY(x),(x) TEACHER(brother(x),注:,我们只讨论一阶谓词演算.,2.合适公式 (,well-formed formula),原子(谓词)公式,原子公式:=谓词名+“(”+项,项+“)”,项:=常量|变量|函数,函数:=函数名+“(”+参数,参数+“)”,合适公式,原子谓词公式是合适公式;,若,A,是合适公式, 则,A,也是合适公式;,若,A,和,B,都是合适公式, 则,A,B, AVB, AB,也都是合适公式;,若,A,是合适公式,x,为任何变量, 则,(,x)A,和(,x)A,也是合适公式;,只有按上述规则产生的公式才是合适公式.(有限步),3.用谓词公式表达知识,例:任何整数或者是正数或者是负数.,用,I(x),表示“,x,是整数”,用,P(x),表示“,x,是正数”,用,N(x),表示“,x,是负数”.,(x)(I(x)(P(x),V N,(x),例:用谓词逻辑表达积木世界.,一.基本概念,语义网络是一种用实体及其语义关系来表达知识的有向图.,结点:代表实体,表示各种事物、概念、情况、属性、状态、事件、动作等; 弧:代表语义关系,表示它所连接的两个实体之间的语义联系.在语义网络中,每一个结点和弧都必须带有标识,这些标识用来说明它所代表的实体或语义.,二.以个体为中心的语义网络,1.实例联系,2.4 语义网络法,2.泛化联系,3.聚集联系,4.属性联系,三.以谓词为中心的语义网络,语义网络表示法和谓词逻辑表示法之间有着对应的表示能力.,1.二元谓词,2.,n,元谓词,n,元谓词可转化为,n,个二元谓词的合取,例:“李明给王宏”,3.连接词的表达,例:“李明给王宏而且王宏读了”,4.量词的表达,存在量词的表达,例:“某个大学生读过”,全称量词的表达,采用语义网络分块化技术.例:“所有的大学生都读过”,三.语义网络的推理,1.网络匹配,2.继承推理,3.网络演绎,四.语义网络的特点,1.优点,结构性,联想性,自索引性,自然性,2.缺点,推理规则不十分明了,表达范围有限，一旦结点个数太多，网络结构复杂，推理就难以进行,2.5 框架表示,一.框架是一种结构性的知识表达方法,框架的作用:,表示事物各方面的属性,表示事物之间的类属关系,事物的特征和变异,识别、分析、预测事物及其行为,一.框架的基本结构,例:有下列描述“2000年5月13日,在西藏的阿里地区发生了里氏5.3级地震,伤亡24人,死亡1人,财产损失2000万人民币”把他表示为框架如下:,Frame(,框架名):地震,Slot1(,槽名):时间: 2000年5月13日,Slot2(,槽名):地点: 西藏的阿里地区,Slot3(,槽名):震级: 里氏5.3级,Slot4(,槽名):伤亡人数: 24,Slot5(,槽名):死亡人数: 1,Slot6(,槽名):财产损失: 2000万人民币,框架的一般结构, ., .,., .,. ., ,. .,有两种特殊的侧面:默认值侧面,附加过程侧面,三.框架的推理,1.匹配,是不完全匹配,2.继承推理,3.填槽,四.附加过程侧面的类型,1.,if-needed,2. if-added,3. if-removed,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,23,24,26,27,28,29,30,31,1,2,活结点表,1,1,2,1,1,2,4,2,2,4,8,4,4,8,16,8,8,16,16,8,17,8,8,17,17,8,8,4,9,4,4,9,18,9,9,18,18,9,19,9,19,19,4,4,2,5,2,2,5,10,5,5,10,20,9,9,9,10,10,20,20,10,21,10,10,21,21,10,10,5,11,5,5,11,深度优先,搜索示意图,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,21,22,23,24,26,27,28,29,30,31,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,活结点表,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,宽度优先搜索,演示图,宽度优先,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,2,5,6,7,3,1 2 3,8 4,7 6 5,目标,8,2 3 4,1 8,7 6 5,4,深度优先,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,2 8 3,6 4,1 7 5,2 8 3,1 6,7 5 4,8 3,2 1 4,7 6 5,2 8 3,7 1 4,6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1,2,3,4,5,6,7,8,9,a,b,d,1 2 3,8 4,7 6 5,目标,3.2 启发式搜索,一.基本思想,也叫,LC-,搜索（,按成本最小的原则从活结点表中作选择,）,需要定义一个评价函数,c，,对当前的搜索状态进行评估，找出一个最有希望的节点来扩展.,二.评价函数,f(n) = h(n) + g(n),f(n):,评价函数或叫作成本函数,表示从开始到目前,再到找到一个问题解的所花费的最小成本的估计.,g(n):,表示从开始到目前所花费的成本值或其估计.,h(n):,启发函数,表示从目前到找到一个问题的最小成本的一个估计,.,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,21,22,23,24,26,27,28,29,30,31,1,2,活结点表,1,1,2,2,3,3,2,4,4,5,5,4,8,8,9,9,5,10,10,11,11,10,1,2,4,5,LC-,搜索,示意图,三.举例:九宫重排,8 3,6 4,7 5,初始状态,1 2 3,8 4,7 6 5,目标状态,h(X)：,结点,X,的格局与目标格局相比，位置不符合的将牌数目；,2 8 3,1 6 4,7 5,2 8 3,1 6 4, 7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5 ,2 8 3, 1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4 ,7 6 5, 8 3,2 1 4,7 6 5,2 8 3,7 1 4, 6 5, 2 3,1 8 4,7 6 5,2 3 ,1 8 4,7 6 5,1 2 3, 8 4,7 6 5,1 2 3,8 4,7 6 5,1 2 3,7 8 4, 6 5,0+4,1+5,1+3,1+5,2+3,2+3,2+4,3+3,3+4,3+2,3+4,4+1,5+0,5+2,目标,4.3,人工神经网络的结构,一.人工神经网络的基本要素:,.神经单元,.输入与输出,.输出函数,.激励函数,.连接模式,.传播规则,.学习法则,二.人工神经网络模型,三.人工神经网络各部分特性,1.神经单元,分为输入单元,输出单元和隐单元,每个单元有激活值,可以是连续实数值,也可以是离散整数值,2.输入与输出,从网络外部到网络内部的为输入信号,从网络内部到网络外部的为输出信号,3.输出函数,单元的输出信号与单元激活值的映射关系,可以是等值函数,也可以是阈值函数,4.激励函数,单元的总输入信号与单元激活值的映射关系,可以是等值函数,也可以是阈值函数或可微的连续函数,5.连接模式,网络中所有单元连接强度(权值)构成的矩阵,6.传播规则,某个神经单元所接受的总输入与其它单元对该单元输出之间的关系,最常用的为加权传播法则.,7.学习法则,神经网络的运行包括两个阶段：,1.,训练或学习阶段 向神经网络提供一系列输入输出数据组,通过数值计算方法和参数优化技术,使节点连接的权值不断调整,直到从给定的输入能产生所期望的输出.,2 2.,预测（应用）阶段 以训练好的网络,对未知的样本进行预测,人工神经网络的主要学习算法,.有师学习,.无师学习,.强化学习,4.4 线性模型与感知机,一.线性网络模型特征,1.只有输入单元和输出单元,没有隐单元,2.单元激活值为连续实数值,3.输出函数和激活函数均为等值函数,4.采用加权传播规则,线性网络模型等价于线形方程组(请课后自行分析),多层线性模型可以找到等价的双层线形模型(既隐单元对线 形模型是多余的) 请在作业中证明.,二.线性阈值模型的特征,1.既有输入单元和输出单元,也有隐单元,2.单元激活值为0,1,3.输出函数为等值函数,4.激活函数为阈值函数,5.采用加权传播规则,三.两层线性阈值模型(感知机),这是一个表达或逻辑的模型,它可以用,delta,学习法则学习,感知机无法表达异或逻辑(请在课后作业证明),异或逻辑甚至更复杂的布尔代数只能用多层线形阈值模型表达,但无法找到合适的学习法则.,感知机局限性的分析:,4.5,BP,模型及应用,一.,BP,模型(反向传播网络)的特征,1.既有输入单元和输出单元,也有隐单元,2.单元激活值为连续实数值,3.输出函数为等值函数,4.激活函数为非递减的可微函数,例如,Sigmoid,函数,非对称,Sigmoid,函数为,f(X)=1/(1+e,-x,),对称,Sigmoid,函数,f(X)=(1-e,-x,)/(1+e,-x,).,5.采用加权传播规则,6.,学习算法采用的是梯度下降法，它使期望输出与实际输出 之间的误差平方和最小.,设误差,e,采用下式表示：,其中,Y,i,fW,*,X,i,是对应第,i,个样本,X,i,的实时输出,Y,i,是对应第,i,个样本,X,i,的期望输出.,要使误差,e,最小，可先求取,e,的梯度：,二.,BP,模型的应用范围及局限,. BP,模型广泛应用于模式识别,预测,信号处理等领域,. 经数学证明,它可以表达任意连续函数,. 其缺点是学习时间长,收敛慢,且容易陷入局部最小,原因是,误差曲面复杂.,三.,BP,模型的应用举例,实例：应用,BP,网络预测气候变化对雅砻江流域径流的影响.经分析,在诸多气候因子中,流域内年均气温和年均降水量是影响流域年均径流的两个主要因子,若把气温和降水看作输入,径流看作输出,可用,BP,网络来研究气温和降水变化对流域径流的影响.建立三层,BP,网络(输入层、输出层和一个隐蔽层),以年均气温和年均降水量作为,BP,网络输入层的输入单元,年均径流量为网络输出层的输出单元.用1960到1990年共31年实测的年均气温、降水和径流量系列资料(即31个样本对)对网络进行训练、检验,其中19601982年资料作为训练样本，1983-1990年资料作为检验样本。,BP,网络在雅砻江流域年均流量的拟合与预测精度(%),项 目,BP,网络模型 线性回归模型,备注,平均相对误差 5.99 6.65,拟合,最大相对误差 17.00 18.52,平均相对误差 7.81 9.33 预测,最大相对误差 21.03 25.46,摘自99年第1期,5.1 遗传算法,一.概述,1.遗传算法(,Genetic Algorithms,简称,GA,),思想来源于生物进化过程,它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法(以字符串表示状态空间).,2.,GA,由美国,J.H.Holland,教授于1975年首先提出,并以其提出的图式定理作为理论基础.,11:41 PM,3.,GA,特别适用于传统数学难以解决的复杂的优化问题,如,TSP,问题.,4.,GA,属于邻域搜索的一类,它用概率方式产生新的邻域个体.,5.简单的,GA,存在参数难以控制,容易陷入局部收敛等缺陷,现在的趋势是把它与其他的优化算法结合起来取长补短.,二.遗传算法的基本机理,1.,编码与解码,遗传算法先将搜索结构编码为字符串形式,每个字,符串结构被称为个体(染色体).,相反将字符串形式编码表示变换为原问题结构的,过程叫解码.,编码方法有二进制编码,实数编码,符号编码等.,2. 染色体优劣的度量-,适应度,每个染色体与其适应度的对应关系是适应度函数,它应该有效反映每个染色体与问题的最优解染色,体之间的差距.,3. 遗传操作,选择(复制),根据个体的适应度函数值决定它在下,一代被淘汰还是被遗传.,交叉,将被选择的两个个体作为母体进行部分子,串的交换.,变异,就是改变染色体的某些基因.,三.遗传算法的准备工作,1.确定表示方案;,2.确定适应值的度量;,3.确定控制该算法的参数和变量;,4.确定怎样指定结果及程序运行结束的标准.,四.遗传算法的具体步骤,1.,随机产生一个由固定长度字符串组成的初始群体;,2.对于字符串群体,迭代地执行下述步骤,直到选种标准被满足为止:,计算群体中的每个个体字符串的适应值;,应用下述三种操作(至少前两种)来产生新的群体:,复制:把现有的个体字符串复制到新的群体中.,杂交:通过遗传重组随机选择两个现有的子字符串, 产生新的字符串.,变异:将现有字符串中某一位的字符随机变异.,3.把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果.这一结果可以是问题的解(或近似),4.简单的杂交操作分为三步,从当前群体,B(t),中选择两个结构：,随机选择一个整数,交换,a,和,a,中位置,x,左边的元素, 产生两个新的结构：,5.简单的变异操作过程如下:,每个位置的字符变量都有一个变异概率,各位置互相独立.通过随机过程选择发生变异的位置：,产生一个新结构,其中 是从对应位置 的字符变量的值域中随,机选择的一个取值。可以同样得到,GEN=0,概率地选择遗传操作,随机创建初始群体,是否满足选中标准？,计算群体中每个个体的适应值,i:=0,i:=M,指定结果,结束,GEN:=GEN+1,是,是,否,概率地选择遗传操作,根据适应值选,择一个个体,完成杂交,i:=i+1,i:=i+1,完成繁殖,p(r),繁殖,基于适应值选,择两个个体,把新的两个孩,子加到群体中,p(c),杂交,变异,p(m),把新的孩子加,入到群体中,完成变异,根据适应值选,择一个个体,把变异后个体,加入到群体中,五.,遗传算法与传统优化算法的主要不同,遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码;,遗传算法不是从单个点,而是在群体中从一个点开始搜索;,遗传算法利用适应值信息,无需导数或其它辅助信息;,遗传算法利用概率转移规则,而非确定性规则.,六.遗传算法举例,问题：求,（1）,编码：,此时取均长为5，每个染色体,（2）初始群体生成：群体大小视情况而定，此处设置为4，随机产生四个个体：,编码： 01101，11000，01000，10011,解码： 13 24 8 19,适应度： 169 576 64 361,（3）适应度评价：,4）选择：选择概率,个体： 01101，11000，01000，10011,适应度： 169 576 64 361,选择概率：0.14 0.49 0.06 0.31,选择结果：01101，11000，11000，10011,（5）交叉操作：发生交叉的概率较大,哪两个个体配对交叉是随机的,交叉点位置的选取是随机的（单点交叉）,0110 1 01100 11 000 11011,1100 0 11001 10 011 10000,（6）变异：发生变异的概率很小,（7）新群体的产生：,保留上一代最优个体，一般为10%左右，至少1个,用新个体取代旧个体，随机取代或择优取代。,11000，11011，11001，10011,（8）重复上述操作：,说明：,GA,的终止条件一般人为设置；,GA,只能求次优解或满意解。,分析：按第二代新群体进行遗传操作，若无变异，永远也找不到最优解择优取代有问题。,若随机的将个体01101选入新群体中，有可能找到最优解。,七.遗传算法应用中的一些基本问题,1. 编码,二进制编码,十进制编码适用于函数优化,二进制编码需要解码,染色体较长,变异容易.,十进制编码直观,交换计算量小,但变异复杂.,符号编码适用于组合优化,2. 适应度函数,适应度函数要求非负,同时把待解优化问题表达为,最大化问题,不同染色体的适应度值既要有差距,又,不要差距过大.,为此,需要对原始函数进行某些数学变换.如:非负,变换,线性变换,幂变换,指数变换等.,3. 控制参数和终止条件,(1)需要控制的参数有种群大小,交叉概率和变异,概率.它们的设定尚无理论指导,根据具体问题,和实验确定.变异概率的选择尤为困难.,(2)简单的,GA,不能收敛到全局最优解,通过改进才,行,但搜索时间可能很长.,(3)没有严格的数学方法判定算法的终止.大多数,采用启发式方法.,八.简单遗传算法的改进,1.改进选择方法 例如:择优选择法,确定选择法等,2.,增加遗传操作 例如:多点交叉,部分匹配交叉,基,因重组等,3.单亲遗传 取消交叉操作,4.混合遗传算法,5.2 进化策略,一.进化策略的算法模型,进化策略模仿自然进化原理作为一种求解参数优化问题的,方法.最简单的实现方法如下:,定义的问题是寻找,n,维的实数向量,x,它使函数,(2),双亲向量的初始群体从每维可行范围内随机选择.,(3) 子孙向量的创建是从每个双亲向量加上零均方差高斯随机变量.,(4) 根据最小误差选择向量为下一代新的双亲.,(5) 向量的标准偏差保持不变,或者没有可用的计算方法,那么处理结束.,二.进化策略的具体步骤:,1.产生出初始群体, 它由关于问题(计算机程序)的函数随机组合而成。,2.迭代完成下述子步骤，直至满足选种标准为止:,执行群体中的每个程序，根据它解决问题的能力，给它指定一个适应值,应用变异等操作创造新的计算机程序群体。基于适应值根据概率从群体中选出一个计算机程序个体，然后用合适的操作作用于该计算机程序个体。 把现有的计算机程序复制到新的群体中。通过遗传随机重组两个现有的程序, 创造出新的计算机程序个体。,3.,在后代中适应值最高的计算机程序个体被指定为进化程序设计的结果。这一结果可能是问题的解或近似解。,