人工智能专题复习
Made by © Isaac. Ty
知识表示
表示方法
直接表示、逻辑表示、产生式规则表示、语义网络表示法、框架表示法、脚本方法、过程表示
逻辑表示法
- 一阶谓词逻辑式谓词逻辑中最直观的一种逻辑。以谓词形式来表示动作的主体、客体，客体可以有多个。
-
谓词逻辑规范表达式：
P
(
x
1
,
x
2
,
x
3
,
…
)
，P是谓词，
x
i
是主体与客体 - 存在问题：谓词表示越细，推理越慢、效率越低，但表示清楚
产生式规则表示法
-
可以看成断言是一个语言变量的值或是多个语言变量间的关系的陈述句，语言变量的值或语言变量间的关系可以使一个词，不一定是数字
-
基本特征：
- 数据库：存放构成产生式的基本元素，又是产生式的作用对象
- 一组规则：产生式本身
- 一个解释程序：从匹配成功的规则中选出一个加以执行
-
基本结构：
- 工作存储器(数据库)：存放当前已知的数据，包括推理过程中形成的中间结论。
- 产生式规则：每条产生式分左右两个部分，左部表示激活条件，右部表示产生结果。
- 规则解释程序：
- 匹配器：判断规则条件是否成立
- 冲突消解器：选择可调用的规则
- 解释器：执行规则的动作。在满足结束条件时终止产生式系统
-
推理方法
正向、反向、双向、与或树
- 正向：从已知事实出发，逐步推导出最后结论。
-
反向：首先提出假设，然后验证这些假设的真假性，找到假设成立的所有证据或事实。
-
双向：既自顶向下、又自底向上作双向推理，直至某个中间界面上两方向结果相符便成功结束。
-
优点：
- 模块性：规则与规则之间相互独立
- 灵活性：知识库易于增加、修改、删除
- 自然性：方便地表示专家的启发性知识与经验
- 透明性：易于保留动作所产生的变化、轨迹
-
缺点：
- 知识库维护难
- 效率低。为了模块一致性
- 理解难。由于规则一致性彼此之间不能调用
语义网络表示法
- 表示形式：每一个要表达的事实用一个“结点”表示，而事实之间用“弧线”表示。即，有向图表示的三元组（结点1，弧，结点2）连接而成。
-
类属关系：类属关系是指有
共同属性
的不同事物间的分类关系、成员关系或实例关系
- 常见属性：
- A-Kind-of 表示一个事物是另一个事物的一种类型
- A-member-of 表示一个事物是另一个事物的成员
- Is-a 表示一个事物是另一个事物的实例
-
包含关系：也称聚类关系，是指具有组织或结构特征的“部分与整体”之间的关系。（包含关系一般不具备属性的继承性）
- 常见属性：
- Part-of 一个事物是另一个事物的一部分
-
属性关系：事物和其他属性之间的关系
- 常见属性：
- Have 表示一个节点具有另一个节点所描述的属性
- Can 一个节点能做另一个节点的事
-
位置关系：不同事物在位置方面的关系
- 常见位置关系：Located-on/-at/-under/inside/outside
-
相近关系：不同事物在形状、内容等方面相似和接近
- 常用相近关系：Similar-to 相似 Near-to 接近
-
时间关系：指不同事件在其发生时间方面的先后关系
- 常用时间关系：Before 表示一个事件在另一个事件之前发生 After 一个事件在一个事件之后发生
- 多元逻辑关系：
-
推理方法
- 网络匹配：结构上的匹配，包括结点和弧的匹配
- 继承推理：利用具有继承性质的语义联系建立一些并不一定显示存在于语义网络知识库中的网络结构。
-
结论：
- 语义网络图的好处是直观、清晰
- 缺点是表达范围有限。
-
特点：
- 结构性好：语义网络是一种结构化的知识表示方法，能够把事物的属性和事物间的各种语义关系显示地表示出来
- 联想性：语义网络作为人类联想记忆模型提出来，强调的就是事物之间的语义关系
- 自然性：语义网络实际上是一个带有标示的有向图，可直观的把事物的属性及事物间的语义联系表示出来，便于理解
框架表示
- 定义：框架是由若干个结点和关系（统称槽）构成的网络。是语义网络更一般化形式的一种结构。同语义网络没有本质区别。
- 表示形式：框架名、槽名、侧面、值
- 推理方法：没有固定的推理机理。遵循匹配和继承的原理
-
软件开发过程中框架理论的使用
- 人们将相同类型问题的解决途径进行抽象，抽取成一个应用框架Framework，提供一套明确机制，让开发人员很容易的扩展和控制整个Framework开发上的结构。
- 为某一特定目的实现一个基本的、可执行的架构。包含了应用程序从启动到运行的主要流程，流程中无法确定的步骤留给用户来实现。程序运行时框架系统自动调用用书实现的功能组件。系统的行为是主动的。
-
性质：
- 对事物进行描述。
- 通过它对一些从感官中没有直接得到的信息进行预测。
- 可以利用框架知识进行判断推理
- 可以通过来认识某一类事物
- 可以通过实例修正框架对某些事物的不完整描述
脚本表示
- 脚本方式式采用一个专用的框架来表示特定领域的知识
- 脚本通过元语作为槽名来代表要表示的对象的基本行为
- 有点像电影剧本
产生式系统
产生式系统的基本组成
组成三要素(*)
-
一个综合
数据库
—— 存放信息 -
一组产生式
规则库
—— 知识 -
一个控制系统
推理机
—— 规则的解释或执行程序（控制策略、推理策略）
产生式系统定义：把一组产生式放在一起，让它们相互配合，协同工作，一个产生式生成的结论可以供另一个产生式作为前提使用，以这种方式求得解决问题的系统叫作产生式系统。
产生式系统的特点
- 数据驱动：从已知事实出发
- 模块化：知识的无序性
- 控制系统与问题无关
- 类似人类认识的过程：规则似乎式模拟人类如何解决问题的自然方法
产生式系统的类型(*)
- 正向推理：从已知事实出发，通过规则库求得结论，也称自底向上或者数据驱动的方式。F规则
- 反向推理：从目标出发，反向使用规则，求得已知事实，也称自顶向下推理方式或者目标驱动方式。B规则
- 双向推理：既自顶向下又自底向上，直至达到某个终结环节两个方向的结果相符边成功结束。
产生式系统总结
- 产生式系统是最简单的知识表示方法，也是应用最广泛的知识表示方法，适于表示各种启发式的经验性关联规则，领域专家无需知识工程工具就能够把自己的知识转化成IF-THEN规则
- 规则选择效率较低，控制策略不灵活，知识表示形式单一
产生式系统的搜索策略
产生式系统的搜索策略
-
盲目搜索
：也称为无信息搜索，即只按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。 -
启发式搜索
：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向进行，加速问题的求解过程并找到最优解。
图搜索策略
- 回溯搜索：只保留从初始状态到当前状态的一条路径
- 图搜索：保留所有已搜索过的路径
基本概念
- 节点深度： 根节点深度 = 0 ，其他节点深度 = 父节点深度 + 1
-
路径： 设一节点序列为
(
n
0
,
n
1
,
…
…
,
n
k
)
，对于i = 1,…,k，若节点
n
i
−
1
具有一个后继节点
n
i
，则该序列称为从
n
0
到
n
k
的路径 -
路径的耗散值： 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用
C
(
n
i
,
n
j
)
表示从n~i~到n~j~的路径的耗散值 -
扩展一个节点： 生成出该节点所有后继节点，并给出它们之间的耗散值。
E
x
p
a
n
d
(
n
)
。 - 辅助存储表：open表：未扩展节点表，closed表：已扩展节点表
无信息图搜索过程
-
深度优先搜索：
- 栈实现
- 一般不能保证找到最优解。当深度限制不合理时，可能找不到解。可将算法改为可变深度限制。最坏的情况搜索空间等同于穷举
- 缺点：如果目标节点不在搜索所进入的分支上而该分支又是一个无穷分支，则就得不到解。
- 优点：如果目标节点恰好在搜索所进入的分支上，则可以较快地得到解
-
宽度优先搜索：
- 队列实现
- 当问题为单位耗散值时，且问题有解时，一定能找到最优解
- 方法与问题无关，具有通用性。
- 效率较低，属于图搜索方法
- 缺点：当目标节点距离初始节点较远时会产生许多无用的节点，搜索效率低
- 优点：只要问题有解，则总可以得到解，是完备的，而且是最短路径的解。
-
回溯与宽度优先方法结合
- 目的：解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题
- 思想：首先个给回溯法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或遍历所有分支
启发式图搜索
利用知识来引导搜索，达到减小搜索范围，降低问题复杂度的目的。
-
启发信息的强度
- 强：降低搜索工作量，但可能导致找不到最优解。
- 弱：一般会使工作量降低不如强的多，极限情况下变为盲目搜索，但是可能会找到最优解
-
启发信息
引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。
-
基本思想
定义启发函数
f
，对当前搜索状态进行评估，找出一个最有希望的节点来扩展。 -
A算法与A*算法定义
或图通常采用如下形式的
估计函数
时，称为A算法。
f
(
n
)
=
g
(
n
)
+
h
(
n
)
g
(
n
)
表示从
s到n点费用的估计
，因为n为当前节点，搜索已达到n点，所以g
(
n
)
可
计算出。
h
(
n
)
表示从
n到目标接近程度的估计
，因为尚未找到解路径，所以
h
(
n
)
仅仅是估计值。 -
A算法(最好优先搜索)
，适用于
或图
搜索。在所有待扩展结点中优先选择最有希望的结点进行扩展。在搜索过程中如果早期选择了一个错误，最好优先搜索提供了
修改的机会
，这是最好优先搜索算法的关键。 但是
A算法并未显示地给出如何定义
启发函数
，A*算法就是对A算法的启发函数加上限制后的一种算法
。
符号定义
-
g
(
n
)
从S到n的最短路径的
耗散值
-
h
(
n
)
从n到G的最短路径的
耗散值
-
f
(
n
)
=
g
(
n
)
+
h
(
n
)
从S经过n到G的最短路径
耗散值
-
g
′
(
n
)
,
h
′
(
n
)
,
f
′
(
n
)
分别式
g
(
n
)
,
h
(
n
)
,
f
(
n
)
的估计值
算法特征
f
(
n
)
=
g
(
n
)
+
h
(
n
)
-
若令
h
(
n
)
≡
0
，则A算法相当于宽度优先搜索，因为上一层节点的搜索费用一般比下一层的小 -
若
g
(
n
)
≡
0
，则相当于最佳优先搜索算法 -
g
(
n
)
≡
h
(
n
)
≡
0
相当于随机算法 -
特别是当要求
h
(
n
)
≤
h
′
(
n
)
，就称为这种A算法为A* 算法
A* 算法性质
定理1： 对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功
在A算法中，如果满足条件：
- g(n)是对g*(n)的估计 g(n)>0
- h(n)≤h*(n)
则A算法称为A*算法
产生式系统
- [ ] 与或图的搜索及与或图启发式搜索算法AO*
- [ ] 与或图搜索中的能解节点和不能解节点
- [ ] 博弈树搜索
- [ ] α-β剪枝的条件
- [ ] 使用α-β剪枝规则完成博弈树搜索的剪枝
与或图表示问题
- 与或图是一个超图，节点间通过连接符连接
- K-连接符
-
K
(
n
,
N
)
=
C
n
+
k
(
n
1
,
N
)
+
…
+
k
(
n
i
,
N
)
-
其中N为终结节点 ，
C
n
为连接符的耗散值
能解节点
- 终节点是能解节点
- 若非终节点有“或”子节点时，当前仅当至少有一能解解时，该非终节点能解
- 若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。
不能解节点
- 没有后裔的非终节点式不能解节点
- 若非终节点有“或”子节点，当前仅当所有子节点均不能解，该非终节点不能解
- 若非终节点有“与”子节点，当至少有一个子节点不能解时，该非终节点才能解
与或图启发式搜索算法AO*
-
AO* 算法两个过程
-
图生成过程，即扩展节点（利用起发信息进行）
-
计算耗散值的过程（根据与或关系）
-
-
具有最小耗散值的解图称为最佳解图，其值也用
h
∗
(
n
)
表示
博弈树搜索
-
博弈问题特点：
- 双人对弈、轮流走步
- 信息完备，双方所得到的信息一样
- 零和，对一方有利的棋，对另一方不利，不存在对双方有利或无利的棋
- 博弈过程寻找对数必败态的过程
- 双方无法干预对方选择
- 可使用图搜索，但是效率很低
-
博弈实例：
- 下棋双方对立
- 一方为正方，MAX节点
- 另一方反方，MIN节点
- 正方反方交替走步，MAX节点MIN节点交替出现
- 图中所有终结点均表示该选手必输的情况，取胜方的目标式设法使棋局发展为结束在对方走步时的终结点上。
-
博弈策略考虑问题：
-
对MIN走后的每一个MAX结点，必须证明MAX对MIN可能走的每一个棋局对弈后能获胜，即MAX必须考虑应付MIN的所有招法。因此MAX结点可看成
与结点
。 -
对MAX走后的每一个MIN结点，只需证明MAX有一步能走赢就可以，即MAX只要考虑走出一步棋使MIN无法招架。因此MIN结点可看成
或节点
。
-
对MIN走后的每一个MAX结点，必须证明MAX对MIN可能走的每一个棋局对弈后能获胜，即MAX必须考虑应付MIN的所有招法。因此MAX结点可看成
-
极大极小搜索过程—-对各个局面进行评估
- 评估目的：对后面的状态提前考虑，并且以各种状态的评估值为基础做出最好的选择
- 评估方法：用评价函数对棋局进行评估
- 赢的评估值设为+∞，输的评估值设为-∞，平局的评估值设为0
- 评估的标准：由于下棋的双方是对立的，只能选择其中一方为评估的标准方
- 由于正方和反方交替走步，因此MAX节点和MIN节点会交替出现。
-
正方（MAX节点）从所有子节点中，选取具有
最大评估值的节点
。 -
反方（MIN节点）从所有子节点中选取具有
最小评估值的节点
- 反复进行选取，可以得到双方各个节点的评估值
α
−
β
搜索过程
在极小极大搜索过程中，必须求出所有终端节点的评估值，当考虑的棋步比较多时，计算量会大大增加。为提高搜索效率，引入了通过对评估值的上下限进行估计，从而减少需进行评估的节点范围的
α
−
β
剪枝法
-
Max节点的评估下限值
α
作为正方出现的Max节点，假设它的MIN子节点有N个，那么当它的第一个MIN子节点的评估值为
α
时，对于其他子节点-
有高过
α
的，就取最高的值作为MAX节点的评估值 -
没有高估的，则该MAX的节点评估值为
α
-
总之Max节点的估计值不会低于
α
，
α
称为该MAX节点的评估下限值
-
有高过
-
MIN节点的评估上限值
β
作为反方出现的MIN节点，假设它的MAX子节点有N个，那么当它的第一个MAX子节点的评估值为
β
时，对于其他子节点-
有低于
β
的，就取那个低于
β
的值作为该MIN节点的估计值 -
没有低于的，则该MIN节点的估计值取
β
-
总之，该MIN节点的评估值不会高过
β
，这个
β
就称为该MIN节点的评估上限值
-
有低于
-
α
剪枝法设MAX节点的下限为
α
，则其所有MIN子节点中，其评估值的
β
上限小于等于
α
的节点，其以下部分的搜索都可以停止了，即对这部分进行
α
剪枝。 -
β
剪枝法设MIN节点的上限为
β
，则其所有的MAX子节点中，其评估值的
α
下限大于等于
β
的节点，其以下部分的搜索都可以停止了，即对这部分进行
β
剪枝。 -
MAX节点的下界为
α
，MIN节点的上界为
β
。则剪枝的条件为：-
祖先节点的
α
值
≥
后辈节点的
β
值时，
α
剪枝 -
祖先节点的
β
值
≤
后辈界节点的
α
值时，
β
剪枝
-
祖先节点的
经典逻辑理论
归结原理
一种定理证明方法，从理论上解决了定理证明问题。
在有限步内给予判定。
子句和子句集
子句：
- 无量词约束
- 元素只是文字的析取
- 否定符只作用于单个文字
- 元素间默认为合取
子句集：合取范式形式下的子命题（元素）的集合
文字：不含任何连接词的谓词公式
子句：一些文字的析取（谓词的和）
子句集求取： G ——>SKOLEM范式 ——>消去存在变量——>以 ， 取代
公式G和由公式求取的子句集的关系
G是不可满足的
≡
S是不可满足的。即G与S不等价，但在不可满足意义下一致
归结的一般过程
- 将命题写成合取范式
- 求出子句集
- 对子句集使用归结推理规则
- 归结式作为新子句参加归结
- 归结式为空，s不可满足的（矛盾），原命题成立
置换/合一，最一般合一者
置换：在一个谓词公式中用置换项去置换变量，形如
{
t
1
/
x
1
,
t
2
/
x
2
,
…
,
t
n
/
x
n
}
的有限集合。其中
x
i
是变量，
t
是不同于
x
i
的项；
t
i
/
x
i
表示用
t
i
置换
x
i
，并且要求
t
i
与
x
i
不相同，而且
x
i
不能循环出现在另一个t中
合一：寻找相对变量的置换，使两个谓词公式一致。设有公式集
F
=
{
F
1
,
F
2
,
…
,
F
n
}
，若存在一个置换
θ
，可使
F
1
θ
=
F
2
θ
=
…
=
F
n
θ
，则称
θ
是F的一个合一。一个公式集的合一不唯一
Skolem标准型（斯克林范式）
- 前束范式：公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式末端。
-
把所有的量词都提到前面去，然后消掉所有量词
- 原则：消去存在量词，略去全称量词
- 左边有全称量词的存在量词，消去时应该改写成为全称量词的函数；如没有则改写成常量。
- SKOLEM定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，但是前束范式不唯一
- SKOLEM标准形：消去量词后的谓词公式
用归结法证明问题(*)
归结过程的控制策略及策略的完备性
- 解决问题：归结方法的知识爆炸
- 控制策略的目的：归结点尽量少
- 控制策略的原则：给出控制策略，以使仅对选择合适的子句间方可做归结，避免多余的、不必要的归结式出现。或者说，少做些归结仍能导出空子句。
- 采用支撑集
- 线性归结：线性归结策略首先从子句集中选取一个称作顶子句的子句C0开始作归结。归结过程中所得到的归结式Ci立即同另一子句B_i进行归结得归结式Ci+1
- 单元归结：单元归结策略要求在归结过程中，每次归结都有一个子句是单元子句（只含一个文字的子句）或单元因子。显而易见，此方法可以简单地削去另一个非单子句中的一个因子，使其长度减少，构成简单化，归结效率较高。
- 输入归结
不确定性推理模型
Bayes贝叶斯网
基本概念
- 一系列变量的联合概率分布的图形表示；一个表示变量之间的相互依赖关系的数据结构；图论与概率论的完美结合
- 贝叶斯网就是一个在弧的连接关系上加入连接强度的因果关系网络。是一种变形的语义网络（特殊的有向无环图）DAG+CPT
定义
-
两个部分：DAG+CPT
-
贝叶斯网络结构图，这是一个
有向无环图
（DAG:Directed Acyclic Graph），其中图中的每个节点代表相应的变量。当有向弧由节点A指向节点B时，则称：A是B的父节点；B是A的子节点。 -
节点和节点之间的
条件概率表
（Conditional Probability Table, CPT），也就是一系列的概率值，表示了局部条件概率分布。P(node|parents) 。
-
贝叶斯网络结构图，这是一个
- 目的：由证据得出原因发生的概率。即观察到P(Y)，求P(X|Y)
计算
-
有向非循环图是各个节点变量关系传递的合理表达形式。
-
条件概率的引入使得计算较之全连接网络有了大大的简化。
-
CPT表(条件概率表)相对比较容易得到，有时可以用某种概率分布表示，需要做的只是计算表示的参数。
-
简单联合概率可以直接从网络关系上得到
-
P
(
X
,
Y
)
=
P
(
X
)
P
(
Y
|
X
)
-
P
(
X
,
Y
,
Z
)
=
P
(
X
)
P
(
Y
)
P
(
Z
|
X
,
Y
)
-
例图中的联合概率密度为：
P
(
S
,
C
,
L
,
E
)
=
P
(
E
|
S
,
C
,
L
)
∗
P
(
L
|
S
,
C
)
∗
P
(
C
|
S
)
∗
P
(
S
)
-
E与L在S条件下独立，所以
P
(
E
|
S
,
C
,
L
)
＝
P
(
E
|
S
,
C
)
L与C在S, E条件下独立，所以
P
(
L
|
S
,
C
)
=
P
(
L
|
S
)
C与S在E条件下独立，所以
P
(
C
|
S
)
=
P
(
C
)
-
独立
-
独立
-
P
(
X
,
Y
)
=
P
(
X
)
P
(
Y
)
-
P
(
X
|
Y
)
=
P
(
X
)
P
(
Y
|
X
)
=
P
(
Y
)
-
-
对于X,Y,E：X与Y在给定E的条件下独立
-
P
(
X
|
Y
,
E
)
=
P
(
X
|
E
)
-
P
(
Y
|
X
,
E
)
=
P
(
Y
|
E
)
例如
P
(
E
|
L
,
S
)
=
P
(
E
|
S
)
,
P
(
L
|
E
,
S
)
=
P
(
L
|
E
)
-
-
多个变量组：d分离(d-separate)
-
P
(
X
1
,
X
2
,
…
,
X
n
|
Y
1
,
Y
2
,
…
,
Y
m
,
E
1
,
E
2
,
…
,
E
p
)
=
P
(
X
1
,
X
2
,
…
,
X
n
|
E
1
,
E
2
,
…
,
E
p
)
-
如果一组节点
X
在给定
E
的条件下，从
X
i
到
Y
j
的每一条通路都被
E
k
d分离，则称X独立于另一组节点Y -
D分离是一种寻找条件独立的有效方法
-
D分离-串行Linear连接
X
→
Z
→
Y
串行事件中，事件X通过事件Z影响事件Y，反之事件Y也是通过事件Z影响事件X。但是如果原因证据Z是给定的，那么通道就被阻塞，X和Y就是独立的了。
X
,
Y
被节点
Z
D分离- D分离-分叉Diverging连接
如果父节点Z是已知的，没有更多的信息能够通过Z影响到所有子节点。同理父节点Z是已知时，子节点
X
,
.
.
.
,
N
是相互独立的。称子节点
X
,
…
,
N
是被
Z
节点D分离的- D分离-汇集Converging连接
如果不从父节点得到推断，子节点Z就一无所知，那么，父节点是相互独立的，它们之间没有相互影响。
但是如果某事件影响了Z，那么，各个父节点就不是相互独立的了。该事件可以直接影响Z，也可以通过它的后代节点影响Z。这种现象称作条件依存。总之，如果子节点有了变化，或子节点的后代节点发生变化，信息是可以通过汇集连接传播的。
E能D分离S和C
-
推理
- 因果推理是从起因到效果。 主要操作：按照给定证据的V和它的所有双亲的联合概率，重新表达给定证据的寻问结点的所求条件概率。
- 诊断推理是从效果到起因。 主要思想：利用贝叶斯规则将诊断推理转化为因果推理
-
辩解推理：因果推理与诊断推理结合使用。推理使用嵌入在一个诊断推理中的因果推理。
-
计算结果的语义解释（*）
主观Bayes贝叶斯网
主观Bayes：
-
贝叶斯规则
P
(
B
|
A
)
=
P
(
A
|
B
)
P
(
B
)
P
(
A
)
- 思路：先定好怎么办，再凑公式
-
LS：充分似然率
L
S
=
O
(
B
|
A
)
O
(
B
)
=
P
(
A
|
B
)
P
(
A
|
−
B
)
，A为真时对B的影响 -
LN：必要似然率
L
N
=
O
(
B
|
−
A
)
O
(
B
)
=
P
(
−
A
|
B
)
P
(
−
A
|
−
B
)
，A为假时对B的影响
几率函数O(x) ：
O
(
x
)
=
P
(
x
)
1
−
P
(
x
)
- P(x)=0，O(x)=0 假；逻辑不发生
- P(x)=0.5，O(x)=1 可能发生/不发生
- P(x)=1，O(x)=∞ 真；逻辑发生
-
O
(
B
|
A
)
=
L
S
∗
O
(
B
)
-
O
(
B
|
−
A
)
=
L
N
∗
O
(
B
)
取值规则
- LS , LN ≥ 0，不独立。都在[0,∞)
- LS , LN 不能同时>1 或 <1 。（证明）
- LS , LN 可同时 = 1
计算A1,A2必然发生时，求结论B1的更新值
-
A 必然出现时 P(A)=1:
-
O
(
B
)
=
P
(
B
)
1
−
P
(
B
)
-
O
(
B
|
A
)
=
L
S
∗
O
(
B
)
-
O
(
B
|
−
A
)
=
L
N
∗
O
(
B
)
-
P
(
A
)
=
O
(
A
)
1
+
O
(
A
)
-
确定性方法-CF模型
规则A —B，可信度表示为CF(B,A)：
-
C
F
(
B
,
A
)
=
M
B
(
B
,
A
)
−
M
D
(
B
,
A
)
- CF是由证据A得到的假设B的确定性因子
-
MB是证据A得到假设B的
信任增加度量
-
MD是证据A得到的假设B的
不信任增加度量
- 确定性因子把信任与不信任组合在了一起
MB和MD表达式（*）
M
B
(
B
,
A
)
=
{
1
m
a
x
{
P
(
B
|
A
)
,
P
(
B
)
}
−
P
(
B
)
1
−
P
(
B
)
P
(
B
)
=
1
其
它
M
D
(
B
,
A
)
=
{
1
m
i
n
{
P
(
B
|
A
)
,
P
(
B
)
}
−
P
(
B
)
−
P
(
B
)
P
(
B
)
=
0
其
它
CF(B,A)表达式 （*）
C
F
(
B
,
A
)
=
⎧
⎩
⎨
⎪
⎪
P
(
B
|
A
)
−
P
(
B
)
1
−
P
(
B
)
P
(
B
|
A
)
−
P
(
B
)
P
(
B
)
P
(
B
|
A
)
≥
P
(
B
)
P
(
B
|
A
)
<
P
(
B
)
CF(B,A)表示的意义
- 证据为真时，相对于P(~B)=1-P(B)来说，A对B为真的支持程度。即A发生更 支持B发生
- 相对于P(B)来说，A对B为真的不支持程度。即A发生不支持B发生
-
−
1
≤
C
F
(
B
,
A
)
≤
1
CF的特殊值
- CF(B,A) = 1 前提真，结论必真 P(B|A)=1
- CF(B,A) = -1前提真，结论必假 P(B|A)=0
- CF(B,A) = 0 前提真假与结论无关 P(B|A) = P(B)
- 实际中CF(B,A)由专家确定，并非由P(B|A),P(B)计算得到
证据A的可信度表示为CF(A)
-
特殊值
- CF(A)=1 前提肯定真
- CF(A)=-1 前提肯定假
- CF(A)=0 对前提一无所知
- CF(A)>0 , 表示A以CF(A)程度为真
- CF(A)<0 , 表示A以CF(A)程度为假
确定性方法-CF模型计算
- 规则推理计算
- 规则合成计算
-
简单的推理计算
- 规则推理计算 1，2，（3，4）
- 是否必然发生，都乘概率，只是必然概率为1
- $$
证据理论（DS）
-
基本概率分配函数m(x)：
-
m
(
x
)
:
2
U
→
[
0
,
1
]
，在U的幂集上定义，取值[0,1] - m(A)表示了证据对U的子集A成立的一种信任度
- A属于U，且不等于U，表示对A的精确信任度
- A等于U，表示这个数不知如何分配
-
- 信任函数Bel(A)：集合和他的子集合的信任总和
- 似然函数
机器学习
概念
机器学习可以分为几类
常见的机器学习方法可分为 连接学习、归纳学习、分析学习和遗传算法与强化学习等
机器学习系统
应有环境、知识库、学习环节和执行环节四个基本部分组成
实例学习及实例学习的两个空间模型
- 例子空间(实例)—>解释例子(泛化)—>规则空间(概念)—>选择例子(例化)
- 例子空间的描述语言可以描述所有例子；规则空间的描述语言可以描述所有规则
-
例子空间
- 示教例子的质量: 不能有错，同时提供正例和反例，逐步分批由选择地送入。
- 选择的条件：最有力地划分规则空间；证实肯定假设规则的集合；否定假设规则的集合。
-
解释例子(泛化)
- 解释例子的目的是从例子中提出用于搜索空间的信息。把示教例子变换成易于进行符号归纳的形式（有时很难）
-
规则空间(最根本，真正学习的部分)
- 定义：一套符号来规定表示规则的算符、术语，所有的描述都在其中。
- 归纳方法：从一般到特殊
-
对规则空间的要求：
- 规则空间表达能力与规则空间搜索难度
- 表示和例子的一致
- 引入新术语（规则空间）
归纳学习及学习的偏置：变形空间与候选消除学习
学习过程
- 实例学习：从特殊的训练样例中得到的普遍规律
- 归纳：保证输出的假设能与训练样例相拟合
- 归纳假设的一个基本假定（偏置）：对于未见实例最好的假设就是与训练数据最佳拟合的假设
- 归纳学习假设：任一假设如果在足够大的训练样例样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数
假设从一般到特殊的转化
任何被较特殊的假设划分为正例的实例都会被较一般的实例划分为正例
Find-S算法：寻找极大特殊假设
使用more_general_than偏序的搜索算法，从H中最特殊假设（最小假设）开始，然后在假设覆盖正例失败时将其一般化
Find-S算法
- 将h初始化H中最特殊假设
-
对每个正例x
-
对h的每个属性约束
a
i
，如果x满足
a
i
，那么不做任何处理 -
否则将h中
a
i
替换为x满足的另一个更一般约束
-
对h的每个属性约束
- 输出假设h
Find-S算法重要特点：对以属性约束的合取式描述的假设空间H，保证输出为H中与正例一致的最特殊的假设
变形空间和候选消除算法
候选消除算法输出与训练样例一致的
所有假设的集合
；在描述这一集合时不需要明确列举所有成员；可用于启发式搜索控制规则来表示，容错性能差。
-
一致的定义：一个假设h与训练样例集合D一致，当且仅当对D中每一个样例
<
x
,
c
(
x
)
>
<script type="math/tex" id="MathJax-Element-122"></script>都有h(x)=c(x)
-
先列表后消除法
能表示变型空间的一种方法是列出其所有成员
- 优点：保证得到所有与训练数据一致的假设
- 缺点：非常繁琐地列出H中的所有假设，大多数实际的假设空间无法做到。
-
变型空间的更简洁表示
变型空间被表示为它的极大一般g和极大特殊s的成员，这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变型空间。
变型空间方法的初始G集是最上面的一个点（最一般的概念），初始S集是最下面的直线上的点（训练正例），初始H集是整个规则空间。
在搜索过程中，G 集逐步下移（进行特例化），S 集逐步上移（进行泛化），H 逐步缩小。最后H收敛为满足要求的概念。
搜索：使用一个可能合理的假设规则的集合H，H是规则空间的子集，是规则空间中间的一段。
H中最一般的元素组成的子集称为G集合，最特殊的元素组成的子集称为S集合。（H是上界G和下界S之间的一段。）
学习基本思想：尽可能合理的进行特殊化和一般化处理，通过搜索减小H，找到一个假设规则。
具体方法：消除候选元素法
-
形式化定义
- 极大一般：更一般中的极大者(元)-下确界
- 极大特殊:更特殊中的极小者(元)-上确界
-
关于假设空间H和训练数据D的一般边界G，是在H中与D相一致的
极大一般
成员的集合 -
关于假设空间H和训练数据D的特殊边界S，是在H中与D相一致的
极大特殊
成员的集合
-
候选消除算法
将G集合初始化为H中极大一般假设
G
0
=
{
<
∅
,
∅
,
∅
,
∅
,
∅
,
∅
,
∅
>
}
将S集合初始化为H中极大特殊假设
S
0
=
{
<
?
,
?
,
?
,
?
,
?
,
?
,
?
>
}
-
初始化G和S
-
如果d是一个
正例
从G中移去所有与d不一致的假设
对S中每个与d不一致的假设s，从S中移出s，把s的所有的极小一般（泛化）式h加入到S中，其中h满足h与d一致，而且G的某个成员比h更一般
-
如果d是一个
反例
从S中移去所有与d不一致的假设
对G中每个与d不一致的假设g，从G中移出g，把g的所有的极小特殊（例化）式h加入到G中，其中h满足h与d一致，而且S的某个成员比h更特殊
正例去掉G中不符合的概念，然后修改S，归纳出最特殊的结果，尽量少改S
反例去掉S中符合的概念，然后修改G，做特殊化得到最一般的结构，尽量少改G
-
-
变型空间法的优缺点
- 搜索空间太大，有可能引起计算爆炸问题（规则总地来说是越扩越多）
- 抗干扰性差，所有数据驱动方法的通病。解决方法：例子一组一组地给。
- 采用析取规则，即此算法不可能发现“或”的关系。
-
归纳偏置
归纳学习需要的预先假定，称为归纳偏置
-
一个有偏的假设空间
在EnjoySport例子中，假设³空间限制为只包含属性值的合取（肯定有偏）
因为这一限制，导致假设空间不能够表示简单一些的析取形式的目标概念。
-
无偏的学习器
为了保证目标概念在假设空间中，需要提供一个假设空间，它能表达所有的可教授概念。换言之，它能表达实例集X的所有子集。
-
EnjoySport的无偏形式
带来的问题：概念学习算法无法从训练样例中泛化。
要想获得单个目标概念，就必须提供X中所有实例作为训练样例
-
无偏学习的无用性
归纳学习的一个基本属性：学习器如果不对目标概念的形式做预先的假定，它从根本上无法对未见实例进行分类
-
基于解释的学习(*)
基于解释的学习，不考虑很多实例，采用演绎推理，少用归纳。可以克服归纳学习的不可靠问题。
基本思想：利用单个问题的求解例子，依据领域知识对实例进行详细分析，构造求解过程的因果关系的解释结构，并获取控制知识，然后对解释进行推广得到一般性描述，以便用于指导以后求解类似问题。
从本质上是属于演绎学习。
解释的过程是为获得相似问题的解决方法（概念）
决策树学习方法，神经网络学习方法(不要求计算)
决策树(Decision Tree)
一种描述
概念空间
的有效的归纳推理办法。基于决策树的学习方法可以进行不相关的多概念学习，具有简单快捷的优势，已经在各个领域取得广泛应用。
-
基本思想
以信息熵为度量标准，构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的示例都属于同一类。
-
基本概念
决策树学习采用的是自顶向下的递归方法
决策树的每一层节点依照某一属性值向下分为子节点，待分类的实例在每一节点处与该节点相关的属性值进行比较，根据不同的比较结果朝相应的子节点扩展，这一过程在到达决策树的叶节点时结束，此时得到结论。
从根节点到叶节点的每一条路经都对应着一条合理的规则，规则间各个部分（各个层的条件）的关系是合取关系。整个决策树就对应着一组析取的规则。
决策树学习算法的最大优点是，它可以自学习。
在学习的过程中，不需要使用者了解过多背景知识，只需要对训练例子进行较好的标注，就能够进行学习。如果在应用中发现不符合规则的实例，程序会询问用户该实例的正确分类，从而生成新的分枝和叶子，并添加到树中。树是由
节点
和
分枝
组成的层次数据结构。
节点
用于存贮信息或知识，
分枝
用于连接各个节点。树是图的一个特例，图是更一般的数学结构，如贝叶斯网络。决策树是
描述分类过程的一种数据结构
，从上端的根节点开始，各种分类原则被引用进来，并依这些分类原则将根节点的数据集划分为子集，这一划分过程直到某种约束条件满足而结束可以看到，一个决策树的内部结点包含学习的实例，每层分枝代表了实例的一个属性的可能取值，叶节点是最终划分成的类。如果判定是二元的，那么构造的将是一棵二叉树，在树中每回答一个问题就降到树的下一层。
判定结构可以机械的转变成产生式规则。可以通过对结构进行广度优先搜索，并在每个节点生成“IF…THEN”规则来实现。如图的决策树可以转换成下规则：
IF “个子大”THEN
IF “脖子短”THEN IF “鼻子长” THEN可能是大象 -
-
构造决策树(四个问题)
-
收集待分类的数据
，这些数据的所有属性应该是完全标注的。 -
设计分类原则
，即数据的哪些属性可以被用来分类，以及如何将该属性量化。 -
分类原则的选择
，即在众多分类准则中，每一步选择哪一准则使最终的树更令人满意。 -
设计分类停止条件
，实际应用中数据的属性很多，真正有分类意义的属性往往是有限几个，因此在必要的时候应该停止数据集分裂：例如该节点包含的数据太少不足以分裂
继续分裂数据集对树生成的目标(例如ID3中的熵下降准则)没有贡献
树的深度过大不宜再分。
-
-
决策树性质
- 证据由属性值对表示
- 目标函数有离散输出值
- 需要不相关的描述
- 容忍训练数据的错误
人工神经网络(ANNs)
-
概述
-
神经网络表示-
非图形符号表示
-
决策树是一种图形符号表示
– 能表示
与或规则
– 形象直观地
图形符号
-
ANNs非图形符号表示法
– 一种
函数表示法
；– 从大量的数据中
抽取规则函数
（或者根本无法表示的识别能力)
-
-
ANN表示的信息
所学的概念是一种非精确表示
-
ANN的学习
- 提供的训练阳历应是数字信息，且有明确的概念
- ANN训练完毕后用于区分其他信息
-
ANN解决问题的步骤：
-
选择确定
网络结构
：输入层、输出层、隐含层的结点数码以及连接权重 -
选择
学习算法
-
训练神经网络
直至能输出正确的结构 -
使用神经网络
-
选择确定
-
网络结构
-
双层网络/多层网络
-
全连接/部分连接神经网络
-
前馈神经网络—— BP算法
计算每个单元的误差，首先计算输出单元的误差；利用
输出单元的误差再计算上一层单元的误差
，依次向上传播，因此又称
反向传播
，又称
逆推学习算法
，简称BP算法。 -
随机神经网络—— 模拟退火算法
-
自组织特征映射神经网络
-
-
学习速率
- ƞ称作学习速率，一般设定为小数
- 学习速率主要用于控制权重的变化
-
学习速率ƞ的大小对学习算法的影响：
- 过大会引起飘移
- 过小收敛速度太慢，学习效率不高
神经网络学习法中学习速率ƞ的概念
了解ID3学习算法构建决策树的原理和过程
采用自顶向下的贪婪搜索遍历可能的决策树空间
-
ID3的思想
-
自顶向下
构造决策树 - 从“哪一个属性将在树的根节点被测试”开始
- 使用统计测试来确定每一个实例属性单独分类训练样例的能力
-
-
ID3的过程
- 分类能力最好的属性被选作树的根节点(如年龄、长相、文化程度、收入、工作性质、家庭背景，性别，姓氏等等)
- 根节点的每个可能值产生一个分支
- 训练样例排列到适当的分支
- 重复上述过程
-
ID3算法
- 随机选择训练实例的子集构成训练窗口
-
重复下列步骤：
- 对窗口内的实例集构造其决策树
- 寻找决策树的一个反例
- 如果反例存在则将其加入到训练窗口中，并转1；否则返回得到决策树
- ID3检查所有的候选属性，选择增益最大的属性A作为根节点，形成数。然后对子树C~1~ ,C~2~ ,…,C~m~以同样处理，递归形成决策树。
-
ID3和候选消除算法的比较
- ID3的搜索范围是一个完整的假设空间，但不彻底地搜索这个空间
- 候选消除算法的搜索范围是不完整的假设空间，但彻底地搜索这个空间
- ID3的归纳偏置完全是搜索车略排序假设的结果，来自搜索策略
- 候选消除算法完全是假设表示的表达能力的结果，来自对搜索空间的定义。
计算智能
关于A,B,C智能（*）
贝兹德克（ Bezdek ）于1992年提出了一种A，B，C智能模型，从而表示ABC与神经网络、模式识别和智能之间的关系：
- Artificial ，人工的、符号的（非生物的）
- Biological ，生物的
- Computational ，计算的
计算智能是一种智力方式的底层认知，它与人工智能的区别是认知层次从中层下降到底层。中层系统含有知识，底层系统没有知识。
当一个系统只涉及数值(低层)数据，含有模式识别部分，不应用于人工智能意义上的知识，而且系统能够呈现出：计算适应性、计算容错性、接近人的计算速度、计算误差率与人接近，则该系统就是
计算智能系统
。
当一个计算智能系统以非数值方式并加上知识，即认为
人工智能系统
。
遗传算法
算法的思想
在生物系统中，进化被认为是一种成功的自适应方法，具有很好的健壮性。其主要特点：
- 直接对结构对象进行操作，不存在求导和函数连续性的限定。
- 具有内在的隐含并行性和更好的全局寻优能力；
- 采用概率化的寻优方法，能自动获取和指导优化的搜索空间。
- 自适应地调整搜索方向，不需要确定的规则
遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串群体中，按所选择的
适应度函数
并通过遗传中的
复制、交叉及变异
对个体进行筛选，
适应度高
的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代
三种基本操作：复制、交叉、变异
-
复制：从一个旧种群中选择生命力强的个体位串产生新种群的过程，具有
高适应度
的位串更有可能在下一代中产生一个或多个子孙。复制操作可以通过随机方法来实现。首先产生0\~1之间均匀分布的随机数，若某串的复制概率为40%，则当产生的随机数在0.40~1.0之间时，该串被复制，否则被淘汰。
-
交叉：复制操作能从旧种群中选择出优秀者，但不能创造新的染色体。而交叉模拟了生物进化过程中的
繁殖现象
，通过两个染色体的交换组合，来产生新的优良品种。交叉的过程为：在匹配池中任选两个染色体，随机选择一点或多点交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串。
-
变异：用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，它
以很小的概率随机地改变遗传基因
（表示染色体的符号串的某一位）的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由1变成0，由0变成1.若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量。为了在尽可能大的空间中获得质量较高的优化解，必须采用变异操作。
适应度函数与轮盘赌算法
在遗传算法中，衡量个体优劣的尺度是
适应度
，根据适应度的大小决定某些个体是繁殖或是消亡。
通常，适应度是费用、赢利、方差等目标的表达式。
-
统一表达式
-
适应度缩放
-
复制（轮盘选择）
-
依次累计群体内各个个体的适应度，得相应的累计值
S
i
,最后一个累计值为
S
n
-
在
[
0
,
S
n
]
区间内产生均匀分布的随机数R - 依次用S~i~ 与R相比较，第一个出现S~i~大于或等于R的个体i被选为复制对象
- 重复(2),(3)直至满足所需要的个体数目。
每代群体中，被复制的个体数目由复制概率Pt控制， Pt常取0.1～0.2，也就是说，群体中有90%～80%个体被复制，相应地有10%
～20%个体被淘汰，以保持群体大小。 -
依次累计群体内各个个体的适应度，得相应的累计值
编码与解码
-
编码（coding）
遗传算法首先要对实际问题进行编码，用字符串表达问题。这种字符串相当于遗传学中的染色体。每一代所产生的字符串个体总和称为群体。为了实现方便，字符串长度固定，字符选为0或1。
遗传算法的工作对象是字符串，因此对字符串的编码有两点要求：
- 字符串要反映所研究问题的性质
- 字符串的表达要便于计算处理
对于兼有多种性质的问题，可以采用长字符串顺序分别表示。例如，可选25位0/1字符串表示物体的体积、重量及颜色，其中前10位数表示体积量，中间10位数表示重量，后5位数表示颜色。
遗传算法工作步骤（*）
复制概率
P
t
：用于控制复制与淘汰的个体数目，取值范围0.4~1。
交叉率
P
c
：参加交叉运算的染色体个数占全体染色体总数的比例，取值范围0.4~0.99
变异率
P
m
：发生变异的基因位数所占全体染色体的基因总位数的比例，取值范围0.0001～0.1
与粒子群算法的相同与不同
群智能（Swarm Intelligence）
概念
智能源于社会性的相互作用
，群智能发展的基石。
已有的群智能理论和应用研究证明群智能方法是一种能够有效解决
大多数优化问题的新方法
两大特点
并行性和分布式
已有的群智能理论的研究和应用证明群智能方法是一种能够有效解决优化问题的方法
群智能典型算法
- 蚁群算法
- 粒子群算法
- 鱼群算法
- 猴群算法
蚁群算法，粒子群算法
-
蚁群算法
-
蚁群算法：
蚂蚁觅食的过程，随机移动，遇到食物返回的路上分泌信息素（易挥发的化学性物质），关键路径上的信息素浓度相对高。
-
蚁群算法原理：
- 基于蚂蚁觅食时最优路径的选择问题，可以构造人工蚁群来解决最优问题
- 人工蚁群中把具有最简单功能的工作单元看作蚂蚁
- 人工蚂蚁与自然蚁群相似：优先选择信息素浓度大的路径；区别：人工蚂蚁具有一定的记忆能力，能够记忆已经访问过的节点
- 人工蚁群在选择吓一跳路径的时候按照一定的算法有意识的寻找最短路径，而不是盲目的。
-
蚁群算法中的各种行为因子
- 范围
- 环境
- 觅食规则
- 移动规则
- 避障规则
- 信息素规则
-
蚁群算法的应用
- 聚类问题
- 路由算法设计
- 图着色
- 车辆调度
- 机器人路径规划
-
-
粒子群算法
-
粒子群优化算法：
模拟鸟群或蜂群的觅食行为。
-
基本思想：通过群体中个体之间的协作和信息共享来寻找最优解。
-
粒子群优化算法原理：
- 每个飞行的小鸟抽象为一个无质量、无体积的粒子
-
每个粒子有一个适应度（评估）函数模拟每只小鸟与食物的
距离
-
每个粒子有一个
速度
决定它的飞行方向和距离，初始值可以随机确定 -
每一次单位时间的飞行后，所有粒子分享信息，下一步将飞向
自身最佳位置
（个体极值）和
全局最优位置
（全局极值）的加权中心
-
粒子群优化算法流程
- 初始化一群粒子（群体规模），包括随机的位置和速度
- 评价每个粒子的适应度
- 对每个粒子更新个体最优位置P~id~
- 更新全局最优位置P~gbest~
- 根据速度和位置方差更行每个粒子的速度和位置（V~id~和P~id~)
- 如果未满足结束条件（通常为满足足够好的适应值或达到设定的最大迭代次数），返回2
-
粒子速度和位置的更新公式（*）
第k+1时刻第i个粒子的位置和速度更新为：
V
k
+
1
i
d
=
w
v
k
i
d
+
c
1
r
a
n
d
(
)
(
p
i
d
+
x
k
i
d
)
+
c
2
r
a
n
d
(
)
(
p
g
b
e
s
t
+
x
k
i
d
)
x
k
+
1
i
d
=
x
k
i
d
+
v
k
+
1
i
d
i
=
1
,
2
,
…
;
d
=
1
,
2
,
…
,
D
惯性权重w
- 使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。
- 表示微粒对当前自身运动状态的信任，依据自身的速度进行惯性运动。
- 较大的w有利于跳出局部极值，而较小的w有利于算法收敛。
加速常数
c
1
和
c
2
-
代表将粒子推向
P
b
e
s
t
和
G
b
e
s
t
位置的统计加速项的权重。 -
表示粒子的动作来源于自己经验的部分和其它粒子经验的部分。
-
较小的值允许粒子在被拉回之前可以在目标区域外徘徊，而较大的值则导致粒子突然冲向或越过目标区域。
-
将c1和c2统一为一个控制参数，φ=c1+c2
如果φ很小，粒子群运动轨迹将非常缓慢；
如果φ很大，则粒子的位置变化非常快；
实验表明，当φ=4.1（通常c1=2.0，c2=2.0）时，具有很好的收敛效果。
粒子数
- 一般取20\~40，对较难或特定类别的问题可以取100~200
最大速度
V
m
a
x
- 决定粒子在一个循环中最大的移动距离，通常设定为粒子的范围宽度。
终止条件
- 最大循环数以及最小错误要求
-
与遗传算法的比较
-
共性：
- 都属于仿生算法
- 都属于全局优化方法
- 都属于随机搜索算法
- 都隐含并行性
- 根据个体的适应信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等；
- 对高位复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点
-
差异：
- PSO有记忆，所有粒子都保存较优解的知识，而GA，以前的知识随着种群的改变被改变
- PSO中的粒子是一种单向信息共享机制。而GA中的染色体之间相互共享信息，使得整个种群都向最优区域移动
- GA需要编码和遗传操作，而PSO没有交叉和变异操作，粒子只是通过内部速度进行更行，因此原理更简单、参数更少、实现更容易。
-
粒子群优化算法的应用
- 巡航导弹的飞行高度进行优化
- 车辆路径问题的应用
- 邮政投递
- 火车及汽车的调度
- 港口装卸集装箱
-
共性：
-
人工鱼群算法
模拟鱼群的觅食行为、集群行为、跟随行为、和随机游动行为。大多数时间，鱼会想有更多食物的方向游动，同事，它们会尽量聚集在一起来并保持和鱼群中心位置的鱼游动方向一致
每种算法提出的思想依据与理论基础
蚁群算法和粒子群算法应用领域
自然语言处理
-
NPL的困难
-
歧义（Ambiguity）
- 注音歧义
- 分词歧义
- 无法在句子内部解决的歧义
- 短语歧义
- 病构（ill-Formedness）
- 重述（Paraphrasing）
-
歧义（Ambiguity）
-
NPL方法论
语言处理的科学内容
-
NPL的任务和瓶颈
-
NLP的性质
NLP需要的知识非常复杂
- 理解语言的过程是动态的，不是静态的
- NLP需要的知识大多是归纳的，不是演绎的
- 人也不一定能够做出一致的理解结果，存在Upper Bound
- NLP是一个非确定性过程
- 领域词典不充分
-
-
统计语言模型及解决问题的思想
| 模型 | 算法 |
|---|---|
| 状态机模型 | 动态编程 |
| 形式规则系统模型 | 及其学习 |
| 统计模型 | 分类/序列模型算法 |
| 向量空间模型 | 最大期望算法 |
人工智能历史
人工智能方法与传统程序的不同
传统方法解决问题。利用已有知识，问题可以结构化-数据结构，数学表达式-数学公式、算法。
利用知识，特别是依赖人类经验的启发知识是人工智能方法与传统数学方法的根本不同之处。基于此，人工智能可以解决众多的难以数学表达的非结构化的实际问题
人工智能首先研究的是以符号表示的知识而不是数值为研究对象。其次采用的是启发式推理的方法而不是常规的算法。控制结构和领域知识是分离的，同时还允许出现相对正确的答案。
人工智能的本质
研究人工智能的途径
人工智能的重要影响人物
- 阿伦-图灵：计算机科学理论创始人
- 马文-明斯基：人工智能之父，框架理论创立者，首位获得图灵奖的人工智能学者
- 约翰-麦卡锡：人工智能之父，LISP语言发明人，首次提出AI概念
- 赫伯特-西蒙：符号主义学派创始人，中国科学院外籍院士
- 艾伦-纽厄尔：符号主义学派创始人一致，西蒙的学生
计算题
-
归结原理
- P4 49页 求归结步骤和归结树
- P4 27页 化为Skolem标准形
-
主观贝叶斯方法
- P5 100页 根据R1,R2，LS,LN求B的更新值(A1,A2必然发生的情况)
-
确定性方法
- P5 124页 CF(B1),CF(B2)的计算