tensorflow_fold/g3doc/quick.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TensorFlow Fold Quick Start\n",
    "\n",
    "TensorFlow Fold is a library for turning complicated Python data structures into TensorFlow Tensors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# boilerplate\n",
    "import random\n",
    "import tensorflow as tf\n",
    "sess = tf.InteractiveSession()\n",
    "import tensorflow_fold as td"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The basic elements of Fold are *blocks*. We'll start with some blocks that work on simple data types."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "scalar_block = td.Scalar()\n",
    "vector3_block = td.Vector(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Blocks are functions with associated input and output types."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<td.Scalar dtype='float32'>: PyObjectType() -> TensorType((), 'float32')\n",
      "<td.Vector dtype='float32' size=3>: PyObjectType() -> TensorType((3,), 'float32')\n"
     ]
    }
   ],
   "source": [
    "def block_info(block):\n",
    "    print(\"%s: %s -> %s\" % (block, block.input_type, block.output_type))\n",
    "    \n",
    "block_info(scalar_block)\n",
    "block_info(vector3_block)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can use `eval()` to see what a block does with its input:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array(42.0, dtype=float32)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "scalar_block.eval(42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 1.,  2.,  3.], dtype=float32)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vector3_block.eval([1,2,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Not very exciting. We can compose simple blocks together with `Record`, like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<td.Record ordered=False>: PyObjectType() -> TupleType(TensorType((3,), 'float32'), TensorType((), 'float32'))\n"
     ]
    }
   ],
   "source": [
    "record_block = td.Record({'foo': scalar_block, 'bar': vector3_block})\n",
    "block_info(record_block)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see that Fold's type system is a bit richer than vanilla TF; we have tuple types! Running a record block does what you'd expect:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([ 5.,  7.,  9.], dtype=float32), array(1.0, dtype=float32))"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "record_block.eval({'foo': 1, 'bar': [5, 7, 9]})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One useful thing you can do with blocks is wire them up to create pipelines using the `>>` operator, which performs function composition. For example, we can take our two tuple tensors and compose it with `Concat`, like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 5.,  7.,  9.,  1.], dtype=float32)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "record2vec_block = record_block >> td.Concat()\n",
    "record2vec_block.eval({'foo': 1, 'bar': [5, 7, 9]})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that because Python dicts are unordered, Fold always sorts the outputs of a record block by dictionary key. If you want to preserve order you can construct a Record block from an OrderedDict.\n",
    "\n",
    "The whole point of Fold is to get your data into TensorFlow; the `Function` block lets you convert a TITO (Tensors In, Tensors Out) function to a block:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-5., -7., -9., -1.], dtype=float32)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "negative_block = record2vec_block >> td.Function(tf.negative)\n",
    "negative_block.eval({'foo': 1, 'bar': [5, 7, 9]})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is all very cute, but where's the beef? Things start to get interesting when our inputs contain sequences of indeterminate length. The `Map` block comes in handy here:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "map_scalars_block = td.Map(td.Scalar())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There's no TF type for sequences of indeterminate length, but Fold has one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<td.Map element_block=<td.Scalar dtype='float32'>>: None -> SequenceType(TensorType((), 'float32'))\n"
     ]
    }
   ],
   "source": [
    "block_info(map_scalars_block)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Right, but you've done the TF [RNN Tutorial](https://www.tensorflow.org/tutorials/recurrent/) and even poked at [seq-to-seq](https://www.tensorflow.org/tutorials/seq2seq/). You're a wizard with [dynamic rnns](https://www.tensorflow.org/api_docs/python/tf/nn/dynamic_rnn). What does Fold offer?\n",
    "\n",
    "Well, how about jagged arrays?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<td.Map element_block=<td.Map element_block=<td.Scalar dtype='float32'>>>: None -> SequenceType(SequenceType(TensorType((), 'float32')))\n"
     ]
    }
   ],
   "source": [
    "jagged_block = td.Map(td.Map(td.Scalar()))\n",
    "block_info(jagged_block)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Fold type system is fully compositional; any block you can create can be composed with `Map` to create a sequence, or `Record` to create a tuple, or both to create sequences of tuples or tuples of sequences:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(array(2.0, dtype=float32), array(1.0, dtype=float32)),\n",
       " (array(4.0, dtype=float32), array(3.0, dtype=float32))]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "seq_of_tuples_block = td.Map(td.Record({'foo': td.Scalar(), 'bar': td.Scalar()}))\n",
    "seq_of_tuples_block.eval([{'foo': 1, 'bar': 2}, {'foo': 3, 'bar': 4}])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([array(0.0, dtype=float32),\n",
       "  array(1.0, dtype=float32),\n",
       "  array(2.0, dtype=float32),\n",
       "  array(3.0, dtype=float32),\n",
       "  array(4.0, dtype=float32),\n",
       "  array(5.0, dtype=float32),\n",
       "  array(6.0, dtype=float32)],\n",
       " [array(0.0, dtype=float32),\n",
       "  array(1.0, dtype=float32),\n",
       "  array(2.0, dtype=float32)])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tuple_of_seqs_block = td.Record({'foo': td.Map(td.Scalar()), 'bar': td.Map(td.Scalar())})\n",
    "tuple_of_seqs_block.eval({'foo': range(3), 'bar': range(7)})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Most of the time, you'll eventually want to get one or more tensors out of your sequence, for wiring up to your particular learning task. Fold has a bunch of built-in reduction functions for this that do more or less what you'd expect:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array(45.0, dtype=float32),\n",
       " array(0.0, dtype=float32),\n",
       " array(9.0, dtype=float32))"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "((td.Map(td.Scalar()) >> td.Sum()).eval(range(10)),\n",
    " (td.Map(td.Scalar()) >> td.Min()).eval(range(10)),\n",
    " (td.Map(td.Scalar()) >> td.Max()).eval(range(10)))\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The general form of such functions is `Reduce`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array(362880.0, dtype=float32)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(td.Map(td.Scalar()) >> td.Reduce(td.Function(tf.multiply))).eval(range(1,10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the order of operations is important, you should use `Fold` instead of `Reduce` (but if you can use `Reduce` you should, because it will be faster):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array(0.0416666679084301, dtype=float32),\n",
       " array(0.6666666865348816, dtype=float32))"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "((td.Map(td.Scalar()) >> td.Fold(td.Function(tf.divide), tf.ones([]))).eval(range(1,5)),\n",
    " (td.Map(td.Scalar()) >> td.Reduce(td.Function(tf.divide), tf.ones([]))).eval(range(1,5)))  # bad, not associative!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's do some learning! This is the part where \"magic\" happens; if you want a deeper understanding of what's happening here you might want to jump right to our more formal [blocks tutorial](https://github.com/tensorflow/fold/blob/master/tensorflow_fold/g3doc/blocks.md) or learn more about [running blocks in TensorFlow](https://github.com/tensorflow/fold/blob/master/tensorflow_fold/g3doc/running.md)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def reduce_net_block():\n",
    "    net_block = td.Concat() >> td.FC(20) >> td.FC(1, activation=None) >> td.Function(lambda xs: tf.squeeze(xs, axis=1))\n",
    "    return td.Map(td.Scalar()) >> td.Reduce(net_block)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `reduce_net_block` function creates a block (`net_block`) that contains a two-layer fully connected (FC) network that takes a pair of scalar tensors as input and produces a scalar tensor as output. This network gets applied in a binary tree to reduce a sequence of scalar tensors to a single scalar tensor.\n",
    "\n",
    "One thing to notice here is that we are calling [`tf.squeeze`](https://www.tensorflow.org/versions/r1.0/api_docs/python/array_ops/shapes_and_shaping#squeeze) with `axis=1`, even though the Fold output type of `td.FC(1, activation=None)` (and hence the input type of the enclosing `Function` block) is a `TensorType` with shape `(1)`. This is because all Fold blocks actually run on TF tensors with an implicit leading batch dimension, which enables execution via [*dynamic batching*](https://arxiv.org/abs/1702.02181). It is important to bear this in mind when creating `Function` blocks that wrap functions that are not applied elementwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def random_example(fn):\n",
    "    length = random.randrange(1, 10)\n",
    "    data = [random.uniform(0,1) for _ in range(length)]\n",
    "    result = fn(data)\n",
    "    return data, result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `random_example` function generates training data consisting of `(example, fn(example))` pairs, where `example` is a random list of numbers, e.g.:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([0.787305870095568,\n",
       "  0.22965378372211998,\n",
       "  0.37373230100201726,\n",
       "  0.5763790512875622,\n",
       "  0.8213490322728823,\n",
       "  0.8670031890415114],\n",
       " 3.655423227421661)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_example(sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([0.6092255329819952, 0.3401567642529808, 0.20512903038956665],\n",
       " 0.20512903038956665)"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_example(min)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def train(fn, batch_size=100):\n",
    "    net_block = reduce_net_block()\n",
    "    compiler = td.Compiler.create((net_block, td.Scalar()))\n",
    "    y, y_ = compiler.output_tensors\n",
    "    loss = tf.nn.l2_loss(y - y_)\n",
    "    train = tf.train.AdamOptimizer().minimize(loss)\n",
    "    sess.run(tf.global_variables_initializer())\n",
    "    validation_fd = compiler.build_feed_dict(random_example(fn) for _ in range(1000))\n",
    "    for i in range(2000):\n",
    "        sess.run(train, compiler.build_feed_dict(random_example(fn) for _ in range(batch_size)))\n",
    "        if i % 100 == 0:\n",
    "            print(i, sess.run(loss, validation_fd))\n",
    "    return net_block\n",
    "                 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we're going to train a neural network to approximate a reduction function of our choosing. Calling `eval()` repeatedly is super-slow and cannot exploit batch-wise parallelism, so we create a [`Compiler`](https://github.com/tensorflow/fold/blob/master/tensorflow_fold/g3doc/py/td.md#compiler). See our page on [running blocks in TensorFlow](https://github.com/tensorflow/fold/blob/master/tensorflow_fold/g3doc/running.md) for more on Compilers and how to use them effectively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/usr/local/google/home/madscience/nuke/v3/local/lib/python2.7/site-packages/tensorflow/python/ops/gradients_impl.py:91: UserWarning: Converting sparse IndexedSlices to a dense Tensor of unknown shape. This may consume a large amount of memory.\n",
      "  \"Converting sparse IndexedSlices to a dense Tensor of unknown shape. \"\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, 3709.2959)\n",
      "(100, 117.03122)\n",
      "(200, 75.517761)\n",
      "(300, 39.155235)\n",
      "(400, 10.953562)\n",
      "(500, 4.590332)\n",
      "(600, 2.8660746)\n",
      "(700, 2.0546255)\n",
      "(800, 1.573489)\n",
      "(900, 1.2537044)\n",
      "(1000, 1.0065227)\n",
      "(1100, 0.82658422)\n",
      "(1200, 0.67432761)\n",
      "(1300, 0.55223799)\n",
      "(1400, 0.46296757)\n",
      "(1500, 0.38158983)\n",
      "(1600, 0.316338)\n",
      "(1700, 0.26881805)\n",
      "(1800, 0.22481206)\n",
      "(1900, 0.20074199)\n"
     ]
    }
   ],
   "source": [
    "sum_block = train(sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array(2.006655216217041, dtype=float32)"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_block.eval([1, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Breaking news: deep neural network learns to calculate 1 + 1!!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course we've done something a little sneaky here by constructing a model that can only represent associative functions and then training it to compute an associative function. The technical term for being sneaky in machine learning is [inductive bias](https://en.wikipedia.org/wiki/Inductive_bias)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, 499.09598)\n",
      "(100, 46.026665)\n",
      "(200, 25.741219)\n",
      "(300, 18.191158)\n",
      "(400, 14.682983)\n",
      "(500, 12.306305)\n",
      "(600, 10.402517)\n",
      "(700, 8.670351)\n",
      "(800, 6.9115524)\n",
      "(900, 5.1144924)\n",
      "(1000, 3.6718786)\n",
      "(1100, 2.6184769)\n",
      "(1200, 2.0114093)\n",
      "(1300, 1.6398822)\n",
      "(1400, 1.3298371)\n",
      "(1500, 1.0525734)\n",
      "(1600, 0.77793711)\n",
      "(1700, 0.55954146)\n",
      "(1800, 0.40301239)\n",
      "(1900, 0.2982769)\n"
     ]
    }
   ],
   "source": [
    "min_block = train(min)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array(-0.6417261958122253, dtype=float32)"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_block.eval([2, -1, 4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oh noes! What went wrong? Note that we trained our network to compute `min` on positive numbers; negative numbers are outside of its input distribution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array(0.1865474432706833, dtype=float32)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_block.eval([0.3, 0.2, 0.9])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Well, that's better. What happens if you train the network on negative numbers as well as on positives? What if you only train on short lists and then evaluate the net on long ones? What if you used a `Fold` block instead of a `Reduce`? ...  Happy Folding!"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}