MiniFlow.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tiny flowing Tensors\n",
    "Implementing a small version of TensorFlow with the help of Udacity, to better understand backpropagation and differentiable graphs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# fancy functions defined by Udacity, that I am a benefactor of\n",
    "\n",
    "def topological_sort(feed_dict):\n",
    "    \"\"\"\n",
    "    Sort the neurons in topological order using Kahn's Algorithm.\n",
    "\n",
    "    `feed_dict`: A dictionary where the key is a `Input` Neuron and the value is the respective value feed to that Neuron.\n",
    "\n",
    "    Returns a list of sorted neurons.\n",
    "    \"\"\"\n",
    "\n",
    "    input_neurons = [n for n in feed_dict.keys()]\n",
    "\n",
    "    G = {}\n",
    "    neurons = [n for n in input_neurons]\n",
    "    while len(neurons) > 0:\n",
    "        n = neurons.pop(0)\n",
    "        if n not in G:\n",
    "            G[n] = {'in': set(), 'out': set()}\n",
    "        for m in n.outbound_neurons:\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",
    "            neurons.append(m)\n",
    "\n",
    "    L = []\n",
    "    S = set(input_neurons)\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_neurons:\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_pass(output_Neuron, sorted_neurons):\n",
    "    \"\"\"\n",
    "    Performs a forward pass through a list of sorted neurons.\n",
    "\n",
    "    Arguments:\n",
    "\n",
    "        `output_Neuron`: A Neuron in the graph, should be the output Neuron (have no outgoing edges).\n",
    "        `sorted_neurons`: a topologically sorted list of neurons.\n",
    "\n",
    "    Returns the output Neuron's value\n",
    "    \"\"\"\n",
    "\n",
    "    for n in sorted_neurons:\n",
    "        n.forward()\n",
    "\n",
    "    return output_Neuron.value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "# Class and Subclass definitions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Neuron(object):\n",
    "    def __init__(self, inbound_neurons=[]):\n",
    "        #print(\"ibn: {}\".format(inbound_nodes))\n",
    "        # Inbound neurons are those that the current node receives values from\n",
    "        # I'm passing a LIST of neuron OBJECTS\n",
    "        self.inbound_neurons = inbound_neurons\n",
    "        # Outbound neurons are those that it passes the values forward to\n",
    "        self.outbound_neurons = []\n",
    "        # For every inbound node add an outbound neuron to that node\n",
    "        # TODO: I don't quite get it. Practice coming up...!\n",
    "        for n in self.inbound_neurons:\n",
    "            n.outbound_neurons.append(self)\n",
    "        # the value the node will eventually calculate\n",
    "        self.value = None\n",
    "         \n",
    "    def forward(self):\n",
    "        \"\"\"\n",
    "        Forward Propagation.\n",
    "        \n",
    "        Compute the output based on `inbound_nodes`\n",
    "        and store the result in self.value\n",
    "        \"\"\"\n",
    "        # implemented in the subclasses\n",
    "        raise NotImplemented"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Input(Neuron):\n",
    "    def __init__(self):\n",
    "        # no inbound neurons for an input neuron\n",
    "        # therefore the instantiator doesn't need inputs\n",
    "        Neuron.__init__(self)\n",
    "        \n",
    "    def forward(self, value=None):\n",
    "        # input neurons get a value input by Mr. Human\n",
    "        # either explicitly or through this forward() method:\n",
    "        if value is not None:\n",
    "            self.value = value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Add(Neuron):\n",
    "    def __init__(self, neuron1, neuron2):\n",
    "        Neuron.__init__(self, [neuron1, neuron2])\n",
    "    \n",
    "    # remember to pass `self` into the class methods!!\n",
    "    def forward(self):\n",
    "        \"\"\"Calculates the sum of the values of the inbound nodes.\"\"\"\n",
    "        value_neuron1 = self.inbound_neurons[0].value\n",
    "        value_neuron2 = self.inbound_neurons[1].value\n",
    "        self.value = value_neuron1 + value_neuron2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Linear(Neuron):\n",
    "    def __init__(self, inputs, weights, bias):\n",
    "        Neuron.__init__(self, [inputs, weights, bias])\n",
    "\n",
    "        # NOTE: The weights and bias properties here are not\n",
    "        # numbers, but rather references to other nodes.\n",
    "        # The weight and bias values are stored within the\n",
    "        # respective nodes.\n",
    "\n",
    "    def forward(self):\n",
    "        \"\"\"Set self.value to the value of the linear function output.\"\"\"\n",
    "        inputs = self.inbound_neurons[0].value\n",
    "        weights = self.inbound_neurons[1].value\n",
    "        bias = self.inbound_neurons[2].value\n",
    "        # the bias is a one-stop thing for the Neuron\n",
    "        # meaning it only gets calculated once\n",
    "        self.value = bias\n",
    "        #print(inputs, weights, bias)\n",
    "        # from here onwards we simply add the other part of the linear function(x*w)\n",
    "        # to the value holding the bias:\n",
    "        for i, x in enumerate(inputs):\n",
    "            # calculate remaining part of the linear function\n",
    "            self.value += x * weights[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Interestingly my code shows consistently different results than the Udacity code playground suggests that it returns.\n",
    "Even though I copied the code I developed here into there. This is strange."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Testing for sanity\n",
    "I wrote a succession of (probably overly complicated) tests to check whether I am making all this up, or if there really is something wrong with Udacity's test code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# create feed_dict from Udacity response\n",
    "def recreate_feed_dict(response):\n",
    "    \"\"\"\n",
    "    Extracts the values of the feed_dict used by Udacity for testing purposes.\n",
    "    \n",
    "    Takes as input the string returned from the Udacity Quiz in *6. Learning and Loss*\n",
    "    and returns the original feed_dict and the suggested result.\n",
    "    \n",
    "    :param response: feedback text from modal\n",
    "    :type response: str\n",
    "    :return: the feed_dict used for testing\n",
    "    :rtype: dict{str : list, str : list, str : int}\n",
    "    :return: the suggested result, according to the feedback text\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    import re\n",
    "    all_nums = re.findall(r\"[\\d]+\", response)\n",
    "    all_nums = [int(n) for n in all_nums]\n",
    "    feed_dict = {}\n",
    "    feed_dict[\"inputs\"] = all_nums[:3]\n",
    "    feed_dict[\"weights\"] = all_nums[3:6]\n",
    "    feed_dict[\"bias\"] = all_nums[6]\n",
    "    suggested_result = all_nums[-1]\n",
    "    return feed_dict, suggested_result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def use_formula(feed_dict):\n",
    "    \"\"\"Calculates the weighted sums of inputs and weights, and ultimately the linear function by adding the bias.\n",
    "    \n",
    "    Code the formula without a detour across Neurons, to make sure the error isn't there.\n",
    "    \n",
    "    value = weighted_sum(x * w) + b\n",
    "    \n",
    "    :param feed_dict: contains values for inputs, weights, and bias\n",
    "    :type feed_dict: dict{str : list, str : list, str : int}\n",
    "    :return: calculated value of the linear function using the weighted sum of inputs and weights\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    inputs = feed_dict[\"inputs\"]\n",
    "    weights = feed_dict[\"weights\"]\n",
    "    bias = feed_dict[\"bias\"]\n",
    "    value = 0\n",
    "    for x, w in zip(inputs, weights):\n",
    "        value += x * w\n",
    "    value += bias\n",
    "    return value\n",
    "\n",
    "def use_NN(input_feed_dict):\n",
    "    \"\"\"Runs a test according to Udacity's `nn.py`, using the Neuron Class I defined further up.\"\"\"\n",
    "    inputs, weights, bias = Input(), Input(), Input()\n",
    "    f = Linear(inputs, weights, bias)\n",
    "    # transforms the input_feed_dict (extracted from the error msg) into a feed_dict\n",
    "    # that consists of Neuron objects.\n",
    "    feed_dict = {\n",
    "        inputs: input_feed_dict[\"inputs\"],\n",
    "        weights: input_feed_dict[\"weights\"],\n",
    "        bias: input_feed_dict[\"bias\"]\n",
    "    }\n",
    "    graph = topological_sort(feed_dict)\n",
    "    output = forward_pass(f, graph)\n",
    "    return output\n",
    "\n",
    "def compare(value1, value2):\n",
    "    \"\"\"Checks whether two values are the same.\"\"\"\n",
    "    assert (value1 == value2), \"Problems brewing! 💥 \"\n",
    "    print(\"Life is good, the ☀️ is shining! Here you go, have an 🍏 !\")\n",
    "    \n",
    "def test_reality(feedback_msg):\n",
    "    \"\"\"Checks whether the NN code returns the same results as the simple function calculation.\"\"\"\n",
    "    feed_dict, udacity_result = recreate_feed_dict(feedback_msg)\n",
    "    nn_output = use_NN(feed_dict)\n",
    "    formula_output = use_formula(feed_dict)\n",
    "    compare(nn_output, formula_output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def test_udacity_tests(feedback_msg):\n",
    "    \"\"\"Checks whether the output of my NN code is indeed the same as Udacity's error message suggests.\"\"\"\n",
    "    feed_dict, ud_result = recreate_feed_dict(feedback_msg)\n",
    "    my_result = use_NN(feed_dict)\n",
    "    compare(my_result, ud_result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So I submitted a few times to collect the output messages. Interestingly enough, one time my code passed, so there must be an edge case that allows it to pass, while generally it fails."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "feedback_list = [\n",
    "    \"Not quite. When given x: 2, y: 5, z: 1, weight_x: 4, weight_y: 9, weight_z: 3, bias: 7, your linear neuron outputs 64\",\n",
    "    \"Not quite. When given x: 1, y: 8, z: 8, weight_x: 4, weight_y: 5, weight_z: 9, bias: 7, your linear neuron outputs 83\",\n",
    "    \"Not quite. When given x: 5, y: 9, z: 5, weight_x: 0, weight_y: 1, weight_z: 4, bias: 3, your linear neuron outputs 12\",\n",
    "    \"Not quite. When given x: 0, y: 4, z: 9, weight_x: 4, weight_y: 8, weight_z: 5, bias: 4, your linear neuron outputs 72\",\n",
    "    \"Not quite. When given x: 6, y: 3, z: 4, weight_x: 4, weight_y: 0, weight_z: 0, bias: 2, your linear neuron outputs 42\"\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Life is good, the ☀️ is shining! Here you go, have an 🍏 !\n",
      "Life is good, the ☀️ is shining! Here you go, have an 🍏 !\n",
      "Life is good, the ☀️ is shining! Here you go, have an 🍏 !\n",
      "Life is good, the ☀️ is shining! Here you go, have an 🍏 !\n",
      "Life is good, the ☀️ is shining! Here you go, have an 🍏 !\n"
     ]
    }
   ],
   "source": [
    "for msg in feedback_list:\n",
    "    test_reality(msg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": "Problems brewing! 💥 ",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-141-11cedee1b44b>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mmsg\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mfeedback_list\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m     \u001b[0mtest_suite\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmsg\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-131-c9da7299d3f6>\u001b[0m in \u001b[0;36mtest_suite\u001b[0;34m(feedback_msg)\u001b[0m\n\u001b[1;32m      2\u001b[0m     \u001b[0mfeed_dict\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mud_result\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mrecreate_feed_dict\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfeedback_msg\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mmy_result\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0muse_NN\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfeed_dict\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m     \u001b[0mcompare\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmy_result\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mud_result\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-137-14f7ef30a202>\u001b[0m in \u001b[0;36mcompare\u001b[0;34m(value1, value2)\u001b[0m\n\u001b[1;32m     36\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     37\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mcompare\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mvalue1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvalue2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 38\u001b[0;31m     \u001b[0;32massert\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mvalue1\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0mvalue2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"Problems brewing! 💥 \"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     39\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Life is good, the ☀️ is shining! Here you go, have an 🍏 !\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     40\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mAssertionError\u001b[0m: Problems brewing! 💥 "
     ]
    }
   ],
   "source": [
    "for msg in feedback_list:\n",
    "    test_suite(msg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "I think there's a problem with the test code. Please correct me if I'm wrong."
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:car]",
   "language": "python",
   "name": "conda-env-car-py"
  },
  "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": 1
}