启发式搜索——算法

在启发式搜索里面，会考虑两个集合，一个叫 Open set 一个叫 Closed set

Open：表示当前需要考虑的，还未完成搜索的节点
Closed：表示已经处理完毕，不会再考虑的节点

启发式搜索的大概步骤是：

把初始的节点加入到Open集合中
将Open set中的节点按照评估函数的大小从小到大排序，选出最小的那个，设置成当前的节点（CS），如果已经没有可以选的了，结束，表示未搜索到
如果CS是终点，结束操作
将CS的所有可达节点进行以下操作：
1. 如果节点在Closed list中，继续下一个
2. 否则加入到 Open list中
将CS加入Closed list中，回到第2步

算法的评估函数为：其中的表示从开始移动到节点的实际代价，而是定义的启发式评估函数，用于评估当前节点到目标节点的代价

由于上面的定义，不难发现，，如果满足那么这个启发式算法是可采纳的，一定会找到最优解的。

这里的应当理解为从点n到终点的真实代价

推理

谓词推理

推理规则一共有如下几条：

取式假言推理：已知和为真，那么为真
拒式假言推理：已知为假且为真，那么为假
与消除：已知为真，那么和分别为真
与引入：已知和分别为真，那么为真
全称例化：已知为真，且为定义域中的一个，那么有为真

合一算法

合一算法的目的是看能否找到一组置换让两个谓词表达式匹配。首先定义什么是置换

一个替换(Substitution)就是形如的有限集合，是互不相同的个体变元，不同于, 也不循环出现在tj中

注意，一个替换中的元素都是项，换句话说，是一个替换，但是不是一个替换

其步骤如下：

首先算Skloem 范式，去掉所有的存在（具体步骤是将存在约束的部分中的所有变量换成一个新的常元，如果存在被一个任意约束，那么就换成一个任意约束的变量的函数）
然后运行算法：
1. 递归地对初始成分进行合一化，如果成功，将返回的表达式应用到两个表达式的剩余部分，以这两个表达式为参数继续进行
2. 如果最终都匹配了，那么就成功，否则失败
基础的合一化如下：
1. 如果传入的是常元或者空表，如果那么无需替换且成功，否则失败
2. 如果是一个变元：
  1. 如果在中出现，那么就失败
  2. 否则
3. 如果是一个变元同上

归结算法

参考维基百科的连接归结原理 - 维基百科，自由的百科全书

首先把所有的量词处理掉：
- 存在量词换成Skloem范式里面的Skloem函数（只有存在的换成常量，被任意修饰的存在换成被任意修饰部分的函数）
- 全称量词直接省略，因为你可以用很多个替换实现
- 注意，在有很多个带全程量词的子句的时候，每一个换掉的变量名应该不同
然后把所有子句换成合取范式（内层是外层是的），然后拆分成只有和的子句
只使用消解规则和替换进行推导，弄出证明树

贝叶斯网络

基本连接方式

顺序连接

形如：

1
2
3

flowchart LR
X(X) --> Y(Y)
Y --> Z(Z)

在Y已知的情况下， X到Z被阻断所以X和Z独立
在Y未知的情况下，X到Z 没有被阻断 所以X和Z不独立

分支链接

形如

1
2
3

graph TD
Y(Y) --> X(X)
Y --> Z(Z)

在给定Y的情况下，X到Z被阻断，X和Z独立
在没有给定Y的情况下，X到Z未被阻断，X和Z不独立

汇合连接

形如：

1
2
3

graph TD
X(X) --> Y(Y)
Z(Z) --> Y

在Y已知的情况下，X和Z是不独立的，X和Z之间未被阻断
在Y未知的情况下，X到Z被阻断

分支汇合连接

这个其实可以看成两个顺序连接

graph TD
X(X) --> Y(Y)
X --> W(W)
Y --> Z(Z)
W --> Z

这里面X和Z独立当且仅当Y和W都已知

Summary

上面的四种情况里面，只有汇合连接是在中间节点及其子节点都未知的情况下，才能阻断X到Z的，否则都是路径上有一个节点已知就阻断

判断d可分

问题定义

判定变量集和变量集在变量集合已知的情况下是否独立

算法

考虑如果对于所有从到的路径，都阻断了路径，那么这两个集合就是独立的

在贝叶斯网络上推理

首先，对于所求的询问节点的条件概率,用所给证据节点和询问节点的所有因节点的联合概率进行重新表达。
然后，对所得表达式进行适当变形, 直到其中的所有概率值都可以从问题贝叶斯网络的CPT中得到。
最后，将相关概率值代入概率表达式进行计算即得所求询问节点的条件概率。

注意事项

在扩展形如的时候，应该是扩展成这才是全概率公式

马尔科夫网络

势函数

对于马尔科夫网络中的每一个团，可以定义一个势函数，这是一个非负函数，表示对于一组特定的的取值，选取该值的偏好，那么出现这个情况的概率可以认为是：

为了方便表示，这里一般把它写成指数的形式，即：

按照PPT上的写法是：

其中的是配分函数，定义为：

这里面的代表的是对于团，里面每个节点的值等于时的可信度（偏好）

对数线性模型

为了方便统计，现在定义一个特征函数表示出团取值为的特征，那么可以把写成线性的形式：

在马尔科夫网络中判断独立性

这玩意的算法非常简单，因为马尔科夫网络是无向图，所以在考虑已知集合时，集合和集合是否独立，只需要考虑扣掉之后，集合和集合是否分属不同的联通分支就行了

符号学习

ID3算法

定义熵

这里的表示该类目有个取值的可能性

定义 信息增益 为：

后面一项被称为条件熵

信息增益换言之，就是在使用对进行分类后，对于原本的熵减少了多少，由于我们的目标是得到一个决策树，使得最后基本上都能得到正确的标签，所以我们希望最好的情况是能够让这里面分类完之后的熵变成0，即某个分类能够完全区分样本，所以希望后面的部分这个趋于0，那么这里整个的含义是通过分类S能能够提供多少的准确度

ID3算法递归地进行，即首先选择出信息增益最大的一个，然后放到第一层里面，提取该属性下的所有样本继续进行，如果某个属性下只有一个值了，那么放上对应的标签

易错点

注意这里算信息增益的时候，要加权，前面有一项不要忘了

C4.5算法

这里定义一个信息分裂程度 Split Information 为：

注意这个和Gain的区别，Gain是

这里面的 Split Information 可以认为是每个属性自己的熵，而C4.5通过

作为指标来选取属性

感知机

感知机在课程里面是一层的，如下图：

这里面更新的方程是：

其中的是学习率，sign是激活函数，考试为了简单可以用阈值代替

这里也可以选取偏置单元，即在最前面再加上一个项来训练，不过考试也可以不取

强化学习

Bellman 方程式

对于一个状态有

注意在考试中，让求每一个状态的价值函数的方法是把所有的贝尔曼方程列出来联立求解，并且所有的策略都是贪心的，即求最大的R

博弈论

纳什均衡的定义

一个纳什均衡满足对于任意的都有

这里面的表示除了之外都选择纳什均衡的动作

纳什均衡的纯策略求法

在一个博弈矩阵里面，先看Player1在固定了他的策略的情况下，Player2选择哪一个动作能够获得最大的收益，在那个位置下面划线，然后反过来固定Player1再来做，例如下面的博弈矩阵（A 的收益在左，B 的收益在右）：

	B1	B2
A1	(3, 2)	(1, 1)
A2	(0, 0)	(2, 3)

首先，假设B选择动作B1，那么对A来说，A1的收益是3大于A2的收益0，所以在3下面划线，假设B选择动作B2，那么对A来说，A1的收益是1小于A2的收益2，所以在2下面划线
然后，假设A选择动作A1，对于B而言，B1的收益是2大于B2的收益1，所以在2下面划线，假设A选择动作A2，对于B而言，B1的收益是0小于B2的收益3，所以在3下面划线，
最后，发现两个数都划线了，同时两个也都划线了，所以这里有两个纳什均衡的解，分别是

混合策略的纳什均衡求法

在上例中，假设A以概率选择A1，B以概率选择A2，那么

而相关均衡要求所以联立解得同理可以求得

帕累托最优和帕累托改进

先定义帕累托改进：在不损害任何一个人的收益的前提下，使得至少一部分的人的收益增加。

而帕累托最优就是没有帕累托改进空间的局面。

下面有一个例子

这个局面里面之所以这三个都是帕累托最优是因为这三个局面里面都没有不损伤一方而使至少一部分人收益增加的了，但是只有 $否认否认$ 是那是均衡 $坦白坦白$ 的帕累托改进