ch06-梯度下降法/04-随机梯度下降法(SGD).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SGD随机梯度下降法\n",
    "`Stochastic-Gradient-Descent`\n",
    "\n",
    "\n",
    "搜索的方向\n",
    "- 不能保证是梯度减小的方向\n",
    "- 不能保证梯度减小最快的方向\n",
    "\n",
    "越逼近，学习率要较少\n",
    "\n",
    "学习率递减，循环次数增加而减少\n",
    "\n",
    "分母加个数 + b：减缓速度\n",
    "\n",
    "模拟退火思想：炼钢过程，火量逐渐变小\n",
    "\n",
    "SGD全样本，走的最稳\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## SGD随机梯度下降\n",
    "优点：更新速度上得到提升\n",
    "\n",
    "缺点：噪声很大，抖动，徘徊比较严重\n",
    "\n",
    "根据不同样本，改变自己的方向和策略"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = 100000\n",
    "\n",
    "x = np.random.normal(size=m)\n",
    "X = x.reshape(-1, 1)\n",
    "y = 4.*x +3. + np.random.normal(0, 3, size=m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def J(theta, X_b, y):\n",
    "    try:\n",
    "        return np.sum((y - X_b.dot(theta)) ** 2.) / len(y)\n",
    "    except:\n",
    "        return float('inf')\n",
    "\n",
    "def dJ(theta, X_b, y):\n",
    "    return X_b.T.dot(X_b.dot(theta) - y) * 2. / len(X_b)\n",
    "\n",
    "def gradient_descent(X_b, y, initial_theta, eta, n_iters=1e4, epsilon=1e-8):\n",
    "    theta = initial_theta\n",
    "    cur_iter = 0\n",
    "\n",
    "    # 条件1：迭代次数\n",
    "    while cur_iter < n_iters:\n",
    "        gradient = dJ(theta, X_b, y)\n",
    "        last_theta = theta\n",
    "        theta = theta - eta * gradient\n",
    "        # 条件2：找到的损失函数的值，已经不能再减小了，达到精度\n",
    "        if (abs(J(theta, X_b, y) - J(last_theta, X_b, y)) < epsilon):\n",
    "            break\n",
    "        cur_iter += 1\n",
    "\n",
    "    return theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4 µs, sys: 1 µs, total: 5 µs\n",
      "Wall time: 11.2 µs\n"
     ]
    }
   ],
   "source": [
    "%time\n",
    "X_b = np.hstack([np.ones((len(X), 1)), X])\n",
    "initial_theta = np.zeros(X_b.shape[1])\n",
    "eta = 0.01\n",
    "theta = gradient_descent(X_b, y, initial_theta, eta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([3.00717   , 4.00886931])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "theta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 随机梯度下降法\n",
    "\n",
    "梯度改变方向是随机的，损失函数不能保证一直是减小的\n",
    "\n",
    "损失函数的值是跳跃的\n",
    "\n",
    "这一次搜索 比上一次搜索，差距越来越小，不代表离损失函数中心更近了！\n",
    "\n",
    "——> 跟样本随机梯度有关\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dJ_sgd(theta, X_b_i, y_i):\n",
    "    return X_b_i.T.dot(X_b_i.dot(theta) - y_i) * 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sgd(X_b, y, initial_theta, n_iters):\n",
    "\n",
    "    t0 = 5\n",
    "    t1 = 50\n",
    "    def learning_rate(t):\n",
    "        return t0 / (t + t1)\n",
    "        \n",
    "    theta = initial_theta\n",
    "    for cur_iter in range(n_iters):\n",
    "        rand_i = np.random.randint(len(X_b))\n",
    "        gradient = dJ_sgd(theta, X_b[rand_i], y[rand_i])\n",
    "        theta = theta - learning_rate(cur_iter) * gradient\n",
    "\n",
    "    return theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 293 ms, sys: 4.42 ms, total: 297 ms\n",
      "Wall time: 307 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "X_b = np.hstack([np.ones((len(X), 1)), X])\n",
    "initial_theta = np.zeros(X_b.shape[1])\n",
    "theta = sgd(X_b, y, initial_theta, n_iters=len(X_b)//3) # 只需要循环1/3的样本个数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([2.98259214, 3.99700692])"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "theta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/stochastic.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6.4rc1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}