distributedwordreps.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# -*- coding: utf-8 -*-"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Distributed word representations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This codelab is about methods for creating effective distributed semantic word representations. Here, \"distributed\" just means that the representations are vectors of real numbers, and these models are also often called __vector space models__ (VSMs). My focus is largely on methods derived from co-occurrence patterns in text, but the section [Supervised signals](#Supervised-signals) illustrates a simple method for imbuing distributional word vectors with label information.\n",
    "\n",
    "A usage note: the term __distributional representatation__ is sometimes reserved for those derived purely from count data, and __distributed representation__ is sometimes reserved for those that involve some kind of supervised optimization.  Here, I use  __distributed representation__ in its most general form. As we will see, many models blur the supervised/distributional distinction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code and data requirements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Download or clone [this Github repository](https://github.com/cgpotts/cs224u) so that you have all the files it includes. \n",
    "\n",
    "Download [the data distribution for this unit](https://web.stanford.edu/class/cs224u/data/distributedwordreps-data.zip), unpack it, and place it in the directory containing the above Github directory.\n",
    "\n",
    "In addition, make sure you have the following installed:\n",
    "\n",
    "* [Numpy, Scipy, and matplotlib](http://www.scipy.org/install.html). (Mac users: I suggest [the Scipy Superpack](http://stronginference.com/ScipySuperpack/))\n",
    "* [scikit.learn](http://scikit-learn.org/)\n",
    "\n",
    "If you want to work in and modify this notebook, you should also install [the latest iPython](http://ipython.org)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contents\n",
    "\n",
    "0. [Distributional matrices](#Distributional-matrices)\n",
    "0. [Vector comparison](#Vector comparison)\n",
    "    0. [Euclidean distance](#Euclidean-distance)\n",
    "    0. [Length normalization](#Length-normalization)\n",
    "    0. [Cosine distance](#Cosine-distance)\n",
    "    0. [Matching-based methods](#Matching-based-methods)\n",
    "    0. [Summary](#Summary)\n",
    "0. [Distributional neighbors](#Distributional-neighbors)    \n",
    "0. [Matrix reweighting](#Matrix-reweighting)\n",
    "    0. [Normalization](#Normalization)\n",
    "    0. [Pointwise Mutual Information](#Pointwise-Mutual-Information)\n",
    "    0. [TF-IDF](#TF-IDF)\n",
    "0. [Dimensionality reduction](#Dimensionality-reduction)\n",
    "0. [Visualization](#Visualization)\n",
    "0. [The semantic orientation method](#The-semantic-orientation-method)\n",
    "0. [Word-sense ambiguities](#Word-sense-ambiguities)\n",
    "0. [GloVe word representations](#GloVe-word-representations)\n",
    "0. [Supervised signals](#Supervised-signals)\n",
    "    0. [Shallow neural network model](#Shallow-neural-network-model)\n",
    "    0. [Logical operator example](#Logical-operator-example)\n",
    "    0. [Sentiment lexicon example](#Sentiment-lexicon-example)\n",
    "    0. [ Word-level inference relations](#Word-level-inference-relations)\n",
    "0. [Word similarity evaluation](#Word-similarity-evaluation)\n",
    "0. [Word analogies evaluation](#Word-analogies-evaluation)\n",
    "0. [Exercises](#Exercises)\n",
    "    0. [Exploratory and open-ended](#Exploratory-and-open-ended)\n",
    "    0. [Straightforward](#Straightforward)\n",
    "    0. [Challenging](#Challenging)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import os\n",
    "import sys\n",
    "import csv\n",
    "import copy\n",
    "import random\n",
    "import itertools\n",
    "from operator import itemgetter\n",
    "from collections import defaultdict\n",
    "\n",
    "# Make sure you've got Numpy and Scipy installed:\n",
    "import numpy as np\n",
    "import scipy\n",
    "import scipy.spatial.distance\n",
    "from numpy.linalg import svd\n",
    "\n",
    "# For visualization:\n",
    "from tsne import tsne # See http://lvdmaaten.github.io/tsne/#implementations\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# For clustering in the 'Word-sense ambiguities' section:\n",
    "from sklearn.cluster import AffinityPropagation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Distributional matrices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a basic recipe for building a word $\\times$ word matrix:\n",
    "    \n",
    "0. Define a notion of co-occurrence context. This could be an entire document, a paragraph, a sentence, a clause, an NP — whatever domain seems likely to capture the associations you care about.\n",
    "0. Scan through your corpus building a dictionary $d$ mapping word-pairs to counts. Every time a pair of words $w$ and $w'$ occur in the same context (as you defined it in 1),  increment $d[(w, w')]$ by $1$.\n",
    "0. Using the count dictionary $d$ that you collected in 2, establish your full vocabulary $V$, an ordered list of words types. For large collections of documents, $|V|$ will typically be huge. You will probably want to winnow the vocabulary at this point. You might do this by filtering to a specific subset, or just imposing a minimum count threshold. You might impose a minimum count threshold even if $|V|$ is small &mdash; for words with very low counts, you simply don't have enough evidence to say anything interesting.\n",
    "0. Now build a matrix $M$ of dimension $|V| \\times |V|$. Both the rows and the columns of $M$ represent words. Each cell $M[i, j]$ is filled with the count $d[(w_i, w_j)]$.\n",
    "\n",
    "For different design matrices, the procedure differs slightly. For example, if you are building a word $\\times$ document matrix, then the rows of $M$ represent words and the columns of $M$ represent documents. The scan in step 2 then just keeps track of (_word_, _document_) pairs &mdash; compiling the number of times that _word_ appears in _document_. Such matrices are often used in information retrieval, because the columns are multi-set representations of documents. They are much sparser than the the word $\\times$ word matrices we will work with here. (In my experience, they yield lower quality lexicons, but others have reported good results with them.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This codebook is distributed with two pre-computed matrices of co-occurrence counts in IMDB move reviews. The `build` function allows you to read them in:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def build(src_filename, delimiter=',', header=True, quoting=csv.QUOTE_MINIMAL):    \n",
    "    reader = csv.reader(file(src_filename), delimiter=delimiter, quoting=quoting)\n",
    "    colnames = None\n",
    "    if header:\n",
    "        colnames = reader.next()\n",
    "        colnames = colnames[1: ]\n",
    "    mat = []    \n",
    "    rownames = []\n",
    "    for line in reader:        \n",
    "        rownames.append(line[0])            \n",
    "        mat.append(np.array(map(float, line[1: ])))\n",
    "    return (np.array(mat), rownames, colnames)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's read these in now for use in later examples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ww = build('distributedwordreps-data/imdb-wordword.csv')\n",
    "wd = build('distributedwordreps-data/imdb-worddoc.csv')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are some great pre-computed matrices available online too. These aren't matrices of counts, but rather more abstract values computed using methods like those under discussion here. Just for kicks, load in the GloVe vectors \n",
    "included in the data distribution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "glv = build('distributedwordreps-data/glove.6B.50d.txt', delimiter=' ', header=False, quoting=csv.QUOTE_NONE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vector comparison"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vector comparisons form the heart of our analyses in this context. For the most part, we are interested in measuring the _distance_ between vectors. The guiding idea is that semantically related words should be close together in the vector spaces we build, and semantically unrelated words should be far apart.\n",
    "\n",
    "The [scipy.spatial.distance](http://docs.scipy.org/doc/scipy-0.14.0/reference/spatial.distance.html) module has a lot of vector comparison methods, so you might check them out if you want to go beyond the functions defined and explored here. Read the documentation closely, though: many of those methods are defined only for binary vectors, whereas the VSMs we'll use allow all float values in principle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Euclidean distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The most basic and intuitive distance measure between vectors is __euclidean distance__. The euclidean distance between two vectors $u$ and $v$ of dimension $n$ is \n",
    "\n",
    "$$\\sqrt{\\sum_{i=1}^{n} |u_{i}-v_{i}|^2}$$ \n",
    "\n",
    "In two-dimensions, this corresponds to the length of the most direct line between the two points. Here, we just rely on \n",
    "`scipy` to define it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def euclidean(u, v):\n",
    "    # Use scipy's method:\n",
    "    return scipy.spatial.distance.euclidean(u, v)\n",
    "    # Or define it yourself:\n",
    "    # return vector_length(u - v)    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The comment above shows how to define this measure yourself. The function used there is the __length__ of a vector $u$ of dimension $n$, which is defined as \n",
    "\n",
    "$$\\|u\\| = \\sqrt{\\sum_{i=1}^{n} u_{i}^{2}}$$ \n",
    "\n",
    "Here's the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def vector_length(u):\n",
    "    return np.sqrt(np.dot(u, u))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's the tiny vector space from the screencast on vector comparisons associated\n",
    "with this codelab:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": [
       "iVBORw0KGgoAAAANSUhEUgAAAXEAAAEACAYAAABF+UbAAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\n",
       "AAALEgAACxIB0t1+/AAAET5JREFUeJzt3X2sZHV9x/H3BxaVJ6k8FKTQLlRQQBpFRS2KV61xBQuk\n",
       "0SqND2DDH9i0Rq1WsdVN1CpqlMZEbdFF6MPSoAFdVBQrlxIpQWGBBakRqxY0LKjEUopVu9/+MbN2\n",
       "enP33jvn3jtnfrvvV7LZOWfOOfPJ7Ozn/u7vzMxJVSFJatNufQeQJHVniUtSwyxxSWqYJS5JDbPE\n",
       "JalhlrgkNWzBEk+yIcnWJFtG1h2b5MoktyTZlOSY1Y8pSZrPYiPxi4B1c9a9Hbikqp4E/MNwWZLU\n",
       "gwVLvKquAx6Ys/onwAFJdgMOmOd+SdKEZLFPbCZZC2yqquOHy48GbgQeC/wAOLGqHlzdmJKk+XQ5\n",
       "sbkB+DCDUfjHgE+saCJJ0pJ1GYnfCxxRVQ8n2Qe4q6oOmWc/v5RFkjqoqix12zUdjn8NcBrwj8Dp\n",
       "wNUrEWQSkqyvqvV955hrGnOZaWnMtHTTmGtKM401AF7sLYYbgeuBxye5O8nZwLuAM5LcCpwCvLtr\n",
       "WEnS8iw4Eq+qM3dw147WS5ImaFf7xOZs3wF2YLbvAPOY7TvAPGb7DjCP2b4DzGO27wA7MNt3gHnM\n",
       "9h1guRY9sdn5wElN25y4JE27cbtzVxuJS9JOxRKXpIZZ4pLUMEtckhpmiUtSwyxxSWqYJS5JDbPE\n",
       "JalhlrgkNcwSl6SGWeKS1DBLXJIaZolLUsMscUlq2GJX9tmQZGuSLXPWn53k60luT3L+6kaUJO3I\n",
       "YiPxi4B1oyuSPBf4A+CZVfVE4AOrlE2StIgFS7yqrgMemLP6XOA9VfXz4Tb3r1I2SdIiusyJHwWc\n",
       "nOTmJNcmOWGlQ0mSlmbBCyUvsM+RwEnA7zCYTnnefBsmWT+yOFtVsx0eT5J2WklmgJnO+y92jc0k\n",
       "a4FNVXX8cPkLwIer6vPD5R8AR1bVT+fs5zU2JWlMk7jG5hXAKRl4OvDtuQUuSZqMxd5iuBG4Hjg6\n",
       "yd1JzgY+zmBK5V+BTwBvXfWUkqR5LTqd0vnATqdI0tgmMZ0iaSjJ/yTZnOTWJJ9L8sS+M2nX4khc\n",
       "WoYkD1bVvsPbLwVeUlUv6zmWGuZIXOpBkgAHAp7k10R1eZ+4pP+zZ5LNwGOAPQE//KaJciQuLc/D\n",
       "VfXkqloLvBb4VM95tItxTlxahjlz4mHwXUOHVtV/9ZtMrXJOXOrPScC3LHBNknPi0vJsnxPfDfge\n",
       "8Iae82gXY4lLy1BV/h9Sr5xOkaSGWeKS1DBLXJIaZolLUsMscUlqmCUuSQ2zxCWpYYtd2WdDkq1J\n",
       "tsxz3xuTbEuy/+rFkyQtZLGR+EXAurkrkxwOvIDBJ9QkST1ZsMSr6joGX+gz1weBN69KIknSko09\n",
       "J57kdOCeqrptFfJIksYw1vc+JNkLOI/BVMovVy+w/fqRxdmqmh3n8SRpZ5dkBpjpvP9i3yeeZC2w\n",
       "qaqOT3I88GVg+1dtHgZ8Hzixqu6bs5/fJy5JYxq3O8caiVfVFuDgkQf7DvCUqvrxOMeRJK2Mxd5i\n",
       "uBG4Hjg6yd1Jzp6zyepcFkiStCRenk2SpoiXZ5OkXYglLkkNs8QlqWGWuCQ1zBKXpIZZ4pLUMEtc\n",
       "khpmiUtSwyxxSWqYJS5JDbPEJalhlrgkNcwSl6SGWeKS1DBLXJIaZolLUsMWLfEkG5JsTbJlZN37\n",
       "k9yZ5OYkFyTZb3VjSpLms5SR+EXAujnrvgQcBzwV2Bt46wrnkiQtwaIlXlXXAQ/MWXd1VW2rqm3A\n",
       "Fxlc9V6SNGErMSd+DvCZFTiOJGlMa5azc5K3AQ9W1WU7uH/9yOJsVc0u5/EkaWeTZAaY6bz/Uq52\n",
       "n2QtsKmqjh9ZdxaDUfjzq+qn8+zj1e4laUzjdmenkXiSdcCbgJPnK3BJ0mQsOhJPshF4DnAgsBV4\n",
       "B4N3ozwC+PFws3+pqtfO2c+RuCSNadzuXNJ0yiSCSJLG704/sSlJDbPEJalhlrgkNcwSl6SGWeKS\n",
       "1DBLXJIaZolLUsMscUlqmCUuSQ2zxCWpYZa4JDXMEpekhlnikiYmyWOSXJTkliR3JPlckqP6ztUy\n",
       "S1zSRCQJ8HkGX139pKo6DngncGi/ydq2rMuzSdIYngv8rKr+ZvuKqrqhxzw7hQVH4kk2JNmaZMvI\n",
       "un2TXJHktiSXJ9ln9WNK2gk8Ebip7xA7m8WmUy4C1s1Z9xfA9VX1W8ANwJ+vRjBJO53VuQLNLm7B\n",
       "Eq+q64AH5qw+Dbh4ePti4IxVyCVp53MH8JS+Q+xsupzYPLiqtg5vbwUOXsE8knZSVfUV4JFJztm+\n",
       "LsnTkpzcY6zmLevdKTW4QKe/IklaqlOAk5LcmuR24O3A93vO1LQu707ZmuSQqro3yWOB+3a0YZL1\n",
       "I4uzVTXb4fEk7SSq6sfAWX3nmCZJZoCZzvsvdrX7JGuBTVV1/HD5fcCPqur8JG8BfqWq3jLPfl7t\n",
       "XpLGNG53LljiSTYCzwEOYDDifjvwKeBvgSOBbwOvrKr/XG4QSdIKl/gkg0iSxu9OP3YvSQ2zxCWp\n",
       "YZa4JDXMEpekhlniktQwS1ySGmaJS1LDLHFJapglLkkNs8QlqWGWuCQ1zBKXpIZZ4pLUMEtckhpm\n",
       "iUtSwyxxSWpY5xJPck6S65PclOSClQwlSVqaTiWeZH/gPOAFwNOAo5O8cCWDSZIW1+Vq9wAPAwH2\n",
       "Gy7vBTywIokkSUvWaSReVQ8D5wLfBe4FvlpVN65gLknSEnSdTjkI+ChwLLAWeGaSU1cwlyRpCbpO\n",
       "p5wI3FBVdwEkuQw4Gfjc6EZJ1o8szlbVbMfHk6SdUpIZYKbz/lXV5UEfDdzMoMwfAi4D/qqq/mlk\n",
       "m6qqdA0mSbuicbuz00i8qv4jybuAyxmc1LwKuKbLsSRJ3XUaiS/pwI7EJWls43ann9iUpIZZ4pLU\n",
       "MEtckhpmiUtSwyxxSWqYJS5JDbPEJalhlrgkNcwSl6SGWeKS1DBLXJIaZolLUsMscUlqmCUuSQ2z\n",
       "xCWpYZa4JDWsc4kn2TvJxUk2J/lGkmesZDBJ0uK6XigZ4CPAtVX16iRrgL1XKJMkaYm6Xih5P2Bz\n",
       "VR25wDZenk2SxjSpy7MdAdyf5JNJbk9yYZI9Ox5LktRR1+mUNcDTgHcB5wJ/DbwUuGR0oyTrRxZn\n",
       "q2q24+NJ0k4pyQww03n/jtMphwBbquqg4fKLgFdV1Zkj2zidIkljmsh0SlXdC9yV5OlJdgNOBb7c\n",
       "5ViSpO46jcQBkhzNYPrkQGAL8IqqemjkfkfikjSmcbuzc4mvdBBJ0uTenSJJmgKWuCQ1zBKXpIZZ\n",
       "4pLUMEtckhpmiUtSwyxxSWqYJS5JDbPEJalhlrgkNcwSl6SGWeKS1DBLXJIatkuWeJIzkmxL8vi+\n",
       "s0jScuySJQ6cCVw5/FuSmrXLfZ94kn2A24GTgS9W1TE9R5KkX5ro94kn2T3J5iSblnOcCTsduKqq\n",
       "/h24P8kJfQeSpK6WO53yOuAbwOoM51fHmcBlw9uX4ZSKpIYt5xqbhwGfBN4NvKGqfnfO/VM3nZJk\n",
       "f+Bu4H4GP3h2B6qqfqPXYJI0NMnplA8BbwK2LeMYk/YS4JKqWltVR1TVrwPfSfLsvoNJUhdruuyU\n",
       "5MXAfVW1OcnMAtutH1mcrarZLo+3gl4OvHfOuk8P1183+TiSdnXDDp3pvH+X6ZQkfwm8EvgF8Cjg\n",
       "0cCnq+pVI9tM3XSKJE27cbtz2W8xTPIc4E9bmBOXpGk30bcYjmjp3SmStNPY5T7sI0nTrK+RuCSp\n",
       "B5a4JDXMEpekhlniktQwS1ySGmaJS1LDLHFJapglLkkNs8QlqWGWuCQ1zBKXpIZZ4pLUMEtckhpm\n",
       "iUtSwyxxSWqYJS5JDetc4kkOT3JNkjuSzCY5awVzSZKWoPOVfZIcAhxSVbckORC4HXhuVd05vN8r\n",
       "+0jSmCZ2ZZ+qureqbhne/iHwNeDQrseTJI1vRebEkzwOOA64YSWOJ0lamjXLPUCSfYBLgddX1UNz\n",
       "7ls/sjhbVbPLfTxJ2pkkmQFmOu+/nKvdJ9kDuBL4QlVdMOc+58QlaUzjdudyTmwGuBj4YVW9YblB\n",
       "JEmTLfFnAf8M3AZsP8hbq+qqLkEkSRMs8ZUOIkma4FsMJUn9s8QlqWGWuCQ1zBKXpIZZ4pLUMEtc\n",
       "khpmiUtSwyxxSWqYJS5JDbPEJalhlrgkNcwSl6SGWeKS1DBLXJIaZolLUsM6l3iSk5PcnOS2JH+8\n",
       "kqEkSUvTqcST7A5sAH4PeArwh0mOWclgq2F4QdKpM425zLQ0Zlq6acw1jZnG1XUkfiJwV1V9t6p+\n",
       "zuBq96evXKxVM9N3gB2Y6TvAPGb6DjCPmb4DzGOm7wDzmOk7wA7M9B1gHjN9B1iuriX+a8DdI8v3\n",
       "DNdJkiaoa4mvzoU5JUlj6XSh5CTPANZX1brh8luBbVV1/sg2Fr0kdbDqV7tPsgb4JvB84AfAjcCZ\n",
       "VXXn2AeTJHW2pstOVfWLJK8BLh8e40ILXJImr9NIXJI0HVblE5vT9kGgJIcnuSbJHUlmk5zVd6bt\n",
       "kuyeZHOSTX1nAUiyd5KLh5m+MTz/0Xemc5Jcn+SmJBf0mGNDkq1Jtoys2zfJFcPX+uVJ9pmCTO9P\n",
       "cufw/+AFSfbrO9PIfW9Msi3J/tOQKcnZSb6e5PYk5+9o/0nmSnJskiuT3JJk06KfwamqFf0D7A7c\n",
       "BawF9gBuAY5Z6ccZM9MhwJOGtw8E7u0700i2NwB/D3y27yzDPBcDrxneXgPs13Oe/YHvAHszGHR8\n",
       "HnhhT1meDTwZ2DKy7n3Am4e3/wx47xRkesHwudoNuHAaMg3XHw5cNfz33L/vTMBzgauBPYbLB03J\n",
       "a+pS4PeHt88ENi50jNUYiU/dB4Gq6t6qumV4+4fA14BD+8wEkOQw4BTg48CSz0avluGI7dlVtQEG\n",
       "5z6q6ic9x3qYwXOzH7AnsBfwQB9Bquq6eR77NAY/+Bj+fUbfmarq6qraVlXbgC8Ch/WdaeiDwJsn\n",
       "mWW7HWQ6F3jPsKeoqvunJNdPgAOS7AYcMM/9/89qlPhUfxAoyeOA44Ab+s4CfAh4E7Ct7yBDRwD3\n",
       "J/nk8NfLC5Ps2WegqnqYwX+27zL4DeqrVXVjn5nmOLiqtg5vbwUO7jPMPM4BPtN3iCSnA/dU1W19\n",
       "ZxlxFLB96vfaJCf0HWjoTcDrGJT3HzH4DW+HVqPEp/ZM6XC+8lLg9VX1UM9ZXgzcV1WbmYJR+NAa\n",
       "4GnAp4d/PxJ4aZ+BkhwEfBQ4lsEU3TOTnNpnph2pwe+/U/P6T/I24MGquqznHHsB5wHvGF3dU5xR\n",
       "a4AjgZOADwz/TIMNwIcZjMI/BnxioY1Xo8S/z2Dua7vDGYzGe5VkDwbl9HdV1fvIBPht4LQk3wE2\n",
       "As9LcknPme4BflRVm4Yj4I3Ai3rOdCJwQ1XdVVU/Ai4DTu4506itSQ4BSPJY4L6e8wAwPHl/CvCK\n",
       "nqMA/CaDH8C3Dl/vhwE3JfnVXlMNXu+XVtXDVbUJeEKSR/WcCeBZwIaq+gWDAl/w9b4aJf514Kgk\n",
       "a5M8AngZ8NlVeJwlSxIGT8YdVdXbuxtGVdV5VXV4VR0BvBz4SlW9qudM9wJ3JXn6cD7uVODLfWYC\n",
       "rgOemmT/JI9k8EPlSz1nGvVZ4NXD268GrugxCwBJ1jH4lfy0qvpp33mqaktVHVxVRwxf7/cAJ1RV\n",
       "3z/wrgBOycDTgW9Pw/MFXMPgXAsMzideveDWq3TG9TnAZmAL8CeTPuM7T55nMZh3vmWYazOwru9c\n",
       "c56vaXl3ytEMzhfcxeDDXHtPQaazgGsZnJB+J7BbTzk2MviE8n8zOO9zNrAvgzK4bfh87dNTpp8N\n",
       "M70G+BbwvZHX+kf6fp7m3P9vTP7dKfP92+3OYLrim8DtwLN6fE39bCTXccP1tzJ459oTFjqGH/aR\n",
       "pIZ5eTZJapglLkkNs8QlqWGWuCQ1zBKXpIZZ4pLUMEtckhpmiUtSw/4XhDN4qNO5D44AAAAASUVO\n",
       "RK5CYII=\n"
      ],
      "text/plain": [
       "<matplotlib.figure.Figure at 0x108960810>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "ABC = np.array([\n",
    "    [ 2.0,  4.0],  # A\n",
    "    [10.0, 15.0],  # B\n",
    "    [14.0, 10.0]]) # C\n",
    "\n",
    "def plot_ABC(m):\n",
    "    plt.plot(m[:,0], m[:,1], marker='', linestyle='')\n",
    "    plt.xlim([0,np.max(m)*1.2])\n",
    "    plt.ylim([0,np.max(m)*1.2])\n",
    "    for i, x in enumerate(['A','B','C']):\n",
    "        plt.annotate(x, m[i,:])\n",
    "\n",
    "plot_ABC(ABC)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The euclidean distances align well with the raw visual distance in the plot:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13.601470508735444"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "euclidean(ABC[0], ABC[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6.4031242374328485"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "euclidean(ABC[1], ABC[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, suppose we think of the vectors as word meanings in the vector-space sense. In that case, the values don't look good: the distributions of B and C are more or less directly opposed, suggesting very different meanings, whereas A and B are rather closely aligned, abstracting away from the fact that the first is far  less frequent than the second. In terms of the large \n",
    "models we will soon explore, A and B resemble a pair like __superb__ and __good__, which have similar meanings but very different frequencies. In contrast, B and C are like __good__ and __disappointing__ &mdash; similar overall frequencies but different distributions with respect to the overall vocabulary."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Length normalization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These affinities are immediately apparent if we normalize the vectors by their length. To do this, we use `vector_length`\n",
    "to define `length_norm`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def length_norm(u):\n",
    "    return u / vector_length(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": [
       "iVBORw0KGgoAAAANSUhEUgAAAW8AAAD7CAYAAAClvBX1AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\n",
       "AAALEgAACxIB0t1+/AAADrxJREFUeJzt3WGMZWV9x/Hvz92lxWiKm02MLitbE6xYxFLCSm0cx5Sk\n",
       "haTSUBuKmBgxdZuGjU1f+Uo26QvTpGl40VSRukhfyCaKxFVQojVjwAiyhQI1i2WttLtLNJAgqWLT\n",
       "3frvi3sWr5e5cy/LvffMM/P9JJOd55xnz/k/uTO/PPPcc85NVSFJassr+i5AkvTSGd6S1CDDW5Ia\n",
       "ZHhLUoMMb0lqkOEtSQ3auqgTJfGaREk6A1WV0W0LC+9xBWx0SfZX1f6+6+jDZh2749585jn2cRNf\n",
       "l00kqUGGtyQ1yPCev5W+C+jRSt8F9GSl7wJ6stJ3AT1aWfQJs6hnmySpzbjmLUkvx7jsdOYtSQ0y\n",
       "vCWpQYa3JDXI8JakBk0M7yQHkvwoyWNr9Pl4kkeT3J/kzbMtUZI0apqZ963AH4zbmeRK4G1VdRHw\n",
       "EeAzsylNkjTOxPCuqnuBZ9fo8h7gtq7vA8A5SV47m/IkSauZxZr3TuDYUPs4cO4MjitJGmNWb1iO\n",
       "XkDuEwQlaY5m8VTBE8Cuofa53bYXSbJ/qLlSVSszOL8kbRhJloHlif2muT0+yW7gS1X11lX2XQnc\n",
       "UFVXJrkMuKmqLluln7fHS9JLNC47J868k9wOvAvYkeQYcCOwDaCqbq6qu5MsdZcS/hT44GxLlySN\n",
       "8sFUkrSO+WAqSdpADG9JapDhLUkNMrwlqUGGtyQ1yPCWpAYZ3pLUIMNbkhpkeEtSgwxvSWqQ4a11\n",
       "K8kfJfl5kt/ouxZpvTG8tZ5dC3y5+1fSEB9MpXUpyauAfwOWgHuq6oKeS5J64YOp1JqrgK9W1X8B\n",
       "Tyf57b4LktYTw1vr1bXA57rvP4dLJ9IvcdlE606S7Qw+1PppBp+HugWoqjqv18KkHrhsopa8F/in\n",
       "qtpdVb9eVW8AfpDknX0XJq0XhrfWoz8F7hzZdke3XRIum0jSuuayiSRtIIa3JDXI8JakBhnektQg\n",
       "w1saI8n/JXk4ySNJ7kpyYd81Sad5tYk0RpL/rqpXd9//CfDeqrqm57K0yXi1iXSGkgTYAfxP37VI\n",
       "p23tuwBpHTs7ycPAa4CzAR+OpXXDmbc03s+q6uKq2g38BfD5nuuRXuCatzTGyJp3gGeB11fV8/1W\n",
       "ps3ENW/p5fld4AmDW+uFa97SeKfXvF8B/CfwVz3XI73A8JbGqCp/P7RuuWwiSQ2aGN5JlpI8lOTR\n",
       "JPtW2X92ktu6O9G+meSq+ZQqSTptzT8Lk2wBDgCXAyeAB5N8vaqODHX7APDTqro4yXnAN5IcqkVd\n",
       "xiJJm9Ckmfce4GhVPVlVJ4GDDD7Ve9hzwKuTbAO2A88b3JI0X5PCeyeDD4I97Xi37QVVdTuDD4h9\n",
       "BrgPuG6WBUqSXmzSu+kTZ9BJbgBOAa8D3grcleS8qvr5Kn33DzVXqmpl+lIlaeNLsgwsT+o3KbxP\n",
       "ALuG2rsYzL6HLQGf7m5eeCDJU8CbgMdHD1ZV+ycVJEmbWTepXTndTnLjav0mLZscBs5PsjvJWcA1\n",
       "wKGRPv8M/GGSVyR5I7C9ql4U3JKk2Vlz5l1Vp5JcD9zZ9b2lqo4k2dvtv5nBm5hvYRD0TwMfmW/J\n",
       "kiQfTCVJ65gPppKkDcTwlqQGGd6S1CDDW5IaZHhLUoMMb0lqkOEtSQ0yvCWpQYa3JDXI8JakBhne\n",
       "ktQgw1uSGmR4S1KDDG9JapDhLUkNMrwlqUGGtyQ1yPCWpAYZ3pLUIMNbkhpkeEtSgwxvSWqQ4S1J\n",
       "DTK8JalBhrckNcjwlqQGGd6S1CDDW5IaZHhLUoMMb0lqkOEtSQ0yvCWpQYa3JDVoYngnWUryUJJH\n",
       "k+wb0+fSJPcleSTJysyrlCT9klTV+J3JFuB7wOXACeBB4NqqOjLU5xzgW8DvV9XxJDuq6plVjlVV\n",
       "lVkPQNL6luQ1wN8BFwPbgCeBv6yqJ/qsqxXjsnPSzHsPcLSqnqyqk8BB4KqRPu8D7qiq4wCrBbek\n",
       "zSlJgLuBb1fVb1XVbwJ/Dby+38raNym8dwLHhtrHu23Dzge2J7k3ycNJrptlgZKa9m7gf6vqU6c3\n",
       "VNX9VfXNHmvaELZO2D9+TeUXtgHLDJZWXgl8LckXqupnox2T7B9qrlTVynRlSmrUhcC/9F1ES5Is\n",
       "M8jUNU0K7xPArqH2Lgaz72HHgK9U1Q+7Ex8GloB7Rg9WVfsnFSRpQ5lmAqgh3aR25XQ7yY2r9Zu0\n",
       "bHIYOD/J7iRnAdcAh0b6fBF4V5JXJtnO4E2Jb51h3ZI2lu8Cl/RdxEa0ZnhX1SngeuBOBn/6HKiq\n",
       "I0n2Jtnb9XkcuJVB0B8Gbqqqn8y3bEktqKpvAL+S5M9Ob+suLV7qsawNYc1LBWd6Ii8VlDal7i/y\n",
       "05cKbgF+wOBSwe/3WlgjxmWn4S1J69iZXuctSVqHDG9JapDhLUkNMrwlqUGGtyQ1yPCWpAYZ3pLU\n",
       "IMNbkhpkeEtSgwxvSWqQ4S1JDTK8JalBhrckNcjwlqQGGd6S1CDDW5IaZHhLUoMMb0lqkOEtSQ0y\n",
       "vCWpQYa3JDXI8JakBhnektQgw1uSGmR4S1KDDG9JapDhLUkNMrwlqUGGtyQ1yPCWpAYZ3pLUoInh\n",
       "nWQpyUNJHk2yb41+lyY5leTq2ZYoSRq1da2dSbYAB4DLgRPAg0m+XlVHVun3N8BXgcypVklSZ9LM\n",
       "ew9wtKqerKqTwEHgqlX67QM+Dzw94/okSauYFN47gWND7ePdthck2ckg0D/RbaqZVSdJWtWk8J4m\n",
       "iG8CPlpVxWDJxGUTSZqzNde8Gaxz7xpq72Iw+x52CXAwCcAO4IokJ6vq0OjBkuwfaq5U1cpLLViS\n",
       "NrIky8DyxH6DCfPYg2wFvgf8HvAU8B3g2tE3LIf63wp8qaq+sMq+qipn5ZL0EozLzjVn3lV1Ksn1\n",
       "wJ1d31uq6kiSvd3+m+dSrSRpTWvOvGd6ImfekvSSjctO77CUpAYZ3pLUIMNbkhpkeEtSgwxvSWqQ\n",
       "4S1JDTK8JalBhrckNcjwlqQGGd6S1CDDW5IaZHhLUoMMb0lqkOEtSQ0yvCWpQYa3JDXI8JakBhne\n",
       "ktQgw1uSGmR4S1KDDG9JapDhLUkNMrwlqUGGtyQ1yPCWpAYZ3pLUIMNbkhpkeEtSgwxvSWqQ4S1J\n",
       "DTK8JalBhrckNcjwlqQGTRXeSZaSPJTk0ST7Vtl/XZJHuq/PJrlw9qVKkk6bGN5JtgAHgKuBS4AP\n",
       "JblgpNt/AEtV9TbgHuAfZ12oJOkXppl57wGOVtWTVXUSOAhcNdyhqr5dVc91zbuAc2dbpiRp2DTh\n",
       "vRM4NtQ+3m0b58PAF19OUZKktW2dok9Ne7Ak7wbeD7xjzP79Q82VqlqZ9tiStBkkWQaWJ/WbJrxP\n",
       "ALuG2rsYzL5HT3gR8Cngiqr68WoHqqr9U5xPkjatblK7crqd5MbV+k2zbHIYOD/J7iRnAdcAh4Y7\n",
       "JHkDcAfw/qo6eoY1S5KmNHHmXVWnklwP3Nn1v6WqjiTZ2+2/GfgYsB34ZBKAk1W1Z35lS9Lmlqqp\n",
       "l7Rf3omSqqos5GSStEGMy07vsJSkBhnektQgw1uSGmR4S1KDDG9JapDhLUkNMrwlqUGGtyQ1yPCW\n",
       "pAYZ3pLUIMNbkhpkeEtSgwxvSWqQ4S1JDTK8JalBhrckNcjwlqQGGd6S1CDDW5IaZHhLUoMMb0lq\n",
       "kOEtSQ0yvCWpQYa3JDXI8JakBhnektQgw1uSGmR4S1KDDG9JapDhLUkNMrwlqUGGtyQ1aGJ4J1lK\n",
       "8lCSR5PsG9Pn493++5O8efZlSpKGrRneSbYAB4CrgUuADyW5YKTPlcDbquoi4CPAZ+ZTapuSLPdd\n",
       "Q18269gd9+bTx9gnzbz3AEer6smqOgkcBK4a6fMe4DaAqnoAOCfJa2deabuW+y6gR8t9F9CT5b4L\n",
       "6Mly3wX0aHnRJ5wU3juBY0Pt4922SX3OffmlSZLGmRTeNeVxcob/T5J0BrZO2H8C2DXU3sVgZr1W\n",
       "n3O7bS+SZFOGepIb+66hL5t17I5781n02CeF92Hg/CS7gaeAa4BrR/ocAm4ADia5DPhxVf1o9EBV\n",
       "NTo7lySdoTXDu6pOJbkeuLPre0tVHUmyt9t/c1Xd3V1O+BjwU+CDc69akja5VG3KlQxJatrM77Dc\n",
       "rDf1TBp3kuuSPNJ9fTbJhX3UOWvTvN5dv0uTnEpy9SLrm6cpf9YvTXJf97qvLLjEuZjiZ/3sJLcl\n",
       "eTjJN5OMXl7cpCQHkvyoW2UY12dx2VZVM/sCtgBHgd3ANuBfgQtG+lwJ3N19/3bg/lnW0MfXlOP+\n",
       "HeDXuu8/sFnGPdTvG8CXgT/uu+4FvubnAN8Fzu3aO/que0Hj/nPgH7rvzwO+T/dXfstfwDuBi4HH\n",
       "xuxfaLbNeua9WW/qmTjuqvp2VT3XNe9iY1wLP83rDbAP+Dzw9CKLm7Npxv4+4I6qOg5QVc8suMZ5\n",
       "mGbczwGvTrIN2A48X12itayq7gWeXaPLQrNt1uG9WW/qmWbcwz4MfHGuFS3GxHEn2cngl/sT3abm\n",
       "f4k707zm5wPbk9zbLSFct7Dq5mfiuKvqdgYz9GeA+4CNMO5pLDTbJl0q+FJt1pt6pq4/ybuB9wPv\n",
       "mF85CzPNuG8CPlpVlSS8+LVv1TRj38bgtunLgVcCX0vyhar62TwLm7OJ405yA3AKeB3wVuCuJOdV\n",
       "1c/nXdw6sLBsm3V4z/SmnoZMM26SXAR8Criiqn68oNrmaZpxX8LgHgCAHcAVSU5W1aHFlDg304z9\n",
       "GPCVqvohQJLDwBJwz0IqnI9pxr0EfLqqngceSPIU8Cbg8cWU2JvFZtuMF/S3MnhzYjdwFpPfsLyM\n",
       "jfHG3TTjfgPwBPD2vutd5LhH+t8KXN133Qt8zd8MfIfBrHs78O/Aq/qufQHj3gv8PYNl2TcCT/Rd\n",
       "9wzHv5vp3rCce7bNdOZdm/SmnmnGDXyMwS/wJ7tZ6Mmq2tNXzbMw5bg3pCl/1h9PciuDO5V/Ffjb\n",
       "qvpJf1W/fFO+5geBtzAY99MMHhXdvCS3A+8CdiQ5BtzIYGmsl2zzJh1JapAfgyZJDTK8JalBhrck\n",
       "NcjwlqQGGd6S1CDDW5IaZHhLUoMMb0lq0P8DId3J4oycZN4AAAAASUVORK5CYII=\n"
      ],
      "text/plain": [
       "<matplotlib.figure.Figure at 0x124cf5910>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_ABC(np.array([length_norm(row) for row in ABC]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, the connection between A and B is more apparent, as is the opposition between B and C."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cosine distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Cosine distance__ takes overall length into account. The cosine distance between two vectors $u$ and $v$ of dimension $n$ is \n",
    "\n",
    "$$1 - \\left(\\frac{\\sum_{i=1}^{n} u_{i} \\cdot v_{i}}{\\|u\\|\\cdot \\|v\\|}\\right)$$\n",
    "\n",
    "The similarity part of this (the righthand term of the subtraction) is actually measuring the _angles_ between the two vectors. The result is the same (in terms of rank order) as one gets from first normalizing both vectors using `vector_length` and then calculating their Euclidean distance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def cosine(u, v):\n",
    "    # Use scipy's method:\n",
    "    return scipy.spatial.distance.cosine(u, v)\n",
    "    # Or define it yourself:\n",
    "    # return 1.0 - (np.dot(u, v) / (vector_length(u) * vector_length(v)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Matching-based methods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Matching-based methods are also common in the literature. The basic `matching` measure  effectively creates a vector consisting of all of the smaller of the two values at each coordinate, and then sums them:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def matching(u, v):\n",
    "    # The scipy implementation is for binary vectors only. This version is more general.\n",
    "    return np.sum(np.minimum(u, v))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One approach to normalizing the `matching` values is the __Jaccard coefficient__. The numerator is the matching coefficient. The denominator &mdash; the normalizer &mdash; is intuitively like the set union: for binary vectors it gives the cardinality of the union of the two being compared:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def jaccard(u, v):\n",
    "    # The scipy implementation is for binary vectors only. This version is more general.\n",
    "    return 1.0 - (matching(u, v) / np.sum(np.maximum(u, v)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Summary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose we set for ourselves the goal of associating A with B and disassociating B from C, in keeping with the semantic intuition expressed above. Then we can assess distance measures by whether they achieve this goal:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "      euclidean(A, B) = 13.60       euclidean(B, C) =  6.40\n",
      "         cosine(A, B) =  0.01          cosine(B, C) =  0.07\n",
      "       matching(A, B) =  6.00        matching(B, C) = 20.00\n",
      "        jaccard(A, B) =  0.76         jaccard(B, C) =  0.31\n"
     ]
    }
   ],
   "source": [
    "for m in (euclidean, cosine, matching, jaccard):\n",
    "    fmt = {'name': m.__name__,  'AB': m(ABC[0], ABC[1]), 'BC': m(ABC[1], ABC[2])}\n",
    "    print '%(name)15s(A, B) = %(AB)5.2f %(name)15s(B, C) = %(BC)5.2f' % fmt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Distributional neighbors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `neighbors` function is an investigative aide. For a given `word`, it ranks all the words in the vocabulary `rownames` according to their distance from `word`, as measured by `distfunc` in matrix `mat`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def neighbors(word=None, mat=None, rownames=None, distfunc=cosine):\n",
    "    if word not in rownames:\n",
    "        raise ValueError('%s is not in this VSM' % word)\n",
    "    w = mat[rownames.index(word)]\n",
    "    dists = [(rownames[i], distfunc(w, mat[i])) for i in xrange(len(mat))]\n",
    "    return sorted(dists, key=itemgetter(1), reverse=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By playing around with this function, you can start to get a sense for how the distance functions differ. Here are some example calls; you might try some new words to get a feel for what these matrices are like and how different words look."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('superb', 0.0),\n",
       " ('excellent', 0.0026965023912962627),\n",
       " ('outstanding', 0.0027344413235226295),\n",
       " ('beautifully', 0.0027345163104325332),\n",
       " ('brilliant', 0.0027888643627086429)]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbors(word='superb', mat=ww[0], rownames=ww[1], distfunc=cosine)[: 5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('superb', 0.0),\n",
       " ('familiar', 1448.8919904533948),\n",
       " ('violent', 1630.3723501090174),\n",
       " ('follows', 1647.0276257549538),\n",
       " ('convincing', 1701.2260284865147)]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbors(word='superb', mat=ww[0], rownames=ww[1], distfunc=euclidean)[: 5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above rankings actually tend to look pretty good, with `cosine` less likely to associate words that happen to have similar frequency. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The GloVe vectors look even better &mdash; but they are based on much more than just raw counts, as we'll see soon:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('superb', 2.2204460492503131e-16),\n",
       " ('brilliant', 0.15809110259014747),\n",
       " ('impressive', 0.19352861376442654),\n",
       " ('masterful', 0.22871323564771928),\n",
       " ('excellent', 0.22928471014596696)]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbors(word='superb', mat=glv[0], rownames=glv[1], distfunc=cosine)[: 5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Matrix reweighting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The goal of reweighting is to amplify the important, trustworthy, and unusual, while deemphasizing the mundane and the quirky. Absent a defined objective function, this will remain fuzzy, but the intuition behind moving away from raw counts is that \n",
    "frequency is a poor proxy for our target semantic ideas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Normalization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Normalization (row-wise or column-wise) is perhaps the simplest form of reweighting. With [length_norm](#Length-normalization), we normalize using `vector_length`. We can also normalize each row by the sum of its values, which turns each row into a probability distribution over the columns:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def prob_norm(u):\n",
    "    return u / np.sum(u)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These normalization measures are insensitive to the _magnitude_ of the underlying counts. This is often a mistake in the messy world of large data sets; $[1,10]$ and $[1000,10000]$ are very different in ways that will be partly or totally obscured by normalization."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pointwise Mutual Information"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Pointwise Mutual Information__ (PMI) addresses this issue, at least in part. The PMI for word $\\times$ context pair $(w,c)$ is \n",
    "\n",
    "$$\\log\\left(\\frac{P(w,c)}{P(w) \\cdot P(c)}\\right)$$\n",
    "\n",
    "with $\\log(0) = 0$. This is a measure of how far that cell's value deviates from what we would expect given the row and column sums for that cell. \n",
    "\n",
    "__Positive PMI__ (PPMI) maps all negative PMI values to 0.0. Our function `pmi` has `positive=True` as a default,\n",
    "in light of the arguments in [Levy and Goldberg 2014](http://papers.nips.cc/paper/5477-neural-word-embedding-as-implicit-matrix-factorization), section 3.3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def pmi(mat=None, rownames=None, positive=True):\n",
    "    \"\"\"PMI on mat; positive=True does PPMI. rownames is not used; it's \n",
    "    an argument only for consistency with other methods used here\"\"\"\n",
    "    # Joint probability table:\n",
    "    p = mat / np.sum(mat, axis=None)\n",
    "    # Pre-compute column sums:\n",
    "    colprobs = np.sum(p, axis=0)\n",
    "    # Vectorize this function so that it can be applied rowwise:\n",
    "    np_pmi_log = np.vectorize((lambda x : _pmi_log(x, positive=positive)))\n",
    "    p = np.array([np_pmi_log(row / (np.sum(row)*colprobs)) for row in p])   \n",
    "    return (p, rownames)\n",
    "\n",
    "def _pmi_log(x, positive=True):\n",
    "    \"\"\"With positive=False, return log(x) if possible, else 0.\n",
    "    With positive=True, log(x) is mapped to 0 where negative.\"\"\"\n",
    "    val = 0.0\n",
    "    if x > 0.0:\n",
    "        val = np.log(x)\n",
    "    if positive:\n",
    "        val = max([val,0.0])\n",
    "    return val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, we reweight the word $\\times$ word IMDB matrix from above using PPMI:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ww_ppmi = pmi(mat=ww[0], rownames=ww[1], positive=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('superb', 0.0),\n",
       " ('excellent', 0.41348274842943578),\n",
       " ('performances', 0.4439162856870249),\n",
       " ('brilliant', 0.45785117509986151),\n",
       " ('performance', 0.46856555779383213)]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbors(word='superb', mat=ww_ppmi[0], rownames=ww_ppmi[1], distfunc=cosine)[: 5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### TF-IDF"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Perhaps the best known reweighting schemes is __Term Frequency&ndash;Inverse Document Frequency__ (TF-IDF), which is, I believe, still the backbone of today's Web search technologies. As the name suggests, it is built from TF and IDF measures:\n",
    "\n",
    "For a word $w$ and collection of documents $D$ containing document $d$:\n",
    "\n",
    "* TF$(w,d)$: $P(w \\mid c)$. (In our VSMs, this is column-normalization using `prob_norm`.)\n",
    "* IDF$(w,D)$: $\\log\\left(\\frac{|D|}{|\\{d \\in D : w \\in d\\}|}\\right)$, where $\\log(0)=0$.\n",
    "* TFIDF$(w,d,D)$: TF$(w,d)$ * IDF$(w,D)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def tfidf(mat=None, rownames=None):\n",
    "    \"\"\"TF-IDF on mat. rownames is unused; it's an argument only \n",
    "    for consistency with other methods used here\"\"\"\n",
    "    colsums = np.sum(mat, axis=0)\n",
    "    doccount = mat.shape[1]\n",
    "    w = np.array([_tfidf_row_func(row, colsums, doccount) for row in mat])\n",
    "    return (w, rownames)\n",
    "\n",
    "def _tfidf_row_func(row, colsums, doccount):\n",
    "    df = float(len([x for x in row if x > 0]))\n",
    "    idf = 0.0\n",
    "    # This ensures a defined IDF value >= 0.0:\n",
    "    if df > 0.0 and df != doccount:\n",
    "        idf = np.log(doccount / df)\n",
    "    tfs = row/colsums\n",
    "    return tfs * idf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TF-IDF generally performs best with sparse matrices. It severely punishes words that appear in many documents; if a word appears in every document, then its IDF value is 0. As a result, it can even be problematic with verb dense word $\\times$ word \n",
    "matrices like `ww`, where most words appear with most other words due to the permissive notion of co-occurrence used to create it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's an example using our word&nbsp;x&nbsp;document matrix `wd`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "wd_tfidf = tfidf(mat=wd[0], rownames=wd[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('superb', 0.0),\n",
       " ('outstanding', 0.72256301656130351),\n",
       " ('remain', 0.73606093603489886),\n",
       " ('viewed', 0.74639986506462097),\n",
       " ('and', 0.74880553661599958)]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbors(word='superb', mat=wd_tfidf[0], rownames=wd_tfidf[1], distfunc=cosine)[: 5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dimensionality reduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above methods deliver solid results. However, they are not capable of capturing higher-order associations in the data. For example, both _gnarly_ and _wicked_ are used as slangily positive adjectives. We thus expect them to have many of the same neighbors. However, at least stereotypically, _gnarly_ is Californian and _wicked_ is Bostonian. Thus, they are unlikely \n",
    "to occur often in the same texts. Dimensionality reduction techniques are often capable of capturing their semantic similarity (and have the added advantage of shrinking the size of our data structures).\n",
    "\n",
    "The general goal of dimensionality reduction is eliminate rows/columns that are highly correlated while bringing similar things together and pushing dissimilar things apart. __Latent Semantic Analysis__ (LSA) is a prominent method. It is an application of truncated __singular value decomposition__ (SVD). SVD is a central matrix operation; 'truncation' here means looking only at submatrices of the full decomposition. LSA seeks not only to find a reduced-sized matrix but also to capture similarities that come not just from direct co-occurrence, but also from second-order co-occurrence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def lsa(mat=None, rownames=None, k=100):\n",
    "    \"\"\"svd with a column-wise truncation to k dimensions; rownames \n",
    "    is passed through only for consistency with other methods\"\"\"\n",
    "    rowmat, singvals, colmat = svd(mat, full_matrices=False)\n",
    "    singvals = np.diag(singvals)\n",
    "    trunc = np.dot(rowmat[:, 0:k], singvals[0:k, 0:k])\n",
    "    return (trunc, rownames)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a look at the example from the slides:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "gnmat = np.array([\n",
    "    [1,0,1,0,0,0],\n",
    "    [0,1,0,1,0,0],\n",
    "    [1,1,1,1,0,0],\n",
    "    [0,0,0,0,1,1],\n",
    "    [0,0,0,0,0,1]], dtype='float64')\n",
    "gn_rownames = ['gnarly', 'wicked', 'awesome', 'lame', 'terrible']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('gnarly', 2.2204460492503131e-16),\n",
       " ('awesome', 0.29289321881345254),\n",
       " ('wicked', 1.0),\n",
       " ('lame', 1.0),\n",
       " ('terrible', 1.0)]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbors(word='gnarly', mat=gnmat, rownames=gn_rownames)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that _gnarly_ and _wicked_ are not close to each other. (Well, it's a small space, but they are as close as _gnarly_ and _lame_.) Reweighting by PMI, PPMI, or TF-IDF is no help. LSA to the rescue:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "gnmat_lsa = lsa(mat=gnmat, rownames=gn_rownames, k=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('gnarly', 0.0),\n",
       " ('wicked', 0.0),\n",
       " ('awesome', 0.0),\n",
       " ('lame', 1.0),\n",
       " ('terrible', 1.0)]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbors(word='gnarly', mat=gnmat_lsa[0], rownames=gnmat_lsa[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can begin to get a feel for what your matrix is like by poking around with the `neighbors` function to see who is close to or far from whom. But this kind of sampling is unlikely to lead to robust new insights, unless you luck out and start to see an interesting cluster of associations developing.\n",
    "\n",
    "[t-Distributed Stochastic Neighbor Embedding](http://jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf) (t-SNE) is a powerful method for visualizing high-dimensional vector spaces in 2d. It allows you to find associations in an intuitive way, to guide later and more precise investigations. Its lead developer, [Laurens van der Maaten](http://lvdmaaten.github.io/tsne/), distributes a number of implementations of it. The following function uses his Python version, together with `matplotlib` to visualize the results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def tsne_viz(\n",
    "        mat=None,\n",
    "        rownames=None,\n",
    "        indices=None,\n",
    "        colors=None,\n",
    "        output_filename=None,\n",
    "        figheight=40,\n",
    "        figwidth=50,\n",
    "        display_progress=False): \n",
    "    \"\"\"2d plot of mat using tsne, with the points labeled by rownames, \n",
    "    aligned with colors (defaults to all black).\n",
    "    If indices is a list of indices into mat and rownames, \n",
    "    then it determines a subspace of mat and rownames to display.\n",
    "    Give output_filename a string argument to save the image to disk.\n",
    "    figheight and figwidth set the figure dimensions.\n",
    "    display_progress=True shows the information that the tsne method prints out.\"\"\"\n",
    "    if not colors:\n",
    "        colors = ['black' for i in range(len(rownames))]\n",
    "    temp = sys.stdout\n",
    "    if not display_progress:\n",
    "        # Redirect stdout so that tsne doesn't fill the screen with its iteration info:\n",
    "        f = open(os.devnull, 'w')\n",
    "        sys.stdout = f\n",
    "    tsnemat = tsne(mat)\n",
    "    sys.stdout = temp\n",
    "    # Plot coordinates:\n",
    "    if not indices:\n",
    "        indices = range(len(rownames))        \n",
    "    vocab = np.array(rownames)[indices]\n",
    "    xvals = tsnemat[indices, 0] \n",
    "    yvals = tsnemat[indices, 1]\n",
    "    # Plotting:\n",
    "    fig, ax = plt.subplots(nrows=1, ncols=1)\n",
    "    fig.set_figheight(40)\n",
    "    fig.set_figwidth(50)\n",
    "    ax.plot(xvals, yvals, marker='', linestyle='')\n",
    "    # Text labels:\n",
    "    for word, x, y, color in zip(vocab, xvals, yvals, colors):\n",
    "        ax.annotate(word, (x, y), fontsize=8, color=color)\n",
    "    # Output:\n",
    "    if output_filename:\n",
    "        plt.savefig(output_filename, bbox_inches='tight')\n",
    "    else:\n",
    "        plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's the code for running this on `ww_pmi` using the default settings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# tsne_viz(mat=ww_ppmi[0], rownames=ww_ppmi[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It takes a while to produce this, so here's an example of the output: [fig/imdb-wordword-ppmi.pdf](fig/imdb-wordword-ppmi.pdf). (t-SNE's output will vary somewhat from run to run)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For more on the techniques, we highly recommend van der Maaten's compelling\n",
    "talk [Visualizing Data Using t-SNE](https://www.youtube.com/watch?v=RJVL80Gg3lA)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The semantic orientation method"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The t-SNE visualization of our running example suggests some lexical clusters that in turn suggest the beginnings of a lexicon. The __semantic orientation__ method of [Turney and Littman 2003](http://doi.acm.org/10.1145/944012.944013) is a general method for building such lexicons for any desired semantic dimension.\n",
    "\n",
    "The method simply exploits our above insights about vector similarity. Here are the steps:\n",
    "\n",
    "0. Define two seed-sets $S_1$ and $S_2$ of words (they should be opposing in some way that is appropriate for your matrix).\n",
    "0. Pick a vector distance measure $f$.\n",
    "0. For the word $w$ of interest, use $f$ to get the sum of all distances between $w$ and the words in $S_1$. Do the same for $S_2$.\n",
    "0. The score is the sum for $S_1$ minus the sum for $S_2$.\n",
    "\n",
    "Here's an implementation; the default seed values correspond to Turney and Littman's basic sentiment experiment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def semantic_orientation(\n",
    "        mat=None, \n",
    "        rownames=None,\n",
    "        seeds1=['bad', 'nasty', 'poor', 'negative', 'unfortunate', 'wrong', 'inferior'],\n",
    "        seeds2=['good', 'nice', 'excellent', 'positive', 'fortunate', 'correct', 'superior'],\n",
    "        distfunc=cosine):\n",
    "    sm1 = so_seed_matrix(seeds1, mat, rownames)\n",
    "    sm2 = so_seed_matrix(seeds2, mat, rownames)\n",
    "    scores = [(rownames[i], so_row_func(mat[i], sm1, sm2, distfunc)) for i in xrange(len(mat))]\n",
    "    return sorted(scores, key=itemgetter(1), reverse=False)\n",
    "\n",
    "def so_seed_matrix(seeds, mat, rownames):\n",
    "    indices = [rownames.index(word) for word in seeds if word in rownames]\n",
    "    if not indices:\n",
    "        raise ValueError('The matrix contains no members of the seed set: %s' % \",\".join(seeds))\n",
    "    return mat[np.array(indices)]\n",
    "    \n",
    "def so_row_func(row, sm1, sm2, distfunc):\n",
    "    val1 = np.sum([distfunc(row, srow) for srow in sm1])\n",
    "    val2 = np.sum([distfunc(row, srow) for srow in sm2])\n",
    "    return val1 - val2    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An example function call using `ww_ppmi`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('poor', -1.2397213851709856),\n",
       " ('bad', -1.2213826663029765),\n",
       " ('worst', -1.1351666124996971),\n",
       " ('awful', -1.1048739686983322),\n",
       " ('waste', -1.0236360853957418)]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "so = semantic_orientation(mat=ww_ppmi[0], rownames=ww_ppmi[1])\n",
    "so[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('well', 0.75360884916526505),\n",
       " ('superior', 0.81493927722684845),\n",
       " ('great', 0.89100807935189241),\n",
       " ('nice', 0.93295714329167501),\n",
       " ('excellent', 1.1687082653604852)]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "so[-5:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Word-sense ambiguities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Distributional approaches are often criticized on the grounds that they do not allow for word-sense ambiguities. This is a fair criticism of the models explored so far. A method for addressing this shortcoming was proposed by [Reisinger and Mooney (2010)](https://aclweb.org/anthology/N/N10/N10-1013.pdf) building on ideas from [Sch&uuml;tze (1998)](http://www.aclweb.org/anthology/J/J98/J98-1004.pdf). Here is a simplified version of their method:\n",
    "    \n",
    "0. For each word $w$ in a word $\\times$ context matrix $M$, cluster the columns (contexts) containing $w$ using a clustering algorithm. \n",
    "0. For each token of $w$ in each of its contexts $d$, subscript $w$ with the cluster index of $d$ according to the clustering done in step 1.\n",
    "0. Rebuild the matrix with the rows now labeled with the expanded vocabulary obtained at step 2.\n",
    "\n",
    "The success of this method will depend a lot on the clustering algorithm used. The implementation below uses [Affinity Propagation](http://scikit-learn.org/stable/modules/clustering.html#affinity-propagation), which allows different numbers of clusters for each word, which seems desirable. [K-means](http://scikit-learn.org/stable/modules/clustering.html#k-means) actually works well too, and one could think about methods for setting $k$ for each word $w$ based on properties of the documents containing $w$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def disambiguate(mat=None, rownames=None, minval=0.0):\n",
    "    \"\"\"Basic unsupervised disambiguation. minval sets what it means to occur in a column\"\"\"\n",
    "    clustered = defaultdict(lambda : defaultdict(int))\n",
    "    # For each word, cluster the documents containing it:\n",
    "    for w_index, w in enumerate(rownames):\n",
    "        doc_indices = np.array([j for j in range(mat.shape[1]) if mat[w_index,j] > minval])\n",
    "        clust = cluster(mat, doc_indices) \n",
    "        for doc_index, c_index in clust:\n",
    "            w_sense = \"%s_%s\" % (w, c_index)\n",
    "            clustered[w_sense][doc_index] = mat[w_index, doc_index]\n",
    "    # Build the new matrix:\n",
    "    new_rownames = sorted(clustered.keys())\n",
    "    new_mat = np.zeros((len(new_rownames), mat.shape[1]))\n",
    "    for i, w in enumerate(new_rownames):\n",
    "        for j in clustered[w]:            \n",
    "            new_mat[i,j] = clustered[w][j]\n",
    "    return (new_mat, new_rownames)\n",
    "\n",
    "def cluster(mat, doc_indices):    \n",
    "    X = mat[:, doc_indices].T\n",
    "    # Other clustering algorithms can easily be swapped in: \n",
    "    # http://scikit-learn.org/stable/modules/classes.html#module-sklearn.cluster\n",
    "    clust = AffinityPropagation()\n",
    "    clust.fit(X)    \n",
    "    return zip(doc_indices,  clust.labels_)     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a small idealized example meant to highlight what the algorithm does mechanically and what it is supposed to do empirically. The idea is that _crane_ is ambiguous between a piece of machinery and a bird. The words _bird_ and _fly_ bias heavily in favor of the 'bird' sense, and the words _equipment_ and _hoist_ bias heavily in favor of the 'machine' sense. 'tall' is more subtly biased in favor of the _machine_ sense."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "cranes = np.array([\n",
    "    [1, 1, 1, 1, 1, 1],  # crane \n",
    "    [1, 1, 1, 0, 0, 0],  # bird\n",
    "    [0, 1, 1, 0, 0, 0],  # fly\n",
    "    [0, 0, 0, 1, 1, 1],  # equipment\n",
    "    [0, 0, 0, 1, 1, 0],  # hoist\n",
    "    [0, 0, 1, 1, 1, 0]], # tall\n",
    "    dtype='float64')\n",
    "\n",
    "crane_vocab = ['crane', 'bird', 'fly', 'equipment', 'hoist', 'tall']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we run `disambiguate` things work out nicely for the target _crane_. The algorithm creates a lot of spurious ambiguities, but these seem to remain close together in vector space, so we might be able to collapse them in a follow-up step. (For example if two words $w_i$ and $w_j$ are sufficiently close in the vector space and share the same orthographic form, then we collapse them back down again.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "crane_da = disambiguate(mat=cranes, rownames=crane_vocab)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('crane_0', -2.2204460492503131e-16),\n",
       " ('bird_1', 0.18350341907227408),\n",
       " ('bird_0', 0.42264973081037416),\n",
       " ('fly_0', 0.42264973081037416),\n",
       " ('fly_1', 0.42264973081037416),\n",
       " ('tall_0', 0.42264973081037416),\n",
       " ('crane_1', 1.0),\n",
       " ('equipment_0', 1.0),\n",
       " ('equipment_1', 1.0),\n",
       " ('hoist_0', 1.0),\n",
       " ('hoist_1', 1.0),\n",
       " ('tall_1', 1.0),\n",
       " ('tall_2', 1.0)]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbors(mat=crane_da[0], word='crane_0', rownames=crane_da[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('crane_1', -2.2204460492503131e-16),\n",
       " ('equipment_0', 0.18350341907227408),\n",
       " ('equipment_1', 0.42264973081037416),\n",
       " ('hoist_0', 0.42264973081037416),\n",
       " ('hoist_1', 0.42264973081037416),\n",
       " ('tall_1', 0.42264973081037416),\n",
       " ('tall_2', 0.42264973081037416),\n",
       " ('bird_0', 1.0),\n",
       " ('bird_1', 1.0),\n",
       " ('crane_0', 1.0),\n",
       " ('fly_0', 1.0),\n",
       " ('fly_1', 1.0),\n",
       " ('tall_0', 1.0)]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbors(mat=crane_da[0], word='crane_1', rownames=crane_da[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## GloVe word representations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We've so far performed our matrix manipulations without an explicit objective function. Rather, we've just had in mind informal ideas about capturing semantic relatedness. The  advantage of an explicit objective function is that we can apply standard optimization techniques.\n",
    "\n",
    "[Pennington et al. (2014)](http://www.aclweb.org/anthology/D/D14/D14-1162.pdf) introduce an objective function for semantic word representations. Roughly speaking, the objective is to learn vectors for words $w_{1}$ and $w_{j}$ such that their dot product is proportional to their co-occurrence count. I won't venture a full technical summary of the GloVe method here. Check out [the GloVe project homepage](http://nlp.stanford.edu/projects/glove/), which links to C code, word vectors, and other resources. I also highly recommend\n",
    "[Jeffrey Pennington's EMNLP talk 'Global vectors for word representation'](https://www.youtube.com/watch?v=RyTpzZQrHCs).\n",
    "\n",
    "The following implementation is an attempt to give the most stripped-down, bare-bones version of the GloVe method possible. In the papers and associated implementation, the authors use the [Adaptive Gradient (AdaGrad) learning method](http://jmlr.org/papers/v12/duchi11a.html). [Jon Gauthier released a Python version that uses that method as well](http://www.foldl.me/2014/glove-python/). Both of these implementations also do considerably more sophisticated things when it comes to compiling the basic co-occurrence counts. The code here is really just meant for instructional purposes. That said, it's a testament to the power of the method that it delivers high quality word vectors even in this basic form!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def randmatrix(m, n, lower=-0.5, upper=0.5):\n",
    "    \"\"\"Creates an m x n matrix of random values in [lower, upper]\"\"\"\n",
    "    return np.array([random.uniform(lower, upper) for i in range(m*n)]).reshape(m, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def glove(\n",
    "        mat=None, rownames=None, \n",
    "        n=100, xmax=100, alpha=0.75, \n",
    "        iterations=100, learning_rate=0.05, \n",
    "        display_progress=False):\n",
    "    \"\"\"Basic GloVe. rownames is passed through unused for compatibility\n",
    "    with other methods. n sets the dimensionality of the output vectors.\n",
    "    xmax and alpha controls the weighting function (see the paper, eq. (9)).\n",
    "    iterations and learning_rate control the SGD training.\n",
    "    display_progress=True prints iterations and current error to stdout.\"\"\"    \n",
    "    m = mat.shape[0]\n",
    "    W = randmatrix(m, n) # Word weights.\n",
    "    C = randmatrix(m, n) # Context weights.\n",
    "    B = randmatrix(2, m) # Word and context biases.\n",
    "    indices = range(m)\n",
    "    for iteration in range(iterations):\n",
    "        error = 0.0        \n",
    "        random.shuffle(indices)\n",
    "        for i, j in itertools.product(indices, indices):\n",
    "            if mat[i,j] > 0.0:     \n",
    "                # Weighting function from eq. (9)\n",
    "                weight = (mat[i,j] / xmax)**alpha if mat[i,j] < xmax else 1.0\n",
    "                # Cost is J' based on eq. (8) in the paper:\n",
    "                diff = np.dot(W[i], C[j]) + B[0,i] + B[1,j] - np.log(mat[i,j])                \n",
    "                fdiff = diff * weight                \n",
    "                # Gradients:\n",
    "                wgrad = fdiff * C[j]\n",
    "                cgrad = fdiff * W[i]\n",
    "                wbgrad = fdiff\n",
    "                wcgrad = fdiff\n",
    "                # Updates:\n",
    "                W[i] -= (learning_rate * wgrad) \n",
    "                C[j] -= (learning_rate * cgrad) \n",
    "                B[0,i] -= (learning_rate * wbgrad) \n",
    "                B[1,j] -= (learning_rate * wcgrad)                 \n",
    "                # One-half squared error term:                              \n",
    "                error += 0.5 * weight * (diff**2)\n",
    "        if display_progress:\n",
    "            print \"iteration %s: error %s\" % (iteration, error)\n",
    "    # Return the sum of the word and context matrices, per the advice \n",
    "    # in section 4.2:\n",
    "    return (W + C, rownames)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following take a while to run, but the results look good, and they can be  improved by adding more vocabulary items, allowing more iterations, and increasing the dimension size. For the output with 100 dimensions and 100 iterations, check out this image: [fig/imdb-wordword-glove100.pdf](fig/imdb-wordword-glove100.pdf)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def glove_viz(mat=None, rownames=None, word_count=1000, iterations=10, n=50, display_progress=True):\n",
    "    glove_indices = random.sample(range(len(rownames)), word_count)\n",
    "    glovemat, _ = glove(mat=mat[glove_indices, :], iterations=iterations, n=n)\n",
    "    tsne_viz(mat=glovemat, rownames=np.array(rownames)[glove_indices])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# glove_viz(mat=ww[0], rownames=ww[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Supervised signals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above methods rely entirely on co-occurrence patterns to achieve word representations. From a semantic perspective, this can seem unnatural. Grounding in the world is a crucial part of natural language meaning; without some connection to the world, we're missing important aspects of meaning.\n",
    "\n",
    "Distributed approaches are compatible with grounding, though. The goal of the current section is to illustrate this possibility with a simple example involving sentiment. The guiding idea is that the labels in a sentiment lexicon provide one very specific kind of grounding, in emotional states. This information is probably not recoverable entirely from distributional facts, but we can bring it into our distributed representations.\n",
    "\n",
    "The method employed here for imbuing distributional vectors with sentiment information is a [shallow neural network](http://ufldl.stanford.edu/wiki/index.php/UFLDL_Tutorial). The inputs to the network are matrices as we constructed them above. I particularly recommend applying PPMI first (count vectors will be problematic), and LSA might also be a valuable preprocessing step. Using the backpropagation algorithm, we learn a weight vector that derives hidden representations from our inputs. These  hidden representations are our word representations. If all goes well, they will encode both the distributional information present in the input vectors and the label information from our lexicon."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Shallow neural network model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a very basic shallow neural network implementation with stochastic gradient descent (SGD) training. (See [the exercises](#Exercises) for suggestions on how to improve this code.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from numpy import dot, outer\n",
    "\n",
    "class ShallowNeuralNetwork:\n",
    "    def __init__(self, input_dim=0, hidden_dim=0, output_dim=0, afunc=np.tanh, d_afunc=(lambda z : 1.0 - z**2)):        \n",
    "        self.afunc = afunc \n",
    "        self.d_afunc = d_afunc      \n",
    "        self.input = np.ones(input_dim+1)   # +1 for the bias                                         \n",
    "        self.hidden = np.ones(hidden_dim+1) # +1 for the bias        \n",
    "        self.output = np.ones(output_dim)        \n",
    "        self.iweights = randmatrix(input_dim+1, hidden_dim)\n",
    "        self.oweights = randmatrix(hidden_dim+1, output_dim)        \n",
    "        self.oerr = np.zeros(output_dim)\n",
    "        self.ierr = np.zeros(input_dim+1)\n",
    "        \n",
    "    def forward_propagation(self, ex):        \n",
    "        self.input[ : -1] = ex # ignore the bias\n",
    "        self.hidden[ : -1] = self.afunc(dot(self.input, self.iweights)) # ignore the bias\n",
    "        self.output = self.afunc(dot(self.hidden, self.oweights))\n",
    "        return copy.deepcopy(self.output)\n",
    "        \n",
    "    def backward_propagation(self, labels, alpha=0.5):\n",
    "        labels = np.array(labels)       \n",
    "        self.oerr = (labels-self.output) * self.d_afunc(self.output)\n",
    "        herr = dot(self.oerr, self.oweights.T) * self.d_afunc(self.hidden)\n",
    "        self.oweights += alpha * outer(self.hidden, self.oerr)\n",
    "        self.iweights += alpha * outer(self.input, herr[:-1]) # ignore the bias\n",
    "        return np.sum(0.5 * (labels-self.output)**2)\n",
    "\n",
    "    def train(self, training_data, maxiter=5000, alpha=0.05, epsilon=1.5e-8, display_progress=False):       \n",
    "        iteration = 0\n",
    "        error = sys.float_info.max\n",
    "        while error > epsilon and iteration < maxiter:            \n",
    "            error = 0.0\n",
    "            random.shuffle(training_data)\n",
    "            for ex, labels in training_data:\n",
    "                self.forward_propagation(ex)\n",
    "                error += self.backward_propagation(labels, alpha=alpha)           \n",
    "            if display_progress:\n",
    "                print 'completed iteration %s; error is %s' % (iteration, error)\n",
    "            iteration += 1\n",
    "                    \n",
    "    def predict(self, ex):\n",
    "        self.forward_propagation(ex)\n",
    "        return copy.deepcopy(self.output)\n",
    "        \n",
    "    def hidden_representation(self, ex):\n",
    "        self.forward_propagation(ex)\n",
    "        return self.hidden"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Logical operator example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Logical operators like 'iff' and 'xor' provides early motivation for hidden representations (see [Rumelhart et al. 1985](http://psych.stanford.edu/~jlm/papers/PDP/Volume%201/Chap8_PDP86.pdf)), so it's satisfying to show that the above code can learn such operators (at least on most runs). Here an example involving 'iff':"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1.0, 1.0] [1.0] [ 0.98] [-0.81  0.87  0.98  0.47  1.  ]\n",
      "[1.0, 0.0] [0.0] [ 0.] [-0.98 -0.62  0.79  0.77  1.  ]\n",
      "[0.0, 1.0] [0.0] [ 0.] [ 0.53  0.99  0.86 -0.04  1.  ]\n",
      "[0.0, 0.0] [1.0] [ 0.99] [-0.56  0.71  0.15  0.43  1.  ]\n"
     ]
    }
   ],
   "source": [
    "def iff_example():\n",
    "    iff_train = [\n",
    "        ([1.,1.], [1.]), # T T ==> T\n",
    "        ([1.,0.], [0.]), # T F ==> F\n",
    "        ([0.,1.], [0.]), # F T ==> F\n",
    "        ([0.,0.], [1.])] # F F ==> T\n",
    "    net = ShallowNeuralNetwork(input_dim=2, hidden_dim=4, output_dim=1)\n",
    "    net.train(copy.deepcopy(iff_train))    \n",
    "    for ex, labels in iff_train:\n",
    "        prediction = net.predict(ex)\n",
    "        hidden_rep = net.hidden_representation(ex)  \n",
    "        print ex, labels, np.round(prediction, 2), np.round(hidden_rep, 2)\n",
    "\n",
    "iff_example()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sentiment lexicon example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To close this section, let's look a somewhat more useful and complex example involving a multidimensional sentiment lexicon. This is actually on its way to being a useful general purpose sentiment resource!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first function just processes the sentiment lexicon included in the data distribution (`Warriner_et_al emot ratings.csv`). We keep only the overall values for the three sentiment dimensions, and we rescale them into the space [-1,1]. (Somewhat counter intuitively, for the valence dimensions, the low values are positive and the high values are negative, because of the original rating scale.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def read_valence_arousal_dominance_lexicon(src_filename='distributedwordreps-data/Warriner_et_al emot ratings.csv'):\n",
    "    rescaler = (lambda x : np.tanh(float(x)-5))\n",
    "    lex = {}\n",
    "    for d in csv.DictReader(file(src_filename)):\n",
    "        vals = {'valence': rescaler(d['V.Mean.Sum']), \n",
    "                'arousal': rescaler(d['A.Mean.Sum']), \n",
    "                'dominance': rescaler(d['D.Mean.Sum'])}\n",
    "        lex[d['Word']] = vals\n",
    "    return lex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next function uses a distributional matrix and a lexicon to create a training set consisting of all the items in the matrix that are also in the lexicon:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def build_supervised_dataset(mat=None, rownames=None, lex=None):\n",
    "    data = []\n",
    "    vocab = []\n",
    "    for word, vals in lex.items():\n",
    "        if word in rownames:\n",
    "            vocab.append(word)\n",
    "            data.append((mat[rownames.index(word)], [y for _, y in sorted(vals.items())]))\n",
    "    return (data, vocab)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're now ready to train the model and view the results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def sentiment_lexicon_example(\n",
    "        mat=None, \n",
    "        rownames=None, \n",
    "        hidden_dim=100, \n",
    "        maxiter=1000, \n",
    "        output_filename=None, \n",
    "        display_progress=False):\n",
    "    # Get the lexicon:\n",
    "    lex = read_valence_arousal_dominance_lexicon()\n",
    "    # Build the training data:\n",
    "    sentidata, sentivocab = build_supervised_dataset(mat=mat, rownames=rownames, lex=lex)\n",
    "    # Set up the network:\n",
    "    sentinet = ShallowNeuralNetwork(\n",
    "        input_dim=len(sentidata[0][0]), \n",
    "        hidden_dim=hidden_dim, \n",
    "        output_dim=len(sentidata[0][1]))\n",
    "    # Train the network:\n",
    "    sentinet.train(copy.deepcopy(sentidata), maxiter=maxiter, display_progress=display_progress)\n",
    "    # Build the new matrix of hidden representations:\n",
    "    inputs, labels = zip(*sentidata)\n",
    "    sentihidden = np.array([sentinet.hidden_representation(x) for x in inputs])\n",
    "    # Visualize the results with t-SNE:\n",
    "    def colormap(vals):\n",
    "        \"\"\"Simple way to distinguish the 2x2x2 possible labels -- could be done much better!\"\"\"\n",
    "        signs = ['CC' if x < 0.0 else '00' for _, x in sorted(vals.items())]\n",
    "        return \"#\" + \"\".join(signs)    \n",
    "    colors = [colormap(lex[word]) for word in sentivocab]\n",
    "    tsne_viz(mat=sentihidden, rownames=sentivocab, colors=colors, display_progress=display_progress, output_filename=output_filename)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function `sentiment_lexicon_example` takes a while to run with reasonable keyword arguments. To see what the results tend to look like with the default  values, here's an informal comparison of the matrix `ww`, reweighted with Positive PMI, before and after supervised sentiment training: [fig/imdb-wordword-ppmi-nn.pdf](fig/imdb-wordword-ppmi-nn.pdf)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Word-level inference relations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Bowman et al. (2015)](http://arxiv.org/abs/1410.4176) use neural networks to predict the relationship between words. \n",
    "The data distribution for this unit includes one of their experiment files, `longer_shuffled_synset_relations.tsv`. The left column gives the semantic relation (`hyponym`, `hypernym`, `coordinate`), and the middle and right columns give the two words. We can use `ShallowNeuralNetwork` to train models that perform this prediction task, beginning either from randomly initialized input vectors or from distributional vectors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Word similarity evaluation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function `word_similarity_evaluation` lets you evaluate a matrix `mat` against the human word similarity judgments in words in the WordSim-353 dataset. If you haven't already, [download that data set](http://www.cs.technion.ac.il/~gabr/resources/data/wordsim353/wordsim353.zip) and unzip it so that the directory `wordsim353` is inside the directory containing this file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def word_similarity_evaluation(src_filename=\"distributedwordreps-data/wordsim353/combined.csv\", \n",
    "        mat=None, rownames=None, distfunc=cosine):\n",
    "    # Read in the data:\n",
    "    reader = csv.DictReader(file(src_filename))\n",
    "    sims = defaultdict(list)\n",
    "    vocab = set([])\n",
    "    for d in reader:\n",
    "        w1 = d['Word 1']\n",
    "        w2 = d['Word 2']\n",
    "        if w1 in rownames and w2 in rownames:\n",
    "            # Use negative of scores to align intuitively with distance functions:\n",
    "            sims[w1].append((w2, -float(d['Human (mean)'])))\n",
    "            sims[w2].append((w1, -float(d['Human (mean)'])))\n",
    "            vocab.add(w1)\n",
    "            vocab.add(w2)\n",
    "    # Evaluate the matrix by creating a vector of all_scores for the wordsim353 data\n",
    "    # and all_dists for mat's distances. \n",
    "    all_scores = []\n",
    "    all_dists = []\n",
    "    for word in vocab:\n",
    "        vec = mat[rownames.index(word)]\n",
    "        vals = sims[word]\n",
    "        cmps, scores = zip(*vals)\n",
    "        all_scores += scores\n",
    "        all_dists += [distfunc(vec, mat[rownames.index(w)]) for w in cmps]\n",
    "    # Return just the rank correlation coefficient (index [1] would be the p-value):\n",
    "    return scipy.stats.spearmanr(all_scores, all_dists)[0]   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Evaluation is then simple. Here's the evaluation using the `ww_ppmi` matrix we built above:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.56579499517630127"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word_similarity_evaluation(mat=ww_ppmi[0], rownames=ww_ppmi[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Word analogies evaluation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def analogy_completion(a, b, c, mat=None, rownames=None, distfunc=cosine):\n",
    "    \"\"\"a is to be as c is to predicted, where predicted is the closest to (b-a) + c\"\"\"\n",
    "    for x in (a, b, c):\n",
    "        if x not in rownames:\n",
    "            raise ValueError('%s is not in this VSM' % x)\n",
    "    avec = mat[rownames.index(a)]\n",
    "    bvec = mat[rownames.index(b)]\n",
    "    cvec = mat[rownames.index(c)]\n",
    "    newvec = (bvec - avec) + cvec\n",
    "    dists = [(w, distfunc(newvec, mat[i])) for i, w in enumerate(rownames) if w not in (a, b, c)]\n",
    "    return sorted(dists, key=itemgetter(1), reverse=False)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('singing', 0.36387000688724269),\n",
       " ('songs', 0.4322230813308281),\n",
       " ('song', 0.43648688095757859),\n",
       " ('musical', 0.45341770142029203),\n",
       " ('musicals', 0.50284943344566313)]"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "analogy_completion('dance', 'dancing', 'sing', mat=ww_ppmi[0], rownames=ww_ppmi[1])[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def analogy_evaluation(src_filename=\"distributedwordreps-data/question-data/gram1-adjective-to-adverb.txt\", \n",
    "        mat=None, rownames=None, distfunc=cosine):\n",
    "    # Read in the data and restrict to problems we can solve:\n",
    "    data = [line.split() for line in open(src_filename).read().splitlines()]\n",
    "    data = [prob for prob in data if set(prob) <= set(rownames)]\n",
    "    # Run the evaluation, collecting accuracy and rankings:\n",
    "    results = defaultdict(int)\n",
    "    ranks = []\n",
    "    for a, b, c, d in data:\n",
    "        predicted = analogy_completion(a, b, c, mat=mat, rownames=rownames, distfunc=distfunc)\n",
    "        # print \"%s is to %s as %s is to %s (actual is %s)\" % (a, b, c, predicted, d)\n",
    "        results[predicted[0][0] == d] += 1\n",
    "        predicted_words, _ = zip(*predicted)\n",
    "        ranks.append(predicted_words.index(d))\n",
    "    # Return the mean reciprocal rank and the accuracy results:\n",
    "    mrr = np.mean(1.0/(np.array(ranks)+1))\n",
    "    return (mrr, results)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.048040778437069588, defaultdict(<type 'int'>, {False: 180, True: 2}))"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "analogy_evaluation(mat=ww_ppmi[0], rownames=ww_ppmi[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.16482840597297255, defaultdict(<type 'int'>, {False: 223, True: 17}))"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "analogy_evaluation(src_filename=\"distributedwordreps-data/question-data/gram7-past-tense.txt\", \n",
    "                   mat=ww_ppmi[0], rownames=ww_ppmi[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exploratory and open-ended"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are largely meant to give you a feel for the material, but some of them could lead to projects. __These are not for credit.__\n",
    "\n",
    "0. Pick a few words from a single domain and see what their neighbors are like in one the VSMs (`ww`, `wd`, `ww_ppmi`, `ww_tfidf`, `glv`), using `neighbors`, comparing `cosine` with `euclidean`.\n",
    "\n",
    "0. We saw that euclidean distance favors raw frequencies. Find words in the matrix `ww` that help make this point: a pair that are semantically unrelated but close according to `euclidean`, and a pair that are semantically related by far apart according to `euclidean`.\n",
    "\n",
    "0. Starting from `ww` or `wd`, toy around with different combinations of (i) weighting scheme, (ii) dimensionality reduction (if any), and (iii) distance measure. Which VSM seems to provide the best reconstruction of our intuitive notion of semantic relatedness.\n",
    "\n",
    "0. What happens if you set `k=1` using `lsa`. What do the results look like then? What do you think this first (and now only) dimension is capturing?\n",
    "\n",
    "0. Use `sentiment_lexicon_example` on a different matrix, with different settings, to see what the results are like. You might also modify the code so that it trains on just a subset of the lexicon values.\n",
    "\n",
    "0. Read in `distributedwordreps-data/gigawordnyt-advmod-matrix.csv`. This is an adjective $\\times$ adverb matrix derived from the Gigaword corpus. Each cell contains the number of times that the modifier phrase _ADV ADJ_ appeared in Gigaword, where _ADJ_ is the row value and _ADV_ is the column value. You can read it in with `build` above. Using the above techniques and measures, try to get a feel for what can be done with this matrix.\n",
    "\n",
    "0. Use the [word2vec](https://code.google.com/p/word2vec/) implementation in [gensim](https://radimrehurek.com/gensim/) for some purpose.\n",
    "\n",
    "0. Find new labels sources to include in your training of a `ShallowNeuralNetwork` instance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Straightforward"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "0. Implement [Jensen&ndash;Shannon distance](http://en.wikipedia.org/wiki/Jensen–Shannon_divergence) and run it on the toy matrix `ABC` defined above. Does this measure place `A` and `B` close together relative to `B` and `C` (our goal for that example)? Submit: (i) your implementation, and (ii) the JS distance values between `A` and `B` and between `B` and `C`.\n",
    "\n",
    "0. Implement the [Dice coefficient](http://en.wikipedia.org/wiki/Sørensen–Dice_coefficient) for real-valued vectors, as \n",
    "\n",
    "  $$1.0 - \\left(\\frac{2\\sum_{i=1}^{n}\\min(u_{i}, v_{i})}{\\sum_{i=1}^{n}u_{i}+v_{i}}\\right)$$ \n",
    "\n",
    "  Run your code on the toy matrix `ABC` defined above. Does this measure place `A` and `B` close together relative to `B` and `C` (our goal for that example)? Submit: (i) your implementation, and (ii) the Dice coefficient values for `A` and `B` and for `B` and `C`.\n",
    "\n",
    "0. Consider the matrix `np.array([[1.0, 0.0, 0.0], [1000.0, 1000.0, 4000.0], [1000.0, 2000.0, 999.0]])`. Reweight this matrix using `pmi` with `positive=True`. Submit: (i) the value obtained for cell `[0,0]`, and (ii) a 1&ndash;2 sentence explanation of what is what is likely problematic about this value.\n",
    "\n",
    "0. The t-test statistic can be thought of as a reweighting scheme. For a word&ndash;context pair $(w, c)$, the weighted value is \n",
    "\n",
    "  $$\\frac{P(w, c)-(P(w)P(c))}{\\sqrt{P(w)P(c)}}$$ \n",
    "\n",
    "  Implement this as a function `ttest` comparable to `pmi` and `tfidf`. Submit: your implementation.\n",
    "\n",
    "0. Using `glv` (which has a large and diverse set or rownames/words), pick a new semantic opposition and see how well `semantic_orientation` captures it. Submit: (i) the name of the semantic opposition you seek to capture (e.g., \"positive/negative\"), and (ii) your seed sets.\n",
    "\n",
    "0. Using `iff_example` as an example, write a function `boolean_nn` that can train a `ShallowNeuralNetwork` on any binary logical connective that the user supplies as training data (in the same format as the training data in `iff_example`). Give the user the option to set the hidden layer dimensionality as a keyword argument. Submit: (i) your function `boolean_nn`, and (ii) an example function call training on the XOR connective. (XOR is the function $f$ such that, for truth-valued arguments $x$ and $y$, $f(x,y)$ is true iff $x$ and $y$ are different.)\n",
    "\n",
    "0. The default activation function for `ShallowNeuralNetwork` is `tanh`. Implement a sigmoid activation function, defined as $f(x) = \\frac{1}{1 + \\exp(-x)}$. Submit: (i) your implementation of this function, and (ii) its derivative (the value of `d_afunc`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Challenging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "0. Use `pickle.load(file('distributedwordreps-data/imdb-posneg-lexicon.pickle'))` to read in a positive/negative sentiment lexicon restricted to the vocabulary of `ww` (same as the rows of `wd`). The dictionary has training and testing lists for the positive and negative categories. Your task: (i) write a function that uses `semantic_orientation` to induce a positive/negative sentiment lexicon on a given matrix by imposing a boundary or boundaries on what counts as positive and what counts as negative, and (ii) write a function to evaluate this function against the training data in `distributedwordreps-data/imdb-posneg-lexicon.pickle`. Submit: the two functions you wrote for (i) and (ii).\n",
    "\n",
    "0. Use `pickle.load(file('distributedwordreps-data/imdb-posneg-lexicon.pickle'))` to read in a positive/negative sentiment lexicon restricted to the vocabulary of `ww` (same as the rows of `wd`). The dictionary has training and testing lists for the positive and negative categories. Your task: write a function that (i) reads in a distributional matrix, (ii) does some manipulation of it, (iii) trains a `ShallowNeuralNetwork` instance on the training portion of `imdb-posneg-lexicon.pickle`, and (iv) evaluates the trained model on the testing portion of `imdb-posneg-lexicon.pickle`. Submit: the function you wrote (which can call smaller functions that you include to make the code manageable).\n",
    "\n",
    "0. The file `distributedwordreps-data/gigawordnyt-advmod-matrix.csv` contains an adjective $\\times$ adverb matrix derived from the Gigaword corpus. Each cell contains the number of times that the modifier phrase _ADV ADJ_ appeared in Gigaword, where _ADJ_ is the row value and _ADV_ is the column value. You can read it in with `build` above. Your task: without introducing any new data, get at least 190 examples right on the analogy file `distributedwordreps-data/question-data/gram3-comparative.txt`. Submit: a function that implements your model and returns the evaluation (the output of `analogy_evaluation` above). (If your function depends on other code you wrote that isn't included in this codelab, include that code as well.)\n",
    "\n",
    "0. Turney and Pantel 2010, p.&nbsp;158, propose a \"contextual discounting\" extension of PMI to try to address its bias for low-frequency events. Extend `pmi` so that the user has the option of performing this discounting with the keyword argument `discounting=True`. Submit: your revised `pmi` in full.\n",
    "\n",
    "0. Modify `disambiguate` so that words with the same \"root\" (e.g., `bird_0` and `bird_1`) are collapsed back down to the same vector if their separate vectors are within a user-supplied distance of one another (to remove spurious ambiguities). Submit: your modified `disambiguate` implementation.\n",
    "\n",
    "0. Modify `glove` so that it uses the [AdaGrad optimization method](http://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf). It's fine to use [the authors' implementation](http://nlp.stanford.edu/projects/glove/) or [Jon Gauthier's implementation](http://www.foldl.me/2014/glove-python/) as a reference, but you might enjoy the challenge of doing this with no peeking at their code. Submit: your revised `glove` code in full.\n",
    "\n",
    "0. Modify the `train` method of `ShallowNeuralNetwork` so that the user can take advantage of the optimization methods in [scipy.optimize](http://docs.scipy.org/doc/scipy/reference/optimize.html). Submit: your revised `ShallowNeuralNetwork` code in full.\n",
    "\n",
    "0. Revise `ShallowNeuralNetwork` to `DeepNeuralNetwork` by adding the capability to handle any number of hidden layers. Submit: your revised `DeepNeuralNetwork` code in full."
   ]
  }
 ],
 "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}