Sanshuiii

维度规约

维度规约，又叫降维，用于提取数据特征，将高维数据转换为低维数据。一方面方便对数据进行可视化和分析；另一方面对数据进行预处理可以加速后续训练，并且减少噪声，使得所训练模型更加简单。如果说密度估计和降维是在数据集样本轴上进行压缩，那么降维就是在数据集特征轴上进行压缩。

降维和聚类可以同时使用，且应该先降维后聚类，因为当数据维度 很大时，所有点之间的近乎是等距的，即

$$\frac{\max||X_i-X_j||}{\min||X_i-X_j||}=1+\mathcal{O}\left(\sqrt{\frac{\log n}{d}}\right)$$

聚类

聚类同样是密度估计的一种。不同于前文所述的密度估计算法，聚类将数据分进多个分布中，每个分布即聚类所得的类。

如图所示，上图是著名的 Old Faithful 数据集。真实的数据分布往往难以用一个分布（左）去刻画，因而使用 GMM 等将数据用多个分布（右）进行刻画的算法往往在实际运用中更有意义。

本文中将介绍两种聚类算法：K-means 和 GMM，并给出 ELBO 与 EM 算法的推导，用于求解含隐变量的参数估计问题。

密度估计

密度估计是一类重要的无监督学习方法，通过从分布 中观测得到的独立同分布的样本集合 ，我们估计 的概率分布 。

密度估计本质上是仍然是参数估计问题，可以使用MLE解决，即

$$\hat{p} = \arg\max_p \mathcal{L}(X_1,X_2,\cdots,X_n;p) = \arg\max_p \prod_{i=1}^np(X_i)$$

然而上述优化问题要在无穷大的解空间

$$\left\{p:p\geq 0 , \int p = 1\right\}$$

上求解，这几乎不可解。

因此有三种解决方案来规避上述问题：

• 参数化密度估计
• 无参密度估计
• 核方法

概率分布变换

定理

给定关于随机变量 的PDF(概率密度函数) ，如果随机变量之间满足关系 , 严格单调且可导，则有

$$f_Y(y)=\frac{f_X(x)}{|g'(x)|}$$

，其中 。

推导

矩阵乘法的几何意义

假定有一个行向量组成的矩阵

$$P=\begin{pmatrix}p_1\\p_2\\\vdots\\p_n\end{pmatrix}$$

和列向量组成的矩阵

$$A=\begin{pmatrix}a_1,a_2,\cdots,a_m\end{pmatrix}$$

, 则有

$$PA=\begin{bmatrix} {p_1a_1}&{p_1a_2}&{\cdots}&{p_1a_m}\\ {p_2a_1}&{p_2a_2}&{\cdots}&{p_2a_m}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {p_na_1}&{p_na_2}&{\cdots}&{p_na_m}\\ \end{bmatrix}$$

考虑向量点积的几何意义 , 当 时， 即为 在 方向的上投影。当 由一组正交基组成时， 可以将每一个列向量 投影到由原来的特征线性组合而成的新的坐标系中，其中每个行向量 都可以被视为一个组合出的新特征，而每个列向量 则是一个样本。

Review of PG

我们目前有一个 on-policy 的算法，即在 下采样若干 τ , 并计算

$$\nabla \overline{R}_\theta = E_{\tau\sim p_\theta(\tau)}[R(\tau)\nabla\log p_\theta(\tau)] \\$$

其主要问题在于，采样的属于一旦计算完梯度，对 θ 进行一轮优化， 的分布就发生了变化，之前采集的数据就不能再用于训练直到模型收敛，这对计算产生了极大的开销。

如果我们能够多次复用这个数据来进行训练，那么训练成本将大大降低，因此我们可以引入重要性采样 Important Sampling 技术。

Review of Gradient Descent

我们已经得到了 Policy gradient 一个最基本的形式，我们定义了目标函数

$$\theta^* = \arg\max_\theta\sum_\tau R(\tau)P(\tau|\theta) \\$$

并得到了优化目标的梯度

$$\nabla\overline{R}_\theta \approx \sum_{n=1}^N\sum_{t=1}^{T_n} R(\tau^n)\nabla\log p(a_t^n|s_t^n,\theta) \\$$

其中 R(τ) 有两项优化：

$$R(\tau) = \sum_{t'=t}^{T_n}\gamma^{t'-t}r_{t'}^n \\$$ $$R'(\tau) = R(\tau) - E[R(\tau)]\\$$

我们可以通过梯度下降法来最大化目标函数

$$\theta' = \theta - \eta \nabla \overline{R}_\theta \\$$

Note: 因为我们的任务是最大化，所以这里的 η 需要是一个负值

本文作为李宏毅老师2020年春季强化学习课程的笔记记录，课件，本文默认读者有一定的机器学习和深度学习的背景知识。

概述

简单的讲，强化学习主要的工作就是训练一个 agent，从环境 （environment） 中获取信息 （observation），并且做出决策 （action） 来影响环境。最终的目标是得到一个决策序列，使得整个过程得到的收益 （reward） 最大。

前言

DQN 作为 value-based 的强化学习方法，擅长处理离散情境下的强化学习问题。其本质是 deep learning 版本的 Q-learning，所以其基本模型和 Q-learning 类似，基于TD时间差分设置目标函数，并 的贪心策略进行探索和学习。在此基础上利用深度学习的优势，将难以维护的Q值表用一个神经网络来维护，形成了 Deep Q-Learning（NIPS 2013）。事实上，我们可以认为 deep learning 在其中的主要作用只是替换了 Q 值表，而算法的核心思想仍然可以认为是一种启发式搜索。

在此基础上，Nature DQN (NIPS 2015) 通过解耦目标Q值动作的选择和目标Q值的计算，提高了算法效率。此后又在 Nature DQN 的基础上产生了三种独立的优化策略: Deep Reinforcement Learning with Double Q-learning (AAAI 2016) 在计算 TD 值中的目标 Q值时，先从当前网络中获取动作，再从目标网络中计算；Dueling Network Architectures for Deep Reinforcement Learning (ICML 2016) 将 Q 值拆分成状态值 V 和动作的优势值 A；Prioritized Experience Replay (ICLR 2016) 认为 TD 值越大的样本对训练越有利，所以在经验池中，有更大概率选取那些 TD 值更大的样本进行训练；以上三种方法都优化了原始 DQN ，并且这几种方法可以被组合起来使用，后续的一些工作主要就做了融合的尝试，但是因为这种融合怪工作本身没有其他的创新点，所以这里暂且忽略不表。

Markov Chain

Markov Decision Process

States :
Actions :
Probability distribution of transitions :
Reward :

Value function: Bellman Equation

RL learns a policy . Reward function reflects only the real time REWARD. For a long term REWARD, we introduce Value Function .