第2章-知识表示技术

第二章知识表示技术§2.1知识表示的基本问题什么是知识？从认识论的角度来看，知识就是人类认识自然界（包括社会和人）的精神产物，是人类进行智能活动的基础。一、知识与知识分类知识的分类方法很多，主要有三种：1.按知识的性质分：叙述性知识：表示问题的状态、概念、条件、事实的知识。过程性知识：表示问题求解过程中用到的各种操作、演算和行动等的知识。控制性知识：表示问题求解过程中决定选用哪种操作、演算和行动等的知识。一、知识与知识分类知识的分类方法很多，主要有三种：2.按知识的层次分：零级知识：最基本层的知识，包括问题域内的事实、属性、定理、定义等，属问题求解的常识性和原理性知识。一级知识：第二层知识，启发式知识。可弥补零级知识的不足，提高求解效率。二级知识：第三层知识，控制性知识。对低层知识起指导作用，组织和运用零级和一级知识。高层次知识：如回忆、综合、概括、抽象等，它们反映人的心理特征。领域知识元知识一、知识与知识分类知识的分类方法很多，主要有三种：3.按知识的来源分：共性知识：指问题域内有关事物、属性、概念、定义、定理、原理、理论、算法等的知识，它们来自教科书和刊物，并已为领域专业人员所承认和接受。它描述问题的细节，确保问题解的精确性，属深层知识。个性知识：来自现场有经验的专业人员，包括大量的经验知识或启发式知识。它描述问题的轮廓，知识严格性差，属浅层（表层）知识。一、知识与知识分类所谓知识表示，就是研究在机器中如何用最合适的形式对知识进行描述，使知识形式化、模型化，以便在机器中存储和使用知识。对于人们习惯的知识表示形式（如自然语言表示），机器不一定能接受，所以必须把人类知识变换成一定形式的机器内部的知识模型，为机器所接受。由于对人类大脑中知识形成和知识结构的机制还没有全部研究清楚，因此没有通用的知识表示形式。目前，人们针对不同问题、不同领域，研究出多种知识表示方法。二、知识表示与知识表示方法常用的知识表示方法有：1．产生式规则表示法2．状态空间表示法3．语义网络表示法4．框架表示法5．逻辑表示法6．“与/或”图表示法二、知识表示与知识表示方法对一个具体问题，可有不同的表示方法。采用不同的表示方法，问题求解的难易程度是不一样的。选择一个合适的知识表示方法，有利于知识的存储和运用，使问题求解变得容易。因此，知识表示方法对问题求解是至关重要的，甚至在有些问题中，智能主要表现在寻找适当的知识表示上，一旦找到了适当的知识表示方法，问题也就基本解决了。二、知识表示与知识表示方法对一个具体问题域的知识描述，往往可以有多种等效的知识表示方法。各种知识表示形式在具体问题求解过程中所表现的效能是有差异的，有必要根据它们在问题的知识处理过程中控制知识运用的要求，作为评估原则去衡量所选择的知识表示方法的适用度，以便能择优表示。三、知识表示方法的评价标准评估原则如下：1.有效性：能准确、有效地表示问题域内的所有类型知识，可实现问题的有效求解。2.可扩展性：能方便地进行知识检查、增删或修改，并对整个知识库不产生或少产生直接影响。3.可理解性：能自然地描述问题域内的所有知识，并符合人类的思维规律，便于理解。4.清晰性：知识表示形式和知识库结构简单。三、知识表示方法的评价标准§2.2状态空间表示法1．状态所谓状态就是描述某一类事物中各个不同事物之间的差异而引入的最少的一组变量的有序集合。它常表示成矢量形式：T210],,,[qqqQ其中的每个元素qi(i=0,1,2,…)叫分量。状态的维数可以是有限的，也可以是无限的。给定每个分量的值qik，就得到一个具体的状态：T210],,,[kkkkqqqQ一、基本概念2．操作引起状态中的某些分量发生改变，从而使问题由一个具体状态变化到另一个状态的作用叫操作。操作可以是一个走步、过程、规则、数学算子、运算符号或逻辑符号等。操作描述了状态之间的关系。一、基本概念3．状态空间问题的状态空间是一个表示该问题的全部可能的状态及其相互关系的图。一般是一个赋值有向图，包含三个方面的说明：S：所有可能的问题初始状态集合；F：操作集合；G：目标状态集合。所以状态空间常记为三元状态〈S，F，G〉。一、基本概念3．状态空间在状态空间表示法中，问题求解过程转化为在图中寻找从初始状态Qs出发到达目标状态Qg的路径问题，也就是寻找操作序列α的问题。Qs：表示某个初始状态；Qg：表示某个目标状态；α：把Qs变换成Qg的有限的操作序列。所以，状态空间中的解可用三元组〈Qs,α,Qg〉表示，它包含三个方面的说明：一、基本概念三枚钱币问题：设有三枚钱币，处在“反、正、反”状态，每次只允许翻动一枚钱币（但不允许一枚都不翻）。问连翻三次后，是否可以出现“正、正、正”或“反、反、反”状态？二、状态空间表示法示例为解这个问题，应首先将它形式化。设钱币正面为0，反面为1，引入一个三元数组Q=(q1，q2，q3)来描述这三枚钱币的总状态。全部可能的状态有8种：Q1=(0，0，0)；Q2=(0，0，1)；Q3=(0，1，0)；Q4=(0，1，1)；Q5=(1，0，0)；Q6=(1，0，1)；Q7=(1，1，0)；Q8=(1，1，1)。二、状态空间表示法示例翻动钱币的操作可以抽象为改变上述状态的算子，共有3个，即F={f1，f2，f3}其中f1：把钱币q1翻转一次；f2：把钱币q2翻转一次；f3：把钱币q3翻转一次。二、状态空间表示法示例问题的状态空间可写成〈{Q6}，{f1，f2，f3}，{Q1，Q8}〉。状态空间如图所示：000Q1100001101111110010011Q2Q5Q3Q4Q6Q8Q7f1f1f1f1f2f2f2f2f3f3f3f3可见：从Q6不可能经过三步到达Q1，即不存在从Q6到达Q1的解。但从Q6到达Q8的解有7个。二、状态空间表示法示例§2.3“与/或”图表示法“与/或”图通常为树图的形式，也称为“与/或”树。它基于人们在求解问题时的两种思维方法：1.分解：“与”树子问题(简单)子子问题(更简单)将复杂的大问题分解为一组简单的小问题，将总问题分解为子问题。若所有子问题都解决了，则总问题也解决了，这是“与”的逻辑关系。而子问题又可分为子子问题。如此类推，可以形成问题分解的树图，称为“与”树。“与/或”图表示方法的概念“与/或”图通常为树图的形式，也称为“与/或”树。它基于人们在求解问题时的两种思维方法：2.变换：“或”树等价问题(易)等价问题(更易)原始问题(难)将较难的问题变换为较易的等价或等效的问题。若一个难问题可以等价变换为几个容易问题，则任何一个容易问题解决了，也就解决了原有的难问题，这是“或”逻辑关系。而这些容易问题还有可能等价变换为若干更容易的问题，如此下去，可形成问题变换的“或”树。“与/或”图表示方法的概念在实际问题求解过程中，常常是兼用“分解”和“变换”方法，因而可用“与”树和“或”树相结合的图——“与/或”树。“与”树“或”树“与/或”图表示方法的概念§2.4产生式规则表示法产生式规则是根据客观世界中各客体之间存在依赖关系的实质而提出的。在客观世界中，各客体之间具有互相存在的因果关系，如：如果现在下雨，就穿雨衣。如果是运算放大器，就可进行信号运算。如果差动保护正确动作，则是变压器内部故障。这些句子表示的是状态—动作对，或前提(条件)—结论(行动)对，可以用产生式规则表示。一、产生式规则产生式规则的格式为如果（IF），则（THEN）；前提（条件），结论（行动）。前提可以是一个，也可以是几个，而结论一般只有一个。一、产生式规则用产生式规则形式表示知识的方法叫知识的产生式规则表示法。如前面的句子可表示成：clothed(rain_proof):-it_is(raining).operate(signals):-amplifier_is(operated).transformer(internal_fault):-action(differntial_protection).二、产生式规则表示法三、产生式系统用产生式规则表示知识所构成的系统称产生式系统，或称基于规则的系统。三、产生式系统产生式系统（或基于规则的系统）是用规则序列的形式来描述问题的思维过程，形成求解问题的知识模型。模型中的每一条规则称为一个产生式，规则用字符串表示。问题求解过程：根据初始数据，在上下文（或称当前数据库）中，搜索可匹配的产生式，并将结论写入上下文；再根据改变后的上下文，重新搜索匹配，最终求得问题的解。1.产生式系统求解问题的基本方法三、产生式系统数据库：用于存放用户提供的初始状态、问题域内对象的性质和属性等事实及求解过程中产生的中间结果数据。知识库：用于存放问题域内的知识，所有知识用产生式规则表示。推理机：又称控制系统或控制策略器。负责如何来运用规则库中的规则与事实匹配，当求解过程中出现多个结论或找不到满意结论时，如何为解决冲突问题提供控制策略。2.产生式系统的组成三、产生式系统自然性：产生式规则结构接近于人的思维和自然推理形式，易于理解。能有效表达启发式（浅层）知识：可根据人的经验程度、数据可靠程度，给出可信度因子，便于实现不精确推理。模块性强：规则库对推理机具有相对独立性，产生式规则间的联系一般是通过上下文的数据结构，而不是规则的互相直接调用。因此规则库中规则的增删、修改，不会对知识库维护产生大的影响。清晰性：规则库规则格式单一，层次清晰，便于知识正确性和一致性检查，推理机设计也易于实现。3.产生式系统的优点三、产生式系统透明度差：虽然其局部每一规则易理解，但因其独立性，因此难于作完整的原理性解释。表达能力受限：由于规则格式单一，对复杂知识、不确定推理的表达显得能力不足和呆板不灵活。大型AI系统有效性降低：产生式系统的强模块性，使得规则间信息传递依赖于上下文的数据，而不能直接调用其他规则，因此求解陷于大量的规则检索、匹配和操作，不能对执行优化序列或优化回溯控制作出明显反应。4.产生式系统的缺点§2.5谓词逻辑表示法1．谓词和个体变量谓词逻辑是一种用句子的内部结构（主语、谓词）为基本符号来研究人的思维规律的数理逻辑。如“张比王小”，用谓词表示为Little(Zhang,Wang)。Little是谓词名（可以是一个字母）；Zhang、Wang是主语或个体（次序不能颠倒）。一、谓词逻辑的一些概念1．谓词和个体变量谓词逻辑的一般形式为P(x1,x2,…xi,…xn),i=1,2,…,n其中P称为谓词，用来刻划个体的性质或关系；xi称为个体变量（又称变元），它表示独立存在的事物，可以是一个抽象的概念，也可以是一个具体的事物。一、谓词逻辑的一些概念1．谓词和个体变量几个术语：个体域：个体变元的变化范围，可以是有限的，也可以是无限的。谓词的元数：个体变元的数目。一元谓词，多元谓词。谓词赋值：将P赋予确定的含义，xi代表确定的个体。谓词的真值：真、假。一、谓词逻辑的一些概念2．联结词在谓词逻辑中，P(x1,x2,…xi,…xn)叫原子谓词公式（简称谓词公式），用P(x)表示。原子公式可以通过“联结词”构成谓词合式公式。在谓词逻辑中定义了五种联结词：一、谓词逻辑的一些概念(1)否定联结词乛：用来否定原来的谓词。如“乛P”表示P的否定，即“非P”。(2)合取联结词∧：用来表示并列的复合句子。如“P∧Q”表示P和Q的合取，即“P与Q”。(3)析取联结词∨：用来表示可兼有的或。如“P∨Q”表示P和Q的析取，即“P或Q”。(4)条件联结词→：表示“如果…那么…”的词句。如“P→Q”表示P是Q的条件，即“若P，则Q”。(5)双条件联结词：表示两个谓词互为条件。如“PQ”表示P和Q相互作为条件，即“若P，则Q；若Q，则P”，亦即“P当且仅当Q”。→←→←一、谓词逻辑的一些概念3．量词有些原子公式P(x)对个体域中所有个体变元都具有T值，但有些则不然。在数理逻辑中用量词来表示这个特点。1)全称量词“()”，读作“对于所有的x”。x()P(x)表示“对于个体域中所有的个体x，谓词P(x)均为T”。x2)存在量词“()”，读作