Readme

这是我的人智导笔记

2024spring期末，六道大题，分别考察了alpha-beta剪枝、修正的A*算法、SVM计算、神经网络的参数/填充/步长/通道数、决策树的ID3和C4.5算法、设计一个全连接网络来得到核函数以及非线性向量机求解的伪代码

复习过程大概是先看一遍雨课堂的回放，然后针对这些常考的算法做一些题，主要是PPT上的例题

一开始1.5倍速看的回放，后来发现要看不完了，于是换成2倍速，发现这样短时间内大量地吸取知识居然还真的理解了不少之前没听懂/没听进去的知识（？）就是过程有点煎熬，战线拉长了后大脑十分疲惫

今年上完马老师就退休了，不知道以后的人智导课程内容与试题会是什么样子呢

第一章 搜索

宽度优先、深度优先、A算法、修正的A算法

搜索是为了解决：如何选择一个（叶）节点扩展，这也是不同搜索算法的不同处

盲目搜索

没有任何启发信息，在图上随便找

  1. 深度优先DFS

根节点深度为0，逐层加1，采用的策略是优先选择深度深的节点扩展，两个节点深度一样的随机选择一个扩展。若本层所有的节点均不满足要求，则回溯一层，选择其他的节点再往下扩展

Eg. 皇后问题：摆放要不同行不同列不同对角

性质：

  • 一般不能保证找到最优解
  • 一般用DFS算法会增加一个深度限制（防止沿着一条无效的路一直走下去），所以当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制（当某一深度限制比较小时，可以将其增加一点再BFS）
  • 最坏情况，DFS相当于穷举

好处：节省内存，因为只储存了从初始节点到当前节点的路径

  1. 宽度优先BFS

优先扩展深度浅的节点。每层逐次扩展所有节点

Eg. 华容道

性质：

  • 当问题有解时，一定能找到解
  • 当问题为单位耗散值（走一步的花费都是一样的），且问题有解时，一定能找到最优解（因为是一步一步来的）
  • 效率低，费空间（最优解、效率高和储存低一般不能同时满足）

但是当问题不是单位耗散值时，BFS找的不一定是最优解，因为这时没有用节点之间的距离，而是用的节点的深度（这时要使用dijkstra算法）

dijkstra算法是BFS算法的改进：优先扩展距离起点最近的节点，****直到终点距离最短（利用节点的距离信息，不是一找到目标就结束搜索）（算法的结束要满足两个条件：扩展到终点且终点距起点距离最近）

性质：

  • 当问题有解时，可以找到最优解
  • 但是只考虑了节点距离起点的距离，没有考虑节点到终点的距离——>启发式搜索

启发式搜索

g*(n)：从s到n的最短路径的耗散值

h*(n)：从n到目标的最短路径的耗散值

f*(n) = g*(n) + h*(n)：从s经过n到目标的最短路径的耗散值

带的是最短路径，不带的是估计值

一般用估计值代替进行搜索

  1. A算法

优先扩展f(n)值最小的节点，直到f(终点)最小

img

一个节点扩展出的节点要分为三类：m_k, m_j, m_l

closed表：被扩展过的节点（子节点已经生成）

open表：没有被扩展过的（即叶节点）

算法描述：

起始：open = {s}, closed = {}

循环：

大条件：只要open表不空（空了则问题无解，否则一定是最优解）

操作：选择open表第一个节点n（即f值最小的节点）

如果n是目标节点，则结束；

如果n不是目标节点，则扩展节点n，将其移动到closed类中，并计算扩展出的子节点{m_i}的f(n, m_i) = g(n, m_i) + h(m_i)——>强调是从n过来的路径计算的

将新节点m_j加入到open表中

（特殊情况：

对于m_k（原来已存在但没有被进一步扩展）：如果新路径比原来的短，则用新路径代替原来的路径；

对于m_l（原来已存在且已被扩展有了子节点）：如果新路径比原来的短，则用新路径代替原来的路径，重新将m_l加入open表中（因为它的子节点的路径也可能被更新）

）

将open表中的节点按f值从小到大排序

（感觉具体的算法描述好复杂，似乎可以用类似Dijkstra的方法手算？）

怎么得到解路径：

从目标开始，顺序访问父节点，直到初始节点

不能保证找到最优解！因为f(n)是估计值

img

  1. A*算法

在A算法中，如果h(n)≤h*(n)，则A算法称为A*算法

A*算法能够保证找到最优解

定义h函数的一般原则：放宽限制条件，在宽条件下，给出估计函数

两个主要结论：

  • 可采纳性定理：保证找到最优解
  • 设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有的非目标节点有**h_2(n) > h_1(n)**，则搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展（不太好的那个可能会扩展更多的节点，浪费更多的资源），即：

h2(n) > h1(n)，则A1扩展的节点数 ≥ A2扩展的结点数

（h(n)更大，则更接近h*(n)，更优）

（注意，是扩展的节点数，而不是节点次数。即同一个节点无论被扩展多少次，都只计算一次）

对h的评价方法：通过实验

平均分叉数b（如二叉树，b = 2）

设共扩展了d层节点，共搜索了N个节点，则：

$$N = \frac{1-b^{(d+1)}}{1-b^}$$

通过N和d的值计算b*

b*越小，说明h效果越好

  1. 修正的A*算法

因为A算法对m_l类节点可能要重新放回到open表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降

出现多次扩展节点的原因：在前面的扩展中，并没有找到从初始节点到当前节点的最短路径

解决途径：

①对h加以限制——>h要是单调的

h单调，满足条件：

img

若h(n)是单调的，则A扩展了节点n之后，就已经找到了到达节点n的最佳路径。即当A选n进行扩展时，有g(n) = g*(n)

②对算法加以改进

将open表以f*(s)为界分为两个部分，由于f(n) < f*(s)的节点一定被扩展，令f*(s)前面的节点（即f值小于f*(s)的节点）h值等于0，这样它们的h值是单调的，则对于这部分节点，选g最小的节点扩展（退化为dijkstra算法）

由于不知道f*(s)的值，所以用估算值f_m代替：f_m是到目前为止已扩展节点的最大f值

相较于A算法，修正的算法增加了NEST数组，NEST数组里是f(n) < f(m)的节点。当NEST数组不为空时，始终选择NEST中g值最小的节点，否则才选择open中f值最小的节点，且要修改f_m的值

img

其他的搜索算法

  1. 爬山法（局部搜索算法）

只能利用局部信息

  1. 随机搜索算法
  2. 动态规划算法——vitebi算法

理论上，当h(n) = 0时，A*算法退化为动态规划算法

img

利用上一个节点的结果，而不是从头计算

公式如下：

img

第二章 神经网络与深度学习

全连接网络、卷积网络、循环网络的运算等等、相关例子、求词向量、几种损失函数、

什么是神经元

从模式匹配说起：

sigmoid函数：将匹配结果转换到0-1之间，判断匹配的程度（可以通过增加偏置项让sigmoid函数平移）

sigmoid是激活函数，还有别的激活函数

迁移到神经元的图：

img

神经元：某个模式的表达，将输入与模式进行匹配

神经网络的横向扩展：增加模式

神经网络的纵向扩展：局部模式（模式组合让神经网络更深）

img

多层神经网络：输入层->隐含层->隐含层->…->输出层

模式通过神经元的连接权重表示，是模型自动学习的，不是手工设计的！

神经元完整结构：

img

全连接网络

相邻两个层的每一个神经元都有连接

损失函数：误差平方和

用于输出是具体数值的问题

img

神经网络的学习——>让损失函数最小

方法：梯度下降法（类比单一变量求导数，对损失函数求梯度）

  • 批量梯度下降算法：每次处理全部样本
  • 随机梯度下降算法：每次处理一个样本，顺序随机。
    • 问题：样本存在噪声，在处理某个样本时可能发生错误。此外，样本并且完全正确，如标注错误等。
  • 小批量梯度下降算法：每次处理小批量的样本

梯度计算：基于随机梯度下降算法。从输出层开始，通过链式法则逐层求梯度，直到输入层（BP算法）

  • 对输出层的神经元：

img

  • 对隐含层的神经元（考虑紧挨着输出层的隐含层）

img

img

“反向”：从输入算出输出，再从输出来逐层向下计算delta来计算每层的权值w

其他的损失函数：交叉熵损失函数

也是越小越好

要加一层softmax激活函数，来得到概率

用于分类问题

卷积神经网络CNN

全连接网络的不足：连接权重过多、影响训练速度、影响使用速度

特点：

  • 局部连接
  • 权值共享

在一个大的输入图像中抽取一些小的模式

权值：卷积核，通过训练得到

一个卷积核相当于一个小的神经元，代表了某种模式

填充：比如输入5x5，卷积核是3x3，想要结果保持5x5大小不变，则可以在外围加一层全为0的数

步长：卷积核每次移动的距离，是可以设定的

多卷积核：

一个卷积核产生一个通道，输出的通道数等于卷积核数

多通道输入时的卷积：

如输入6x6x3，则卷积核为3x3x3（是一个卷积核！得到的是一个通道），最后一个数字表示厚度

img

多层小卷积可以实现大卷积

池化：一种降维的手段

最大池化：取窗口内的最大值，如：

img

窗口可重叠，与步长有关

池化是对通道做的，每个通道单独做池化！做完池化前后通道数不变

举例：

  1. LeNet神经网络
  2. VGG-16神经网络

特点：

  • 参数少，只与卷积核的大小和数量有关
  • 具有特征抽取能力（卷积核）
  • 一定程度上，特征的平移不变性（通过池化）

神经网络遇到的两大问题

  1. 梯度消失问题

神经网络靠梯度对参数进行修正

解决思路：

使用ReLU激活函数（之前使用的是sigmoid函数），消除由于激活函数的导数造成的梯度消失

两个实例，看怎么解决梯度消失问题的：

  • GoogLeNet

三个输出

类似高楼供水，分多个口解决

img

Inception模块：

同时使用不同大小的卷积核

1×1卷积降维

  • 残差网络（ResNet）

神经网络的退化现象

解决思路：加了一个恒等映射，形成残差模块，至少保证原来的性能

img

img

  1. 过拟合问题

过拟合：曲线弯曲过多，模型过于复杂

img

减少过拟合方法：

  • 使用验证集：当在验证集上的错误率最低时停止训练
  • 正则化项法：增加一个权重平方和（范数）
    • 正则化项的作用：降低模型复杂性
  • 舍弃法Dropout
    • 随机地临时舍弃一些神经元
    • 少数神经元得到了充分训练，其他的没有，所以每个神经元都得到了充分训练（集成学习）
  • 数据增强法：数据越多，过拟合的风险就越小

词向量

怎么处理文本，让一个词在内部表达中具有语义

  1. 独热（one-hot）编码

用与词表等长的向量表示一个词，向量只要一个元素为1，其余为0，第i个元素为1的向量用于表示词表中第i个词

特点：稀疏，简单，但是编码太长，且无法度量词之间的相似性

  1. 分布式表示

稠密向量，每一位都用上

如一个词：（<动物>，<植物>，<食物>）

得到词向量实际做法：词嵌入Word Embedding（将词向量从高维空间嵌入到低维空间中的一个方法）

利用语言模型

词向量也是在训练神经网络语言模型中被训练出来的

如何训练神经网络语言模型：最大似然方法估计神经网络语言模型的参数

如何训练词向量：也是bp算法，将输入固定为1，将要得到的参数当作权重

word2vec模型：一种简化的神经网络语言模型

两种实现方式：

  • 连续词袋模型CBOW：一个句子的含义只与句子中的词有关，与词的顺序无关
    • 求和，然后利用霍夫曼树
      • img
  • 跳词模型Skip-Gram Model：

词向量应用举例：TextCNN

循环神经网络RNN

循环模块：

前i-1个词的输出+第i个词向量

img

双向循环神经网络：

问题的提出：序列前面的内容被后面的内容淹没

方式：正向来一次，反向来一次，得到的向量拼接在一起

长短期记忆网络LSTM：

第三章 对抗搜索

alpha-beta剪枝；蒙特卡洛搜索（四步）；alpha狗的策略网络、估值网络怎么计算、怎么与蒙特卡洛搜索结合；三种基本的强化学习方法；

极小-极大模型

从下往上

极小点：该对方走，选择二者中更小的数

极大点：自己走，选择二者中更大的数

img

alpha-beta剪枝

img

img

蒙特卡洛树搜索

  • 选择
  • 扩展
  • 模拟
  • 回传

选择策略：

对尚未充分了解的节点的探索

对当前具有较大希望节点的利用

信心上限算法UCB

节点不是随机选择，而是根据UCB1选择信心上限值最大的节点

每次选中、模拟、回传后，要从最上面第一层选择子节点，选择信心上限最大的节点进行模拟

可能被选择扩展的节点需要满足：

  • 还有子节点没有生成
  • 在上一节点的子节点中信心上限最大

回传的方式：

这一条路径上所有节点的总扩展次数加1

同色的节点获胜的次数不变（模拟的节点输了）或加1（模拟的节点胜了）

AlphaGo

将神经网络与蒙特卡洛树搜索结合在一起

引入了围棋的经验知识，减少盲目性

主要用的两类网络：

  1. 有监督学习的策略网络

输入：当前棋局，48个19x19的通道

有361个输出，是棋局上每个点的行棋概率

等效为一个分类问题

目标：像人类那样下棋

  1. 估值网络

输入有49个通道

只有一个输出，表示输入的棋局的胜率情况，[-1, 1]

等效为一个回归问题

与蒙特卡洛树搜索融合：

  • 利用：收益好的节点
  • 探索：模拟次数少的节点
  • 经验：落子概率高的节点

由于有估值网络，所以可以直接选择，优先选择Q+u大的子节点，直到遇到叶节点结束，该节点被选中，生成它的所有子节点

对被选中的节点进行模拟，规定了模拟次数与树的深度

回传过程：是正负交替的，直到传到祖先节点

AlphaGo如何确定走步：

根节点子节点中被选中次数最多的节点作为最终的走步

（收益多但被选择次数少的节点可能不太可靠，故选被选择次数最多的节点）

围棋中的深度强化学习方法

强化学习：试错与延迟收益

将收益转化为标注，不能获得所有情况下既正确又有代表性的示例

三种强化学习方法：

  1. 基于策略梯度的强化学习

在强化学习过程中，每个样本只使用一次（样本不一定准确；有足够的样本供其学习）

基于策略梯度的强化学习方法学到的是在每个可落子点行棋的获胜概率（监督学习策略网络学到的是在某个可落子点行棋的概率）

  1. 基于价值评估的强化学习

输入：当前棋局和当前行棋点

输出：取值在[-1, 1]之间的估值

对一个行棋点的价值（即收益）进行评估

  1. 基于演员-评价方法的强化学习

找出关键的点

演员：策略网络

评价：评估网络

收益增量A：评价一步棋的好坏。A越大越说明走了一步妙招

img

AlphaGo Zero

升级版

利用强化学习从零学习，不用人类棋手的数据以及人工特征作为输入

将策略网络和估值网络合并为一个双输出网络

输入：17个通道

没有随机模拟了，只用估值网络

将MCTS结合到深度强化学习中

引入多样性：防止走向错误的方向，对策略网络的输出增加噪声（MCTS具有纠错能力）

第四章 统计机器学习

id3和c4.5方法，id3要算信息增益，c4.5是信息增益比，最后有个什么剪枝（？

分类：

  • 监督学习
  • 非监督学习
  • 半监督学习
  • 弱监督

支持向量机SVM

二类分类器（只能分为两类）

间隔最大化线性分类器，通过核技巧实现非线性分类

线性可分支持向量机 ：

  1. 定义

img

即y_i等于±1

目的是求w和b

  1. 函数间隔

img

  1. 几何间隔

img

  1. 间隔最大化

img

——>

问题转化为如下的凸二次规划问题：

img

img

  1. 学习的对偶算法

利用拉格朗日函数：

img

img

img

img

img

img

img

img

线性可分支持向量机：

引入松弛变量：

img

img

对偶问题对alpha加了一个限制：

img

img

非线性分类问题：使用一个变换，将原空间数据映射到新空间中

SVM应用：文本分类

i是词项，j是文档

t_ij表示第i个词项在文档j中的词频，用来表示权重

df_i：出现词项i的文档树/N，文档频率

idf_i：逆文档频率，idf_i = log(1/df_i)

决策树

决策树模型是一种描述对实例进行分类的树形结构，由节点和有向边组成

节点有两种类型：内部节点和叶节点。内部节点表示一个特征或者属性，叶节点表示一个类

img

  1. 特征选择

按照信息增益选择特征

信息增益：某个特征A对数据集D进行分类的不确定性减少的程度

img

img

img

  1. 决策树生成

①ID3

基本的决策树生成算法

递归的算法

看例子，信息熵的算法类似概率

②C4.5

对ID3的改进

利用信息增益比

img

此时对熵的计算方法不一样，之前是按照最终的分类结果计算，现在是按照当前的分类

C4.5增加了对连续值属性的处理

  1. 决策树剪枝

为了防止过拟合问题

后剪枝：先生成树，再剪枝

从下往上，看子节点是否可以合并到父节点