人工智能复习提纲
人工智能知识梳理目录第一章绪论第二章智能Agent第三章通过搜索进行问题求解第五章对抗搜索第七章逻辑Agent第八章概率推理第十七章概率推理第十八章样例学习考试大题：一共三道，一道alpha-beta剪枝，一道贝叶斯网络计算，一道人工神经网络计算。分值占的蛮大，这三个是重点。
第一章绪论一、什么是人工智能
定义？人工智能（ArtificialIntelligence）是从事如何用软件和硬件构建智能主体（IntelligentAgent）的科学与技术。
衡量一个AI的好坏
左侧利用和人的行为的逼真程度衡量，右侧依靠一个行为的合理性衡量。我们主要依靠合理性衡量
ThinkinghumanlyThinkingrationallyActinghumanlyActingrationally像人一样行动，可以依靠图灵测试来检测像人一样思考，可以通过认知建模（认知科学领域）来实现合理思考，有逻辑流派，逻辑主义流派等合理行动，智能体Agent，合理的Agent。合理性比起像人一样行动更具有普适性以及更经得起科学的检验。二、人工智能的历史：
三、人工智能的三个层次：
人工专用智能（弱人工智能）人工通用智能（强人工智能）人工超级智能（超智能）第二章智能Agent一、智能体和环境
智能体：通过传感器感知所处环境并通过执行器对该环境产生作用的东西定义：给定感知序列－－－求取行动，通过智能体函数来实现，抽象的数学表示：[f:P*->A]智能体=体系结构+程序二、理性
理性的判断定义成功标准的性能度量智能体对环境的先验知识智能体可以采取的行动智能体截止到那时的感知序列理性!=全知，理性!=完美特点：信息收集－为了修改未来的感知信息而采取的行动自主性：学习和自适应三、环境
PEAS
性能度量（Performancemeasure）环境（Environment）执行器（Actuators）传感器（Sensors）环境的类型
完全可观察的vs.部分可观察的如果agent在每一个时间都能获取环境的完整状态，那么是完全可观察的确定的vs.随机的环境的下一个状态完全取决于agent的行为片段式的vs.延续式的延续式是当前每一个动作会影响未来决策静态的vs.动态的动态：在agent决策的时候会变化离散的vs.连续的感知和行动是有限数量且可被清晰定义的单智能体vs.多智能体环境中有多少智能体四、智能体的类型
简单反射Agent直接对感知信息做出反应基于模型的反射Agent保持内部状态，追踪记录当前感知信息中反映不出来的世界各方面基于目标的Agent行动是为了达到目标基于效用的Agent试图最大化它期望的值第三章通过搜索进行问题求解一、问题形式化描述
一个问题要用五个部分进行形式化描述
初始状态：eg.Agent位置和灰尘位置确定行动eg.Left（左移），Right（右移），Suck（吸尘）转移模型eg.行动会产生对应的预期效果目标测试eg.检查所有位置是否干净路径耗散eg.路径的总步数。二、搜索的基本问题与主要过程
搜索解决的基本问题是否一定能找到一个解（完备性）。找到的解是否是最佳解。（最优性）找到解需要花费多长时间？（时间复杂度）在执行搜索的过程中需要多少内存？（空间复杂度）是否终止运行或是否会陷入一个死循环。主要流程从初始或目的状态出发，并将它作为当前状态将适用当前状态的一些操作作用于当前状态而得到新的状态，并建立指向其父结点的指针检查是否结束，如结束，则得到问题的一个解；否则，将新状态作为当前状态，继续搜索三、无信息搜索
宽度优先搜索定义：在下图的搜索中，顺序是12345678
伪代码
//一般使用队列实现voidBFS(图)for（所有顶点若该顶点未被访问BFS（该顶点）;分析
完备，可求得最优时间复杂度O(B^M)空间复杂度O(B^M)一致代价搜索原理：一致代价搜索总是扩展路径消耗最小的节点N。N点的路径消耗等于前一节点N-1的路径消耗加上N-1到N节点的路径消耗。
与BFS区别：
目标检测应用于节点被选择扩展时，而不是在节点生成的时候。原因：一致代价搜索希望在替换代价更小的节点后再确认解如果边缘中的节点有更好的路径到达该节点，那么会引入一个测试个人觉得和A*算法也有一点相似，但是这个是无信息搜索，区别很大。
分析
完备，可求得最优时间复杂度空间复杂度深度优先搜索定义：在下图中搜索顺序为：ABEIFCDGH伪代码：//一般使用栈实现voidDFS(图)for（所有顶点若该顶点未被访问DFS（该顶点）;分析：时间复杂度：O(B^M)空间复杂度：O(BM)可能无法求到最优深度受限搜索通过设置界限l来避免DFS在无限状态空间下搜索失败的尴尬情况。迭代加深的深度优先搜索如上的搜索树，假设目标在A2，那么搜A1的子树的时候会耗费很多时间，而且可能会超时。既然要求深度最小的可行解，那么不妨每次用深度优先搜索搜深度≤k的节点，把k逐次增加，这样既可以最早搜到A2（判断A2可行后就直接返回了），又不会耗过多空间。
在深度受限搜索的基础上逐步增加深度限制，不断的重新启动算法，直到找到目标结点。该算法结合了深度优先和广度优先的优点。从实际应用来看，迭代加深搜索的效果比较好，并不比广度优先搜索慢很多，但是空间复杂度却与深度优先搜索相同，比广度优先搜索小很多四、启发式搜索
启发式策略和信息启发信息：在具体求解中，能够利用与该问题有关的信息来简化搜索过程，称此类信息为启发信息启发式策略：利用与问题有关的启发信息进行搜索启发式搜索：利用启发信息的搜索过程评价函数：一般的形式：f(n)=g(n)+h(n)g(n)比重越大，说明越倾向于宽度优先，h(n)越大，越倾向于启发性搜索启发函数h(n)：从目标节点到节点的耗散值。最佳优先搜索按评估函数值递减的顺序排列未扩展节点，依次扩展贪婪最佳优先搜索评价函数：f(n)=h(n)可能会陷入死循环，可能无法到达最优境地时间复杂度和空间复杂度都是O(b^m)A*搜索算法及其特性分析思路：避免扩展耗散已经很大的路径
流程图：
评估函数：f(n)=g(n)+h(n)
g(n)=到达此结点n时已经花费的代价h(n)=从该结点n到目标结点的最小代价路径的估计值f(n)=经过结点n的最小代价解的估计代价在运算过程中，A*算法每次从优先队列中选取优先级最高的节点作为下一个待遍历的节点。
可以在有限时间取得最优解，时间复杂度是指数级，空间复杂度高
第五章对抗搜索一、博弈
零和问题博弈：有完整信息的、确定性的、轮流行动的、两个游戏者的零和游戏。博弈问题二、博弈中的优化决策
极大极小算法
Minimax算法，是一种最小化对手最大得益的算法。通过递归算法，先走到底层的叶节点，并求得该叶节点的估值，譬如最左边的10和正无穷。之后会取最小值10返回上一层的节点，以此类推，在10、5中选择最大值传回第二层等。极大极小值算法相当于对于一棵博弈树进行了一次深度优先搜索。通过这样的搜索来获得当前最好走法。若树的最大搜索层数是b，而每一次走棋的合法行棋数量为a，那么时间复杂度将是O(b^a)。时间复杂度和空间复杂度极高，需要改善多人博弈时的最优决策
效用值为向量，每个玩家都要最大化自身效用值
三、α-β剪枝
算法：
当节点N以下的搜索完成（或剪枝中止）时，更新N的父节点的α或β值当一个MAX节点N的α值>=N的MIN祖先节点的β值，则节点N以下的搜索中止当一个MIN节点N的β值B->E赋值后，我们发现节点5的值与当前的alpha值比较更新，alpha>=beta，因此修剪E的右后继。以此类推。伪代码
functionalphabeta(node,depth,α,β,maximizingPlayer)isifdepth=0ornodeisaterminalnodethenreturntheheuristicvalueofnodeifmaximizingPlayerthenvalue:=−∞foreachchildofnodedovalue:=max(value,alphabeta(child,depth−1,α,β,FALSE))α:=max(α,value)ifα≥βthenbreak(*βcut-off*)returnvalueelsevalue:=+∞foreachchildofnodedovalue:=min(value,alphabeta(child,depth−1,α,β,TRUE))β:=min(β,value)ifα≥βthenbreak(*αcut-off*)returnvalue四、不完美的实时决策
评估函数首先，评估函数对终止状态的排序应该和真正的效用函数的排序结果一样；第二，评估函数的计算本身不能花费太长时间（总观点是为了更快地搜索）；第三，对于非终止状态，评估函数应该和取胜几率密切相关。
一般使用线性加权函数表示。和子力与棋局状态相关。
截断搜索需要更加复杂的截断测试。评估函数只适用于那些静态棋局，以及需要消除地平线效应。
修改ALPHA-BETA-SEARCH当适合截断搜索时调用启发式函数EVAL
向前剪枝是指在某个结点上无需进一步考虑而直接剪枝一些子结点
第七章逻辑Agent基于知识的Agent知识库=由形式语言组成的句子集合，核心部件智能体可以在知识级别或者如何实现的级别被查看构建智能体（或其他系统）的声明性方法：告诉它所需要知道的一切Wumpus世界了解的内容：性能度量，环境，执行器，传感器完全可观察性，非片段式，静止，离散性，单智能体逻辑逻辑是一个用来处理事实的形式化系统，目的是得到正确的结论语法:构造知识库有效句子的规则语义:句子的“含义”,或者逻辑语句和真实世界之间的关系蕴含：意味着一样东西是从另一样东西中派生出来的知识库KB蕴含句子α当且仅当α在所有KB为真的世界里为真模型：这些模型是可以评估真假的形式化的结构世界KB╞αiffM(KB)属于M(α)例如，KB=巨人队赢了and红队赢了;α=巨人队赢了问：谁是kb，谁蕴含了谁只导出蕴涵句的推理算法被称为可靠的或真值保持的如果推理算法可以生成任一蕴涵句，则它是完备的命题逻辑定义：能判断真假的陈述句。这种陈述句的判断只有两种可能：一种是正确的判断，一种是错误的判断。称判断为正确的命题的真值（或值）为真，称判断为错误的命题的真值（或值）为假。命题的分类：简单命题、复合命题简单命题符号化：用大写英文字母P,Q,R,…,Pi,Qi,Ri(i≥1）表示简单命题，将表示命题的符号放在该命题的前面，称为命题符号化。语法：取非、析取、合取、蕴含、双条件逻辑等价性：两个语句是逻辑等价的当且仅当下列谓词逻辑在相同模型中为真α≡ßiffα╞βandβ╞α有效性：如果一个语句在所有的模型中为真，那么这个语句是有效的推理规则（可以看一看离散数学联合范式（CNF可满足性：如果一个语句在一些模型中为真，那么这个语句是可满足的前向链接和反向链接前向：用已知去一直推导所有能得到的信息。可能生成无限多新事实以至于无法结束。低效：匹配代价高等后向：扫描知识库，找到结论为最终结论的事实，然后对改结论实例化，然后找到该结论的前提条件，之后对前提替换……直到与已知符合。不完备，但快。区别：FC是数据驱动的,自动的,无意识的过程,可能会做许多与目标相关的工作BC是目标驱动的,正确解决问题第八章概率推理命题逻辑的局限性：命题逻辑不考虑命题之间的内在联系和数量关系
一阶逻辑中的基本概念：个体、谓词和命题函数(谓词是布尔函数，函数是返回对象的)
原子语句复杂语句forall一般都是用蕴含，存在一般都是合取知识的一阶逻辑表达方法
一阶逻辑化为子句
消蕴含和等价：利用P→Q=¬P∨Q；P↔Q=（P∧Q）∨（¬P∧¬Q）等价关系消去蕴含符“→”和双条件符“↔”
否定内移：减少否定号的辖域
变量标准化：即使每个量词采用不同的变量
消去存在量词∃：如果存在量词不在任何一个全称量词的辖域内，则该存在量词不依赖于任何其它的变量，因此可用一个新的个体常量代替。如将(∃x)P（x）化为P(A)。如果存在量词是在全称量词的辖域内（如在公式(“∀y)（(∃x)P（x，y））中，变量x的取值依赖于变量y的取值）由Skolem函数（f(y)）表示依赖关系注意，函数名应是原合式公式中没有的。
将公式化为前束形
化为合取范式
略去全称量词
消去合取符号∧，把母式用子句集表示
子句变量标准化：重新命名变量，使每个子句中的变量符号不同
归结原理：
两个表达式匹配当且仅当其语法是等价的合一就是寻找项对变量的置换而使表达式一致的过程归结原理的应用
第十七章概率推理决策理论=概率理论+效用理论
P(类别|特征)=p(特征|类别)*p(特征)/p(特征)
贝叶斯网络：一种使用简单局部分布（条件概率）描述复杂联合分布的技术
是一个有向无环图，也称之为图模型变量之间的依赖关系本质上表示任何完全联合概率分布贝叶斯网络画法以及计算
条件概率表CPTS
因果模型和诊断模型。Tversky和Kahneman发现，老练的医生更喜欢给出因果规则。1982
规范分布：完整的概率分布表能够通过确定所使用的模式的名称，并提供少量的几个参数来指定
确定性节点：子节点完全由父节点决定噪声或：有可能是a引起，但是a不一定引起遗漏节点：etc.连续变量：离散化
贝叶斯网络中的精确推理
证据变量，查询变量，隐藏变量归一化方法p(x|e)=a*p(x,e)=a*p(x,e,y)按y取和,a=1/p(e)，然后就好算了已知，一个事件e={JohnCalls=true,andMaryCalls=true}，试问出现盗贼的概率是多少？
变量消元法
精确推理，复杂性高度依赖网络结构
第十八章样例学习学习反馈：有监督无监督强化学习：给当前输入一个评价，不会给出具体期望输出前提条件：一致假设：对训练集中的x都一致不同假设可能拟合不同决策树：一个节点一个节点根据属性做选择的树如何选择决策树学习的属性：信息增益（通过信息内容或熵定义选择信息增益最大的作为决策树节点的特征决策树终止增长：当该节点下面的所有记录都属于同一类，或者当所有的记录属性都具有相同的值时需要剪枝防止过拟合人工神经网络输入输出隐藏层BP神经网络：三层或三层以上的多层前馈神经网络，按梯度算法使计算输出与实际输出的误差沿逆传播修正各连接权值的神经网络模型。信号前向传播，误差反向传播。训练过程利用随机数初始化权重（-1.0—1.0，或-0.5—0.5）将训练集样本逐一的输入到网络中对于每一个样本利用单元全部输入的线性组合和单元的偏置计算单元的净输入将激活函数作用于单元的净输入，得到单元输出；计算误差；修改权重和偏置值。更新方法：实例更新；周期更新终止：收敛；周期到了；准确率可以会考人工神经网络的权重修正以及误差的计算！还有传播过程计算！会考一道大题！！多看看这块蛮重要的！