4.2　非规范知识处理研究成果概述

非规范知识处理在理论研究上取得的成果主要包括进程代数及其互模拟、基于SAT的计算复杂性、非经典逻辑的证明论和模型论，以及定性空间知识表示和推理等。

应明生吸取了Shannon的信息论中信息噪声的思想，提出了带噪声信道的Pi演算，从而迈出了把历史上最重要的两大通信理论结合起来的第一步。曹永志通过将移动通信进程中噪声信道上的单个传值或传名理解为无噪声信道上的传词，进一步发展了带噪声的Pi演算，包括给出了带噪声的Pi演算的早变迁语义及其两种表示。柳欣欣提出了上下文无关文法进程扩张互模拟的概念，给出了其等价性的一个有穷刻画，并提出了一个Tableau方法来有效地解决上下文无关文法进程之间的弱互模拟等价判定问题。朱朝辉对近似互模拟方法和行为拟度量方法的内在联系进行了研究，证明Lambda互模拟可以诱导出进程之间一种距离度量，并给出了该距离函数的不动点特征，但该距离与Breugel行为拟度量具有完全不同的直观含义。林方真将“completion+循环公式”的思想扩充到非单调逻辑circumscription，这个结果可以高效实现SAT求解器或答集求解器的命题级circumscription；进一步地，林方真将此结果推广到一阶逻辑和带函数的正规逻辑程序。苏开乐（与林翰合作）提出了一个求解（带权）MAX-SAT问题的一般逻辑框架，弱化了以往MAX-SAT求解器的严格等价规则，进而提出了等价的概念和等价但非严格等价的规则，得到了MAX-2-SAT的一个新的可纳（admissible）下界启发函数，它一致地优于此前的下界函数。苏开乐提出了全自动模型检测时态认知逻辑的一个原始版本，该方法要求Agent带有完全记忆，给出了实用有效的完全自动的模型检测时态知识、信念、意图逻辑规范的算法。林作铨研究了超协调缺省逻辑，作为缺省逻辑的一种超协调扩展，它在包含不协调知识时同样能得到有意义的结论，而且还不增加计算复杂度；同时，林作铨进一步研究超协调描述逻辑，并给出了基于表系统和归结方法的ABox和TBox自动推理系统。朱朝晖研究了非单调逻辑中重要的一种语义模型—占优模型的模型论性质，为非单调推理尤其是择优型非单调推理提供了模型论基础，将非单调逻辑模型论的研究推进到类似于经典逻辑和模态逻辑的深度。刘椿年、郑磊、王洁等将他们在约束归纳逻辑程序设计、概率逻辑程序设计、遗传归纳逻辑程序设计、基于答集语义的模糊约束逻辑程序设计等方面的成果应用于解决实际问题，成功地从静力学实验数据学习出杠杆平衡方程，还研制了遗传归纳逻辑程序设计系统GILP。李三江提出了一个包括离散和连续模型的新理论—GRCC理论，并给出从离散模型构造连续模型的方法；他还研究了RCC理论的可数模型和极小模型，给出RCC11关系（RCC8关系的一个细化）的一个外延性模型，证明任何相容的RCC8关系网络都是可以一步相容扩张的，并给出了相应算法。欧阳继红、刘大有等人把Egenhofer的9-交集模型应用于非凸域的研究，推导出39种新的拓扑关系，提出了新的D9-交集模型，可以同时表达带洞区域拓扑关系。李三江对一般区域间的拓扑关系进行了完备分类，得到了43种9-交拓扑关系。

非规范知识处理在技术和算法研究上取得的成果主要在金融智能算法、非规范数据的数据挖掘和机器学习、复杂系统的结构和动力学行为、领域有关的非规范知识等方向。

邓小铁研究了基于博弈论方法设计合理协议以保证个体行为真诚的问题，在多种特别条件下给出了计算套利的多项式算法，研究了证券组合的动态最优配置分析，其中风险模型是比通常方法更为精确的EaR方法；他还得到了一个最基本的离散空间不动点定理，以往的离散空间不动点定理都可以由此得出。石纯一、张伟等研究了基于多Agent组合的拍卖和多属性拍卖，针对边际效用递减的组合拍卖提出了物品组合的1-UNT条件，给出了一种基于1-UNT检查的近似算法，证明了1-UNT算法的解的效用率不低于0.5。张成奇和张师超等研究了数据层面上的非规范性，如数据不完备（缺失数据、难获取数据）、数据污染和数据异质性（表示异质、度量异质、数据信息量不对称）对数据挖掘的影响，以及在数据非规范情况下的特定数据挖掘技术，开发了缺失数据补值、含缺失数据的归纳学习模型、差异分析、高维模式发现、局部模式分析、减量式挖掘、跨事务项集对挖掘、代价敏感学习等多种有效技术。周志华通过引入三个分类器提出了Tri-training算法，不要求充分且独立的数据属性集，对个体学习器算法类型没有限制，并且不需要使用耗时的交叉验证，能够更好地利用未标记数据来提高泛化性能。钟义信指出知识是一个大规模、多层次、多分支、具有复杂交互作用的网络体系，提出并研究了知识作为一个具有生命的开放的动态过程，还研究了信息-知识-智能转换机制，以及知识的系统结构、分类准则、描述方法与定量计算。章忠志和周水庚等从确定性与随机性两个方面构建各类复杂网络的演化模型，解析并模拟研究了模型的统计特性，能再现真实系统的主要特性，还将小世界网络与无尺度网络、分形的无尺度网络与非分形的无尺度网络分别进行了统一，提出计算网络平均距离与谱性质的解析方法，在经典分形与复杂网络之间建立了一一对应的映射关系。李德毅从云模型和认知物理学出发研究了关联知识的网络拓扑表示方式，对网络拓扑的不确定性进行了计算机模拟，利用数据场理论研究了复杂网络动力学的同步行为和涌现机制，从能量传播的角度研究了复杂网络中节点失效的级联传播导致网络连锁崩溃的机制，建立了基于能量的复杂网络级联失效传播模型。牟克典、金芝等研究了不一致性需求处理技术，包括采用多值信任半格以区分处理不同的非规范需求，提出了一系列基于需求优先级的矛盾需求度量函数，研究效用向量函数以评估并排序处理方案，基于矛盾处理的不同视点提出视点投票机制，提出基于协商和Merging的矛盾处理方法。卜东波课题组和王飞课题组以系统生物学为背景研究生物分子网络的拓扑结构、特征提取、网络融合、网络演化和网络形式化模型等。陆汝占提出一套汉语概念内涵逻辑模型的理论，这种植根于本土文化的汉语概念内涵逻辑的思想已开始走向网络检索和图书情报检索的应用领域。应明生课题组研究量子信息处理涉及的非规范性，例如非交换性、非分配性、非局域性等，应明生建立了基于量子逻辑的计算理论，冯元等给出了4×4维纠缠态转化存在2×2维催化剂的充分必要条件，对一般情形，给出了判断催化剂存在的多项式时间算法；段润尧研究了概率纠缠转化中的催化剂和部分催化剂存在的条件及优化算法。

非规范知识处理在平台建设上取得的成果主要在第二代浏览器和语义网、非规范知识资源库等方向。

陆汝钤院士提出第二代浏览器的思想，让计算机从网页中自动提取和组织知识。目前共研究和开发了两个初步具有此功能的浏览器：一个是周傲英课题组开发的Dolphin系统，另一个是孙吉贵课题组开发的第二代浏览器原型系统CRAB。Dolphin系统是一个能够从科技文献类的网页中提取关键信息，组织成知识库，并向用户提供查询界面的第二代浏览器雏形，研究内容功能包括Web页面分类、Web页面聚类和分布式Web搜索，在网上知识获取、数据的有效组织和索引、高效的数据分析等方面均取得了比较理想的效果；CRAB是一个面向金融信息领域的网页搜索和知识抽取系统，包括网页分类器、主题网页爬行器、定向信息爬行器、网页处理器、网页知识抽取器、本体实例化组件、知识合并组件、查询分析器、查询模版管理器、报告生成器、本体推理器等模块。王珊、杜小勇课题组研究了基于领域本体的知识组织体系理论，以经济学和法学为专业领域，建设一个示范人文社会科学语义网（知识仓库），完成主题资料编辑出版器和网上虚拟实验室等应用示范，构建经济学领域本体EO2.0，完成了本体数据管理系统CODE v1.0和CODERS v2.0的研制经济学知识检索系统和法学知识检索系统。非规范知识处理也建设了一批非规范知识资源库，包括百科专业知识库CNKI（曹存根）、概念和概念关系库XHS（曹存根）、近30年计算机科学论文库Dolphin系统（周傲英）、经济学和法学知识本体库（王珊、杜小勇）、基因数据仓库BioWorld（彭政、王飞）、非编码基因综合知识库NONCODE（卜东波）、支持时空推理的WebGIS平台PMGIS及其农业应用版本（王生生、刘大有）等。

国家自然科学基金重大项目“非规范知识处理的基本理论和核心技术”结题距今已将近十年，以其为起点，十年来中国人工智能学者对非规范知识处理的研究取得了长足的进步，做出了很多有自己特色并得到国际同行高度评价的深入工作。在理论研究方面，应明生在理论计算机科学，特别是量子计算方面处于国际领先地位，成为该领域国际著名专家和领军人物。他建立了量子程序的首个公理化逻辑并证明其完备性，从而开拓了量子程序正确性证明的方向，被称为“量子程序设计语言理论发展中的一个里程碑”。他的研究还包括量子程序形式语义、量子纠缠态平行双模拟、基于量子马尔科夫链的形式语义、拓扑进程演算及其形式语义、量子线路代数、量子随机游走、全加型概率进程代数等。在知识工程研究方面，陆汝钤院士提出知件（Knowware）的概念，把知识从软件中分离出来，作为硬件和软件之后的第三大IT支柱，他给出了知件概念，并研究知件技术、知件生命周期模型以及基于知件的软件工程。陆汝钤院士研究大知识现象，通过深入分析国内外若干大型知识工程项目提炼出大知识的5个MC（Massive Characteristics）特征，以及大知识系统应有的5+5个MC特征，并给出了各个MC特征的定性和定量参考标准，进一步地给出了大知识工程的初步定义及其生命周期模型。曹存根前瞻性地提出建设国家知识基础设施，致力于研究大规模公共知识和专业知识的获取与处理方法，同时研究知识的基础理论，包括各种语义现象的分类和描述框架的构建、本体论、概念空间理论、知识分析、常识推理、情绪模型等，建立了大规模多学科知识资源，涉及中医、地理、军事、汉语、常识等，并以此为基础研究各类应用技术，包括知识共享系统、知识管理系统、中文自然语言对话系统、企业客服系统、错误字符识别和纠错系统、故事生成等。在机器学习研究方面，周志华成为中国机器学习研究的领军人物之一，在集成学习、办监督学习、多示例和多标记学习等方面做出了在国际上有重要影响的工作。