{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import numpy as np\n", "from bokeh.plotting import figure, show, output_notebook" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## algorithm" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def gradient_descent(F, dF, x, steps=100, lr=0.001):\n", " loss = []\n", " \n", " for _ in range(steps):\n", " dx = dF(x)\n", " x -= lr * dx\n", " loss.append(F(x))\n", "\n", " return x, loss" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def rmsprop(F, dF, x, steps=100, lr=0.001, decay=.9, eps=1e-8):\n", " loss = []\n", " dx_mean_sqr = np.zeros(x.shape, dtype=float)\n", "\n", " for _ in range(steps):\n", " dx = dF(x)\n", " dx_mean_sqr = decay * dx_mean_sqr + (1 - decay) * dx ** 2\n", " x -= lr * dx / (np.sqrt(dx_mean_sqr) + eps)\n", " loss.append(F(x))\n", " \n", " return x, loss" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def rmsprop_momentum(F, dF, x, steps=100, lr=0.001, decay=.9, eps=1e-8, mu=.9):\n", " loss = []\n", " dx_mean_sqr = np.zeros(x.shape, dtype=float)\n", " momentum = np.zeros(x.shape, dtype=float)\n", "\n", " for _ in range(steps):\n", " dx = dF(x)\n", " dx_mean_sqr = decay * dx_mean_sqr + (1 - decay) * dx ** 2\n", " momentum = mu * momentum + lr * dx / (np.sqrt(dx_mean_sqr) + eps)\n", " x -= momentum\n", " loss.append(F(x))\n", "\n", " return x, loss" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## function" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def F(x):\n", " residual = A @ x - np.eye(len(A), dtype=float)\n", " return np.sum(residual ** 2)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def dF(x):\n", " return 2 * A.T @ (A @ x - np.eye(len(A), dtype=float))" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": true }, "outputs": [], "source": [ "A = np.array([\n", " [2, 5, 1, 4, 6],\n", " [3, 5, 0, 0, 0],\n", " [1, 1, 0, 3, 8],\n", " [6, 6, 2, 2, 1],\n", " [8, 3, 5, 1, 4],\n", "], dtype=float)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## optimization" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(array([[ 0.79, -0.01, 0.18, 0.19, -0.08],\n", " [-0.01, 0.8 , 0. , 0.2 , -0.07],\n", " [ 0.18, 0. , 0.85, -0.15, 0.07],\n", " [ 0.19, 0.2 , -0.15, 0.66, 0.13],\n", " [-0.08, -0.07, 0.07, 0.13, 0.95]]), 0.54691984767143453)" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "X, loss1 = gradient_descent(F, dF, A * 0, steps=300)\n", "(A @ X).round(2), loss1[-1]" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(array([[ 0.84, -0.05, 0.1 , 0.1 , -0.06],\n", " [-0.04, 0.82, 0.03, 0.19, -0.03],\n", " [ 0.12, 0.03, 0.9 , -0.08, 0.03],\n", " [ 0.15, 0.2 , -0.12, 0.75, 0.06],\n", " [-0.08, -0.09, 0.04, 0.1 , 0.97]]), 0.32396954419819657)" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "X, loss2 = rmsprop(F, dF, A * 0, steps=300)\n", "(A @ X).round(2), loss2[-1]" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(array([[ 0.99, 0.01, 0. , -0.01, 0. ],\n", " [-0. , 1. , 0. , -0. , 0. ],\n", " [-0. , 0.01, 1. , -0.01, 0. ],\n", " [-0.01, 0.01, 0. , 0.99, 0. ],\n", " [-0.01, 0.01, 0. , -0.01, 1. ]]), 0.00062303887772378397)" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "X, loss3 = rmsprop_momentum(F, dF, A * 0, steps=300)\n", "(A @ X).round(2), loss3[-1]" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "\n", "
\n", " \n", " Loading BokehJS ...\n", "
" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "application/javascript": [ "\n", "(function(global) {\n", " function now() {\n", " return new Date();\n", " }\n", "\n", " var force = true;\n", "\n", " if (typeof (window._bokeh_onload_callbacks) === \"undefined\" || force === true) {\n", " window._bokeh_onload_callbacks = [];\n", " window._bokeh_is_loading = undefined;\n", " }\n", "\n", "\n", " \n", " if (typeof (window._bokeh_timeout) === \"undefined\" || force === true) {\n", " window._bokeh_timeout = Date.now() + 5000;\n", " window._bokeh_failed_load = false;\n", " }\n", "\n", " var NB_LOAD_WARNING = {'data': {'text/html':\n", " \"
\\n\"+\n", " \"

\\n\"+\n", " \"BokehJS does not appear to have successfully loaded. If loading BokehJS from CDN, this \\n\"+\n", " \"may be due to a slow or bad network connection. Possible fixes:\\n\"+\n", " \"

\\n\"+\n", " \"\\n\"+\n", " \"\\n\"+\n", " \"from bokeh.resources import INLINE\\n\"+\n", " \"output_notebook(resources=INLINE)\\n\"+\n", " \"\\n\"+\n", " \"
\"}};\n", "\n", " function display_loaded() {\n", " if (window.Bokeh !== undefined) {\n", " var el = document.getElementById(\"d8b01c18-bc74-42bd-8485-9e68ed5f812a\");\n", " el.textContent = \"BokehJS \" + Bokeh.version + \" successfully loaded.\";\n", " } else if (Date.now() < window._bokeh_timeout) {\n", " setTimeout(display_loaded, 100)\n", " }\n", " }\n", "\n", " function run_callbacks() {\n", " window._bokeh_onload_callbacks.forEach(function(callback) { callback() });\n", " delete window._bokeh_onload_callbacks\n", " console.info(\"Bokeh: all callbacks have finished\");\n", " }\n", "\n", " function load_libs(js_urls, callback) {\n", " window._bokeh_onload_callbacks.push(callback);\n", " if (window._bokeh_is_loading > 0) {\n", " console.log(\"Bokeh: BokehJS is being loaded, scheduling callback at\", now());\n", " return null;\n", " }\n", " if (js_urls == null || js_urls.length === 0) {\n", " run_callbacks();\n", " return null;\n", " }\n", " console.log(\"Bokeh: BokehJS not loaded, scheduling load and callback at\", now());\n", " window._bokeh_is_loading = js_urls.length;\n", " for (var i = 0; i < js_urls.length; i++) {\n", " var url = js_urls[i];\n", " var s = document.createElement('script');\n", " s.src = url;\n", " s.async = false;\n", " s.onreadystatechange = s.onload = function() {\n", " window._bokeh_is_loading--;\n", " if (window._bokeh_is_loading === 0) {\n", " console.log(\"Bokeh: all BokehJS libraries loaded\");\n", " run_callbacks()\n", " }\n", " };\n", " s.onerror = function() {\n", " console.warn(\"failed to load library \" + url);\n", " };\n", " console.log(\"Bokeh: injecting script tag for BokehJS library: \", url);\n", " document.getElementsByTagName(\"head\")[0].appendChild(s);\n", " }\n", " };var element = document.getElementById(\"d8b01c18-bc74-42bd-8485-9e68ed5f812a\");\n", " if (element == null) {\n", " console.log(\"Bokeh: ERROR: autoload.js configured with elementid 'd8b01c18-bc74-42bd-8485-9e68ed5f812a' but no matching script tag was found. \")\n", " return false;\n", " }\n", "\n", " var js_urls = [\"https://cdn.pydata.org/bokeh/release/bokeh-0.12.5.min.js\", \"https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.5.min.js\"];\n", "\n", " var inline_js = [\n", " function(Bokeh) {\n", " Bokeh.set_log_level(\"info\");\n", " },\n", " \n", " function(Bokeh) {\n", " \n", " },\n", " \n", " function(Bokeh) {\n", " \n", " document.getElementById(\"d8b01c18-bc74-42bd-8485-9e68ed5f812a\").textContent = \"BokehJS is loading...\";\n", " },\n", " function(Bokeh) {\n", " console.log(\"Bokeh: injecting CSS: https://cdn.pydata.org/bokeh/release/bokeh-0.12.5.min.css\");\n", " Bokeh.embed.inject_css(\"https://cdn.pydata.org/bokeh/release/bokeh-0.12.5.min.css\");\n", " console.log(\"Bokeh: injecting CSS: https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.5.min.css\");\n", " Bokeh.embed.inject_css(\"https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.5.min.css\");\n", " }\n", " ];\n", "\n", " function run_inline_js() {\n", " \n", " if ((window.Bokeh !== undefined) || (force === true)) {\n", " for (var i = 0; i < inline_js.length; i++) {\n", " inline_js[i](window.Bokeh);\n", " }if (force === true) {\n", " display_loaded();\n", " }} else if (Date.now() < window._bokeh_timeout) {\n", " setTimeout(run_inline_js, 100);\n", " } else if (!window._bokeh_failed_load) {\n", " console.log(\"Bokeh: BokehJS failed to load within specified timeout.\");\n", " window._bokeh_failed_load = true;\n", " } else if (force !== true) {\n", " var cell = $(document.getElementById(\"d8b01c18-bc74-42bd-8485-9e68ed5f812a\")).parents('.cell').data().cell;\n", " cell.output_area.append_execute_result(NB_LOAD_WARNING)\n", " }\n", "\n", " }\n", "\n", " if (window._bokeh_is_loading === 0) {\n", " console.log(\"Bokeh: BokehJS loaded, going straight to plotting\");\n", " run_inline_js();\n", " } else {\n", " load_libs(js_urls, function() {\n", " console.log(\"Bokeh: BokehJS plotting callback run at\", now());\n", " run_inline_js();\n", " });\n", " }\n", "}(this));" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\n", "\n", "
\n", "
\n", "
\n", "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "output_notebook()\n", "\n", "plot = figure()\n", "plot.line(x=range(len(loss1)), y=loss1, color='steelblue', legend='gd')\n", "plot.line(x=range(len(loss2)), y=loss2, color='green', legend='rmsprop')\n", "plot.line(x=range(len(loss3)), y=loss3, color='red', legend='rmsprop+momentum')\n", "\n", "show(plot)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "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.0" } }, "nbformat": 4, "nbformat_minor": 2 }