CMAC.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cerebellar Model Articulation Controller (CMAC)\n",
    "\n",
    "# Theoretical Background\n",
    "## Formulation\n",
    "\n",
    "This is a proposed computing model based on the principles of the brain's architecture. This is similar in inspiration to multilayer perceptrons (aka. MLPs, neural networks).\n",
    "\n",
    "In a similar way to MLPs, the model can be defined as [1,2]:\n",
    "\n",
    "$$f : S \\rightarrow A$$\n",
    "$$g : A \\rightarrow P$$\n",
    "\n",
    "and $$y = \\sum A^{*}_i w_i$$\n",
    "\n",
    "Where $A$ are association cells/tiles (i.e. memory cells), $P$ are response output vectors, $S$ are the sensory input vectors.\n",
    "\n",
    "Here we essentially say, the output is the sum of all the memory cells/tiles, where we store weights in a memory table. We then learn these by filling in values of the table cells (initially set to 0).  \n",
    "By repeatedly trying to solve a task, we can adjust these weights. And learning is controlled through supervised learning (compare real vs. predicted).\n",
    "\n",
    "BUT WE NEED TO GENERALIZE! This cell architecture is prone to non-generality. Indeed, if a state would be represented by the single feature whose cell/tile it falls within, generalization would be achieved for all states in that specific tile but nonexistent to states outside it.  \n",
    "To remedy that we need a mapping function that maps a given input vector ($X=(x_1,x_2,...,x_n)$) to a **set** of cells ($A^*$) instead of a single one. Of course for this set of cells to improve generalization over a single cell, we need each memory cell to overlap with other cells such that the feature we want to represent falls in multiple cells (thus improving generalization). In order to achieve this we shift each cell by a fraction of a cell width. This coarse coding helps generalize the cells to inputs. And thus the sum becomes: (1) map inputs $X_1 \\rightarrow A_1^{*}$ and $X_2 \\rightarrow A_2^{*}$ then compute the sums of $A_1^* \\text{ and }A_2^*$ respectively.  \n",
    "We can observe an illustration of this idea in Figures 1 and 2 below [3, 4]: \n",
    "\n",
    "![cmac](images/cmac_as_table.png)\n",
    "![cmac](images/tile_coding_illustration.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Therefore in designing the mapping function, the increase of the size of $A^{*}$ will make the model more general.\n",
    "\n",
    "As only a small fraction of the table is used, we often use a hashing function.\n",
    "\n",
    "To learn this function, we compute the error and add: $\\frac{(y-\\hat{y})}{|A^{*}|}$ to each cell in $A^{*}$ where $\\hat{y}$ is the prediction ($\\sum A^{*}$) and $y$ is the ground truth. This is the learning method proposed in [5].\n",
    "\n",
    "This can be generally viewed as a 2-dimensional lookup table as shown above. However the original idea originated from receptive field in the human brain, and a more natural illustration would thus be as a neural network formulated as shown in figure 3 below [3]:\n",
    "\n",
    "![cmac](images/cmac_formulation.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The algorithm [3]\n",
    "\n",
    "Now how would we go about implementing CMAC/tilecoding ?  \n",
    "Pseudo code presented here from [3].\n",
    "\n",
    "- We start off by initializing all the arguments to the CMAC object, as listed below :\n",
    "![cmac](images/cmac_alg_init.png)\n",
    "The number of association units $n_a$ denotes the number of tilings we wish to use (each with some offset $d$ along feature dimension $j$). The input resolution describes the number of tiles/subdivisions we wish to have for each association unit.  \n",
    "Note the unconventional use of $y$ for inputs and $x$ as outputs.\n",
    "\n",
    "\n",
    "- We can now proceed to obtaining the weights associated with each tile in each association unit, for a given input vector $y$ as shown in the following function:\n",
    "![cmac](images/cmac_alg_quantize.png)\n",
    "The CMACHASH function simply gives us the weights associated to each association unit from the table indices $p^i$.  \n",
    "\n",
    "\n",
    "- Once we have these weights we can use them to actually map the specific input vector to an output, x (which ideally approximates the function we want it to by the end of training), as shown below in the function CMACMAP:\n",
    "![cmac](images/cmac_alg_map.png)\n",
    "To evaluate a specific input we would simply call the CMACMAP function.\n",
    "\n",
    "\n",
    "- Of course the CMACMAP function is called for both training and testing. We show below its use in the training procedure which essentially boils down to gradient descent:\n",
    "![cmac](images/cmac_alg_map.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CMAC vs the human brain\n",
    "Looking at Figure 3, we can correlate each section loosely to the human brain. However, these are loose correlations and do not accurately model the cerebellum. More importantly the model is fast as it can be viewed as a lookup table.\n",
    "\n",
    "#### Feature Detecting Neurons (Mossy fibers)\n",
    "The Mossy fibers are one of the two input fiber systems to the cerebellum. Therefore as the first layer (L1) in Figure 3 is the input to the CMAC architecture, drawing a parallel is fairly natural.\n",
    "\n",
    "#### Granule cells\n",
    "These cells are the most numerous cells in the brain ($\\approx3 \\times 10^{10}$ granule cells in the cerebellum\n",
    "alone). They can be said to be association cells which \"recode inputs from N inputs to at least 100N inputs\" [6].  \n",
    "We can relate this mechanism to the second layer in Figure 3 since in the CMAC architecture, a single feature links to multiple tilings/AUs.\n",
    "\n",
    "#### Purkinje cells\n",
    "Purkinje cells, as shown below, are highly branched neurons which connect to a number of other cells. They exist in a single layer over the cortex. They form a sort of tree structure over other cells. A parallel fiber below it “synapses with virtually every Purkinje dendritic tree it passes” [6]. The axons of these fibers are the only network exit from the cerebellar cortex.   \n",
    "Note that this structure relates to Layer 3 fairly intuitively. As Layer 3 in our CMAC architecture connects in a tree-like fashion to the AUs, so does the Purkinje fibers connect down to the parallel synapses below it and aggregate these potentials before passing them out of the cerebellar cortex. This is an obvious simplification of the fibers, but the parallels are noticeable.\n",
    "![cmac](images/purkinje.png) [wikipedia:Purkinje cells]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## MLP vs CMAC\n",
    "\n",
    "The difference between MLPs (Multi Layer Perceptrons) and CMAC [1] is that in MLPs, $f$ is fully connected, while CMAC restricts the associations to close neighbors.  \n",
    "CMAC is more in tune with Convolutional Neural Networks in a sense, see section CMAC vs CNNs below.\n",
    "\n",
    "## CNNs vs CMAC\n",
    "\n",
    "Indeed, Tile Coding bears some resemblance to both Convolutional Neural Networks and HMAX (Hierarchical Model and X) in several ways.  \n",
    "To demonstrate this similarity, we first look at the biological basis for CNNs/HMAX. In HMAX [7], the early layers of the visual cortex are modeled as convolutional filters which are precomputed to match those found in the visual cortex. These convolutional filters match the receptive fields found in the human brain. Receptive fields come from the foundation that each cell is activated by a small area of the visual input. In the early layers of the visual cortex, we find that the receptive fields are simple and circular (on and off depending on stimulus in one area). These cells are called simple cells.   \n",
    "Moving forward in the visual cortex, we find more complex activation patterns (complex cells) which have receptive fields responsive to lines or curves. In CNNs, these convolutional filters representing receptive fields are learned [8]. These compare to tile coding as the tiles can be thought of as square receptive fields which aggregate the input from a set of sensory inputs. As we can see, this parallels HMAX and CNNS. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Benefits of CMAC\n",
    "\n",
    "When compared to an \"equivalent\" Multi Layer Perceptron, CMAC will be faster as only the activated tiles need to be evaluated whereas the full network needs to be fed forward for the MLP.  \n",
    "Additionally, thanks to the restrictions that CMAC imposes by design on the mapping function, it effectively decreases the chance of been trapped in a local minimum during the learning process. As an additional benefit, as noted in [4], the tiling idea allows for a more intuitive setting of the learning rate hyperparameter by the user.  \n",
    "Finally, CMAC restricts the association of features in a certain neighboring range. This mapping property significantly accelerates the learning process of CMAC, which is considered its main advantage when compared to other neural network models [1].\n",
    "\n",
    "## Disadvantages\n",
    "\n",
    "As outlined in [3], CMAC exhibits a few disadvantages which may outweigh its benefits in some applications:   \n",
    "- First, by design most of the time CMAC will require many more weight parameters compared to normal MLP models (due to multiple tilings).  \n",
    "- Secondly, the local generalization mechanism may cause some training data to be incorrectly interpolated, especially when data is sparse relative to the size of the CMAC used.  \n",
    "- Finally, as CMAC is a discrete model, analytical derivatives do not exist which can be inconvenient in many cases.\n",
    "\n",
    "### Relation to Tile Coding\n",
    "As explained in [4], Tile coding is simply another term for CMAC, first introduced in the first edition of [4] (1998)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementation and Experiments\n",
    "Our implementation of CMAC/Tile Coding was done in TensorFlow.  \n",
    "Note: Our implementation is based off of [9, 10], and the plotting functions off of [10].\n",
    "\n",
    "### Function approximation\n",
    "We demonstrate our CMAC implementation with parameters resolution = 50 and n_AU =50 on a few 2-dimensional functions and compare it to a 2-layer Multi Layer Perceptron :  \n",
    "Note that for the both mean squared error graphs, each epoch is 100 training examples.\n",
    "\n",
    "- $f(\\textbf{x}) = cos(x_1) + sin(x_2)$ : \n",
    "#### CMAC\n",
    "![cmac](images/cmac_function_in_the_making.gif)\n",
    "And the associated mean squared error: \n",
    "![cmac](images/mse_cmac_sin_cos.png)\n",
    "#### MLP\n",
    "![cmac](images/mlp_function_in_the_making.gif)\n",
    "And the associated mean squared error: \n",
    "![cmac](images/mse_mlp_sin_cos.png)\n",
    "\n",
    "As we can observe, the MLP takes about 1100*100 = 110000 training examples to reach an MSE below 0.1 while CMAC only needs about 20*100 = 2000.\n",
    "\n",
    "\n",
    "- $ \\sin (\\sqrt{( (2x_0 -4)^2)} + \\sqrt{((2x_1 - 4)^2)})$:\n",
    "#### CMAC\n",
    "![cmac](images/cmac_cone_in_the_making.gif)\n",
    "And the associated mean squared error: \n",
    "![cmac](images/mse_cmac_cone.png)\n",
    "#### MLP\n",
    "![cmac](images/mlp_cone_in_the_making.gif)\n",
    "And the associated mean squared error: \n",
    "![cmac](images/mse_mlp_cone.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "[1] Xing, Frank Z. \"A Historical Review of Forty Years of Research on CMAC.\" arXiv preprint arXiv:1702.02277 (2017).\n",
    "\n",
    "[2] http://www4.cs.umanitoba.ca/~jacky/Teaching/Courses/74.795-L02/2003/Lectures/cmac.pdf\n",
    "\n",
    "[3] Smith, Russell L. Intelligent motion control with an artificial cerebellum. Diss. ResearchSpace@ Auckland, 1998.\n",
    "\n",
    "[4] Sutton, R.S., Barto, A.G. (2017). Reinforcement Learning: An Introduction (Second Edition Draft) MIT Press.\n",
    "\n",
    "[5] J.S. Albus (1975). \"A New Approach to Manipulator Control: the Cerebellar Model Articulation Controller (CMAC)\". In: Trans. ASME, Series G. Journal of Dynamic Systems, Measurement and Control, Vol. 97, pp. 220–233, 1975.\n",
    "\n",
    "[6] J.S. Albus (1978). \"A theory of cerebellar function\"\n",
    "\n",
    "[7] Henderson, Peter, and Dhirendra Singh (2013). \"Biologically Motivated Object Recognition.”\n",
    "\n",
    "[8] Rashad, https://www.quora.com/What-is-a-receptive-field-in-a-convolutional-neural-network\n",
    "\n",
    "[9] Stober, 2012. https://gist.github.com/stober/1792732\n",
    "\n",
    "[10] Pezeshki, 2017. https://github.com/mohammadpz/Theano_Tile_Coding"
   ]
  }
 ],
 "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.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}