人工智能期末复习概要.ppt

人工智能复习北京师范大学信息科学与技术学院王醒策第一章 绪论­课程研究的主要内容–知识表示–推理方式­确定性推理（主要归结原理）­不确定性推理–搜索技术研究­普通图搜索­超图搜索（与或图搜索）第一章 绪论­需要解决的问题：–万能的人工智能的知识体系结构从根本上就不可能有，最根本的原因是缺乏知识人是根据知识行事的，而不是根据抽象原则上进行推理–即使是推理系统中，它的主要技术是状态空间搜索而在执行的过程中最主要的问题就是组合爆炸问题，只有是用理性的知识才能够摆脱困境第一章 绪论­人工智能的瓶颈问题–知识获取–规模扩展–应用前景第二章 知识的表示­知识的获取–如何从现实世界中得到知识­知识的表示–如何将已经获取的知识以计算机内部代码的形式加以合理的表示，以便于存储­知识的运用–如何运用这些知识进行推理以解决实际的问题第二章 知识的表示­知识的定义–数据–信息–知识第二章 知识的表示­知识表示方式–直觉表示方法–逻辑表示方法逻辑表示方法–产生式表示方法产生式表示方法–语义网络表示方法语义网络表示方法–框架表示方法框架表示方法第二章 知识的表示­知识表示方式–面向对象表示方法–脚本表示方法–状态空间表示方法状态空间表示方法–与与/或树表示方法或树表示方法第二章 知识的表示­逻辑表示法（经典逻辑推理）–一阶谓词逻辑–谓词逻辑的规范表达式P(x1,x2,…,xn)–逻辑表示法­语法和语义­1 基本符号­2 原子公式­3 连词和量词第二章 知识的表示­产生式表示法（产生式系统、专家系统）–产生式表示的形式–产生式与谓词逻辑中的蕴涵式的区别­蕴涵式只能表示精确知识，产生式不仅可以表示精确知识，而且可以表示不精确知识­蕴涵式要求前提精确匹配，产生式可以不精确匹配­蕴含式有真值，产生式没有真值第二章 知识的表示­产生式知识表示方法–确定性规则知识的产生式表示–不确定性规则知识的产生式表示–确定性事实知识的产生式表示–不确定性事实知识的产生式表示­产生式系统的组成–规则库、综合数据库、推理机（匹配、冲突解决、操作）第二章 知识的表示­语义网络表示法（自然语言理解）–从理论上来说，语义网络与一阶谓词具有同样的知识表示能力。

–语义网络中常用的语义联系­类属关系（AKO、AMO、ISA）­包含关系（Part-of）­占有关系（Have）­时间关系（Before、After、During）第二章 知识的表示­语义网络表示法–语义网络中常用的语义联系­位置关系（Located-on、 Located-at 、 Located-under、 Located-inside、 Located-outside）­相近关系（Similar-to、Near-to）­属性关系（IS）第二章 知识的表示­语义网络表示知识的方法–事实性知识–情况和动作的表示­情况的表示（情况节点）­动作和事件的表示（动作节点）–逻辑关系的表示­合取和析取的表示­存在量词和全称量词的表示第二章 知识的表示­框架表示法–组成：­框架是由框架名、槽、侧面和值四个部分组成的­举例子：计算机主机–框架表示法表示知识的步骤­分析表达只是对象及其属性，对框架中的槽进行合理设置­对各对象之间的联系进行考察使用一些常用的或根据需要定义的槽名，来表示上下框架联系第二章 知识表示­状态空间表示法–问题的状态空间构成­状态­算符­状态空间（S,F,G）状态空间的图示形式成为状态空间图。

节点表示状态，有向边表示算符第二章 知识表示­用状态空间表示问题的步骤–定义状态的描述形式–用所定义的状态描述形式把问题的所有可能状态都表示出来，并确定出问题的初始状态描述和目标状态集合描述–定义一组算符，使得利用这组算符可把问题有一种状态转变为另一种状态第二章 知识表示­与/或树表示法–问题的分解与等价变换–问题的归约的与/或树表示­与树、或树、与/或树­端节点与终止节点­可解节点与不可解节点­解树第三章 确定性推理方法­要求：­熟练掌握构造逻辑公式的合取范式，skolem标准型的转化方法，归结法进行归结的过程掌握归结过程中的控制策略第三章 确定性推理方法­推理方式–正向推理–反向推理–双向推理–混合推理第三章 确定性推理方法­自然演绎推理方法–假言三段论P Q，Q R=>P R–拒取式P Q，~Q=>~P–假言推理：P，P Q=>Q第三章 确定性推理方法­归结推理方法（消解法）­将谓词公式化为Skolem标准形步骤–消去→号和(双蕴含符号)；–～深入到量词内部；–全称量词左移，使所有的变元名称均不相同；–消去存在量词–把全称量词全部移到公式的左边–母式化为和取范式第三章 确定性推理方法­归结过程的步骤–将命题写成合取范式–根据给出的合取范式求出子句集–根据求得子句集，使用归结原理进行归结–归结之后的新子句还要再次放入子句集，参加归结。

–直到归结为空的时候，即使得问题得证第三章 确定性推理方法­用归结原理进行定理证明–首先否定结论，并将否定后的结论~B与前提公式集相与A1 ∧~B，组成如下的谓词公式G= A1 ∧~B–求谓词公式G的字句集S–应用归结原理，证明子句集S的不可满足性，从而证明谓词公式G的不可满足性这样就说明对结论B的否定是错误的，推断出定理的成立第三章 确定性推理方法­用归结原理进行问题求解–把已知前提条件用谓词公式表示出来，并化成相应的子句集，设该子句集的名字为S1–把待求解问题用谓词公式表示出来，然后将其否定，并与一谓词ANSWER构成析取式谓词ANSWER是一个转为求解问题而设置的谓词，其变量必须与问题公式的变量完全一致–把问题公式与谓词ANSWER构成的析取式化为子句集，并把该子句集与S1合并构成子句集S第三章 确定性推理方法­归结过程中的控制策略–删除策略­纯文字删除法­重言式删除法­包孕删除法–支持集归结策略–线性归结策略–单文字（单元）归结策略–输入归结策略第四章 不确定性推理­学习目标 –了解不确定性推理的含义、思路和讨论的主要问题–掌握可信度方法、主观Bayes方法和证据理论不确定性推理方法第四章 不确定性推理­计算问题–不确定性的传递问题–证据不确定性的合成问题–结论不确定性的合成问题第四章 不确定性推理­可信度方法­知识不确定性的表示–在基于可信度的不确定性推理模型中，知识是以产生式规则来表示的，而只是的不确定性则是以可信度CF(H,E)来表示的，其一般的形式为：第四章 不确定性推理­可信度方法­组合证据不确定性表示–当多个证据以合取得方式构成一个组合证据的时候，组合证据的可信度为这些单一证据的可信度最小值；–当多个证据以析取得方式构成一个组合证据的时候，组合证据的可信度为这些单一证据的可信度最大值；第四章 不确定性推理–MB(H,E)：信任增长度–MD(H,E)：不信任增长度–MB(H,E)与MD(H,E)是互斥的–解释­当MD(H,E)>0时，应该有P(H/E)< P(H),那么有MB(H,E)=0­当MB(H,E)>0时，则为P(H/E)> P(H),那么有MD(H,E)=0­如果P(H/E)= P(H),则MD(H,E)= MD(H,E)=0表示，E与H无关第四章 不确定性推理­不确定性的传递问题–单条知识–多条知识第四章 不确定性推理­主观Bayes方法­知识的不确定性–LS：充分性度量–LN：必要性度量–是为度量产生式规则的不确定性而引入的一组数值。

第四章 不确定性推理­LS和LN的讨论–LN和LS之间的关系­LS>1且LN<1­LS=LN=1­LS<1且LN>1第四章 不确定性推理­主观Bayes方法­证据的不确定性–给定了可信度C(E/S)，就等价于告知了P(E/S)，–组合证据的不确定性­当证据E是由多个单一证据合取组合而成­当证据E是由多个单一证据析取组合而成­对于非运算第四章 不确定性推理–不确定性的传递问题­当证据肯定出现的时候P(E)=P(E/S)=1­肯定出现的时候，用下面的式子既可以把先验几率O(H)更换为后验几率O(H/E)­如果我们把几率用概率替换即可得第四章 不确定性推理–在证据肯定不出现时P(E)=P(E/S)=0, P(~E)=1.–那么用下式计算当E肯定不出现的情况下，把先验几率O(H)更新为O(H/~E)–根据概率和几率的换算关系可得第四章 不确定性推理­用概率表示证据的不确定性–上述针对确定性证据的后验概率将不再适用而要使用下面的公式第四章 不确定性推理–P(E/S)=1; P(H/S)=P(H/E)–P(E/S)=0; P(H/S)=P(H/~E)–P(E/S)=P(E); P(H/S)=P(H)第四章 不确定性推理­利用这三个特殊点，使用分段插值公式可得P(E/S)与P(H/S)的解析表达式第四章 不确定性推理­若有n条知识都支持相同的结论，并且每条知识的前提条件所对应的证据Ei都有相应的观察Si，这时需要按照下面的式子求得P(H/S1,…,Sn)D-S理论的数学基础–信任函数 Bel：2D →[0,1]。

–似然函数 Pl: 2D →[0,1]D-S理论的数学基础–概率分配函数正交和–设M1和M2是两个概率分配函数，则他们的正交和M=M1⊕M2为­M(Φ) = 0;­M(A) = K-1∑m1(X)m2(Y), 当X∩Y = A­其中K = 1 - ∑m1(X)m2(Y), 当X∩Y =Φ　　　　　= ∑m1(X)m2(Y), 当X∩Y ≠Φ特定概率分配函数­设样本空间D={S1,S2,…,Sn},领域内的命题都用D的子集来表示，则定义2D上的概率分配函数M(x)满足如下条件特定概率分配函数–其中，|A|表示命题A对应的集合中所包含的元素个数–在这种特定的概率分配函数中，定义了只有单个元素构成的子集和样本空间D本身的基本概率数才有可能大于0，其它子集的基本概率数均为0基于特定概率分配函数的不确定性推理­信任度函数–性质不确定性推理­信任度函数–推论不确定性推理­证据的不确定性表示–证据E为初始简单证据，f(E)由用户给出–证据E为前面推理所得到的结论，f(E)有推理计算给出–证据E为组合证据的时候­由多个证据的合取组成­由多个证据的析取组成不确定性推理­知识的不确定性表示–不确定性知识用如下形式的产生式规则表示–E为前提条件–H是结论，用样本空间中的子集来表示，h1,h2,…,hn是该子集中的元素–CF是该集合中的可信度因子，用集合的形式来表示。

不确定性推理­不确定性的传递计算方法–求出H的概率分配函数–求出H的信任函数Bel(H)和似然函数Pl(H)–求出结论H的信任度f(H)第五章 状态空间的搜索策略­状态空间搜索可以分为盲目搜索和启发式搜索两种–盲目搜索­又称为无信息搜索也就是在搜索的过程中只按预先的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略–启发式搜索­称为有信息搜索它是指在问题搜索过程中，根据问题本身的特征或者搜索过程中产生出来的一些信息来不断地改变或者调整搜索方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解第五章 状态空间的搜索策略­回溯搜索：–不是图搜索-不能记忆路径–BackTrack（DATA）递归过程­纵向递归­横向循环第五章 状态空间的搜索策略­状态空间的搜索算法：–1 建立一个只含有初始节点S0的搜索图G，把S0放入到open表中–2 建立closed表，并且将其置为空表–3 判断open表是否为空表，若为空，则问题无解，退出–4 若open表非空，则选择open表中的第一个节点，把它从open表中移出，并放入closed表中，将此节点标记为节点n第五章 状态空间的搜索策略–5 考察节点n是 否为目标节点，如果是，则问题有解，并且成功退出。

问题的解既可从图G中沿着指针从n到S0的这条路径得到–6 扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点加入图G中第五章 状态空间的搜索策略–7 对于那些未曾在G中出现过的（即未曾在open表上或closed表上出现过的）M中的节点，设置一个指向父节点（即节点n）的指针，并把这些节点加入到open表中；对于已在G中出现过的M中的那些节点，确定是否需要修改指向父节点（n节点）的指针；对于那些先前已经在G中出现并且已在closed表中的那些M中的节点，确定是否需要修改通向它们后继点的指针–8 按照某一种方式或者某种策略重排open表中的节点的顺序–9 转到第（3）步第五章 状态空间的搜索策略­节点类型说明第五章 状态空间的搜索策略­盲目搜索–宽度优先搜索­第六步，将节点放入open表的末端­应用队列来实现–深度优先搜索­第六步，将节点放入open表的前端­应用栈来实现–扩展：有界深度优先搜索第五章 状态空间的搜索策略­考虑搜索代价问题­代价树宽度优先算法–第六步，计算扩展节点的代价，根据节点的代价大小对open表进行排序­代价树深度优先算法–第六步，计算扩展节点的代价，按照有向边代价从达到小排序，放置到open表的前端。

第五章 状态空间的搜索策略­启发式搜索­重要：如何设定估价函数­优先搜索–全局最佳优先搜索­与宽度优先搜索类似，对扩展后继节点计算f(x)值，对open表中的全部节点排序–局部最有优先搜索­与深度优先搜索类似，仅对扩展的后继节点排序，并放入open表的前端第五章 状态空间的搜索策略­A算法和A*算法–评价函数­形式：f(n)=g(n)+h(n)–A*算法第五章 状态空间的搜索策略­A*性质–可采纳性–单调性–信息性。