定性推理经典方法的数学结构分析.pdf

定性推理经典方法的数学结构分析定性推理经典方法的数学结构分析 杨正瓴1 1天津大学电气与自动化工程学院 300072 E mail zlyang 摘摘 要 要 在简单回顾了定性推理的目标和特征的基础上 从代数结构 信息复杂性等方面分 析了现存的 6 个代表性定性推理理论 从代数结构上看 它们或大约在环的水平 或大约接 近于域 从复杂性看 有的以一阶逻辑为演算核心 有的大约以实数域作为核心 从求解效 率看 最坏情况大都倾向于到指数界 平均情况时好时坏 常在多项式界 最后 提出 一 般的几何曲线 层次的演算体系是定性推理的最高数学抽象 关键词 关键词 定性推理 数学结构 复杂性 环 域 人工智能 1 引引 言 AI 中定性推理的目标和特征概述言 AI 中定性推理的目标和特征概述 人工智能 AI 中的定性推理定性推理研究起因起因于力图将专家及常人解决常识问题的能力的计算 机化 Williams等人认为 定性推理的核心是 发展关于科学家 工程师以及常人的下述的 核心技能的计算理论 即他们的假设 验证 预言 创造 优化 诊断和维修物理机构的能 力 1 p2 这是一个关于定性推理的从外部功能的描述 定性推理的 5 个直接的起因为 常识性知识的使用与表示 某些领域的问题 精确定量的信息是不可能或不必要的 需 要进行的是定性行为的分析和预测 在启发式专家系统中 不同领域和不同任务的知识转换 时遇到的困难 需要定性方法 某些情况下系统的动态行为 或时态推理的需要 寻找系统 的因果关系 众所周知 如果一个问题能找到精确的数量化方法并且求解不太难的话 人们通常不会 采用定性方法 如在物理学中用微分方程来描述物理系统 但由于 大多数从实际问题抽象 出来的微分方程的通解不能用初等函数的积分来表示 2 p60 因此现代意义上的定量是不能 实现 实际上 客观世界中大量的问题的微分方程模型就是这样的 19 世纪末H 庞加莱和 A M 李亚谱诺夫开始发展较为系统的 常微分方程的定性方法 2 p60 可是对于复杂的非 线性问题 这种属于传统数学的 定性方法 仅能得到很少的一些性质 3 p70 不足以实用化 于是 在 20 世纪 70 年代 在AI中蓬勃发展起了AI中的 定性方法 其目的在于解决实 际中的各种复杂问题 这些问题的基本特征是 人类 可解 但现有数学 不可解 从 定量到定性方法的一个大致关系如下图 1 所示 传统数学中的 定性方AI 中的 定性方法 定量化 图 1 从定量到定性 对于常识和复杂问题的表达 定量方法 能力太弱 能力以箭头方向加强 1 现存定性推理的目的现存定性推理的目的是通过对系统的结构 行为和功能的描述 寻找它们之间的关系和 因果性 并且力图弄清人类的常识推理 现存定性推理与传统定量方法的主要区别有 度量尺度不同 定性推理是量空间的离散度量 传统方法是实空间的连续度量 描述问题的模型不同 前者使用定性约束定性进程等定性模型 后者使用微分方程代数 方程等精确定量模型 仿真过程和结果的差异 前者使用局部传播得到系统的定性行为描述 预测和解释 后 者是方程求解力图得到精确的数量解 推理能力不同 前者使用局部传播得到系统的定性行为描述 预测和解释 给出因果性 关系 后者不具备明显的因果能力 因果性隐含在解的数值之中 4 当今国际 AI 界对定性推理是很重视的 Artificial Intelligence 在 1984 1991 年分别 出过 2 个专辑 1993 年又有大量篇幅用在定性推理的展望上 如文献 18 23 24 以及其它一 些我们没有列出的该辑的文献 2 现存的现存的 AI 中的定性推理的主要代表性方法的代数结构中的定性推理的主要代表性方法的代数结构 2 1 现存的代表性定性推理理论现存的代表性定性推理理论 公认的定性推理的三大基本方法是 Kuipers的定性模拟QSIM 5 Forbus的定性进程方法 6 de Kleer的透视法 定性方程 法 7 另外一些有特色的工作有Williams的定性定量结合 研究 8 H A Simon关于定性推理数学本质的研究 9 一些其它的方法 除了是对上述几类 工作的发展外 还有Simon的定性因果法 Yip的定性动力学分析方法 Weld的复合透视法 Ishida关于相平面中的线性系统的定性行为的研究 Wong对于优先关系和单调关系的研究 Davis Reiter de Kleer等人的定性故障诊断的研究 10 17 Nilson对定性运动学的研究 等 等 4 不一而论 2 2 现存的现存的 AI 中的定性推理的主要代表性方法的代数结构中的定性推理的主要代表性方法的代数结构 我们评论的方法是 估计各种理论的代数结构的水平 理论的复杂性水平及求解的效率 三个方面 结论是 1 从代数结构上看 它们或大约在环的水平 5 6 18 或大约接近于域 8 2 从复杂性看 有的以一阶逻辑为演算核心 6 19 有的大约以实数域作为核心 8 3 从求 解效率看 最坏情况大都倾向于到指数界 因为有些理论的推理结果的数目就是类似指数 方式的 5 20 平均情况时好时坏 常在多项式界 2 2 1 定性模拟定性模拟 QSIM Kuipers的 5 是原始文献 这个方法是近年来最受重视的方法 许多工作都是对 5 的扩 充和完善而来的 21 27 12 年的历史证明 单纯定性推理会引起较大的不确定性或不真实解 5 12 27 加入定量运算 22 或定性化的定量运算 21 27 可以弥补其不足 5 中 QSIM 的数学结构为 1 初始元素 由实函数抽象来的定性函数 通常按实函数的单调性区间逐段描述 2 演算关系 由通常意义下的 并结合一定的逻辑演算 3 推理规则 类似 高于 一阶逻辑 大体相当于 高于 环 2 就其本义 是要解决分段单调曲线间的代数演算 其代数结构大体在 高于 环的水平 演算复杂性大约类似一阶逻辑 计算时间最坏情况倾向于到指数界 因为推理结果的数目最 多为指数形式的 其改进的代表工作 20 引入了高阶导数 21 加强了求解结果的精确性 加入曲线的 二次导数即曲率的信息 22 中加入定量方法 形成混合结构 使其除了保持原有的能力 外 还能进行量化推理及稳定性分析等 27 提出半定量微分方程法 它使用 定性的 单 调函数限制 下的 数值区间 函数行为描述 来进行推理 这些工作都增加了计算复杂 性 基本数学结构没有重大变化 都达不到域具有的良好性质 2 2 2 定性过程定性过程 QP Forbus的原始论文为 6 由于对复杂情况的处理不很成功 后继工作不多 28 QP 的数学结构为 1 初始元素 逻辑变量 类似二值逻辑 实数 2 演算关系 一阶谓词逻辑 并结合一些很弱的已逻辑化的数量演算关系 3 推理规则 类似一阶逻辑 大体相当于环 就其本义 是要机械化 独立机构假设 人的定性推理能力 但由于其过分接近于一阶 逻辑的一种扩充 导致表示能力过弱 参见G del不完全性定理 29 及Chaitin的离散公理系统 的信息量研究 30 31 其代数结构大体在环的水平 计算时间最坏情况倾向于到指数界 因为推理过程的太逻辑化 由于过分排斥定量信息 对于复杂系统尚未看到明显的应用前景 因而后继工作不多 28 2 2 3 透视法 定性方程法 透视法 定性方程法 J de Kleer在 7 中建立了以汇流 confluences 为核心思想的 主要用于微分方程的定 性化及其求解的方法 其基本方法是把单调区间上的实数变量定性化 即分成几个定性值加 以表达 并将原方程定性 变化方向 化形成 定性方程 后继工作不多 32 透视法的数学结构为 1 初始元素 定性变量 可取有限个定性值 类似于多值逻辑中的变量 2 演算关系 定性加法 乘法等 实质上是变量的变化方向的判断 显然有时得不到有 意义的判断 如对于定性加法 两个定性变量的取值一个为正 另一个为负时 3 推理规则 类似于整数环 就其本义 是把原实数轴分成几个区间 类似多值逻辑化 然后进行整个系统中的变 量的变化推断 类似多值逻辑演算 其代数结构大体在环的水平 计算时间最坏情况倾向 于到指数界 因为推理过程及其结果的数目的组合状态较多 相比定性过程QP 二值逻辑 而言 表达能力要强得多 内在原因见Chaitin的离散公理系统的信息量研究 30 31 2 2 4 定性定量推理的 结合 合并 定性定量推理的 结合 合并 Williams 的获奖论文 8 比较成功地进行了定性定量推理的 合并 它把定量 实数 域 和定性 接近一个域 合并在一起 具有较高的理论价值 十分有助于看透定性推理的 3 数学本质 由于其代数结构水平较高 8 的能力是较强的 关于推理时间 8 没有太多的 研究 相应地 Meiri 的 19 在时间推理中 将时间点和时间区间加以二值逻辑化的描述 在一 定程度上实现了定性定量推理的结合 但由于其完全地是一阶逻辑的扩充 故 19 的能力是 较弱的 并且推理时间也较长 2 2 5 第一原理的定性推理 故障诊断 第一原理的定性推理 故障诊断 10 17 Reiter等人提出了基于 第一原理 利用系统的结构和行为 的定性的故障诊断方法 12 这是一种 2 步诊断法 第一步给出可能的候选解 12 第二步通过增加测量来逐步找到真的 故障元 10 11 14 17 第一步用一阶二值逻辑来描述系统的拓扑结构 并结合输入 输出值 通过归结算法产生候选诊断 求解的方法是采用各种 归结算法 这是一种比较标准的 一 阶谓词演算 第二步根据候选诊断 形成合适的测量点 逐次归结以找到真实故障元件 这类方法的相近工作不少 有 J de Kleer 的 11 13 R Davis 的 15 我们详细地研究过这类方法 见 1994 年的 10 1997 年的 17 发现在优化测量点时 不使用定量信息 系统拓扑结构对不同测量点效果的影响 元件的先验故障率 找不到优 化的测量点 经过一系列的努力和失败后 迫使我们使用了一些定量化的信息 实际上 J de Kleer 1990 年的工作也使用了定量化信息 11 对这一具体的定性推理方法的深入研究 使 我们及时认识到单纯定性推理在实用中的局限性 如同后来Kuipers 1997 年 22 2000 年 27 以及其他人的关于定性推理的认识类似 2 2 6 第一原理的定性推理 故障诊断 第一原理的定性推理 故障诊断 10 17 Williams等人认为 定性推理的核心是 发展关于科学家工程师以及常人的下述的核心 技能的计算理论 即他们的假设 验证 预言 创造 优化 诊断和维修物理机构的能力 1 p2 这实际上是从外部功能角度的描述 显然 对照 34 可知 这在很大程度上是对人类右半脑 能力的模拟 H A Simon等人 9 中认为 定性推理的数学本质是 研究关于系统在单调或 拓扑变换下保持不变的系统性质 这一观点很好的提炼了现有的定性推理方法的数学特性 这说明 几何曲线 能力是定性推理的本质 它主要是右半脑的功能 33 3 我们对于定性推理的看法我们对于定性推理的看法 3 1 定性推理的能力与公理系统的信息复杂性定性推理的能力与公理系统的信息复杂性 Chaitin定理的部分内容简介 30 31 直观地说 1 每一个形式系统有一个特定的信息 量CT 凡复杂性高于CT的命题不能在该形式系统内证明 2 对于复杂性低于CT的命题 的证明 公理的复杂性高 则证明的过程就简单 反之 如果公理的复杂性低 证明的过程 就复杂 甚至这种复杂性超过 可计算函数 的复杂性 一般认为 Chaitin定理是G del不 完全性定理 29 的信息论形态下的具体化 是关于形式系统 能行的可机械推理的系统 能 力的重要结果 这就是说 推理系统的公理信息复杂性水平决定了该系统的能力 Chaitin的观点已被十 4 几年的定性推理的研究史所证明 凡是能力弱的系统 都表现为公理系统的信息复杂性较低 即系统中的变量的状态数的数目及公理的信息量的偏低 具体些 定性过程理论QP 6 很接近 一阶二值谓词逻辑 如同Meiri的 19 是能力最低的定性推理理论 但它们很容易在数字机 上实现 透视法 定性方程 7 类似一阶多值逻辑 或不到整数环 该系统的信息量要比定 性过程理论QP大的多 能力居中 而定型模拟QSIM 5 能力较强 该系统的信息量不到整数 环系统的信息量 由于推理规则确定 不象定性过程理论QP含有较明显的不确定推理 因而能力最强 表现为后继工作最多 如上所述 这不是偶然的 这段历史已证明了 Kolmogorov 34 Chaitin 30 31 等人工作的深远意义 3 2 定性推理的生理背景定性推理的生理背景 Sperry 等人的分离大脑半球的结果 1981 年Nobel生理及医学奖 简介 33 大脑 左半球同抽象思维 象征性关系和对细节的逻辑分析有关 它具有语言 包括书 写语言 的 理念的 分析的 连续的和计算的能力 它能说 写 和进行数学计算 在一 般功能方面它主要是分析 犹如计算机一样 右半球则与知觉和空间有关 处理单项的 事物而不是数理的排列 它具有音乐的 绘画的 综合的 整体性和几何 空间的鉴别能力 右半球的特征事实上完全是非语言的 非数学的 非连续的 它们主要地是空间的和想象 的 类似的地方可以是 一幅画或智力的想象相当于一千个词 这些实例包括 辨认面貌 在大的空间画面安排图案 从一小段圆弧判断整个圆 辨认和回忆难以描述的形状 作智力 的空间转换 辨别音弦 根据积木块的大小和形状分类 从各部分的聚集中觉察整体 直觉 的感觉及几何原理的理解 33 按照我们看法 35 36 左半脑的能力为处理离散 连续的信息 其复杂性为 自然数 基 数或复杂性为a 实数 基数或复杂性为c 右半脑的能力为 几何曲线 基数或 复杂性为f 以及更高 基数或复杂性为h 从定性推理的基本目的看 1 它们主要是对右 半脑的某些能力的描述或机器化 我们推断 定性推理的数学提炼有助于纯数学的跨复杂性 层次的大发展 3 3 定性推理的发展定性推理的发展 f 数学 或以 一般的几何曲线 为元素的数学数学 或以 一般的几何曲线 为元素的数学 现存的数学几乎都是以 自然数 包括一阶谓词逻辑 它们的二值 多值是对自然数 的进一步的限制 实数 为基本元素的 由上可知 它们大体上是对左半脑能力的描述 或机器化 而定性推理的基本目标与右半脑有更多的联系 因此应该是以 一般的几何曲线 为元素的推理体系 这是对 Simon 等人 9 的观点的继承和进一步的具体化 现有的定性推 理只是在很限制的情况下 初步探讨了这种实现 由于数字计算机的复杂性不超出 a 因此采用数字计算机来演算定性推理 往往会遇到 较高的复杂性 这是 Chaitin 定理的必然结果 因此有以下的观点 我们的结论我们的结论 1 人脑的定性推理能力是很复杂和很强大的 人的面孔识别对人很容易 对数字计 算机很难 这说明人脑的能力比数字机强的多 且人脑的高层次计算是定性定量合一的 定 量在定性的基础上建立 33 37 2 数字计算机 大体上为大脑左半球的抽象思维的模拟 上的定性定量推理注定不 5 能完全模拟人的定性推理能力 大脑右半球的形象思维 直觉等能力 因此一个在数字计 算机上可有效实现的定性定量推理算法 应该与专家系统类似 带有明显的领域特征 不能 追求一般的有效的定性定量推理方法 3 发展 f 复杂性层次上的计算工具 如几何光学计算机 才能比较有效地实现人的 某些定性推理能力 另外量子场计算机或生物计算机 也可能成为 定性定量推理机 本 文工作的目的 尤其在于呼吁人们重视比数字计算机能力更强的计算机的现实的研究 尽管 我国专家在 38 中已初步提出这方面的设想 但一直未见比较系统的工作 参考文献 五号 黑体 参考文献 五号 黑体 1 B C Williams et al Qualitative reasoning about physical system Artificial Intelligence 1991 51 1 9 2 中国大百科全书 数学 北京 中国大百科全书出版社 1988 3 戴汝为 人工智能发展的几个问题 模式识别与人工智能 1992 5 1 69 78 4 石纯一 陈见 等 定性推理进展 模式识别与人工智能 1993 6 2 121 126 5 B J Kuipers Qualitative simulation Artificial Intelligence 1986 29 289 338 6 K D Forbus Qualitative process theory Artificial Intelligence 1984 24 85 168 7 J de Kleer et al A qualitative physics based on confluence Artificial Intelligence 1984 24 7 83 8 B C Williams A theory of interactions Artificial Intelligence 1991 51 39 94 9 J Kalagnanam H A Simon et al The mathematical based for qualitative reasoning IEEE Expert 1991 6 2 11 19 10 Lin Kong Yuan Yang Zheng Ling Using structure information to guide diagnosis Transactions of Tianjin University 1997 3 1 48 53 11 J De Kleer Using crude probability estimates to guide diagnosis Artificial Intelligence 1990 45 381 391 12 R Reiter A theory of diagnosis from first principles Artificial Intelligence 1987 32 57 95 13 J De Kleer Diagnosing multiple faults Artificial Intelligence 1987 32 97 130 14 M R Genesereth The use of design descriptions in automated diagnosis Artificial Intelligence 1984 23 411 436 15 R Davis Diagnosing reasoning based on structure and behavior Artificial Intelligence 1984 24 347 410 16 R Davis Retrospective on Diagnosing reasoning based on structure and behavior Artificial Intelligence 1993 59 149 157 17 林孔元 杨正瓴 模型故障诊断中测量点优选的一类期望熵法 天津大学学报 1994 27 4 398 402 18 B J Kuipers Reasoning with qualitative models Artificial Intelligence 1993 59 125 131 19 I Meiri Combining qualitative and quantitative constraints in temporal reasoning Artificial Intelligence 1996 87 343 385 20 B J Kuipers et al High order derivative constrains in qualitative simulation Artificial Intelligence 1991 51 343 386 21 A Hossain et al An extension of QSIM with qualitative curvature Artificial Intelligence 1997 96 303 350 22 D Berleant et al Qualitative and quantitative simulation Artificial Intelligence 1997 95 215 155 23 B J Kuipers Reasoning with qualitative models Artificial Intelligence 1993 59 125 131 24 B J Kuipers Qualitative simulation then and now Artificial Intelligence 1993 59 133 140 25 O Dordan Mathematical problems arising in quantitative simulation Artificial Intelligence 1992 55 61 86 26 A C C Say Quantitative system identification Artificial Intelligence 1996 83 75 141 27 H Kay B Rinner B Kuipers Se