稀疏自编码器

自编码器

传统反向传播神经网络缺点：

• 梯度越来越稀疏（梯度弥散）：从顶层越往下，误差校正信号越来越小；
• 容易收敛到局部最小值，尤其是从远离最优区域开始的时候（将参数初始化为随机值会导致这种情况发生）；
• 只能进行有监督训练，但大部分的数据是没有标签的，而人类的大脑可以从没有标签的数据中学习。

1986 年，Rumelhart 提出了自动编码器的概念，并将其用于高维复杂数据的处理，促进了神经网络的发展。自编码神经网络是一种无监督（自监督）学习算法，它使用了反向传播算法，并让目标值等于输入值，即自编码神经网络尝试学习一个 $h_{W, b}(x) \approx x$ 的函数。

自编码器分类：

• 浅层自编码（Autoencoder）
• 稀疏自编码（Sparse Autoencoder）
• 栈式自编码（Stacked Autoencoder）
• 去噪自编码（Denoising Autoencoder）
• 变分自编码（Variational Autoencoder）

自编码器的共同点：学习一个与输入相同的输出，并尽可能的让其具有较强的泛化能力。

自编码器的构成：

降维和特征选择

KNN

KNN 是一种常用的监督学习方法。其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的 $k$ 个训练样本，基于这 $k$ 个邻居的信息进行预测。

通常，在分类任务中可以使用“投票法”，即选择这 $k$ 个样本中出现次数最多的类别标记为预测结果（朴素方法直接寻找出现次数最多，值域过大可以考虑离散化，可以考虑摩尔投票法）；在回归任务中可使用“平均法”，即将这 $k$ 个样本的实值输出标记的平均值作为预测结果；还可以基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。

KNN 算法的学习有一个与其他算法明显不同之处：它没有显式的学习过程，这被称为懒惰学习。此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。

与之相对的是急切学习，此类学习技术在训练阶段就对样本进行学习处理。

KNN 分类器中的超参数 $k$ 是一个重要参数，当 $k$ 取不同值时，分类结果会有显著不同。

另一方面，若采用不同的距离计算方式，则找出的“近邻”可能有显著差别，从而也会导致分类结果有显著不同。

下面对最近邻分类器（1NN，即 $k=1$）在二分类问题上的性能做一个简单的讨论。

聚类分析

介绍

在无监督学习中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。此类学习任务中研究最多、应用最广的是“聚类”（clustering）。

常见的无监督学习任务还有密度估计、异常检测等。

聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称作一个“簇”。

形式化地，假定样本集 $D = \left\{\boldsymbol{x}_1,\boldsymbol{x}_2, \dots,\boldsymbol{x}_m\right\}$ 包含 $m$ 个无标记样本，每个样本 $\boldsymbol{x}_i = \left(x_{i1};x_{i2};\dots;x_{in}\right)$ 是一个 $n$ 维特征向量，则聚类算法将样本集 $D$ 划分为若干个不相交的簇 $\left\{C_l \mid l = 1, 2, \dots, k\right\}$，其中 $C_{l'} \bigcap_{l' \neq l} C_l = \varnothing$ 且 $D = \bigcup_{l=1}^{k}{C_l}$。

令 $\lambda_j \in \left\{1, 2,\dots, k\right\}$ 表示样本 $\mathbf{x}_j$ 的簇标记，即 $\mathbf{x}_j \in \lambda_j$，则聚类的结果可用包含 $m$ 个元素的簇标记向量 $\vec\lambda = \left(\lambda_1; \lambda_2;\dots;\lambda_k\right)$ 表示。

对于聚类的结果，我们希望“簇内相似度”高，而“簇间相似度”低。下面是一些常用的聚类性能度量的内部指标：

• DB 指数：

支持向量机

支持向量机（support vector machines）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，它在学习复杂的非线性方程时能提供一种更加清晰和强大的方法。

在 Logistic 回归中，如果要令 $y = 1$，则有 $h_\theta(x) = \dfrac{1}{1+e^{-\theta^Tx}} \approx 1$，即 $\theta^Tx \gg 0$；当 $y=0$ 时有 $h_\theta(x)\approx 0$，即 $\theta^Tx\ll 0$。

对于 Logistic 回归，其代价函数为

$$-(y\log h_\theta(x) + (1 - y) \log (1 - h_\theta(x)))$$

将 $h_\theta(x)$ 代入上述函数得

$$-y\log\dfrac 1{1+e^{-\theta^Tx}} - (1-y) \log (1 - \dfrac 1{1+e^{-\theta^Tx}})$$

当 $y = 1$ 时，代价函数变为 $-\log \dfrac1{1+e^{-z}}$，此时令 $z \to +\infty$，代价函数将会趋近于 0，这也是为什么在看见 $y = 1$ 这样的样本时，会将 $z$ 赋值为一个极大值；类似地，当看见 $y = 0$ 这样的样本时，会将 $z$ 赋值为一个极小值。

在 Logistic 回归中，我们的代价函数 $J(\theta)$ 为

$$J(\theta) = \min_{\theta}\dfrac 1m\left[\sum\limits_{i = 1}^my^{(i)}\left(-\log h_{\theta}(x^{(i)})\right) + (1 - y^{(i)})\left(-\log (1 - h_\theta(x^{(i)}))\right)\right] + \dfrac{\lambda}{2m}\sum\limits_{j = 1}^n \theta_j^2$$

决策树

基本流程

决策树基于树结构进行决策，每个内部节点对应某个属性上的“测试”（test），每个分支对应于该测试的一种可能结果，每个叶结点对应于一个预测结果。

学习过程：通过对训练样本的分析来确定“划分属性”；

预测过程：将测试实例从根节点开始，沿着划分属性所构成的“判定测试序列”下行，直到叶子结点。

基本流程：分治：从上往下递归，在每个中间节点找到“划分”属性

停止条件：

• 当前节点包含的样本全部属于同一类别，无需划分；
• 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分：我们把当前结点标记为叶结点，其类别设定为该结点所含样本最多的类别；
• 当前节点包含的样本集合为空，不能划分：我们把当前结点标记为叶结点，其类别设定为其父节点所含样本最多的类别。

注意，第二类和第三类处理实质不同：第二类是利用当前结点的后验分布，第三类是把父节点的样本分布作为当前结点的先验分布。

Linear Regression

Model representation

线性回归的预测方程可以写为

$$h_\theta(x) = \sum_{i=0}^n\theta_ix_i$$

其中规定 $x_0 = 1$。

若令

$$\boldsymbol{\theta} = \begin{bmatrix}\theta_0 \\ \theta_1 \\ \vdots \\ \theta_n\end{bmatrix} \in \mathbb R^{n+1}, \boldsymbol{X} = \begin{bmatrix}x_0 \\ x_1 \\ \vdots \\ x_n\end{bmatrix} \in \mathbb R^{n+1}$$

则预测方程可以写为

$$h_\theta(x) = \boldsymbol{\theta}^\mathrm T\boldsymbol{X}$$

Cost function

Regularization

The problem of overfitting

过拟合（overfitting）指的是当有多个特征时，预测函数的代价可能会很低，但对于新的预测数据全都错误的情况，这会导致模型的泛化能力较差。

左侧的称为欠拟合（underfitting），右侧的称为过拟合。

当特征过多而数据过少时，就有可能出现过拟合的情况。

当过拟合的情况发生时，该如何解决呢？

1. 减少特征的数量，我们可以选择重要的特征进行保留，也可以使用模型选择算法，这种算法可以自动选择保留哪些特征和选择哪些特征，但是删去某些特征会导致一些信息的丢失，有可能这些信息都是我们需要的；
2. 保留所有的特征，进行正则化。我们通过正则化将参数 $\theta_j$ 的量级或数量减小，这在我们有很多特征的时候非常有效，由于每个特征都会对结果产生贡献，所以这种方法是行之有效的。

Cost Function

假设此时我们的模型为 $\theta_0 + \theta_1x + \theta_2x^2 + \theta_3x^3 + \theta_4x^4$，我们考虑加入惩罚项，使得 $\theta_3$ 和 $\theta_4$ 非常小，即

$$\underset{\boldsymbol{\theta}}{\arg\min}\dfrac 1{2m}\sum\limits_{i = 1}^m{\left(h_\theta(x^{(i)}) - y^{(i)}\right)^2} + 1000 \theta_3^2 + 1000\theta_4^2$$

Logistic Regression

逻辑回归可以用来处理离散标签分类的问题，如二分类、三分类 $\cdots$ $n$ 分类等。

由于在分类时我们不希望得到连续的值，而只得到两类离散值，如 $0$、$1$，我们引入 Sigmoid 函数（也称为 Logistic 函数）：

$$g(x) = \dfrac{1}{1+e^{-x}}$$

可以发现，$g(x) \in (0,1)$，$g(0) = \dfrac 12$，且 $\lim\limits_{x \to -\infty}g(x) = 0$，$\lim\limits_{x\to +\infty}g(x)=1$。

与线性回归类似地，我们定义回归函数为 $F_{\vec w, b}(\vec x) = \vec w \cdot \vec x + b$，与 Sigmoid 函数结合，就得到了逻辑回归模型 $f_{\vec w, b}(\vec x) = g(\vec w \cdot \vec x + b)=g\left(\sum\limits_{i=0}^nw_ix_i+b\right)$。

对于逻辑回归模型，它所做的是输入一个（组）特征 $x$，输出一个 0 到 1 之间的数字。

Interpretation of logistic regression output

我们将 $F_{\vec w, b}(\vec x)$ 的输出看做给定某个输入 $x$ 的分类 $y$ 等于 1 的概率。

Neural Networks

Non-linear hypotheses

在特征较少时，对于一个边界较为复杂的数据集中，我们可以使用逻辑回归，通过构造一个多项式来拟合决策边界，但在特征较多时，逻辑回归便显得较为繁杂，我们很难构造一个合适的多项式来较好的拟合其决策边界。

例如，当有 100 个特征时，如果我们只构造一个二次多项式，那么这个多项式最多会有 $\binom{100}{2}$ 个，也就是说，二次项会有 $\mathcal{O}(n^2)$ 个，极易导致过拟合的情况出现，同时也会出现计算量过大的问题。

如果我们继续将多项式的次数提高，那么会有 $\mathcal{O}(n^3)$ 个三次项，$\mathcal{O}(n^4)$ 个四次项……这对我们的模型构造和计算都是不可承受的。

考虑一个计算机视觉中的问题：如何让计算机识别出一辆汽车？人眼对于识别一辆汽车轻而易举，但对于计算机，它得到的可以是一个亮度的矩阵，也可以是一个颜色的矩阵等等。

在训练这样的模型时，我们需要做的是提供两个带标签的数据集，其中一个表示这里面的数据全都是车，另一个表示全都不是车。在分类器训练完成后，如果给定一个汽车的图片并要求它分类，理想状态下分类器可以识别出这是一辆汽车。

具体地，我们假设在每个图片的相同位置取两个像素点，并将其传入分类器中，如下图所示：

对于是汽车的样本和不是汽车的样本，我们可以发现，存在一个非线性的决策边界使得这两类可以被分开：

现在我们考虑每个样本的特征数量，假设每个样本都是一张 $50 \times 50$ 的图片，那么就有 2500 个像素点，特征数量 $n = 2500$，这是在只使用灰度图片的情况下，如果我们使用彩色图片，这个数字将会变为 $2500 \times 3 = 7500$。
此时如果使用逻辑回归的话极大可能会出现过拟合的问题，这就引出了我们的神经网络模型。