1、Donghua Univ.Donghua Univ.Professor Tao GongCollege of Info S&T2014/09Book: Artificial Immune System Based on Normal Model and Its Applications, Tsinghua University Press, 2011Network Course: http:/ Representation, Search Ch1 Representation, Search and Reasoning of Knowledgeand Reasoning of Knowledg
2、eISCTao GongCollege of Information Science and Technology, DHU2CH1CH1 Representation, Search and Representation, Search and Reasoning of KnowledgeReasoning of KnowledgeConcepts and Designs of Expert SystemsSearch and Reasoning of KnowledgeKnowledge Representation of symbolicismThree Major Groups of
3、AIISC3Nowadays, the major groups of artificial intelligence (AI) include the following three ones:(1)Symbolicism, or called logicism, psychologism, computerism: its principles include the physical symbol system (i.e. symbol operation system) hypothesis and limited rationality principle.(2)Connection
4、ism, or called bionicsism, physiologism: its principles include neural networks, the connection mechanism among the neural networks, and learning algorithms.(3)Actionism, or called evolutionism, cyberneticsism: its principles include cybernetics and sensing-action control system.1 Three Major Groups
5、 of AICh1 Representation, Search & Reasoning of KnowledgeCollege of Information Science and Technology, DHUTao GongISC4 Symbolicism thinks that the AI originated from the mathematical logic.The mathematical logic developed quickly since the end of the 19th century, and it was used to describe the in
6、telligent behaviors since 1930s.After the invention of the computer, the computer was used to implement the logic deduction system. The heuristic program LT logic theorist was one of the typical fruits, and this program proved 38 mathematic theorems. This fact shows that the computer can be used to
7、investigate the thinking process of human beings and simulate their intelligent activity. Another example is the mechanical proving of geometry theorems by Prof. Wenjun Wu, and he won the top science award of China.Heuristic algorithmsExpert systemsKnowledge engineering1.1 Symbolicism1 Three Major G
8、roups of AICollege of Information Science and Technology, DHUTao GongISC5 Connectionism thinks the AI originated from the bionics, especially such as the research on the brain.The typical fruit of connectionism was the brain model (MP model), which was proposed by the physiologist McCulloch and the
9、mathematical logician Pitts in 1943. This model opened a new path of simulating the structure and functions of the brain with electric devices.MP modelperceptronHopfield neural networkBP algorithm1.2 Connectionism1 Three Major Groups of AICollege of Information Science and Technology, DHUTao GongISC
10、61.3 Actionism1 Three Major Groups of AICollege of Information Science and Technology, DHUTao Gong Actionism thinks that the AI originated from the cybernetics.The idea of cybernetics was popular from 1940s to 1950s, and this cybernetics was interesting for early researches (e.g. Wiener, Macollough
11、and Xuesen Qian) on artificial intelligence.From 1960s to 1970s, with the development of these control systems, the intelligent control and the intelligent robots were proposed. In 1980s, the intelligent control systems and the intelligent robots were designed and developed.The first typical fruit o
12、f actionism was the six-legged walking robot, which was designed by Brooks to simulate the insect behaviors with the control system based on the sensing-behavior pattern.The three major groups of AI will coexist and cooperate with each other for a long time by fusion and integration.ISC7 With on the
13、 symbols and logics, the traditional problem solving of AI is based on the knowledge representation and reasoning. Each knowledge-symbol-based intelligent system uses a searching procedure to find the solution for the problem. However, before the searching procedure, some knowledge representation ap
14、proaches should be utilized to represent the problem. These problem-representation approaches include the state space, the problem reduction, and the predicate formula etc. The right selection of suitable knowledge representation is important to increase the problem-solving efficiency of AI. The kno
15、wledge representation approaches use graphs, formulas, structures and statements etc.2 Knowledge RepresentationCh1 Representation, Search & Reasoning of KnowledgeCollege of Information Science and Technology, DHUTao GongISC8 The state space approach is a solution-space-based problem representation a
16、nd solving approach, which utilizes the states and the operators. When the knowledge is represented with the state space graph, the initial state is changed with one by one operator. The experimental series of the operators is built step by step, until the target state is attained. Because luxuriant
17、 nodes should be extended with the state space approach and this easily causes the combination explosion, this approach is only suitable for representing simple problems. The state is an ordered subset of the variables q0, q1, , qn , which describes the difference among the different objects of the
18、same class. Its vector is Q=q0,q1,qnT Here, the element qi (i=0,1,n) represents the state variable.2.1 State Space Approach2 Knowledge RepresentationCollege of Information Science and Technology, DHUTao GongISC9 The demo for solving the problem of the monkey and the banana is shown below. The right
19、text box shows the current state (W,x,Y,z). W denotes the horizontal position of the monkey; x has the value 1 when the monkey is on the box, otherwise x has the value 0; Y represents the horizontal position of the box; z has the value 1 when the monkey gets the banana, otherwise z has the value 0.C
20、ollege of Information Science and Technology, DHUTao Gong2.1 State Space Approach2 Knowledge RepresentationISC10 The problem reduction method is used from the object (the problem to be solved), through the backward inference and a series of transformations, to turn the initial problem into the set o
21、f sub-problems and the set of sub-sub-problems. These transformations end at the basic sub-problem set. The basic sub-problem can be solved directly, so that the initial problem can be solved. This problem-solving approach can be represented with the AND-OR graph. The state space approach is a speci
22、al example for the problem reduction method.2.2 Problem Reduction MethodCollege of Information Science and Technology, DHUTao Gong2 Knowledge RepresentationISC11College of Information Science and Technology, DHUTao Gong2.2 Problem Reduction Method2 Knowledge RepresentationISC12The predicate logic me
23、thod utilizes the appropriate formula of the predicate and one-order predicate calculation, in order to transform the problem solving into the problem proving. Afterwards, the resolution theorems and the resolution inversion are used to prove that a new sentence is derived from the known correct sen
24、tences, so this new sentence is also proved correct. The predicate logic is a kind of formal language, which can make the logical arguments of math symbolic.The predicate logic method is often used with other knowledge representation methods, and it is flexible and convenient to represent more compl
25、ex problems.College of Information Science and Technology, DHUTao Gong2.3 Predicate Logic Method2 Knowledge RepresentationISC13 语义网络是一种结构化表示方法，它由节点和语义网络是一种结构化表示方法，它由节点和弧线或链线组成。节点用于表示物体、概念和状态，弧线或链线组成。节点用于表示物体、概念和状态，弧线用于表示节点间的关系。弧线用于表示节点间的关系。 语义网络的解答是一个经过推理和匹配而得到语义网络的解答是一个经过推理和匹配而得到的具有明确结果的新的语义网络。的具有明
26、确结果的新的语义网络。 语义网络可用于表示多元关系，扩展后可以表语义网络可用于表示多元关系，扩展后可以表示更复杂的问题。示更复杂的问题。2.4 Semantic Network MethodCollege of Information Science and Technology, DHUTao Gong2 Knowledge RepresentationISC14 框架是一种结构化表示方法，是一种表示概念或对象框架是一种结构化表示方法，是一种表示概念或对象的一成不变知识的数据结构。框架通常由指定事物各个方的一成不变知识的数据结构。框架通常由指定事物各个方面的槽组成，每个槽拥有若干个侧面，而每
27、个侧面又可拥面的槽组成，每个槽拥有若干个侧面，而每个侧面又可拥有若干个值。有若干个值。 大多数实用系统必须同时使用许多框架，并可把它们大多数实用系统必须同时使用许多框架，并可把它们联成一个框架系统。框架表示已得到广泛应用，然而并非联成一个框架系统。框架表示已得到广泛应用，然而并非所有问题都可以用框架表示。所有问题都可以用框架表示。 剧本是框架的一种特殊形式，它使用一组槽来描述事剧本是框架的一种特殊形式，它使用一组槽来描述事件的发生序列。剧本表示特别适用于描述顺序性动作或事件的发生序列。剧本表示特别适用于描述顺序性动作或事件，但使用不如框架灵活，因此应用范围也不如框架广泛。件，但使用不如框架灵活
28、，因此应用范围也不如框架广泛。 框架是一种复杂结构的语义网络，因此语义网络推理框架是一种复杂结构的语义网络，因此语义网络推理中的匹配和特性继承在框架系统中也可以实行。此外，框中的匹配和特性继承在框架系统中也可以实行。此外，框架可以在新的情况下推论出未被观察到的事实。架可以在新的情况下推论出未被观察到的事实。2.5 框架和剧本框架和剧本2 符号主义的知识表示符号主义的知识表示College of Information Science and Technology, DHUTao GongISC15 知识的搜索与推理是人工智能研究的另一个核心问题。对知识的搜索与推理是人工智能研究的另一个核心问题
29、。对这一问题的研究曾经十分活跃，而且至今仍不乏高层次这一问题的研究曾经十分活跃，而且至今仍不乏高层次的研究课题。的研究课题。(1)盲目搜索只是穷举，不运用特别信息。盲目搜索包括宽盲目搜索只是穷举，不运用特别信息。盲目搜索包括宽度优先搜索、深度优先搜索和等代价搜索等。度优先搜索、深度优先搜索和等代价搜索等。(2)启发式搜索主要讨论有序搜索启发式搜索主要讨论有序搜索(或最好优先搜索或最好优先搜索)、最优搜、最优搜索索A*算法和算法和AO*算法。算法。(3)在求解问题时，可把问题表示为一个有待证明的问题或在求解问题时，可把问题表示为一个有待证明的问题或定理，然后用消解原理和消解反演过程来证明。定理，
30、然后用消解原理和消解反演过程来证明。(4)高级求解系统是知识推理和搜索的先进方法，规则演绎高级求解系统是知识推理和搜索的先进方法，规则演绎系统和产生式系统就是两种比较有效的搜索方法。系统和产生式系统就是两种比较有效的搜索方法。(5)系统组织技术将一个大系统或复杂系统中的知识划分为系统组织技术将一个大系统或复杂系统中的知识划分为一组相对独立的模块，然后考虑各子模块间在求解时的一组相对独立的模块，然后考虑各子模块间在求解时的合作问题。合作问题。3 知识的搜索与推理技术知识的搜索与推理技术Ch1 Representation, Search & Reasoning of KnowledgeColle
31、ge of Information Science and Technology, DHUTao GongISC16 A*算法一种有序搜索算法，其特点算法一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有在于对估价函数的定义上。对于一般的有序搜索，总是选择估价函数序搜索，总是选择估价函数 f 值最小的节值最小的节点作为扩展节点。因此，估价函数点作为扩展节点。因此，估价函数 f 是根是根据需要找到一条最小代价路径的观点来估据需要找到一条最小代价路径的观点来估算节点的。可考虑每个节点算节点的。可考虑每个节点 n 的估价函数的估价函数值为两个分量：从起始节点到节点值为两个分量：从起始节点到
32、节点 n 的代的代价以及从节点价以及从节点 n 到达目标节点的代价。到达目标节点的代价。3.1 A*算法算法3 知识的搜索与推理技术知识的搜索与推理技术College of Information Science and Technology, DHUTao GongISC17 遗传算法是仿真生物遗传学和自然选择机理，通过遗传算法是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索算法，从某种程度上说遗传人工方式所构造的一类搜索算法，从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。算法是对生物进化过程进行的数学方式仿真。Holland在在他的著作他的著作Adaptation
33、in Natural and Artificial Systems首次提出遗传算法，并主要由他和他的学生发展起来的。首次提出遗传算法，并主要由他和他的学生发展起来的。 遗传算法自从遗传算法自从1965年提出以来，在国际上已经形成年提出以来，在国际上已经形成了一个比较活跃的研究领域，已召开了多次比较重要的了一个比较活跃的研究领域，已召开了多次比较重要的国际会议和创办了很多相关的国际刊物。国际会议和创办了很多相关的国际刊物。 遗传算法已用于求解带有应用前景的一些问题，例遗传算法已用于求解带有应用前景的一些问题，例如遗传程序设计、函数优化、排序问题、人工神经网络、如遗传程序设计、函数优化、排序问题、
34、人工神经网络、分类系统、计算机图像处理和机器人运动规划等。分类系统、计算机图像处理和机器人运动规划等。3.2 遗传算法遗传算法3 知识的搜索与推理技术知识的搜索与推理技术College of Information Science and Technology, DHUTao GongISC18 生物种群的生存过程普遍遵循达尔文进化准则，群体中的个生物种群的生存过程普遍遵循达尔文进化准则，群体中的个体根据对环境的适应能力而被大自然所选择或淘汰。进化过程的体根据对环境的适应能力而被大自然所选择或淘汰。进化过程的结果反映在个体的结构上，其染色体包含若干基因，相应的表现结果反映在个体的结构上，其染色
35、体包含若干基因，相应的表现型和基因型的联系体现了个体的外部特性与内部机理间逻辑关系。型和基因型的联系体现了个体的外部特性与内部机理间逻辑关系。通过个体之间的交叉、变异来适应大自然环境。通过个体之间的交叉、变异来适应大自然环境。 遗传算法类似于自然进化，通过作用于染色体上的基因寻找遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问题。与自然界相似，遗传算法对求解问题的好的染色体来求解问题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的
36、染色体有更多评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若干个所求解问的繁殖机会。在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始群体；通过适应度函数给每题的数字编码，即染色体，形成初始群体；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。对这个新种群进行下一轮进化。这就是遗传算法的基本原理。群。对这个新种群进行下一轮
37、进化。这就是遗传算法的基本原理。3.2 遗传算法遗传算法3 知识的搜索与推理技术知识的搜索与推理技术College of Information Science and Technology, DHUTao GongISC19 在谓词公式、某些推理规则以及置换合一等概念的基础在谓词公式、某些推理规则以及置换合一等概念的基础上，能够进一步研究消解原理上，能够进一步研究消解原理(resolution principle)。 消解是一种可用于一定的子句公式的重要推理规则。一消解是一种可用于一定的子句公式的重要推理规则。一个子句定义为由文字的析取组成的公式个子句定义为由文字的析取组成的公式(一个原子公
38、式和原一个原子公式和原子公式的否定叫做文字子公式的否定叫做文字)。当消解可使用时，消解过程被应。当消解可使用时，消解过程被应用于母体子句对，以便产生一个导出子句。例如，如果存在用于母体子句对，以便产生一个导出子句。例如，如果存在某个公理某个公理E1E2和另一公理和另一公理E2E3，那么，那么E1E3在逻辑在逻辑上成立，这就是消解，而上成立，这就是消解，而E1E3称为称为E1E2和和E2E3的的消解式消解式(resolvent)。 任一谓词演算公式可以按照以下九步化成一个子句集任一谓词演算公式可以按照以下九步化成一个子句集：(1) 消去蕴涵符号；消去蕴涵符号；(2) 减少否定符号的辖域；减少否定
39、符号的辖域；(3) 对变量标对变量标准化；准化；(4) 消去存在量词；消去存在量词；(5) 化为前束形；化为前束形；(6) 把母式化成把母式化成合取范式；合取范式；(7) 消去全称量词；消去全称量词；(8) 消去连词符号消去连词符号；(9) 更更换变量名称。换变量名称。3.3 消解原理消解原理3 知识的搜索与推理技术知识的搜索与推理技术College of Information Science and Technology, DHUTao GongISC20 在所有基于规则的系统中，每个在所有基于规则的系统中，每个if可能与某断言可能与某断言(assertion)集中的一个或多个断言匹配。有
40、时把该断言集中的一个或多个断言匹配。有时把该断言集称为工作内存。在许多基于规则的系统中，集称为工作内存。在许多基于规则的系统中，then部分部分用于规定放入工作内存的新断言。这种基于规则的系统用于规定放入工作内存的新断言。这种基于规则的系统称为规则演绎系统称为规则演绎系统(rule based deduction system)。在这。在这种系统中，通常称每个种系统中，通常称每个if部分为前项部分为前项(antecedent)，称每，称每个个then部分为后项部分为后项(consequent)。 有时，有时，then部分用于规定动作，这时，称这种基于部分用于规定动作，这时，称这种基于规则的系统
41、为反应式系统规则的系统为反应式系统(reaction system)或产生式系统或产生式系统(production system)。 在基于规则的系统中，无论是规则演绎系统还是规在基于规则的系统中，无论是规则演绎系统还是规则产生式系统，均有两种推理方式，即正向推理则产生式系统，均有两种推理方式，即正向推理(forward chaining)和逆向推理和逆向推理(backward chaining)。3.4 规则演绎系统规则演绎系统3 知识的搜索与推理技术知识的搜索与推理技术College of Information Science and Technology, DHUTao GongISC
42、21 产生式系统产生式系统(production system)首先是由首先是由Post于于1943年年提出的产生式规则提出的产生式规则(production rule)而得名的，他们用这种而得名的，他们用这种规则对符号串进行置换运算。后来，美国的纽厄尔和西蒙利规则对符号串进行置换运算。后来，美国的纽厄尔和西蒙利用这个原理建立一个人类的认知模型用这个原理建立一个人类的认知模型(1965年年)。同时，斯坦。同时，斯坦福大学利用产生式系统结构设计第一个专家系统福大学利用产生式系统结构设计第一个专家系统DENDRAL。 产生式系统用来描述若干个不同的以一个基本概念为基产生式系统用来描述若干个不同的以
43、一个基本概念为基础的系统，这个基本概念就是产生式规则或产生式条件和操础的系统，这个基本概念就是产生式规则或产生式条件和操作对的概念。在产生式系统中，论域的知识分为两部分：用作对的概念。在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为。生式规则表示推理过程和行为。 产生式系统表达自然直观，便于推理，可进行模块化处产生式系统表达自然直观，便于推理，可进行模块化处理，格式清晰，设计和检测方便，表示灵活，因而曾得到广理，格式清晰，设计和检测方便，表示灵活，因而曾得到广泛应用。不过，
44、产生式系统因求解效率低和无法表示结构性泛应用。不过，产生式系统因求解效率低和无法表示结构性知识，不适用于求解复杂系统。知识，不适用于求解复杂系统。3.5 产生式系统产生式系统3 知识的搜索与推理技术知识的搜索与推理技术College of Information Science and Technology, DHUTao GongISC22 专家系统（专家系统（expert system）已越来越普遍地获得应用，）已越来越普遍地获得应用，其领域要求高度可靠，并具有快速决策和不同功能。其领域要求高度可靠，并具有快速决策和不同功能。 这些功能包括解释、预测、分析、诊断、调试、设计、这些功能包括解
45、释、预测、分析、诊断、调试、设计、规划、诊断、控制、监视、教学、检测、咨询、管理、规划、诊断、控制、监视、教学、检测、咨询、管理、评估和决策支持等。评估和决策支持等。 专家控制系统是一个应用专家系统技术的控制系统，专家控制系统是一个应用专家系统技术的控制系统，也是一个典型的和广泛应用的基于知识的控制系统。也是一个典型的和广泛应用的基于知识的控制系统。 Hayes-Roth等在等在1983年提出专家控制系统，关于专家年提出专家控制系统，关于专家控制系统应用的第一次报导是在控制系统应用的第一次报导是在1984年年用于炼油的用于炼油的分布式实时过程控制系统。分布式实时过程控制系统。 奥斯特洛母等在奥
46、斯特洛母等在1986年发表他们的题为年发表他们的题为“专家控制专家控制”（Expert Control）的论文。）的论文。 4 专家系统专家系统Ch1 Representation, Search & Reasoning of KnowledgeCollege of Information Science and Technology, DHUTao GongISC23 专家：指的是那些对解决专门问题非常熟悉的人们，专家：指的是那些对解决专门问题非常熟悉的人们，他们的这种专门技术通常源于丰富的经验以及他们处理问他们的这种专门技术通常源于丰富的经验以及他们处理问题的详细专业知识。题的详细专业知识
47、。 专家系统尚无统一的定义。专家系统的先行者专家系统尚无统一的定义。专家系统的先行者Feigenbaum曾把专家系统定义为一个智能计算机程序，曾把专家系统定义为一个智能计算机程序，它应用知识和推理过程来求解那些需要大量的人类专家经它应用知识和推理过程来求解那些需要大量的人类专家经验才能解决的难题。验才能解决的难题。 定义定义1 专家系统主要指的是一个智能计算机程序系统，专家系统主要指的是一个智能计算机程序系统，其内部含有大量的某个领域专家水平的知识与经验，能够其内部含有大量的某个领域专家水平的知识与经验，能够利用人类专家的知识和解决问题的经验方法来处理该领域利用人类专家的知识和解决问题的经验方
48、法来处理该领域的高水平难题。专家系统是一种模拟人类专家解决领域问的高水平难题。专家系统是一种模拟人类专家解决领域问题的计算机程序系统。题的计算机程序系统。 专家系统的基本功能：取决于它所含有的知识，因此，专家系统的基本功能：取决于它所含有的知识，因此，有时也把专家系统称为基于知识的系统（有时也把专家系统称为基于知识的系统（knowledge-based system）。）。 4.1 专家系统的概念专家系统的概念4 专家系统专家系统College of Information Science and Technology, DHUTao GongISC24 1. 启发性：专家系统要解决的问题，其
49、结构往往是不启发性：专家系统要解决的问题，其结构往往是不合理的，其问题求解（合理的，其问题求解（problem-solving）知识不仅包括理）知识不仅包括理论知识和常识，而且包括专家本人的启发知识。在问题求论知识和常识，而且包括专家本人的启发知识。在问题求解过程中，专家们应用和组合启发知识（甚至是多种经解过程中，专家们应用和组合启发知识（甚至是多种经验），模仿专家的思维和认知过程。专家系统具有启发性，验），模仿专家的思维和认知过程。专家系统具有启发性，并能够高效和准确地作出推理、判断、决策和结论。并能够高效和准确地作出推理、判断、决策和结论。 2. 透明性透明性: 专家系统能够解释本身的推理
50、过程和回专家系统能够解释本身的推理过程和回答用户提出的问题，以便让用户了解推理过程，增大对专答用户提出的问题，以便让用户了解推理过程，增大对专家系统的信任感。家系统的信任感。例如，医疗诊断专家系统诊断出某病人例如，医疗诊断专家系统诊断出某病人患有肺炎，而且建议使用某种抗生素治疗，那么，专家系患有肺炎，而且建议使用某种抗生素治疗，那么，专家系统能够向病人解释为什么患有此病以及为什么必须用这种统能够向病人解释为什么患有此病以及为什么必须用这种抗生素治疗，就象一位医疗专家详细向病人解释病情和治抗生素治疗，就象一位医疗专家详细向病人解释病情和治疗方案一样。疗方案一样。解释机制为专家系统提供一个透明的界
