人工智能发展近况

CommunicationsofCCF2008/815人工智能发展近况高小山孙吉贵李三江姚天顺陆汝占欧阳丹彤石纯一韩战钢曹存根郑晓龙曾大军王飞跃陆汝钤工智能在最近几十年的发展跌宕起伏，然而始终是计算机科学家关注的重要领域，因为其研究对计算机科学不断提出新的挑战，促进了计算机科学各个分支的探索。中国科学家在这一过程中也做出了重要贡献。本文由人工智能各个领域的一些专家分头执笔，力图为读者提供一幅人工智能发展的全景视图，以便各学科更好地互相借鉴。一、数学机械化吴文俊提出的数学机械化设想虽然是数学领域的工作，但对人工智能的许多领域却有着深远影响。在过去的20多年中，中国学者把方程求解的“吴消元法”用于定理自动证明、物理规律自动发现、计算机图形学、智能计算机辅助设计（CAD1）、计算机视觉、图像压缩、机器人和数控等关键技术的研究中，取得了重要进展。目前，数学机械化研究还处于初始阶段，主要研究集中在初等与微分几何定理的机械化证明与代数与微分方程的自动求解。近年来这方面研究所产生的重要成果如下：1．高级不变量的机械化方法[1]：希尔伯特（Hilbert）、维羽勒（Weyl）虽然解决了基本几何不变量的理论问题，但存在难于计算的困难。自1970年以来，罗塔（Rota）学派发展的格拉斯曼-克雷（Grassmann-Cayley）代数，虽然部分地解决了基本不变量的计算问题，但计算困难依然很大。中国学者建立了经典几何的高级不变量代数系统，解决了计算量大的问题，因而可用它证明几何定理。国际同行认为，该项工作是符号机器证明领域的一个突破，其意义超出该领域本身。该成果获得当年美国计算机学会（ACM2）符号与代数计算专委的“ISSAC3杰出论文奖”。2．微分-差分方程的特征列方法[2]：针对微分-差分（DD4）方程，证明了微分-差分多项式系统的诺特（Noetherian）性质，即任意微分-差分多项式组的零点与有限个微分-差分多项式组的零点相同。此外，建立了微分差分情形的零点分解定理，解决了微分-差分多项式系统的完备理想成员问题，将数学机械化方法推广到了微分-差分方程中。3．计算机处理无穷对象的研究[3]：基本的想法是将这些概念看作某些方程的解来处理。劳伦特-奥尔（Laurent-Ore）模是线性微分与差分方程的抽象表示。该项研究首次提出了确定劳伦特-奥尔模一维子模的算法，为分解有限型微分-差分模奠定了基础，并获得美国计算机学会符号与代数计算专委的“ISSAC杰出论文奖”。4．数学机械化方法在数控技术中的应用[4]：斯图尔特（Stewart）平台是一种应用广泛的并联机构。通过引进广义斯图尔特平台概念，得到了比原来的机构更好的机械和1ComputerAidedDesign，计算机辅助设计2AssociationforComputingMachinery3InternationalSymposiumonAlgorithmsandComputation，国际算法与计算研讨会4Differential-Difference人专题报道／CoverFeaturesCommunicationsofCCF2008/816数学性质，还给出了其最佳解的个数，解决了这类并联机构应用的瓶颈。并联机构的研究被应用于集成电路制造设备的关键部件——超精密运动台与离子注入机靶室的研制。二、机器学习有人断言，在这个信息爆炸的时代，全世界只有不到1%的信息可以作为知识使用。如何使信息自动转化为知识，是机器学习的任务。2001年，美国科学家在《科学》（Science）杂志上撰文指出：机器学习对科学研究的整个过程正起到越来越大的支持作用，该领域在今后的若干年内将取得稳定而快速的发展。2003年，美国国防部高级研究计划署（DARPA5）开始启动以机器学习为核心的5年学习型感知助手（PAL6）计划。该计划首期（1～1.5年）投资2900万美元，将机器学习技术放到了国家安全的角度来考虑。自20世纪90年代万普尼克（Vapnik）提出统计机器学习理论以来，机器学习得到快速发展和广泛应用。万普尼克的统计学习理论及在其基础上发展的支持向量机算法的主要贡献在于：其一，在有限样本的条件下建立泛化的统计理论，因而符合应用的情景；其二，将非线性学习的问题化为寻找高维空间线性模型的问题，该过程称为核映射；其三，算法设计基于凸优化。与此同时，基于弱分类器的方法也在发展。所谓弱分类器，就是计算一组模型，其中每个模型对问题的正确率仅比随机猜想稍好，即比50%稍好。理论上已经证明，将这些弱分类器组合，可以获得一个正确率达到要求的强分类器。针对不同的数据和应用场景发展了多种学习方法。例如流形学习旨在通过对观测数据的计算，发现高维空间中数据集合构成的低维流形。关系学习试图从关系数据集合中归纳出一个模型来。半监督学习用于处理样本量很大，但其中只有一小部分有标记的情况。排序（Rank）学习来源于信息检索，利用样本集进行排序。增强学习的理论就像“吃一堑，长一智”一样，主要解决机器人规划、避障与在环境中适应的学习问题。多示例学习针对同一学习对象有多个属性描述的问题。数据流学习则用于处理高速通过但不能存储且不能二次扫描的数据。中国学者的机器学习研究主要在研究院所和高校进行，其中在数据归约理论[5-6]，集群学习[7]和半监督学习理论[8]等方面的成果均受到国际重视。三、自动推理自动推理作为人工智能的核心技术取得了丰富的研究成果。其方法主要包括：归结方法、表推演方法、基于公理的系统、自然演绎方法、专门用于等词推理的重写系统和新兴起的实例化方法[9]。基于归结方法的优秀推理系统有奥特（Otter）和吸血鬼（Vampire）等，已经成功应用于很多学术和工业项目。近年来出现了非经典逻辑归结方法的新热点。吴文俊的“吴方法”独树一帜，并于1997年获国际自动推理领域最高奖——埃尔布朗（Herbrand）奖[10]。有关的学术会议主要有国际自动推理联合大会（IJCAR7），学术刊物有自动推理学报（JAR8）。欧洲在自动推理方法、推理系统的研究和应用等方面处于世界领先地位，尤以德国、英国最为突出。除欧洲之外，美国和澳大利亚也位于前列。英国利物浦大学在将归结方法推广到时态逻辑方面取得了丰富的成果，并且已经在分布式系统的设计中得到了成功的应用。澳大利亚国立大学将归结方法结合到局部随机搜索中，大幅度提高了可满足性问题（SAT9）和约束满足问题（CSP10）系统的求解效率。5TheDefenseAdvancedResearchProjectsAgency6PerceptiveAssistantthatLearns7InternationalJointConferenceonAutomatedReasoning8JournalofAutomatedReasoning9Satisfiability10ConstraintSatisfactionProblemCommunicationsofCCF2008/817自动推理的发展深刻地影响着人工智能乃至计算机科学的研究方向，并在工业生产和科学研究中发挥着巨大的作用。模型检测是自动推理的重要应用领域之一。美国德克萨斯大学开发的数理逻辑机械化定理证明器ACL211已经成功地应用到许多重要工业和商业硬件校验项目中。美国的IBM、超威（AMD）、英特尔、微软和摩托罗拉等著名的跨国企业均采用自动推理技术来提高自己的产品质量，并取得了丰厚的商业回报。中国学者在归结方法的改进和非经典逻辑推理方法研究方面取得了一系列成果，并将其应用于智能规划和安全协议验证等领域中。2003年提出了一种新的独立于归结和表推演方法的扩展规则方法[11]。国际著名人工智能专家戴维斯（Davis）称之为与归结方法“互补”的自动推理方法，墨瑞（Murray）教授也对基于该方法提出的EPCCL理论给予了很高评价[12]。四、时间和空间知识表示和推理时间和空间的表示与推理是人工智能的重要研究内容，在地理信息系统、机器人学和自然语言处理等领域有着重要应用。艾伦（Allen）[13]提出的区间代数是时态推理的主要模型。国际上已有大量针对区间代数的性质和计算复杂性的工作。相对而言，空间推理要比（本质上是一维的）时态推理复杂得多。空间关系大致可以分为拓扑关系、方位关系和度量关系等三种。目前提出的空间关系模型已有几十种，最著名当属区域连接演算8（RCC812）拓扑代数[14]和9-交模型13[15]。中国学者在空间知识的表示与推理方面也做了大量的工作。在空间关系建模方面，陈军等[16]提出了基于沃洛诺依（Voronoi）区域的9-交拓扑关系模型；刘瑜等[17]建立了空间内方位关系模型；李三江等发展了区域连接演算，提出了能同时容纳空间拓扑信息的离散和连续模型的形式系统[18]，建立了空间拓扑信息的分层表示理论[19]，并对一般区域间的拓扑关系进行了完备分类[20]。在空间约束求解方面，李三江等发展了复合推理技术，解决了复合推理的两个关键问题[21,22]，证明了以往研究中采用的“RCC8代数对关系复合封闭”假定对任何区域连接演算模型都是不成立的，提出了一步扩张的重要概念，并证明了RCC8关系代数满足这一性质[23]，解决了内贝尔（Nebel）等人[24]工作中存在的问题；张晓彤等[25]首次给出了葛亚-艾恩霍夫（Goyal-Egenhofer）主方位关系模型[26]的可满足性问题的多项式算法。此外，在多种空间约束的融合、空间不确定信息建模等方面，中国学者也做了很多工作[27-31]。五、自然语言处理自然语言处理是以机器翻译为代表兴起的，先后经历了基于规则、基于实例和基于统计等三种研究方法和融合阶段，至今还有一些基本问题（例如，对于汉语词类划分这样一个最基本的问题）尚未解决。现代汉语中词分为几类？如何划分？当前社会实践中出现诸多跨类的活用情况，已显示出新鲜活力，难以用传统的词类规范及句法理论来解释。由此也影响分词技术以及句法分析的准确性。分词是汉、日等亚洲语言所特有的基础性技术。由于词串是表达相对完整语义的，可作为语言计算的单元，因此要将文本中的字符串分割成词串。深层次的原因是汉语属于义符文字，没有形态变化，汉语在词、语、句三个不同阶段的构造方法都是一致的，在形式上是毗连（组合），实质上是概念直接耦合，语言组合规则不显现在形态的词法和句法上，而是包含在修辞范围内[32]。被世界公认的由祖国大陆学者在语言处理领域提出的创新理论方法并不多见。要在这方面有所突破，是从方法论出发，还是从汉语本身特点出发呢？真11AComputationalLogicforApplicativeCommonLisp12RegionConnectionCalculus139-交模型是一种表达三维空间拓扑关系的常用方法专题报道／CoverFeaturesCommunicationsofCCF2008/81正的创新性理论可能在于后者，因为共性寄寓于个性之中。董振东[33]建立的汉语“知网”与本体论（Ontology）的语义网从某个视角来看是类似的，都是从意义的最小基本单元出发，通过构建知识网络体系，把求解2个语词所表示的概念之间的关系归结到知识网上两点间的距离。虽然作为一个语言的概念语义体系，知识网是一个静态的全局网络结构（尽管在使用中可动态维护、扩展和修改），但其任意2个语词表达的概念间距离却是可动态计算的，因此也为处理词义的相似性、相关性提供了可能性。由于客观世界中每个实体及其所包含的内涵特性是个性化的，因而需要展开其内涵定义和凸现区分特点[34]。对于汉语来说，实体命名拥有独特方式，即“实体类名+凸现区分特征”这种方式构成命名时的必要特征，用以区分各子类实体，比如“面包”、“面包片”和“奶酪面包”。为此，检索应用中需要考虑汉语实体命名中内涵特征以及语用情况下内涵特征的增、删、变异操作（如“笔”中“金笔”、“奥运镶玉金笔”）是如何进行概念内涵特征运算的。语料库方法已经得到普遍采用。1991年，中国国家语言文字工作委员会开始建立国家级大型汉语语料库来供汉语信息处理研究。语言文字应用研究所基于2