神经网络

感知器融合

图 1: 感知器的线性融合 [PNG]

上图展示了感知器的线性融合结构，其中包含两层的权重$\mathbf w_t$和$\boldsymbol\alpha$，还包含两层的符号函数（sign function）$g_t$和$G$。这样的融合可以表示什么样的分类边界呢？

图 2: AND和XOR运算 [PNG]

单层感知器可以实现如上图所示的AND运算（+1表示TRUE，-1表示FALSE） \[ G(\mathbf x)=\mbox{sign}(-1+g_1(\mathbf x)+g_2(\mathbf x))， \] 也可实现OR和NOT运算。

图 3: 足够多感知器的融合 [PNG]

即使感知器的线性组合，分类能力也很强大，如上图所示。只要对足够多的感知器融合，可以在空间中切割出任意凸集（convex set），但$d_{VC}\rightarrow\infty$。

图 4: 两层感知器的线性融合实现XOR运算 [PNG]

但是，单层感知器不能实现XOR运算，经过XOR运算的特征转换$\phi(\mathbf x)=(g_1(\mathbf x),g_2(\mathbf x))$后数据线性不可分。线性不可分数据继续特征转换，最终将XOR用AND和OR实现 \[ XOR(g_1,g_2)=OR(AND(-g_1,g_2),AND(g_1,-g_2))， \] 并且可以用上图所示的两层级连结构表示¹。

由此可见，虽然感知器算法简单，经过线性融合，以及多层级连，可以得到功能强大的分类器。多层感知器就是基本的神经网络结构。

神经网络

图 5: 简单的神经网络模型 [PNG]

事实上，对最后一层OUTPUT神经元，除了用感知器外，可以采用其它的线性模型。若要分类，OUTPUT采用线性分类模型；若要回归分析，OUTPUT采用线性回归（不做任何处理）；若要soft分类，OUTPUT采用logistic回归。

中间层神经元采用的转换函数（transformation function），除了使用阶梯（符号）函数，也可采用其它转换函数。若所有神经元都采用线性回归，整个网络都是线性运算，用一个线性模型就可以实现。因此，很少用线性回归作为转换函数。阶梯函数是离散的，难以通过最优化求解$\mathbf w$，也很少使用。通常使用的是S形的转换函数 \[ \tanh(s)={\exp(s)-\exp(-s)\over\exp(s)+\exp(-s)}=2\theta(2s)-1， \] 可以通过logistic函数得到。该函数是阶梯函数的近似，且容易优化，传说和生物神经元也相近。

图 6: 常用的神经网络模型 [PNG]

常用的神经网络采用$\tanh$作为转换函数，输出采用线性回归，如上图所示。$d^{(0)},d^{(1)},\ldots,d^{(L)}$表示每层神经元数目（节点数目），每层的权值为 \[ w_{ij}^{(\ell)}:\left\{ \begin{aligned} &1\leq\ell\leq L&\mbox{layers}&\\ &0\leq i\leq d^{(\ell-1)}&\mbox{inputs}&\\ &1\leq j\leq d^{(\ell)}&\mbox{outputs}&， \end{aligned} \right. \] 常数+1的神经元相当于偏移项，评分函数为 \begin{equation} s_j^{(\ell)}=\sum_{i=0}^{d^{(\ell-1)}}w_{ij}^{(\ell)}x_i^{(\ell-1)}， \end{equation} 转换后的特征为 \begin{equation} x_j^{(\ell)}=\left\{ \begin{aligned} &\tanh\left(s_j^{(\ell)}\right)&\mbox{if }\ell<L\\ &s_j^{(\ell)}&\mbox{if }\ell=L \end{aligned} \right. \label{eq:forward-x} \end{equation}

神经网络将$\mathbf x$当作输入层$\mathbf x^{(0)}$，隐层计算变换后的特征$\mathbf x^{(\ell)}$，输出层计算预测结果$x_1^{(L)}$。

神经网络隐层相当于模式（特征）提取（pattern extraction），进行$\mathbf x^{(\ell)}$和权值向量的模式匹配（利用基于内积的余弦相似度），每个神经元提取一种特征，权值向量纪录了从数据中学到的模式。

BP算法

如何通过最小化$E_{in}\left(\left\{w_{ij}^{(\ell)}\right\}\right)$学到权值$\left\{w_{ij}^{(\ell)}\right\}$？

如果只有一个隐层，神经网络相当于感知器的融合，可以通过GradientBoost方法一个接一个的确定隐层的神经元。如果有多个隐层，问题就变得复杂了。

每个数据的误差记为 \[ e_n=(y_n-\mbox{NNet}(\mathbf x_n))^2， \] 若能计算$\partial e_n\over \partial w_{ij}^{(\ell)}$，就可以通过梯度下降法求解。对输出层 \[ e_n=\left(y_n-s_1^{(L)}\right)^2=\left(y_n-\sum_{i=0}^{d^{(L-1)}}w_{i1}^{(L)}x_i^{(L-1)}\right)^2， \] 对输出层和其它层分别求偏微分 \[ \begin{aligned} &{\partial e_n\over\partial w_{i1}^{(L)}} ={\partial e_n\over\partial s_{1}^{(L)}}\cdot{\partial s_{1}^{(L)}\over\partial w_{i1}^{(L)}} =-2\left(y_n-s_1^{(L)}\right)\cdot x_i^{(L-1)}，\\ &{\partial e_n\over\partial w_{ij}^{(\ell)}} ={\partial e_n\over\partial s_{j}^{(\ell)}}\cdot{\partial s_{j}^{(\ell)}\over\partial w_{ij}^{(\ell)}} =x_i^{(\ell-1)}\delta_j^{(\ell)}。 \end{aligned} \] 对输出层，令² \begin{equation} \delta_1^{(L)}=-2\left(y_n-s_1^{(L)}\right)。 \label{eq:backpropagation-delta-L} \end{equation} 对其它层 \begin{equation} \delta_j^{(\ell)} ={\partial e_n\over\partial s_{j}^{(\ell)}} =\sum_{k=1}^{d^{(\ell+1)}}{\partial e_n\over\partial s_{k}^{(\ell+1)}}{\partial s_{k}^{(\ell+1)}\over\partial x_{j}^{(\ell)}}{\partial x_{j}^{(\ell)}\over\partial s_{j}^{(\ell)}} =\tanh’\left(s_j^{(\ell)}\right)\sum_{k=1}^{d^{(\ell+1)}}\delta_k^{(\ell+1)}w_{jk}^{(\ell+1)}， \label{eq:backpropagation-delta2} \end{equation} 也就是前一层的$\delta_j^{(\ell)}$，可以通过后一层$\delta_k^{(\ell+1)}$回推计算，其中 \[ \tanh’(s)=1-\tanh^2(s)=\left({2\over \exp(s) + \exp(-s)}\right)^2， \] 那么 \begin{equation} \delta_j^{(\ell)} =\left(1-\left(x_j^{(\ell)}\right)^2\right)\sum_{k=1}^{d^{(\ell+1)}}\delta_k^{(\ell+1)}w_{jk}^{(\ell+1)},\quad(j\geq 1)。 \label{eq:backpropagation-delta} \end{equation}

####BP（backpropagation）算法

用小的随机值初始化所有的$w_{ij}^{(\ell)}$；

对于$t=1,2,\ldots,T$，循环执行：

1. 随机化：随机选取$n\in\{1,2,\ldots,N\}$；
2. 前向传播：从$\mathbf x^{(0)}=\mathbf x_n$开始，利用\eqref{eq:forward-x}计算所有$x_i^{(\ell)}$；
3. 误差回传：对$\mathbf x^{(0)}=\mathbf x_n$，利用\eqref{eq:backpropagation-delta-L}和\eqref{eq:backpropagation-delta}计算所有$\delta_j^{(\ell)}$；
4. 梯度下降：$w_{ij}^{(\ell)}\leftarrow w_{ij}^{(\ell)}-\eta x_i^{(\ell-1)}\delta_j^{(\ell)}$；

返回$g_{\mbox{NNET}}(\mathbf x)=\left(\ldots\tanh\left(\sum_jw_{jk}^{(2)}\cdot\tanh\left(\sum_iw_{ij}^{(1)}x_i\right)\right)\right)$。

在实际应用中，第1步至第3步可以先执行多次后，再用$x_i^{(\ell-1)}\delta_j^{(\ell)}$的平均值执行第4步的更新，这就是mini-batch的方法。

神经网络通过最小化 \[ E_{in}(\mathbf w)={1\over N}\sum_{n=1}^Nerr\left(\left(\ldots\tanh\left(\sum_jw_{jk}^{(2)}\cdot\tanh\left(\sum_iw_{ij}^{(1)}x_i\right)\right)\right),y_n\right) \] 计算权值。通常多隐层神经网络的误差函数是非凸的（non-convex），难以达到全局最小值（global minimum），梯度下降法通过BP算法也仅仅得到局部极小值（local minimum）。不同的初始化$w_{ij}^{(\ell)}$，会得到不同的局部极值：

• BP算法对权重初始值敏感；
• 若权值太大，会落到$\tanh$的saturate区域（梯度很小），每次按梯度更新很小；
• 用小的随机值初始化权值$w_{ij}^{(\ell)}$。

若初始化$w_{ij}^{(\ell)}＝0$，由于$x_0^{(\ell)}=1$，除了${\partial e_n\over \partial w_{01}^{(L)}}\neq 0$外，其它的导数都为0；若初始化$w_{ij}^{(\ell)}＝1$，那么$w_{ij}^{(1)}=w_{i(j+1)}^{(1)}$。因此，$w_{ij}^{(\ell)}$不能初始化为0和1。

虽然神经网络很难最优化，但在实际中很有用。

正则化

若用形如$\tanh$的转换函数，神经网络的$d_{VC}=O(VD)$，$V$为神经元数量，$D$为神经元之间的权值数量。当神经元数目足够时，可以做任意逼近，也更容易导致过拟合。为了避免过拟合，需要采取正则化方法。

一、weight-elimination正则化

常用的方法是基于$L_2$的weight-decay正则化，$\Omega(\mathbf w)=\sum\left(w_{ij}^{(\ell)}\right)^2$。这种正则化对权值的压缩（shrink）力度和权值大小“成比例”，大的权值压缩厉害，小的权值压缩较小。

如果通过正则化使权值部分为0（稀疏），就能有效减小$d_{VC}$，常用的方法是$L_1$正则化，$\Omega(\mathbf w)=\sum\left\lvert w_{ij}^{(\ell)}\right\rvert$，但是不可微。采用weight-elimination正则化（放缩的$L_2$正则化），大的权值中等幅度的压缩（median shrink），小的权值也中等幅度的压缩，小的权值就会接近0，具有权值稀疏化的效果。weight-elimination正则化采用 \begin{equation} \Omega(\mathbf w)=\sum{\left(w_{ij}^{(\ell)}\right)^2\over 1+\left(w_{ij}^{(\ell)}\right)^2}， \end{equation} 那么 \[ {\partial\Omega(\mathbf w)\over \partial w_{ij}^{(\ell)}} ={2w_{ij}^{(\ell)}\over\left(1+\left(w_{ij}^{(\ell)}\right)^2\right)^2}。 \]

二、尽早停止迭代

图 7: 迭代次数对误差的影响 [PNG]

迭代的次数$t$越多，选择过的$\mathbf w$也就越多，有效的$d_{VC}$也越大。小的$t$使得$d_{VC}$也较小。尽早停止（early stopping）迭代，通过如上图右的最佳$t^*$，获得如上图左的最佳$d_{VC}^*$，克服过拟合。通过验证（validation）确定停止迭代的参数$t$。

所有和梯度有关的优化算法，都可利用尽早停止迭代的机制，实现某种正则化。

程序示例

nnet_train <- function(X, Y, struct, r, eta, TT) {
  # X -- a matrix with each feature row 
  # Y -- a matrix 
  # struct -- a vector with neuron number of each layer, including the input layer
  # r -- initialization range
  # eta -- learning rate
  # TT -- iteration times
  
  X <- cbind(1, X)
  num_data <- nrow(X)
  num_layer <- length(struct) 
  nnetwork <- Xs <- Deltas <- list()
  
  # initialization
  for (i in 1 : (num_layer - 1)) {
    nnetwork[[i]] <- matrix(runif((struct[i] + 1) * struct[i + 1], -r, r),
                            struct[i] + 1, struct[i + 1])
  }
  
  for (t in 1 : TT) {
    n <- sample(1:num_data, 1)
    
    # forward
    Xs[[1]] <- t(X[n,,drop = F])
    for (i in 2 : num_layer) {
      xx <- tanh(t(t(Xs[[i - 1]]) %*% nnetwork[[i - 1]]))
      ifelse(i != num_layer, Xs[[i]] <- rbind(1, xx), Xs[[i]] <- xx)
    }
    
    # backward
    for (i in num_layer : 2) {
      ifelse(i == num_layer,
             Deltas[[i]] <- 
               -2 * (t(Y[n,,drop=F]) - Xs[[i]]) * (1 - Xs[[i]] ^ 2),
             Deltas[[i]] <- 
               ((nnetwork[[i]] %*% Deltas[[i + 1]]) *
                  (1 - Xs[[i]] ^ 2))[2:nrow(nnetwork[[i]]),,drop=F])
    }
    
    # update weight
    for (i in 1 : (num_layer - 1)) {
      nnetwork[[i]] <- nnetwork[[i]] - eta * Xs[[i]] %*% t(Deltas[[i + 1]])
    }
    
  }
  return(nnetwork)
}

参考资料

脚注