机器学习技法笔记 – Deep Learning(深度学习)

Deep Neural Network

一言以概之的说,Deep Learning(深度学习)通常也指Deep Neural Network(深度神经网络),也即DNN。

DNN通常设计并使用了多层神经网络,相对于浅层神经网络,他们通常分别具有如下特点:

对于浅层神经网络,它通常具有训练速度快、层次结构简单、泛化能力强。

而对于深度神经网络,它通常较难训练、层次结构复杂、泛化能力非常强,对于一些特定问题中使用的特定的深度神经网络模型,如CNN时,它可能还具有一定的物理意义,例如下图用于手写数字识别的DNN:

可以看出,在该DNN中,第二层的神经元分别都只专注于原始图像的某一块区域,这使得在这种问题,特别是图像处理问题中,赋予了这些神经元以物理意义。

而对于上文提到的DNN存在的较难训练、层次结构复杂等问题,随着硬件软件的进步带来的性能提升,已经逐渐不再是主要的问题。

我们在上节提到,对于Neural Network而言,不同的\(w^{(l)}_{ij}\)的Initialization(初始化)与Regularization可能会带来非常不同的局部最优解。

所以在本节,我们将更专注于训练DNN时的Regularization与Initialization问题上。

AutoEncoder

所谓Initialization也即是Pre-training。接下来我们介绍一种在实际中非常流行的Pre-training技术,称之为AutoEncoder。

AutoEncoder使用了一种被称之为Information-Preserving Encoding的思想。

对于\(l+1\)层第\(j\)个神经元的输入\(s^{(l+1)}_{ij}\),它们本质上第\(l\)层的输入\(x^{(l)}_{i}\)向量左乘了一个权重矩阵\(w^{(l+1)}_{ij}\)得到的。

Information-Preserving Encoding认为,一个好的\(w^{(l+1)}_{ij}\)应该尽可能使得:

$$tanh(s^{(l+1)}_{ij}) =w^{(l+1)}_{ij} ·x^{(l)}_{i} ≈ x^{(l)}_{i}$$

而AutoEncoder即是这样一种技术:

某种意义上,AutoEncoder训练出的每层权重,更像是一个Approximating Identity Function(近似恒等函数),它的作用如下:

即对于Supervised Learning(监督式学习)来说,Identity Function可以用于发现某些数据集隐藏的具有代表性的特征,而对于Unsupervised Learning(非监督式学习)来说,某些时候可以用于孤立点检测。

对于Basic AutoEncoder(一种最基本的AutoEncoder),它的Error Function具有如下形式:

$$e = \sum^{d}_{i=1} (g_{i}(x) – x_i)^2$$

使用Basic AutoEncoder用于Pre-training过程如下:

  • 利用AutoEncoder与反向传播算法逐层训练神经网络。
  • 使用\(w^{(1)}_{ij} =w^{(2)}_{ji}\)用于Regularization。

Denoising AutoEncoder

本节将会介绍一种用于对抗噪声的AutoEncoder,一言以概之,即是在Pre-training的时候主动添加人工噪声,通过这样被称之为Denoising AutoEncoder的方式进行Pre-training后,在之后的训练中,将具有更强的鲁棒性:

截至目前,我们已经有了四种Regularization的方法,他们分别是:Structural Constraints(结构化约束)、L1、L2 Regularizer(权重衰减正则化)、Early Stopping(提前停止)。

Principal Component Analysis

在本节中,我们将从最优化理论角度来分析为什么使用AutoEncoder来做Pre-training可以使得最终的DNN表现更好。

为了简化问题,我们假设某DNN的第\(k\)层输出\(h(x)\)具有如下形式:

$$h_k(x) = \sum^{\widetilde{d}}_{j=0} w_{kj}(\sum^{d}_{i=1} w_{ij}x_{i})$$

同时约定:

  • 移除\(x_0\)偏置项
  • 以\(w^{(1)}_{ij} = w^{(2)}_{ji} =w_{ij}\)作为Regularizer
  • 假设输出维度\( \tilde{d}\)远小于输入维度\(d\):

同时,将\(h_{k}(x)\)写成矩阵乘法形式如下:

$$\mathbf{h(x) = \color{red}{W}\color{blue}{W^{T}}X}$$

在上式中:

  • \(X\)是\(d×1\)的矩阵
  • \(\color{blue}{W^T}\)是\(\tilde{d} × d\)的矩阵
  • \(\color{blue}{W^T}X\)是\(\tilde{d}×1\)的矩阵
  • \(\color{red}{W}\)是\(1×\tilde{d}\)的矩阵
  • \(\color{red}{W}\color{blue}{W^T}X\)是实数

其Error Function具有如下形式:

$$E_{in}(W) = \frac{1}{N} \sum^{N}_{n=1} \begin{Vmatrix}X_n – \color{red}{W}\color{blue}{W^{T}}X_n \end{Vmatrix}^2$$

为了最小化\(E_{in}\),回忆线性代数的知识,我们首先对\(\color{red}{W}\color{blue}{W^{T}}\)做特征分解:

$$\color{red}{W}\color{blue}{W^{T}} =\color{red}{V}\Gamma\color{blue}{V^{T}}$$

其中,\(V\)为\(\Gamma\)矩阵中每个特征值对应的特征向量构成的矩阵,\(\Gamma\)为特征值构成的对角矩阵。

我们令:

$$X_n = \color{red}{V}I\color{blue}{V^{T}}X_n$$

则可以将原式改写为以下形式:

$$\min\limits_{v}\min\limits_{\Gamma} \frac{1}{N} \sum^{N}_{n=1} \begin{Vmatrix}\color{red}{V}I\color{blue}{V^{T}}X_n – \color{red}{V}\Gamma\color{blue}{V^{T}}X_{n} \end{Vmatrix}^2$$

首先最优化\(\Gamma\),此时\(V\)可以视为常数,通过观察上式,我们可以发现原函数值只与\(I – \Gamma\)有关,其中\(\Gamma\)是对角矩阵,它的秩小于等于\(\tilde{d}\),我们希望\(I – \Gamma\)的值越小越好,即\(\Gamma\)越接近单位矩阵\(I\)越好。

所以,我们将最优化的\(\Gamma\)记作:

$$\begin{bmatrix} I_{\tilde{d}} & 0 \\ 0 & 0 \\ \end{bmatrix}$$

然后我们将\(\Gamma\)视为常数,最优化\(V\),此时原函数可以改写为以下形式:

$$\min\limits_{V} \sum^{N}_{n=1} \begin{Vmatrix} \begin{bmatrix} 0 & 0 \\ 0 &I_{d- \widetilde{d}} \\ \end{bmatrix}V^{T}X_{n} \end{Vmatrix}^2$$

我们通过替换\(I_{d-\tilde{d}}\)为\(I_{\tilde{d}}\)改变了原函数的符号,将最小化问题替换为最大化问题:

$$\max\limits_{V} \sum^{N}_{n=1} \begin{Vmatrix} \begin{bmatrix}I_{\widetilde{d}} & 0 \\ 0 & 0 \\ \end{bmatrix}V^{T}X_{n} \end{Vmatrix}^2 $$

我们甚至可以通过观察发现,我们希望\(V\),即由特征向量组成的矩阵越大越好。

我们首先考察一种简单的情况,即\(\tilde{d}=1\),则原函数可由矩阵形式改写回原形式:

$$\begin{align} \max\limits_{V} \sum^{N}_{n=1} v^{T}x_{n}x^{T}_{n}v  && \text{subject to } v^{T}v = 1 \end{align}$$

上式是一个等式约束的最优化问题,回忆拉格朗日乘数法:即原函数的梯度与约束条件的梯度平行且方向相反,通过解其Lagrange Function来求得最优解:

$$\nabla{E_{in}} = \sum^{N}_{n=1} x_{n}x^{T}_{n}v – \lambda v = 0$$

而最优解的\(v\)正是在约束\(v^Tv=1\)下矩阵\(X^TX\)(输入数据集构成的\(n×n\)矩阵)的最大的一组特征向量。

而对于更一般\(\tilde{d}\),因为\(I_{\tilde{d}}\)是对角矩阵且有可能非满秩,即存在特征值为\(0\)为行列,所以对于每一个非零的特征值\(\gamma_j\),都存在一个最大的\(v_j\)与之对应,他们都是\(X^TX\)的特征向量。

求出了矩阵\(\Gamma\)与矩阵\(V\),则原矩阵\(\color{red}{W}\color{blue}{W^{T}}\)即为所求。

即我们得到了第\(k-1\)层各个输入与\(k\)层各个输入的特征转换关系,然后通过反向传播算法,进而计算出各个层的最佳权重,从而完成Pre-training。

以上是对Deep Learning在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Radial Basis Function Network。

机器学习技法笔记 – Neural Network(神经网络)

Motivation

一言以概之,Neural Network(神经网络)是一种Non-Linear Aggregation,我们首先从一个Perceptron(感知机)的Linear Aggregation开始,对Neural Network的工作原理做一个简单的介绍。

原始问题我们设定为分类问题,假设我们已经训练出了\(d\)个Perceptrons,并对其做Linear Blending,其\(G(x)\)具有以下形式:

若以Neural Network的角度,进行图像化的描述,则\(G(x)\)具有以下形式:

这样的\(G(x)\)即是最基础最简单的Neural Network(神经网络)模型了,它具有输入层,一层隐含层,输出层。

通过这样的单层Neural Network,我们可以实现\(AND(x_1, x_2)\)这样的数学运算:

它的\(G(x)\)具有以下形式:

用图形化的描述,以上Neural Network具有以下形式:

显然,我们可以通过更多,甚至无穷多的\(g_t\)进行Linear Blending,这种通过线性超平面经过无穷多组合后,甚至可以表示非线性的超平面:

但是这样并不是无代价的,其代价就是\(d_{vc}→∞\),在机器学习基石课程中曾经提到了\(d_{vc}\),\(d_{vc}\)是成长函数的Break Point,越大的\(d_{vc}\)意味着更强大泛化能力,但是也可能带来Overfitting与复杂的Model Complexity:

同时,单一层的Neural Network模型具有局限性,这样的Neural Network甚至不可以用来运算\(XOR(x_1, x_2)\),但是通过使用多层(多个隐含层),即可用来运算\(XOR(x_1, x_2)\),这某种意义上也是一种Feature Transform:

Neural Network Hypothesis

接下来为了后续问题的讨论,我们将用一些符号对Neural Network的一些基本概念做一些抽象化的定义。

对于一个如下形式的Neural Network:

其中,最左侧的\(x_0, x_1, x_2, … , x_d\)被称之为输入层,即输入的数据集。

而图中每一个节点被称之为一个神经元。

中间的两层被称之为隐含层,隐含层将其上层的输出\(s^{(l)}_j\)经过\(tanh(x)\)运算后作为下层的输入,其中\(s^{(l)}_j\)的计算公式如下:

$$s^{(l)}_j = \sum^{d^{(l-1)}}_{i=0} w^{(l)}_{ij}x^{(l-1)}_i$$

其中\(l\)是第\(l\)层,\(j\)是第\(j\)个神经元。

所以第\(l\)层的第\(j\)个神经元的输入计算公式如下:

$$x^{(l)}_j = \begin{cases}tanh(s^{(l)}_j) & \text{if l < L}\\ s^{(l)}_j & \text{if l = L} \end{cases}$$

其中\(tanh(x)\)的函数图像与解析式如下:

$$tanh(s) = \frac{exp(s)-exp(-s)}{exp(s)+exp(-s)} = 2\theta(2s)-1$$

\(tanh(x)\)在Neural Network模型中是一种流行的选择,因为它兼具线性函数与符号函数的特性。

夹在每一层中的\(w^{(l)}_{ij}\)被称之为权重,这也是我们后续需要优化的对象。

而最右侧层称之为输出层,即最终的结果。

梳理上述符号如下图:

对于每一层所有的神经元,他们的输入可以又以下矩阵表示:

Neural Network Learning

在Neural Network中,我们的目标是训练出每一层的所有\(w^{(l)}_{ij}\),使得最后的\(G(x)\)的\(E_{in}\)最小,我们定义Neural Network的Error Function如下:

$$e_n = (y_n – NNet(x_n))^2$$

接下来我们将介绍一种被称之为BackPropagation的算法来最小化\(e_n\):

我们首先考虑一个只有一个输出神经元的Neural Network,然后在输出层将\(e_n\)展开:

$$\begin{align} e_n & = (y_n – NNet(x_n))^2 = (y_n – s^{(L)}_1)^2 \\ & = (y_n – \sum^{d^{(L-1)}}_{i=0} w^{(L-1)}_{i1}x^{(L-1)}_i)^2 \end{align}$$

为了最小化\(L-1\)层权重\(w^{(L-1)}_{i1}\),我们对上式求偏微分,注意:

$$s^{(L)}_1 = \sum^{d^{(L-1)}}_{i=0} w^{(L)}_{i1}x^{(L-1)}_i$$

则原始关于\(w^{(L-1)}_{i1}\)偏微分具有如下形式:

$$\begin{align} \frac{\partial{e_n}}{\partial{w^{(L)}_{i1}}} & =\frac{\partial{e_n}}{\partial{s^{(L)}_{1}}} · \frac{\partial{s^{(L)}_1}}{\partial{w^{(L)}_{i1}}} \\ & =-2(y_n – s^{(L)}_1) · (x^{(L-1)}_{i}) \end{align}$$

然后我们可以通过Gradient Descent或者Stochastic Gradient Descent训练出一个最优的\(w^{(L)}_{i1}\),使得\(e_{n}\)最小,注意上式的\(w^{(L)}_{i1}\)隐含在\(s^{(L)}_1\)中。

我们令:

$$\delta^{(L)}_{1} = -2 (y_n – s^{(L)}_{1})$$

更一般地,对于任意层\(l\),其权重\(w^{(l)}_{ij}\)与\(e_n\)的偏微分关系如下:

$$\frac{\partial{e_n}}{\partial{w^{(l)}_{ij}}} =\frac{\partial{e_n}}{\partial{s^{(l)}_{j}}} ·\frac{\partial{s^{(l)}_{j}}}{\partial{w^{(l)}_{ij}}} =\delta^{(l)}_{j} · (x^{(l-1)}_i)$$

我们首先观察第\(l\)层第\(j\)个节点的\(\delta^{(l)}_{j}\)与\(e_n\)的关系:

$$s^{(l)}_{j} \stackrel{tanh}\Rightarrow x^{(l)}_{j} \stackrel{w^{(l+1)}_{jk}}\Rightarrow \begin{bmatrix}s^{(l+1)}_{1} \\ ··· \\ s^{(l+1)}_{k} \\ ··· \end{bmatrix}\Rightarrow ···\Rightarrow e_n$$

所以第\(l\)层第\(j\)个节点的\(\delta^{(l)}_{j}\)的计算公式如下:

$$\begin{align} \delta^{(l)}_{j} & =\frac{\partial{e_n}}{\partial{s^{(l)}_{j}}} \\ & = \sum^{d^{(l+1)}}_{k=1} \frac{\partial{e_n}}{\partial{s^{(l+1)}_{k}}} · \frac{\partial{s^{(l+1)}_{k}}}{\partial{x^{(l)}_{j}}} · \frac{\partial{x^{(l)}_{j}}}{\partial{s^{(l)}_{j}}} \\ & = \sum_{k} (\delta^{(l+1)}_{k}) (w^{(l+1)}_{jk}) (tanh'(s^{(l)}_{j})) \end{align}$$

通过计算上式,我们可以发现一个重要的事实:

即第\(l\)层的第\(j\)个节点的\(\delta^{(l)}_{j}\)可以通过第\(l+1\)层的\(k\)个\(\delta^{(l+1)}_{k}\)来表示。

如果假设本问题中的Neural Network只有一个输出节点,而我们已知:

$$\delta^{(L)}_{1} = -2 (y_n – s^{(L)}_{1})$$

然后,我们正向逐层计算\(x^{(l)}_{i}\),然后反向逐层计算所有\(\delta^{(l)}_{j}\),然后根据\(x^{(l)}_{i}\)与\(\delta^{(l)}_{j}\)更新梯度,从而最小化所有\(w^{(l)}_{ij}\),从而达到最小化\(e_n\)的目的。

这种算法被称之为BackPropagation Algorithm(反向传播算法),它的基本步骤如下:

通常步骤1到3会分多次,分多批并行进行,这种方式我们称之为mini-batch:

Optimization and Regularization

对于Neural Network的\(E_{in}\):

$$E_{in}(w) = \frac{1}{N}\sum^{N}_{n=1} err(( tanh(\sum_{i} w^{(l)}_{ij}x_{n, j})), y_n)$$

但是遗憾的是,多数情况下,Neural Network模型对应的\(E_{in}\)很可能不是凸函数(non-convex),所以多数情况下,我们可能无法找到所有的全局最优\(w^{(l)}_{jk}\),所以更多的情况我们可能会使用GD/SGD通过BackPropagation得到局部的最优。

通常情况下,不同的\(w^{(l)}_{jk}\)初始值决定了最后的局部最优解:

在下一节,我们将会介绍一种被称之为auto-encoder的方法,用于初始化\(w^{(l)}_{jk}\)。

接下来我们从VC Dimension的角度考察一下Neural Network,Neural Network的\(d_{vc} = O(V · D)\),其中\(V\)是神经元的数量,而\(D\)是各个神经元的权重。

我们可以看出,通过合理控制\(V\),我们可以得到Model Complexity与\(E_{in}和\)latex E_{out}$分别都在容忍范围的结果。

那么如何做Regularization呢?

一个基础的选择即是使用Weight-Decay L2的Regularizer:

$$\Omega(w) = \sum(w^{(l)}_{ij})^2$$

但是L2 Regularizer通常情况下带来的解释稠密的,为了避免这个问题,在Neural Network问题中一个更流行的Weight-Elimination Regularizer具有如下形式:

$$\sum \frac{(w^{(l)}_{jk})^2}{1+(w^{(l)}_{jk})^2}$$

这样的Regularizer具有L2 Regularizer的特性,同时等比缩放了每一个权重,一定程度避免了局部存在的较大权重带来的Overfitting。

同时,Early Stopping也是在Neural Network中常用的Regularization方法。

Early Stopping顾名思义即是提早停止,即在使用GD/SGD训练Neural Network时按适当的时机多次停止,并使用Validation验证Neural Network,并分别考察数次停止训练出的\(NNet(x)\),从而起到Regularization的效果。

为什么这样做可以起到Regularization呢?因为VC Dimension:

在机器学习基石的课程中我们曾有过结论,适当的\(d_{vc}\)通常是我们的最佳选择,而不是\(E_{in}=0\)的\(d_{vc}\)。

以上是对Neural Network在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Deep Learning。

机器学习技法笔记 – Gradient Boosted Decision Tree(GBDT)

Adaptive Boosted Decision Tree

一言以概之,Gradient Boosted Decision Tree简称GBDT,即AdaBoost与Decision Tree的Aggregation:

如果说Random Forest是在数据集上通过Bagging的方式,以数据集的随机性获得训练出决策树\(g_t\)的差异性。

那么对对于GBDT,则是通过Re-weighted的数据集,来训练出差异化的决策树\(g_t(t)\),最后将他们做Blending,来得到\(G(x)\):

接下来我们介绍一种被称之为Weighted Decision Tree Algorithm的算法,用于训练GBDT。

对于Re-weighted权重的最佳化问题,我们需要最小化下式:

接下来训练出\(u^t_n\)权重对应的\(g_t\),然后计算出Blending时该\(g_t\)的权重:

然后重复上述步骤\(T\)次,最后做Blending,得到\(G(x)\)。

但是这样做存在一些问题,对于一颗未经剪枝的决策树,它的\(E_{in}=0\),这非常可怕,这会导致错误率\(\epsilon_t=0\),这会导致\(\alpha_t=∞\),那么Blending也就显得毫无意义了,这样显然是不行的:

所以剪枝是必要的,在训练GBDT时,我们通常采用的决策树剪枝方法称之为Extremely-Pruned Tree,这种特殊的决策树的高度只有\(1\),是一种非常弱的决策树:

这种决策树又被称之为AdaBoost-Stump。

Optimization View of AdaBoost

接下来的内容,是对AdaBoost的一些数学上的理论分析,这一小节的理论分析,将会对\(\alpha_t=ln(\sqrt{\frac{1-\epsilon_t}{\epsilon_t}})\)这一结论做详细的解释。

对于AdaBoost的Re-weighted,其\(u^{(T+1)}_n\)有以下计算方式:

以分类问题为例,在上式中,无论是乘以或者除以\(♦︎_t\),都可以简化为\(♦︎^{-y_ng_t(x_n)}_t\),然后添加\(exp(x)\),在指数中补一个\(\alpha_t\),从而进一步整理上式如下:

上式将连乘替换为连加,值得注意的是,\(\sum^{T}_{t=1} \alpha_tg_t(x_n)\)即是\(G(x)\),所以我们有以下结论:

值得注意的是,对于下式:

与SVM中的Margin:

具有一些联系,可以看出,\(\sum^{T}_{t=1} \alpha_tg_t(x_n)\)即是为正规化的\(margin\),在SVM中,我们希望\(margin\)越大越好,在AdaBoost中也恰恰反映为如果\(\sum^{T}_{t=1} \alpha_tg_t(x)\)足够大,就会使得\(u^{(T+1)}_n\)足够小,从而达到Re-weighted的目的。

接下来我们介绍AdaBoost Error Function,对于AdaBoost,我们总希望\(u^{(T+1)}_n\)越小越好,所以我们希望\(\sum^{N}_{n=1} u^{(t)}_n\)越小越好,故AdaBoost Error Function具有以下形式:

对比\(err_{0/1}\)与\(err_{ada}\),我们可以发现\(err_{ada}\)是\(err_{0/1}\)上界:

接下来我们通过Gradient Descent(梯度下降)最小化\(\sum^{N}_{n=1} u^{(t)}_n\),注意\(h(x_n)\)是自变量:

通过观察,可以发现\(\frac{1}{N}exp(-y_n\sum^{t-1}_{\tau} \alpha_{\tau}g_{\tau}(x_n))\)可以进一步改写为\(u^{(t)}_n\),因此可以将原始进一步改写为以下形式:

上式是一个指数函数,回忆指数函数的麦克劳林泰勒展开:

$$e^x = \sum^{∞}_{n=0} \frac{x^n}{n!}$$

对上式做一阶泰勒展开:

由于:

$$\sum^{N}_{n=1} u^{(t)}_n = E_{in}$$

到此为止,回忆梯度下降的基本形式:

所以有:

$$v^T▽E_{in}(w_t) = \sum^{N}_{n=1} u^{(t)}_ny_nh(x_n)$$

需要注意的是,由于\(h(x_n)\)是函数,这里没有办法像在解Linear Regression或者Logistics Regression时,先对Error Function求梯度,再将\(x_n\)带入梯度函数后求值,同时乘以\(\eta\),然后迭代\(T\)次或者直到梯度值收敛到\(0\),所以进行了不同的处理。

回到原问题,最后问题转化为最小化下式:

以分类问题为例,上式的取值具有以下可能:

将等式右边进行如下改写:

回忆\(E_{in} · N = u^{(t)}_n\),所以上式可以继续改写:

那么谁来最小化\(E^{u^{(t)}}_{in}\)呢?回忆AdaBoost的工作过程,很容易发现是每一次根据\(u^{(t)}_n\)来训练\(g_t\)的过程。

那么最有步长\(\eta\)又该如何确定呢?这里同样与解Linear Regression或者Logistics Regression时不同,无法通过经验直接给定一个例如值为\(0.001\)的步长。

在AdaBoost每次根据当前权重训练出\(g_t\)时,回顾Error Function:

我们可以发现,除了\(\eta\),其他参数都是已知的,所以原问题转化为了一个最小化\(\eta\)的问题。

对于分类问题:

\(exp(-y_n{\eta}g_t(x_n))\)的取值可能有如下情况:

所以将原始进行一下改写:

最后令\(\frac{\partial{\widehat{E}_{ADA}}}{\partial{\eta}}=0\),最后求解得出\(\eta=ln(\sqrt{\frac{1-\epsilon_t}{\epsilon}})=\alpha_t\),即最佳步长。

小结一下上述推导:通过理论分析,我们证明了在使用AdaBoost时,通过梯度下降最小化\(u^{(t)}_n\)时,其最速下降方向\(h(x)\)即是每一次根据\(u^{(t)}_n\)来训练出\(g_t\),而最佳步长则是在训练出\(g_t\)后,令\(\frac{\partial{\widehat{E}_{ADA}}}{\partial{\eta}}=0\)后求解得出。

以上数学的推导即是AdaBoost在最佳化理论上的支撑。

Gradient Boosting

对于AdaBoost,其Error Function具有如下形式:

而所谓Gradient Boosting,它的Error Function则不再需要具体的形如指数函数这样的某一函数,它可以是任意函数:

如果将Gradient Boosting用于Regression问题,则可以使用平方误差函数:

对上式进行一阶泰勒展开:

与AdaBoost的情况类似,Regression问题在最小化\(h(x)\)时,最后经过化简,最终变成了最小化\(\sum^{N}_{n=1} h(x_n) · 2(s_n-y_n)\)的问题。

但是没有约束的\(h(x_n)\)有可能会使得\(h(x_n)=-∞\),如果是一个\(-∞\)的\(h(x_n)\),则步长\(\eta\)将无法约束下降步长,梯度下降也就无从谈起了。

所以Regularization是必要的,我们通过添加\(h(x_n)\)的平方项,再通过配方,将原式做以下改写:

我们可以发现,在\(y_n, s_n\)已知的情况下,求解\(h(x_n)\)即是求解一个Linear Regression问题。

最后确定最佳步长\(\eta\):

在各项已知的情况下,易求出\(\eta\)。

最后对Gradient Boosting做一下小结:

首先根据Gradient Boosting Error Function最小化\(g_t\),然后求出最佳化步长\(\eta\),也即Blending时的\(\alpha\),然后更新\(s_n\),重复\(T\)次,最后Blending,得出\(G(x)\)。

Summary of Aggregation Models

最后对所有的Aggregation方法做一个总结。

对于在训练完差异化的\(g_t\)后再进行Blending的方式:

对于一边训练出差异化的\(g_t\),一边进行Blending的方式:

以上是对Gradient Boosted Decision Tree在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Neural Network。

机器学习技法笔记 – Random Forest(随机森林)

Random Forest Algorithm

一言概之,随机森林即Bagging与Decision Tree的Aggregation:

其中,Bagging是指通过bootstrap的方式从数据集\(D\)中,随机抽选\(N\)组数据,重复\(T\)次,每次得到的数据集称之为\(\widetilde{D}_t\),然后通过C&RT等方法在\(\widetilde{D}_t\)上生成决策树,得到\(g_t\),最后通过Blending的方式对\(g_t\)线性组合,得到最后的\(G(x)=Uniform(g_t)\):

这里简要的回顾一下决策树与C&RT算法:

即在原始数据集\(D\)上通过Decision Stump训练出不纯度最低的\(b(x)\),再将数据集一分为二,然后将一分为二的数据集视为原始数据集,递归的训练重复上述步骤,直到不纯度为\(0\)或者数据集不可再分,最后进行剪枝。

值得注意的是,在Random Forest中,训练每一个决策树\(g_t(x)\)的过程是可以并行化的,因为每一个Bagging与Bootstrap操作与C&RT算法的执行互相独立。

Random Forest中对于每一颗由C&RT生成决策树来说,由于Bagging而从数据集的差异性上获得了\(g_t\)的差异性。

但是在实际应用中,Random Forest通常还会使用被称之为Feature Projection或者Feature Expansion的方法强化训练数据集的差异性,从而使得训练出的\(g_t\)经过Blending后表现更好。

所谓Feature Projection,即在\(n\)维数据集\(D\)中每次并非选取\(n\)维的数据,而是选取更低维度的数据,这种选取方式等效于对\(d’\)维向量\(x\)乘以一个对角线上部分为latex 0$的单位对角矩阵:

通过Feature Projection得到的Random Forest可以由以下形式概括:

而所谓Feature Expansion,是在经过Feature Projection操作后得到的\(d’\)维数据集\(\widetilde{D}\)的\(x\)向量的某一或多个维度上再乘以矩阵\(x\),得到一些具有新特征的向量:

通过FeatureExpansion得到的Random Forest可以由以下形式概括:

Out-Of-Bag Estimate

回顾Random Forest的Bagging过程,对于每一颗训练出的决策树\(g_t\),与数据集\(D\)有如下关系:

对于星号的部分,即是没有选择到的数据,称之为Out-of-bag(OOB)数据,当数据足够多,对于任意一组数据\((x_n, y_n)\)是OOB的概率为:

对于这些OOB数据,可以用来验证Random Forest最后的\(G(x)\):

当用于验证\(G(x)\),其Cost Function具有以下形式:对于Random Forest,通常使用上式评价其表现。

Feature Selection

对于一个\(N\)维向量\(x\),即\(x\)向量具有\(N\)个特征,但是并不是每一个维度的特征都和最终的\(G(x)\)是相关的。

这一点非常重要,特征提取是一个重要话题,当原始数据集\(D\)的维度非常大时,在使用某种机器学习算法前,特征提取是必要的,这样可以很大程度减少后续训练的时间与空间复杂度。

在Random Forest中,我们使用一种被称之为Permutation Test的方法来做Feature Selection,它具有以下形式:

其中,\(performance(D)\)是Random Forest在原始数据集\(D\)上的表现,而\(performance(D^{(p)})\)是将原始数据集\(D\)上的第\(x_i\)维度与\(x_j\)调换位置后得到的\(D^{(p)}\)上的表现,所以\(importance(i)\)即描述了\(x_i\)的重要程度,更进一步的,所谓\(performance(D)\)即\(E_{oob}(D)\):

上式也说明了我们使用OOB数据做Permutation Test。

Random Forest in Action

下图是21颗决策树组成的随机森林在二位数据上的表现:

以上是对Random Forest在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Gradient Boosted Decision Tree。

机器学习技法笔记 – Decision Tree(决策树)

Decision Tree Hypothesis

在上一章中,我们介绍了通过Re-weighted思想来差异化\(u^{(t)}_n\)(权重)训练出不同的\(g_t(x)\)然后做Aggregation的AdaBoost。

AdaBoost本质上是一种non-uniform的Bagging Aggregation方法。

在本章中,我们将介绍一种conditional的Bagging Aggregation方法,称之为Decision Tree(决策树)

首先,我们从下图在视觉上初步认识一下决策树:

上图是一个形象化的例子,通过树形图的方式描述了“要不要上课”这一条件决策流程。

其公式化的描述如下:

需要注意的是这是一种递归的描述,其中,\(G(x)\)是一颗生成树,是整颗决策树的入口,\(b(x)\)是判断是否要进入当前分支\(c\)的Branching Criteria Function,\(G_c(x)\)是子树的入口。

接下来,将介绍生成决策树的算法。

Decision Tree Algorithm

生成决策树具有很多著名的算法,在本文中我们介绍C&RT(Classification and Regression Tree),这个算法的主要思路如下:

即对于决策树函数,对于输入的数据集\(D\),如果递归至叶子节点,则输出叶子节点的\(g_t(x)\)对于数据集\(D\)中\((x_n, y_n)\)的值,否则,在当前数据集\(D\)上训练\(b(x)\),然后在将数据集\(D\)一分为二,递归调用决策树函数。

在C&RT中,如何训练\(b(x)\)是非常重要的话题。

其中,\(b(x)\)具有以下形式:

对于每一个\(b(x)\),最小化\(\sum^{2}_{c=1} \vert h(D_c) \vert · impurity(h(D_c))\),可以看出\(c=2\),即\(b(x)\)的输入是被分为两份的数据集\(D\),表现在数据结构上,即是二叉树,而\(impurity(h(D_c))\)是不纯度。

通常,对于回归问题,其\(impurity(h(D_c))\)通常有以下定义:

而对于分类问题,\(impurity(h(D_c))\)则有以下定义:

对于基础的Base Hypothesis,我们依然选择Decision Stump(决策桩),它具有以下形式:

通过最小化\(impurity(h(D_c))\),可以求出最佳的\(\theta\),接下来我们将给出完整的C&RT算法。

Decision Tree Heuristics in C&RT

一个完整的C&RT算法如下:

当\(impurity(h(D_c))=0\),或者\(D_c\)不可再分,则C&RT算法结束。

需要注意的是,C&RT算法生成的决策树如果没有任何的Regularization操作,放任子树生长,会使得\(E_{in}=0\),即会带来Overfitting,所以我们需要为C&RT算法加上Regularization项来避免Overfitting的发生,这个过程也称之为剪枝。

通常可以通过对叶子节点剪枝来做Regularization:

而Regularization项具有以下形式:

具体过程如下:

  • 首先通过C&RT生成决策树
  • 随机剪枝一个或多个叶子节点,重复多次,得到\(N\)个\(G(x)\)
  • 对所有\(G(x)\)在数据集\(D\)做Validation,选取\(E_{in}\)最小的\(G(x)\)

决策树不仅可以用在Numerical Features中,也可以用于Categorical Features:

对于数据集中不分数据的缺失,也可以通过训练多个\(b_n(x)\),来做最佳\(b(x)\)的近似。

Decision Tree in Action

下图是一个C&RT与AdaBoost算法的对比,通常情况下C&RT具有更高的效率:

最后对C&RT做一个总结:

C&RT具有诸多优点,例如对于人类易于解释,易于处理多分类问题,对于有缺失的数据集也可以应对,易于处理非线性分类或者预测问题。

以上是对Decision Tree在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Random Forest。

机器学习技法笔记 – Adaptive Boosting(AdaBoost)

Motivation of Boosting

在上一章中,我们证明了在Blending时,如果\(g_t(x)\)之间的差异越大,则最后得到的\(G(x)\)的泛化能力越强。

在上一章的结尾我们介绍了Bootstrap,这Bagging Aggregation种方法通过在数据集\(D\)中随机抽取\(N\)组数据,重复\(T\)次,每次训练出\(g_t(x)\),然后在用Linear Blending做Aggregation,得到\(G(x)\),这是一种通过数据集的差异性来获得\(g_t(x)\)的方法。

在本章中,我们将引入Weighted(权重)的概念,并介绍一种Weighted Base Algorithm,通过权重的差异性得到差异化的\(g_t(x)\),这种算法我们称之为Adaptive Boosting,通常简称为AdaBoost。

Diversity by Re-weighting

下图是一个引入权重的例子:

在右图中,描述了一次Bootstrap在\(\widetilde{D}_t\)上随机选取的数据点,可以发现\((x_1, y_1)\)被选取了两次。

在左图中,数据集\(D\)上每一组\((x_n ,y_n)\)的权重\(u_n\)为该次Bootstrap该数据被选中的次数,然后通过最小化\(E_{in}\),得到\(g(x)\)。

最小化带权重的\(E^{u}_{in}\)的一般形式如下:

接下来,我们将介绍如何通过Re-weighting(重置权重)来得到差异化的\(g(x)\):

从上图可以看出,对于相同的数据集\(D\),我们如果想要得到不同的\(g_t(x)\),那我们需要使每次用于训练\(g(x)\)的权重\(u^{(t)}_n\)不同,或者说非常不同。

那么如何使得\(u^{(t)}_n\)非常不同呢?

比较直观的做法是,让\(g_t(x)\)在使用\(u^{(t+1)}_n\)进行Blending后得到的\(G(x)\)在\(D\)上表现非常差,甚至正确率只有50%,如同抛硬币:

假设数据集\(D\)上共有7337个数据,使用\(u^{(t)}_n\)的\(G(x)\)的正确分类了6211个数据,错误分类了1126个数据,则使用\(u^{(t)}_n\)的正确率为\(\frac{6211}{7337}\),为了使得\(u^{(t+1)}_n\)的正确率为\(\frac{1126}{7337}\),需要使\(u^{(t)}_n\)乘以\(\frac{6211}{1126}\)。

有了Re-weighted的思想,我们将在下节介绍AdaBoost算法。

Adaptive Boosting Algorithm

我们先定义错误率\(\epsilon_t\)如下:

在定义缩放因子如下:

其中,\(\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}\)在定义域\([0, 1]\)上单调递减,在\(\epsilon_t = 0\)的极限为\(∞\),在\(\epsilon_t = \frac{1}{2}\)时值为\(\frac{1}{2}\),在\(\epsilon_t = 1\)时值为\(0\),从\(u^t_n\)更新到\(u^{t+1}_n\),只需要乘以或者除以放缩因子即可。

完整的AdaBoost算法如下:

首先初始化\(u^{(1)} = [\frac{1}{N}, \frac{1}{N}, ···, \frac{1}{N}]\),然后重复\(T\)次下述操作:

  • 从数据集\(D\)中以\(u^{(t)}\)权重训练出\(g_t\)
  • 更新权重\(u^{(t)}\)到\(u^{(t+1)}\),具体根据需要乘以或者除以放缩因子。
  • 计算\(\alpha_t\)

最终得到\(G(x) = sign(\sum^{T}_{t=1} \alpha_tg_t(x))\)

下图是AdaBoost的理论保证:

即只要\(\epsilon_t < frac{1}{2}\),\(E_{in}(G)\)经过T轮迭代后会足够小,而且\(d_{vc}\)增长较慢

Adaptive Boosting in Action

在实际问题中,我们通常会使用一个比较弱的Learning Algorithm,较为常用的是Decision Stump(决策桩):

Decision Stump在二维数据集上是一条有向线段,下图是一个AdaBoost算法在经过\(t = 100\)次循环后在二维数据集上的表现:

以上是对Adaptive Boosting在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Decision Tree。

 

机器学习技法笔记 – Blending and Bagging(混合与装袋)

Motivation of Aggregation

本章将讨论Aggregation在已知Hypotheses上的应用,通过Mix(混合)或者Combine(组合),得到表现更加的Predictor和Classifier。

以下是四种Aggregation方式的例子:

  • Select with validation:

选择\(E_{in}\)最小的\(g_*(x)\),即经过Validation后表现最好的\(g(x)\):

  • Mix uniformly:

每个\(g(x)\)平权投票:

  • Mix non-uniformly:

每个\(g(x)\)非平权投票:

  • Combine conditionally:

每个\(g(x)\)的票数由一个\(q_t(x)\)决定:

为什么需要Aggregation?

假设我们现在有一些比较弱的Hypotheses,通过Aggregation,例如Mix uniformly,我们可以得到一个泛化能力更强的\(G(x)\),这个\(G(x)\)在数据集上的表现更好,如下图:

Uniform Blending

接下来我们将介绍一种Aggregation的方法,称之为Uniform Blending,即Mix uniformly,所有\(g(x)\)平权投票:

上式是Uniform Blending用于分类的形式,对于预测类的问题,Uniform Blending具有以下形式:

下面将给出证明来说明为什么Uniform Blending相对于单独的\(g(x)\)表现更好:

其中,\(avg\)可以视为\(\sum_{t=1}^{N} \frac{g_t(x)}{N}\),而\(G=\sum_{t=1}^{N} g_t(x)\)

所以有以下结论:

即Uniform Blending相对于单独的\(g(x)\)表现更好。

Linear and Any Blending

接下来介绍非平权投票的Aggregation方式,即Linear Blending:

上式的Cost Function如下:

通过最小化\(E_{in}\)即上式,求得最优的\(\alpha\)矩阵。

对于分类问题,约束\(\alpha_t≥0\),是可有可无的,因为如果求出的\(\alpha_n<0\),则只需要将\(g(x)\)取相反数即可。

上文介绍了\(\alpha\)矩阵的求解方法,它和求解一般的Linear Regression的思路大同小异,最后求得的\(\alpha\)矩阵是一个解析解。

通过在数据集上最小化\(E_{in}\)得到\(g_t(x)\)后,在最小化\(\alpha_n\)所带来的复杂度非常高。

这样可能会导致Overfitting。

通过以下方法可以一定程度降低Overfitting的风险。

首先将原始数据集分为\(D_{train}\)与\(D_{val}\),通过\(D_{train}\)训练得到\(g^-(x)\),然后让\(g^-(x)\)作用在\(D_{val}\)上,得到\(z_n = \phi^-(x) = \sum^{N}{t=1} g_t(x)\),这样一定程度避免了两次最小化\(E{in}\)可能造成的Overfitting。

上述Aggregation方法即是Linear Blending,如果需要更强大的泛化能力,可以在计算\(\phi^-(x)\)时采用更加复杂的模型。

这种方法即是Any Blending,但是具有更高的Overfitting风险。

Bagging

与Blending不同的是,Bagging不需要事先从数据集训练出各种\(g(x)\),而是一边训练,一边组合的。

对于如何训练出不同的\(g(x)\),通常有以下方法:

即从不同的模型训练得到、从不同的参数得到、从算法的随机性得到、从数据的随机性得到。

接下来我们将介绍一种从数据的随机性训练出不同的\(g(x)\)的方法,这种方法通过在数据集上随机选取N个数据,重复T次,在这N个数据中通过Pocket算法训练出\(g_t(x)\),然后将他们做Uniform Blending,得到最终的\(G(x)\),效果如下图:

我们可以发现通过这样的方法,依然可以做到非线性的分类,仍然具有不错的泛化能力。

以上是对Blending and Bagging在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Adaptive Boosting。

机器学习技法笔记 – Support Vector Regression (支撑向量回归)

Kernel Ridge Regression

在上一章中,我们将Kernel的思想运用于Logistic Regression,在本章,我们将介绍Kernel的思想在Ridge Regression与Support Vector Regression上的运用。

在上一章中,我们介绍了Representer Theorem(表示定理),这个定理指出,对于任何L2 Regularized的问题,其最佳的\( w_* = \sum_{n=1}^{N} \beta_{n}Z_{n}\),即任何最佳的\(w_*\)都可以表示为\(\beta_n\)与\(Z_n\)的线性组合,如下图:

如果原始问题带有L2 Regularized的正则项,且\(err(y_n, w^Tz_n) = (y_n-w^Tz_n)^2\),则该问题是一个Ridge Regression问题,如下图:

将\(w_*\)用\(\sum^{N}_{n=1}\beta_nZ_n\)表示并运用Kenel Trick后,原始问题具有以下形式:

用矩阵乘法的形式替代求和符号后,可以将原问题改写为以下形式:

上式即Kernel Ridge Regression的标准形式,之后求上式梯度,并令其梯度为\(0\),然后可以求得\(\beta\)的解析解:

其解析解具有以下形式:

其中,因为\(K\)是半正定的,所以,当\(\lambda > 0\)矩阵\((\lambda I+K)^{-1}\)的逆一定存在的。

对于Kernel Ridge Regression相比于Linear Ridge Regression,他们的解析解和复杂度总结如下:

易见,当Linear Ridge Regression的泛华能力有限,难以做比较复杂的数据拟合,而Kernel Ridge Regression由于使用了Kernel Function,具有更强的泛华能力,但是同时也带来了更高的计算复杂度。

Support Vector Regression Primal

接下来,我们将介绍Support Vector Regression(支撑向量回归),首先介绍它的原始问题。

在上文介绍的Kernel Ridge Regression的别名即Least-Squares Support Vector Machine(最小二乘支撑向量机),对比于Soft-Margin Support Vector Machine(软间隔支撑向量机),具有以下问题:

即LSSVM的解析解的\(\beta\)矩阵不是Sparse(稀疏)的,这会导致计算复杂度增加,我们希望\(\beta\)是Sparse的,而不是dense(稠密)的。

为解决这个问题,接下来我们介绍Tube Regression:

对于Regression问题,与Soft-Margin Support Vector Machine类似,Support Vector Regression同样容忍犯错,并记录犯错的程度,然后试图最小化犯错。

它的Error Measure函数如下:

之所以又叫Tube Regression,是因为在二维数据集上,这种Error Measure的方式划分了一个形似Tube(管道)的区域,这个Tube具有\(2\epsilon\)的高度,超平面容忍在\(2\epsilon\)内数据集,同时记录不在Tube中的数据集偏离Tube的距离,如下图:

Tube Regression与Squared Regression的的Error Measure曲线如下图所示:

可以看出,当\(\vert{s-y}\vert\)很小时,两者相近。

接下来,我们用Tube Regression与L2 Regularized项构造Support Vector Regression的原始问题:

与推导Soft-Margin Support Vector Machine的原始问题时相同,上式不是一个QP问题,不能用QP Solver求解,所以需要使用一个或者多个变量替代\(max(0, \vert{w^Tz_n-y}\vert-\epsilon)\)。

仿照Soft-Margin Support Vector Machine的思路,我们可以对上式进行如下改写:

我们通过引入\(\xi^∨_n\)和\(\xi^∧_n\),分别描述了给定数据在Tube上的偏离程度,将原始问题改写为一个QP问题,然后通过构造Lagrange Function,从而进一步通过求解其强对偶问题,然后使用QP Solver求解。

Support Vector Regression Dual

由于Support Vector Regression同样满足KKT条件,我们通过构造Lagrange Function:

然后对\(w, b\)求偏微分,结果如下:

 

最终,其强对偶问题具有以下形式:

之后可以便可以使用QP Solver求解。

然后考虑结合对偶松弛条件:

对于在Tube内,即\(\vert{w^Tz_n+b-y_n}\vert  < \epsilon\)的数据集,将有以下结论:

由于\(w=\sum^{N}_{n=1}(\alpha^∨_n-\alpha^∧_n)z_n\),由于对偶松弛条件,\(\xi^∨_n=0\)和\(\xi^∧_n=0\),所以\((\epsilon+\xi^∨_n-y_n+w^Tz_n+b)≠0\)且\((\epsilon+\xi^∧_n-y_n+w^Tz_n+b)≠0\),所以\(\alpha^∨_n=0\)且\(\alpha^∧_n=0\),所以\(\beta_n=0\)

这说明了\(\beta\)矩阵是可能是稀疏的。

Summary of Kernel Models

对于线性模型:

其中,第二行所展示的方法较为常用,在数据量较少,不需要强大的泛化能力时,可以尝试使用线性模型。

对于核模型:

其中,第二行较为常用,第三行由于\(\beta\)矩阵是dense的,在数据量较大时计算复杂度较高。

以上是对Kernel Support Vector Regression在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Blending and Bagging。