try.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isinstance(1, (list, tuple))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Copyright 2015 Google Inc. All Rights Reserved.\n",
    "#\n",
    "# Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "# you may not use this file except in compliance with the License.\n",
    "# You may obtain a copy of the License at\n",
    "#\n",
    "#     http://www.apache.org/licenses/LICENSE-2.0\n",
    "#\n",
    "# Unless required by applicable law or agreed to in writing, software\n",
    "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "# See the License for the specific language governing permissions and\n",
    "# limitations under the License.\n",
    "# ==============================================================================\n",
    "\n",
    "\"\"\"A very simple MNIST classifier, modified to display data in TensorBoard.\n",
    "\n",
    "See extensive documentation for the original model at\n",
    "http://tensorflow.org/tutorials/mnist/beginners/index.md\n",
    "\n",
    "See documentation on the TensorBoard specific pieces at\n",
    "http://tensorflow.org/how_tos/summaries_and_tensorboard/index.md\n",
    "\n",
    "If you modify this file, please update the excerpt in\n",
    "how_tos/summaries_and_tensorboard/index.md.\n",
    "\n",
    "\"\"\"\n",
    "from __future__ import absolute_import\n",
    "from __future__ import division\n",
    "from __future__ import print_function\n",
    "\n",
    "import tensorflow as tf\n",
    "\n",
    "from tensorflow.examples.tutorials.mnist import input_data\n",
    "\n",
    "\n",
    "flags = tf.app.flags\n",
    "FLAGS = flags.FLAGS\n",
    "flags.DEFINE_boolean('fake_data', False, 'If true, uses fake data '\n",
    "                     'for unit testing.')\n",
    "flags.DEFINE_integer('max_steps', 100, 'Number of steps to run trainer.')\n",
    "flags.DEFINE_float('learning_rate', 0.01, 'Initial learning rate.')\n",
    "\n",
    "isinstance(1, (list, tuple))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Copyright 2015 Google Inc. All Rights Reserved.\n",
    "#\n",
    "# Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "# you may not use this file except in compliance with the License.\n",
    "# You may obtain a copy of the License at\n",
    "#\n",
    "#     http://www.apache.org/licenses/LICENSE-2.0\n",
    "#\n",
    "# Unless required by applicable law or agreed to in writing, software\n",
    "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "# See the License for the specific language governing permissions and\n",
    "# limitations under the License.\n",
    "# ==============================================================================\n",
    "\"\"\"Implements the graph generation for computation of gradients.\"\"\"\n",
    "\n",
    "from __future__ import absolute_import\n",
    "from __future__ import division\n",
    "from __future__ import print_function\n",
    "\n",
    "import collections\n",
    "import warnings\n",
    "\n",
    "import numpy as np\n",
    "from six.moves import xrange  # pylint: disable=redefined-builtin\n",
    "\n",
    "from tensorflow.python.framework import dtypes\n",
    "from tensorflow.python.framework import ops\n",
    "from tensorflow.python.framework import tensor_shape\n",
    "from tensorflow.python.framework import tensor_util\n",
    "from tensorflow.python.ops import array_grad  # pylint: disable=unused-import\n",
    "from tensorflow.python.ops import array_ops\n",
    "from tensorflow.python.ops import constant_op\n",
    "from tensorflow.python.ops import control_flow_grad  # pylint: disable=unused-import\n",
    "from tensorflow.python.ops import control_flow_ops\n",
    "from tensorflow.python.ops import image_grad  # pylint: disable=unused-import\n",
    "from tensorflow.python.ops import logging_ops  # pylint: disable=unused-import\n",
    "from tensorflow.python.ops import linalg_grad  # pylint: disable=unused-import\n",
    "from tensorflow.python.ops import math_grad  # pylint: disable=unused-import\n",
    "from tensorflow.python.ops import math_ops\n",
    "from tensorflow.python.ops import linalg_ops\n",
    "from tensorflow.python.ops import functional_ops\n",
    "\n",
    "from tensorflow.python.platform import logging\n",
    "\n",
    "# Warn the user if we convert a sparse representation to dense with at\n",
    "# least this number of elements.\n",
    "_LARGE_SPARSE_NUM_ELEMENTS = 100000000\n",
    "\n",
    "isinstance(1, (list, tuple))\n",
    "\n",
    "def _IndexedSlicesToTensor(value, dtype=None, name=None, as_ref=False):\n",
    "  \"\"\"Converts an IndexedSlices object `value` to a Tensor.\n",
    "\n",
    "  NOTE(mrry): This function is potentially expensive.\n",
    "\n",
    "  Args:\n",
    "    value: An ops.IndexedSlices object.\n",
    "    dtype: The dtype of the Tensor to be returned.\n",
    "    name: Optional name to use for the returned Tensor.\n",
    "    as_ref: True if a ref is requested.\n",
    "\n",
    "  Returns:\n",
    "    A dense Tensor representing the values in the given IndexedSlices.\n",
    "\n",
    "  Raises:\n",
    "    ValueError: If the IndexedSlices does not have the same dtype.\n",
    "  \"\"\"\n",
    "  _ = as_ref\n",
    "  if dtype and not dtype.is_compatible_with(value.dtype):\n",
    "    raise ValueError(\n",
    "        \"Tensor conversion requested dtype %s for IndexedSlices with dtype %s\" %\n",
    "        (dtype.name, value.dtype.name))\n",
    "  if value.dense_shape is None:\n",
    "    raise ValueError(\n",
    "        \"Tensor conversion requested for IndexedSlices without dense_shape: %s\"\n",
    "        % str(value))\n",
    "  # TODO(mrry): Consider adding static shape information to\n",
    "  # IndexedSlices, to avoid using numpy here.\n",
    "  dense_shape_value = tensor_util.constant_value(value.dense_shape)\n",
    "  if dense_shape_value is not None:\n",
    "    num_elements = np.prod(dense_shape_value)\n",
    "    if num_elements >= _LARGE_SPARSE_NUM_ELEMENTS:\n",
    "      warnings.warn(\n",
    "          \"Converting sparse IndexedSlices to a dense Tensor with %d elements. \"\n",
    "          \"This may consume a large amount of memory.\" % num_elements)\n",
    "  else:\n",
    "    warnings.warn(\n",
    "        \"Converting sparse IndexedSlices to a dense Tensor of unknown shape. \"\n",
    "        \"This may consume a large amount of memory.\")\n",
    "  return math_ops.unsorted_segment_sum(value.values,\n",
    "                                       value.indices,\n",
    "                                       value.dense_shape[0],\n",
    "                                       name=name)\n",
    "\n",
    "\n",
    "ops.register_tensor_conversion_function(ops.IndexedSlices,\n",
    "                                        _IndexedSlicesToTensor)\n",
    "\n",
    "\n",
    "def _MarkReachedOps(from_ops, reached_ops):\n",
    "  \"\"\"Mark all ops reached from \"from_ops\".\n",
    "\n",
    "  Args:\n",
    "    from_ops: list of Operations.\n",
    "    reached_ops: list of booleans, indexed by operation id.\n",
    "  \"\"\"\n",
    "  queue = collections.deque()\n",
    "  queue.extend(from_ops)\n",
    "  while queue:\n",
    "    op = queue.popleft()\n",
    "    if not reached_ops[op._id]:\n",
    "      reached_ops[op._id] = True\n",
    "      for output in op.outputs:\n",
    "        queue.extend(output.consumers())\n",
    "\n",
    "\n",
    "def _GatherInputs(to_ops, reached_ops):\n",
    "  \"\"\"List all inputs of to_ops that are in reached_ops.\n",
    "\n",
    "  Args:\n",
    "    to_ops: list of Operations.\n",
    "    reached_ops: list of booleans, indexed by operation id.\n",
    "\n",
    "  Returns:\n",
    "    The list of all inputs of to_ops that are in reached_ops.\n",
    "    That list includes all elements of to_ops.\n",
    "  \"\"\"\n",
    "  inputs = []\n",
    "  queue = collections.deque()\n",
    "  queue.extend(to_ops)\n",
    "  while queue:\n",
    "    op = queue.popleft()\n",
    "    # We are interested in this op.\n",
    "    if reached_ops[op._id]:\n",
    "      inputs.append(op)\n",
    "      # Clear the boolean so we won't add the inputs again.\n",
    "      reached_ops[op._id] = False\n",
    "      for inp in op.inputs:\n",
    "        queue.append(inp.op)\n",
    "  return inputs\n",
    "\n",
    "\n",
    "def _GetGradsDevice(op, colocate_gradients_with_ops):\n",
    "  \"\"\"Gets the device to which to assign gradients of \"op\".\n",
    "\n",
    "  Args:\n",
    "    op: an Operation.\n",
    "    colocate_gradients_with_ops: If True, try colocating gradients with the\n",
    "      corresponding op.\n",
    "\n",
    "  Returns:\n",
    "    A device string.\n",
    "  \"\"\"\n",
    "  if colocate_gradients_with_ops and op.device:\n",
    "    return op.device\n",
    "  else:\n",
    "    return \"\"\n",
    "\n",
    "\n",
    "def _PendingCount(graph, to_ops, from_ops):\n",
    "  \"\"\"Initialize the pending count for ops between two lists of Operations.\n",
    "\n",
    "  'pending_count[op._id]' indicates the number of backprop inputs\n",
    "  to this operation.\n",
    "\n",
    "  Args:\n",
    "    graph: a Graph.\n",
    "    to_ops: list of Operations.\n",
    "    from_ops: list of Operations.\n",
    "\n",
    "  Returns:\n",
    "    A tuple containing: (1) a list of integers indexed by operation id,\n",
    "    indicating the number of backprop inputs to this operation, and (2)\n",
    "    a boolean which is True if any of the ops in between from_ops and to_ops\n",
    "    contain control flow loops.\n",
    "  \"\"\"\n",
    "  # Mark reachable ops from from_ops.\n",
    "  reached_ops = [False] * (graph._last_id + 1)\n",
    "  for op in to_ops:\n",
    "    reached_ops[op._id] = True\n",
    "  _MarkReachedOps(from_ops, reached_ops)\n",
    "\n",
    "  # Mark between ops.\n",
    "  between_ops = [False] * (graph._last_id + 1)\n",
    "  between_op_list = []\n",
    "  queue = collections.deque()\n",
    "  queue.extend(to_ops)\n",
    "  while queue:\n",
    "    op = queue.popleft()\n",
    "    # We are interested in this op.\n",
    "    if reached_ops[op._id]:\n",
    "      between_ops[op._id] = True\n",
    "      between_op_list.append(op)\n",
    "      # Clear the boolean so we won't add the inputs again.\n",
    "      reached_ops[op._id] = False\n",
    "      for inp in op.inputs:\n",
    "        queue.append(inp.op)\n",
    "\n",
    "  # 'loop_state' is None if there are no while loops.\n",
    "  loop_state = control_flow_ops.MaybeCreateControlFlowState(between_op_list,\n",
    "                                                            between_ops)\n",
    "\n",
    "  # Initialize pending count for between ops.\n",
    "  pending_count = [0] * (graph._last_id + 1)\n",
    "  for op in between_op_list:\n",
    "    for x in op.inputs:\n",
    "      if between_ops[x.op._id]:\n",
    "        pending_count[x.op._id] += 1\n",
    "    for x in op.control_inputs:\n",
    "      if between_ops[x._id]:\n",
    "        pending_count[x._id] += 1\n",
    "\n",
    "  return pending_count, loop_state\n",
    "\n",
    "\n",
    "def _AsList(x):\n",
    "  return x if isinstance(x, (list, tuple)) else [x]\n",
    "\n",
    "\n",
    "def _DefaultGradYs(grad_ys, ys, colocate_gradients_with_ops):\n",
    "  \"\"\"Fill in default values for grad_ys.\n",
    "\n",
    "  Args:\n",
    "    grad_ys: List of gradients, can contain None.\n",
    "    ys: List of tensors.\n",
    "    colocate_gradients_with_ops: If True, try colocating gradients with\n",
    "      the corresponding op.\n",
    "\n",
    "  Returns:\n",
    "    A list of gradients to use, without None.\n",
    "\n",
    "  Raises:\n",
    "    ValueError: If one of the grad_ys is invalid.\n",
    "  \"\"\"\n",
    "  if len(grad_ys) != len(ys):\n",
    "    raise ValueError(\"Passed %d grad_ys for %d ys\" % (len(grad_ys), len(ys)))\n",
    "  grad_ys = ops.convert_n_to_tensor_or_indexed_slices(grad_ys, name=\"grad_y\")\n",
    "  for i in xrange(len(grad_ys)):\n",
    "    grad_y = grad_ys[i]\n",
    "    y = ys[i]\n",
    "    if grad_y is None:\n",
    "      with ops.device(_GetGradsDevice(y.op, colocate_gradients_with_ops)):\n",
    "        grad_ys[i] = array_ops.fill(\n",
    "            array_ops.shape(y),\n",
    "            constant_op.constant(1, dtype=y.dtype))\n",
    "    else:\n",
    "      if grad_y.dtype != y.dtype:\n",
    "        raise ValueError(\"Y and ys_grad must be of the same type, \"\n",
    "                         \"not y: %s, ys_grad: %s \" %\n",
    "                         (dtypes.as_dtype(y.dtype).name,\n",
    "                          dtypes.as_dtype(grad_y.dtype).name))\n",
    "  return grad_ys\n",
    "\n",
    "\n",
    "def _IsFloat(tensor):\n",
    "  dtype = dtypes.as_dtype(tensor.dtype)\n",
    "  return dtype.base_dtype in (dtypes.float32, dtypes.float64)\n",
    "\n",
    "\n",
    "def _VerifyGeneratedGradients(grads, op):\n",
    "  \"\"\"Verify that gradients are valid in number and type.\n",
    "\n",
    "  Args:\n",
    "    grads: List of generated gradients.\n",
    "    op: Operation for which the gradients where generated.\n",
    "\n",
    "  Raises:\n",
    "    ValueError: if the gradients are invalid.\n",
    "  \"\"\"\n",
    "  if len(grads) != len(op.inputs):\n",
    "    raise ValueError(\"Num gradients %d generated for op %s do not match num \"\n",
    "                     \"inputs %d\" % (len(grads), op.node_def, len(op.inputs)))\n",
    "  for i in xrange(len(grads)):\n",
    "    grad = grads[i]\n",
    "    inp = op.inputs[i]\n",
    "    if grad is not None:\n",
    "      if not grad.dtype.is_compatible_with(inp.dtype):\n",
    "        raise ValueError(\"Gradient type %s generated for op %s does \"\n",
    "                         \"not match input type %s\" %\n",
    "                         (dtypes.as_dtype(grad.dtype).name, op.node_def,\n",
    "                          dtypes.as_dtype(inp.dtype).name))\n",
    "\n",
    "\n",
    "def _StopOps(from_ops, pending_count):\n",
    "  \"\"\"The set of ops that terminate the gradient computation.\n",
    "\n",
    "  This computes the frontier of the forward graph *before* which backprop\n",
    "  should stop. Operations in the returned set will not be differentiated.\n",
    "  This set is defined as the subset of `from_ops` containing ops that have\n",
    "  no predecessor in `from_ops`. `pending_count` is the result of\n",
    "  `_PendingCount(g, xs, from_ops)`. An 'op' has predecessors in `from_ops`\n",
    "  iff pending_count[op._id] > 0.\n",
    "\n",
    "  Args:\n",
    "    from_ops: list of Operations.\n",
    "    pending_count: List of integers, indexed by operation id.\n",
    "\n",
    "  Returns:\n",
    "    The set of operations.\n",
    "  \"\"\"\n",
    "  stop_ops = set()\n",
    "  for op in from_ops:\n",
    "    is_stop_op = True\n",
    "    for inp in op.inputs:\n",
    "      if pending_count[inp.op._id] > 0:\n",
    "        is_stop_op = False\n",
    "        break\n",
    "    if is_stop_op:\n",
    "      stop_ops.add(op._id)\n",
    "  return stop_ops\n",
    "\n",
    "\n",
    "store_activations_set = set()\n",
    "\n",
    "import copy\n",
    "from tensorflow import Operation\n",
    "def recomputed_op(op):\n",
    "    print('copying ' + op.name)\n",
    "    print(store_activations_set)\n",
    "    if op in store_activations_set:\n",
    "        return op\n",
    "\n",
    "    if op in recomputed_op.cache:\n",
    "        return recomputed_op.cache[op]\n",
    "    \n",
    "    print('copying ' + op.name)\n",
    "    inputs = recomputed_inputs(op)\n",
    "    # Copy op.\n",
    "    op_node_def = copy.deepcopy(op.node_def)\n",
    "    op_node_def.name = op_node_def.name + '_copy'\n",
    "    op_def = copy.deepcopy(op._op_def)\n",
    "#                     p_copy = Operation(p_node_def, p._graph, p._inputs, p._control_inputs, p._input_types, p._original_op,\n",
    "#                p._op_def)\n",
    "\n",
    "#     op_copy = Operation(op_node_def, op._graph, inputs, output_types=op._output_types, input_types=op._input_types,\n",
    "#                        original_op=op, op_def=op_op_def)\n",
    "    op_copy = Operation(op_node_def, op._graph, inputs, output_types=op._output_types, input_types=op._input_types,\n",
    "                        control_inputs=op._control_inputs, original_op=op, op_def=op_def)\n",
    "    #Use Graph's hidden methods to add the op\n",
    "    ops.get_default_graph()._add_op(op_copy)\n",
    "    ops.get_default_graph()._record_op_seen_by_control_dependencies(op_copy)\n",
    "    for device_function in reversed(ops.get_default_graph()._device_function_stack):\n",
    "        op_copy._set_device(device_function(op_copy))\n",
    "\n",
    "    recomputed_op.cache[op] = op_copy\n",
    "\n",
    "    return op_copy\n",
    "recomputed_op.cache = {}\n",
    "\n",
    "            \n",
    "def recomputed_inputs(op):\n",
    "    # For an operation return the list of its inputs.\n",
    "    # The function copies parts of the computational graph to recompute the result\n",
    "    # of each op which is not marked as op.store_activations=True\n",
    "    inputs = []\n",
    "    for x in op.inputs:\n",
    "        if x in store_activations_set:\n",
    "            inputs.append(x)\n",
    "        else:\n",
    "            input_op = recomputed_op(x.op)\n",
    "            output_idx = x.op.outputs.index(x)\n",
    "            inputs.append(input_op.outputs[output_idx])\n",
    "    return inputs\n",
    "\n",
    "\n",
    "######################################################################################################\n",
    "def gradients(ys,\n",
    "              xs,\n",
    "              grad_ys=None,\n",
    "              name=\"gradients\",\n",
    "              colocate_gradients_with_ops=False,\n",
    "              gate_gradients=False,\n",
    "              aggregation_method=None):\n",
    "  \"\"\"Constructs symbolic partial derivatives of `ys` w.r.t. x in `xs`.\n",
    "\n",
    "  `ys` and `xs` are each a `Tensor` or a list of tensors.  `grad_ys`\n",
    "  is a list of `Tensor`, holding the gradients received by the\n",
    "  `ys`. The list must be the same length as `ys`.\n",
    "\n",
    "  `gradients()` adds ops to the graph to output the partial\n",
    "  derivatives of `ys` with respect to `xs`.  It returns a list of\n",
    "  `Tensor` of length `len(xs)` where each tensor is the `sum(dy/dx)`\n",
    "  for y in `ys`.\n",
    "\n",
    "  `grad_ys` is a list of tensors of the same length as `ys` that holds\n",
    "  the initial gradients for each y in `ys`.  When `grad_ys` is None,\n",
    "  we fill in a tensor of '1's of the shape of y for each y in `ys`.  A\n",
    "  user can provide their own initial `grad_ys` to compute the\n",
    "  derivatives using a different initial gradient for each y (e.g., if\n",
    "  one wanted to weight the gradient differently for each value in\n",
    "  each y).\n",
    "\n",
    "  Args:\n",
    "    ys: A `Tensor` or list of tensors to be differentiated.\n",
    "    xs: A `Tensor` or list of tensors to be used for differentiation.\n",
    "    grad_ys: Optional. A `Tensor` or list of tensors the same size as\n",
    "      `ys` and holding the gradients computed for each y in `ys`.\n",
    "    name: Optional name to use for grouping all the gradient ops together.\n",
    "      defaults to 'gradients'.\n",
    "    colocate_gradients_with_ops: If True, try colocating gradients with\n",
    "      the corresponding op.\n",
    "    gate_gradients: If True, add a tuple around the gradients returned\n",
    "      for an operations.  This avoids some race conditions.\n",
    "    aggregation_method: Specifies the method used to combine gradient terms.\n",
    "      Accepted values are constants defined in the class `AggregationMethod`.\n",
    "\n",
    "  Returns:\n",
    "    A list of `sum(dy/dx)` for each x in `xs`.\n",
    "\n",
    "  Raises:\n",
    "    LookupError: if one of the operations between `x` and `y` does not\n",
    "      have a registered gradient function.\n",
    "    ValueError: if the arguments are invalid.\n",
    "\n",
    "  \"\"\"\n",
    "  ys = _AsList(ys)\n",
    "  xs = _AsList(xs)\n",
    "  if grad_ys is None:\n",
    "    grad_ys = [None] * len(ys)\n",
    "  else:\n",
    "    grad_ys = _AsList(grad_ys)\n",
    "  with ops.op_scope(ys + xs + grad_ys, name, \"gradients\"):\n",
    "    ys = ops.convert_n_to_tensor_or_indexed_slices(ys, name=\"y\")\n",
    "    xs = ops.convert_n_to_tensor_or_indexed_slices(xs, name=\"x\")\n",
    "    grad_ys = _DefaultGradYs(grad_ys, ys, colocate_gradients_with_ops)\n",
    "\n",
    "    # The approach we take here is as follows: Create a list of all ops in the\n",
    "    # subgraph between the ys and xs.  Visit these ops in reverse order of ids\n",
    "    # to ensure that when we visit an op the gradients w.r.t its outputs have\n",
    "    # been collected.  Then aggregate these gradients if needed, call the op's\n",
    "    # gradient function, and add the generated gradients to the gradients for\n",
    "    # its input.\n",
    "\n",
    "    # Initialize the pending count for ops in the connected subgraph from ys\n",
    "    # to the xs.\n",
    "    to_ops = [t.op for t in ys]\n",
    "    from_ops = [t.op for t in xs]\n",
    "    pending_count, loop_state = _PendingCount(ops.get_default_graph(),\n",
    "                                              to_ops, from_ops)\n",
    "\n",
    "    # Iterate over the collected ops.\n",
    "    #\n",
    "    # grads: op => list of gradients received on each output endpoint of the\n",
    "    # op.  The gradients for each endpoint are initially collected as a list.\n",
    "    # When it is time to call the op's gradient function, for each endpoint we\n",
    "    # aggregate the list of received gradients into a Add() Operation if there\n",
    "    # is more than one.\n",
    "    grads = {}\n",
    "\n",
    "    # Add the initial gradients for the ys.\n",
    "    for y, grad_y in zip(ys, grad_ys):\n",
    "      _SetGrad(grads, y, grad_y)\n",
    "\n",
    "    # Initialize queue with to_ops.\n",
    "    queue = collections.deque()\n",
    "    # Add the ops in 'to_ops' into the queue.\n",
    "    to_ops_set = set()\n",
    "    for op in to_ops:\n",
    "      # 'ready' handles the case where one output gradient relies on\n",
    "      # another output's gradient.\n",
    "      # pylint: disable=protected-access\n",
    "      ready = (pending_count[op._id] == 0)\n",
    "      if ready and op._id not in to_ops_set:\n",
    "        to_ops_set.add(op._id)\n",
    "        queue.append(op)\n",
    "\n",
    "    if loop_state:\n",
    "      # The \"unused\" exits of the loops are added to ys. As an example,\n",
    "      # people often write:\n",
    "      #         v1, _ = While(p, b, [x1, x2])\n",
    "      #         result = gradients(v1, x1)\n",
    "      # The exit node of x2 is not included by the betweenness analysis.\n",
    "      # But we need it if x2 is involved in computing v1. So we add it\n",
    "      # back in backprop with a zeros_like gradient.\n",
    "      loop_exits = loop_state.GetAllLoopExits()\n",
    "      for y in loop_exits:\n",
    "        if pending_count[y.op._id] == 0 and y.op._id not in to_ops_set:\n",
    "          if _IsFloat(y):\n",
    "            # Floating-point outputs get a zero gradient.\n",
    "            _SetGrad(grads, y, loop_state.ZerosLikeForExit(y))\n",
    "          queue.append(y.op)\n",
    "\n",
    "    # The set of 'from_ops'.\n",
    "    stop_ops = _StopOps(from_ops, pending_count)\n",
    "    while queue:\n",
    "      # generate gradient subgraph for op.\n",
    "      op = queue.popleft()\n",
    "      with ops.device(_GetGradsDevice(op, colocate_gradients_with_ops)):\n",
    "        if loop_state:\n",
    "          loop_state.EnterGradWhileContext(op)\n",
    "        out_grads = _AggregatedGrads(grads, op, loop_state, aggregation_method)\n",
    "        grad_fn = None\n",
    "\n",
    "        # pylint: disable=protected-access\n",
    "        is_func_call = ops.get_default_graph()._is_function(op.type)\n",
    "#         print(loop_state, op.name)\n",
    "        \n",
    "        # pylint: enable=protected-access\n",
    "\n",
    "        if not is_func_call and any(out_grads) and op._id not in stop_ops:\n",
    "        # pylint: enable=protected-access\n",
    "          # A grad_fn must be defined, either as a function or as None\n",
    "          # for ops that do not have gradients.\n",
    "          try:\n",
    "            grad_fn = ops.get_gradient_function(op)\n",
    "          except LookupError:\n",
    "            raise LookupError(\n",
    "                \"No gradient defined for operation '%s' (op type: %s)\" %\n",
    "                (op.name, op.type))\n",
    "        if (grad_fn or is_func_call) and any(out_grads):\n",
    "          # NOTE: If _AggregatedGrads didn't compute a value for the i'th\n",
    "          # output, it means that the cost does not depend on output[i],\n",
    "          # therefore dC/doutput[i] is 0.\n",
    "          for i, out_grad in enumerate(out_grads):\n",
    "            if not out_grad and _IsFloat(op.outputs[i]):\n",
    "              # Only floating-point outputs get a zero gradient. Gradient\n",
    "              # functions should ignore the gradient for other outputs.\n",
    "              if loop_state:\n",
    "                out_grads[i] = loop_state.ZerosLike(op, i)\n",
    "              else:\n",
    "                out_grads[i] = array_ops.zeros_like(op.outputs[i])\n",
    "          with ops.name_scope(op.name + \"_grad\"):\n",
    "            # pylint: disable=protected-access\n",
    "            with ops.get_default_graph()._original_op(op):\n",
    "              # pylint: enable=protected-access\n",
    "              wrapped_op = op\n",
    "              if loop_state:\n",
    "                wrapped_op = loop_state.MakeWrapper(op)\n",
    "              if is_func_call:\n",
    "                # For function call ops, we add a 'SymbolicGradient'\n",
    "                # node to the graph to compute gradients.\n",
    "#                 if op.name == 'Wx_b_/add':\n",
    "#                     asdkj\n",
    "#                     p = op.inputs[0].op\n",
    "#                     p_node_def = copy.deepcopy(p.node_def)\n",
    "#                     p_node_def.name = p_node_def.name + '_copy'\n",
    "#                     inputs = [Operation(p_node_def, p._graph, p._inputs, p._control_inputs, p._input_types, p._original_op,\n",
    "#                p._op_def)]\n",
    "#                 else:\n",
    "#                     inputs = op.inputs\n",
    "                \n",
    "########################################################################################################\n",
    "                f_in = [x for x in inputs] + out_grads\n",
    "                f_types = [x.dtype for x in inputs]\n",
    "                # pylint: disable=protected-access\n",
    "                in_grads = _AsList(functional_ops._symbolic_gradient(\n",
    "                    f_in, f_types, op.type))\n",
    "                # pylint: enable=protected-access\n",
    "              else:\n",
    "                if op.name == 'Wx_b_/add':\n",
    "                    import copy\n",
    "                    store_activations_set.add(op.inputs[1])\n",
    "                    for x in op.inputs[0].op.inputs: store_activations_set.add(x)\n",
    "                    inputs = recomputed_inputs(op)\n",
    "                    \n",
    "            ######################################################################################\n",
    "                    op_node_def = copy.deepcopy(op.node_def)\n",
    "                    op_node_def.name = op_node_def.name + '_copy'\n",
    "                    op_def = copy.deepcopy(op._op_def)\n",
    "                    op_copy = Operation(op_node_def, op._graph, inputs, input_types=op._input_types,\n",
    "                                        output_types=op._output_types, control_inputs=op._control_inputs,\n",
    "                                        original_op=op, op_def=op_def)\n",
    "                    wrapped_op = op_copy\n",
    "                in_grads = _AsList(grad_fn(wrapped_op, *out_grads))\n",
    "              _VerifyGeneratedGradients(in_grads, op)\n",
    "              if gate_gradients and len(tuple(filter(None, in_grads))) > 1:\n",
    "                in_grads = control_flow_ops.tuple(in_grads)\n",
    "          logging.vlog(1, \"Gradient for '\" + op.name + \"'\")\n",
    "          logging.vlog(1, \"  in  --> %s\",\n",
    "                       \", \".join([x.name for x in out_grads if x]))\n",
    "          logging.vlog(1, \"  out --> %s\",\n",
    "                       \", \".join([x.name for x in in_grads if x]))\n",
    "        else:\n",
    "          # If no grad_fn is defined or none of out_grads is available,\n",
    "          # just propagates a list of None backwards.\n",
    "          in_grads = [None] * len(op.inputs)\n",
    "        for t_in, in_grad in zip(op.inputs, in_grads):\n",
    "#           asdf\n",
    "          if in_grad:\n",
    "            _SetGrad(grads, t_in, in_grad)\n",
    "        if loop_state:\n",
    "          loop_state.ExitGradWhileContext(op)\n",
    "\n",
    "      # update pending count for the inputs of op.\n",
    "      # pylint: disable=protected-access\n",
    "      for x in op.inputs:\n",
    "        pending_count[x.op._id] -= 1\n",
    "        ready = (pending_count[x.op._id] == 0)\n",
    "        if loop_state and not ready:\n",
    "          ready = (pending_count[x.op._id] > 0 and\n",
    "                   control_flow_ops.IsLoopSwitch(x.op))\n",
    "        if ready:\n",
    "          queue.append(x.op)\n",
    "      for x in op.control_inputs:\n",
    "        pending_count[x._id] -= 1\n",
    "        if pending_count[x._id] is 0:\n",
    "          queue.append(x)\n",
    "      # pylint: enable=protected-access\n",
    "  return [_GetGrad(grads, x) for x in xs]\n",
    "\n",
    "\n",
    "def _SetGrad(grads, t, grad):\n",
    "  \"\"\"Sets gradient \"grad\" in \"grads\" for tensor \"t\".\"\"\"\n",
    "  op = t.op\n",
    "  op_grads = grads.get(op)\n",
    "  if not op_grads:\n",
    "    op_grads = [[] for _ in xrange(len(op.outputs))]\n",
    "    grads[op] = op_grads\n",
    "  t_grads = op_grads[t.value_index]\n",
    "  if isinstance(t_grads, list):\n",
    "    t_grads.append(grad)\n",
    "  else:\n",
    "    assert control_flow_ops.IsLoopSwitch(op)\n",
    "    op_grads[t.value_index] = grad\n",
    "\n",
    "\n",
    "def _GetGrad(grads, t):\n",
    "  \"\"\"Gets gradient for tensor \"t\".\"\"\"\n",
    "  op = t.op\n",
    "  op_grads = grads.get(op)\n",
    "  if not op_grads:\n",
    "    return None\n",
    "  t_grad = op_grads[t.value_index]\n",
    "  assert not isinstance(t_grad, list), (\n",
    "      \"gradients list should have been aggregated by now.\")\n",
    "  return t_grad\n",
    "\n",
    "\n",
    "def _GetGrads(grads, op):\n",
    "  \"\"\"Gets all gradients for op.\"\"\"\n",
    "  if op in grads:\n",
    "    return grads[op]\n",
    "  else:\n",
    "    return [[] for _ in xrange(len(op.outputs))]\n",
    "\n",
    "\n",
    "def _HandleNestedIndexedSlices(grad):\n",
    "  assert isinstance(grad, ops.IndexedSlices)\n",
    "  if isinstance(grad.values, ops.Tensor):\n",
    "    return grad\n",
    "  else:\n",
    "    assert isinstance(grad.values, ops.IndexedSlices)\n",
    "    g = _HandleNestedIndexedSlices(grad.values)\n",
    "    return ops.IndexedSlices(\n",
    "        g.values, array_ops.gather(grad.indices, g.indices), g.dense_shape)\n",
    "\n",
    "\n",
    "def _AccumulatorShape(inputs):\n",
    "  shape = tensor_shape.unknown_shape()\n",
    "  for i in inputs:\n",
    "    if isinstance(i, ops.Tensor):\n",
    "      shape = shape.merge_with(i.get_shape())\n",
    "  return shape\n",
    "\n",
    "\n",
    "class AggregationMethod(object):\n",
    "  \"\"\"A class listing aggregation methods used to combine gradients.\n",
    "\n",
    "  Computing partial derivatives can require aggregating gradient\n",
    "  contributions. This class lists the various methods that can\n",
    "  be used to combine gradients in the graph:\n",
    "\n",
    "  *  `ADD_N`: All of the gradient terms are summed as part of one\n",
    "     operation using the \"AddN\" op. It has the property that all\n",
    "     gradients must be ready before any aggregation is performed.\n",
    "  *  `DEFAULT`: The system-chosen default aggregation method.\n",
    "  \"\"\"\n",
    "  ADD_N = 0\n",
    "  DEFAULT = ADD_N\n",
    "  # The following are experimental and may not be supported in future releases.\n",
    "  EXPERIMENTAL_TREE = 1\n",
    "  EXPERIMENTAL_ACCUMULATE_N = 2\n",
    "\n",
    "\n",
    "def _AggregatedGrads(grads, op, loop_state, aggregation_method=None):\n",
    "  \"\"\"Get the aggregated gradients for op.\n",
    "\n",
    "  Args:\n",
    "    grads: The map of memoized gradients.\n",
    "    op: The op to get gradients for.\n",
    "    loop_state: An object for maintaining the state of the while loops in the\n",
    "                graph. It is of type ControlFlowState. None if the graph\n",
    "                contains no while loops.\n",
    "    aggregation_method: Specifies the method used to combine gradient terms.\n",
    "      Accepted values are constants defined in the class `AggregationMethod`.\n",
    "\n",
    "  Returns:\n",
    "    A list of gradients, one per each output of `op`. If the gradients\n",
    "      for a particular output is a list, this function aggregates it\n",
    "      before returning.\n",
    "\n",
    "  Raises:\n",
    "    TypeError: if the incoming grads are not Tensors or IndexedSlices.\n",
    "    ValueError: if the arguments are invalid.\n",
    "\n",
    "  \"\"\"\n",
    "  if aggregation_method is None:\n",
    "    aggregation_method = AggregationMethod.DEFAULT\n",
    "  if aggregation_method not in [AggregationMethod.ADD_N,\n",
    "                                AggregationMethod.EXPERIMENTAL_TREE,\n",
    "                                AggregationMethod.EXPERIMENTAL_ACCUMULATE_N]:\n",
    "    raise ValueError(\n",
    "        \"Invalid aggregation_method specified %s.\" % aggregation_method)\n",
    "  out_grads = _GetGrads(grads, op)\n",
    "  for i, out_grad in enumerate(out_grads):\n",
    "    if loop_state:\n",
    "      if isinstance(out_grad, (ops.Tensor, ops.IndexedSlices)):\n",
    "        assert control_flow_ops.IsLoopSwitch(op)\n",
    "        continue\n",
    "    # Grads have to be Tensors or IndexedSlices\n",
    "    if not all([isinstance(g, (ops.Tensor, ops.IndexedSlices))\n",
    "                for g in out_grad if g]):\n",
    "      raise TypeError(\"gradients have to be either all Tensors \"\n",
    "                      \"or all IndexedSlices\")\n",
    "    # Aggregate multiple gradients, and convert [] to None.\n",
    "    if out_grad:\n",
    "      if all([isinstance(g, ops.Tensor) for g in out_grad if g]):\n",
    "        tensor_shape = _AccumulatorShape(out_grad)\n",
    "        if len(out_grad) < 2:\n",
    "          used = \"nop\"\n",
    "          out_grads[i] = out_grad[0]\n",
    "        elif (aggregation_method == AggregationMethod.EXPERIMENTAL_ACCUMULATE_N\n",
    "              and len(out_grad) > 2 and tensor_shape.is_fully_defined()):\n",
    "          # The benefit of using AccumulateN is that its inputs can be combined\n",
    "          # in any order and this can allow the expression to be evaluated with\n",
    "          # a smaller memory footprint.  When used with gpu_allocator_retry,\n",
    "          # it is possible to compute a sum of terms which are much larger than\n",
    "          # total GPU memory.\n",
    "          # AccumulateN can currently only be used if we know the shape for\n",
    "          # an accumulator variable.  If this is not known, or if we only have\n",
    "          # 2 grads then we fall through to the \"tree\" case below.\n",
    "          used = \"accumulate_n\"\n",
    "          out_grads[i] = math_ops.accumulate_n(out_grad)\n",
    "        elif aggregation_method in [AggregationMethod.EXPERIMENTAL_TREE,\n",
    "                                    AggregationMethod.EXPERIMENTAL_ACCUMULATE_N\n",
    "                                   ]:\n",
    "          # Aggregate all gradients by doing pairwise sums: this may\n",
    "          # reduce performance, but it can improve memory because the\n",
    "          # gradients can be released earlier.\n",
    "          #\n",
    "          # TODO(vrv): Consider replacing this with a version of\n",
    "          # tf.AddN() that eagerly frees its inputs as soon as they are\n",
    "          # ready, so the order of this tree does not become a problem.\n",
    "          used = \"tree\"\n",
    "          with ops.name_scope(op.name + \"_gradient_sum\"):\n",
    "            running_sum = out_grad[0]\n",
    "            for grad in out_grad[1:]:\n",
    "              running_sum = math_ops.add_n([running_sum, grad])\n",
    "            out_grads[i] = running_sum\n",
    "        else:\n",
    "          used = \"add_n\"\n",
    "          out_grads[i] = math_ops.add_n(out_grad)\n",
    "        logging.vlog(2, \"  _AggregatedGrads %d x %s using %s\", len(out_grad),\n",
    "                     tensor_shape, used)\n",
    "      else:\n",
    "        out_grad = math_ops._as_indexed_slices_list([g for g in out_grad if g])\n",
    "        out_grad = [_HandleNestedIndexedSlices(x) for x in out_grad]\n",
    "        # Form IndexedSlices out of the concatenated values and\n",
    "        # indices.\n",
    "        out_grads[i] = ops.IndexedSlices(\n",
    "            array_ops.concat(0, [x.values for x in out_grad]),\n",
    "            array_ops.concat(0, [x.indices\n",
    "                                 for x in out_grad]), out_grad[0].dense_shape)\n",
    "    else:\n",
    "      out_grads[i] = []\n",
    "  return out_grads\n",
    "\n",
    "\n",
    "# TODO(vrv): Make this available when we want to make it public.\n",
    "def _hessian_vector_product(ys, xs, v):\n",
    "  \"\"\"Multiply the Hessian of `ys` wrt `xs` by `v`.\n",
    "\n",
    "  This is an efficient construction that uses a backprop-like approach\n",
    "  to compute the product between the Hessian and another vector. The\n",
    "  Hessian is usually too large to be explicitly computed or even\n",
    "  represented, but this method allows us to at least multiply by it\n",
    "  for the same big-O cost as backprop.\n",
    "\n",
    "  Implicit Hessian-vector products are the main practical, scalable way\n",
    "  of using second derivatives with neural networks. They allow us to\n",
    "  do things like construct Krylov subspaces and approximate conjugate\n",
    "  gradient descent.\n",
    "\n",
    "  Example: if `y` = 1/2 `x`^T A `x`, then `hessian_vector_product(y,\n",
    "  x, v)` will return an expression that evaluates to the same values\n",
    "  as (A + A.T) `v`.\n",
    "\n",
    "  Args:\n",
    "    ys: A scalar value, or a tensor or list of tensors to be summed to\n",
    "        yield a scalar.\n",
    "    xs: A list of tensors that we should construct the Hessian over.\n",
    "    v: A list of tensors, with the same shapes as xs, that we want to\n",
    "       multiply by the Hessian.\n",
    "\n",
    "  Returns:\n",
    "    A list of tensors (or if the list would be length 1, a single tensor)\n",
    "    containing the product between the Hessian and `v`.\n",
    "\n",
    "  Raises:\n",
    "    ValueError: `xs` and `v` have different length.\n",
    "\n",
    "  \"\"\"\n",
    "\n",
    "  # Validate the input\n",
    "  length = len(xs)\n",
    "  if len(v) != length:\n",
    "    raise ValueError(\"xs and v must have the same length.\")\n",
    "\n",
    "  # First backprop\n",
    "  grads = gradients(ys, xs)\n",
    "\n",
    "  assert len(grads) == length\n",
    "  elemwise_products = [math_ops.mul(grad_elem, array_ops.stop_gradient(v_elem))\n",
    "                       for grad_elem, v_elem in zip(grads, v)\n",
    "                       if grad_elem is not None]\n",
    "\n",
    "  # Second backprop\n",
    "  return gradients(elemwise_products, xs)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Extracting /tmp/data/train-images-idx3-ubyte.gz\n",
      "Extracting /tmp/data/train-labels-idx1-ubyte.gz\n",
      "Extracting /tmp/data/t10k-images-idx3-ubyte.gz\n",
      "Extracting /tmp/data/t10k-labels-idx1-ubyte.gz\n",
      "copying Wx_b_/MatMul\n",
      "set([<tf.Tensor 'Variable/read:0' shape=(10,) dtype=float32>, <tf.Tensor 'x-input:0' shape=(?, 784) dtype=float32>, <tf.Tensor 'weights/read:0' shape=(784, 10) dtype=float32>])\n",
      "copying Wx_b_/MatMul\n",
      "[<tf.Tensor 'Wx_b_/MatMul_copy:0' shape=<unknown> dtype=float32>, <tf.Tensor 'Variable/read:0' shape=(10,) dtype=float32>]\n",
      "Accuracy at step 0: 0.098\n",
      "Accuracy at step 10: 0.7404\n",
      "Accuracy at step 20: 0.8041\n",
      "Accuracy at step 30: 0.814\n",
      "Accuracy at step 40: 0.8421\n",
      "Accuracy at step 50: 0.8381\n",
      "Accuracy at step 60: 0.8518\n",
      "Accuracy at step 70: 0.8403\n",
      "Accuracy at step 80: 0.8066\n",
      "Accuracy at step 90: 0.8624\n"
     ]
    },
    {
     "ename": "SystemExit",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "An exception has occurred, use %tb to see the full traceback.\n",
      "\u001b[1;31mSystemExit\u001b[0m\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "To exit: use 'exit', 'quit', or Ctrl-D.\n"
     ]
    }
   ],
   "source": [
    "\n",
    "def main(_):\n",
    "  # Import data\n",
    "  mnist = input_data.read_data_sets('/tmp/data/', one_hot=True,\n",
    "                                    fake_data=FLAGS.fake_data)\n",
    "\n",
    "  sess = tf.InteractiveSession()\n",
    "\n",
    "  # Create the model\n",
    "  x = tf.placeholder(tf.float32, [None, 784], name='x-input')\n",
    "  W = tf.Variable(tf.zeros([784, 10]), name='weights')\n",
    "  b = tf.Variable(tf.zeros([10], name='bias'))\n",
    "  b.store_out_activations = True\n",
    "\n",
    "  # Use a name scope to organize nodes in the graph visualizer\n",
    "  with tf.name_scope('Wx_b_'):\n",
    "    y = tf.nn.softmax(tf.matmul(x, W) + b)\n",
    "\n",
    "  # Add summary ops to collect data\n",
    "  _ = tf.histogram_summary('weights', W)\n",
    "  _ = tf.histogram_summary('biases', b)\n",
    "  _ = tf.histogram_summary('y', y)\n",
    "\n",
    "  # Define loss and optimizer\n",
    "  y_ = tf.placeholder(tf.float32, [None, 10], name='y-input')\n",
    "  # More name scopes will clean up the graph representation\n",
    "  with tf.name_scope('xent'):\n",
    "    cross_entropy = -tf.reduce_sum(y_ * tf.log(y))\n",
    "    _ = tf.scalar_summary('cross entropy', cross_entropy)\n",
    "  with tf.name_scope('train'):\n",
    "        variables = tf.trainable_variables()\n",
    "        grads = gradients(cross_entropy, variables, gate_gradients=True)\n",
    "        vars_and_grads = zip(grads, variables)\n",
    "        train_step = tf.train.GradientDescentOptimizer(\n",
    "            FLAGS.learning_rate).apply_gradients(vars_and_grads)\n",
    "\n",
    "  with tf.name_scope('test'):\n",
    "    correct_prediction = tf.equal(tf.argmax(y, 1), tf.argmax(y_, 1))\n",
    "    accuracy = tf.reduce_mean(tf.cast(correct_prediction, tf.float32))\n",
    "    _ = tf.scalar_summary('accuracy', accuracy)\n",
    "\n",
    "  # Merge all the summaries and write them out to /tmp/mnist_logs\n",
    "  merged = tf.merge_all_summaries()\n",
    "  writer = tf.train.SummaryWriter('/tmp/mnist_logs', sess.graph_def)\n",
    "  tf.initialize_all_variables().run()\n",
    "\n",
    "  # Train the model, and feed in test data and record summaries every 10 steps\n",
    "\n",
    "  for i in range(FLAGS.max_steps):\n",
    "    if i % 10 == 0:  # Record summary data and the accuracy\n",
    "      if FLAGS.fake_data:\n",
    "        batch_xs, batch_ys = mnist.train.next_batch(\n",
    "            100, fake_data=FLAGS.fake_data)\n",
    "        feed = {x: batch_xs, y_: batch_ys}\n",
    "      else:\n",
    "        feed = {x: mnist.test.images, y_: mnist.test.labels}\n",
    "      result = sess.run([merged, accuracy], feed_dict=feed)\n",
    "      summary_str = result[0]\n",
    "      acc = result[1]\n",
    "      writer.add_summary(summary_str, i)\n",
    "      print('Accuracy at step %s: %s' % (i, acc))\n",
    "    else:\n",
    "      batch_xs, batch_ys = mnist.train.next_batch(\n",
    "          100, fake_data=FLAGS.fake_data)\n",
    "      feed = {x: batch_xs, y_: batch_ys}\n",
    "      sess.run(train_step, feed_dict=feed)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "  tf.app.run()"
   ]
  }
 ],
 "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.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}