强化学习基础笔记

强化学习与监督学习的区别：

(1) 训练数据中没有标签，只有奖励函数 (Reward Function)。

(2) 训练数据不是现成给定，而是由行为 (Action) 获得。

(3) 现在的行为 (Action) 不仅影响后续训练数据的获得，也影响奖励函数 (Reward Function) 的取值。

(4) 训练的目的是构建一个“状态 \rightarrow 行为”的函数，其中状态 (State) 描述了目前内部和外部的环境，在此情况下，要使一个智能体 (Agent) 在某个特定的状态下，通过这个函数决定此时应该采取的行为。希望采取这些行为后，最终获得最大的奖励函数值。

Q 学习

定义

在这里，我们假设状态数有限，行为数有限。

第一个假设:

第二个假设: 下一个时刻的状态只与这一时刻的状态和这一时刻的行为有关

一些假设

MARKOV DECISION PROCESS (MDP)

①在 t=0 时刻，环境给出一个初始状态 s_0 \sim p(s_0)

②for t=0 : end

• 智能体选择行为为 a_t
• 环境采样奖励函数 r_t \sim R(\cdot \mid s_t, a_t)
• 环境产生下一个状态：s_{t+1} \sim P(\cdot \mid s_t, a_t)
• 智能体获得奖励函数 r_t 和下一个状态 s_{t+1}

目标: 我们需要学习一个策略 (Policy) \pi^*，这是一个从状态到行为的映射函数，也就是可以得到a_{t+1}，使得最大化累积的奖励。

待优化目标函数

增强学习中的待优化目标函数是累积奖励，即一段时间内的奖励函数加权平均值：

G_t = R_{t+1} + \gamma R_{t+2} + \dots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}

在这里，\gamma 是一个衰减项。

增强学习中已经知道的的函数是： R_s^a = \mathbb{E}[R_{t+1} \mid S_t = s, A_t = a]

需要学习的函数是： \pi(S_t, a_t) = p(a_t \mid S_t)

根据一个决策机制 (Policy)，我们可以获得一条路径：
s_0, a_0, r_0, s_1, a_1, r_1, \dots

定义1：价值函数 (Value Function) 是衡量某个状态最终能获得多少累积奖励的函数：
V^{\pi}(s) = \mathbb{E} \left[ \sum_{t \geq 0} \gamma^t r_t \mid s_0 = s, \pi \right]

定义2：Q函数是衡量某个状态下采取某个行为后，最终能获得多少累积奖励的函数：
Q^{\pi}(s, a) = \mathbb{E} \left[ \sum_{t \geq 0} \gamma^t r_t \mid s_0 = s, a_0 = a, \pi \right]

V^{\pi}(s) = \sum_{a \in \mathcal{A}} p(a \mid s) Q^{\pi}(s, a)

其中

• 已知

• 未知

• \sum_{s' \in \mathcal{S}} P_{ss'}^a (R_s^a + \gamma V^{\pi}(s')) \Rightarrow Q^{\pi}(s, a)

但倘若我们已经知道\pi(s, a) = p(a|s) \Rightarrow V^{\pi}(s) = ✓ \cdot ✓ \cdot (✓ + \gamma V^{\pi}(s'))

\Rightarrow 可见这是一个线性方程 \Rightarrow 因此我们具体地做法如下

先给p(a|s) 一个初始值 \Rightarrow 然后求得V^{\pi}(s) \Rightarrow 利用V^{\pi}(s)再对\pi(s, a)来调整

\Rightarrow Q^{\pi}(s, a) = \sum_{s' \in S} P_{ss'}^{a} (R_{s}^{a} + \gamma V^{\pi}(s'))

\Rightarrow 原式 = V^{\pi}(s) = \sum_{a \in A} P(a|s) \cdot Q^{\pi}(s, a)

\Rightarrow 若Q^{\pi}(s, a)已知，我们要让V^{\pi}(s)最大 \Rightarrow 怎么调p(a|s)？

\Rightarrow 设\pi(s, a) = \begin{cases} 1 & \text{若} \, a = \arg\max \, Q(s, a) \\ 0 & \text{其他} \end{cases} \Leftarrow 对于使得Q(s, a)最大的动作a，让其\pi(s, a) = 1 \Rightarrow 每步定有一个最正确的策略

别忘了\pi(s, a) = p(a|s)

\Rightarrow 不断迭代（必定收敛，证明略）

\Rightarrow 则有V^{\pi}(s) = \sum_{a \in A} \pi(s, a) \cdot Q^{\pi}(s, a)

综上所述: 简单来说就是定住 V 算 \pi 或者定住 \pi 算 V

找最佳策略的迭代算法

输入 E = \langle S, A, P, R \rangle

过程：
1° 初值：\forall s \in S, V(s) = 0 \quad \pi(s, a) = \frac{1}{|A|}

​ 2° while (1)
​ {
​ while (1)
​ {
\forall s \in S, 计算

​ V'(s) = \sum_{a \in A} \pi(s, a) \sum_{s' \in S} P_{ss'}^{a} \left( R_{s}^{a} + \gamma V^{\pi}(s') \right)

				     if $\|V - V'\| < \epsilon$  ( $V$ 收敛)
					       break
				    else
				            $V = V'$
				   }

​ \forall s \in S', a \in A, 计算

​ Q(s, a) = \sum_{s' \in S} P_{ss'}^{a} \left( R_{s}^{a} + \gamma V^{\pi}(s') \right)

​ 重新安排 \pi \Rightarrow \pi(s, a) = \begin{cases} 1 & \text{if } a = \arg\max Q(s, a) \\ 0 & \text{else} \end{cases}

​ if \|\pi - \pi'\| < \delta （当重新安排的\pi和以前\pi差异小时退出循环）

		     break

​ else \pi = \pi'

​ }

​ 输出最优策略\pi

注意，这个算法有一定的劣势：

(1) 状态数和行为数很多时，算法不现实 \Rightarrow 也就是说只有状态数和行为数少的情况下，算法才收敛

聪明做法

再改进是DQN了

思路: 深度神经网络模拟Q^*(s, a) \Rightarrow Q(s, a; \theta) \approx Q'(s, a) \Rightarrow 用Bellman equation和Deep network结合

原式 \Rightarrow Q^*(s, a) = \mathbb{E}_{s' \sim \varepsilon} \left[ r + \gamma \max_{a'} Q^*(s', a') \mid s, a \right]

\Rightarrow (1) 向前计算 \Rightarrow Loss function

\Rightarrow (2) 向后传播 \Rightarrow \nabla_{\theta_{i}} L_{i}(\theta_{i}) = \mathbb{E}_{s, a \sim p(.);s' \sim \varepsilon} \, \left[ \left( r + \gamma \max_{a'} Q(s', a'; \theta_{i-1}) - Q(s, a; \theta_{i}) \right) \nabla_{\theta_{i}} Q(s, a; \theta_{i}) \right]

贪心算法: 以小概率去尝试

DQN算法流程：

① 初始化Q(s, a, \theta)，初始化记忆内存D

② for episode = 1 \sim M do （进行了M次游戏）

• 初始化s_1（即进入游戏初始画面）

③ for t = 1 \sim T do （依时间采样）

• if random() < given_probability

  • 采取随机行为为a_t

• else

  • a_t = \max Q(s_t, a_t, \theta)

• 设置 S_{t+1} \sim P_{S_{t} S_{t+1}}^{a_t} \, , \, r_{t} = R_{S_{t}}^{a_t}

• 将(s_t, a_t, r_t, s_{t+1})存入记忆内存D

• 随机从D中取出一个batch的(s_t, a_t, r_t, s_{t+1})数据，根据(s_j, a_j, r_j, S_{j+1})_{j=1 \sim p}

  • 设置y_j = \begin{cases} r_j & \text{如果} \, s_{j+1} \, \text{是终止状态} \\ r_j + \gamma \max Q(s_{j+1}, a', \theta) & \text{其他} \end{cases}

• 更新\theta = \theta - \left( y_j - Q(s_j, a_j, \theta) \right) \nabla_{\theta} Q(s_j, a_j, \theta)

输出深度神经网络Q(s, a, \theta)

Q-learning的劣势：

（1）在一些应用中，状态数或行为数很多时，会使Q函数非常复杂，难以收敛。例如图像识别方面的应用，状态数是（像素值取值范围）^(像素个数)。这样的方法，对图像和任务没有理解，单纯通过大数据来获得收敛。

（2）很多程序，如下棋程序等，REWARD是最后获得（输或赢），不需要对每一个中间步骤都计算REWARD。

\Rightarrow Policy Gradient

主要思想：每个状态下，根据当前现有的P(a_t|s_t)来采样a_t \Rightarrow 如此往复，获得一组状态-行为对= s_1, a_1, s_2, a_2, \dots, s_t,a_t

此时，最终得到的奖励函数为r_T，假设r_T可取正负值 \Rightarrow 其中正值表示获得奖励，负值表示惩罚

最终，我们根据r_t去修改每一步的P(a_t|s_t) \Rightarrow P(a_t|s_t) = P(a_t|s_t) + \alpha r_T \Rightarrow 如果获得奖励，这一步的概率就大一些

如果P(a_t|s_t) \sim Q(s_t, a_t, \theta) \Rightarrow 则有 \theta = \theta + \alpha r_T \nabla_{\theta} Q(s_t, a_t, \theta) 其中 \nabla是让 Q 在 \theta 处求偏导

缺点：\begin{cases} \text{训练过程更加缓慢} \\ \text{要特别精心去调节} \, r_T \, \text{，才能相对收敛} \end{cases}

改进：

其中 V(s_t) 是预期值 \Rightarrow 是估值函数 \Rightarrow 回顾之前的估值函数定义

\Rightarrow 价值函数是衡量在某个状态下，最终能获得多少累计奖励： \Rightarrow V^{\pi}(s) = \mathbb{E} \left( \sum_{t=0}^{\infty} \gamma^{t} r_t \Big| s_0 = s, \pi \right)

\Rightarrow 怎么算呢？在S很多时，是算不了的 \Rightarrow 那么怎么做呢？\Rightarrow 用深度网络 \Rightarrow 叫做估值网络 \Rightarrow 输入S，输出是最终的收益值

Actor-Critic算法：

初始化Q(s, a, \theta)，初始化V(s, \phi)，初始化 p_\theta(a|s) = \text{softmax}[Q(s, a, \theta)]

for episode = 1 \sim M do

• 在现有策略p_\theta(a|s)下采样m个轨迹
• \Delta \theta \leftarrow 0

for i = 1 \sim m do
- for t = 1 \sim T do
- 计算A_{t}^{i} = \sum_{t' \geq t} \gamma^{t' - t} r_{t }^{i} - V(S_{t}^{i}, \phi)
- \Delta \theta \leftarrow \Delta \theta + A_{t} \nabla_{\theta} \log[p_{\theta}(a_{t}^{i}|S_{t}^{i})]
- \Delta \phi = \sum_{i} \sum_{t} \nabla_{\phi} \|A_{t}^{i}\|^{2}

• 更新\theta = \theta + \alpha \Delta \theta
• 更新\phi = \phi + \beta \Delta \phi

输出Q(s, a, \theta)，V(s, \phi)

总结：

（1）目前强化学习的发展状况：在一些特定的任务上达到人的水平或胜过人，但在一些相对复杂的任务上，例如自动驾驶等，和人存在差距。

（2）和人的差距，可能不完全归咎于算法，传感器、机械的物理限制等，也是决定性因素。

（3）机器和人的另一差距是：人有一些基本的概念，依据这些概念，人能只需要很少的训练就能学会很多，但机器只有通过大规模数据，才能学会。

（4）但是，机器速度快，机器永不疲倦，只要有源源不断的数据，在特定的任务上，机器做得比人好，是可以期待的。

特征提取和特征选择

特征提取：主成分分析

特征选择：自适应提升算法 AdaBoost （这两个方法非常常用）

问题描述：

特征选择问题：特征向量N个维度有冗余 \Rightarrow 那么如何从N个维度中选取M个维度（M < N），从而使得识别率最高。

N个维度 \{x_{i1}, x_{i2}, \dots, x_{iN}\}，需要构造一个函数从而能利用这N个维度的信息。

\Rightarrow 构造f_1(x_i \sim x_{iN}), f_2(x_i \sim x_{iN}), \dots, f_M(x_i \sim x_{iN}) \Rightarrow 维度从N维降到M维 \Rightarrow 希望f_1 \sim f_M可以充分保留特征信息

\Rightarrow 此问题叫做特征提取。

主成分分析 \Rightarrow 构造一个 A, b 使 Y = A x + b \Rightarrow 对比之前 Y = W^T x + b \Rightarrow 其中

主成分分析可以看成是一个一层的有 M 个神经元的神经网络 \Rightarrow 注意，主成分分析中 x 是无标签的（Label）

想到之前自编码器也是如此 \Rightarrow AE的做法 \Rightarrow 可以通过神经网络训练的方式 \Rightarrow 来获得 A 矩阵中的参数

再来看PCA做法

PCA = 主成分分析 \Rightarrow 其核心是：寻找使方差最大的方向，并在该方向上投影。

N = 2，M = 1 \Rightarrow 建立二维坐标系，将所有点投影到数据坐标系上 \Rightarrow 2维变换为1维

\Rightarrow 其方程为 Y = A(x - \bar{x}) 其中 \bar{x} = E(x) = \frac{1}{P} \sum_{j=1}^{P} x_j

\Rightarrow A是 M \times N 矩阵 \Rightarrow A = \begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_m \end{bmatrix} 每一个小a_i代表一个投影方向 \Rightarrow 我们要找一个方差最大的方向来进行投影。

\Rightarrow 根据公式 Y = A(x - \bar{x}) \Rightarrow $Y = \begin{bmatrix}
a_1 (x - \bar{x}) \
a_2 (x - \bar{x}) \
\vdots \
a_m (x - \bar{x})
\end{bmatrix}$

\Rightarrow 假设训练样本 x 有 p 个 \Rightarrow \{x_i\}_{i=1\sim p}

\Rightarrow 原式变成 \Rightarrow $Y_i = \begin{bmatrix}
a_1 (x_i - \bar{x}) \
a_2 (x_i - \bar{x}) \
\vdots \
a_m (x_i - \bar{x})
\end{bmatrix} = \begin{bmatrix}
y_{i1} \
y_{i2} \
\vdots \
y_{im}
\end{bmatrix} \quad (i = 1 \sim p)$

\Rightarrow 我们要寻找一个方向 a ，来使得方差最大 \Rightarrow 最大化 \sum_{i=1}^p (y_{i1} - \bar{y}_{i1})^2

\Rightarrow

\Rightarrow \bar{y}_{i1} = \frac{a_1}{p} \left( \sum_{i=1}^{p} x_i - p \bar{x} \right)

\Rightarrow 又 \because \bar{x} = \frac{1}{p} \sum_{j=1}^{p} x_j \\$ \Rightarrow$ $ \bar{y}{i1} = \frac{a_1}{p} \left( \sum{i=1}^{p} x_i - p \cdot \frac{1}{p} \sum_{j=1}^{p} x_j \right) = 0 \$

\Rightarrow 综上所述

\Rightarrow 继续往下推导

\Rightarrow \sum_{i=1}^{p} (y_{i1} - \bar{y}_{i1})^2 = a_1 \Sigma a_1^T \Rightarrow 其中 \quad \Sigma = \sum_{i=1}^{p} (x_i - \bar{x})(x_i - \bar{x})^T 称作协方差矩阵

\Rightarrow 还必须对 a_1的大小进行优化 \Rightarrow 问题变成：

\Rightarrow 用拉格朗日乘子法

\Rightarrow E(a_1) = a_1 \Sigma a_1^T - \lambda (a_1 a_1^T - 1) \Rightarrow 向量求导: \frac{\partial E}{\partial a_1} = \left( \Sigma a_1^T - \lambda a_1^T \right)^T = 0

\Rightarrow \Sigma a_1^T = \lambda a_1^T \quad (a_1^T \text{ 是 } \Sigma \text{ 的特征向量})(\lambda \text{ 是 } \Sigma \text{ 的特征值}) \Rightarrow 线代知识

\Rightarrow a_1 (\Sigma a_1^T) = a_1 (\lambda a_1^T) = \lambda

\Rightarrow \lambda 是 \Sigma 最大的那个特征值 \Rightarrow 而 a_1 是 \Sigma 最大的那个特征值对应的特征向量 且 a_1 a_1^T = 1

\Rightarrow 原问题变成最大化 \lambda \Rightarrow 原二维例子中 \Rightarrow 二维例子结束

\Rightarrow 但是多维情况下问题怎么做？\Rightarrow 继续求 a_2

\Rightarrow 原问题变成

拉格朗日乘子法：

E(a_2) = a_2 \Sigma a_2^T - \lambda (a_2 a_2^T - 1) - \beta a_2 a_1^T \Rightarrow \frac{\partial E}{\partial a_2} = (\Sigma a_2^T - \lambda a_2^T - \beta a_1^T)^T = 0 \Rightarrow 即 \Sigma a_2^T - \lambda a_2^T - \beta a_1^T = 0

要证明：\beta = 0

(\Sigma a_2^T - \lambda a_2^T - \beta a_1^T)^T = 0 \Rightarrow a_2 \Sigma - \lambda a_2 - \beta a_1 = 0

\Rightarrow \Sigma是一个对称矩阵，即 \Sigma = \Sigma^T \Rightarrow

\Rightarrow a_2 \Sigma - \lambda a_2 - \beta a_1 = 0 \Rightarrow (a_2 \Sigma - \lambda a_2 - \beta a_1) a_1^T = 0 \Rightarrow a_2 (\Sigma a_1^T) - \lambda (a_2 a_1^T) - \beta a_1 a_1^T = 0\Rightarrow 其中正交关系:

\Rightarrow (由于前面得到) \Rightarrow \Sigma a_1^T = \lambda a_1^T \Rightarrow \lambda 是 \Sigma 最大的特征值，不是 \lambda

\Rightarrow 原式= a_2 \lambda_1 a_1^T - \lambda \cdot 0 - \beta = 0 \Rightarrow 0 - 0 - \beta = 0 \Rightarrow \beta = 0

\Rightarrow 导致结果如下：

\Rightarrow 如果要继续求 a_3 \Rightarrow 原问题变成

PCA算法总结：

\Rightarrow 这就是整个降维的工作。

\Rightarrow 求特征值用 SVD 算法 (Singular Value Decomposition)

人脸识别方面的应用 \Rightarrow 没学

特征选择：

X = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_N \end{bmatrix} \Rightarrow 特征提取是怎么做的？ \Rightarrow 先构造一个函数把 N 个特征全部用上，再构造一个f 将其降低到低维度。

\Rightarrow 特征选择是怎么做的？ \Rightarrow 从 N 个特征中选 M 个使识别率最高（可能有一些是噪声）。

\Rightarrow 选法数： C_N^M = \frac{N!}{M!(N - M)!} \Rightarrow 可见如果 N大 M小 ，这个值将会是天文数字
\Rightarrow 这是一个离散化问题 \Rightarrow 对于连续化问题在它求最优的时候，至少有导数 ，只要有导数，就可以用梯度下降。
\Rightarrow 但是本问题无法求导数 \Rightarrow $
\begin{cases}
1^\circ\text{ 暴力破解} \
2^\circ\text{ 启发性的方法} \Rightarrow \text{ 如递增法}
\end{cases}
$

①递增法 先选一个特征X_1 \Rightarrow N个特征中识别率最高的特征 \Rightarrow 固定X_1，选X_2 \Rightarrow 使\{X_1, X_2\}组合的识别率最高 \Rightarrow 不断循环

②递减法 \Rightarrow N个特征中测一个识别率，再减去一个特征，再测一下识别率，若更好，就继续。

但是这些方法不常用 \Rightarrow 因为用神经网络已经可以做到这个事了。

我们接下来要说的是另一种方法 \Rightarrow 自适应提升算法 即：\text{AdaBoost}

数据集 T = \{(x_1, y_1), \dots, (x_N, y_N)\}

二分类问题 Y = \{-1, +1\}

$
\begin{cases}
\text{输入：} T = {(x_i, y_i)}_{i = 1 \sim N} \
\text{输出：分类器 } G(x) = \pm 1
\end{cases}
$

算法流程：

先是一个弱分类器，只用一个特征（不好，但是总比瞎猜好）

随后是重采样过程，更多采样分错的样本，更少的采集已经分对的训练样本。因此被分错的训练样本可能被采集了不止一次，而有一些分对的没有被采集到。

此时再进行评估，选出一个训练样本，在新数据集中，使得其识别率更高。

\Rightarrow 因此有了 两个特征和两个弱识别器

\Rightarrow 再构造第三个识别器。再进行采样，若前两个识别器分的样本都正确，那么给它最小的权重，对于 '一个分对一个分错' 的样本，给它大一点的权重，对于两个识别器都分错的样本，给它最大的权重

\Rightarrow 结果是，第三个识别器将更多的包含前两个分错的样本 ，再去找一个特征，让其在这个训练集上表现更好

\Rightarrow 最后把这些弱分类器取加权平均值

流程：

① 初始化采样权重

​

② 对 m = 1, 2, \dots, M （M 是弱分类器个数）

​ 用 D_m 采样 N 个训练样本，在训练样本上获得弱分类器 G_m(x) = \pm 1

③ 计算加权错误率

​ e_m = P(G_m(x_i) \neq y_i) = \sum_{i=1}^N W_{mi} \, I(G_m(x_i) \neq y_i) \quad (e_m < \frac{1}{2})

​ \alpha_m = \frac{1}{2} \log \frac{1 - e_m}{e_m} \quad (\text{识别器 } G_m(x_i) \text{ 的权重} \quad \alpha_m > 0)

④ 更新权重分布

​ D_{m+1} = (W_{m+1,1}, \, W_{m+1,2}, \, \dots, \, W_{m+1,N})

​ 下一次在每个样本点上的分布 \Rightarrow \, W_{m+1,i} = \frac{W_{m,i}}{Z_m} \exp\{-\alpha_m y_i G_m(x_i)\}

​ Z_m = \sum_{i=1}^N W_{m,i} \exp\{-\alpha_m y_i G_m(x_i)\}

⑤ 回到 ② 循环 M 次

​ 最后的识别器 G(x) $
\begin{cases}
​ f(x) = \sum_{m=1}^M \alpha_m G_m(x) & (\text{加权求和}) \
​ G(x) = \operatorname{sign}(f(x)) = \operatorname{sign} \left( \sum_{m=1}^M \alpha_m G_m(x) \right) & (\text{若大于 } 0, \text{取 } +1)
\end{cases}
$

先引入一个定理：

随着 M 增加，AdaBoost 最终分类器 G(x) 在训练集上的错误率会越来越小。

但注意，在训练集上错误率过小 也可能不一定是好事 \Rightarrow 可能出现过拟合 \Rightarrow 但是 AdaBoost 不是很容易出现过拟合。

证明此定理

错误率: E = \frac{1}{N} \sum_{i=1}^{N} I(G(x_i) \neq y_i) 其中 $I(G(x_i) \neq y_i) =
\begin{cases}
1, & \text{若} G(x_i) \neq y_i \
0, & \text{若} G(x_i) = y_i
\end{cases}$

\Rightarrow E = \frac{1}{N} \sum_{i=1}^{N} I(G(x_i) \neq y_i) \leq \frac{1}{N} \sum_{i=1}^{N} \exp(-y_i f(x_i)) 其中 f(x) = \sum_{m=1}^{M} \alpha_m G_m(x)

并且 G(x_i) 和 y_i 都只能取

上式成立：

1° 若 G(x_i) = y_i \Rightarrow 则 I(G(x_i) \neq y_i) = 0 \Rightarrow 则 y_i f(x_i) > 0 也就是同号 \Rightarrow \exp(-y_i f(x_i)) \Rightarrow e^{?< 0} \Rightarrow exp一定是大于0的

2° 若 G(x_i) \neq y_i \Rightarrow I(G(x_i) \neq y_i) = 1 \Rightarrow 则 y_i f(x_i) < 0 也就是不同号 \Rightarrow \exp(-y_i f(x_i)) \Rightarrow e^{?> 0} \Rightarrow exp一定是大于1的

所以原式 \Rightarrow E = \prod_{m=1}^{M} Z_m 其中 Z_m = \sum_{i=1}^{N} W_{mi} \exp(-\alpha_m y_i G_m(x_i))

\Rightarrow 证明上面这一步：

接下来我们要证明的是 Z_m = 2\sqrt{e_m (1 - e_m)}

其中 e_m 是 \Rightarrow e_m = p(G_m(x_i) \neq y_i) = \sum_{i=1}^{N} W_{mi} I(G_m(x_i) \neq y_i) （ e_m < \frac{1}{2}）

Z_m = \sum_{i=1}^{N} W_{mi} \exp(-\alpha_m y_i G_m(x_i))

​ = \sum_{\substack{i=1 \\ y_i = G_m(x_i)}}^{N} W_{mi} e^{-\alpha_m} + \sum_{\substack{i=1 \\ y_i \neq G_m(x_i)}}^{N} W_{mi} e^{\alpha_m} = (1 - e_m) e^{-\alpha_m} + e_m \cdot e^{\alpha_m}

再将 \alpha_m = \frac{1}{2} \log \left( \frac{1 - e_m}{e_m} \right) 代入得 \Rightarrow Z_m \leq 2 \sqrt{e_m (1 - e_m)}

\Rightarrow 如果 \ e_m < \frac{1}{2} \Rightarrow 则有 Z_m < 1

这部分是应用，被我省略了，有课件，后续可以补充上

目标检测 (利用卷积神经网络)

定位于识别 ➔ 并行两任务

多目标检测 ➔ RCNN ➔ ppt

多目标和单目标的差别在于目标的不确定性，但是可以用分割算法分割出目标的候选项 \Rightarrow 叫做 Region Proposal：目标候选区域

\Rightarrow 每个候选项都做一个识别 \Rightarrow 利用 Selective Search（传统方式）\Rightarrow 然后放到 CNN 中 \Rightarrow 再用SVM区分

语义分割 \Rightarrow 标注每个像素点

所有关于人脸识别的应用部分均未学习

概率分类法

在深度学习之前就有，并会长久的存在于机器学习的领域中 \Rightarrow 用概率的思维和方法来做机器学习

基本问题：

求 P(W_1 | X) 和 P(W_2 | X) \Rightarrow 即 X 属于某一类的概率。

首先必定有 P(W_1 | X) + P(W_2 | X) = 1 \Rightarrow 于是分类问题变成 $\Rightarrow \begin{cases}
\text{若 } P(W_1 | X) > P(W_2 | X) \text{ 则 } X \in W_1 \
\text{若 } P(W_1 | X) < P(W_2 | X) \text{ 则 } X \in W_2
\end{cases}$

根据贝叶斯公式:

接下来比较它们的大小。因为它们的分母是一样的，所以只需要比较分子的大小。

\Rightarrow 判别标准可以修改成： \begin{cases} \text{若 } P(W_1 | X) P(W_1) > P(X | W_2) P(W_2) ，则 X \in W_1 \\ \text{若 } P(W_1 | X) P(W_1) < P(X | W_2) P(W_2) ，则 X \in W_2 \end{cases}

​ 其中， P(W_1) 和 P(W_2) 叫做 W 的先验概率

P(X | W_1)、P(X | W_2) 叫做 X 在 W 上的条件概率
P(W_1 | X)、P(W_2 | X) 叫做 X 在 W 上的后验概率

之前做过的卷积神经网络和人工神经网络在做分类问题时，最后经过 softmax 后，基本上都在模拟 P(W_1 | X)、P(W_2 | X)

但在模拟它们时，一些存在的问题需要被理解 \Rightarrow 我们必须要非常关注先验概率

换句话说，即使我们用神经网络直接模拟 P(W_1 | X)、P(W_2 | X) ，但是对先验概率也必须重视

比如说，用 Network 做一个两类问题划分，那么基本上要保证 W_1, W_2 出现的频率在训练集中和实际出现的情况下，其比率大致一致。

即训练和测试的先验概率大致相同（比较难保证）

现在假设 P(W_1)、P(W_2) 已知 (比如可以通过统计获得) 。若不知道先验概率，则假设所有先验概率一样。

在此情况下，分类标准将会变成

在上述所有假设都结束的情况下 ，接下来就来做：如何估计 P(X | W) \Rightarrow 给定一组 \{x_i\}_{i=1 \sim N} \in W，如何求 P(x | W)

这个问题叫做：概率密度估计问题 \Rightarrow 从简单到复杂来研究这个问题

(1) 朴素贝叶斯分类（Naive Bayesian Classifier） \Rightarrow 最基本的统计

首先，它有两个限制条件如下：

应用：垃圾邮件分类

怎么做这个训练呢？ \Rightarrow 如果要用概率分类法，则需要学习 P(d | C_1) 和 P(d | C_2)

概率分类法

P(d | C) = P(f_w, w_2, ..., w_n | C) 其中 C 属于 C_1 或者 C_2

并且其中 w 是离散的 \Rightarrow 因此，限定条件 1 是符合的，但是限定条件 2 是不符合的 \Rightarrow 但是我们先假设条件 2 成立

P(d | C) = \prod_{i=1}^n P(w_i | C) （独立性假设） \Rightarrow P(W | C_j)_{j=1,2} = \frac{\text{Count}(W, C_j)}{\sum_{W \in V} \text{Count}(W, C_j)} \Rightarrow 这是什么意思呢？

\Rightarrow 比如说 P(I | C_j)_{j=1,2} = \frac{\text{I 出现的次数}}{\text{总次数}} \Rightarrow 并且:

\Rightarrow 如果 P(C_1) P(d | C_1) > P(C_2) P(d | C_2)

但是如果有一个词在训练样本中一次都没有出现，但在测试样本中出现了

\Rightarrow 就会导致 P(w_i | C) = 0 \Rightarrow 不可接受 \Rightarrow 改进一下原公式 \Rightarrow P(W | C_j)_{j=1,2} = \frac{\text{Count}(W, C_j) + 1}{\sum_{W \in V} \text{Count}(W, C_j) + |V|}

\Rightarrow 这样可以使没有出现的单词概率是 \frac{1}{|V|}

(2) 高斯概率密度估计

假设 \{x_i\}_{i=1 \sim N} \in C \Rightarrow 一维情况下： \begin{cases} P(X | C) = \frac{1}{\sqrt{2 \pi} \sigma} e^{-\frac{(x - \mu)^2}{2 \sigma^2}}\\\mu = \frac{1}{N} \sum_{i=1}^{N} x_i \\ \sigma^2 = \frac{1}{N-1} \sum_{i=1}^{N} (x_i - \mu)^2 \end{cases}

复习：略微做一些推导 \Rightarrow 当x 是多维的情况 \Rightarrow 假设概率密度是一个多维高斯分布

P(X | C) = \frac{1}{\sqrt{(2 \pi)^d |\Sigma|}} \exp \left( -\frac{1}{2} (x - \mu)^T \Sigma^{-1} (x - \mu) \right)

待求参数：\Sigma 和 \mu \Rightarrow 其中 \Sigma 是 d \times d 矩阵，\mu 是 d \times 1 向量

即已知 \{x_i\}_{i=1\sim N} \Rightarrow 求 \Sigma 和 \mu

构造目标函数（极大似然法，Maximum Likelihood） \Rightarrow E(\mu, \Sigma) = \sum_{i=1}^{N} \ln P(x_i | C)

假设：

E(\mu, \Sigma) = -\frac{Nd}{2} \ln (2 \pi) - \frac{N}{2} \ln |\Sigma| - \frac{1}{2} \sum_{i=1}^{N} (x_i - \mu)^T \Sigma^{-1} (x_i - \mu)

注意: 高斯函数是凸函数，上面求极值是全局极值，所以可以直接拿下 \mu 和 \Sigma。

但在很多情况下，构造出目标函数极值，我们算不出来怎么办呢？ \Rightarrow

下面要讲的是，就是构造完全局函数后但算不出来的例子 \Rightarrow 混合高斯模型（Gaussian Mixture Model）

步骤:

① 假设 X 的概率分布的具体形式为

总共有k 个高斯，每个高斯都有一个均值 \mu_k 和一个协方差矩阵 \Sigma_k

\sum_{k=1}^{K} \pi_k = 1 是什么意思呢？\Rightarrow 在以前 X 为单个高斯的情况下，只有一个分布，但是如果是有多个高斯，不同的高斯分布占据能量不同，但是总共占100% \Rightarrow

$\Rightarrow$   $\text{两个加起来 } = 1$

② 用极大似然去估计概率密度，构造优化目标函数

最小化： E

E \left( \{\pi_k, \mu_k, \Sigma_k\}_{k=1 \sim K} \right) = -\sum_{i=1}^{N} \ln P(x_i | C) = -\sum_{i=1}^{N} \ln \left( \sum_{k=1}^{K} \pi_k \frac{1}{\sqrt{(2\pi)^d |\Sigma_k|}} \exp \left( -\frac{1}{2} (x_i - \mu_k)^T \Sigma_k^{-1} (x_i - \mu_k) \right) \right)

由于上述的问题是非凸问题，无法求全局极值，只可求局部极值

$\begin{cases}
\frac{\partial E}{\partial \pi_k} = 0 \
\frac{\partial E}{\partial w_k} = 0 \
\frac{\partial E}{\partial \Sigma_k} = 0
\end{cases} \Rightarrow 超复杂 \Rightarrow 但是怎么做呢？\Rightarrow$ 可以使用 如下方法

EM算法

随机化 \left\{ \pi_k, \mu_k, \Sigma_k \right\}_{k=1 \sim K} \Rightarrow

高斯混合模型的 EM 算法 (Expectation - Maximization)

① 随机化 \left\{ \pi_k, \mu_k, \Sigma_k \right\}_{k=1 \sim K}

② E-step：
\gamma_{nk} = \frac{\pi_k N(X_n | \mu_k, \Sigma_k)}{\sum_{k=1}^{K} \pi_k N(X_n | \mu_k, \Sigma_k)} \quad (n=1 \sim N) \quad (k=1 \sim K)

③ 更新步骤：M-step：
N_k = \sum_{n=1}^{N} \gamma_{nk} （所有 N 个样本中有多少属于第 k 个高斯） \Rightarrow \gamma_{nk}：第 n 个样本属于第 k 个高斯的概率
\sum_{k=1}^{K} N_k = N

​

④ 回到步骤②，再去估计新的 \gamma_{nk}，再一次，不断循环，直至收敛。关于收敛性的证明略

上面是一个高斯混合模型 EM 例子

另一个 EM 算法例子：K-均值聚类（K-means clustering）

问题是：

知道 \mu_1, \mu_2, \dots, \mu_K，即K个类别的中心点，怎么把各自样本归类呢？ \Rightarrow 样本隔谁近就是哪一类

但现在问题是我们只有数据点，没有数据点的中心

K-均值算法步骤：

① 随机化 \mu_1, \mu_2, \dots, \mu_K

② E-step
z_i = \arg \min_k \|x_i - \mu_k\| \Rightarrow 离谁近就属于谁 (i=1 \sim N)

③ M-step
N_k = \sum_{i=1}^{N} I(z_i = k) \Rightarrow 表示 N 个样本中有多少属于第 k 类
\mu_k = \frac{1}{N_k} \sum_{\substack{i=1 \\ z_i = k}}^{N} x_i \Rightarrow 表示第 k 类样本的均值

④ 回到步骤 ②，不断循环，直至收敛 \Rightarrow 证明其收敛性

构造目标函数：E(\{\mu_k\}) = \sum_{k=1}^{K} \sum_{\substack{i=1 \\ z_i = k}}^{N} \|x_i - \mu_k\|^2

\Rightarrow 先想一个问题：去求一个 C，使 \sum_{i=1}^{N} \|x_i - C\|^2 最小 \Rightarrow 这个 C 该取哪个？ \Rightarrow C = \frac{1}{N} \sum_{i=1}^{N} x_i

\Rightarrow 那么目标函数中如何调整 \mu_k 以使 E 最小呢？ \Rightarrow 让 \mu_k 等于其均值即可

\Rightarrow 第②③步都使 E 变小，而 E 有下界 0 \Rightarrow 因此一定收敛

下面讲 EM 算法的标准形式，以及用这种形式同时证明其收敛性

设 Q_i(z_i) 为 z_i 的概率分布，则 \sum_{z_i} Q_i(z_i) = 1

E(\theta) = \sum_{i=1}^{N} \log \left[ \sum_{z_i} Q_i(z_i) \frac{p(x_i, z_i | \theta)}{Q_i(z_i)} \right] 由于 p \leq 1 \Rightarrow p \cdot \log p \leq 0 \Rightarrow E(\theta) 的角上界

根据 Jensen's Inequality

\Rightarrow E(\theta) \geq \sum_{i=1}^{N} \sum_{z_i} Q_i(z_i) \log \frac{p(x_i, z_i | \theta)}{Q_i(z_i)} \Rightarrow 当且仅当 Q_i(z_i) 与 p(x_i, z_i | \theta) 成比例时，等号成立。

当 Q_i(z_i) = \frac{p(x_i, z_i | \theta)}{\sum_{z_i} p(x_i, z_i | \theta)} 时，E(\theta) 取最大值 \Rightarrow \sum_{i=1}^{N} \sum_{z_i} Q_i(z_i) \log \frac{p(x_i, z_i | \theta)}{Q_i(z_i)}

基于以上推导，可以推出 EM 算法的一般形式：

① 随机选取 \theta_0

② E-step:
Q_i(z_i) = \frac{p(x_i, z_i | \theta_k)}{\sum_{z_i} p(x_i, z_i | \theta_k)}

③ 固定 Q_i(z_i)，找 \theta^{(new)}:
\theta_{k+1}^{(new)} = \arg \max_{\theta} \sum_{i=1}^{N} \sum_{z_i} Q_i(z_i) \log \frac{p(x_i, z_i | \theta)}{Q_i(z_i)}

④ 回到 ②，循环至收敛

证明：

设 M(\theta) = \sum_{i=1}^{N} \sum_{z_i} Q_i(z_i) \log \frac{p(x_i, z_i | \theta)}{Q_i(z_i)}

则：
做完②E-step后，E(\theta) = M(\theta)（E 为达到最大值）

做完③后，M(\theta_{k+1}) \geq M(\theta_k)

再接着第②步，E(\theta_{k+1}) = M(\theta_{k+1}) \geq M(\theta_k) = E(\theta_k)

且 E(\theta) \leq 0（上界 0），所以一定收敛。

K-均值算法如何和上述对应？

K-均值算法

输入 \{x_i\}_{i=1 \sim N} 样本，待求 \theta = \{\mu_1, \mu_2, \dots, \mu_K\}

定义 \{z_i\}_{i=1 \sim N}，z_i = \{1, 2, 3, \dots, K\} 代表 K 个类中的哪一个

定义 $p(x, z | \theta) =
\begin{cases}
\frac{1}{ (\sqrt{2\pi})^d} \exp \left( -\frac{|x - \mu_z|^2}{2} \right) & \text{当 } z = \arg \min_j |x - \mu_j| \Rightarrow 隔得近\
0 & \text{其他}
\end{cases}$

根据上述算法，一步步推导 K-均值算法

① 随机选取 \theta = \{\mu_1, \mu_2, \dots, \mu_K\}

② E-step:
$Q_i(z_i) = \frac{p(x_i, z_i | \theta_k)}{\sum_{z_i} p(x_i, z_i | \theta_k)} =
\begin{cases}
1 & \text{当 } z_i = \arg \min_j |x_i - \mu_j| \
0 & \text{其他}
\end{cases}$

③ 固定 Q_i(z_i)，找 \theta^{(new)}：
\theta_{k+1}^{(new)} = \arg \max_{\theta} \sum_{i=1}^{N} \sum_{z_i} Q_i(z_i) \log \frac{p(x_i, z_i | \theta_k)}{Q_i(z_i)}

​ \mu_j^{(new)} = \arg \max_{\mu_j} \sum_{\substack{i=1 \\ z_i = j}}^{N} \log p(x_i, z_i=j | \theta_k)

​ 注意：Q_i(z_i) = 1 ， \sum_{zi} 这个求和符号被拿到了 z_i = j 这里。

​ 假设: E(\mu_j) = \sum_{\substack{i=1 \\ z_i = j}}^{N} \ \ log( p(x_i, j| \theta_k)) = -\sum_{\substack{i=1 \\ z_i = j}}^{N} \frac{\|x_i - \mu_j\|^2}{2} 这是个常数

​ 那么: \frac{\partial E}{\partial \mu_j} = - \sum_{\substack{i=1 \\ z_i = j}}^{N} (x_i - \mu_j) = 0 \Rightarrow \mu_j = \frac{\sum\limits_{\substack{i=1 \\ z_i = j}}^{N} x_i}{\sum\limits_{\substack{i=1 \\ z_i = j}}^{N} 1} 所有属于第 j 类的 x 求均值

④ 回到 ② 循环至收敛

关于高斯混合模型的 EM 算法推导，自己研究。

注意几点：

① EM 算法是求局部极值，不要调参数，迭代即可。

② 所有求局部极值算法的缺点 \Rightarrow 无法保证一定比其他方法更优 \Rightarrow 初始值选择不一样，最终结果完全不同。没有办法证明哪个比哪个更好。

语音识别： 连续行为的识别

比如说对于声音文件，我们不知道每个字所占的时间

\Rightarrow 两方法解决：

不仅仅是声音文件，也可能是一段连续动作的识别. \Rightarrow 不知道某一状态下行为持续多长. \Rightarrow 必须引入时间参数

可以用前面的 K 均值方法来聚类，但是效率低，不实用

输入 O_1, O_2, \dots, O_T \Rightarrow 特征向量 (MFCC)

每个输入对应于一个隐含状态: q_1, q_2, \dots, q_T

隐含马尔可夫模型 - HMM \Rightarrow 一个 HMM 由三部分组成 \lambda = \{A, B, \pi\} $
\begin{cases}
A \text{ 状态转移矩阵} \
B \text{ 观测概率} \
\pi \text{ 状态先验概率}
\end{cases}
$

假设有 P 个状态 \{S_0, S_1, \dots, S_{P-1}\}

① N(S_i) 代表一开始在 S_i 状态的概率 \Rightarrow 先验概率
② A = \{a_{ij}\} 表示状态转移概率

​ a_{ij} = P(q_{t+1} = S_j | q_t = S_i) \Rightarrow 马尔可夫链假设 \Rightarrow 这里是单步的马尔可夫链

​ $
\begin{cases}
​ \text{转移矩阵 } a_{ij} \text{ 和 } t \text{ 无关} \
​ \text{后一时刻状态只和前一时刻状态有关}
\end{cases}
$

​ 这里也可以升级成 多步的马尔可夫链 \Rightarrow a = P(q_{t+1} = S_j | q_{1 \sim t} = S_1, S_2, \dots, S_t)

​ 这样就和之前时刻都有关系

​ 为了简化，我们这里用单步马尔可夫链

③ B = \{b_j(o)\}

​ 若输入向量 O 是属于 S_j 的，则对应的概率分布用 b_j(o) 来表示

​ 传统方法是采用高斯混合模型 b_j(o)

​ 即 我们知道所有的 O，但我们不知道每个 O 所对应的状态 q。状态 q 是隐含在 O 中的，是要被求出来的。

三个问题

① 识别问题

给出一串序列 O = O_1, O_2, \dots, O_T \Rightarrow 同时给出一个 HMM 模型 \lambda = \{A, B, \pi\} \Rightarrow 求 P(O | \lambda)

对每个模型，都要测定P(O | \lambda) \Rightarrow 在此模型下，产生 O 的概率 \Rightarrow 哪个模型得到的概率大 就认为是哪个

O_1 时状态 q_1 \Rightarrow 在 q_1 时状态概率是 \pi(S_i)

P(O|\lambda) = \sum_{q_1=S_0}^{S_{P-1}} \pi(q_1) \cdot b_{q_1}(O_1) \cdot \sum_{q_2=S_0}^{S_{P-1}} a_{q_1 q_2} \, b_{q_2}(O_2) \cdot \sum_{q_3=S_0}^{S_{P-1}} a_{q_2 q_3} \, b_{q_3}(O_3) \cdots \sum_{q_T=S_0}^{S_{P-1}} a_{q_{T-1} q_T} \cdot b_{q_T}(O_T)

其中:

这些求和符号对我们的计算非常不友好

比如 P = 5（5个状态），T = 50 \Rightarrow P(O|\lambda) 将有 5^{50} 项 \Rightarrow 我们可以用简便的方法来解

问题一 - 简便算法：

① 定义 \alpha_t(i) = P(O_1, O_2, O_3, \dots, O_t, q_t = S_i | \lambda)

② \alpha_1(i) = P(O_1, q_t = S_i | \lambda)

​ \alpha_1(i) = \pi(S_i) \, P(O_1 | q_1 = S_i, \lambda) = \pi(S_i) \, b_i(O_1)

③ \alpha_{t+1}(j) = \left[\sum_{i=1}^{P} \alpha_t(i) \, a_{ij}\right] \, b_j(O_{t+1})

​ \alpha_{t+1}(j) = P(O_1, O_2, \dots, O_t, O_{t+1}, q_{t+1} = S_j | \lambda) 遍历所有的 O_t

​ = \sum_{i=1}^{P} P(O_1, O_2, \dots, O_t, q_t = S_i | \lambda) \, a_{ij} \cdot b_j(O_{t+1}) = \left[\sum_{i=1}^{P} \alpha_t(i) \, a_{ij}\right] \, b_j(O_{t+1}) （递归公式）

④ P(O|\lambda) = \sum_{i=1}^{P} \alpha_T(i) = \sum_{i=1}^{P} P(O_1, O_2, \dots, O_T, q_T = S_i | \lambda) = \sum_{i=1}^{P} P(O_1, O_2, \dots, O_T | \lambda) = P(O|\lambda)

算完了 P(O|\lambda) 后，怎么用呢？

例如 0 \sim 9 为数字识别问题

(2) 第二个问题：

给定一个隐含马尔可夫模型 \lambda = \{ \pi, A, B \}

给定序列 O = O_1, O_2, \dots, O_T（观测向量）

要求一串状态序列 Q = q_1, q_2, \dots, q_T

使 E(Q) = \pi(S_{q_1}) b_{q_1}(O_1) a_{q_1 q_2} b_{q_2}(O_2) \dots a_{q_{T-1} q_T} b_{q_T}(O_T)

要求每一个状态对应的状态，并使求出现的状态发生概率最大

O_1 是观测的，对应的状态 q_1 是隐含的，但是其概率是可求的 \Rightarrow 其先验概率就是 \pi(S_{q_1}) \Rightarrow q_1 状态下出现 O_1 的概率是 b_{q_1}(O_1) \Rightarrow q_1 状态转移到 q_2 的概率是 a_{q_1 q_2} \Rightarrow 不断延续 \Rightarrow 我们要让这个概率最大 \Rightarrow 维特比算法

维特比算法 （Viterbi Algo）

图形表达理解部分由于图片太多将其省略

数学表达

① 定义：

​ \delta_t(i) = \max_{q_1 q_2 \dots q_{t-1}} P(q_1 q_2 \dots q_{t-1}, q_t = S_i, O_1 O_2 \dots O_t)

​ \delta_t(i) 就是每个点的最大值

② 建立递推公式：

③ E(Q) = \max_i \left[ \delta_T(i) \right]

​ q_T = \arg\max \left[ \delta_T(i) \right], \quad q_t = \psi_{t+1}(q_{t+1})

​ 综上所述 问题二 是给 O 打标签的操作

③ 问题三：训练问题

给定 O = O_1, O_2, \dots, O_T （这里是大量的 O，不是一个） \Rightarrow 选择\lambda = \{ \pi, A, B \} 使 P(O|\lambda) 最大

​ 定义：\alpha_t(i) = P(O_1, O_2, O_3, \dots, O_t, q_t = S_i | \lambda)

​ 定义：\beta_t(i) = P(O_{t+1}, O_{t+2}, \dots, O_T | q_t = S_i, \lambda)

​ \beta_T(i) = 1 \quad (i = 1 \sim P)

​ \beta_t(i) = \sum_{j=1}^P a_{ij} \, \beta_{t+1}(j) \, b_j(O_{t+1}) \quad \text{其中 } t = (T-1) \sim 1

​ 接下来要计算几个值：

​ 1° 随机初始化 \lambda = \{\pi, A, B\}

​ 2° 计算 \xi_t(i, j) = P(q_t = S_i, q_{t+1} = S_j | O, \lambda)

​ \xi_t(i, j) = \frac{\alpha_t(i) \, a_{ij} \, b_j(O_{t+1}) \, \beta_{t+1}(j)}{\sum_{i=1}^P \sum_{j=1}^P \alpha_t(i) \, a_{ij} \, b_j(O_{t+1}) \, \beta_{t+1}(j)}

​ \gamma_t(i) = P(q_t = S_i) = \sum_{j=1}^P \xi_t(i, j)

​ 3° 估计：

​ \pi(S_i)^{\text{new}} = \gamma_1(i) = P(q_1 = S_i)

    	        $a_{ij}^{\text{new}} = \frac{\sum_{t=1}^{T-1} \xi_t(i, j)}{\sum_{t=1}^{T-1} \gamma_t(i)}$      $a_{ij}^{\text{new}}$代表 从 $S_i \Rightarrow S_j$ 状态转移的概率

更新 \pi^{\text{new}}, A^{\text{new}} 后，用第二个问题的求解方法：

即获得观测序列和状态序列

下面是更新 b^{\text{new}} 这里剩下内容没了! 以及后续应用也没写

循环神经网络 (Recurrent Neural Network, RNN)

它和 RCN 不同 \Rightarrow RCN 做图像分割

\Rightarrow RNN 处理时间序列的信号，和隐含马尔可夫过程类似 \Rightarrow 用传统的方式来处理时间序列信号

循环神经网络：t 时刻的状态，与 t-1 时刻的状态和 t 时刻的输入有关

\Rightarrow h_t = f_W(h_{t-1}, x_t) 其中，h_t 为 t 时刻的状态，x_t 为 t 时刻的输入。

请注意：f_W 与 t 无关。

思考题：请证明若 f_W 为三层神经网络，且状态数有限，则 RNN 可以模拟 GMM-HMM。

h_t = f_W(h_{t-1}, x_t)

f_W 的形式(一层神经网络) \Rightarrow

换句话说 h_t = \text{非线性函数} \left( \begin{bmatrix} W_{hh}, W_{xh} \end{bmatrix} \begin{bmatrix} h_{t-1} \\ x_t \end{bmatrix} \right) = \tanh \left( W \begin{bmatrix} h_{t-1} \\ x_t \end{bmatrix} \right) 其中 \tanh = \frac{e^x - e^{-x}}{e^x + e^{-x}}

有多种形式

每种形式都有对应的结构图，但是我没展示，后续精细化的时候再补充吧。

权值共享 \Rightarrow 怎么做梯度反向传播？ \Rightarrow 如果碰到同样 W 把同样的东西加到一起就行。

LSTM：RNN 中一种 \Rightarrow 主要解决 RNN 训练问题，增加了 RNN 中单元的复杂度，使模型更复杂，增加系统表现力。

VANILLA RNN 的训练问题：

训练中 h_0 获得的梯度，将是矩阵 W 的对应于 h_0 的部分被乘了很多次，将会导致梯度爆涨或梯度消失。 \Rightarrow 传回h_0 的梯度过大或过小

Vanilla RNN： h_t = \tanh \left( W \begin{bmatrix} h_{t-1} \\ x_t \end{bmatrix} \right)

LSTM： \begin{cases}\begin{pmatrix} i \\ f \\ o \\ g \end{pmatrix} = \begin{pmatrix} \sigma \\ \sigma \\ \sigma \\ \tanh \end{pmatrix} W \begin{bmatrix} h_{t-1} \\ x_t \end{bmatrix} \\ c_t = f \odot c_{t-1} + i \odot g \\ h_t = o \odot \tanh(c_t)\end{cases}

\Rightarrow RNN 的基本 f(W) 太简单，LSTM 给它复杂化了。