08. Градиентный спуск.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "применение градиента\n",
      "минимум v [-3.195798902263642e-06, 3.195798902263642e-06, -1.9174793413581833e-06]\n",
      "минимальное значение 2.410298827195441e-11\n",
      "\n",
      "применение пакетной минимизации minimize_batch\n",
      "минимум v [-0.001063382396627933, 0.0, 0.001063382396627933]\n",
      "минимальное значение 2.2615642429163335e-06\n"
     ]
    }
   ],
   "source": [
    "# -*- coding: utf-8 -*-\n",
    "\n",
    "# gradient_descent.py\n",
    "\n",
    "import sys\n",
    "sys.path.append(\"../code-python3-ru\")\n",
    "\n",
    "from collections import Counter\n",
    "from lib.linear_algebra import distance, vector_subtract, scalar_multiply\n",
    "from functools import reduce\n",
    "import math, random\n",
    "\n",
    "def sum_of_squares(v):\n",
    "    \"\"\"вычисляет сумму квадратов элементов вектора v\"\"\"\n",
    "    return sum(v_i ** 2 for v_i in v)\n",
    "\n",
    "def difference_quotient(f, x, h):\n",
    "    return (f(x + h) - f(x)) / h\n",
    "\n",
    "def plot_estimated_derivative():\n",
    "\n",
    "    def square(x):\n",
    "        return x * x\n",
    "\n",
    "    def derivative(x):\n",
    "        return 2 * x\n",
    "\n",
    "    derivative_estimate = lambda x: difference_quotient(square, x, h=0.00001)\n",
    "\n",
    "    # построить диаграмму, чтобы показать, что фактические производные\n",
    "    # и их приближения в сущности одинаковые\n",
    "    import matplotlib.pyplot as plt\n",
    "    x = range(-10,10)\n",
    "    plt.plot(x, map(derivative, x), 'rx')           # красный  x\n",
    "    plt.plot(x, map(derivative_estimate, x), 'b+')  # синий +\n",
    "    plt.show()                                      # фиолетовый *, будем надеяться\n",
    "\n",
    "def partial_difference_quotient(f, v, i, h):\n",
    "\n",
    "    # прибавить h только к i-му элементу v\n",
    "    w = [v_j + (h if j == i else 0)\n",
    "         for j, v_j in enumerate(v)]\n",
    "\n",
    "    return (f(w) - f(v)) / h\n",
    "\n",
    "def estimate_gradient(f, v, h=0.00001):\n",
    "    return [partial_difference_quotient(f, v, i, h)\n",
    "            for i, _ in enumerate(v)]\n",
    "\n",
    "def step(v, direction, step_size):\n",
    "    \"\"\"двигаться с шаговым размером step_size в направлении от v\"\"\"\n",
    "    return [v_i + step_size * direction_i\n",
    "            for v_i, direction_i in zip(v, direction)]\n",
    "\n",
    "def sum_of_squares_gradient(v):\n",
    "    return [2 * v_i for v_i in v]\n",
    "\n",
    "def safe(f):\n",
    "    \"\"\"определить новую функцию-обертку для f и вернуть ее\"\"\"\n",
    "    def safe_f(*args, **kwargs):\n",
    "        try:\n",
    "            return f(*args, **kwargs)\n",
    "        except:\n",
    "            return float('inf')    # в Python так обоозначается бесконечность\n",
    "    return safe_f\n",
    "\n",
    "#\n",
    "#\n",
    "# минимизация / максимизация на основе пакетного градиентного спуска\n",
    "#\n",
    "#\n",
    "\n",
    "def minimize_batch(target_fn, gradient_fn, theta_0, tolerance=0.000001):\n",
    "    \"\"\"использует градиентный спуск для нахождения вектора theta, \n",
    "    который минимизирует целевую функцию target_fn\"\"\"\n",
    "\n",
    "    step_sizes = [100, 10, 1, 0.1, 0.01, 0.001, 0.0001, 0.00001]\n",
    "\n",
    "    theta = theta_0                           # установить тэта в начальное значение\n",
    "    target_fn = safe(target_fn)               # безопасная версия целевой функции target_fn\n",
    "    value = target_fn(theta)                  # минимизируемое значение\n",
    "\n",
    "    while True:\n",
    "        gradient = gradient_fn(theta)\n",
    "        next_thetas = [step(theta, gradient, -step_size)\n",
    "                       for step_size in step_sizes]\n",
    "\n",
    "        # выбрать то, которое минимизирует функцию ошибок\n",
    "        next_theta = min(next_thetas, key=target_fn)\n",
    "        next_value = target_fn(next_theta)\n",
    "\n",
    "        # остановиться, если функция сходится \n",
    "        if abs(value - next_value) < tolerance:\n",
    "            return theta\n",
    "        else:\n",
    "            theta, value = next_theta, next_value\n",
    "\n",
    "def negate(f):\n",
    "    \"\"\"вернуть функцию, которая для любого входящего x возвращает -f(x)\"\"\"\n",
    "    return lambda *args, **kwargs: -f(*args, **kwargs)\n",
    "\n",
    "def negate_all(f):\n",
    "    \"\"\"то же самое, когда f возвращает список чисел\"\"\"\n",
    "    return lambda *args, **kwargs: [-y for y in f(*args, **kwargs)]\n",
    "\n",
    "def maximize_batch(target_fn, gradient_fn, theta_0, tolerance=0.000001):\n",
    "    return minimize_batch(negate(target_fn),\n",
    "                          negate_all(gradient_fn),\n",
    "                          theta_0,\n",
    "                          tolerance)\n",
    "\n",
    "#\n",
    "# минимизация / максимизация на основе стохастического градиентного спуска \n",
    "#\n",
    "\n",
    "def in_random_order(data):\n",
    "    \"\"\"генератор, который возвращает элементы данных в случайном порядке\"\"\"\n",
    "    indexes = [i for i, _ in enumerate(data)]  # создать список индексов\n",
    "    random.shuffle(indexes)                    # перемешать данные и\n",
    "    for i in indexes:                          # вернуть в этом порядке\n",
    "        yield data[i]\n",
    "\n",
    "def minimize_stochastic(target_fn, gradient_fn, x, y, theta_0, alpha_0=0.01):\n",
    "\n",
    "    data = list(zip(x, y))\n",
    "    theta = theta_0                             # первоначальная гипотеза\n",
    "    alpha = alpha_0                             # первоначальный размер шага\n",
    "    min_theta, min_value = None, float(\"inf\")   # минимум на этот момент\n",
    "    iterations_with_no_improvement = 0\n",
    "\n",
    "    # остановиться, если достигли 100 итераций без улучшений\n",
    "    while iterations_with_no_improvement < 100:\n",
    "        value = sum( target_fn(x_i, y_i, theta) for x_i, y_i in data )\n",
    "\n",
    "        if value < min_value:\n",
    "            # если найден новый минимум, то запомнить его\n",
    "            # и вернуться к первоначальному размеру шага\n",
    "            min_theta, min_value = theta, value\n",
    "            iterations_with_no_improvement = 0\n",
    "            alpha = alpha_0\n",
    "        else:\n",
    "            # в противном случае улучшений нет,\n",
    "            # поэтому пытаемся сжать размер шага\n",
    "            iterations_with_no_improvement += 1\n",
    "            alpha *= 0.9\n",
    "\n",
    "        # и делаем шаг градиента для каждой из точек данных\n",
    "        for x_i, y_i in in_random_order(data):\n",
    "            gradient_i = gradient_fn(x_i, y_i, theta)\n",
    "            theta = vector_subtract(theta, scalar_multiply(alpha, gradient_i))\n",
    "\n",
    "    return min_theta\n",
    "\n",
    "def maximize_stochastic(target_fn, gradient_fn, x, y, theta_0, alpha_0=0.01):\n",
    "    return minimize_stochastic(negate(target_fn),\n",
    "                               negate_all(gradient_fn),\n",
    "                               x, y, theta_0, alpha_0)\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "\n",
    "    print(\"применение градиента\")\n",
    "\n",
    "    v = [random.randint(-10,10) for i in range(3)]\n",
    "\n",
    "    tolerance = 0.0000001\n",
    "\n",
    "    while True:\n",
    "        #print v, sum_of_squares(v)\n",
    "        gradient = sum_of_squares_gradient(v)   # вычислить градиент в точке v\n",
    "        next_v = step(v, gradient, -0.01)       # сделать шаг антиградиента\n",
    "        if distance(next_v, v) < tolerance:     # остановиться, если сходимся\n",
    "            break\n",
    "        v = next_v                              # продолжить, если нет\n",
    "\n",
    "    print(\"минимум v\", v)\n",
    "    print(\"минимальное значение\", sum_of_squares(v))\n",
    "    print()\n",
    "\n",
    "\n",
    "    print(\"применение пакетной минимизации minimize_batch\")\n",
    "\n",
    "    v = [random.randint(-10,10) for i in range(3)]\n",
    "\n",
    "    v = minimize_batch(sum_of_squares, sum_of_squares_gradient, v)\n",
    "\n",
    "    print(\"минимум v\", v)\n",
    "    print(\"минимальное значение\", sum_of_squares(v))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}