courses/CS22N-NLP/Word2Vec_from_scratch.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementing word2vec from scratch\n",
    "\n",
    "In this notebook we will implement word2vec (skipgram method) from scratch using numpy. To see detailed notes, go to lecture 1 notebook of CS224N - [Lecture-1-Introduction-and-Word-Vectors](Lecture-1-Introduction-and-Word-Vectors.ipynb). Some quick notes from there. \n",
    "\n",
    "- The word2vec is based on the linguistic principle that meaning of a word is defined by the company it keeps.  In other words, meaning of the word is defined by the words near it.\n",
    "- Word2vec creates Word Embeddings i.e. numerical representation of each word in a vector space. \n",
    "- Consider this sentence. \"The pacific northwest city Seattle is famous for it's iconic space needle, coffee shops and rainy weather\". The vector representation of \"Seattle\" is likely to be close to representation of words \"rainy\", \"coffee\", \"pacific\" and \"northwest\".\n",
    "- Word2vec is neural network model to generate these word embedding by training the model on a supervised classification problem. It has two approaches, in this note, we are focusing on \"Skip Gram\" method.  Given a center word, we want to train the model such that it can predict a nearby word. Given \"Seattle\", it can predict \"pacific\" or \"coffee\".\n",
    "- The idea is that if the word's vector representations can't predict the context words, we adjust this representation through backpropagation. In our example if Seattle's nearby word should be rainy, but if it is not we adjust the representation.\n",
    "- A well trained set of word vectors will place the similar words close to each other. \n",
    "- We initially initialize these representation as random vectors, and then with each iteration, we improve them to their true representation.\n",
    "- The size of the vector representation is arbitrary. It could be 50, 100, 3000. It is hyperparameter of the algorithm.\n",
    "- We go through each position *t* in the corpus, and define the word at position *t* as **c** and the nearby words called context words as **o**. The context words are the words which are *m* words left of **c** and *m* words right of **c**, essentially words between position *t-m* and *t+m* excluding *t* are context words **o** . *m* is also a hyperparameter of the algorithm.\n",
    "- We will want to maximize the likelihood of the context words given the center word.  In other words, we will calculate the probability of the model predicting context words given center word. This likelihood can be represented as\n",
    "    - $\\text{Likelihood} = L(\\theta) = \\displaystyle\\prod_{t=1}^{T}\\prod_{-m \\leq j \\leq m \\atop j \\neq 0} P(w_{t+j} | w_t; \\theta)$\n",
    "    - Representing it in more math friendly way.\n",
    "    - $ J(\\theta) = -\\frac{1}{T} log L(\\theta) = -\\frac{1}{T} \\displaystyle\\sum_{t=1}^{T}\\sum_{-m \\leq j \\leq m \\atop j \\neq 0} logP(w_{t+j} | w_t; \\theta)$\n",
    "\n",
    "\n",
    "\n",
    "## Variables\n",
    "\n",
    "We will use the following variables in our implementation of `word2vec`.\n",
    "\n",
    "- `V` : Number of unique words in the corpus (vocabulary)\n",
    "- `x` : Input layer (One hot encoding of our input word)\n",
    "- `N` : Number of neurons in the hidden layer of neural network i.e. the dimension of the vector representation of the word.\n",
    "- `W` : Weights between input layer and hidden layer.\n",
    "- `W'`: Weights between hidden layer and output layer.\n",
    "- `y` : A softmax layer having probabilities of each word in our corpus\n",
    "- `alpha` : Learning rate of the training. \n",
    "\n",
    "![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Fdailygrind%2FiX7rd0bVNJ.png?alt=media&token=5ac14c23-1165-4a20-be6c-c1dac015d50d)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation details\n",
    "\n",
    "As described in the lecture notebook, the idea is to go through the corpus and treat each token as center word, and tokens around it as context words\n",
    "\n",
    "- Input Layer (`x`): It is one hot encoding of the current center word. It's size of is *V* x 1, where *V* is the size of the vocabulary/unique words in corpus.\n",
    "- Weight Matrix (`W`) : It is the matrix of the representation of the all center words in the vocabulary. There will be *V* rows (one for each word in vocabulary) and each row vector has N dimension, hence its size is V x N.\n",
    "- Hidden Layer (`h`): It is nothing but representation of the center word in column vector. It is calculated by \n",
    "    $$\n",
    "        h = W^T.x\n",
    "    $$\n",
    "    h's dimension will be N x 1.\n",
    "- Weight Matrix 2 (`W'`): It is the matrix which stores the context word representation of each word in vocabulary. However, here each word is represented as column. There will be *V* columns of *N* dimension for each word in vocabulary. Thus shape will be N x V.\n",
    "\n",
    "- The intermediate output layer(`u`): This is the output we get when we find similary between the hidden layer `h` (center word represented as column vector) and the matrix representing the words as context words. \n",
    "    $$\n",
    "        u = W'^T.h\n",
    "    $$\n",
    "\n",
    "    Note that the dimension of W' is N x V and dimension of h is N x 1, thus u will be V x 1.\n",
    "\n",
    "    Let $u_j$ represents the $j^{th}$ neuron of the layer $u$ and $W_j$ be the $j^{th}$ word in vocabulary, where j is the $j^{th}$ word in vocabulary.\n",
    "    Thus $u_j$ is basically telling us score of how similar the center word (represented by h) and $j^th$ word is.\n",
    "\n",
    "- Output Layer (`y`):. We apply the softmax on the matrix u to get the output layer. The softmax converts the integer values to probability distribution. Thus $y_j$ value is telling us how similar the center word (represented by h) and $j^th$ word is. We compare `y`  with training data `y_train`. `y_train` is essentially a vector which is built from training data in such a way that if a word appears in context of center word, it's corresponding score is 1 in the `y_train` else 0. Comparing `y` and `y_train` lets us calculate the loss.\n",
    "\n",
    "- Forward propagation: The process of moving getting the output layer `y` from `x` is forward propagation.\n",
    "- Backward propagation: In this process, based on the loss we calculate using gradient descent, we propagate the updated values in backward direction and update the `W` and `W'` to get `y` as close as possible to `y_train`.\n",
    "\n",
    "- Initialization: We initialize the parameters we want to learn i.e `W` and `W'` to be randomly initialized.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from collections import defaultdict\n",
    "\n",
    "class word2vec(object):\n",
    "    def __init__(self):\n",
    "        self.N = 20\n",
    "        self.X_train = []\n",
    "        self.y_train = []\n",
    "        self.context_size = 5\n",
    "        self.alpha = 0.001\n",
    "        self.tokens = []\n",
    "        self.token_index = {}\n",
    "    \n",
    "    def initialize(self, V, corpus):\n",
    "        self.V = V\n",
    "        self.W = np.random.uniform(-0.8, 0.8, (self.V, self.N))\n",
    "        self.W1 = np.random.uniform(-0.8, 0.8, (self.N, self.V))\n",
    "        self.tokens = corpus\n",
    "        for i in range(len(corpus)):\n",
    "            self.token_index[corpus[i]] = i\n",
    "            \n",
    "    def softmax(self, x):\n",
    "        e_x = np.exp(x - np.max(x))\n",
    "        return e_x / e_x.sum()\n",
    "    \n",
    "    def forward_pass(self, X):\n",
    "        self.h = np.dot(self.W.T, X).reshape(self.N, 1)\n",
    "        self.u = np.dot(self.W1.T, self.h)\n",
    "        self.y = self.softmax(self.u)\n",
    "        return self.y\n",
    "    \n",
    "    def backward_pass(self, x, y):\n",
    "        error = self.y - np.asarray(y).reshape(self.V, 1)\n",
    "        #gradient wrt to w1\n",
    "        dLdw1 = np.dot(self.h, e.T)\n",
    "        X = np.array(x).reshape(self.V, 1)\n",
    "        #graident wrt to w\n",
    "        dLdw = np.dot(X, np.dot(self.W1, e).T)\n",
    "        self.W1 = self.W1 - self.alpha * dLdw1\n",
    "        self.W = self.W - self.alpha * dLdw\n",
    "\n",
    "    def train(self, epochs):\n",
    "        for x in range(epochs):\n",
    "            self.loss = 0\n",
    "            for j in range(len(self.X_train)):\n",
    "                self.forward_pass(self.X_train[j])\n",
    "                self.backward_pass(self.X_train[j], self.y_train[j])\n",
    "                C = 0\n",
    "                for k in range(self.V):\n",
    "                    if (self.y_train[j][k]):\n",
    "                        self.loss += -1 * self.u[k][0]\n",
    "                        C += 1\n",
    "                self.loss += C*np.log(np.sum(np.exp(self.u))) \n",
    "            print(\"epoch \",x, \" loss = \",self.loss) \n",
    "            self.alpha *= 1/( (1+self.alpha*x) ) \n",
    "    \n",
    "    def predict(self, word, num_of_predictions):\n",
    "        if word in self.tokens:\n",
    "            index = self.token_index[word]\n",
    "            # one hot encode\n",
    "            X = [0 for i in range(self.V)]\n",
    "            X[index] = 1\n",
    "            prediction = self.forward_pass(X)\n",
    "            output = {}\n",
    "            for i in range(self.V):\n",
    "                output[prediction[i][0]] = i\n",
    "            top_context_words = []\n",
    "            for k in sorted(output, reverse=True):\n",
    "                top_context_words.append(self.words[output[k]])\n",
    "                if (len(top_context_words) >= num_of_predictions):\n",
    "                    break\n",
    "            return top_context_words\n",
    "        else:\n",
    "            print(\"Word not in vocabulary\")\n",
    "            \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's just briefly test this"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "38\n",
      "Vocabulary size: 38\n",
      "Shape of training data:  (1, 216) (1, 216)\n",
      "Word to index:  {'a': 0, 'after': 1, 'and': 2, 'banana': 3, 'bananas': 4, 'been': 5, 'buckets.': 6, 'by': 7, 'carrying': 8, 'convince': 9, 'could': 10, 'death': 11, 'doing': 12, 'else': 13, 'everyone': 14, 'few': 15, 'fields': 16, 'give': 17, 'have': 18, 'heaven': 19, 'him': 20, 'history': 21, 'in': 22, 'is': 23, 'limitless': 24, 'monkey': 25, 'never': 26, 'people': 27, 'ploughing': 28, 'promising': 29, 'something': 30, 'that': 31, 'to': 32, 'very': 33, 'was': 34, 'water': 35, 'while': 36, 'you': 37}\n"
     ]
    }
   ],
   "source": [
    "corpus = ['''You could never convince a monkey to give you a banana by promising him limitless bananas after death in monkey heaven''',\n",
    "'''History is something that very few people have been doing while everyone else was ploughing fields and carrying water buckets.''']\n",
    "(X, y, word_index, index_word) = generate_training_data(corpus, context_size=3)\n",
    "vocab_size = len(index_word)\n",
    "print(\"Vocabulary size:\", vocab_size)\n",
    "print(\"Shape of training data: \", X.shape, y.shape)\n",
    "print(\"Word to index: \", word_index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will need each word to be represented as one-hot encoding representation. So let's do that too."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def word2OneHot(word, word_index):\n",
    "    vocab_size = len(word_index)\n",
    "    y_one_hot = np.zeros((vocab_size))\n",
    "    y_one_hot[word_index[word]] = 1\n",
    "    return y_one_hot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(38,)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0.])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word2OneHot('monkey', word_index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}