11 - Pystruct.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Pystruct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Structured Prediction! Chains first\n",
    "from ``pystruct/examples/plot_letters.py``\n",
    "\n",
    "http://pystruct.github.io/auto_examples/plot_letters.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from pystruct.datasets import load_letters\n",
    "\n",
    "letters = load_letters()\n",
    "X, y, folds = letters['data'], letters['labels'], letters['folds']\n",
    "\n",
    "print(\"length of X: %d\" % len(X))\n",
    "print(\"shape of first data point: %s\" % (X[0].shape,))\n",
    "print(\"shape of 200th data point: %s\" % (X[200].shape,))\n",
    "\n",
    "print(\"length of y: %d\" % len(y))\n",
    "print(\"shape of first label: %s\" % (y[0].shape,))\n",
    "print(\"y[0]: %s\" % y[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "_, axes = plt.subplots(1, len(X[0]))\n",
    "for ax, x in zip(axes, X[0]):\n",
    "    ax.matshow(x.reshape(16, 8), cmap=\"gray\")\n",
    "    # (c)ommanding"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# we convert the lists to object arrays, as that makes slicing much more\n",
    "# convenient\n",
    "X, y = np.array(X), np.array(y)\n",
    "X_train, X_test = X[folds == 1], X[folds != 1]\n",
    "y_train, y_test = y[folds == 1], y[folds != 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from sklearn.svm import LinearSVC\n",
    "# Train linear SVM\n",
    "svm = LinearSVC(dual=False, C=.1)\n",
    "# flatten input\n",
    "svm.fit(np.vstack(X_train), np.hstack(y_train))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print(\"Test score with linear SVM: %f\" %\n",
    "      svm.score(np.vstack(X_test), np.hstack(y_test)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Model + Solver + Inverence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from pystruct.models import ChainCRF\n",
    "from pystruct.learners import FrankWolfeSSVM\n",
    "\n",
    "# Train linear chain CRF\n",
    "model = ChainCRF()\n",
    "ssvm = FrankWolfeSSVM(model=model, C=.1, max_iter=11)\n",
    "ssvm.fit(X_train, y_train)\n",
    "\n",
    "print(\"Test score with chain CRF: %f\" % ssvm.score(X_test, y_test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# plot some word sequenced\n",
    "abc = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "\n",
    "n_words = 4\n",
    "rnd = np.random.RandomState(1)\n",
    "selected = rnd.randint(len(y_test), size=n_words)\n",
    "max_word_len = max([len(y_) for y_ in y_test[selected]])\n",
    "fig, axes = plt.subplots(n_words, max_word_len, figsize=(10, 10))\n",
    "fig.subplots_adjust(wspace=0)\n",
    "for ind, axes_row in zip(selected, axes):\n",
    "    y_pred_svm = svm.predict(X_test[ind])\n",
    "    y_pred_chain = ssvm.predict([X_test[ind]])[0]\n",
    "    for i, (a, image, y_true, y_svm, y_chain) in enumerate(\n",
    "            zip(axes_row, X_test[ind], y_test[ind], y_pred_svm, y_pred_chain)):\n",
    "        a.matshow(image.reshape(16, 8), cmap=plt.cm.Greys)\n",
    "        a.text(0, 3, abc[y_true], color=\"#00AA00\", size=25)\n",
    "        a.text(0, 14, abc[y_svm], color=\"#5555FF\", size=25)\n",
    "        a.text(5, 14, abc[y_chain], color=\"#FF5555\", size=25)\n",
    "        a.set_xticks(())\n",
    "        a.set_yticks(())\n",
    "    for ii in range(i + 1, max_word_len):\n",
    "        axes_row[ii].set_visible(False)\n",
    "\n",
    "plt.matshow(ssvm.w[26 * 8 * 16:].reshape(26, 26))\n",
    "plt.title(\"Transition parameters of the chain CRF.\")\n",
    "plt.xticks(np.arange(25), abc)\n",
    "plt.yticks(np.arange(25), abc);\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Different models get different X!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercise\n",
    "* Use the GraphCRF model, in which each x is a tuple of features and edges so solve the sequence prediction task, see http://pystruct.github.io/user_guide.html#graphcrf set the inference_method, the default may be slow! What does \"directed\" do?\n",
    "* Use the EdgeFeatureGraphCRF model, in which each x is a tuploe of features, edges and edge features, to solve the sequence prediction task, see http://pystruct.github.io/user_guide.html#edgefeaturegraphcrf set the inference_method, the default may be slow!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# %load solutions/letters_graph_crf.py\n",
    "from pystruct.models import GraphCRF, EdgeFeatureGraphCRF\n",
    "\n",
    "def make_edges(n_nodes):\n",
    "    return np.c_[np.arange(n_nodes - 1), np.arange(1, n_nodes)]\n",
    "\n",
    "X_graph = np.array([(x, make_edges(len(x))) for x in X])\n",
    "X_graph_train, X_graph_test = X_graph[folds == 1], X_graph[folds != 1]\n",
    "\n",
    "\n",
    "graph_model = GraphCRF(inference_method=\"max-product\")\n",
    "ssvm = FrankWolfeSSVM(model=graph_model, C=.1, max_iter=11)\n",
    "ssvm.fit(X_graph_train, y_train)\n",
    "print(\"score with GraphCRF %f\" % ssvm.score(X_graph_test, y_test))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# %load solutions/letters_graph_crf.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Awesome example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# %load http://pystruct.github.io/_downloads/plot_snakes.py\n",
    "\"\"\"\n",
    "==============================================\n",
    "Conditional Interactions on the Snakes Dataset\n",
    "==============================================\n",
    "This example uses the snake dataset introduced in\n",
    "Nowozin, Rother, Bagon, Sharp, Yao, Kohli: Decision Tree Fields ICCV 2011\n",
    "\n",
    "This dataset is specifically designed to require the pairwise interaction terms\n",
    "to be conditioned on the input, in other words to use non-trival edge-features.\n",
    "\n",
    "The task is as following: a \"snake\" of length ten wandered over a grid. For\n",
    "each cell, it had the option to go up, down, left or right (unless it came from\n",
    "there). The input consists of these decisions, while the desired output is an\n",
    "annotation of the snake from 0 (head) to 9 (tail).  See the plots for an\n",
    "example.\n",
    "\n",
    "As input features we use a 3x3 window around each pixel (and pad with background\n",
    "where necessary). We code the five different input colors (for up, down, left, right,\n",
    "background) using a one-hot encoding. This is a rather naive approach, not using any\n",
    "information about the dataset (other than that it is a 2d grid).\n",
    "\n",
    "The task can not be solved using the simple DirectionalGridCRF - which can only\n",
    "infer head and tail (which are also possible to infer just from the unary\n",
    "features). If we add edge-features that contain the features of the nodes that are\n",
    "connected by the edge, the CRF can solve the task.\n",
    "\n",
    "From an inference point of view, this task is very hard.  QPBO move-making is\n",
    "not able to solve it alone, so we use the relaxed AD3 inference for learning.\n",
    "\n",
    "PS: This example runs a bit (5 minutes on 12 cores, 20 minutes on one core for me).\n",
    "But it does work as well as Decision Tree Fields ;)\n",
    "\"\"\"\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from sklearn.preprocessing import label_binarize\n",
    "from sklearn.metrics import confusion_matrix, accuracy_score\n",
    "\n",
    "from pystruct.learners import OneSlackSSVM\n",
    "from pystruct.datasets import load_snakes\n",
    "from pystruct.utils import make_grid_edges, edge_list_to_features\n",
    "from pystruct.models import EdgeFeatureGraphCRF\n",
    "\n",
    "\n",
    "def one_hot_colors(x):\n",
    "    x = x / 255\n",
    "    flat = np.dot(x.reshape(-1, 3), 2 ** np.arange(3))\n",
    "    one_hot = label_binarize(flat, classes=[1, 2, 3, 4, 6])\n",
    "    return one_hot.reshape(x.shape[0], x.shape[1], 5)\n",
    "\n",
    "\n",
    "def neighborhood_feature(x):\n",
    "    \"\"\"Add a 3x3 neighborhood around each pixel as a feature.\"\"\"\n",
    "    # we could also use a four neighborhood, that would work even better\n",
    "    # but one might argue then we are using domain knowledge ;)\n",
    "    features = np.zeros((x.shape[0], x.shape[1], 5, 9))\n",
    "    # position 3 is background.\n",
    "    features[:, :, 3, :] = 1\n",
    "    features[1:, 1:, :, 0] = x[:-1, :-1, :]\n",
    "    features[:, 1:, :, 1] = x[:, :-1, :]\n",
    "    features[:-1, 1:, :, 2] = x[1:, :-1, :]\n",
    "    features[1:, :, :, 3] = x[:-1, :, :]\n",
    "    features[:-1, :-1, :, 4] = x[1:, 1:, :]\n",
    "    features[:-1, :, :, 5] = x[1:, :, :]\n",
    "    features[1:, :-1, :, 6] = x[:-1, 1:, :]\n",
    "    features[:, :-1, :, 7] = x[:, 1:, :]\n",
    "    features[:, :, :, 8] = x[:, :, :]\n",
    "    return features.reshape(x.shape[0] * x.shape[1], -1)\n",
    "\n",
    "\n",
    "def prepare_data(X):\n",
    "    X_directions = []\n",
    "    X_edge_features = []\n",
    "    for x in X:\n",
    "        # get edges in grid\n",
    "        right, down = make_grid_edges(x, return_lists=True)\n",
    "        edges = np.vstack([right, down])\n",
    "        # use 3x3 patch around each point\n",
    "        features = neighborhood_feature(x)\n",
    "        # simple edge feature that encodes just if an edge is horizontal or\n",
    "        # vertical\n",
    "        edge_features_directions = edge_list_to_features([right, down])\n",
    "        # edge feature that contains features from the nodes that the edge connects\n",
    "        edge_features = np.zeros((edges.shape[0], features.shape[1], 4))\n",
    "        edge_features[:len(right), :, 0] = features[right[:, 0]]\n",
    "        edge_features[:len(right), :, 1] = features[right[:, 1]]\n",
    "        edge_features[len(right):, :, 0] = features[down[:, 0]]\n",
    "        edge_features[len(right):, :, 1] = features[down[:, 1]]\n",
    "        edge_features = edge_features.reshape(edges.shape[0], -1)\n",
    "        X_directions.append((features, edges, edge_features_directions))\n",
    "        X_edge_features.append((features, edges, edge_features))\n",
    "    return X_directions, X_edge_features\n",
    "\n",
    "\n",
    "print(\"Please be patient. Learning will take 5-20 minutes.\")\n",
    "snakes = load_snakes()\n",
    "X_train, Y_train = snakes['X_train'], snakes['Y_train']\n",
    "\n",
    "X_train = [one_hot_colors(x) for x in X_train]\n",
    "Y_train_flat = [y_.ravel() for y_ in Y_train]\n",
    "\n",
    "X_train_directions, X_train_edge_features = prepare_data(X_train)\n",
    "\n",
    "inference = 'qpbo'\n",
    "# first, train on X with directions only:\n",
    "crf = EdgeFeatureGraphCRF(inference_method=inference)\n",
    "ssvm = OneSlackSSVM(crf, inference_cache=50, C=.1, tol=.1, max_iter=100,\n",
    "                    n_jobs=1)\n",
    "ssvm.fit(X_train_directions, Y_train_flat)\n",
    "\n",
    "# Evaluate using confusion matrix.\n",
    "# Clearly the middel of the snake is the hardest part.\n",
    "X_test, Y_test = snakes['X_test'], snakes['Y_test']\n",
    "X_test = [one_hot_colors(x) for x in X_test]\n",
    "Y_test_flat = [y_.ravel() for y_ in Y_test]\n",
    "X_test_directions, X_test_edge_features = prepare_data(X_test)\n",
    "Y_pred = ssvm.predict(X_test_directions)\n",
    "print(\"Results using only directional features for edges\")\n",
    "print(\"Test accuracy: %.3f\"\n",
    "      % accuracy_score(np.hstack(Y_test_flat), np.hstack(Y_pred)))\n",
    "print(confusion_matrix(np.hstack(Y_test_flat), np.hstack(Y_pred)))\n",
    "\n",
    "# now, use more informative edge features:\n",
    "crf = EdgeFeatureGraphCRF(inference_method=inference)\n",
    "ssvm = OneSlackSSVM(crf, inference_cache=50, C=.1, tol=.1, switch_to='ad3',\n",
    "                    n_jobs=-1)\n",
    "ssvm.fit(X_train_edge_features, Y_train_flat)\n",
    "Y_pred2 = ssvm.predict(X_test_edge_features)\n",
    "print(\"Results using also input features for edges\")\n",
    "print(\"Test accuracy: %.3f\"\n",
    "      % accuracy_score(np.hstack(Y_test_flat), np.hstack(Y_pred2)))\n",
    "print(confusion_matrix(np.hstack(Y_test_flat), np.hstack(Y_pred2)))\n",
    "\n",
    "# plot stuff\n",
    "fig, axes = plt.subplots(2, 2)\n",
    "axes[0, 0].imshow(snakes['X_test'][0], interpolation='nearest')\n",
    "axes[0, 0].set_title('Input')\n",
    "y = Y_test[0].astype(np.int)\n",
    "bg = 2 * (y != 0)  # enhance contrast\n",
    "axes[0, 1].matshow(y + bg, cmap=plt.cm.Greys)\n",
    "axes[0, 1].set_title(\"Ground Truth\")\n",
    "axes[1, 0].matshow(Y_pred[0].reshape(y.shape) + bg, cmap=plt.cm.Greys)\n",
    "axes[1, 0].set_title(\"Prediction w/o edge features\")\n",
    "axes[1, 1].matshow(Y_pred2[0].reshape(y.shape) + bg, cmap=plt.cm.Greys)\n",
    "axes[1, 1].set_title(\"Prediction with edge features\")\n",
    "for a in axes.ravel():\n",
    "    a.set_xticks(())\n",
    "    a.set_yticks(())\n",
    "plt.show()\n"
   ]
  }
 ],
 "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": 0
}