神经网络算法初识

感知机算法

1. 概述

感知机由两层神经元组成，输入层接收外界输入信号后传递给输出层，输出层是M-P神经元，亦称“阈值逻辑单元”（threshold logic unit）。其学习能力非常有限，若二分类数据集线性可分，即存在一个线性超平面能将它们分开，则感知机的学习过程一定会收敛而求得适当的权向量；否则感知机学习过程会发生振荡， $\omega$ 难以稳定下来。
要解决非线性可分问题，需考虑使用多层功能神经元，即在输出层和输入层之间加入隐藏层，隐藏层和输出层神经元都是拥有激活函数的功能神经元。
感知机（perceptron）是二分类的线性分类模型，旨在求出将训练数据进行线性划分的分离超平面，导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。感知机模型包含两种形式：原始形式和对偶形式。

2. 感知机模型

假设输入空间（特征空间） $\chi \subseteq R^n$ ，输出空间是 $\gamma = \{ -1,+1\}$ 。由输入空间到输出空间的如下函数：
$f(x) = sign(\omega \cdot x + b)$ 其中， $x \in \chi, y \in \gamma$ ， $\omega \in R^n$ 表示权值（weight）或权值向量（weight vector）， $b \in R$ 叫做偏置（bias），而 $\omega \cdot x$ 表示 $\omega$ 和 $x$ 的内积。 $sign$ 是符号函数，即
$sign(x) = \begin{cases} +1, \quad x \geq 0 \\ -1, \quad x < 0 \end{cases}$

3. 感知机学习策略

假设训练样本数据集是线性可分的，感知机学习的目标是得到一个能够将训练集正负实例点正确分开的分离超平面。为了找到这样的超平面，即确定感知机模型参数 $\omega,b$ ，需要确定一个学习策略，即定义并极小化损失函数。
损失函数采用误分类点到超平面的总距离，为此，写出输入空间 $R^n$ 中任一点 $x_0$ 到超平面 $S$ 的距离 $\frac {1} {\parallel \omega \parallel} \mid \omega \cdot x_0 + b \mid$ ， $\parallel \omega \parallel$ 是 $\omega$ 的 $L_2$ 范数。
给定训练数据集

$T = \{(x_1,y_1), (x_2,y_2), \cdots, (x_N,x_N)\}$ 其中， $x_i \in \chi \subseteq R^n, y_i \in \gamma = \{ +1, -1 \}$ 。则感知机 $sign(\omega \cdot x + b)$ 学习的损失函数定义为
$L(\omega, b) = - \sum_{x_i \in M} y_i (\omega \cdot x_i + b)$ 其中 $M$ 为误分类点的集合。这个损失函数就是感知机学习的经验风险函数。

4. 感知机学习算法

4.1. 感知机学习算法的原始形式

输入：训练数据 $T = \{ (x_1,y_1), (x_2,y_2), \cdots, (x_N,y_N) \}$ ，其中 $x_i \in \chi = R^n$ ， $y_i \in \gamma = \{ -1, +1 \}$ ， $i = 1, 2, \cdots, N$ ；学习率 $\eta (0 < \eta \leq 1)$ ；
输出： $\omega, b$ ；感知机模型 $f(x) = sign(\omega x + b)$

选取初值 $\omega_0, b_0$
在训练集中选取数据 $(x_i, y_i)$
如果 $y_i (\omega x_i + b) \leq 0$
$\begin{aligned} \omega \leftarrow \omega + \eta y_i x_i \\ b \leftarrow b + \eta y_i \end{aligned}$
转到第二步，直至训练集中没有误分类点

这种学习算法直观上的解释：当一个实例点被误分类，即位于错误的一侧时，则调整 $\omega,b$ 的值，使分离超平面向该误分类点的一侧移动，以减少误分类点和超平面的距离，直至超平面越过该误分类点使其被正确分类。

4.2. 感知机学习算法的对偶形式

输入：线性可分的数据集 $T = \{ (x_1,y_1), (x_2,y_2), \cdots, (x_N,y_N) \}$ ，其中 $x_i \in \chi = R^n$ ， $y_i \in \gamma = \{ -1, +1 \}$ ， $i = 1, 2, \cdots, N$ ；学习率 $\eta (0 < \eta \leq 1)$ ；
输出： $a,b$ ；感知机模型 $f(x) = sign (\sum_{j=1}^N \alpha_j y_j x_j \cdot x +b)$ ，其中 $\alpha = (\alpha_1, \alpha_2, \cdots, \alpha_N)^T$

$\alpha \leftarrow 0, b \leftarrow 0$
在训练集中选取数据 $(x_i, y_i)$
如果 $y_i (\sum_{j=1}^N \alpha_j y_j x_j \cdot x_i + b) \leq 0$
$\begin{cases} \alpha_i \leftarrow \alpha_i + \eta \\ b \leftarrow + \eta y_i \end{cases}$
转至步骤2，直到没有误分类数据

BP神经网络

1. 概述

神经网络主要由三部分组成：网络架构；激活函数；参数学习算法；误差逆传播算法（error BackPropagation, BP）是一种使用较为广泛的参数学习算法。算法基本思想：学习过程由信号的正向传播与误差的反向传播两个过程组成。

正向传播时，训练样本从输入层传入，经隐藏层逐层处理后，传到输出层。若输出层的实际输出与期望的输出不符，则转入误差的反向传播阶段。
反向传播时，将输出以某种形式通过隐藏层向输入层逐层反传，并将误差分摊给各层的所有单元，从而获得各层单元的误差信号，该误差信号作为修正各单元权值的依据。

BP神经网络采用BP算法带来的问题：基于局部梯度下架调整权值时容易出现梯度弥散（Gradient Diffusion）现象，根源在于非凸目标代价函数导致求解陷入局部最优。并且，随着网络层数的增加，这种情况会愈发严重。

2. 算法介绍

给定训练集 $D = \{ (x_1,y_1), (x_2, y_2), \cdots, (x_m, y_m) \}, x_i \in R^d, y_i \in R^l$ ，即输入示例由 $d$ 个属性描述，输出 $l$ 维实值向量。给出一个拥有 $d$ 个输入神经元、 $l$ 个输出神经元、 $q$ 个隐藏神经元的多层前馈网络结构。其中 $\theta_j$ 表示输出层第 $j$ 个神经元的阈值， $\gamma_h$ 表示隐藏层第 $h$ 个神经元的阈值； $v_{ih}$ 表示输入层第 $i$ 个神经元与隐藏层第 $h$ 个神经元之间的连接权， $\omega_{hj}$ 表示隐藏层第 $h$ 个神经元与输出层第 $j$ 个神经元之间的连接权。于是隐藏层第 $h$ 个神经元的输入为 $\alpha_h = \sum_{i=1}^d v_{ih} x_i$ ；输出层第 $j$ 个神经元的输入为 $\beta_j = \sum_{h=1}^q \omega_{hj} b_h$ ，其中 $b_h$ 为隐藏层第 $h$ 个神经元的输出。
对于训练样本 $(x_k, y_k)$ ，神经网络的输出为 $\hat {y}_k = (\hat {y}_1^k, \hat {y}_2^k, \cdots, \hat {y}_l^k)$ ，即
$\hat {y}_j^k = f(\beta_j - \theta_j)$ 则网络在 $(x_k, y_k)$ 上的均方误差为
$E_k = \frac {1} {2} \sum_{j=1}^l (\hat {y}_j^k - y_j^k)^2$ BP算法基于梯度下降（gradient descent）策略，以目标的负梯度方向对参数进行调整。对于误差 $E_k$ ，给定学习率 $\eta$ ，有
$\begin{aligned} \Delta \omega_{hj} &= - \eta \frac {\partial E_k} {\partial \omega_{hj}} \\ &= \frac {\partial E_k} {\partial \hat {y}_j^k} \cdot \frac {\partial \hat {y}_j^k} {\partial \beta_j} \cdot \frac {\partial \beta_j} {\partial \omega_{hj}} \end{aligned}$ 根据 $\beta_j$ j的定义，显然有
$\frac {\partial \beta_j} {\partial \omega_{hj}} = b_h$ 此外Sigmoid函数有一个很好的性质：
$f^{'} (x) = f(x) (1 - f(x))$ 于是，有
$\begin{aligned} g_j &= - \frac {\partial E_k} {\partial \hat {y}_j^k} \cdot \frac {\partial \hat {y}_j^k} {\partial \beta_j} \\ &= - (\hat {y}_j^k - y_j^k) f^{'}(\beta_j - \theta_j) \\ &= \hat {y}_j^k (1 - \hat {y}_j^k) (y_j^k - \hat {y}_j^k) \end{aligned}$ 于是，得到更新公式
$\begin{aligned} \Delta \omega_{hj} &= \eta g_j b_h \\ \Delta \theta_j &= - \eta g_j \\ \Delta v_{ih} &= \eta e_h x_i \\ \Delta \gamma_h &= - \eta e_h \end{aligned}$ 其中
$\begin{aligned} e_h &= - \frac {\partial E_k} {\partial b_h} \cdot \frac {\partial b_h} {\partial \alpha_h} \\ &= - \sum_{j=1}^l \frac {\partial E_k} {\partial \beta_j} \cdot \frac {\partial \beta_j} {\partial b_h} f^{'} (\alpha_h - \gamma_h) \\ &= \sum_{j=1}^l \omega_{hj} g_j f^{'} (\alpha_h - \gamma_h) \\ &= b_h (1 - b_h) \sum_{j=1}^l \omega_{hj} g_j \end{aligned}$

2.1. 误差逆传播算法

输入：训练集 $D = \{ (x_k, y_k) \}_{k=1}^m$ ；学习率 $\eta$
输出：连接权与阈值确定的多层前馈神经网络
过程：

在 $(0,1)$ 范围内随机初始化网络中所有连接权和阈值
repeat
for all $(x_k, y_k) \in D$ do
根据当前参数和式 $\hat {y}_j^k = f(\beta_j - \theta_j)$ 计算当前样本的输出 $\hat {y}_k$ ；
根据式 $g_j = \hat {y}_j^k (1 - \hat {y}_j^k) (y_j^k - \hat {y}_j^k)$ 计算输出层神经元的梯度项 $g_j$ ；
根据式 $e_h = b_h (1 - b_h) \sum_{j=1}^l \omega_{hj} g_j$ 计算隐藏神经元的梯度项 $e_h$ ；
根据下式更新连接权 $\omega_{hj}, v_{ih}$ 与阈值 $\theta_j, \gamma_h$
$\begin{cases} \Delta \omega_{hj} = \eta g_j b_h \\ \Delta \theta_j = - \eta g_j \\ \Delta v_{ih} = \eta e_h x_i \\ \Delta \gamma_h = - \eta e_h \end{cases}$
end for
until 达到停止条件