lesson5_gd.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### GD2 exercise\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def gradient_descent_update(x, gradx, learning_rate):\n",
    "    \"\"\"\n",
    "    Performs a gradient descent update.\n",
    "    \"\"\"\n",
    "    # TODO: Implement gradient descent.\n",
    "    x -= learning_rate*gradx\n",
    "    # Return the new value for x\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "EPOCH 0: Cost = 22657605.000, x = 9520.000\n",
      "EPOCH 1: Cost = 21760364.040, x = 9329.600\n",
      "EPOCH 2: Cost = 20898653.822, x = 9143.008\n",
      "EPOCH 3: Cost = 20071067.329, x = 8960.148\n",
      "EPOCH 4: Cost = 19276253.260, x = 8780.945\n",
      "EPOCH 5: Cost = 18512913.829, x = 8605.326\n",
      "EPOCH 6: Cost = 17779802.640, x = 8433.219\n",
      "EPOCH 7: Cost = 17075722.653, x = 8264.555\n",
      "EPOCH 8: Cost = 16399524.234, x = 8099.264\n",
      "EPOCH 9: Cost = 15750103.272, x = 7937.279\n",
      "EPOCH 10: Cost = 15126399.381, x = 7778.533\n",
      "EPOCH 11: Cost = 14527394.163, x = 7622.962\n",
      "EPOCH 12: Cost = 13952109.552, x = 7470.503\n",
      "EPOCH 13: Cost = 13399606.212, x = 7321.093\n",
      "EPOCH 14: Cost = 12868982.004, x = 7174.671\n",
      "EPOCH 15: Cost = 12359370.515, x = 7031.178\n",
      "EPOCH 16: Cost = 11869939.640, x = 6890.554\n",
      "EPOCH 17: Cost = 11399890.229, x = 6752.743\n",
      "EPOCH 18: Cost = 10948454.774, x = 6617.688\n",
      "EPOCH 19: Cost = 10514896.163, x = 6485.335\n",
      "EPOCH 20: Cost = 10098506.473, x = 6355.628\n",
      "EPOCH 21: Cost = 9698605.814, x = 6228.515\n",
      "EPOCH 22: Cost = 9314541.222, x = 6103.945\n",
      "EPOCH 23: Cost = 8945685.588, x = 5981.866\n",
      "EPOCH 24: Cost = 8591436.636, x = 5862.229\n",
      "EPOCH 25: Cost = 8251215.944, x = 5744.984\n",
      "EPOCH 26: Cost = 7924467.990, x = 5630.085\n",
      "EPOCH 27: Cost = 7610659.256, x = 5517.483\n",
      "EPOCH 28: Cost = 7309277.347, x = 5407.133\n",
      "EPOCH 29: Cost = 7019830.162, x = 5298.991\n",
      "EPOCH 30: Cost = 6741845.086, x = 5193.011\n",
      "EPOCH 31: Cost = 6474868.218, x = 5089.151\n",
      "EPOCH 32: Cost = 6218463.635, x = 4987.367\n",
      "EPOCH 33: Cost = 5972212.673, x = 4887.620\n",
      "EPOCH 34: Cost = 5735713.249, x = 4789.868\n",
      "EPOCH 35: Cost = 5508579.203, x = 4694.070\n",
      "EPOCH 36: Cost = 5290439.664, x = 4600.189\n",
      "EPOCH 37: Cost = 5080938.451, x = 4508.185\n",
      "EPOCH 38: Cost = 4879733.487, x = 4418.021\n",
      "EPOCH 39: Cost = 4686496.239, x = 4329.661\n",
      "EPOCH 40: Cost = 4500911.186, x = 4243.068\n",
      "EPOCH 41: Cost = 4322675.301, x = 4158.206\n",
      "EPOCH 42: Cost = 4151497.557, x = 4075.042\n",
      "EPOCH 43: Cost = 3987098.452, x = 3993.542\n",
      "EPOCH 44: Cost = 3829209.551, x = 3913.671\n",
      "EPOCH 45: Cost = 3677573.051, x = 3835.397\n",
      "EPOCH 46: Cost = 3531941.356, x = 3758.689\n",
      "EPOCH 47: Cost = 3392076.676, x = 3683.516\n",
      "EPOCH 48: Cost = 3257750.638, x = 3609.845\n",
      "EPOCH 49: Cost = 3128743.910, x = 3537.648\n",
      "EPOCH 50: Cost = 3004845.850, x = 3466.895\n",
      "EPOCH 51: Cost = 2885854.152, x = 3397.557\n",
      "EPOCH 52: Cost = 2771574.526, x = 3329.606\n",
      "EPOCH 53: Cost = 2661820.372, x = 3263.014\n",
      "EPOCH 54: Cost = 2556412.484, x = 3197.754\n",
      "EPOCH 55: Cost = 2455178.747, x = 3133.799\n",
      "EPOCH 56: Cost = 2357953.867, x = 3071.123\n",
      "EPOCH 57: Cost = 2264579.092, x = 3009.700\n",
      "EPOCH 58: Cost = 2174901.958, x = 2949.506\n",
      "EPOCH 59: Cost = 2088776.038, x = 2890.516\n",
      "EPOCH 60: Cost = 2006060.705, x = 2832.706\n",
      "EPOCH 61: Cost = 1926620.899, x = 2776.052\n",
      "EPOCH 62: Cost = 1850326.910, x = 2720.531\n",
      "EPOCH 63: Cost = 1777054.162, x = 2666.120\n",
      "EPOCH 64: Cost = 1706683.015, x = 2612.798\n",
      "EPOCH 65: Cost = 1639098.566, x = 2560.542\n",
      "EPOCH 66: Cost = 1574190.461, x = 2509.331\n",
      "EPOCH 67: Cost = 1511852.716, x = 2459.144\n",
      "EPOCH 68: Cost = 1451983.547, x = 2409.961\n",
      "EPOCH 69: Cost = 1394485.196, x = 2361.762\n",
      "EPOCH 70: Cost = 1339263.780, x = 2314.527\n",
      "EPOCH 71: Cost = 1286229.133, x = 2268.236\n",
      "EPOCH 72: Cost = 1235294.657, x = 2222.872\n",
      "EPOCH 73: Cost = 1186377.187, x = 2178.414\n",
      "EPOCH 74: Cost = 1139396.848, x = 2134.846\n",
      "EPOCH 75: Cost = 1094276.931, x = 2092.149\n",
      "EPOCH 76: Cost = 1050943.762, x = 2050.306\n",
      "EPOCH 77: Cost = 1009326.587, x = 2009.300\n",
      "EPOCH 78: Cost = 969357.453, x = 1969.114\n",
      "EPOCH 79: Cost = 930971.095, x = 1929.732\n",
      "EPOCH 80: Cost = 894104.838, x = 1891.137\n",
      "EPOCH 81: Cost = 858698.485, x = 1853.314\n",
      "EPOCH 82: Cost = 824694.223, x = 1816.248\n",
      "EPOCH 83: Cost = 792036.529, x = 1779.923\n",
      "EPOCH 84: Cost = 760672.081, x = 1744.325\n",
      "EPOCH 85: Cost = 730549.664, x = 1709.438\n",
      "EPOCH 86: Cost = 701620.096, x = 1675.249\n",
      "EPOCH 87: Cost = 673836.138, x = 1641.744\n",
      "EPOCH 88: Cost = 647152.425, x = 1608.909\n",
      "EPOCH 89: Cost = 621525.387, x = 1576.731\n",
      "EPOCH 90: Cost = 596913.179, x = 1545.197\n",
      "EPOCH 91: Cost = 573275.616, x = 1514.293\n",
      "EPOCH 92: Cost = 550574.099, x = 1484.007\n",
      "EPOCH 93: Cost = 528771.563, x = 1454.327\n",
      "EPOCH 94: Cost = 507832.407, x = 1425.240\n",
      "EPOCH 95: Cost = 487722.442, x = 1396.735\n",
      "EPOCH 96: Cost = 468408.831, x = 1368.801\n",
      "EPOCH 97: Cost = 449860.039, x = 1341.425\n",
      "EPOCH 98: Cost = 432045.780, x = 1314.596\n",
      "EPOCH 99: Cost = 414936.965, x = 1288.304\n",
      "EPOCH 100: Cost = 398505.659, x = 1262.538\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Given the starting point of any `x` gradient descent\n",
    "should be able to find the minimum value of x for the\n",
    "cost function `f` defined below.\n",
    "\"\"\"\n",
    "import random\n",
    "#from gd import gradient_descent_update\n",
    "\n",
    "\n",
    "def f(x):\n",
    "    \"\"\"\n",
    "    Quadratic function.\n",
    "\n",
    "    It's easy to see the minimum value of the function\n",
    "    is 5 when is x=0.\n",
    "    \"\"\"\n",
    "    return x**2 + 5\n",
    "\n",
    "\n",
    "def df(x):\n",
    "    \"\"\"\n",
    "    Derivative of `f` with respect to `x`.\n",
    "    \"\"\"\n",
    "    return 2*x\n",
    "\n",
    "\n",
    "# Random number better 0 and 10,000. Feel free to set x whatever you like.\n",
    "x = random.randint(0, 10000)\n",
    "# TODO: Set the learning rate\n",
    "learning_rate = 0.01\n",
    "epochs = 100\n",
    "\n",
    "for i in range(epochs+1):\n",
    "    cost = f(x)\n",
    "    gradx = df(x)\n",
    "    print(\"EPOCH {}: Cost = {:.3f}, x = {:.3f}\".format(i, cost, gradx))\n",
    "    x = gradient_descent_update(x, gradx, learning_rate)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Gradient Descent Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Implement the backward method of the Sigmoid node.\n",
    "\"\"\"\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "class Node(object):\n",
    "    \"\"\"\n",
    "    Base class for nodes in the network.\n",
    "\n",
    "    Arguments:\n",
    "\n",
    "        `inbound_nodes`: A list of nodes with edges into this node.\n",
    "    \"\"\"\n",
    "    def __init__(self, inbound_nodes=[]):\n",
    "        \"\"\"\n",
    "        Node's constructor (runs when the object is instantiated). Sets\n",
    "        properties that all nodes need.\n",
    "        \"\"\"\n",
    "        # A list of nodes with edges into this node.\n",
    "        self.inbound_nodes = inbound_nodes\n",
    "        # The eventual value of this node. Set by running\n",
    "        # the forward() method.\n",
    "        self.value = None\n",
    "        # A list of nodes that this node outputs to.\n",
    "        self.outbound_nodes = []\n",
    "        # New property! Keys are the inputs to this node and\n",
    "        # their values are the partials of this node with\n",
    "        # respect to that input.\n",
    "        self.gradients = {}\n",
    "        # Sets this node as an outbound node for all of\n",
    "        # this node's inputs.\n",
    "        for node in inbound_nodes:\n",
    "            node.outbound_nodes.append(self)\n",
    "\n",
    "    def forward(self):\n",
    "        \"\"\"\n",
    "        Every node that uses this class as a base class will\n",
    "        need to define its own `forward` method.\n",
    "        \"\"\"\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def backward(self):\n",
    "        \"\"\"\n",
    "        Every node that uses this class as a base class will\n",
    "        need to define its own `backward` method.\n",
    "        \"\"\"\n",
    "        raise NotImplementedError\n",
    "\n",
    "\n",
    "class Input(Node):\n",
    "    \"\"\"\n",
    "    A generic input into the network.\n",
    "    \"\"\"\n",
    "    def __init__(self):\n",
    "        # The base class constructor has to run to set all\n",
    "        # the properties here.\n",
    "        #\n",
    "        # The most important property on an Input is value.\n",
    "        # self.value is set during `topological_sort` later.\n",
    "        Node.__init__(self)\n",
    "\n",
    "    def forward(self):\n",
    "        # Do nothing because nothing is calculated.\n",
    "        pass\n",
    "\n",
    "    def backward(self):\n",
    "        # An Input node has no inputs so the gradient (derivative)\n",
    "        # is zero.\n",
    "        # The key, `self`, is reference to this object.\n",
    "        self.gradients = {self: 0}\n",
    "        # Weights and bias may be inputs, so you need to sum\n",
    "        # the gradient from output gradients.\n",
    "        for n in self.outbound_nodes:\n",
    "            grad_cost = n.gradients[self]\n",
    "            self.gradients[self] += grad_cost * 1\n",
    "\n",
    "\n",
    "class Linear(Node):\n",
    "    \"\"\"\n",
    "    Represents a node that performs a linear transform.\n",
    "    \"\"\"\n",
    "    def __init__(self, X, W, b):\n",
    "        # The base class (Node) constructor. Weights and bias\n",
    "        # are treated like inbound nodes.\n",
    "        Node.__init__(self, [X, W, b])\n",
    "\n",
    "    def forward(self):\n",
    "        \"\"\"\n",
    "        Performs the math behind a linear transform.\n",
    "        \"\"\"\n",
    "        X = self.inbound_nodes[0].value\n",
    "        W = self.inbound_nodes[1].value\n",
    "        b = self.inbound_nodes[2].value\n",
    "        self.value = np.dot(X, W) + b\n",
    "\n",
    "    def backward(self):\n",
    "        \"\"\"\n",
    "        Calculates the gradient based on the output values.\n",
    "        \"\"\"\n",
    "        # Initialize a partial for each of the inbound_nodes.\n",
    "        self.gradients = {n: np.zeros_like(n.value) for n in self.inbound_nodes}\n",
    "        # Cycle through the outputs. The gradient will change depending\n",
    "        # on each output, so the gradients are summed over all outputs.\n",
    "        for n in self.outbound_nodes:\n",
    "            # Get the partial of the cost with respect to this node.\n",
    "            grad_cost = n.gradients[self]\n",
    "            # Set the partial of the loss with respect to this node's inputs.\n",
    "            self.gradients[self.inbound_nodes[0]] += np.dot(grad_cost, self.inbound_nodes[1].value.T)\n",
    "            # Set the partial of the loss with respect to this node's weights.\n",
    "            self.gradients[self.inbound_nodes[1]] += np.dot(self.inbound_nodes[0].value.T, grad_cost)\n",
    "            # Set the partial of the loss with respect to this node's bias.\n",
    "            self.gradients[self.inbound_nodes[2]] += np.sum(grad_cost, axis=0, keepdims=False)\n",
    "\n",
    "\n",
    "class Sigmoid(Node):\n",
    "    \"\"\"\n",
    "    Represents a node that performs the sigmoid activation function.\n",
    "    \"\"\"\n",
    "    def __init__(self, node):\n",
    "        # The base class constructor.\n",
    "        Node.__init__(self, [node])\n",
    "\n",
    "    def _sigmoid(self, x):\n",
    "        \"\"\"\n",
    "        This method is separate from `forward` because it\n",
    "        will be used with `backward` as well.\n",
    "\n",
    "        `x`: A numpy array-like object.\n",
    "        \"\"\"\n",
    "        return 1. / (1. + np.exp(-x))\n",
    "\n",
    "    def forward(self):\n",
    "        \"\"\"\n",
    "        Perform the sigmoid function and set the value.\n",
    "        \"\"\"\n",
    "        input_value = self.inbound_nodes[0].value\n",
    "        self.value = self._sigmoid(input_value)\n",
    "\n",
    "    def backward(self):\n",
    "        \"\"\"\n",
    "        Calculates the gradient using the derivative of\n",
    "        the sigmoid function.\n",
    "        \"\"\"\n",
    "        # Initialize the gradients to 0.\n",
    "        self.gradients = {n: np.zeros_like(n.value) for n in self.inbound_nodes}\n",
    "\n",
    "        # Cycle through the outputs. The gradient will change depending\n",
    "        # on each output, so the gradients are summed over all outputs.\n",
    "\n",
    "        \"\"\"\n",
    "        TODO: Your code goes here!\n",
    "\n",
    "        Set the gradients property to the gradients with respect to each input.\n",
    "\n",
    "        NOTE: See the Linear node and MSE node for examples.\n",
    "        \"\"\"\n",
    "        for n in self.outbound_nodes:\n",
    "            # Get the partial of the cost with respect to this node.\n",
    "            grad_cost = n.gradients[self]\n",
    "            sigmoid_value = self.value\n",
    "            # Set the partial of the loss with respect to this node's inputs.\n",
    "            self.gradients[self.inbound_nodes[0]] += grad_cost * sigmoid_value * (1- sigmoid_value)\n",
    "\n",
    "\n",
    "\n",
    "class MSE(Node):\n",
    "    def __init__(self, y, a):\n",
    "        \"\"\"\n",
    "        The mean squared error cost function.\n",
    "        Should be used as the last node for a network.\n",
    "        \"\"\"\n",
    "        # Call the base class' constructor.\n",
    "        Node.__init__(self, [y, a])\n",
    "\n",
    "    def forward(self):\n",
    "        \"\"\"\n",
    "        Calculates the mean squared error.\n",
    "        \"\"\"\n",
    "        # NOTE: We reshape these to avoid possible matrix/vector broadcast\n",
    "        # errors.\n",
    "        #\n",
    "        # For example, if we subtract an array of shape (3,) from an array of shape\n",
    "        # (3,1) we get an array of shape(3,3) as the result when we want\n",
    "        # an array of shape (3,1) instead.\n",
    "        #\n",
    "        # Making both arrays (3,1) insures the result is (3,1) and does\n",
    "        # an elementwise subtraction as expected.\n",
    "        y = self.inbound_nodes[0].value.reshape(-1, 1)\n",
    "        a = self.inbound_nodes[1].value.reshape(-1, 1)\n",
    "\n",
    "        self.m = self.inbound_nodes[0].value.shape[0]\n",
    "        # Save the computed output for backward.\n",
    "        self.diff = y - a\n",
    "        self.value = np.mean(self.diff**2)\n",
    "\n",
    "    def backward(self):\n",
    "        \"\"\"\n",
    "        Calculates the gradient of the cost.\n",
    "\n",
    "        This is the final node of the network so outbound nodes\n",
    "        are not a concern.\n",
    "        \"\"\"\n",
    "        self.gradients[self.inbound_nodes[0]] = (2 / self.m) * self.diff\n",
    "        self.gradients[self.inbound_nodes[1]] = (-2 / self.m) * self.diff\n",
    "\n",
    "\n",
    "def topological_sort(feed_dict):\n",
    "    \"\"\"\n",
    "    Sort the nodes in topological order using Kahn's Algorithm.\n",
    "\n",
    "    `feed_dict`: A dictionary where the key is a `Input` Node and the value is the respective value feed to that Node.\n",
    "\n",
    "    Returns a list of sorted nodes.\n",
    "    \"\"\"\n",
    "\n",
    "    input_nodes = [n for n in feed_dict.keys()]\n",
    "\n",
    "    G = {}\n",
    "    nodes = [n for n in input_nodes]\n",
    "    while len(nodes) > 0:\n",
    "        n = nodes.pop(0)\n",
    "        if n not in G:\n",
    "            G[n] = {'in': set(), 'out': set()}\n",
    "        for m in n.outbound_nodes:\n",
    "            if m not in G:\n",
    "                G[m] = {'in': set(), 'out': set()}\n",
    "            G[n]['out'].add(m)\n",
    "            G[m]['in'].add(n)\n",
    "            nodes.append(m)\n",
    "\n",
    "    L = []\n",
    "    S = set(input_nodes)\n",
    "    while len(S) > 0:\n",
    "        n = S.pop()\n",
    "\n",
    "        if isinstance(n, Input):\n",
    "            n.value = feed_dict[n]\n",
    "\n",
    "        L.append(n)\n",
    "        for m in n.outbound_nodes:\n",
    "            G[n]['out'].remove(m)\n",
    "            G[m]['in'].remove(n)\n",
    "            # if no other incoming edges add to S\n",
    "            if len(G[m]['in']) == 0:\n",
    "                S.add(m)\n",
    "    return L\n",
    "\n",
    "\n",
    "def forward_and_backward(graph):\n",
    "    \"\"\"\n",
    "    Performs a forward pass and a backward pass through a list of sorted Nodes.\n",
    "\n",
    "    Arguments:\n",
    "\n",
    "        `graph`: The result of calling `topological_sort`.\n",
    "    \"\"\"\n",
    "    # Forward pass\n",
    "    for n in graph:\n",
    "        n.forward()\n",
    "\n",
    "    # Backward pass\n",
    "    # see: https://docs.python.org/2.3/whatsnew/section-slices.html\n",
    "    for n in graph[::-1]:\n",
    "        n.backward()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[array([[ -3.34017280e-05,  -5.01025919e-05],\n",
      "       [ -6.68040138e-05,  -1.00206021e-04]]), array([[ 0.9999833],\n",
      "       [ 1.9999833]]), array([[  5.01028709e-05],\n",
      "       [  1.00205742e-04]]), array([ -5.01028709e-05])]\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Test your network here!\n",
    "\n",
    "No need to change this code, but feel free to tweak it\n",
    "to test your network!\n",
    "\n",
    "Make your changes to backward method of the Sigmoid class in miniflow.py\n",
    "\"\"\"\n",
    "\n",
    "import numpy as np\n",
    "#from miniflow import *\n",
    "\n",
    "X, W, b = Input(), Input(), Input()\n",
    "y = Input()\n",
    "f = Linear(X, W, b)\n",
    "a = Sigmoid(f)\n",
    "cost = MSE(y, a)\n",
    "\n",
    "X_ = np.array([[-1., -2.], [-1, -2]])\n",
    "W_ = np.array([[2.], [3.]])\n",
    "b_ = np.array([-3.])\n",
    "y_ = np.array([1, 2])\n",
    "\n",
    "feed_dict = {\n",
    "    X: X_,\n",
    "    y: y_,\n",
    "    W: W_,\n",
    "    b: b_,\n",
    "}\n",
    "\n",
    "graph = topological_sort(feed_dict)\n",
    "forward_and_backward(graph)\n",
    "# return the gradients for each Input\n",
    "gradients = [t.gradients[t] for t in [X, y, W, b]]\n",
    "\n",
    "\"\"\"\n",
    "Expected output\n",
    "\n",
    "[array([[ -3.34017280e-05,  -5.01025919e-05],\n",
    "       [ -6.68040138e-05,  -1.00206021e-04]]), array([[ 0.9999833],\n",
    "       [ 1.9999833]]), array([[  5.01028709e-05],\n",
    "       [  1.00205742e-04]]), array([ -5.01028709e-05])]\n",
    "\"\"\"\n",
    "print(gradients)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}