# 主定理
主定理是用于计算如下递推形式的时间复杂度
$$
T(n)=aT\left(\dfrac nb\right)+f(n)
$$



根据$f(n)$与 $\log_ba$ 的大小关系分为四种情况
$$
f(n)\stackrel{?}{>=<}n^{\log_ba}
$$

1. $f(n)=O\left(n^{\log_ba-\epsilon}\right)$ 可以理解为 $f(n)<n^{\log_ba}$, 则有
$$
T(n)=\Theta\left(n^{\log_ba}\right)
$$
2. $f(n)=\Theta\left(n^{\log_ba}\right)$ 可以理解为 $f(n)=n^{\log_ba}$, 则有
$$
T(n)=\Theta\left(n^{\log_ba}\log n\right)
$$
3. $f(n)=\Omega\left(n^{\log_ba+\epsilon}\right)$ 可以理解为 $f(n)>n^{\log_ba}$, 则有
$$
T(n)=f(n)
$$
4. 第四种情形是特殊的, 当$f(n)=\Omega\left(n^{\log_ba}\log^kn\right)$ 即 $f(n)=n^{\log_ba}\log^kn$时
$$
T(n)=\Theta\left(n^{\log_ba}\log^{k+1}n\right)
$$

# 简化的主定理

如果取$f(n)$是多项式复杂度的, 即 $f(n)=O(n^d)$, 递推式即
$$
T(n)=aT\left(\dfrac nb\right)+O(n^d)
$$
那么就能讲主定理简化为

1. $d<\log_ba$
$$
T(n)=O\left(n^{\log_ba}\right)
$$
2. $d=\log_ba$
$$
T(n)=O(n^d\log n)
$$
3. $d>\log_b a$
$$
T(n)=O(n^d)
$$

时间复杂度分析:主定理

# 一阶马尔可夫链
某一时刻状态转移的概率只依赖前一个状态，状态之间以一定概率转移



![image.png](/static/img/2990e27e65b3c461b5c715dc4b377a7d.image.webp)

将概率写为矩阵，$P_{ij}$表示从状态$i$转移到状态$j$的概率

$$
P=\begin{pmatrix}
0.9&0..075&0.25\\
0.15&0.8&0.05\\
0.025&0.25&0.5
\end{pmatrix}
$$
$P_{ij}$也可以用条件概率写为
$$
P(j|i)
$$
那么初态也可以写完一个向量，$a_i$表示系统处于状态$i$的概率，那么经过$k$次状态转移后，系统的状态就是
$$
P^k a
$$

若令$k\to\infty$，则状态的分布达到稳定；该稳定的状态与初态无关

# 隐马尔可夫模型

隐马尔可夫模型中，系统的状态不能直接观察到，只能通过**传感器**反映。通常来说给定状态转移模型，它只与上一刻的状态有关
$$
P(R_t|R_{t-1})
$$
和传感器模型，它只与当前状态有关
$$
P(U_t|R_t)
$$
还需要给定一个初始分布
$$
P(R_0)
$$
此后先根据转移模型得到转移的分布（此处是矩阵乘法）
$$
P(R_t)=P(R_t|R_{t-1})P(R_{t-1})
$$
然后根据传感器的结果$u_t$修正分布（此处是向量的点乘）
$$
P(R_t|u_t)=\alpha P(u_t|R_t)\cdot P(R_t)
$$

# 确定性环境的决策
定义
- 状态的集合$S$
- 每个状态下可以采取的动作集合$A$
- 奖励函数$R(s,a,s')$，它表示在状态$s$时采取动作$a$转移到状态$s'$获得的奖励

可以定义**效用**是历史所有动作的累加，称为**加性奖励**
$$
U_h(s_0,a_0,s_1,a_1,\cdots)=R(s_0,a_0,s_1)+R(s_1,a_1,s_2)+\cdots
$$

更常用的是**加性折扣奖励**
$$
U_h(s_0,a_0,s_1,a_1,\cdots)=\gamma^0R(s_0,a_0,s_1)+\gamma^1R(s_1,a_1,s_2)+\cdots
$$
其中$\gamma$称为折扣因子，接近$0$时倾向于当前奖励，接近$1$时倾向于长期奖励，等于$1$时退化为纯加性奖励

<center><br><hr width=40%><br></center>

**策略**就是在所有状态下应该采取的动作，**最优策略**是能产生最大效用的策略，它与初始状态无关

由状态$s$开始执行策略$\pi$的效用为
$$
U^\pi(s)=\sum_{t=0}^\infty R(s_t,\pi(s_t),s_{t+1})
$$

若采取加性折扣奖励，则策略$\pi$的效用为
$$
U^\pi(s)=\sum_{t=0}^\infty \gamma^t R(s_t,\pi(s_t),s_{t+1})
$$

# 马尔可夫决策过程MDP

与确定性环境的决策不同的是，马尔可夫决策过程采取动作后得到的状态是随机的，由**转移模型**刻画。$T(s,a,s')$表示采取动作$a$后从状态$s$转移到状态$s'$的概率，即
$$
T(s,a,s')=P(s'|s,a)
$$

那么动作的效用也应由期望定义
$$
U(s_0,a)=E[R(s_0,a,s_t)]=\sum_tP(s_t|s_0,a)R(s_0,a,s_t)
$$

采用策略$\pi$的效用也应该由期望定义（采样加性折扣奖励）
$$
U^\pi(s)=E\left[\sum_{t=0}^\infty \gamma^t R(s_t,\pi(s_t),s_{t+1})\right]
$$

 # 效用与贝尔曼方程
 
 一个**状态的效用**定义为从该状态出发的期望总奖励，正如上一节所说，从状态$s_0$开始执行策略$\pi$获得的期望效用为
$$
U^\pi(s_0)=E\left[\sum_{t=0}^\infty \gamma^t R(s_t,\pi(s_t),s_{t+1})\right]
$$

会存在一个最优的策略$\pi^*$，它比其它的策略具有更大的效用
$$
U^{\pi^*}(s)=\max(U^\pi(s))
$$

假定已知了$\pi^*$的效用为$U(s)$，在状态$s$下，最佳策略$\pi^*$应当选取期望效用最大的动作
$$
\pi^*(s)=\argmax_a \sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma U(s')]
$$

该动作的效用即为该状态的效用，即**贝尔曼方程**

:::info{title="Note"}
$$
U(s)=\max_a \sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma U(s')]
$$
:::

它的解就是各状态的效用

<center><br><hr width=40%><br></center>

同样可以定义**动作效用**为给定状态下采取给定动作的期望效用
$$
Q(s,a)= \sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma U(s')]
$$
进而写出关于动作效用的贝尔曼方程
$$
Q(s,a)= \sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma \max_{a'}Q(s',a')]
$$

# 价值迭代算法
价值迭代方法是一个求解贝尔曼方程的迭代方法，可以描述如下

0. 初始化所有效用为零
1. 枚举每个状态，对于当前状态$s$，枚举允许的所有动作，计算它们的效用
$$
Q(s,a)= \sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma U(s')]
$$
2. 选择具有最大效用的动作$a$，用它的效用更新$s$的效用
$$
U'(s)=\max_a Q(s,a)
$$
3. 更新完所有状态后，令$U=U'$，返回`1`进行下一轮迭代

价值迭代最终可以收敛于贝尔曼方程的唯一解

# 策略迭代算法
与价值迭代算法不同，策略迭代算法针对于策略。它可以描述如下

0. 初始化策略$\pi$
1. 依据策略$\pi$计算每个状态的效用（进行迭代求解）
$$
U^\pi(s)=\sum_{s'}P(s'|s,\pi(s))[R(s,\pi(s),s')+\gamma U^\pi(s')]
$$
2. 基于计算得到的效用改进策略$\pi$
$$
\pi'(s)=\argmax_a \sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma U^\pi(s')]
$$
3. 若改进的策略无变化，则停止迭代；否则回到`1`继续迭代

# 被动强化学习

被动强化学习指的是采取固定的策略$\pi$，尝试学习效用函数$U^\pi(S)$

一个简单的方法是**直接效用估计**
- 进行多次实验，统计每个状态的效用
- 对每个状态的效用进行平均，只要实验的次数足够多，均值将收敛到期望值

由于忽视了状态之间的联系，直接效用估计收敛速度较慢。解决这个问题可以使用**自适应动态规划**
- 通过反馈可以得到奖励函数
- 通过动作的结果可以得到转移模型
- 将学习到的转移模型与奖励函数代入贝尔曼方程中求解各个状态的效用

另外可以从另一个角度出发得到**时序差分学习TD**，它采取迭代的方式计算效用

0. 初始化效用$U^\pi$
1. 学习ing：如果在状态$s$下采取动作$\pi(s)$达到了状态$s'$，则更新$s$的效用；其中$N(s)$是$s$出现的频率，替换概率
$$
U^\pi(s)=U^\pi(s)+\alpha N(s)[R(s,\pi(s),s')+\gamma U^\pi(s')-U^\pi(s)]
$$
2. 反复执行更新操作直到收敛

TD方法调整状态的效用来达到与其观测到的后继状态一致，而自适应动态规划调整状态的效用来达到与所有可能发生的后继状态一致

TD**不需要通过转移模型**来进行更新

# 主动强化学习

可以利用策略迭代方法或者价值迭代方法求解最优策略，称为**主动自适应动态规划**

主动动态规划是基于贪心的，不一定收敛到最优策略，因而引入$\epsilon-$贪心法，即以$\epsilon$的概率尝试当前策略以外的动作，以$1-\epsilon$的概率做出当前策略的动作，称其为**探索与利用**

- 探索：尝试所学习到“最优策略”以外的动作
- 利用：选择当前最优的动作

在选择动作时，若要进行探索，则应选取当前状态下探索次数少的动作

同样也可以推广得到**主动时序差分学习**，不过随着策略的更新，效用函数$U^\pi$也要更新；在进行“探索”时会尝试多种策略，这意味着需要保存多个效用函数，这不好，进而将效用迭代换为**动作效用的迭代**

> $$
> Q(s,a)= \sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma \max_{a'}Q(s',a')]
> $$

更新规则与被动类似，同样使用频率代替转移模型

$$
Q(s,a)=Q(s,a)+\alpha N(s)[R(s,a,s')+\gamma\max_{a'}Q(s',a')-Q(s,a)]
$$

这种方法称为**Q-learning**，其中的$Q$函数是最佳策略下的动作效用；与之对应的是**SARSA**，它使用实际采取的动作效用进行更新（不计算平均）
$$
Q(s,a)=Q(s,a)+\alpha [R(s,a,s')+\gamma\max_{a'}Q(s',a')-Q(s,a)]
$$

当进行探索时，若产生负面奖励，由于平均，Q-learning不会惩罚该动作，而SARSA会

Q-learning是一种离策略（off-policy）学习算法，它所学习的Q值回答了问题“假设我停止使用我正在使用的任何策略，并依照（根据估计）选择最佳动作的策略开始行动，那么这个动作在该状态下的价值是多少？”

 SARSA是一种同策略（on-policy）的算法，它通过学习Q值回答了问题“假设我坚持自己的策略，那么这个动作在该状态下的价值是多少？”

马尔可夫与强化学习

# 基本的RNN模型

RNN模型的隐藏层是循环连接的，它的上一次输出会被重新输入

<center><img src="/static/img/d693c6253e90bce1578d597261a8d7f0.image.webp" width=30%></center>



其中$z$是隐藏层，$x$是输入，$y$是输出；隐藏层的输出是与时间相关的，可以记为
$$
z_t=g_z(W_{z,z}z_{t-1}+W_{x,z}x_t)
$$
输出层倒是只与隐藏层输出有关
$$
y_t=g_y(W_{z,y}z_t)
$$

# 基于时间的反向传播

给定一系列的输入向量及其对应的输出
$$
x_1,\cdots, x_T,y_1\cdots,y_T
$$
可以将网络进行$T$步展开，转换为前馈网络

![image.png](/static/img/2f512603db9c7d98778c4e2bf6ab44c1.image.webp)

其中的权重是同步更新的，称为**基于时间的反向传播（BPTT）**

# 堆叠循环神经网络（SRNN）

堆叠循环神经网络具有多个隐藏层，它们的输出都是与时间相关的。同样可以将它展开

![image.png](/static/img/42caa6e77070608ac6615dd3cdb14763.image.webp)

# 长短期记忆（LSTM）

LSTM是一种特殊的RNN，它分为三个步骤：遗忘，记忆，输出，它分为四层，结构如下

![image.png](/static/img/88a6bcba0defa40f61b3a7f48355f199.image.webp)

其中$h$是隐藏层的输出，$x$是输入

首先由遗忘门$f$决定要舍弃哪些信息，它接收上一次隐藏层的输出$h_{t-1}$与本次的输入$x_t$，经由$Sigmoid$输出$0-1$之间的指数。输出$1$表示保留全部记忆，输出$0$表示忘记全部记忆


![image.png](/static/img/0ae9f3f14ac78922c4dfb64d6bb21b3c.image.webp)

输出可以抽象地写为
$$
f_t=\sigma(W_f[h_{t-1},x_t]+b_f)
$$

然后由输入门$i$决定要保存的新信息，它接收上一次的隐藏层输出$h_{t-1}$和输入$x_t$，经由$Sigmoid$输出$0-1$之间的指数；$tanh$层接收$h_{t-1}$与$x_t$，输出一个新信息向量$\tilde{C_t}$，它被上面输入门的指数作用后向下一层传递。当$i_t$等于$1$时表示完整传递，$i_t$为$0$时表示不记忆新信息

![image.png](/static/img/49329b459a7274fab6194a4516112f2a.image.webp)

可以抽象地将它们的输出表示为
$$
i_t=\sigma(W_i[h_{t-1},x_t]+b_i)
$$
$$
\tilde{C_t}=\tanh(W_c[h_{t-1},x_t]+b_c)
$$

然后根据遗忘门和输入门更新记忆单元

![image.png](/static/img/ee46a633e260481d2f191ab7e3bb368b.image.webp)

$$
C_t=f_t\cdot C_{t-1}+i_t\cdot C_t
$$

最后由输出门$o$决定记忆单元的输出。它接收$h_{t-1},x$，经由SIgmoid输出一个$0-1$之间的指数，与记忆单元的值作用后输出

![image.png](/static/img/d3ad81878c443264d477efbde350c905.image.webp)

$$
o_t=\sigma(W_o[h_{t-1},x_t]+b_o)
$$
$$
h_t=o_t\cdot\tanh(C_t)
$$

循环神经网络RNN

# 卷积层
神经网络中的卷积是为了模拟视觉皮层细胞的感受野表现出**空间局部性**




![image.png](/static/img/bb3424b6f111a4c64e82d8a4c9c8ad95.image.webp)

此处的卷积是对上层节点输出的加权和，权值矩阵称为**卷积核**

# 池化层

池化将相邻的几个数据合并为一个数据，使得数据的尺寸减小


![image.png](/static/img/342a36d665907931c7268429a1226185.image.webp)

池化能降低卷积层对位置的敏感性；同时降低对空间降采样表示的敏感性；减小了下一层输入大小，进而减小计算量和参数个数；在一定程度上能防止过拟合的发生

池化也称子采样和下采样

# 多分类神经网络的输出层

在二分类问题中，线性分类器使用Logistic函数
$$
\sigma(x)=\dfrac{1}{1+e^{-x}}
$$

在多分类问题中，输入和输出都需要是一个向量。记输入为
$$
x=(x_1,x_2,\cdots,x_d)
$$
则定义**Softmax**
$$
softmax(x)_k=\dfrac{e^{x_k}}{\sum_{i}e^{x_i}}
$$
Logistic函数就是$d=2$情形下的Softmax

# 暂退法（Dropout）

在训练过程中，对于每个神经元以概率$p$保留，以$1-p$的概率丢弃；丢弃即将其输出固定为0，不参与梯度计算，也不参与权值更新

通过随机丢弃神经元，网络的不同部分在每次训练时都会变得不同，相当于训练多个小规模的子网络。这可以让网络不再过度依赖某些特定的神经元或特征，从而提高网络的泛化性能，使其在新数据上的表现更好

![image.png](/static/img/9615cbd753dbc4192853527a1a66d172.image.webp)

可以把Dropout想象成是在训练过程中让神经网络“强制分工合作”，因为任何一个神经元都可能被忽略，所以网络必须学会让不同的神经元都能贡献一部分任务，从而增强模型的鲁棒性和泛化能力

# 批量归一化BN

机器学习假设训练数据和测试数据是独立同分布的，这是通过训练数据获得的模型能够在测试集获得好的效果的基本保障。不过训练过程中，每一层的参数更新会导致上层的输入数据分布发生变化，层层叠加后，高层的输入分布变化会非常剧烈，给训练带来困难

在训练时，对于每一个小批量样例的前向传播，将神经网络中的某个节点的输出进行重新缩放；假定某个节点$z$在训练中一个批量的数据输出为
$$
z_1,z_2,\cdots,x_m
$$
那么将其重新缩放为
$$
z'_i=\gamma\dfrac{z_i-\mu}{\sqrt{\epsilon+\sigma^2}}+\beta
$$
其中$\epsilon$是防止除数为零的较小的常数，$\mu$是均值$\sigma$是方差，$\beta$和$\gamma$是可以学习的参数

在前传播中，对一层的节点左批量归一化后再输入给下一层的节点。批量归一化可以带来一系列的性能改善，如加速SGD收敛，防止梯度消失，缓解过拟合等。在某种程度上，批量归一化的效果与残差网络的效果相似

# 残差网络ResNet

经典的神经网络层间关系为
$$
z^{(i)}=g^{(i)}(W^{(i)}z^{(i-1)})
$$
在残差网络中，从输入直接引入一个短连接到非线形层的输出上，即
$$
z^{(i)}=g^{(i)}(z^{(i-1)}+g^{(i)}(W^{(i)}z^{(i-1)}))
$$
用图形象地画出即
<center><img src="/static/img/4407243f989108f80594f0ef0b56c7b0.image.webp"></center>

使用残差网络后，能有效缓解高层数网络的梯度消失导致的退化问题（训练集loss增大）

卷积神经网络CNN

# 神经网络与其前向传播
一个三层的简单神经网络可以如图画出

![](https://gbwater.icu/static/img/9d0b1982723b4d25dee83730da1529bf.image.webp)



其中$x_i$是**输入**，$+1$是**偏置**，各$W$是**权重**，各$b$是各个神经元的**偏置**，各$z$是各个神经元的总输入，各$a$是各神经元的**输出**，它们满足
$$
z^{(2)}_i=\sum_j W_{ij}x_j+b^{(1)}_i
$$
$$
a^{(1)}_i=f(z_i^{(1)})
$$

写成矢量形式会更加清晰
$$
\bm{z}^{(l+1)}=\bm{W}^{(l)}\bm{a}^{(l)}+\bm{b}^{(l)}\quad \bm{a}^{(l+1)}=f(\bm{z}^{(l+1)})
$$

实际上神经网络可以不止两层，输出神经元也可以不止一个。从输入一层一层地计算得到输出的过程就叫**前向传播**

# 神经网络的训练与误差反向传播

神经网络的训练即调整各个权重和偏置，使得**代价函数**最小。假定有很多个训练样本
$$
(x^{(1)},y^{(1)}),\cdots,(x^{(m)},y^{(m)})
$$

对于单个样本定义其代价函数为
$$
J(W,b,x,y)=\dfrac12||h_{W,b}(x)-y||^2
$$

总的代价函数除了各个样本的代价均值外，还要加上权重的惩罚项（**Weight decay**）
$$
J(W,b)=\left[\dfrac1m\sum_{i=1}^m\left(\dfrac12||h_{w,b}(x^{(i)})-y^{(i)}||^2\right)\right]+\dfrac\lambda2\sum_{i,j,l}|W_{i,j}^{(l)}|^2
$$

其中$\lambda$是一个超参数，较大的$\lambda$会使得训练倾向于减小权值。显然（好像也不显然）$J$并不是一个凸函数，理论上梯度下降法训练无法达到全局最优；不过实践中发现梯度下降法效果仍然不错

在更新参数时，也应遵循梯度下降法，按照代价函数的梯度更新参数
$$
W_{ij}^{(l)}=W_{ij}^{(l)}-\alpha\dfrac{\partial}{\partial W_{ij}^{(l)}}J(W,b)
$$
$$
b^{(l)}=b^{(l)}-\alpha\dfrac{\partial}{\partial b^{(l)}}J(W,b)
$$

鉴于
> $$
> z^{(2)}_i=\sum_j W_{ij}x_j+b^{(1)}_i
> $$
> $$
> a^{(1)}_i=f(z_i^{(1)})
> $$

只需要知道每个神经元的$z$误差即可，定义**感知误差**，这是一个向量
$$
\delta^{(l)}=\dfrac{\partial J(W,b)}{z^{(l)}}
$$
利用链式法则可以得到

$$
\delta^{(l)}=\dfrac{\partial a^{(l)}}{z^{(l)}}\cdot\dfrac{\partial z^{(l+1)}}{\partial a^{(l)}}\cdot\dfrac{\partial J(W,b)}{\partial z^{(l+1)}}=f'_l(z^{(l)})(W^{(l)})^T\delta^{(l+1)}
$$

即得到了误差的递推关系。那么利用感知误差更新各参数
$$
\dfrac{\partial}{\partial W_{ij}^{(l)}}J(W,b,x,y)=a_j^{(l)}\delta_i^{(l+1)}
$$
$$
\dfrac{\partial}{\partial b_i^{(l)}}J(W,b,x,y)=\delta_i^{(l+1)}
$$

# 梯度消失和梯度爆炸

神经网络的每一层应当有
$$
a_n=f(Wa_{n-1})
$$
那么求其导有
$$
\dfrac{\partial a_n}{\partial a_{n-1}}=f'\cdot W
$$

那么当$f'<1$时，梯度会在传播中越来越小；而$W>1$时，梯度会越来越大。称之为梯度消失与梯度爆炸