神经网络/04. 反向传播算法.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在上一节中，我们构造了三个两层神经网络来解决 AND、OR、NOT 问题，并构造了一个三层神经网络来解决 XOR 问题，那么这些神经网络结构是如何构造出来的呢？神经元之间的权重和每个神经元的阈值又是如何确定的呢？如果是线性可分问题，两层神经网络就可以解决，这也就是感知机模型，通过前面学习的随机梯度下降法来训练感知机即可求解，如果是线性不可分问题，需要构造更复杂的多层网络结构，通常使用 **反向传播算法**（error BackPropagation，简称 **BP 算法**，也叫做 **误差逆传播算法**）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 神经网络的符号表示\n",
    "\n",
    "假设我们要求解的神经网络如下图所示：\n",
    "\n",
    "<img src=\"../images/bp-method.png\" width=\"800px\" />\n",
    "\n",
    "该神经网络的特点如下：\n",
    "\n",
    "* 输入层有 $d$ 个节点，表示输入的特征向量为 $d$ 维\n",
    "* 输出层有 $l$ 个节点，表示输出向量为 $l$ 维，也就是 $l$ 类分类问题，$l = 2$ 时就是二分类问题\n",
    "* 隐层有 $q$ 个节点\n",
    "* 第 $i$ 个输入层神经元和第 $h$ 个隐层神经元之间的连接权重为 $v_{ih}$\n",
    "* 第 $h$ 个隐层神经元的阈值为 $\\gamma_h$\n",
    "* 第 $h$ 个隐层神经元和第 $j$ 个输出层神经元之间的连接权重为 $w_{hj}$\n",
    "* 第 $j$ 个输出层神经元的阈值为 $\\theta_j$\n",
    "\n",
    "所以有，第 $h$ 个隐层神经元接受到的输入为：\n",
    "\n",
    "$$\n",
    "\\alpha_h = v_{1h}x_1 + v_{2h}x_2 + \\dots + v_{dh}x_d = \\sum_{i=1}^d v_{ih}x_i\n",
    "$$\n",
    "\n",
    "它的输出为：\n",
    "\n",
    "$$\n",
    "b_h = f(\\alpha_h - \\gamma_h)\n",
    "$$\n",
    "\n",
    "这里的 $f(z)$ 表示激活函数，譬如 Sigmoid 函数。最后得到，第 $j$ 个输出层神经元的输入为：\n",
    "\n",
    "$$\n",
    "\\beta_j = w_{1j}b_1 + w_{2j}b_2 + \\dots + w_{qj}b_q = \\sum_{h=1}^q w_{hj}b_h\n",
    "$$\n",
    "\n",
    "它的输出为：\n",
    "\n",
    "$$\n",
    "y_j = f(\\beta_j - \\theta_j)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 神经网络的损失函数\n",
    "\n",
    "从上面的计算过程中可以看出，这里一共有 $dq + lq + q + l$ 个参数：输入层到隐层的 $dq$ 个权值，隐层到输出层的 $lq$ 个权值，$q$ 个隐层神经元的阈值，$l$ 个输出层神经元的阈值。要求解这些参数，一个很容易想到的方法是使用梯度下降法，首先定义神经网络的损失函数，然后给每个参数一个初始值，再根据损失函数的梯度对初始值迭代更新，最终收敛。那么神经网络的损失函数该如何定义呢？\n",
    "\n",
    "假设对于输入样本 $\\bf{x}_k$ 我们有输出 $\\hat{\\bf{y}}_k = (\\hat{y}_1^k, \\hat{y}_2^k, \\dots, \\hat{y}_l^k)$，和线性回归一样，我们可以得到预测值和真实值的平方误差：\n",
    "\n",
    "$$\n",
    "E_k = \\frac{1}{2} \\sum_{j=1}^l (\\hat{y}_j^k - y_j^k)^2\n",
    "$$\n",
    "\n",
    "很显然，我们可以把这个函数当作神经网络的损失函数，我们的目标就是让它的值最小。不过要注意的是，这里的损失函数是定义在某一个样本上的，也就是说每次仅针对一个训练样本更新连接权值和阈值，这种方法叫做 **标准BP算法**。如果我们把损失函数定义成所有样本损失的平均值的话：\n",
    "\n",
    "$$\n",
    "E = \\frac{1}{m} \\sum_{k=1}^m E_k\n",
    "$$\n",
    "\n",
    "这就是 **累积BP算法**。这有点类似于随机梯度下降和标准梯度下降。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### BP算法的推导\n",
    "\n",
    "在BP算法中，最重要的就是如何计算各个参数对损失函数的梯度，待确定的参数虽然很多，但是我们可以把它分成四种类型，同一种类型的参数计算方法是一样的，这四种类型分别为：输入层到隐层的权值 $v_{ih}$，隐层到输出层权值 $w_{hj}$，隐层神经元的阈值 $\\gamma_h$，输出层神经元的阈值 $\\theta_j$。所以要分别计算下面四个梯度：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\nabla v_{ih} &= -\\eta \\frac{\\partial E_k}{\\partial v_{ih}} \\\\\n",
    "\\nabla w_{hj} &= -\\eta \\frac{\\partial E_k}{\\partial w_{hj}} \\\\\n",
    "\\nabla \\gamma_{h} &= -\\eta \\frac{\\partial E_k}{\\partial \\gamma_{h}} \\\\\n",
    "\\nabla \\theta_{j} &= -\\eta \\frac{\\partial E_k}{\\partial \\theta_{j}} \\\\\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "我们先来看 $\\frac{\\partial E_k}{\\partial \\theta_{j}}$，这是输出层神经元的阈值的梯度，直接对 $E_k$ 求导是不行的，因为 $E_k$ 并不是 $\\theta_j$ 的函数，但是我们发现 $E_k$ 是 $y_j$ 的函数，而 $y_j$ 又是 $\\theta$ 的函数，所以可以使用求导的链式法则:\n",
    "\n",
    "$$\n",
    "\\frac{\\partial E_k}{\\partial \\theta_{j}} = \\frac{\\partial E_k}{\\partial y_j} \\frac{\\partial y_j}{\\partial \\theta_{j}}\n",
    "$$\n",
    "\n",
    "其中，$y_j$ 是 Sigmoid 函数，它具有如下性质：\n",
    "\n",
    "$$\n",
    "f'(x) = f(x)(1-f(x))\n",
    "$$\n",
    "\n",
    "所以：\n",
    "\n",
    "$$\n",
    "\\frac{\\partial y_j}{\\partial \\theta_{j}} = -y_j(1-y_j)\n",
    "$$\n",
    "\n",
    "另外，很容易求得：\n",
    "\n",
    "$$\n",
    "\\frac{\\partial E_k}{\\partial y_j} = \\hat{y}_j-y_j\n",
    "$$\n",
    "\n",
    "所以有：\n",
    "\n",
    "$$\n",
    "\\frac{\\partial E_k}{\\partial \\theta_{j}} = -y_j(1-y_j)(\\hat{y}_j-y_j)\n",
    "$$\n",
    "\n",
    "然后再来计算 $\\frac{\\partial E_k}{\\partial w_{hj}}$，同样，根据链式法则：\n",
    "\n",
    "$$\n",
    "\\frac{\\partial E_k}{\\partial w_{hj}} = \\frac{\\partial E_k}{\\partial y_j} \\frac{\\partial y_j}{\\partial \\beta_j} \\frac{\\partial \\beta_j}{\\partial w_{hj}}\n",
    "$$\n",
    "\n",
    "其中，\n",
    "\n",
    "$$\n",
    "\\frac{\\partial \\beta_j}{\\partial w_{hj}} = b_h\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial E_k}{\\partial y_j} \\frac{\\partial y_j}{\\partial \\beta_j} = \\frac{\\partial E_k}{\\partial \\beta_j} = -\\frac{\\partial E_k}{\\partial \\theta_j} = y_j(1-y_j)(\\hat{y}_j-y_j)\n",
    "$$\n",
    "\n",
    "所以有：\n",
    "\n",
    "$$\n",
    "\\frac{\\partial E_k}{\\partial w_{hj}} = y_j(1-y_j)(\\hat{y}_j-y_j) b_h\n",
    "$$\n",
    "\n",
    "然后再来计算 $\\frac{\\partial E_k}{\\partial \\gamma_{h}}$：\n",
    "\n",
    "$$\n",
    "\\frac{\\partial E_k}{\\partial \\gamma_{h}} = \\frac{\\partial E_k}{\\partial b_h} \\frac{\\partial b_h}{\\partial \\gamma_{h}}\n",
    "$$\n",
    "\n",
    "$b_h$ 是 Sigmoid 函数，有：\n",
    "\n",
    "$$\n",
    "\\frac{\\partial b_h}{\\partial \\gamma_{h}} = -b_h(1-b_h)\n",
    "$$\n",
    "\n",
    "这里要注意的是 $\\frac{\\partial E_k}{\\partial b_h}$ 的求导，$b_h$ 和输出层之间有 $l$ 条连线，所以要求和：\n",
    "\n",
    "$$\n",
    "\\frac{\\partial E_k}{\\partial b_h} = \\sum_{j=1}^l \\frac{\\partial E_k}{\\partial y_j} \\frac{\\partial y_j}{\\partial \\beta_j} \\frac{\\partial \\beta_j}{\\partial b_h}\n",
    "$$\n",
    "\n",
    "其中 $\\frac{\\partial E_k}{\\partial y_j} \\frac{\\partial y_j}{\\partial \\beta_j}$ 在上面计算过，不妨令其为 $g_j$，另外：\n",
    "\n",
    "$$\n",
    "\\frac{\\partial \\beta_j}{\\partial b_h} = w_{hj}\n",
    "$$\n",
    "\n",
    "所以：\n",
    "\n",
    "$$\n",
    "\\frac{\\partial E_k}{\\partial b_h} = \\sum_{j=1}^l g_j w_{hj}\n",
    "$$\n",
    "\n",
    "于是就得到了：\n",
    "\n",
    "$$\n",
    "\\frac{\\partial E_k}{\\partial \\gamma_{h}} = -b_h(1-b_h) \\sum_{j=1}^l g_j w_{hj}\n",
    "$$\n",
    "\n",
    "最后我们计算 $\\frac{\\partial E_k}{\\partial v_{ih}}$：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\frac{\\partial E_k}{\\partial v_{ih}} &= \\frac{\\partial E_k}{\\partial b_h} \\frac{\\partial b_h}{\\partial \\alpha_h} \\frac{\\partial \\alpha_h}{\\partial v_{ih}} \\\\\n",
    "&= \\frac{\\partial E_k}{\\partial b_h} b_h(1-b_h) x_i \\\\\n",
    "&= b_h(1-b_h) x_i \\sum_{j=1}^l g_j w_{hj}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "这样就得到了所有参数的梯度更新公式，从而使用梯度下降算法不断迭代，直到收敛，得到各个参数的值。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 过拟合\n",
    "\n",
    "在上面我们学习了如何使用 BP 算法求解神经网络中的各个参数，不过有一点要注意，这个神经网络的隐层有 $q$ 个神经元，可以证明，只需要隐层包含足够多的神经元，神经网络就可以以任意精度逼近任意复杂度的连续函数。那么这个 $q$ 该如何选取呢？遗憾的是，一般没什么好的办法，实际运用中都是靠不断的试错来选一个比较靠谱的 $q$。\n",
    "\n",
    "正是由于神经网络的表示能力太强大，神经网络经常会遭遇过拟合问题。有两种方法来缓解过拟合：\n",
    "\n",
    "* **早停**（early stopping）：将数据分为训练集和验证集，训练集用来计算梯度、更新权重和阈值，验证集用来估计误差，若训练集误差降低但验证集误差升高，则停止训练，同时返回具有最小验证集误差的权重和阈值。\n",
    "* **正则化**（regularization）：在损失函数中增加一个用于描述网络复杂度的部分，例如权重和阈值的平方和，于是损失函数就变成这样：\n",
    "\n",
    "$$\n",
    "E = \\lambda \\frac{1}{m} \\sum_{k=1}^m E_k + (1-\\lambda) \\sum_i w_i^2\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 全局最小和局部极小\n",
    "\n",
    "根据梯度下降法求解出来的参数值可以使得当前点的梯度为零，这时我们得到的解是局部极小解，如果损失函数只有一个局部极小，那么这个解也是全局最小解，但是现实任务中，损失函数通常具有多个局部极小，不能保证我们得到的解是全局最小的，我们要想办法避免参数寻优陷入局部极小。通常使用下面几种方法：\n",
    "\n",
    "* 以多组不同参数值初始化神经网络，相当于从多个不同的初始点开始搜索，从中选择使损失函数最小的参数；\n",
    "* 使用模拟退火（simulated annealing），在每一步都以一定概率接受比当前解更差的结果，在每步迭代过程中，接受次优解的概率要随着时间的推移而逐渐降低，保证算法稳定；\n",
    "* 随即梯度下降\n",
    "* 遗传算法（genetic algorithms）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考\n",
    "\n",
    "1. https://blog.csdn.net/zhaomengszu/article/details/77834845\n",
    "1. https://www.jianshu.com/p/c5cda5a52ee4"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}