第一章
回溯策略
盲搜的一种。
在当前状态未使用过的规则中找到第一条可应用的规则，应用于当前状态，得到的新的状态重新设置为当前状态，并重复以上搜索。
如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜索，直到找到问题的解或者试探了所有可能仍找不到问题的解为止。
递归法是常见的回溯法。
图搜索策略
无信息图搜索
- 深度优先
所谓深度优先搜索，就是在每次扩展一个结点时，选择到目前为止深度最深的结点优先扩展。
- dfs不但不能保证找到最优解，也不能保证一定能找到解。
- 如果状态空间是有限的，则可以保证找到解。
- 如果状态空间是无限的，可能会跌入“深渊”。
- 宽度优先
在每次扩展一个结点时， 每次选择深度最浅的结点进行扩展。
- 当问题有解时，bfs一定能找到解，并且在单位耗散的情况下，可以保证找到最优解。
启发式图搜索
- A算法
定义一个评价函数f，每次对当前的搜索状态进行评估，招呼一个最有希望的结点来扩展。
评价函数：
f(n) = g(n) + h(n)
其中n是被评价的结点。
g* (n) ： 表示从初始结点到结点n的最短路径的散耗值。
h* (n) ： 表示从结点n到目标结点的最短路径的散耗值。
f* (n) : 从初始结点经过n结点，到目标结点最短路径的散耗值。
f(n) ，g(n)， h(n) 则是对*值的预测。
- 在A算法中，h（n）恒等于 0，则A算法演变为动态规划算法。
在实际的问题中，h（n）常常难以定义，所以动态规划仍然是常用的算法。
动态规划实际上是分支界限法的改进。
- 最佳图算法 A*算法
在算法A的评价函数中，当h（n）满足h（n）<= h * (n) ，即对h(n)的估计总是保守的估计，则这个算法成为A *算法。
- 当问题有解时，A *算法一定可以找到一条到达目标结点的最佳路径，如h(n)恒等于 0的极端情况（动态规划），一定可以找到最佳路径。如果此时g恒等于d（deep）则算法等同于bfs。
影响A *算法的三个因素：
- 路径的散耗值
- 求解路径时所扩展的结点数（从扩展结点的角度来看h == h *扩展的结点数最少，但是会造成h的计算复杂）
- 计算h所需要的工作量
第二章 与或图搜索
AO *算法
- 扩展：完成自顶向下的图生成操作，先通过有标记的连接符，找到目前为止最好的局部有解图。然后对其中一个非终结点进行扩展并对其后继结点赋估计散耗值和加能解标记。
- 修正：完成自下向上的散耗值修正计算，连接符（即指针）的标记以及结点的能解标记。
博弈树
极大极小搜索过程
假定有一个评价函数可以对所有棋局进行评估，当评价函数值大于0时，表示棋局对我方有利，对对方不利。当评价函数小于0时，表示棋局对对我方不利，对对方有利。
在只看一步棋的情况下，我方一定走评价函数值最大的一步棋，而对方一定走评价函数值最小的一步棋。
a-贝塔搜索
只要发生a（后基层） >= 贝塔（先辈层），就终止该层的搜索。
- 比较在极大和极小层，同类层中对比没有意义。
- 比较的是先辈层，不止是父辈层。
- 当只有一个结点的值“固定”后，其值才能够向其父结点传递。
- 该方法得到的方法和极大极小的方法得的结果是一致的。
第三章 谓词逻辑与归结原理
命题逻辑
命题逻辑是数理逻辑的一个重要组成部分。
命题
命题公式
单个常量或变量的命题称作合式公式。联结词联结的合式公式的组合也是合式公式。合式公式的有限次组合构成的字符串称为命题公式。
意义
命题逻辑演算扩展了布尔代数，为人们提供了描述特征的约定和进行推理的必要工具。命题逻辑有数理逻辑作为坚实的理论支柱，同时又是谓词逻辑的基础，对于人工智能知识表示与推理研究具有重要的意义。
命题逻辑的归结法
归结原理依赖于一个单一的规则，即：
p V q 和 ~q V r都为真，则p V r为真。
此规则可以由真值表证明是正确的。
证明一个定理成立，就要证明该定理在这个域中每个点的情况下都成立，当域是不可数的显然无法解决。
Herbrand定理就是把证明永真转换为不可满足（只要有限归结出Nil即可）
归结原理的理论基础是Herbrand定理，其基本思想就是：
将待证明逻辑公式的结论，通过等值公式转换成附加前提，再证明该逻辑公式是不可满足的。
归结原理是在逻辑逻辑公式的子句集合之上进行归结的。
归结法证明过程
- 建立待归结命题公式。首先根据反证法将所求证的问题转换为命题公式，求证其是矛盾式（永假式）。
- 求合取范式
- 建立子句集
- 归结，对子句集中的子句使用归结规则：
- 归结式作为新子句加入子句集参加归结
- 归结式为空子句Nil，停止。
得到空子句Nil，表示S是不可满足的（矛盾），故原命题成立。
归结法的完备性
- 归结法的完备性： A->B成立，那么归结过程将能够归结出空子句。因而可以说归结方法是完备的。
- 归结法的不完备性：A->B不成立，使用归结方法得不到任何结论。
最终可以认为归结方法是半完备的。
谓词逻辑
命题逻辑有其局限性，不能表达原子单元的内部结构。谓词逻辑能跟即指明事物的名称又能指明有关该事物性质（细节）。
与命题逻辑相比，谓词更加细化：
- 表达能力强（表达层次）
- 谓词可以代表变化
- 在不同的知识之间建立联系
层次、变化、联系
谓词的知识表示
谓词表示的知识之间可看作一种映射关系。知识之间的关系可以映射为关系谓词，知识的常量可以映射为谓词表示中的常量，谓词公式中的解释便表示了知识具体内容的真伪性。
谓词逻辑归结原理
基本原理与命题逻辑一样，以Herbrand为基础，与命题逻辑不同的是，谓词逻辑有谓词、变量和函数，所以在生成子句集之前要对逻辑公式做一些处理，将其转换为Skolem标准型，然后在子句集的基础上再进行归结，其中还设计到置换合一。
Skolem标准型
- 前束范式
- 去掉->
- ~深入内部
- 更换每个辖域的变量名不同
- 两次左移
- Skolem标准型
- 消去存在量词（看其在哪些任意量词的范围，换成函数表示）
- 略去任意量词
Skolem定理：证明谓词公式的任意公式都可以转换为与之等价的前束范式。
子句集
归结法和其他推理方法的比较
语义网络、框架表示、产生式规则等知识表示方法都是以逻辑推理方法为前提的。即有了规则和条件，就可以根据一定的规则和公理找到结果。是一个循序渐进的过程。
而归结法没有这样的循序渐进的过程，而是在一个规则（p V q 和 ~q V r都为真，则p V r为真。）指导下，进行自动推导。
置换和合一
- 置换
在谓词公式中用置换项去置换变量 - 合一
寻找相对变量的置换，使两个谓词公式一致。
归结式
在谓词逻辑下去两个子句的归结式，和命题逻辑一样是消去互补对，但需要考虑变量合一与置换。
归结的过程
-
写出谓词关系表达式
-
用反演法写出谓词表达式
-
化Skolem标准型
-
求取子句集S
-
对S中可归结的子句做归结
-
归结式仍放入S中，反复归结过程
-
得到空子句
-
命题得证
归结过程控制策略
- 要解决的解决问题是归结方法的知识爆炸
- 控制策略的目的主要是归结点尽量少
- 控制策略的原则是删除不必要的子句，对参加归结的子句加以限制
- 给出策略，便于选择合适的子句进行归结，避免多余的，不必要的归结式出现。
语义树
将子句集S的所有可能解释展示在一棵树上，今儿观察每个分支对应的S的逻辑真值是真是假。
第四章 知识表示
知识表示的方法
语义网络
语义网络是一种用实体以及语义关系来表达知识的知识表达方式。
产生式
产生式表示法同行用于表示事实、规则及它们的不确定度量，适合于表示事实性知识和规则性知识。
框架表
框架表示法是以框架理论为基础发展起来的一种结构化的知识表示，它适用于表达多种类型的知识。
几种知识表示方法的优缺点。
归结法和其他推理方法的比较
语义网络、框架表示、产生式规则等知识表示方法都是以逻辑推理方法为前提的。即有了规则和条件，就可以根据一定的规则和公理找到结果。是一个循序渐进的过程。
而归结法没有这样的循序渐进的过程，而是在一个规则（p V q 和 ~q V r都为真，则p V r为真。）指导下，进行自动推导。
第五章 不确定推理方法
不确定推理是指那种建立在不确定性知识和证据的基础上的推理。它实际上是一种从不确定的初始证据出发，通过运用不确定性知识，最终推出既保持一定程度的不确定性，又是合理的基本合理结论的推理过程。
不确定证据---不确定知识--》不确定结论，又基本合理
为什么要采取不确定推理？
一个人工智能系统，由于本身的不精确和不完全，采用标准逻辑意义下的推理方法难以达到解决问题的目的。对于一个智能系统来说，知识库是其核心。在这个知识库中，往往大量包含模糊性、随机性、不可靠性或不知道等不确定性因素的知识。为了解决这种条件下的推理计算问题，不确定性推理方法应运而生。
不确定性推理的依据是什么？
不确定推理中要解决哪些基本问题？
- 表示问题：用什么方法描述不确定性
- 计算问题：不确定性的传播和更新，即获得新的信息的过程。
- 语义问题：如何解释上述的表示和计算的含义。
不确定性推理可以分为哪几种类型？
贝叶斯网络：
贝叶斯网络结构+条件概率表CPT 有向无环图
在实际中，相关因素繁多，二千很多概率值是无法得到的，所以在推理中引入大量的近似计算会产生误差。
主观贝叶斯：
一种不确定推理模型，成功应用在地矿勘探系统中，引入了两个数值（LS, LN），前者体现规则成立的充分性，后者表现了规则成立的必要性。
- 优点：是直观、明了。
- 缺点：要求部分事件独立（无关），实际上是不可能的，由此可能引起一系列误差。
确定性方法（可置信度方法CF）：
（现象+经验+相信程度）
随即不确定的一种推理模型，以产生式作为知识的表示方法应用在医疗诊断专家系统中。
CF方法的宗旨不是理论上的严密性，而是处理问题的可用性。
-
优点：
CF方法主要优点是通过简单的计算就可以使得各方的不确定性得到传播，最终得到系统结果。
CF值的物理意义明确，并且可以将信任与不信任清楚地分开。同时CF方法本身也比较容易理解和实现。 -
缺点：
不能一成不变的应用到其他领域，甚至不能适用于所有的科学领域。推广至其他领域的时候需要做具体的修改。
证据理论：
信任函数， 广义概率论，表达不知道
把证据的信任函数与概率的上下限值相联系，提出的一种构造不确定推理模型的一般框架。主要用于处理那些不确定、不精确以及间或不准确的信息。引入了信任函数，满足了概率论的弱公理。当概率值已知的时候，证据理论就变成了概率论。概率论是证据理论的一个特例，有的时候也称证据理论为广义概率论。
特点：满足比贝叶斯更弱的条件，具有直接表达“不知道”和“不确定”的能力。
机器学习
概念
研究如何使用机器来模拟人类学习活动的一门学科。
学习是一个有特定目的的知识获取和能力增长过程，其内在行为是获得知识、积累经验、发现规律等，其外部表现是改进性能、适应环境、实现自我完善等。
机器学习应用
决策树学习
ID3构造决策树
选取具有最高收益的属性进行划分。
最高收益：信息量最大的属性或则说让系统熵降低最多的属性(条件熵最小)。
优缺点
分类测试速度块，用于大数据库的分类问题。不好理解，不能处理未知属性值，对噪声没有很好的处理办法。
第六点五章 神经网络
符号化主义和连接主义
符号主义创造专家，连接主义创造婴儿。
生物神经元的基本模型
y=f(u),称为特性函数，也称为激活函数，可以看作神经元的数学模型。
神经网络的基本模型
前馈型网络
信号由输入层到输出层单向传输。每层的神经元仅与前层的神经元相连接，只接收前层传输来的信息。
输入输出有反馈的前馈型网络
输出层存在一个反馈回路到数层的回路，而网络本身还是前馈型。
前馈内层互联
顾名思义
反馈型全联网络
网络所含的神经元只有有互相连接的网络。
单感知器
人类历史上第一个真正成功的人工神经网络。
、
学习方法
简单感知器引入的学习算法称之为误差学习算法：
误差型(δ)学习规则：
- 选择一组初始权值wi(0)。
- 计算某一输入对应的实际输出与期望输出的误差δ。
- 如果δ小于给定值，返回2，否则继续。
- 更新权值(阈值可视为输入恒为1的一个权值)：
Δwi（t+1）＝ wi（t+1）- wi（t）
＝η[d—y(t)]xi。
η为在区间(0，1)上的一个常数，称为学习步长，它的取值与训练速度和w收敛的稳定性有关；d、y为神经元的期望输出和实际输出；xi为神经元的第i个输入。 - 返回(2)，重复，直到对所有训练样本模式，网络输出均能满足要求。
BP神经网络
BP算法基本原理
利用输出后的误差来估计输出层的直接前导层的误差，再用这个误差估计更前一层的误差，如此一层一层的反传下去，就获得了所有其他各层的误差估计。
高级搜索
局部搜索
爬山
退火模拟
解决爬山法的局部最优问题
对于随即产生的解的接收程度根据其能量有不同的接收情况。
爬山法：新解能量低(更稳定)则更新为现在解，否则不接收。
模拟退火：新解能量低(更稳定)则更新为现在解，否则根据当前的温度高低和能量情况有一定的接受概率。
新解能量低：
新解能量高：
，f(j) - f(i) >0，t越大p越接近1。温度越高越容易接受。
退火模拟必须满足的3个条件：
- 初始温度必须足够高。
- 在每个温度下，状态的交换必须充分。
- 温度T的下降必须足够缓慢。
网友评论