5_Skip_Gram_Tutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Skip Gram for Word Embeddings (Word Vectors) Tutorial\n",
    "\n",
    "This tutorial walks through the Skip-Gram model proposed by [Mikolov et al](https://arxiv.org/pdf/1301.3781.pdf). The purpose of this tutorial is more about the architecture of the model rather than the estimation. \n",
    "\n",
    "<b>IMPORTANT</b>: Here, I only discuss training the model with gradient descent, however as practitioners will know, this is inefficient with large databases. As a result, [Mikolov et al](http://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf) released another paper with a technique known as negative sampling, which trains only a subset of weights each epoch. This would be more effective in obtaining word vectors with an actual text database. This will be the topic of a subsequent tutorial.\n",
    "\n",
    "## Example ##\n",
    "Textual analysis is a booming field with practical applications in social science. The first thing to consider in most textual analyses is the representation of words in a computer program. \n",
    "\n",
    "Consider the following sentences:\n",
    "\n",
    "Example 1: <i>we think uncertainty about unemployment</i><br>\n",
    "Example 2: <i>uncertainty and fears about inflation</i><br>\n",
    "Example 3: <i>we think fears about unemployment</i><br>\n",
    "Example 4: <i>we think fears and uncertainty about inflation and unemployment</i><br>\n",
    "Example 5: <i>constant negative press covfefe</i><br>\n",
    "\n",
    "In total, there are 12 unique words: and, about, constant, unemployment, uncertainty, fears, we, negative, inflation, press, think, covfefe\n",
    "\n",
    "## One-Hot Representation ##\n",
    "One common way of representing words is with a <b>one-hot encoded</b> vector. This would be a vector of length 12 where each index represents one of the 12 unique words. We can represent each word with such a vector, with a 1 at the index of the word and zero everywhere else. \n",
    "\n",
    "For example, we can represent the word <i>fears</i> as follows:\n",
    "$$\n",
    "\\small{\\begin{array}{|cccccccccccc|}\n",
    " \\text{and}  & \\text{uncertainty} & \\text{fears}& \\text{we}& \\text{about}& \\text{constant}& \\text{unemployment}& \\text{negative}& \\text{inflation}& \\text{press}& \\text{think}& \\text{covfefe} \\\\\n",
    "\\hline\n",
    "0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "\\end{array}}$$\n",
    "\n",
    "### Why use word vectors/embeddings? ###\n",
    "One issue with this representation is how to relate two words. How is the word <i>fears</i> related to the word <i>uncertainty</i>? They both contain length 12, have a 1 only in one index and 0 everywhere else. Essentially, all individual words are the same distance from each other. Note that if we were to calculate the distances between words, <i>fears</i> would be the same distance to <i>covfefe</i>; <i>fears</i> would be the same distance to <i>uncertainty</i>; and <i>uncertainty</i> would be the same distance to <i>covfefe</i>\n",
    "\n",
    "$$\\small{\\begin{array}{l|cccccccccccc|}\n",
    "& \\text{and}  & \\text{uncertainty} & \\text{fears}& \\text{we}& \\text{about}& \\text{constant}& \\text{unemployment}& \\text{negative}& \\text{inflation}& \\text{press}& \\text{think}& \\text{covfefe} \\\\\n",
    "\\hline\n",
    "\\text{fears} & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "\\hline\n",
    "\\text{uncertainty} & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "\\hline\n",
    "\\text{covfefe} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n",
    "\\end{array}}$$\n",
    "\n",
    "Word vectors, or [word embeddings](https://en.wikipedia.org/wiki/Word_embedding), solve this issue. They map words to some arbitrary H-dimensional space, $\\mathbb{R}^H$, where semantic and syntactic similarities are preserved. Below provides an example of these 12 words mapped into a 3-Dimensional space. The 3-Dimensional vectors were obtained using the Skip-Gram model proposed by Mikolov et al. Notice, that words <i>fear</i> and <i>uncertainty</i> appear alongisde each, as do the words <i>inflation</i> and <i>unemployment</i>, suggesting similar meanings (with respect to their usage in sentences) through syntax and semantics. \n",
    "\n",
    "<img src=\"markdown/scatter.png\">\n",
    "\n",
    "## Overview of Skip-Gram Model to Obtain Word Embeddings ##\n",
    "\n",
    "The Skip-Gram Model aims to understand the link between words in sentences, and their context. For example, in Example 1, <i>we think uncertainty about unemployment</i>, consider the word <i>uncertainty</i>. The words within it's immediate proximity are <i>think</i> and <i>about</i>. Word embeddings leverage the information that similar words typically show up with similar contexts. \n",
    "\n",
    "The Skip-Gram Model aims to use as input the one-hot encoded vector for the word <i>uncertainty</i> and output the word <i>think</i> and the word <i>about</i>, each represented as their own one-hot encoded vector. Let's take the input <i>uncertainty</i> and output <i>think</i>. Below is an image of the neural network at work (it might look daunting at first, so I'll try to explain each step below!).\n",
    "\n",
    "### Example of 1 Training Example: Input <i>uncertainty</i>, Output <i>think</i>###\n",
    "<img src=\"markdown/neural_net.png\">\n",
    "\n",
    "Each step in the neural network is known as a layer. \n",
    "\n",
    "### Input Layer ### \n",
    "Here we define the input, represented by a 12 length vector as above, with a one at the target word, <i>uncertainty</i>.\n",
    "\n",
    "### Hidden Layer ###\n",
    "This is the target word represented in the H-dimensional space, $\\mathbb{R}^H$. In our example, we will use a 3-Dimensional space.\n",
    "\n",
    "How do we get the Hidden Layer from the Input Layer of just a one-hot encoded vector. We multiply the Input Vector by a 3-by-12 matrix <b>we will call the $\\mathbf{U}$ matrix</b>.\n",
    "\n",
    "Input to Hidden Layer \n",
    "\n",
    "$\\mathbf{U}\\cdot x_{uncertainty}^\\prime = \\begin{bmatrix}\n",
    "u^{and}_{1} & u^{uncertainty}_{1} & u^{fears}_{1} \\cdot\\cdot\\cdot & u^{think}_{1} \\\\\n",
    "u^{and}_{2} & u^{uncertainty}_{2} & u^{fears}_{2} \\cdot\\cdot\\cdot & u^{think}_{2} \\\\\n",
    "u^{and}_{3} & u^{uncertainty}_{3} & u^{fears}_{3} \\cdot\\cdot\\cdot & u^{think}_{3} \\\\\n",
    "   \\end{bmatrix}\n",
    "\\small{\n",
    "\\begin{bmatrix}\n",
    "     0  &   1 & \\cdot \\cdot \\cdot & 0 &  0 \\\\\n",
    " and & uncertainty & \\cdot\\cdot \\cdot & think & covfefe\n",
    "\\end{bmatrix}}^\\prime$\n",
    "\n",
    "$=\n",
    "\\begin{bmatrix}\n",
    "u^{uncertainty}_{1}  &  u^{uncertainty}_{2}& u^{uncertainty}_{3}\n",
    "\\end{bmatrix}^\\prime  = \\mathbf{u_{uncertainty}^\\prime}$\n",
    "\n",
    "<b>NOTE</b> that since $\\mathbf{U}$ is H-by-V in size, each column represents one of the words in our vocabulary. Since <i>uncertainty</i> is the third index in our input matrix, the third column of $\\mathbf{U}$ represents <i>uncertainty</i> in our H-Dimensional space. <b>This H-Dimensional vector is the word embedding we are looking after</b>.\n",
    "\n",
    "### Output Layer ###\n",
    "\n",
    "We multiply the hidden layer, $\\mathbf{u_{uncertainty}}$ by a 12-by-3 matrix <b>we will call the $\\mathbf{V}$ matrix</b>.\n",
    "\n",
    "Hidden Layer to Output\n",
    "\n",
    "$\\mathbf{V}\\cdot \\mathbf{u_{uncertainty}^\\prime} = \\begin{bmatrix}\n",
    "v^{and}_{1} & v^{and}_{2}& v^{and}_{3} \\\\\n",
    "v^{uncertainty}_{1} & v^{uncertainty}_{2} & v^{uncertainty}_{3} \\\\\n",
    "\\cdot \\\\\n",
    "\\cdot \\\\\n",
    "\\cdot \\\\\n",
    "v^{think}_{1} & v^{think}_{2} & v^{think}_{3} \n",
    "   \\end{bmatrix}\n",
    " \\mathbf{u_{uncertainty}}$\n",
    " $\n",
    "=\\begin{bmatrix}\n",
    " \\mathbf{v_{and}^\\prime} \\mathbf{u_{uncertainty}} &  \\mathbf{v_{uncertainty}^\\prime} \\mathbf{u_{uncertainty}} & \\cdot \\cdot \\cdot & \\mathbf{v_{think}^\\prime} \\mathbf{u_{uncertainty}} &  \\mathbf{v_{covfefe}^\\prime} \\mathbf{u_{uncertainty}}\n",
    "\\end{bmatrix}\n",
    "$\n",
    "### Output Probability ###\n",
    "\n",
    "Because we want to be able to predict the words in the context of <i>uncertainty</i> in the sentence, i.e. <i>think</i> and <i>about</i>, we should handle this appropriately. One way is to normalize the values to probabilities by applying the [softmax function](https://en.wikipedia.org/wiki/Softmax_function). \n",
    "\n",
    "$\\begin{array}{cccc}[\\frac{exp(\\mathbf{v_{and}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}&\\frac{\\mathbf{v_{uncertainty}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}&...&\\frac{exp(\\mathbf{v_{covfefe}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}]\\end{array}$\n",
    "\n",
    "We know we wanted to predict the word <i>think</i> in this example, therefore we have the prediction and the target value.\n",
    "\n",
    "$$\\small{\\begin{array}{l|cccccccccccc|}\n",
    "& \\text{and}  & \\text{uncertainty} & \\text{fears}& \\text{we}& \\text{about}& \\text{constant}& \\text{unemployment}& \\text{negative}& \\text{inflation}& \\text{press}& \\text{think}& \\text{covfefe} \\\\\n",
    "\\hline\n",
    "\\text{Input} & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "\\hline\n",
    "\\text{Output} & \\frac{exp(\\mathbf{v_{and}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})} & \\frac{exp(\\mathbf{v_{uncertainty}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}& \\frac{exp(\\mathbf{v_{fears}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}&\\frac{exp(\\mathbf{v_{we}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}&\\frac{exp(\\mathbf{v_{about}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}&\\frac{exp(\\mathbf{v_{constant}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}&\\frac{exp(\\mathbf{v_{unemployment}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}&\\frac{exp(\\mathbf{v_{negative}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}&\\frac{exp(\\mathbf{v_{inflation}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}&\\frac{exp(\\mathbf{v_{press}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}&\\frac{exp(\\mathbf{v_{think}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}&\\frac{exp(\\mathbf{v_{covfefe}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}&\\\\\n",
    "\\hline\n",
    "\\text{Target} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\\n",
    "\\end{array}}$$\n",
    "\n",
    "## Estimating U and V ##\n",
    "\n",
    "Now I will discuss exactly how we can use these training examples to train the neural network and obtain good estimates fo the word embeddings, matrix $\\mathbf{U}$. \n",
    "\n",
    "Without loss of generality, let's update just one training example, the word <i>uncertainty</i> in the sentence <i>we think uncertainty about unemployment</i>. Assume that the context is M=1, so that we assume the context are the words before and after the current word. So, in this case, the input is <i>uncertainty</i> and the context is <i>think</i> and <i>about</i>. \n",
    "\n",
    "We want to maximize the likelihood of observing these two words, conditional on <i>uncertainty</i>.\n",
    "\n",
    "<b>GOAL:</b> \n",
    "\n",
    "$\n",
    "\\begin{align*}\n",
    "  \\max_{\\mathbf{U},\\mathbf{V}} p(about|uncertainty)p(think|uncertainty)\n",
    "\\end{align*}\n",
    "$\n",
    "\n",
    "What is $p(about|uncertainty)$? We calculated that above using the current estimates of $\\mathbf{U}$ and $\\mathbf{V}$. \n",
    "\n",
    "<b>GOAL:</b> \n",
    "\n",
    "$\n",
    "\\begin{align*}\n",
    "  \\max_{\\mathbf{U},\\mathbf{V}} \\frac{exp(\\mathbf{v_{about}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}\\frac{exp(\\mathbf{v_{think}^\\prime} \\mathbf{u_{uncertainty}})}{\\sum_{n=1}^{12} exp(\\mathbf{v_{n}^\\prime} \\mathbf{u_{uncertainty}})}\n",
    "\\end{align*}\n",
    "$\n",
    "\n",
    "It's much easier, we'll see, to maximize the $log$ of these quantities. Also, if we negate the previous expression and minimize the quantity nothing really changes. But the interpretation would be minimizing an error term. \n",
    "\n",
    "$\n",
    "\\begin{align*}\n",
    "\\min_{\\mathbf{U},\\mathbf{V}}  E &= -[log( p(think | uncertainty) )+log( p(about | uncertainty) )]\\\\\n",
    "&=-[log\\frac{exp(v_{think}^\\prime u_{uncertainty})}{\\sum_{j^\\prime=1}^V exp(v_{j}^\\prime u_{uncertainty})}+log\\frac{exp(v_{about}^\\prime u_{uncertainty})}{\\sum_{j^\\prime=1}^V exp(v_{j}^\\prime u_{uncertainty})}] \\\\\n",
    "&=-[v_{think}^\\prime u_{uncertainty}-log(\\sum_{j^\\prime=1}^V exp(v_{j}^\\prime u_{uncertainty}))+v_{about}^\\prime u_{uncertainty}-log(\\sum_{j^\\prime=1}^V exp(v_{j}^\\prime u_{uncertainty}))]\n",
    "\\end{align*}\n",
    "$\n",
    "\n",
    "### Updating specific word to understand mechanism ###\n",
    "How do we change $\\mathbf{v_{think}}$ given the current predictions?\\\\\n",
    "$\n",
    "\\begin{align*}\n",
    "\\frac{\\partial E}{\\partial v_{think}^\\prime} = -[u_{uncertainty} - 2\\frac{exp(\\mathbf{v_{think}}\\mathbf{u_{unc.}})}{\\sum_{n=1}^{V} exp(\\mathbf{v_{n}}\\mathbf{u_{unc.}})} u_{uncertainty}] = 2u_{uncertainty}(p(think|uncertainty)-\\frac{1}{2})\n",
    "\\end{align*}$\n",
    "\n",
    "More generally, we move around $\\mathbf{U}$ and $\\mathbf{V}$ so that the error improves (gradient descent)\n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align*}\n",
    "\\mathbf{V}^{new} = \\mathbf{V}^{old} - \\alpha\\frac{\\partial E}{\\partial \\mathbf{V}^{old}} \\\\\n",
    "\\mathbf{U}^{new} = \\mathbf{U}^{old} - \\alpha\\frac{\\partial E}{\\partial \\mathbf{U}^{old}}\n",
    "\\end{align*}\n",
    "$\n",
    "\n",
    "### General Updating V Matrix ###\n",
    "\n",
    "$\n",
    "\\begin{align*}\n",
    "\\frac{\\partial E}{\\partial \\mathbf{V}} &= \\sum_{m=-M}^{M}(\\mathbf{V}\\mathbf{u_{uncertainty}}-x_{w_m})\\frac{\\partial \\mathbf{V}\\mathbf{u_{uncertainty}}}{\\partial \\mathbf{V}} = \\sum_{m=-M}^{M}(\\mathbf{V}\\mathbf{u_{uncertainty}}-x_{w_m})\\mathbf{u_{uncertainty}^\\prime}\n",
    "\\end{align*}\n",
    "$\n",
    "\n",
    "Thus, we will update V as follows:\n",
    "\n",
    "$\n",
    "\\begin{align*}\n",
    "\\mathbf{V}^{new} = \\mathbf{V}^{old} - \\alpha [\\sum_{m=-M}^{M}\\delta_m^2 u_{uncertainty}^\\prime] \n",
    "\\end{align*}\n",
    "$\n",
    "\n",
    "where $\\delta_m^2= \\mathbf{V}\\mathbf{u_{uncertainty}}-x_{w_m}$\n",
    "\n",
    "### General Updating U Matrix ###\n",
    "\n",
    "$\n",
    "\\begin{align*}\n",
    "\\frac{\\partial E}{\\partial \\mathbf{U}} &= \\sum_{m=-M}^{M}(\\mathbf{V}\\mathbf{u_{uncertainty}}-x_{w_m})\\frac{\\partial \\mathbf{V}\\mathbf{u_{uncertainty}}}{\\partial \\mathbf{U}} = \\sum_{m=-M}^{M}\\mathbf{V}^\\prime(\\mathbf{V}\\mathbf{u_{uncertainty}}-x_{w_m})\\frac{\\partial \\mathbf{u_{uncertainty}}}{\\partial \\mathbf{U}} = \\sum_{m=-M}^{M}\\mathbf{V}^\\prime(\\mathbf{V}\\mathbf{u_{uncertainty}}-x_{w_m})\\frac{\\partial \\mathbf{U}x_{uncertainty}}{\\partial \\mathbf{U}} \\\\\n",
    "&= \\sum_{m=-M}^{M}\\mathbf{V}^\\prime \\delta_m^2 \\circ x_{uncertainty}\n",
    "\\end{align*}\n",
    "$\n",
    "\n",
    "where $\\circ$ is the [Hadamard Product](https://en.wikipedia.org/wiki/Hadamard_product_%28matrices%29).\n",
    "\n",
    "\n",
    "Thus, we will update U as follows:\n",
    "\n",
    "$\n",
    "\\begin{align*}\n",
    "\\mathbf{U}^{new} = \\mathbf{U}^{old} - \\alpha [\\sum_{m=-M}^{M} \\mathbf{V^T} \\delta_m^2 x_{uncertainty}^\\prime] \n",
    "\\end{align*}\n",
    "$\n",
    "\n",
    "## Implementation in Python ##\n",
    "\n",
    "First, let's load the relevant libraries and create our documents."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np \n",
    "import re\n",
    "import matplotlib.pyplot as plt\n",
    "from mpl_toolkits.mplot3d import Axes3D\n",
    "import itertools\n",
    "\n",
    "docs = [\"we think uncertainty about unemployment\",\n",
    "\t\t\"uncertainty and fears about inflation\",\n",
    "\t\t\"we think fears about unemployment\",\n",
    "\t\t\"we think fears and uncertainty about inflation and unemployment\",\n",
    "\t\t\"constant negative press covfefe\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we would like to find the unique words in our documents and then generate a one-hot encoded vector of length 12 for each word."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "docs_split = map(lambda x: x.split(),docs)\n",
    "docs_words = list(itertools.chain(*docs_split))\n",
    "words = np.unique(docs_words)\n",
    "\n",
    "vectors = np.eye(words.shape[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we will define the window size of the context, $M$. That is, how many words to look left and right for each word in order to traing the matrices. We will also define the matrices $\\mathbf{U}$ and $\\mathbf{V}$ as well as the number of dimensions in the hidden layer. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "M = 2\n",
    "H = 3\n",
    "\n",
    "U = np.random.randn(H,words.shape[0])\n",
    "V = np.random.randn(words.shape[0],H)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each word in each sentence, we need to know the context. We will create a function which takes in a sentence, in the form of a list of words, and then return the $M$ words to the left and right of each word in the sentence. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_context(word_list):\n",
    "\tsamples = []\n",
    "\tfor word_ind in range(len(word_list)):\n",
    "\t\tcontext_inds = range(max(0,word_ind-M),\n",
    "\t\t\t\t\t\t\tmin(word_ind+M+1,len(word_list)))\n",
    "\t\tcontext_inds.remove(word_ind)\n",
    "\t\tcontext = [word_list[el] for el in context_inds]\n",
    "\t\tsamples.append((word_list[word_ind],context))\n",
    "\treturn samples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's generate all the training examples, apply <b>get_context</b> to each sentence in <i>docs_split</i>, and then converting it to one list using itertools."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "training = list(itertools.chain(*map(get_context,docs_split)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Next, we will get to the meat of the code. We will run 10,000 <b>epochs</b>, which means looping through each word in each sentence 10,000 times. For each word, we will <b>forward propogate</b> the one-hot encoded vector and obtain a probability distribution over all 12 words in our vocabular. Then, for each word in the context, compute the error. Lastly, we will sum up the errors and then update the $\\mathbf{U}$ and $\\mathbf{V}$ matrices. \n",
    "\n",
    "Along the way, I will update the log likehood function, to ensure we are maximizing the probabilities. \n",
    "\n",
    "Also, I use a linear learning rate, so that each iteration it gets linearly closer to 0. I chose the default value of 2.5% but this is a <b>hyper parameter</b> (along with the H-Dimension in the hidden layer) which should be messed around with to get best results. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sigma(vector, deriv=False):\n",
    "\tif deriv:\n",
    "\t\treturn sigma(vector)*(1-sigma(vector))\n",
    "\telse:\n",
    "\t\treturn np.exp(vector)/np.exp(vector).sum()\n",
    "\n",
    "log_likelihood = np.array([])\n",
    "epochs = 10000\n",
    "learning_rate = 0.001\n",
    "tolerance = 0.001\n",
    "discount = float(learning_rate)/epochs\n",
    "\n",
    "for epoch in range(epochs):\n",
    "\tlikelihood = 0\n",
    "\tfor example in training:\n",
    "\t\t# Forward propogate word\n",
    "\t\tinput_index = np.where(words==example[0])[0][0]\n",
    "\t\tl_input = vectors[input_index]\n",
    "\t\tl_hidden = np.dot(U,l_input)\n",
    "\t\tl_output = np.dot(V,l_hidden)\n",
    "\t\tl_output_a = sigma(l_output)\n",
    "\t\terrors = np.zeros(words.shape[0])\n",
    "\t\t# Compute the error for each word in context window\n",
    "\t\tfor context in example[1]:\n",
    "\t\t\toutput_index = np.where(words==context)[0][0]\n",
    "\t\t\tl_target= vectors[output_index]\n",
    "\t\t\terrors += (l_output_a-l_target)\n",
    "\t\t# Update the weights of V and W matrices\n",
    "\t\tdelta2 = errors*sigma(l_output,True)\n",
    "\t\tV -= learning_rate*np.outer(delta2,l_hidden)\n",
    "\t\tU -= learning_rate*np.outer(np.dot(V.T,delta2),l_input)\n",
    "\t\tlikelihood+=sum(map(np.log,l_output_a))\n",
    "\tlog_likelihood=np.append(log_likelihood,likelihood)\n",
    "\tlearning_rate -= discount\n",
    "\tif epoch<2: continue\n",
    "\tif (abs(likelihood-log_likelihood[-2])<tolerance):\n",
    "\t\tbreak"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's plot out the word embeddings from the matrix $\\mathbf{U}$ along with the log likelihood function. Since the initialized $\\mathbf{U}$ and $\\mathbf{V}$ matrices were initialized to be random numbers from a normal distribution, you will get different results. Though the log likelihood and the proximity of words should be more or less similar. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "fig = plt.figure()\n",
    "ax = fig.add_subplot(1,2,1,projection=\"3d\")\n",
    "ax.scatter(U[0],U[1],U[2], alpha=0.3)\n",
    "for i,txt in enumerate(words):\n",
    "\tax.text(U[0][i],U[1][i],U[2][i],txt, size=10)\n",
    "ax = fig.add_subplot(1,2,2)\n",
    "ax.plot(log_likelihood)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"markdown/scatter.png\">\n",
    "<img src=\"markdown/ll.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#################################\n",
    "### Author: Paul Soto \t\t  ###\n",
    "### \t\tpaul.soto@upf.edu ###\n",
    "#\t\t\t\t\t\t\t\t#\n",
    "# This file is a script to run ##\n",
    "# a Skip Gram Model using a toy #\n",
    "# sample of documents. While ####\n",
    "# negative sampling should be ###\n",
    "# used to train the neural ######\n",
    "# network, I use gradient #######\n",
    "# descent to focus on the #######\n",
    "# architecture rather than the ##\n",
    "# optimal estimation ############\n",
    "#################################\n",
    "\n",
    "import numpy as np \n",
    "from collections import Counter\n",
    "import re\n",
    "import itertools\n",
    "import matplotlib.pyplot as plt\n",
    "from mpl_toolkits.mplot3d import Axes3D\n",
    "\n",
    "# M is the number of words to look (on one side) of each word for the context\n",
    "M = 2\n",
    "# H is the dimension of the hidden layer\n",
    "H = 3\n",
    "\n",
    "def sigma(vector, deriv=False):\n",
    "\t\"\"\"\n",
    "\tThis function returns a vector evaluated using the sigmoid function\n",
    "\n",
    "\tvector: numpy array of real values\n",
    "\tderiv: if True, evaluate first derivate of sigmoid \n",
    "\t\"\"\"\n",
    "\tif deriv:\n",
    "\t\treturn sigma(vector)*(1-sigma(vector))\n",
    "\telse:\n",
    "\t\treturn np.exp(vector)/np.exp(vector).sum()\n",
    "\n",
    "def get_context(word_list):\n",
    "\t\"\"\"\n",
    "\tThis function returns the 2*M words in the context of each word in \n",
    "\tthe list\n",
    "\n",
    "\tword_list: List of words\n",
    "\tM: global variable of the window size\n",
    "\t\"\"\"\n",
    "\tsamples = []\n",
    "\tfor word_ind in range(len(word_list)):\n",
    "\t\tcontext_inds = range(max(0,word_ind-M),\n",
    "\t\t\t\t\t\t\tmin(word_ind+M+1,len(word_list)))\n",
    "\t\tcontext_inds.remove(word_ind)\n",
    "\t\tcontext = [word_list[el] for el in context_inds]\n",
    "\t\tsamples.append((word_list[word_ind],context))\n",
    "\treturn samples\n",
    "\n",
    "docs = [\"we think uncertainty about unemployment\",\n",
    "\t\t\"uncertainty and fears about inflation\",\n",
    "\t\t\"we think fears about unemployment\",\n",
    "\t\t\"we think fears and uncertainty about inflation and unemployment\",\n",
    "\t\t\"constant negative press covfefe\"]\n",
    "\n",
    "\n",
    "# Split each document into a list of words\n",
    "docs_split = map(lambda x: x.split(),docs)\n",
    "docs_words = list(itertools.chain(*docs_split))\n",
    "\n",
    "# Find unique words across all documents\n",
    "words = np.unique(docs_words)\n",
    "\n",
    "# Generate a one hot encoded vector for each unique word\n",
    "vectors = np.eye(words.shape[0])\n",
    "\n",
    "# Initiate randomly V and W matrices\n",
    "U = np.random.randn(H,words.shape[0])\n",
    "V = np.random.randn(words.shape[0],H)\n",
    "\n",
    "# Create list of all training examples\n",
    "training = list(itertools.chain(*map(get_context,docs_split)))\n",
    "\n",
    "log_likelihood = np.array([])\n",
    "epochs = 10000\n",
    "learning_rate = 0.001\n",
    "tolerance = 0.001\n",
    "discount = float(learning_rate)/epochs\n",
    "\n",
    "for epoch in range(epochs):\n",
    "\tlikelihood = 0\n",
    "\tfor example in training:\n",
    "\t\t# Forward propogate word\n",
    "\t\tinput_index = np.where(words==example[0])[0][0]\n",
    "\t\tl_input = vectors[input_index]\n",
    "\t\tl_hidden = np.dot(U,l_input)\n",
    "\t\tl_output = np.dot(V,l_hidden)\n",
    "\t\tl_output_a = sigma(l_output)\n",
    "\t\terrors = np.zeros(words.shape[0])\n",
    "\t\t# Compute the error for each word in context window\n",
    "\t\tfor context in example[1]:\n",
    "\t\t\toutput_index = np.where(words==context)[0][0]\n",
    "\t\t\tl_target= vectors[output_index]\n",
    "\t\t\terrors += (l_output_a-l_target)\n",
    "\t\t# Update the weights of V and W matrices\n",
    "\t\tdelta2 = errors*sigma(l_output,True)\n",
    "\t\tV -= learning_rate*np.outer(delta2,l_hidden)\n",
    "\t\tU -= learning_rate*np.outer(np.dot(V.T,delta2),l_input)\n",
    "\t\tlikelihood+=sum(map(np.log,l_output_a))\n",
    "\tlog_likelihood=np.append(log_likelihood,likelihood)\n",
    "\tlearning_rate -= discount\n",
    "\tif epoch<2: continue\n",
    "\tif (abs(likelihood-log_likelihood[-2])<tolerance):\n",
    "\t\tbreak\n",
    "\n",
    "# Plot out word embeddings and log-likelihood function\n",
    "fig = plt.figure()\n",
    "ax = fig.add_subplot(1,2,1,projection=\"3d\")\n",
    "ax.scatter(U[0],U[1],U[2], alpha=0.3)\n",
    "for i,txt in enumerate(words):\n",
    "\tax.text(U[0][i],U[1][i],U[2][i],txt, size=10)\n",
    "ax = fig.add_subplot(1,2,2)\n",
    "ax.plot(log_likelihood)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I hope this was useful for you. Any questions or feedback please forward to my email paul.soto@upf.edu or message me on GitHub."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}