不确定人工智能中的复杂网络.doc

不确定性人工智能中的复杂网络摘要人工智能是当前科学技发展的一门前沿学科，同时也是一门新思想，新观念，新理论，新技术不断出现的新兴学科以及正在发展的学科。它是在计算机科学，控制论，信息论，神经心理学，哲学，语言学等多种学科研究的基础发展起来的，因此又可把它看作是一门综合性的边缘学科。它的出现及所取得的成就引起了人们的高度重视,并取得了很高的评价。有的人把它与空间技术，原子能技术一起并誉为20世纪的三大科学技术成就。归纳逻辑是人工智能的逻辑基础。伴随人工智能研究的逐步深入，科学哲学、人工智能和归纳逻辑研究相互影响，出现了新的研究方向。以归纳逻辑为基础，多学科相互合作，可以建立新的机器学习系统或归纳学习系统。关键词：小世界模型；聚类系数；归纳逻辑；机器学习；专家系统一、 不确定性人工智能1.1 客观世界的不确定性无论是科学界还是哲学界，都对这个世界是确定的还是不确定的这一问题进行着长期的争论。以牛顿理论为代表的确定性科学,创造了给世界以精确描绘的方法，认为只要知道初始条件,就可以决定未来的一切.不确定的原因是对初始条件的测量误差,或者人类自身认知的局限性和知识的不完备,而并非事物的本来面貌.也有科学家对确定论提出质疑.麦克斯韦认为这个世界的真正逻辑是概率演算,玻尔兹曼则把随机性观点引入物理学,建立了统计力学.对确定论造成更大冲击的是量子力学的出现.海森堡的测不准原理表明,获得严格精确的初值在原理上是不可能的.这意味着,不确定性是客观世界中的一种真实存在,是存在于宇宙间的基本要素,与人类是否无知没有关系.客观世界中的绝大部分现象都是不确定的,所谓确定的、规则的现象,只会在一定的前提和特定的边界条件下发生,只会在局部或者较短的时间内存在.随着不确定性研究的深入,世界的不确定性特征越来越得到学术界的普遍认可,无论是在物理学、数学、生物学等自然科学领域,还是在哲学、经济学、社会学、心理学、认知学等社会科学领域,虽然许多人还在从事着确定性的研究,但已经很难有人对世界的不确定性本质提出实质性的质疑了. 当然,不确定性和确定性并非完全对立,在一定程度上可以相互转化.例如,某一层次的不确定性可能是更高层次上的确定性,种种不确定性中还可能隐藏着某些确定的规律等.越来越多的科学家相信,不确定性是这个世界的魅力所在,只有不确定性本身才是确定的.正是在这样的背景下,混沌科学、复杂性科学和不确定性人工智能才得到了蓬勃发展.1.2 随机性和模糊性是不确定性的最基本内涵 随机性又称偶然性,是指因为事件发生的条件不充分,使得条件与结果之间没有决定性的因果关系,在事件的出现与否上表现出的不确定性质,可以用随机数学作为工具进行研究. 在现实世界中,科学家至今没有解释清楚宇宙是怎样形成的.地球的形成和人类的出现有很大的偶然性.地球至少经历了6次生物大规模灭绝,最著名的是6千万年前的恐龙灭绝.如果没有那次灾变,今天的地球是不是恐龙世界?人类是否还能是今天的模样?不仅仅是地球,包括太阳、行星等整个星系的形成与分布,生命的出现, 物种的演变,都含有许许多多偶然的因素.模糊性又称非明晰性.它的出现是由于概念本身模糊,一个对象是否符合这个概念难以确定,在质上没有明确含义,在量上没有明确界限.这种边界不清的性质,不是由人的主观认识造成的,而是事物的一种客观属性.概念外延的不确定性质,可以用模糊数学作为工具来研究. 天空中变幻莫测的云彩、袅袅升起的炊烟、突然的一场大雾,每个人都熟悉这类现象,但是却无法准确地描述它们的形状.这是因为这类现象没有明确的边界,外观形状不规则、不光滑、极其复杂、随时间变化.边界的模糊性是自然界的一种美。春夏秋冬,季节交替,人们可以说,某月是春天,某月是夏天,但是很难确定不同季节具体是在哪一天转换的,怎么能说今天是春天,而明天就是夏天了呢?同样,白昼黑夜,哪一刻是分明的界限?少年青年,谁会在一夜之间长大?广而言之,所有转变过程在微观上都是一个渐近的连续过程,不存在明确的、突变的界限,这也是一种模糊性.在不确定现象中,混沌、分形和复杂网络是目前人们研究不确定性最感兴趣的3个领域.下面对复杂网络的研究做简要分析。二、 复杂网络研究简介1.1 小世界概念 很多人可能有这样的经历：偶尔碰到一个陌生人，同他聊了一会儿后发现你认识的莫个人居然他也认识，然后你们会一起发出“这个世界真小”的感叹。那么对于地球上任意两个人来说，借助第三者、第四者这样的间接关系来建立起他们两个人之间的联系，平均需要通过几个人呢？20世纪60年代美国哈佛大学的心理学家Milgram的著名的小世界实验（社会调查）给出的推断是：地球上任意两个人之间的平均距离是6.也就是说，平均中间只要通过5个人的传递，一个人就能与地球上任何一个角落的另一个人建立联系。这就是著名的六度分离推断。尽管这个平均数6不一定很准确，但他反映了人与人之间的平均距离与全球人口数量相比是一个非常小的数。1.2 随即图理论20世纪60年代，两位匈牙利科学家Erdos和Renyi建立的随即图理论被公认为实在数学上开创了复杂网络理论的系统性研究。在Erdos和Renyi建立的随即图模型中，任意两个节点之间有一条边相连接的概率都为p。因此，一个含有N个节点的ER随即图中边的总数的期望值为pN(N-1)/2的随机变量。由此可以推得，产生一个有N个节点和M条边的ER随即图的概率为pM(1-p)N(N-1)/2-M。1.3 度与度分布度(degree)是单独节点的属性中简单而又重要的概念节点的度是指与该节点相关联的边的条数，也就是指与该节点连接的其它节点的数目度分布(degree distribution)是指网络中各节点具有的度的分布，一般记作p(惫)p(是)也等于在随机一致的原则下挑选出的节点其度数为k的概率。1.4 平均最短路径网络的平均最短路径可以对网络的连通性进行较好地描述网络中两个节点i和J之间的距离d州定义为连接这两个节点的最短路径上的边数网络的平均最短路径长度L定义为任意两点之间的最短路径的平均值，即L=112N(N-1)，其中N为网络的节点数1.5 聚类系数聚类系数表征的是网络的聚类特性，也就是群落特性一般假设网络中的节点i与ki条边关联，即与另外ki个节点相连显然，在这ki个节点之间最多可能有ki(ki-1)2条边而这ki个节点之间实际存在的边数是Ei那么这ki个节点之间实际存在的边数是Ei与总的可能的边数ki(ki一1)2之比就定义为节点i的聚类系数Ci，即Ci=Eiki(ki-1)/2而对网络中所有节点的聚类系数取平均值，就是整个网络的聚类系数C，即C=1Ni=1NCi其中N为网络的节点数1.6 规则网络在一个全局耦合网络中，任意两个点之间都有边直接相连。因此，在具有相同节点数的所有的网络中，全局耦合网络具有最小的平均路径长度Lgc=1和做大的聚类系数Cgc=1.虽然全局耦合网络模型反映了许多实际网络具有的聚类和小世界性质，但该模型做为实际网络的局限性也很明显：一个有N个点的全局耦合网络有N（N-1）/2条边，然而大多数大型实际网络都是很稀疏的，他们边的数目一般至多是O(N)，而不是O(N2)。一个得到大量研究的稀疏的规则网络模型是最近邻耦合网络，其中每一个节点只和它周围的邻居节点相连。具有周期边界条件的最近邻耦合网络包含N个围城一个环的点，其中每个节点都与他左右各K/2个邻居节点相连，这里K是一个偶数。规则网络的聚类系数C=3(K-2)4（K-1）34。平均路径长度为LncN2K。1.7 WS小世界模型规则的最近邻耦合网络虽然具有高聚类特性，但并不是小世界网络。另一方面，ER随即图虽然具有晓得平均路径长度但却并没有高聚类特性。因此，这两类网络模型都不能再现真是网络的一些重要特征，毕竟大部分实际网络既不是完全规则的，也不是完全随机的。在现实生活中，人们通常认识他们的邻居和同时，但也有可能有少量远在异国他乡的朋友，做为从完全规则网络向完全随机图的过度，Watts和Strogtz于1988年引入了WS小世界网络模型。这个模型从规则图开始，以概率p随机地重新连接网络中的每个变，即将边的一个端点保持不变，而另一个断电取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。在WS小世界网络模型中, p = 0 对应于完全规则网络, p = 1 则对应于完全随机的网络,通过调节p 的值可以控制从完全规则网络到完全随机网络的过渡。由以上算法我们可以看出，WS小世界网络模型从具有高聚类系数但平均路径长度很大的规则最近邻耦合网络开始，逐渐向具有低聚类系数但是平局路径长度却很短的随即图发展，并且在发展的过程中，当p较小的时候，重新连线后得到的网络与原始的规则网络的局部属性差别不大，从而网络中的聚类系数变化也不大，但其平局路径长度却下降很快。这类具有较高的聚类系数的网络就成为小世界网络。三、 基于WS的远距离优先加边小世界模型构造算法2.1 远距离优先加边小世界模型构造算法的引入有以上可知，对图论的研究，经过WS小世界模型，NW小世界模型，已经基本建立起了成熟的小世界模型。小世界模型是在最近邻耦合规则网络的基础上，通过重连或者加边，对本来连接在节点附近的边连接到较远的地方，从而达到降低平均最短路径的目的。虽然在WS小世界网络模型中这一过程中会造成聚类系数的变大，但是如果重连概率p1，平均最短路径长度会几乎呈指数下降很快，而聚类系数变化不恨明显。但是我们对WS小世界模型分析同样可知，如果说选择重连的节点离将要被连接的节点越远，那么最短路径长度变化也就越明显，也就是说，如果说被重新连接的点优先考虑连接离本身节点较远的节点，那么随着重连概率p变大，平均最短路径长度变小的幅度会明显变大。2.2 远距离优先加边小世界模型构造算法下面介绍远距离优先加边小世界模型构造算法：构建一个含有N个点的最近邻耦合规则图：构造一个图，含有N个节点，将这些节点进行编号，然后将每个节点都与他左右相邻的各K/2个节点相连，其中，K是偶数；从编号为1的节点开始，顺时针选择一条连接离此节点最近的邻居节点的边，以概率p1判断这条边是否进行重连；如果这条边需要重连，以概率p2将这条边随机重连到另外一个节点上。跟另外任意一个节点相连的概率p2=MN，其中M为这个节点与被连接节点之间的距离；如果这条边不需要重连，保持这条边不变；顺时针选择下一个节点，重复步骤-；等循环完一圈以后，重新从编号为1的节点开始，顺时针选择一条连接离此节点距离为加一的邻居节点的边，重复以上步骤-；重复步骤一直到并顺时针一条连接此节点距离为K/2为止。四、 远距离优先加边小世界模型构造算法分析小世界模型，主要从两个方面分析他的性能，一个是聚类系数，一个是平均最短路径长度。聚类系数越大，平均最短路径长度越小，越符合小世界性能。4.1 远距离优先加边小世界模型的聚类系数由1.6可知，最近邻耦合规则网络聚类系数C=3(K-2)4（K-1）34，远距离优先加边小世界网络的聚类系数为C=五、结语习的基础理论与系统的研究和开发，这是人工智能科学研究中的一项重大任务9。参考文献：1 阿兰麦席森图灵.计算机能思考吗D.中国知网，1950.2 蔡自兴，徐光佑人工智能及其应用M.北京：清华大学出版社，1996.3 Hilary Putnam.Words and LifeM. Harvard University Press，1994.4 陈波人工智能:当代逻辑发展的动力