人工智能哲学

我们来看看这个求解简单代数方程的问题：

$$
\mathbf { A X } + \mathbf { B } = \mathbf { C X } + \mathbf { D }
$$

其检验是将解定义为任一形式如X=E的表达式，使 $\mathbf { A } \mathbf { E } + \mathbf { B } = \mathbf { C } \mathbf { E } + \mathbf { D } ,$ 当然，我们可以用无论什么过程作为生成程序，由该过程得出一些数字，然后将这些数字代入后一方程进行检验。我们不会把这种过程叫做智能生成程序。

换一种方式，我们可以采用一些利用这个事实的生成程序：在不改变原方程的解的情况下，可以对原方程进行修正——在两边加或减相等的量，或用同样的量乘或除两边。当然，我们还可以得到更多的指导生成程序的信息，其做法是将原表达式与解的形式加以比较，在方程中精确地作出使解保持不变的一些改变，与此同时使方程变成所希望的形式。这种生成程序会注意到原方程的右边有一个多余的CX，将它从两边减去，再将一些项合并。接下来它会注意到左边有一个多余的B，于是减掉它。最后，它可以用除法将左边多余的系数(A-C)去掉。

这一过程表现出相当高的智能，这样，生成程序就通过它产生出相继的符号结构，每一结构都是通过对前一结构的修正获得的，而修正的目的是在保持解的其他条件不变的情况下，减少输入结构形式与检验表达形式之间的差异。

这个简单例子已经说明了不少以智能方式做问题求解的符号系统所采用的主要机制。首先，每个后继表达式都不是独立生成的，而是通过修正以前产生的表达式而产生的。第二，这些修正不是杂乱无章的，而是依赖于两种信息。它们依赖于在整个这类代数问题中保持不变的信息，而这些信息已被植入生成程序本身的结构中：对表达式的所有修正必须使方程的解保持不变。它们也依赖于每一步中的变化信息：测出当前表达式与期望表达式之间在形式上仍存在的差异。实际上，生成程序本身含有该解必须满足的一些检验，所以不满足这些检验的表达式是决不会生成的。对第一种信息的使用保证了在所有可能存在的表达式中，实际生成的只是一个很小的子集合，同时该子集合又不会遗漏解的表达式。使用第二种信息则是运用简单形式的手段目的分析方法得出搜索方向，通过一系列近似形式，达到所期望的解。

人工智能哲学

132

要问引导搜索的信息是从哪里来的，这没有什么神秘。我们不必追随柏拉图，把一个已经知道解的“以前的生存”赋予符号系统。一个适度复杂的生成程序检验系统不必求助于灵魂转世，就能达到目的。

搜索树以简单的代数问题作为搜索的例子看起来也许是不大常见的，甚至有点反常。它显然不是试错式搜索，因为虽然有一些试探，但却没有任何错误。我们更习惯于把问题求解搜索看作生成枝叉繁多的树，作为部分解，它们具有这种可能性：在得出一个解之前，会长出数以千计的、甚至数以百万计的分支来。这样，如果生成程序从它产生的每一个表达式中造出B个新的分支，那么这棵树就会长出B个分枝，D是它的深度。对代数问题而言，这棵生长的树有其特殊性，那就是它的分支数B等于1。

国际象棋程序一般会长成庞大的搜索树，在某些情况下，其分支数目多达百万以上。这个例子虽然可用来说明我们关于树搜索的观点，但是应该看到，国际象棋中的搜索目的不是生成拟议中的解，而是对解进行评价(作检验)。研究弈棋程序的路线之一，已集中在改进棋盘表述方式上，以及改进在其上走子的过程，以便提高搜索速度，使搜索更大的树成为可能。不难看出，该方向的基本原理为：动态搜索越深，对其结果的评价也就越准确。而另一方面，又有充分的经验证据表明：最高水平的人类棋手—大师们，极少开发出超过一百个分支的搜索树。这种经济性的取得，主要不是因为搜索的深度不及国际象棋程序，而是每一节点上的分支非常稀少，并且有选择性。在不致造成评价失真的情况下，要做到这一点，只能是将更多的选择性植入生成程序本身，这样，它就可以只选择生成那些极有可能提供对阵势来说有重要参考价值的信息的分支。

上述讨论造成了听上去有些自相矛盾的结论：搜索，亦即相继生成潜在解结构，是符号系统在问题求解中行使智能的基本方面，但是它所表现出的智能的多少，却不是由搜索的多少来衡量的。一个问题成其为问题，并不是该问题的解需要进行大量的搜索，而是，如果不应用必要的智能水平的话，就需要进行大量的搜索。当致力于解决一个问题的符号系统对它要做的事情有充分的了解时，就会简捷地径直向它的目标前进；但是在进入未知领域时，它的知识一旦变得不够用了，在重新找到它的道路之前，会面临进行大量搜索的威胁。

5 作为经验探索的计算机科学：符号和搜索

133

在生成问题解答的每一个方案中，都存在着搜索树指数激增的可能性，这种情况警告我们，在补偿生成程序的无知和选择能力缺乏时不要依赖计算机的蛮力，哪怕是最大、最快的计算机。在某些人的胸中时而还会燃起这种希望：可以找到足够快的、并且充分巧妙地编程的计算机让它们通过蛮力搜索而高明地下棋。还未曾听说过在弈棋理论中能完全排除这种可能性。然而，关于规模相当大的树中的搜索处理的经验研究并未取得显著成果，这使我们看到，这一研究方向的前途远不如当初国际象棋首选为恰当的人工智能任务时显得那么光明。这一点应当看作是国际象棋程序研究方面取得的重要经验发现之一。

智能的形式因而，智能的任务就是防止搜索中始终存在的由指数激增造成的威胁。这一点如何才能实现呢？第一种途径是将选择性植入生成程序，代数的例子已对此作出了说明，同时只为后继分析生成“似平合理”走步的国际象棋程序也对此作出了说明，即只生成保证是解的、或是沿着通向解的路径的结构。这种做法的结果通常可以降低分支的速度，而不能完全杜绝分支。除了像代数例子那种例外地高结构化的情况而外，最终的指数激增是难以避免的，只不过是推迟它的到来而已。所以智能系统一般必须以别的使用信息引导搜索的技术来增补它的解生成程序的选择性。

在处理各种各样任务环境中的树搜索方面已积累了20年的经验，这些经验已经产生出一小套一般性技术，它们成为当今每一位人工智能研究者的知识的组成部分。这些技术已在许多一般性著作中作过介绍，如尼尔森的著作(Nilsson1971)，所以我们可以在这里对它们作出十分简单的概括。

人工智能哲学

134

串行启发式搜索中的基本问题总是：下一步要做什么？在树搜索中该问题又分为两个方面：(1)下一步搜索从树的哪个节点开始，(2)从该节点起应取什么方向？有助于回答第一个问题的信息，可以解释为对不同节点与目标的相对距离的测定。佳者优先搜索要求从那个看来离目标最近的节点开始下一步搜索。获得有助于回答第二个问题的信息，即在什么方向上进行搜索，其方法正如代数例子所表明的那样，常常是测出当前节点结构与由对解的检验所描述的目标结构之间的特定差异，并选择那些对减少这些特殊类型差异有重要作用的行动。这就是称为手段目的分析的技术，它在一般问题求解程序的结构中起着主导作用。

经验研究作为AI研究中的一般思想源泉的重要性，可以通过回顾佳者优先搜索和手段目的分析这两个主导思想的历史，在大量问题求解程序中清楚地得到证明。佳者优先搜索的雏形在1955年的逻辑理论家程序中已经出现，虽然当时没有叫这个名字。体现了手段目的分析的一般问题求解程序，约在1957年出现，但是它是与改进的深度优先搜索相结合的，而不是与佳者优先搜索相结合。出于节约内存的目的，国际象棋程序一般是与深度优先搜索联姻的，大约在1958年之后，增补了强有力的α-β修剪过程。这些技术中的每一项都数度东山再起，直到60年代中后期，一直很难看到根据这些概念对问题求解所作的一般性的、与任务分离的理论探讨。它们从数学理论中得到的形式依据，总计起来为数也不多：一些关于搜索还原的定理，这些定理可从使用α-β启发法中获得；两个关于最短路径搜索的定理(尼尔森曾提到过，Nilsson1971)；以及最近才出现的一些带有概率论评价功能的佳者优先搜索定理。

“弱”方法与“强”方法我们一直在讨论的这些技术都是用于控制指数扩张的，而不是阻止指数扩张。因此，把它们称做“弱”方法是恰如其分的——在问题空间实际含有的符号系统知识或结构数量不足以保证完全避免搜索时所使用的方法。对比一下高结构化情境与低结构化情境的不同是有益的，前者可以用公式表达为比如线性规划问题，后者则是像旅行售货员问题或时间调度问题那样的组合问题。（这里“低结构化”是指与问题空间结构相关的理论是不充分的或不存在的。）

5 作为经验探索的计算机科学：符号和搜索

135

在解决线性规划问题时，也许需要做数量可观的计算，但是这种搜索不出现分支，每一步都沿着通向解的路线行进。在解决组合问题或是证明定理时，树搜索就难以避免了，而成功则有赖于我们已描述过的那类启发式搜索方法。

AI问题求解研究的趋势并非全都依照我们以上概述的途径发展。对定理证明系统的研究就是一个观点有所不同的例子。在这里，从数学和逻辑引进的思想已对探索方向产生出强烈的影响。例如，在完备性得不到证明的情况下，就不能使用启发法(这有一点讽刺的意味，因为就我们所知，大多数有价值的数学系统是不可判定的)。由于对佳者优先搜索启发法或对多种选择生成程序来说，完备性特性是很难得到证明的，这一必备条件就具有相当的约束力。当定理证明程序因它们的搜索树组合激增而一再显得无能为力的时候，人们开始把目光投向有选择性的启发法了，在很多情况下，这种方法原来不过是对一般问题求解程序中所使用的启发法的模拟。例如，支持集启发法就是一种适合于分解定理证明环境的反向工作形式。

经验总结 至此，我们已介绍了第二个定性结构定律的工作方式，这一定律表明物理符号系统是通过启发式搜索来解题的。除此之外，我们还考察了启发式搜索的某些附带特征，特别是它始终面临的来自搜索树指数激增的威胁，以及为了避开这种威胁而采用的某些手段。在有效的启发式搜索是怎样作为问题求解机制的问题上，看法产生了分歧，而看法的不同取决于涉及什么任务域，以及采纳什么样的恰当性判据。降低愿望水平可以使成功得到保证，反之，提高愿望水平则会招致失败。其证据也许可以大致归结如下：几乎没有什么程序是在“专家”的职业水平上解决问题的。最有名的例外情况要算萨谬尔的检查者程序和费根鲍姆及莱德伯格的DENDRAL系统了，但是我们也可以指出，有许多启发式搜索程序用于像时间调度和整体程序设计那样的运筹学问题领域。在许多领域中，程序的性能达到相当高的业余水平，如国际象棋、某些定理证明领域、类型众多的游戏和难题。具有复杂感知“前端”的程序，如视觉识别程序、口语理解程序、必须在实际时空中运动自如的机器人，距离人类水平还相当远。然而，在解决这些困难任务方面，已经取得了令人印象深刻的进步，并积累了大量的经验。

人工智能哲学

136

我们没有对那些已经出现的特殊性能模式作深入的理论解释。然而，我们可以在经验的基础上得出两点结论。第一，从我们已经掌握的人类专家在完成像国际象棋这样的任务时的表现来看，很有可能是，任何可与这种表现相匹敌的系统，都必须存取其存储器中存储的大量语义信息。第二，人类完成任务时在丰富的感知组成方面的优势，可部分地归因于人类眼和耳的那种生而有之的特殊目的的并行处理结构。

总之，性能质量必然依赖于问题的领域和处理它们时所用符号系统这两方面的特征。就我们感兴趣的大多数实际生活领域而言，至今尚未证明这种领域结构已简单到足以产生出关于复杂性的定理，或是不以经验的方式向我们说明，大量现实世界的问题是如何与我们用以解决它们的符号系统的能力发生关系的。这种情况也许会改变，但是在它改变之前，我们必须依赖于经验探究，通过使用我们知道如何建立的最佳问题求解程序，将经验探究作为关于问题难点的大小和特征知识的主要源泉。即使在高结构化的领域像线性规划中，理论在加强启发法最强有力的解题算法的基础一方面所起的作用，也远比在提供对复杂性的深层分析方面所起的作用大得多。

毋需大量搜索的智能

我们对智能进行分析时，将智能与抽取和使用有关问题空间结构的信息的能力等同起来，目的是使一个问题的解能够尽可能快和尽可能直接地生成。那么，为改善符号系统解题能力而建立的新方向，也可以与抽取和使用信息的新方法等同起来。至少有三种这样的方法得到确认。

5作为经验探索的计算机科学：符号和搜索

137

信息的非局部用法首先，已有好几位研究者注意到，在树搜索过程中收集的信息通常仅仅以局部方式使用，这样有助于在生成这一信息的特定节点上作决策。关于国际象棋阵势的信息，如果是由对后持续的次级树的动态分析获得的，通常只用于该阵势的评价，而不用于评价别的可能含有许多相同特点的阵势。所以一些完全相同的事实不得不在这一搜索树的不同节点上重复去发现。简单地把信息从它出现的语境中抽取出来，作为一般形式来使用，并不能解决这一问题，因为该信息也可能只在一个有限的语境范围中有效。近年来，在把信息从它的原始语境传递到其他恰当语境这方面，已做了一些开拓性的工作。尽管评价这一思想的力度，甚或确切说明如何实现它，还为时过早，这一思想的前景却不可小看。伯利纳(Berliner1975)所沿袭的重要研究路线，就是使用因果分析确定出一条特殊信息的有效范围。这样，如果可以从一个国际象棋阵势的破绽追溯到造成它的那一走法，那么可以预料，同样的走法也会在别的阵势中留下同样的破绽。

HEARSAY口语理解系统采用了另一种使信息在全局有效的方法。该系统寻求的是通过在多个不同层次上实行并行搜索来识别语音串，这些层次有：音位的、词汇的、句法的和语义的。每个这样的搜索都提出一些假设，并对其作出评价，这时它把它获得的信息提供给一块公共的“黑板”，所有资源都可以阅读这块黑板。例如，这一共享的信息可以用来消去假设，甚至是整个类别的假设，否则的话，这些假设还得由一个过程来搜索。这样，就增加了我们非局部地使用树搜索信息的能力，也为提高问题求解系统的智能提供了保证。

语义识别系统 第二种提高智能的有效方式是向符号系统就其所涉及的任务域提供大量语义信息。例如，对国际象棋大师技巧所作的经验研究表明，大师的技巧主要来源于所存储的信息，这些信息有的能使他识别出棋盘上大量的特定特点和特点的模式，有的利用这种识别，提出与所识别特点相适合的行动。当然，国际象棋程序几乎从一开始就吸收了这种一般性思想。新的东西则是在数量上对这种模式的了解，以及了解可能是大师级表演所必须存储的那些联想信息，这种信息大约有5万个。

人工智能哲学

138

识别之所以可能取代搜索，是因为特殊的模式，特别是稀有模式，可能包含大量信息，只要它是与问题空间结构密切联系的。当结构“不规则”，并且不服从于简单的数学描述时，大量相关模式的知识就有可能成为智能行为的关键。任一特殊任务域的情况是否如此还是一个问题，要解决它，用经验调查比用理论更容易。我们关于符号系统的经验虽然被赋予丰富的语义信息，并被赋予很多存取这些信息的模式识别能力，然而这种经验仍然是极为有限的。

以上讨论特别谈及了与识别系统有联系的语义信息。当然，在语义信息加工和语义存储的组织方面还有整整一个AI研究的大领域，这不在本文讨论的论题范围之中。

选择恰当的表述方式 第三条探索路线涉及是否能够通过选择恰当的问题空间来减少搜索或避免搜索。有一个有代表性的例子可生动地说明这种可能性，即残缺国际象棋棋盘问题。标准的国际象棋棋盘有64个方格，每一个1乘2的长方形薄片恰好覆盖两格，用32个薄片正好能将整个棋盘覆盖。现在，假定将棋盘对角线上相对两角的方格割去，剩下总共62个方格，这个残缺的棋盘能够正好用31个薄片覆盖吗？以(一丝不苟的)极大耐心，把各种可能的排列形式都试一番，可以证明这种覆盖是不能实现的。对于耐心较差而智慧较高的人来说，可采用另一种方法，由观察了解到棋盘对角线上相对两角方格的颜色是相同的。所以在残缺的棋盘上，一种颜色的方格比另一种颜色的少两个。但是每个薄片所覆盖的都是一种颜色和另一种颜色的方格各一个，任何一组薄片所覆盖的两种颜色的方格数目必然是相等的，所以这个问题的解不存在。一个符号系统在解决该问题时，怎样才能发现这种简明的归纳论证，用以替代在所有可能的覆盖方式中进行搜索的徒劳尝试呢？我们将给找到解的系统在智能上判高分。

5 作为经验探索的计算机科学：符号和搜索

139

然而，在提出这些问题时，我们也许并不是在避开搜索过程。我们只是把搜索从可能问题解答空间移置到了可能表述空间。无论如何，在问题求解研究领域中，从一种表述方式转移到另一种表述方式，以及发现和评价这些表述方式的整个过程，基本上是一块尚未开发的土地。支配表述方式的定性结构定律还有待于发现。几乎可以肯定，在未来的10)年中，搜索它们的工作将受到极大的关注。

结 论

以上是我们就符号系统和智能所作的论述。从柏拉图的《美诺篇》到今天，走过了一条漫长的道路，然而或许令人鼓舞的是，在这条路途上的大部分进展是进入20世纪后取得的，而其中很大的部分又是在20)世纪中叶以后取得的。思维在被现代形式逻辑解释为形式标记的处理之前，一直是不可捉摸和难以名状的东西。在计算机教我们知道符号如何能由机器加工之前，它看来主要仍是存在于柏拉图的理念王国里，或是在同样模糊不清的人类心灵空间里。本世纪中叶，在这些发展处于转折点上的时候，图灵作出了伟大的贡献一—将现代逻辑引入了计算机。

物理符号系统对逻辑和计算机的研究已向我们揭示出：智能存在于物理符号系统之中。这是计算机科学最基本的定性结构定律。

符号系统是许多模式和过程的集合体，而后者能够产生前者，并破坏和修正前者。模式最重要的特性是，它们能指称对象、过程或其他模式，而当它们指称过程时，它们就能得到解释。解释的意思就是完成被指称的过程。在我们所了解的符号系统中，有两类的意义最为重大，即人类和计算机。

正如前面指出的那样，我们目前对符号系统的理解是经历了一系列阶段才增长起来的。形式逻辑使我们熟悉了符号，把符号看作思维的原材料，以句法方式来处理它们，同时也使我们熟悉了根据仔细定义的形式过程来处理符号的观念。图灵机真正以机器的方式完成了对符号的句法加工，同时也证实了严格定义的符号系统的潜在普适性。计算机的存储程序思想再次证实了已经隐含在图灵机中的符号的可解释性。表处理把符号的指称能力推到最前面，同时它定义符号加工的方式可使其独立于基础层次物质机器固定结构。到1956年时，所有这些思想都已完成，同时也获得了实现它们的硬件。对于符号系统的智能—这个人工智能的主题——的研究可以开始了。

人工智能哲学

140

启发式搜索 AI的第二个定性结构定律是，符号系统是通过生成潜在可能的解，并对其进行检验，也就是通过搜索的方式，来解题的。建立符号表达式，对它们进行一系列修正，直到它们满足解的条件，这就是寻找解的一般方式。因而符号系统是通过搜索来解题的。由于它们的资源有限，这一搜索不可能立即全部完成，而必须依次进行。它留给我们的或者是从起点到目标的一条单一路线，或者是在必须修正和退回的情况下由所有这些路线组成一整棵搜索树。

符号系统处于完全混沌的环境时，不可能表现出智能。从一个问题域中抽取出信息，并运用这些信息指导搜索，从而避开错误方向和迁回曲折的分叉，符号系统是通过这种方式来行使智能的。若要使该方法有效，问题域必须包含信息，亦即包含某种程度的秩序和结构。《美诺篇》中的悖论是因注意到信息可以记住而解决的，然而新信息也有可能从符号所指称的区域中抽取出来。在这两种情况下，信息的最终源泉都是任务域。

经验基础人工智能研究关心的是，符号系统为了具有智能行为必须怎样组织。20)年来，这一领域的工作已积累了大量知识，足以写成许多部书(也已经这样做了)，其中大部分知识是以相当具体的经验形式出现的，针对的是特定任务域中特定类别符号系统的行为。然而在这种经验之中，也出现了某些一般性方式，它们超越了任务域和系统，反映出智能及其实现方法的一般特征。

5 作为经验探索的计算机科学：符号和搜索

141