第1卷第2期 智能系统学报 Vol.1 N2 2 2006年10月 CAAI Transactions on Intelligent Systems 0ct.2006 基于多Agent的模式识别框 程显毅陈小波 (江苏大学计算机科学与通信工程学院江苏镇江212013) 摘要:传统的模式识别方法主要存在两个方面的不足:集中式控制;依赖于特征抽取和选择的质量,本文的研究是 在分析自上而下模式识别方法和自下而上模式识别方法的特性和优缺点基础上,基于多ag©nt理论和技术,提出了 将两种不同类型的方法集成的模式识别框架APRF(A gent~-Based Pattern Recognition Frame):先用自下而上定量计 算方法对模式建模,使其有利于分类:再用自上而下的定性分析方法对模式涌现.目的是让计算机模式识别更符合 人的认知过程,APRF的基本思想是:模式识别=模式建模+模式涌现 关键词:模式识别:Agent:APRF:模式记忆:模式涌现 中图分类号:TP391.4文献标识码:A文章编号:16734785(2006)02-0089-05 Frame of pattern recognition based on multi Agent CHEN G Xian-yi ,CHEN Xiao-bo (Computer Science Communication Engineering Institute Jiangsu University,Zhenjiang 212013,China) Abstract:Traditional pattern recognition methods have two disadvantages in general:centralized control and depending on the quality of the features extracted or selected.APRF(Agent-Based Pattern Recognition Frame)is proposed based on multi-agent theories and techniques after the analysis of the characteristics, advantages and disadvantages of the top-down and bottom-up methods.The pattern is modeled by quanti- tatively computing from bottom to top so as to ease the classification.Then the pattern is emerged by the qualitatively analytical approach from top to bottom.APRF is aimed to make the pattern recognition by computer more accordant with the cognition of human.The core of APRF is:Pattern Recognition=Pat- tern Modeling Pattern Emergence. Keywords:pattern recognition;Agent;APRF;pattern memory;pattern emerge 模式识别是人类的一项基本智能,在日常生活 多姿势的识别(表情识别)、依赖于环境或其他对象 中,人们经常进行“模式识别”.在短短的50年里,模 的模式识别(远程协同诊断、文本识别)等都客观上 式识别方法和技术层出不穷,如统计模式识别、句法 要求研究分布模式识别方法,而日前在这方面的研 模式识别山、神经网络模式识别、协同模式识别!、 究成果不多.迫切需要一种理论、方法和技术,解决 仿生模式识别)、子空间模式识别、模糊模式识别和 只有通过协作才能高效完成的模式识别任务。 多分类器组合等,它们已成功地应用于工业、农 文中研究的第2个动机是给出基于知识的模式 业、国防、科研、医疗卫生、气象、天文等各种领域, 表示.模式的表示模型决定着模式识别的效率,目 但在实际应用中,经常遇到同一模式多角度的 前,对模式表示的研究结果很少,大多采用特征向量 识别(人脸识别、遥感图像识别)、同一模式的多模式 或灰度矩阵的表示模型,只有在句法模式识别中,才 识别(医学图像需要处理同一器官的CT图像、MR 把模式表示为基元树或基元图模型,这实际上是把 图像、SPECT图像、PET图像的处理)、同一模式的 模式作为数据看待,这就决定了传统的模式识别方 法只能是一种定量计算的过程.其实,把图像看作知 收稿日期:200602-23. 识更恰当.因为,图像所包含的信息是立体的、多层 基金项目:国家自然科学基金资助项目(60473039);江苏省研究生创 次的、有含义的.对于知识已有逻辑、语义网、产生式 新基金资助项目(xm0435);江苏省重点科技攻关资助项 日(BE2004093). 系统框架、原语过程、面向对象和动态Peti网等 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 1 卷第 2 期 智 能 系 统 学 报 Vol. 1 №. 2 2006 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2006 基于多 Agent 的模式识别框 程显毅 ,陈小波 (江苏大学 计算机科学与通信工程学院 ,江苏 镇江 212013) 摘 要 :传统的模式识别方法主要存在两个方面的不足 :集中式控制 ;依赖于特征抽取和选择的质量. 本文的研究是 在分析自上而下模式识别方法和自下而上模式识别方法的特性和优缺点基础上 ,基于多 agent 理论和技术 ,提出了 将两种不同类型的方法集成的模式识别框架 APRF(Agent2Based Pattern Recognition Frame) :先用自下而上定量计 算方法对模式建模 ,使其有利于分类 ;再用自上而下的定性分析方法对模式涌现. 目的是让计算机模式识别更符合 人的认知过程 ,APRF 的基本思想是 :模式识别 = 模式建模 + 模式涌现. 关键词 :模式识别 ; Agent ; APRF ; 模式记忆 ; 模式涌现 中图分类号 : TP391. 4 文献标识码 :A 文章编号 :167324785 (2006) 0220089205 Frame of pattern recognition based on multi2Agent CH EN G Xian2yi ,CHEN Xiao2bo (Computer Science & Communication Engineering Institute , Jiangsu University , Zhenjiang 212013 ,China) Abstract : Traditional pattern recognition met hods have two disadvantages in general : centralized control and depending on t he quality of t he features extracted or selected. A PRF(Agent2Based Pattern Recognition Frame) is proposed based on multi2agent t heories and techniques after the analysis of t he characteristics , advantages and disadvantages of t he top2down and bottom2up met hods. The pattern is modeled by quanti2 tatively comp uting from bottom to top so as to ease t he classification. Then t he pattern is emerged by t he qualitatively analytical approach from top to bottom. A PRF is aimed to make t he pattern recognition by comp uter more accordant with t he cognition of human. The core of A PRF is : Pattern Recognition = Pat2 tern Modeling + Pattern Emergence. Keywords :pattern recognition ; Agent ; A PRF; pattern memory ; pattern emerge 收稿日期 :2006202223. 基金项目 :国家自然科学基金资助项目(60473039) ;江苏省研究生创 新基金资助项目( xm04235) ;江苏省重点科技攻关资助项 目(BE2004093) . 模式识别是人类的一项基本智能 ,在日常生活 中 ,人们经常进行“模式识别”. 在短短的 50 年里 ,模 式识别方法和技术层出不穷 ,如统计模式识别、句法 模式识别[1 ] 、神经网络模式识别、协同模式识别[2 ] 、 仿生模式识别[3 ] 、子空间模式识别、模糊模式识别和 多分类器组合等[ 4 ] ,它们已成功地应用于工业、农 业、国防、科研、医疗卫生、气象、天文等各种领域. 但在实际应用中 ,经常遇到同一模式多角度的 识别(人脸识别、遥感图像识别) 、同一模式的多模式 识别(医学图像需要处理同一器官的 CT 图像、MR 图像、SPECT 图像、PET 图像的处理) 、同一模式的 多姿势的识别(表情识别) 、依赖于环境或其他对象 的模式识别(远程协同诊断、文本识别) 等都客观上 要求研究分布模式识别方法 ,而目前在这方面的研 究成果不多. 迫切需要一种理论、方法和技术 ,解决 只有通过协作才能高效完成的模式识别任务. 文中研究的第 2 个动机是给出基于知识的模式 表示. 模式的表示模型决定着模式识别的效率 ,目 前 ,对模式表示的研究结果很少 ,大多采用特征向量 或灰度矩阵的表示模型 ,只有在句法模式识别中 ,才 把模式表示为基元树或基元图模型 ,这实际上是把 模式作为数据看待 ,这就决定了传统的模式识别方 法只能是一种定量计算的过程. 其实 ,把图像看作知 识更恰当. 因为 ,图像所包含的信息是立体的、多层 次的、有含义的. 对于知识已有逻辑、语义网、产生式 系统、框架、原语、过程、面向对象和动态 Petri 网等
·90· 智能系统学报 第1卷 表示方法 创建 本文基于多Agent理论,提出的模式识别框架 2)借助分布式分类器,将模式识别划分成若干 APRF基本思想是统一微观层次的模式建模和宏观 子任务后分配给各个分类器,于是,可以从这种并行 层次的模式涌现,从整体的演化角度认识模式 性中获得真正的加速处理; 3)最适合问题的某部分的方法可能对问题的其 1传统模式识别的局限性 他部分不是最好的,虽然某个Agent提供一个错误 模式识别在给人们带来希望的同时也应看到, 答案或线索,但其他Agent却可能也提供正确答 由于问题本身的多样性和复杂性,现有的理论和方 案 法离实际要求还有相当距离,一些根本性的问题还 Agent计算是对专家系统、神经网络、面向对 有待进一步深入研究1 象、可视化计算、网络计算等技术的集成和发展.每 1)特征抽取问题.在理论上缺乏一种统一的能 个Agent有自己的控制线程,能够主动感知其他A- 适合各种问题的特征抽取手段,因而分类器的设计 gent的意图. 存在一定的盲目性 3 2)结构识别与统计模式识别的结合问题.有一 基于Agent的模式识别框架 些学者曾提出把统计法和结构法结合起来,但多数 APRF框架由一系列Agent组成,每个Agent 停留在分工组合上.尚没有一种把两者有机的融合 担任不同的角色,如图1所示 在一起的方法,没有有效的基元协作的机制.所以如 Pattern 何发挥结构识别的作用,研究的成果不多 Interecption 3)基于连续逻辑的模糊模式识别是用隶属度作 为模式之间相似度的度量,虽然能反映模式整体与 决策Agen 主要特性,有相当程度的抗干扰和畸变能力,但准确 合理的隶属度函数往往难以建立,所以,限制了它的 应用 H标Agent 4)基于神经网络的模式识别在许多场合得到了 知识库 知识 应用,但是需要较多的训练样本及训练时间,并且没 Agent 特征Agent 有充分的利用模式的先验知识 2 Agent理论在模式识别中的应用 观察Agent 为了设计有效的模式识别系统,传统的做法是 首先进行最优的特征提取,然后设计最优的分类器, Pattern 实际上,要达到这两个“最优”是非常困难的.近年 来,随着分布式计算和全球互联网技术的快速发 图1APRF框架 展,人工智能研究开始将研究重点转向Agent(智能 Fig.1 Frame of APRF 体)计算,研究人员试图通过Agent的研究,找到群 观察Agent的任务是最简单的,它们只记录外 体涌现机制的实现方法,克服单一体系的局限性.这 来信号的原始状态和模式的变化,相当于观察器.然 样既能降低对单分类器性能最优的苛刻要求,又能 后,特征Agent在模式上寻找某些特征:看看某种 较容易地得到高性能的识别系统,其中的道理也非 线条特征、角度特征…是否出现,目标Agent注 常简单,不同的Agent往往从不同的侧面认识输入 视着概念Agent的反应.每个目标Agent负责识别 模式,如果能让不同的Agent进行有效地协作,则 某种特定的模式.例如,一个目标Agent识别字母 对输入模式能得到更全面的认识,从而得到更高的 “A”,而另一个目标Agent识别字母“B”,如此类推, 识别性能.所以,APRF利用多Agent技术,通过A- 负责“A"的目标Agent努力寻找于“A”这个特定模 gent协作实现输入模式向参考模式的演化 式有关的特征Agent.目标Agent一旦找到一个合 在模式识别中,分布式的知识表示和推理是有 适的特征Agent,其能量就大增,找到的越多,能量 益的,主要基于如下原因61 就越大.最后决策Agent注意目标Agent的能量变 1)与集中式分类器比较,分布式分类器更容易 化,它把能量最大的Agent选出,作为模式的解释, 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
表示方法. 本文基于多 Agent 理论 ,提出的模式识别框架 APRF 基本思想是统一微观层次的模式建模和宏观 层次的模式涌现 ,从整体的演化角度认识模式. 1 传统模式识别的局限性 模式识别在给人们带来希望的同时也应看到 , 由于问题本身的多样性和复杂性 ,现有的理论和方 法离实际要求还有相当距离 ,一些根本性的问题还 有待进一步深入研究[5 ] . 1) 特征抽取问题. 在理论上缺乏一种统一的能 适合各种问题的特征抽取手段 ,因而分类器的设计 存在一定的盲目性. 2) 结构识别与统计模式识别的结合问题. 有一 些学者曾提出把统计法和结构法结合起来 ,但多数 停留在分工组合上 ,尚没有一种把两者有机的融合 在一起的方法 ,没有有效的基元协作的机制. 所以如 何发挥结构识别的作用 ,研究的成果不多. 3) 基于连续逻辑的模糊模式识别是用隶属度作 为模式之间相似度的度量 ,虽然能反映模式整体与 主要特性 ,有相当程度的抗干扰和畸变能力 ,但准确 合理的隶属度函数往往难以建立 ,所以 ,限制了它的 应用. 4) 基于神经网络的模式识别在许多场合得到了 应用 ,但是需要较多的训练样本及训练时间 ,并且没 有充分的利用模式的先验知识. 2 Agent 理论在模式识别中的应用 为了设计有效的模式识别系统 ,传统的做法是 首先进行最优的特征提取 ,然后设计最优的分类器 , 实际上 ,要达到这两个“最优”是非常困难的. 近年 来 , 随着分布式计算和全球互联网技术的快速发 展 ,人工智能研究开始将研究重点转向 Agent (智能 体) 计算 ,研究人员试图通过 Agent 的研究 ,找到群 体涌现机制的实现方法 ,克服单一体系的局限性. 这 样既能降低对单分类器性能最优的苛刻要求 ,又能 较容易地得到高性能的识别系统. 其中的道理也非 常简单 ,不同的 Agent 往往从不同的侧面认识输入 模式 ,如果能让不同的 Agent 进行有效地协作 ,则 对输入模式能得到更全面的认识 ,从而得到更高的 识别性能. 所以 ,A PRF 利用多 Agent 技术 ,通过 A2 gent 协作实现输入模式向参考模式的演化. 在模式识别中 ,分布式的知识表示和推理是有 益的 ,主要基于如下原因[6 ] : 1) 与集中式分类器比较 ,分布式分类器更容易 创建 ; 2) 借助分布式分类器 ,将模式识别划分成若干 子任务后分配给各个分类器 ,于是 ,可以从这种并行 性中获得真正的加速处理 ; 3) 最适合问题的某部分的方法可能对问题的其 他部分不是最好的 ,虽然某个 Agent 提供一个错误 答案或线索 ,但其他 Agent 却可能也提供正确答 案. Agent 计算是对专家系统、神经网络、面向对 象、可视化计算、网络计算等技术的集成和发展. 每 个 Agent 有自己的控制线程 ,能够主动感知其他 A2 gent 的意图. 3 基于 Agent 的模式识别框架 APRF 框架由一系列 Agent 组成 ,每个 Agent 担任不同的角色 ,如图 1 所示. 图 1 APRF 框架 Fig. 1 Frame of APRF 观察 Agent 的任务是最简单的 ,它们只记录外 来信号的原始状态和模式的变化 ,相当于观察器. 然 后 ,特征 Agent 在模式上寻找某些特征 :看看某种 线条特征、角度特征 ……是否出现 ,目标 Agent 注 视着概念 Agent 的反应. 每个目标 Agent 负责识别 某种特定的模式. 例如 ,一个目标 Agent 识别字母 “A”,而另一个目标 Agent 识别字母“B”,如此类推. 负责“A”的目标 Agent 努力寻找于“A”这个特定模 式有关的特征 Agent. 目标 Agent 一旦找到一个合 适的特征 Agent ,其能量就大增 ,找到的越多 ,能量 就越大. 最后决策 Agent 注意目标 Agent 的能量变 化 ,它把能量最大的 Agent 选出 ,作为模式的解释 , · 09 · 智 能 系 统 学 报 第 1 卷
第2期 程显毅,等:基于多Aget的模式识别框 ·91· 决策Agent相当于分类器.这样一个过程是自下而 所具有,这个步骤相当于“聚类分析”; 上的,也叫数据驱动,因为此时,系统的一切的活动 2)记忆模式的差异特征,该特征反映该模式与 从到达的感知数据开始的,依次通过各级分析向前 同类模式的差别,是独一无二的 的,是按照某种逻辑进行的.对于数据驱动系统来 无疑,理解式记忆具有强的表达能力.作为联想 说,当在最底层输入数据之前,系统什么情况也不发 记忆的神经网络模型,无论是Hopfield模型还是 生,一旦有了输入数据,一切处理就直截了当,迅速 BP模型,实践表明对非常相似的样本或称为同类样 给出答案.所以,数据驱动缺乏灵活性 本都很难记忆.例如Hebb规则的Hopfield网络只 能记忆相互正交或近似正交的样本集,基于伪逆技 术的Hopfield网络只能记忆相互(线性)独立的样 本集.它们均要求样本间有较大的差别.尽管有些算 法能记忆相似的样本,但这些样本的吸引域一般来 说都很小.换句话说,网络对这些样本几乎无联想能 力.这些网络所实现的记忆是否是一种机械记忆这 是值得探讨的问题.人工神经元网络要实现理解式 的记忆,网络必须具备2种能力,即聚类分析与定性 特征分析能力.BP网络是一种前馈网络,Hopfield 网络是一种单层反馈网络,要求如此简单结构的网 络同时具有这2种能力是不现实的 将Agent用于模式内部建模工具,神经网络用 图2心脏MRI 于模式外部建模工具,给出了具有定性分析能力的 Fig.2 MRI of cardiac 模式表示框架(Agent influence map,AIM),它可以 可借的是模式识别并非如此简单.当我们什么 根据任何相似度对样本进行聚类,由神经网络实现 也不知道时,要想用数据驱动解释图2是非常困难 人类在求解复杂问题时所使用的定性推理, 的.当告诉你,这是一张心脏核磁共振切片图时,似 AIM的每个节点称为Agent,其状态值反映了 乎会加快整个解释过程,当你知道要看的是什么,就 Agent对环境的适应性,节点之间的连线标记的权 容易看到它,也就是客体可能的概念的知识有助于 重,称为Agent之间的影响度.影响度的改变采用 解释该客体,这种解释机制是自上而下的,或是概念 类似感知机的影射机制,状态值的改变采用并行的 驱动的,概念驱动从可能是什么概念开始,而后寻找 动力学演化策略 肯定的证据,使处理器倾向于给出预期的结果,概念 AM结构类似于神经网络,但和神经网络有着 驱动系统从某些方面看正是数据驱动的反面,人类 本质的区别:首先,神经网络中的神经元间的相互联 识别过程是需要概念驱动的.知识Agent的引入就 系和影响基本上是以固定的“有线连接”方式进行 是为了实现模式识别的概念驱动.知识Agent随机 的,而AM中的Aget之间的联系却是以一种变 地向观察Agent、特征Agent、目标Agent和决策 动的、可移动的“无线连接”方式实现的;其次,神经 Aget发出信号,帮助它们进行正确的统计和决策. 网络的神经元是没有思维和记忆的,而AM的节点 由Agent组成,Agent是有思维和记忆的,其状态用 4 模式表示 BDI(belief-desier-intention)刻画. 表示与记忆有关,所以首先分析人的记忆原理 最简单Agent可视示为规则.图3给出了短线 记忆方式决定表示的能力.孤立地、刻板地记忆 段对应的AM.它由4个Agent组成,R1,R2,R3 各个模式,是一种机械记忆.这种记忆获得的知识缺 等3个Agent是处理元,R0是全局Agent,是知识 乏相互间的联系,因而它所决定的联想品质是低劣 元,R0的状态值反映了线段的可信度.3个自由输 的.理解式记忆是把当前观察到的模式与已知模式 入端连接着特征Agent. 进行比较分析,加以类别归属,记忆该模式的一般特 如果全局Agent是另一个AIM中某个Agent 征;再将该模式与同类模式进行比较,记忆该模式的 的信念,则该全局节点就演变成处理元,两个AM 差异特征.可以将理解式记忆过程分为2个步骤: 组合成为更复杂的AM. 1)记忆模式的一般特征,这种特征为同类模式 线段距离是相对的,否则AM对图像的缩放敏 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
决策 Agent 相当于分类器. 这样一个过程是自下而 上的 ,也叫数据驱动 ,因为此时 ,系统的一切的活动 从到达的感知数据开始的 ,依次通过各级分析向前 的 ,是按照某种逻辑进行的. 对于数据驱动系统来 说 ,当在最底层输入数据之前 ,系统什么情况也不发 生 ,一旦有了输入数据 ,一切处理就直截了当 ,迅速 给出答案. 所以 ,数据驱动缺乏灵活性. 图 2 心脏 MRI Fig. 2 MRI of cardiac 可惜的是模式识别并非如此简单. 当我们什么 也不知道时 ,要想用数据驱动解释图 2 是非常困难 的. 当告诉你 ,这是一张心脏核磁共振切片图时 ,似 乎会加快整个解释过程 ,当你知道要看的是什么 ,就 容易看到它 ,也就是客体可能的概念的知识有助于 解释该客体 ,这种解释机制是自上而下的 ,或是概念 驱动的 ,概念驱动从可能是什么概念开始 ,而后寻找 肯定的证据 ,使处理器倾向于给出预期的结果 ,概念 驱动系统从某些方面看正是数据驱动的反面 ,人类 识别过程是需要概念驱动的. 知识 Agent 的引入就 是为了实现模式识别的概念驱动. 知识 Agent 随机 地向观察 Agent 、特征 Agent 、目标 Agent 和决策 Agent 发出信号 ,帮助它们进行正确的统计和决策. 4 模式表示 表示与记忆有关 ,所以首先分析人的记忆原理. 记忆方式决定表示的能力. 孤立地、刻板地记忆 各个模式 ,是一种机械记忆. 这种记忆获得的知识缺 乏相互间的联系 ,因而它所决定的联想品质是低劣 的. 理解式记忆是把当前观察到的模式与已知模式 进行比较分析 ,加以类别归属 ,记忆该模式的一般特 征 ;再将该模式与同类模式进行比较 ,记忆该模式的 差异特征. 可以将理解式记忆过程分为 2 个步骤 : 1) 记忆模式的一般特征 ,这种特征为同类模式 所具有 ,这个步骤相当于“聚类分析”; 2) 记忆模式的差异特征 ,该特征反映该模式与 同类模式的差别 ,是独一无二的. 无疑 ,理解式记忆具有强的表达能力. 作为联想 记忆的神经网络模型 ,无论是 Hopfield 模型还是 BP 模型 ,实践表明对非常相似的样本或称为同类样 本都很难记忆. 例如 Hebb 规则的 Hopfield 网络只 能记忆相互正交或近似正交的样本集 ,基于伪逆技 术的 Hopfield 网络只能记忆相互 (线性) 独立的样 本集. 它们均要求样本间有较大的差别. 尽管有些算 法能记忆相似的样本 ,但这些样本的吸引域一般来 说都很小. 换句话说 ,网络对这些样本几乎无联想能 力. 这些网络所实现的记忆是否是一种机械记忆 这 是值得探讨的问题. 人工神经元网络要实现理解式 的记忆 ,网络必须具备 2 种能力 ,即聚类分析与定性 特征分析能力. BP 网络是一种前馈网络 , Hopfield 网络是一种单层反馈网络 ,要求如此简单结构的网 络同时具有这 2 种能力是不现实的. 将 Agent 用于模式内部建模工具 ,神经网络用 于模式外部建模工具 ,给出了具有定性分析能力的 模式表示框架(Agent influence map ,AIM) ,它可以 根据任何相似度对样本进行聚类 ,由神经网络实现 人类在求解复杂问题时所使用的定性推理. AIM 的每个节点称为 Agent ,其状态值反映了 Agent 对环境的适应性 ,节点之间的连线标记的权 重 ,称为 Agent 之间的影响度. 影响度的改变采用 类似感知机的影射机制 ,状态值的改变采用并行的 动力学演化策略. AIM 结构类似于神经网络 ,但和神经网络有着 本质的区别 :首先 ,神经网络中的神经元间的相互联 系和影响基本上是以固定的“有线连接”方式进行 的 ,而 A IM 中的 Agent 之间的联系却是以一种变 动的、可移动的“无线连接”方式实现的 ;其次 ,神经 网络的神经元是没有思维和记忆的 ,而 AIM 的节点 由 Agent 组成 ,Agent 是有思维和记忆的 ,其状态用 BDI(belief2desier2intention) 刻画. 最简单 Agent 可视示为规则. 图 3 给出了短线 段对应的 AIM. 它由 4 个 Agent 组成 , R1 , R2 , R3 等 3 个 Agent 是处理元 ,R0 是全局 Agent ,是知识 元 ,R0 的状态值反映了线段的可信度. 3 个自由输 入端连接着特征 Agent. 如果全局 Agent 是另一个 A IM 中某个 Agent 的信念 ,则该全局节点就演变成处理元 ,两个 AIM 组合成为更复杂的 AIM. 线段距离是相对的 ,否则 A IM 对图像的缩放敏 第 2 期 程显毅 ,等 :基于多 Agent 的模式识别框 · 19 ·
·92 智能系统学报 第1卷 到.换句话说,在系统行为中存在一些规则,这些规 R,:IF对比度<0.3THEN连接两线段,0.4 R2:1F距离<0.01THEN连接两线段,0.56 则是无法通过直接考察各组成部分所满足的规律得 R,:lF平行度<0.2THEN连接两线段,0.7 到的.这些整体行为规则不但可以解释(或部分地解 Rm:IF短线度 释)系统的行为,而且能够用以说明特定行为控制方 式 R R: 3)涌现的特征是组成部分不断改变稳定模式: 0.4 0.56 只有这样的稳定模式才会对涌现系统将来的结构产 生直接的可追踪的影响.当然,规则在一定程度上反 0.7 应了模式结构和变化中所需遵循的联系 R 4)涌现出来的稳定模式的功能是由其所处的环 境决定的.由于非线性的相互作用,一些意义或功能 图3短线段连接AM 是通过上下文体现的,这使得涌现现象很难按一般 Fig.3 AIM of connecting short line 的先验的方式加以定义和研究. 感性较大 5)稳定模式通常满足宏观规律.当宏观规律可 平行度用角度差表示:a叫-2,叫和2分别 以用规则清楚地表达时,对整体模式行为的表达就 为两线段与x轴夹角 不必再借助那些决定组成个体行为的微观规律.相 对比度表示为:s=sl/2,其中sl=graya/ 对于组成个体行为的细节,宏观规律通常是较为简 grayb,2=grayc/grayd,graya为点a的灰度,a,b 单的 为第1个线段的2个端点,c,d为第2个线段的2个 基于涌现原理,给出AM的推理过程,设给定 端点 一个包含n个Agent的AIM,不妨设AgS={R, 优良的短线段特征作为形状识别的局部特征, R,…R},对应的状态值向量V={n,2,,vm}, 可大大减少形状识别的计算量.因此,在形状识别前 w是节点对节点的影响度,其学习算法(略),则影 能够形成具有明显意义的局部特征(基本形状的短 响度矩阵: 线段)是非常必要的 w11 W12 1w1 短线AM可以把诸多短线段连接准则存储在 W21 W22 W2a AM节点中,对连接线段规则的增加,只需增加相 W= 0 应的节点.而目前的线段连接方法比如启发搜索、层 N W22 次标记编组法、认知图法1等只能使用刚性规则,不 Agent的状态转换规则: 能使用连续函数。 V=V .W (1) 5模式涌现 令 V= Swyvi.i=1.2......n. (2) 混沌是确定性系统其内在的随机性,涌现是随 定义节点R的状态输出函数f:,得到节点R,的新 机性系统内在的确定性,混沌和涌现是模式识别具 状态 有的2个显著特征,在模式记忆阶段主要特征是混 沌,而在模式分类阶段主要特征是涌现劇 v=f(wgv},i=1,2,…n (3) 涌现的本质特征:简单中孕育着复杂.在涌现研 Agent的每一次状态转换都可以看作一步推理,A~ 究中,规则集中体现了人类运用抽象和归纳的方法 gent的每步推理都由矩阵运算和状态输出函数实 重新认识世界的能力.涌现的特征可总结如下: 现.设V()是第k步的状态,V(k+1)是下一步的状 1)涌现系统是由那些种类相对较少并遵循着简 态,则从第k步到第k+1步的推理由下式实现: 单规律的一些Agent组成的.一般来说,这些Agent v(k+1)f(v()[f1.f2.....f.]. 相互连接起来形成一种网,这个网在转换函数的作 AM模型给出了Agent知识和环境的完整表达,推 用下可以随时间变化其结构。 理过程通过数值迭代计算的方式单独完成,充分利 2)在涌现系统中,整体大于部分和.模式各部分 用了Agent内部信息,最终的推理结果由决策 间的相互作用是非线性的,所以,模式的整体行为无 Agenta给出的. 法通过相对独立的各组成部分行为的简单叠加得 V的改变反映了待识别模式整体特征的变化, 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 3 短线段连接 AIM Fig. 3 AIM of connecting short line 感性较大. 平行度用角度差表示 :|α1 - α2| ,α1 和α2 分别 为两线段与 x 轴夹角. 对比度表示为 : s = s1/ s2 , 其中 s1 = graya/ grayb , s2 = grayc/ grayd , graya 为点 a 的灰度 , a , b 为第 1 个线段的 2 个端点 ,c ,d 为第 2 个线段的 2 个 端点. 优良的短线段特征作为形状识别的局部特征 , 可大大减少形状识别的计算量. 因此 ,在形状识别前 能够形成具有明显意义的局部特征 (基本形状的短 线段) 是非常必要的. 短线 A IM 可以把诸多短线段连接准则存储在 AIM 节点中 ,对连接线段规则的增加 ,只需增加相 应的节点. 而目前的线段连接方法比如启发搜索、层 次标记编组法、认知图法[7 ]等只能使用刚性规则 ,不 能使用连续函数. 5 模式涌现 混沌是确定性系统其内在的随机性 ,涌现是随 机性系统内在的确定性 ,混沌和涌现是模式识别具 有的 2 个显著特征 ,在模式记忆阶段主要特征是混 沌 ,而在模式分类阶段主要特征是涌现[8 ] . 涌现的本质特征 :简单中孕育着复杂. 在涌现研 究中 ,规则集中体现了人类运用抽象和归纳的方法 重新认识世界的能力. 涌现的特征可总结如下 : 1) 涌现系统是由那些种类相对较少并遵循着简 单规律的一些 Agent 组成的. 一般来说 ,这些 Agent 相互连接起来形成一种网 ,这个网在转换函数的作 用下可以随时间变化其结构. 2) 在涌现系统中 ,整体大于部分和. 模式各部分 间的相互作用是非线性的 ,所以 ,模式的整体行为无 法通过相对独立的各组成部分行为的简单叠加得 到. 换句话说 ,在系统行为中存在一些规则 ,这些规 则是无法通过直接考察各组成部分所满足的规律得 到的. 这些整体行为规则不但可以解释(或部分地解 释) 系统的行为 ,而且能够用以说明特定行为控制方 式. 3) 涌现的特征是组成部分不断改变稳定模式. 只有这样的稳定模式才会对涌现系统将来的结构产 生直接的可追踪的影响. 当然 ,规则在一定程度上反 应了模式结构和变化中所需遵循的联系. 4) 涌现出来的稳定模式的功能是由其所处的环 境决定的. 由于非线性的相互作用 ,一些意义或功能 是通过上下文体现的 ,这使得涌现现象很难按一般 的先验的方式加以定义和研究. 5) 稳定模式通常满足宏观规律. 当宏观规律可 以用规则清楚地表达时 ,对整体模式行为的表达就 不必再借助那些决定组成个体行为的微观规律. 相 对于组成个体行为的细节 ,宏观规律通常是较为简 单的. 基于涌现原理 ,给出 AIM 的推理过程. 设给定 一个包含 n 个 Agent 的 A IM ,不妨设 AgS = { R1 , R2 , …, Rn } ,对应的状态值向量 V = { v1 , v2 , …, vn } , wij是节点对节点的影响度 ,其学习算法 (略) ,则影 响度矩阵 : W = w11 w12 … w1 n w21 w22 … w2 n … … … … wn1 wn2 … wnn . Agent 的状态转换规则 : V = V ·W. (1) 令 V i = ∑ n j = 1 wij v i , i = 1 ,2 , ……, n. (2) 定义节点 Ri 的状态输出函数 f i ,得到节点 Ri 的新 状态. v′i = f i ( ∑ n j = 1 wij v i) , i = 1 ,2 , …, n. (3) Agent 的每一次状态转换都可以看作一步推理 ,A2 gent 的每步推理都由矩阵运算和状态输出函数实 现. 设 V ( k) 是第 k 步的状态 ,V ( k + 1) 是下一步的状 态 ,则从第 k 步到第 k + 1 步的推理由下式实现 : V ( k + 1) = f (V ( k) ) = [ f 1 , f 2 , …, f n ] T . AIM 模型给出了 Agent 知识和环境的完整表达 ,推 理过程通过数值迭代计算的方式单独完成 ,充分利 用了 Agent 内部信息 , 最终的推理结果由决策 Agent给出的. V 的改变反映了待识别模式整体特征的变化 , · 29 · 智 能 系 统 学 报 第 1 卷
第2期 程显毅,等:基于多Aget的模式识别框 ·93· 该变化是通过AM推理来融合待识别模式的局部 特征得到的.所以,基于APRF的识别不是基于某 参考文献: 一规则的二份法,而是利用待识别模式的所有局部 [1JIAN A K,DUIN R P W,MAO Jianchang.Statistical 特征融合而成,待识别模式某一局部特征的缺省,不 pattern recognition:a view [J].IEEE Transaction on Pat- 会对目标识别产生较大的影响.因此,APRF模式识 tern Analysis and Machine Intelligence,2000,22(1):34- 别方法具有较好的鲁棒性 37 [2]HAJEB H.大脑工作原理—脑活动、行为和认知的协 6 仿真实验结果分析 同学研究[M.上海:上海科技教育出版社,2000 [3]王首觉.仿生模式识别—一种模式识别新模型的理论 根据第4节的计算框架,用Matlab进行了联想 与应用[U].电子学报,2002,30(10):1417-1420 记忆的仿真实验.对OL库的人脸人为进行了x WANG Shoujue.Bionic Topological)pattern recogni- 方向缩小,如图4的第1幅图.经过15步演化正确 tion-a new model of pattern recognition theory and its 识别出原始的人脸,但不一定是缩小的那张人脸,而 applications [J ]Acta Electronica Sinica,2002,30(10): 是同类人脸10个样本的一个.同样的样本用PCA 1417.1420. 方法识别结果是错误的. [4]CHARTIER S,BOU KADOUM M.A sequential dy- namic heteroassociative memory for multistep pattern recog-nition and one-to-many association [J].IEEE Transactions on Neural Networks,2006,17(1):59-68 [5]RAHTU E,SALO M,HEIKKILA J.Affine invariant Gu 国国国国国 pattern recognition using multiscale autoconvolution[J]. 道 IEEE Transactions on Machine Intelligence,2005,27 (6):908-918 [6]程显毅.Agent计算[M].哈尔滨:黑龙江科学技术出版 社,2003. 图4放缩噪声的识别结果 [7]骆祥峰,高隽,张旭东.基于信任知识库的概率模糊认 Fig.4 Recognition results of test data including scaling noise 知图J].计算机研究与发展,2003,40(7):925.934. LUO Xiangfeng,GAO Jun,ZHANG Xudong.Probabilis- 7结束语 tic fuzzy cognitive map based on belief knowledge data 传统模式识别研究以简单特征为基础,而 base [J].Journal of Computer Research and Develop- ment,2003,40(7):925.934. APRF的注意力集中在整个特征网络的活动上.本 [8]HOLLANDJ H.涌现从混沌到有序[M].上海:上 文运用多Agent技术,将传统的静态、集中式模式 海科技教育出版社,2001 识别环境推广到动态、分布计算环境中,把传统的自 作者简介: 上而下的模式识别方法和自上而下的模式识别方法 程显毅,男,1956年生,博士,教授 统一起来,分为2个阶段.模式建模阶段解决“记忆” 主要研究方向为模式识别、多Agent系 问题,模式涌现阶段解决“推理”问题.提出了基于知 统.参与或主持课题多项,主要学术专 识的模式表示模型,或称为Agent影响图(Agent 著《Aagent计算》,发表论文70多篇.E influence map,AM).该模型能够实现用简单规则 mail xycheng @ujs.edu.cn. 控制的模型来解释模式涌现现象:从局部到整体的 转换.由于篇幅所限,本文只是简单地说明了APRF 的研究目标和基本思想,在后续的文章中,将讨论 陈小波,男,1982年生,江苏大学计 APRF的关键技术的设计和实现, 算机科学与通信工程学院硕士研究生 主要研究方向为模式识别,多Agct系 统 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
该变化是通过 AIM 推理来融合待识别模式的局部 特征得到的. 所以 ,基于 APRF 的识别不是基于某 一规则的二份法 ,而是利用待识别模式的所有局部 特征融合而成 ,待识别模式某一局部特征的缺省 ,不 会对目标识别产生较大的影响. 因此 ,APRF 模式识 别方法具有较好的鲁棒性. 6 仿真实验结果分析 根据第 4 节的计算框架 ,用 Matlab 进行了联想 记忆的仿真实验. 对 ORL 库的人脸人为进行了 x 方向缩小 ,如图 4 的第 1 幅图. 经过 15 步演化正确 识别出原始的人脸 ,但不一定是缩小的那张人脸 ,而 是同类人脸 10 个样本的一个. 同样的样本用 PCA 方法识别结果是错误的. 图 4 放缩噪声的识别结果 Fig. 4 Recognition results of test data including scaling noise 7 结束语 传统模式识 别研究以 简单特征 为基础 , 而 APRF 的注意力集中在整个特征网络的活动上. 本 文运用多 Agent 技术 ,将传统的静态、集中式模式 识别环境推广到动态、分布计算环境中. 把传统的自 上而下的模式识别方法和自上而下的模式识别方法 统一起来 ,分为 2 个阶段. 模式建模阶段解决“记忆” 问题 ,模式涌现阶段解决“推理”问题. 提出了基于知 识的模式表示模型 ,或称为 Agent 影响图 ( Agent influence map ,A IM) . 该模型能够实现用简单规则 控制的模型来解释模式涌现现象 :从局部到整体的 转换. 由于篇幅所限 ,本文只是简单地说明了 APRF 的研究目标和基本思想 ,在后续的文章中 ,将讨论 APRF 的关键技术的设计和实现. 参考文献 : [1 ]J IAN A K , DUIN R P W , MAO Jianchang. Statistical pattern recognition : a view[J ]. IEEE Transaction on Pat2 tern Analysis and Machine Intelligence ,2000 ,22 (1) :34 - 37. [2 ] HAJ EB H. 大脑工作原理 ———脑活动、行为和认知的协 同学研究[ M ]. 上海 :上海科技教育出版社 ,2000. [3 ]王首觉. 仿生模式识别 ———一种模式识别新模型的理论 与应用[J ]. 电子学报 ,2002 ,30 (10) :1417 - 1420. WAN G Shoujue. Bionic ( Topological ) pattern recogni2 tion —a new model of pattern recognition theory and its applications[J ]. Acta Electronica Sinica , 2002 ,30 (10) : 1417 - 1420. [4 ] CHARTIER S , BOU KADOUM M. A sequential dy2 namic heteroassociative memory for multistep pattern recog2nition and one2to2many association [ J ]. IEEE Transactions on Neural Networks ,2006 ,17 (1) :59 - 68. [5 ] RA H TU E , SALO M , HEIKKILA J. Affine invariant pattern recognition using multiscale autoconvolution[J ]. IEEE Transactions on Machine Intelligence , 2005 , 27 (6) :908 - 918. [6 ]程显毅. Agent 计算[ M]. 哈尔滨 :黑龙江科学技术出版 社 ,2003. [7 ]骆祥峰 ,高 隽 ,张旭东. 基于信任知识库的概率模糊认 知图[J ]. 计算机研究与发展 ,2003 ,40 (7) :925 - 934. LUO Xiangfeng , GAO J un , ZHAN G Xudong. Probabilis2 tic fuzzy cognitive map based on belief knowledge data base [J ]. Journal of Computer Research and Develop2 ment , 2003 ,40 (7) :925 - 934. [8 ] HOLLAND J H. 涌现 ———从混沌到有序[ M ]. 上海 :上 海科技教育出版社 ,2001. 作者简介 : 程显毅 ,男 ,1956 年生 ,博士 ,教授 , 主要研究方向为模式识别、多 Agent 系 统. 参与或主持课题多项 ,主要学术专 著《Aagent 计算》,发表论文 70 多篇. E2 mail :xycheng @ujs. edu. cn. 陈小波 ,男 ,1982 年生 ,江苏大学计 算机科学与通信工程学院硕士研究生 , 主要研究方向为模式识别 ,多 Agent 系 统. 第 2 期 程显毅 ,等 :基于多 Agent 的模式识别框 · 39 ·