# 术语及其缩写

# 搜索

Uniform Cost Search

启发式搜索

A*搜索

• 什么情况下A*能保证完备和最优？

• 如何对于每个中间节点都能保证pop出来一定是最优的呢？

• 结论：当启发是可接受的（admissible），A*在树搜索树上可以保证最优 当启发是一致的（consistent），A*在图搜索树上可以保证最优（否则可能中间节点被取出的时候不是最优的）

CDCL

Min-Max与alpha beta剪枝

1. 向下递归时，子节点继承父节点的不等式（直接copy，不用变符号），这里不等式包括所有之前走过的节点构成的约束

2. 搜索子节点，如果子节点的值违反了当前节点的“反向不等式”（即min节点违反≥alpha，max节点违反≤beta），则返回该异常值（其实返回+-inf也可以）；否则更新父节点对应约束（min节点更新≤，max节点更新≥），接着搜子节点。如果全部搜完都没有异常，则返回min{son}或max{son}

1. 节点有三个参数，写作：alpha≤v≤beta

2. 初始化：从父节点继承上下界，或者为-inf~+inf。v为-inf

3. 从子节点得到其v，如果与beta冲突（与alpha冲突没事！），直接返回v。否则更新自己的v和alpha。

MCTS

1. 选择。从当前局面的节点（根）开始，只要当前节点下还有节点（即经过次数>1），则用UCB走向估值最高的点。

2. 扩展。当步骤1来到叶子节点，则向下扩展一个节点。

3. 模拟。从新扩展的节点开始，纯随机或者已某种概率算法模拟一定步数，然后返回分数到新扩展节点。模拟过程中的节点不会加入MCTS树种。

4. 回溯。更新从新扩展节点到根的路径上所有节点的访问次数和分数，重复步骤1

# 神经网络基础

#脉络

#模型分类

#训练过程

训练误差(training error)低不代表模型就是好的，因为其泛化(generalization)能力并不一定好，可能过拟合(overfitting)，因此还要看它的测试误差(test error)

#K近邻(k-Nearest Neighbor, k-NN)

#线性回归(linear regression)

#经验风险最小化框架(Empirical Risk Minimization, ERM)

#最大似然估计框架(Maximum Likelihood Estimation, MLE)

#逻辑回归(Logistic Regression)（核心：根据yf(x)判断Loss）

• 零一损失函数

• sigmoid函数（将f(x)转化成概率）

• Softmax回归

#正则化(Regularization)

#超参数与模型验证

• K-折交叉验证： • 将测试集外的所有数据随机分为 K 份 • 对一组给定的超参数组合： • 每次使用 K-1 份数据训练模型，用 1 份验证模型误差 • 将 K 次验证的模型误差取平均来衡量该组超参数的好坏 • 遍历所有可能的超参数组合 • 返回平均误差最低的超参数组合，在测试集上最终测试模型性能

#决策树与随机森林

决策树：在每一层上根据同一个标准对节点样本集进行特征测试，根据结果将样本归入下一层的节点。根节点包含所有数据点，而叶子节点则对应着决策结果

• 熵的定义

• 熵的性质

• 联合熵、条件熵与互信息

• 划分准则1：信息增益

• 划分准则2：信息增益率

• 信息增益会偏好取值可能多的属性，而信息增益率则会偏好取值可能少的，很难说哪种一定比哪种好

• 划分准则3：基尼系数（不再用熵衡量“纯度”）

• 属性从离散到连续

• 标签从离散到连续

• 随机森林

#神经网络

• 感知器(perceptron)

• 多层感知器(Multi-Layer Perceptron, MLP)

• 反向传播(backpropagation)

• 矩阵形式

#卷积神经网络(CNN)

• 卷积层(Convolution Layers)

• 批归一化(batch normalization)

• 池化层(pooling)

• Dropout

• 全连接层

• 残差连结

层数过多会导致梯度消失或者梯度爆炸。

通过跨层的直接连结可以顺利地把梯度信息传递回去

#递归神经网络(RNN)

#图网络(GNN)

#成像与三维重建

# 自然语言处理

#句法分析

• CYK算法：处理上下文无关的文法(Context-Free Grammar, CFG)，且必须遵循乔姆斯基范式(CNF)
X→Y意为左边的东西可以由Y构成。大写表示非终结符（即还能被分解为更小的单位，可以理解为短语），小写表示终结符（即为最小单位，可以理解为单词）。



CYK算法基于dp思想，自底向上计算构成短语的各种可能性。最后看S是否存在于最上层的格子中。再用一个三维数组p[n,n,r]记录路径，即可给出句法树。



A*算法比CYK快。

#词袋模型(Bag-of-Words Model, BoW)

#朴素贝叶斯(Naive Bayes)

#信息检索：tf-idf

#词表示(Word Representation)

• 独热表示(one-hot)
每个词用只有一个1，其余全为0的向量表示

• 分布式表示：从上下文决定词语的意思

• 分布式的一种：word2vec(CBOW)



真实标签是我们手动设置的希望值。最后独热向量*周围词向量矩阵=1*N向量即为学习到的向量表示。

#Transformer

• 一些技巧：
多头注意力：对每个X，用多个注意力矩阵进行计算，最后把数个结果综合起来（先concat，然后用矩阵右乘变为原来的维度）
为了使模型对词序敏感，在单词的向量中加入位置编码
当嵌入表示的维度d变得很大时，点乘的结果会变得很大。Softmax的输入也会很大，导致梯度很小。因此在Softmax前，给注意力的结果除上
残差连结。
层归一化LayerNorm，在每个词自己embed的维度上进行归一化。不采用BatchNorm是因为一个batch的数据量会很大。

#知识图谱

• 知识抽取(Extraction)，从数据中提取知识

• 知识表示（Knowledge Representation, KR）

• 其他的知识表示方法

• 知识推理(reasoning)

#机器人

#定位与地图创建

• 蒙特卡洛定位（假设地图准确已知），基于粒子滤波器

• 如果地图不是已知的？SLAM

#运动规划（连续空间的搜索）

• 构型空间(configuration space)
机器人的各个运动参数构成的、不会碰到障碍物的状态空间

• Way1~4：能见度图，沃罗诺伊图式、单元分解、随机运动规划

• 快速探索随机树(RRT)
每次在图上随机采样一个点，找到目前在RRT树上的离这个点最近的点，从树上的点向随机点前进stepsize的距离。如果前进后的点在可行域内，则将其加入RRT树，否则重新随机。直到RRT树上某个点与目标点足够近。



缺点：地图有大量障碍物或者狭窄通道的时候，模型收敛很慢

#运动控制

• P控制器（比例控制器）
施加正比于误差的力or力矩
然而，如果外界有恒定阻力，会使得机器人接近目标时无法再前进

• PI控制器（比例积分控制器）
把误差对时间的累计也计入



但是这样会导致运动过度，产生较大震荡

• PID控制器（比例积分微分控制器）

#强化学习

• 基本概念
• 状态
• 动作
• 转移模型 ，行动不一定和想象的效果一样
• 奖励函数 ，一般是确定的，也可以是概率分布
• 策略 ，一个概率分布函数
• 轨迹 ，按照某个策略行动的状态、行动、奖励的序列
• 价值 。以s0为起点，往未来看，后面都是还没发生的事情

• 价值函数：用来评价一个策略的好坏
状态价值函数
表示采用策略，从s0出发的各种可能的轨迹得到的价值的期望值
为了能方便从当前状态选择具体动作，再定义一个动作价值函数

• Bellman Function
本质上是动态规划的想法，详细推导见课件



在最优方程里，策略不再是一个概率，而是对每个s给出一个确定的动作a。因为无后效性（对于马尔科夫问题），所以局部最优的动作就是全局最优的动作
• 策略迭代
第一步：对于所有策略（概率性的），求出。采用数值迭代的方法



第二步：对每个状态s，计算，并从中找到最好的a作为当前的最佳策略（确定性的）。因为马尔科夫无后效性，这样的策略不会变差。（Rmk：第二步依赖于第一步，因为Q的更新必须要知道所有的V）



当V不再变化的时候，满足最优Bellman方程，此时策略最优，算法结束；否则回到第一步，再来一轮



• 数值迭代：直接采用数值迭代求Bellman最优方程的解，求出最优的V*后，对每个s求使得Q最好，即算出Q*



• Q-Learning（对数值迭代的改进）
注意到在数值迭代中，算V*每次都需要遍历。可不可以只遍历一些状态？选择下一个要遍历的状态时采用greedy



• 如果S、A空间很大？没法列举所有的V(s)和Q(s,a)，但是可以用神经网络代替。但是很难收敛，因为对神经网络而言，其目标是不断在变化的

#多智能体

#仿真

#外观仿真

几何表示

• SDF（Signed Distance Function）

• 点云表示

• 体素表示

• 多边形网络
将形状近似的用多边形面片表示，只需记录顶点的坐标，面片上点的坐标可以通过插值计算

渲染

#物理仿真