启发式搜索
耗散值=代价、开销
一般图搜索是一类无信息搜索
启发式信息：人类的直观感觉或经验，往往无法证明
评价函数
$$
f(n)=g(n)+h(n)\\
f(n):评价函数\\
h(n):启发函数\\
g^*(n):从起点S到当前点n的最短路径的耗散值\\
h^*(n)从当前点n到目标节点T的最短路径的耗散值\\
f^*(n)=g^*(n)+h^*(n)\\
带星的是实际值，不带的是估计值\\
g(n)不一定等于g^*(n),只有过程中找最近的扩展才是相等的
$$
当$h(n)=0$时，A*就变成Dijkstra了。
当$h(n)\le h^*(n)$时，能够保证找到的是最短路
当$h(n)>h^*(n)$时，只能加速，不能保证找到的是最优
如果满足条件$h(n)\le h^*(n)$，则A算法称作A*算法
证明
定理1
对有限图，如果从初始节点S到目标节点T有路径存在，则算法A一定成功结束
路径是有限的，且算法不会走重复路径
引理1.1
对无限图，若有从初始节点S到目标节点T的路径，则A*不结束时，在Open表中即使最小的一个f值也将增到任意大，或有$f(n)>f^*(S)$
引理1.2
A*结束前，Open表中必定存在$f(n)\le f^*(S)$
由$h(n)\le h^*(n)$易证
定理2
对无限图，若从初始节点S到目标节点T有路径存在，则A*一定成功结束。
证明：
由引理1.1，A*如果不结束，则对Open表中所有的n有$f(n)>f^*(S)$
由引理1.2，在A*结束前，必存在节点n，使得$f(n)\le f^*(S)$
所以如果不结束将导致矛盾
推论1
Open表上任一具有$f(n)<f^*(S)$的节点n，最终都将被A*选作扩展的结点
证明：
由定理1、2，A*一定结束。由A*的规则，Open表中$f(T)$最小时才被选择。而$f(T)\ge f^*(T)=f^*(S)$
所以$f(n)<f^*(S)$的n均会被扩展。
定理3（可采纳性定理）
若存在从初始节点S到目标节点T的路径，则A*必定能找到最佳解并结束。
证明：
由定理1、2，A*一定结束。设找到的路径不是最佳的，则$f(T)=g(T)>f^*(S)$。由引理1.2可得，结束前Open表中存在$f(n)\le f^*(S)$的节点n，所以$f(n)\le f^*(S)<f(T)$
因此A*应选择n扩展，而不是T。矛盾。
推论2
A*选作扩展的任一节点n，有$f(n)\le f^*(S)$
证明：
由引理1.2，结束前Open表中存在节点n’，使$f(n’)\le f^*(S)$。设此时选择n扩展。
若n=n’，则$f(n)\le f^*(S)$
否则，$f(n)\le f(n’)\le f^*(S)$
得证
定理4
设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有$h_2(n)>h_1(n)$，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。
优化
当启发评估函数h满足$h(n_i)-h(n_j)\le c(n_i,n_j)$时，称为h(n)单调，可以保证每个点只会被扩展一次。
定理5
若$h(n)$单调，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。即：当A*选n扩展时，有$g(n)=g^*(n)$。
定理6
若$h(n)$是单调的，则由A*所扩展的节点序列其f值是非递减的。即$f(n_i)\le f(n_j)$
改进
优先扩展 比已扩展节点的f最大值小的点中g最小的
不确定搜索
邻域搜索约等于贪心爬山法
刚开始有一个解 逼近法
刚开始没有解 把他搜出来 构造法
模拟退火
$$
P(Accept)=exp(\frac{-\Delta x}{T})
$$
博弈搜索
min-max搜索
意思就是先向下搜，返回时候一层选min，一层选max
alpha-beta剪枝
判断出了上下限就可以把没这么优的剪枝了
约束满足
与前面的搜索的区别：没有优化目标，而是找到满足约束的点即可。
方法就是搜索剪枝
剪枝的方法：
- 向前查看：约束传播 把能确定的一次性全搞掉，判断邻居是否有合法解
- 启发式：用已知信息决定哪个点先赋值。有多种排序方式，适应不同问题
机器学习
经验误差：历史数据
泛化误差：未来数据
决策树
信息熵 设$p_k$表示样本集合中第$k$类样本所占的比例
$$
H(D)=-\sum _ {k=1}^ {|y|}p_k\lg(p_k)
$$
信息增益，大概就是信息熵减少的值。假设以$a$属性分类，分成$v$类：
$$
G(D,a)=H(D)-\sum _ {v=1} ^ V\frac{|D^v|}{|D|}\cdot H(D^v)
$$
K-means
简略过程：先随机一个初始分割中心点，把每个点归到最近的那类，算每一类的中心点作为新分割中心点，直到分割不变。
神经网络
只考基础内容-多层感知机的基本结构
深度学习
CNN特点
全连接的参数数量巨大（平方级），且训练耗时太长、难以收敛。难以提取局部不变特征（缩放、平移旋转等）
卷积层局部连接代替全连接层
CNN计算
输入层卷完参数vector再输入神经网络
步长：隔多远算一次
填充：边缘是否补0
x层卷y层池化配合成一个卷积快，z个卷积块之后交给常规的全连接
强化学习
与监督学习的区别：目的不同，预测（判断）与决策
Reward Is Enough
关键要素：<A,X,R,P>
A动作空间
X状态空间
R奖赏函数
P状态转移概率
学到策略，使长期执行该策略后得到的累积奖赏最大
知识计算
知识表示
将元素表示为低维稠密实值向量
向量化面向机器处理
符号化面向人的理解，可以实现符号推理
关键是合理定义知识图谱中关于事实（三元组<h,r,t>）的损失函数$f_r(h,t)$
$$
\text{argmin} \sum_{r\in KB}f_r(h,t)
$$
基于距离的模型
SE模型 两个实体属于同一个三元组时，向量表示在投影后的空间应该比较靠近
基于翻译的模型
TransE
看作是头实体h到尾实体t利用关系r进行的翻译
知识图谱
基于规则
基于统计
贝叶斯网络
贝叶斯公式
$$
P(B_i|A)= \frac {P(B_i) P(A|B_i)}{\sum _ {k=1}^n P(B_k)P(A|B_k)}
$$
贝叶斯网络=网络结构+条件概率表