【人工智能 学习总结】第二章 知识表示（1）
2.1概述2.1.1知识及知识的分类
概念：知识是人们改造客观世界的实践中积累起来的认识和经验
分类：
①按性质：概念、命题、公理、定理、规则、方法等；
②按适应范围：常识性知识（通识知识）、领域性知识（专业性知识）；
③按作用效果：事实性知识（叙述性知识，常以“......是......”的形式出现）、过程性知识（规则、定律、定理构成）、控制性知识（元知识或超知识，是知识库中的高层知识）；
④按确定性：确定性知识、不确定性知识；
⑤按等级：零级知识（陈述性知识或事实性知识，回答“是什么”“为什么”）、一级知识（过程性知识或程序性知识，回答“怎么做”）、二级知识（控制性知识或策略性知识）等；
⑥按结构：逻辑性知识、形象性知识
2.1.2知识表示方法
知识表示：用一些约定的符号把知识编码成一组能被计算机接受并便于系统使用的数据结构
要求：①有表示能力；②可理解性；③可访问性（有效利用）；④可扩充性
方法：①谓词逻辑；②状态空间；③产生式规则；④语义网络；⑤框架；⑥概念存储；⑦脚本；⑧petri网；⑨面向对象
2.2谓词逻辑表示法2.2.1基本概念
谓词：设D是论域，P：D^n→{T，F}是一个映射，其中D²={（x₁，x₂，...，xn）|x₁，x₂，...，xn∈D}，则称P是一个n元谓词（n=1,2,...），记为P（x₁，x₂，...，xn）。其中，x₁，x₂，...，xn为个体变元。
二阶谓词：P（Q（x））的谓词的谓词
常用联结词：﹁（否定或非），∨（析取），∧（合取），→（条件或蕴含），↔（双条件）
2.2.2谓词逻辑表示法
例：用谓词逻辑表示下列知识：
⑴所有整数不是偶数就是奇数
Z(x)：表示x是整数；D(x)：表示x是偶数；S(x)：表示x是奇数
(任意x)(Z(x)→D(x)∨S(x))
⑵所有父母都有自己的孩子
P(x)：表示x是父母；C(y)：表示y是孩子；P(x,y)：表示x是y的父母
(任意x)(存在y)(P(x)→P(x,y)∧C(y))
2.2.3谓词逻辑表示法的经典应用
2.2.4谓词逻辑表示法的特点
①接近自然语言，灵活；②模块化
2.3产生式表示法2.3.1概述
①事实的表示
对于确定性知识，事实通常用一个三元组表示，即(对象,属性,值)或(关系，对象1,对象2),其中，对象就是语言变量。对于不确定性知识，事实通常用一个四元组表示，即(对象，属性,值，可信度因子)或(关系,对象1,对象2,可信度因子),其中，可信度因子是指该事实为真的可信程度,类似于模糊数学中的隶属程度，可用一个0~1的数表示。
例：“雪是白的”可表示为(snow,color,white)或(雪，颜色，白)。
“老王和老张是朋友”可表示为(friendship,wang,zhang)或(朋友，老王，老张)。
“李二比王三的年龄大很多”可以用四元组表示(largethan,lier,wangsan,0.9)。可信度因子越高，事实就越“真”。
②规则的表示
规则表示的是事物间的因果关系。其表现形式为
P→Q（可表示精确或不精确的值） 或 IFPTHENQ
其中,P表示前提条件,Q表示所得到的结论成组操作。这里需要注意的是，要得到结论，需要前提条件必须为真。该规则又称产生式,类似于谓词逻辑中的蕴含式,但有所区别，区别在于蕴含式只能表示确定性知识，而产生式不仅可以表示确定性知识，还能表示不确定性知识。
例如，在MYCIN专家系统中,有这样的产生式:P： 细菌革式染色阴性 形态杆状 生长需氧Q: 该细菌是肠杆菌属，可信度为0.8在该规则中，所包含的事实就是不确定性知识，当前提条件满足时，就有结论“该细菌是肠杆菌属”可以相信的程度是0.8，这个0.8是规则强度。这是蕴含式所不能做到的。
2.3.2产生式系统
规则库：知识库，是某领域知识用规则形式表示的集合
综合数据库：事实库，用来存放当前与求解问题有关的各种信息的数据集合
推理机：推理机又称控制系统，由一组程序组成.用来控制和协调规则库与综合数据库的运行，决定了问题的推理方式和控制策略。关键词：匹配。
2.3.3产生式表示法应用举例
例：
求解一般步骤：
(1)初始化综合数据库(事实库)
(2)检测规则库中是否有与事实库相匹配的规则，若有，则执行(3),否则执行(4)
(3)更新综合数据库，即添加步骤(2)所检测到与综合数据库匹配的规则.并将所有规则做标记
(4)验证综合数据库是否包含解，若有，则终止求解过程，否则转(2)
(5)若规则库中不再提供更多的所需信息，则问题求解失败，否则更新综合数据库，转(2)。
2.3.4产生式系统的推理方式
①正向推理（数据驱动式推理）
推理过程：
(1)用数据库中的事实与可用规则集中所有规则的前件进行匹配，得到匹配的规则集合
(2)使用冲突解决算法，从匹配规则集合中选择一条规则作为启用规则。
(3)执行启用规则的后件，将该启用规则的后件送人综合数据库或对综合数据库进行必要的修改。
(4)重复这个过程，直到达到目标或者无可匹配规则为止。
②逆向推理（目标驱动式推理）
推理过程：
(1)用规则库中的规则后件与目标事实进行匹配，得到匹配的规则集合
(2)使用冲突解决算法，从匹配规则集合中选择一条规则作为启用规则
(3)将启用规则的前件作为子目标
(4)重复这个过程，直至各子目标均为已知事实为止。
③双向推理
是一种自顶向下又自底向上的推理。推理从两个方向同时进行，直至某个中间界面上双方向结果相符便成功结束。
2.3.5产生式系统的特点
①优点
（1）自然性；（2）模块性；（3）清晰性；（4）有效性
②缺点
（1）效率较低；（2）不便于表示结构性知识；（3）难以扩展；（4）控制的饱和问题
人工智能基础第一章——绪论笔记
智能：人的智能是他们理解和学习事务的能力。智能是思考和理解的能力而不是本能的做事能力。智能机器是一种能够呈现人类智能行为的机器。人工智能是关于知识的科学。
人工智能的各种学派符号主义—（功能模拟）：人的认知基元是符号，认知过程即是符号操作过程。AI的核心：知识表示、知识推理和知识运用
连接主义—（结构模拟）人的思维基元是神经元。神经元连接的大脑工作模式行为主义—（行为模拟）：只能取决于感知和行为。不需要知识、不需要推理。智能行为只能在现实世界中与环境交互作用而表现出来。
智能信息处理系统的假设信息处理系统又叫符号操作系统或物理符号系统。所谓符号就是模式。一个完善的符号系统应具备以下六个功能：输入符号：input输出符号：output存储符号：store复制符号：copy建立符号结构：通过找出符号间的关系，在符号系统中形成符号结构条件性迁移：根据已有符号，继续完成活动过程。
任何一个系统，如果它能表现出智能，那么它就必定能够执行上述6种功能。反之，任何系统如果具有这6种功能，那么它就能够表现出智能；这种智能指的是人类所具有的那种智能。把这个假设称为物理符号系统的假设。
人工智能研究的基本内容：认知建模：信息处理过程，心理上的符号计算，问题求解，思维，诸如知觉，记忆，思考等关联活动知识表示知识推理知识应用机器感知机器思维机器学习机器行为智能系统构建
智能应用的三种模式数据智能知识智能社会智能
人工智能第四章
无信息搜索一.无信息搜索(uniformedsearchstrategies)二.广搜(breadfirstsearch)三.统一代价查询(Uniformcostsearch)四.深搜(Uniformcostsearch)五.有限深搜(Depth-limitedsearch)六.迭代深搜(Iterativedeepeningsearch,IDS)六.双向查询(Bidirectionalsearch)七.结语一.无信息搜索(uniformedsearchstrategies)无信息搜索的含义是搜索时，除了状态外，无额外信息来帮助你搜索.从边缘节点中挑选某个节点进行扩展，直到找到我们的目标节点(含目标状态),如何挑选节点进行扩展这就是我们今天要讨论的内容.
首先先介绍下无信息搜索有哪些查询策略:(1)广搜(breadth-firstsearch)(2)统一代价搜索(uniform-costsearch)(3)深搜(Depth-limitedsearch)(4)迭代深搜(Iterativedeepeningsearch)(5)双向查询(Bidirectionalsearch)
评估查询策略有这4个标准:(1)完备性(completeness):是否总能找到一个存在的解(2)优解:是否是最优解，例如每个节点是个城市，当然了节点还能存其他信息，例如它的父节点，子节点，深度等.节点之间相连接的边是代价，例如油钱，从城市A到城市B花多少油钱.最优解就是花最少的油钱到目的地城市.(3)时间复杂度:花多久能找到这个解(4)空间复杂度:需要多少内存，你也可以理解这整个数据结构例如树，图，毕竟这些你写代码的时候肯定会存在一个变量里，例如你的边缘节点们肯定会存在一个变量里这个变量的数据结构可能是队列，可能是栈，甚至是个列表.然后取个节点来开点.如何取哪些点来开这就是你的查询策略.
开始讲查询策略前，我们在来定义下一些变量.
b:最大分叉数，例如上图，最大分叉数是2.d:最浅深度，d=2，就是上图哪个实心黑色节点处在最浅深度.m:最大深度，m=3
最后在解释搜索策略之前，和大家阐述策略代码里的三个核心变量.
(1)node:node这就是个变量名字你想叫啥都行，没别的意思，node这个变量就是存储我们的节点，这个节点存着我们的状态(state)，代价(cost),深度(deep),子节点，父节点，等调用时,node.cost,node.state…(2)frontier:这是个数据结构，你可以是列表，队列，甚至字典也行，反正你怎么舒服怎么来，名字叫做frontier，用来存储边缘节点，去一个边缘节点用来开点，开点的意思就是我们看过这个节点了，或者经过这个节点了，那么这个节点又会有自己的边缘节点，再存储再这个数据结构中.至于选哪个节点开，这就是我们的查询策略.(3)explored:就是开点，经过的点.都存储在这个数据结构里，你用列表也行，怎么舒服怎么来.
二.广搜(breadfirstsearch)策略:展开最浅深度没有展开的节点.当然了，写程序的时候，我们会把边缘节点都存在某个数据结构里例如列表，那么我们展开边缘节点的策略就是FIFO，先到先服务，打开该边缘节点，那么打开这个边缘节点的边缘节点要放在列表中最后面，对吧.
我们可以来举下图例子.广搜就是把每一层节点开完，在往下一个深度开点.
完备性:没错，广搜具有完备性.当然了，前提是b和d要有穷.
时间复杂度:1+b+b2+b3+...+bd=O(bd+1)=O(bd)1+b+b^2+b^3+...+b^d=O(b^{d+1})=O(b^d)1+b+b2+b3+...+bd=O(bd+1)=O(bd)很简单，就是把看分叉数，就是每个节点广度开点.当然了，我们要开最浅深度所以用d.本质就是再算多少个节点，指数是深度，例如二叉树，第2深度节点数为,第3深度节点数为,最后全加一起.
空间复杂度:O(bd+1)O(b^{d+1})O(bd+1)与时间复杂度一样，本质就是再算多少个节点.
优解:当代价是1时，它是最优解.也就是节点和节点之间的边代价是1时，才是最优解，例如油钱都是1块钱，如果油钱代价不一样，有的是1快有的是3块，那找到的肯定不是最优解，因为我们开点策略仅仅是展开最浅深度没有展开的节点.
宽度查询的逻辑(图片搜索)我们来看看上述伪代码.先将初始节点放入变量node里.然后检查这个节点是否是目标节点,即proble.FOAL-TEST(node.STATE).如果是则return解，若不是接着运行下一条命令.现在我们将这个初始点放入我们的frontier里，准备取出开它，按照先进先出,它开后会有它自己的边缘点，再放入frontier里.开过的点我们放入explored里,但初始它是空的.你用列表也行，队列也行(推荐队列).
之后就是循环loopdo，开先进的边缘点，记录代价cost，记录行为action，它自己的边缘点再放入frontier里,放到最后边.开过的点放入叫explored的数据结构里.
宽度查询(简单二叉树搜索)很简单，就是横着找.
缺点:随着深度增加，指数级增长节点个数，内存需求和执行时间都太大了，宽度优先搜索不能解决指数复杂性问题.仅仅cost均相同时，才能找到最优解，当cost不相同，仅仅找到目标点而已.
三.统一代价查询(Uniformcostsearch)我们来定义下，g(n):意味着到某个节点n的总代价即到第n点一路的代价.统一代价搜索:扩展的是路径消耗g(n)最小的节点n,用优先队列来实现，对解的路径步数不关心，只关心路径总代价。即使找到目标节点也不会结束，而是再检查新路径是不是要比老路径好，确实好，则丢弃老路径。
策略：展开代价(cost)最小的没有展开的节点.
举个例子:假如我们初始点Sibiu,目标点是Bucharest.那我们开始用统一代价来走走，先看g(Rimnicu)=80和g(Fagara)=99,那么选Rimnicu,然后再看g(Pit)=80+97,g(Fagara)=99,那选Fagara,g(Buch)=99+211=310,那么走Rim那g(Buch)=80+97+101=270,总之,用新路的一路代价和旧路的一路代价进行比对.
完备性:是的,但条件是代价是正数.ϵepsilonϵ>0.ϵepsilonϵ为最少的代价
时间复杂度:我们来定义下C∗C^*C∗为解的最优代价(一路上的总代价).那么时间复杂度为O(b1+C∗ϵ)O(b^{1+frac{C^*}{epsilon}})O(b1+ϵC∗)，其中C∗ϵfrac{C^*}{epsilon}ϵC∗为最多需要多少步才能到达目标点，相当于d。
全代价搜索代码我们来看看上述代码，首先给初始节点，例如上述例子假如我们初始点Sibiu,那么node这个就是关于Sibiu的节点.frontier这个变量是个优先队列，代价最小的节点优先，例如Sibiu它有俩城市Fagaras和Rimnicu，这俩节点.那么frontier=[Rimnicu,Fagras],先开Rimnicu,因为Rimnicu的代价才80，Fagras代价要99.那么已开点explored=[Sibiu,Fagras],frontier=[Fagaras,Pitesti],为啥Pitesti在Fagaras后面，因为Pitesti的代价是80+97=177，比99代价的Fagras要小.所以下一步我们会开Fagras,那么explored=[Sibiu,Fagras,Pitesti].…以此类推开点.
四.深搜(Uniformcostsearch)策略:开深度最深的未开节点.它的frontier是最后进的节点先开.我们试试深搜，深搜我们会发现，它好像不考虑代价.还是这仨变量node,frontier,explored.我们从Sibilu要到Bucharest.那么当我们开Sibilu这个节点，我们要看它的状态，node.state,我们发现是Sibilu，不是我们的目标节点.那它的边缘节点即子节点是Fagaras和Rimunice，那么frontier=[Fagaras,Rimunice],因为是最后进的节点先开，那么，我们会先打开Rimunice这个节点，explored=[Sibilu,Rimunice],那么它的边缘节点，有Pitesti,存到frontier里，那么frontier=[Fagaras,Pitesti],所以，我们最后看到，深搜是一口气一路搜下去，直到找到目标点.我们会发现深搜没有考虑代价，所以它不能找到最优解.
完备性:对于树搜索它会有循环，反复见到重复的节点(详见第三章图与树的区别),而且还有深度无穷的情况，所以树搜索时，深搜不具有完备性.换句话说，如果是深度查询图搜索(graphsearch)，避免了重复状态和冗余的路径，iscomplete是完备的(即能找到解)，因为它会打开所有节点如果是深度查询树搜索(treesearch),它是不完备的，因为会有loop循环，A→B→A→B.虽然在树图中深度查询可以改进，使其避免重复节点，但避免不了冗余路径.
时间复杂度：O(bm)O(b^m)O(bm),当mmm远大于ddd时，需要时间很多.如果解很多，因为毕竟条条大路通罗马，深搜又不考虑代价，所以有时候表现情况比广搜要好.
空间复杂度:O(bm)O(bm)O(bm)线性空间.
优解:不能，深搜没考虑代价.
对于图像查询，深度搜索一无事处，一点用没有对比广度查询，但是在树查询中，深度搜索空间复杂度是O(bm)，只需要bm个节点.比广搜空间复杂度要小很多.
深搜会得到很多个解，但广搜会得到一个很短的解，啥意思，我们的解不是说找到目标就够了，我们还要返回它的路径,也就是说深搜能找到路径最短的解.
深度查询的变种backtrackingsearch回溯查询,在CSP满足问题里，我们会见到的.先告诉你结论，通过回溯查询，空间复杂度才仅仅O(m).也就是说只要做O(m)个操作.因为回溯查询，每次仅仅开一个后继者，所以没有b个，只有1个所以O(1*m)不是树查询的O(bm).
深度查询(基于树查询)
五.有限深搜(Depth-limitedsearch)有限深度查询(DLS).当状态空间无穷(其实是问题太深太复杂),那么需要节制深度.
时间复杂度:O(bl)O(b^l)O(bl)空间复杂度:O(bl)O(bl)O(bl)
有限深度查询（基于树查询）这里的limit就是限制深度.它在不断的减少limit，当然了，你可以自己设置个深度界限，如果达到就停.代码里的cutoff相当于flag，就是不要再往下搜的意思.
六.迭代深搜(Iterativedeepeningsearch,IDS)迭代深搜时结合了广度查询优点（最短解）和深度查询的优点(空间复杂度小).逐渐增加深度，利用广搜.
完备性:是的
时间复杂度:就是算多少个节点，IDS的时间复杂度和广度查询的时间复杂度一样O(bd)O(b^d)O(bd).
空间复杂度:就是存储了多少个节点，IDS的空间复杂度和深度查询的空间复杂度近似O(bd)O(bd)O(bd).
优解:当代价均为1时，是最优解.黑色点是开点.绿色点是边缘点.
下面则是迭代深搜的伪代码
cutoff:叫IDS增加limit的上限
六.双向查询(Bidirectionalsearch)策略:从初始位置出查询发，于此同时从终点位置出发查询，两个查询在中间碰头.所以两个查询的时间复杂度相加，空间复杂度相加.深度为一半！
如果用广度查询进行双向查询:时间复杂度：O(bd/2)+O(bd/2)=O(bd/2)O(b^{d/2})+O(b^{d/2})=O(b^{d/2})O(bd/2)+O(bd/2)=O(bd/2)空间复杂度：O(bd/2)+O(bd/2)=O(bd/2)O(b^{d/2})+O(b^{d/2})=O(b^{d/2})O(bd/2)+O(bd/2)=O(bd/2)
难点:backwardsearch，从终点位置查询，要找到一个对于终点位置查询来说x是前任节点，对于forwardsearch,起点查询来说x是继任点.也就是这个中间点很难办.优点:空间复杂度和时间复杂度为原来一半.
七.结语下章为大家解释有信息查询。若有谬误，请指出，感谢.