机器学习笔记-Neural Network

林轩田机器学习技法关于特征学习系列，其中涉及到Neural Network，Backpropagation Algorithm，Deep Learning，Autoencoder，
PCA，Radial Basis Function Network，K-Means，Matrix Factorization 等。

• 机器学习笔记-Neural Network
• 机器学习笔记-Deep Learning
• 机器学习笔记-Radial Basis Function Network
• 机器学习笔记-Matrix Factorization

Motivation

从我们熟悉的perceptron说起， 在perceptron算法中，通过比较权重和特征的乘积与0的大小关系来对样本进行分类。如果我们现在将一堆的perceptron用linear aggregation的方式组合起来的话，我们可以使用如下的图示来表示：

对于一个输入X，和第一个perceptron g1的权重w1的乘积然后取sign可以得到g1的分类结果；和第二个perceptron g2的权重w2的乘积然后取sign可以得到g2的分类结果；⋯。然后对所有这些g1,g2,⋯,gT的结果利用权重α1,α2,α3,⋯,αT做一个线性的组合得到最后的模型G。该模型的数学表达式如下：

通过上述的计算过程就可以得到一个样本x的输出G(x)。

可以看到在这个模型中有

• 两组权重，第一组w1,w2,⋯,wT是每一个perceptron的权重，第二组α1,α2,⋯,αT用来表示每一个g的“票数”或者说是权重。
• 在这个模型中除了有两层权重之外，还有两层sign函数。也就是在每一个神经元中都有一个sign函数，将权重和特征的乘积映射到{+1,−1}然后输出。使用阶梯状来表示得到下图。
  

这就是一个利用linear aggregation将多个perceptron集成起来的模型，我们可以调节所有的参数w和α，这样的模型有什么用呢？或者说通过这样的模型我们可以得到什么样的边界呢？

假设我们有两个perceptron分别是g1和g2，现在我们看看当我们使用linear aggregation的方式将两个感知器或者说两条线合起来也就是得到一个aggregation of perceptron模型的时候，这个模型可以做到一个怎么样的边界呢？可能这个模型可以做到如右图所示的逻辑操作AND。也就是只有当两个g的结果都输出+1的时候，aggregation of perceptron的输出为+1，否则为−1。下面我们来分析一下linear aggregation of perceptron是怎么做到AND(g1,g2)的。

一种可能的方式是：将第二层的权重值设置为α0=−1,α1=+1,α2=+1，也就是两个perceptron g1和g2的权重都是+1，另外假设还有一个perceptron g0，它的输出是+1（其实是偏置b的角色）， 它的权重是−1。那么linear aggregation of perceptron的数学表达式为：G(x)=sign(−1+g1(x)+g2(x))，通过这样的设置G(x)就能做到如上图中的AND操作。事实上：如果g1(x)=g2(x)=+1⟶G(x)=sign(−1+1+1)=sign(1)=1；如果g1和g2中至少有一个是−1，那么G(x)=−1。这样我们可以得到，将perceptron通过linear aggregation的方式集成起来就可以得到一些比较复杂的非线性的边界。

这样的模型其实是非常有能力的，例如对于下图所示的数据来说，使用任意一个单一的perceptron都不能将数据划分的很好，但是当使用8个不同的perceptron的时候可以得到一个差不多的分类边界，当使用16个不同的perceptron的时候就能得到一个更为平滑的分类边界。

Multi-Layer Perceptrons: Basic Neural Network

尽管这样的模型非常的powerful，但是仍然有些事情是做不到的， 例如同样使用上文提到的两个perceptron g1,g2， 想要使用上文中的模型G(x)做逻辑操作XOR(g1,g2)是不可能的。XOR(g1,g2)当且仅当g1和g2中只有一个为TRUE时，结果为TRUE，否则为FALSE。我们注意到XOR(g1,g2)=OR(AND(−g1,g2),AND(g1,−g2))。即其实我们需要先经过对g1和g2的两个AND操作，然后再将AND的结果做OR就可以得到XOR。其模型的示意图如下，通过这样的模型得到的结果就和XOR(g1,g2)的结果是一致的。

现在从单一的perceptron延伸到linear aggregation of perceptron，然后又延伸到Multi Layer perceptron，这样的模型其实就是神经网络最基本的结构。需要说明的是， 虽然Neuron Network跟生物体中的神经网络有一定的关系，做了一定的借鉴，但是从工程学来说我们处理的是一个数学模型，不需要受到生物体的神经网络的机制的影响，就像飞机是参考鸟制造的，但却不是通过摆动机翼来飞行的。

Neural Network Hypothesis

上一小节给出了神经网络的基本长相：

如果将每一层的计算当成是一个转化的话，那么上图中节点OUTPUT可以理解为输入是其上一层转换结果的一个线性模型：s=wTϕ(2)(ϕ(1)(x))。我们之前学习过的每一个线性模型都可以用在这里：如果我们想要做分类，那么就对s加一个sign函数；如果要做回归分析的话，s直接作为最终的结果进行输出；如果要做soft分类的话，那么对s加一个logistic函数作为结果输出。在以后的讲解中，我们将线性回归模型作为神经网络最后一层所使用的模型，也就是关心神经网络最终的输出和真实输出的square error。

除了输出神经元部分，再来看看中间的其他神经元在做什么，通常每一个神经元会将上一层的输出（作为这个神经元的输入）和该神经元的权重的乘积s喂给一个函数做运算作为该神经元的输出，我们将这个函数称之为**函数，常用的**函数是tanh(s)。为什么不使用如上图中所示的sign函数， 或使用线性函数，即直接将s输出呢？原因是sign函数不是连续的，难以最佳化；如果每一个神经元都使用线性函数的话，那么整个模型仍然是一个简单的线性的模型，其表达能力和使用perceptron并没有区别。

tanh函数的长相如下图：

可以看到它和阶梯函数sign长的有点像，又比sign容易做最佳化，并且和我们熟悉的logistic函数θ有很大的关系。其函数的表达式为：

在以后的讲解中，每一个中间层的神经元的**函数都默认使用tanh函数。

Neural Network Hypothesis

一个简单的神经网络的结构如下：

该神经网络共有3层，为了描述方便，我们将输入层规定为第0层，第一层和第二层为hidden layer，每一层分别有2个神经元和3个神经元，第三层为输出层只有一个神经元。所以该神经网络的层数L=3， 每一层的神经元的个数为d(1)=2, d(2)=3, d(3)=1。

网络中的权重表示为 w(l)ij。首先：w(l)表示第l−1层到第l层的权重，即w(2)表示第1层到第2层的权重；w(l)ij表示第l−1层中第i个神经元到第l层中第j个神经元的权重， 即w(2)23表示第1层中第2个神经元到第2层中第3个神经元的权重。其中：

• 1≤l≤L；
• 0≤i≤d(l−1)；
• 1≤j≤d(l)。

l−1层中由于会多一个偏置项，所以 i 的起始值为 0 而不是 1。

定义了这些权重之后，我们就可以通过这些权重来计算每一个神经元的输入 s 和输出 x 。
第 l 层第 j 个神经元的输入为 s(l)j：

第 l 层第 j 个神经元的输出为 x(l)j：

s(l)j和x(l)j的关系是：s(l)j⟶tanh(s)⟶x(l)j

通过上面的计算方法，给定一个样本x，我们将其作为输入层x(0)，依次计算每一层的输出x(l)，最终在L层给出预测值x(L)1。
通常我们可以神经网络中每一层的神经元的个数来描述一个神经网络的架构，例如3-5-1 NNet表示的是一个 3 层神经网络，其输入层有 3 个神经元，隐藏层有 5 个神经元，输出层有 1 个神经元。这样我们也可以得知这个网络中所有的权重的个数为(3+1)×5+(5+1)=26个。

Neural Network Learning

现在我们已经对神经网络的基本工作方式有了直观上的了解：将输入x经过与第1层的权重计算得到第1层神经元的输入， 经过hyperbolic tangent转换为第1层的输出， ⋯。现在我们要解决的问题是如何从资料data中学习到这些权重，使得改模型的Ein最低。当只有一个神经元的时候，这个模型退化为Perceptron，那么我们可以通过PLA算法来得到最终的权重；如果有多个神经元，也就是有了一层隐藏层的时候，这个模型其实就是aggregation of perceptron，这个时候可以通过gradient boosting的方式学习得到其中的权重，即每一次加一个神经元到网络中，直到达到满意的结果为止。

当有多个隐藏层的时候，该如何计算其中的权重呢？在regression的设定下，我们希望对于某一个样本点(xn,yn)来说， 该模型的输出h(xn)和target value yn之间的squared error最小，即对于一个样本点来说， 我们想要最小化 en=(yn−h(xn))2=(yn−NNet(xn))2。如果我们知道 en 关于每一个变量 w(l)ij 的变动是如果变化的， 那么我们就可以更新 w(l)ij 来最小化 en， 而梯度∂en∂w(l)ij正好告诉了我们这件事情， 当我们知道了en关于每一个变量的w(l)ij的梯度之后， 就可以使用gradient descent(GD)或者stochastic gradient descent(SGD)来找到一步一步的更新w(l)ij最后找到最佳的权重。所以现在的问题只剩下如何计算∂en∂w(l)ij

从简单的开始算起， 首先我们计算∂en∂w(L)i1， 也就是en对于最后一层权重的偏导数。en和w(L)i1的关系如下：

根据求导的链式法则可以得到：

那么现在对于第L层中的每一个权重，我们都已经可以通过上式进行计算了。
那么en对于一般的第 l 层(1≤l<L)中的权重 w(l)ij(0≤i≤d(l−1);1≤j≤d(l))的偏导仿照(1)式可以得到：

其中δ(l)j使我们目前算不出来的， δ(l)j=∂en∂s(l)j， 表示en对于第l层第j个神经元的偏导。

所以现在的问题剩下如何求解 δ(l)j=∂en∂s(l)j

现在我们来分析下 s(l)j 是如何影响到 en 的，

同样使用求导的链式法则：

根据这样的推导我们发现，如果我们知道了δ(L)，就能计算出δ(L−1)， ⋯，就能计算得到δ(1)， 而根据前面的计算可以知道δ(L)=−2(yn−s(L)1)。
另外根据

可以很轻易的求出tanh′(s)。
至此我们就得到了计算梯度(2)的方法。有了计算梯度的方法，那么我们就可以利用梯度下降类方法最小化en并确定最终的权重 w(l)ij。通过上面的推导得到了一个很著名的算法：Backpropagation Algorithm

Backpropagation Algorithm

initialize all weights w(l)ij
for t=0,1,2,⋯,T

1. stochastic:randomly pick n∈{1,2,⋯,N}
2. forward: compute all x(l)i with x(0)=xn
3. backward: compute all δ(l)j
4. gradient descent: w(l)ij⟵w(l)ij−ηx(l−1)iδ(l)j

return gNNET=(⋯tanh(∑jw(2)jk⋅tanh(∑iw(1)ijxi)))

即首先初始化所有的权重w(l)ij，在每一轮更新中任取一个样本点(xn,yn)（步骤1）。计算梯度 x(l−1)iδ(l)j 并且更新（步骤4）。要完成步骤4，就需要知道所有的 x(l−1)i 和所有的 δ(l)j ，其中所有的 x(l−1)i 通过前向传播（步骤2）得到； 所有的δ(l)j通过反向传播（步骤3）得到。

考虑上面的过程我们发现，由于使用的是随机梯度下降算法， 对于仅仅一个样本点， 我们就要计算进行一次前向传播得到所有的 x(l−1)i， 完了之后进行一次反向传播得到所有的 δ(l)j ， 计算完了之后也只能向着梯度下降的方向走一点， 并且还有可能走向的是局部最优解。所以为了解决这样的问题，通常使用的方法是mini-batch SGD，这种方法介于SGD和GD之间。一种做法是， 每次不再只是选取一个样本点， 而是选取多个，并行的计算这些样本点各自的x(l−1)i和δ(l)j，最后沿着所有这些点的梯度方向进行参数w(l)ij的更新。

考虑一个问题：
根据以上的计算可以得到∂en∂w(L)i1=−2(yn−s(L)1)⋅(x(L−1)i)， 当什么时候∂en∂w(L)i1=0呢？

• yn=s(L)1
• x(L−1)i=0
• s(L−1)i=0

Optimization and Regularization

Neural network optimization

上一小节介绍了训练一个神经网络的基本方法，即通过GD类的算法来最小化Ein。需要注意的是， 由于包含了很多层的转换tanh，所以最终的目标函数很有可能不是w的凸函数，也就是说这些函数是non-convex的，有多个局部最优值。这样使用上一小节中给出的梯度下降的方法就会最终找到local minimum，而不一定是global minimum。
实际应用中我们通常使用一些技巧来得到比较好的结果， 例如，如果在初始化的时候将权重设置的过大，那么tanh(∑wx)的偏导就会很小，这样导致权重的更新会非常的缓慢，所以通常会初始化一些比较小的， 并且是随机的权重。 通过在不同的初始权重下进行更新，可能会得到不同的local minimum，这样可能会得到不错的结果。

Regularization for neural network

有理论证明在使用tanh作为神经网络的**函数时， 该模型的dvc=O(VD)，其中V表示神经元的数量，D表示权重的数量。这表明可以通过增加神经元的个数来增强模型的复杂度，当然这样就有可能会 overfitting。为了避免过拟合通常我们使用的方法是添加正则化项。例如可以在目标函数中添加L2 regularizer Ω(w)=∑(w(l)ij)2。但是这样的正则化项的一个缺点是会等比的将原始的权重缩小。我们希望得到一些w=0，虽然L1 regularizer ∑|w(l)ij|可以做到， 但是却难以微分导致无法最优化。所以通常在神经网络中使用的是weight elimination regularizer(scaled L2)：∑(w(l)ij)2((w(l)ij)2+1，通过这样的正则化项，可以得到比较稀疏的权重。为什么呢？

除了weight elimination regularizer之外， 在神经网络中还有另一个经常使用的用于regularization的机制：early stopping。简单的说，通过提前终止权重的更新，可以减少w的搜索范围从而做到降低模型的复杂度。提前终止这样的机制可以通用于所有使用梯度的方法中来做regularization， 至于要在何时停止，即更新多少步，那么可以使用validation的机制来进行确定。

Other

• https://gormanalysis.com/introduction-to-neural-networks/
• https://gormanalysis.com/