sample/nlp-word_mover_distance.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Word Mover's Distance\n",
    "\n",
    "![](https://cdn.pixabay.com/photo/2017/10/23/23/41/hong-kong-2883036_960_720.jpg)\n",
    "Photo: https://pixabay.com/en/hong-kong-harbor-boats-water-night-2883036/\n",
    "\n",
    "Word Mover's Distance (WMD) is proposed fro distance measurement between 2 documents (or sentences). It leverages Word Embeddings power to overcome those basic distance measurement limitations. \n",
    "\n",
    "WMD[1] was introduced by Kusner et al. in 2015. Instead of using Euclidean Distance and other bag-of-words based distance measurement, they proposed to use word embeddings to calculate the similarities. To be precise, it uses normalized [Bag-of-Words](https://towardsdatascience.com/3-basic-approaches-in-bag-of-words-which-are-better-than-word-embeddings-c2cbc7398016) and [Word Embeddings](https://medium.com/towards-data-science/3-silver-bullets-of-word-embedding-in-nlp-10fa8f50cc5a) to calculate the distance between documents.\n",
    "\n",
    "After reading this article, you will understand:\n",
    "- Earth Mover Distance (EMD)\n",
    "- Word Mover's Distance (WMD)\n",
    "- Relaxed Word Moving Distance (RWMD)\n",
    "- WMD Implementation\n",
    "- Take Away"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Earth Mover Distance (EMD)\n",
    "Before introducing WMD, I have to share the idea of Earth Mover Distance (EMD) first because the core part of WMD is EMD.\n",
    "\n",
    "EMD [2] solves transportation problem. For instance, we have m and n while m and n denote a set of suppliers and warehouses. The target is going to minimize transportation cost such that shipping all goods from m to n. Given that there are constraints:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "- Only allowing transport from m to n. Not allowing transport from n to m\n",
    "- Total number of sending cargoes cannot exceed total capacity of m\n",
    "- Total number of receiving cargoes cannot exceed total capacity of n\n",
    "- Maximum number of transportation is the minimum between total cargoes in m and total cargoes in n\n",
    "\n",
    "The denotations are:\n",
    "- p: Set of origin\n",
    "- q: Set of destination\n",
    "- f(i,j): flow from i to j\n",
    "- m: Number of origin\n",
    "- n: Number of destination\n",
    "- w(i, j): Number of cargo transport from i to j\n",
    "\n",
    "To optimal flow F, the linear formula is\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Word Mover's Distance (WMD)\n",
    "In the previous blog, I shared how we can use simple way to find the \"similarity\" between two documents (or sentences). At that time, Euclidean Distance, Cosine Distance and Jaccard Similarity are introduced but it has some limitations.  WMD is designed to __overcome synonym problem__.\n",
    "\n",
    "The typical example is \n",
    "- Sentence 1: Obama speaks to the media in Illinois\n",
    "- Sentence 2: The president greets the press in Chicago\n",
    "\n",
    "Except the stop words, there is no common words among two sentences but both of them are taking about same topic (at that time).\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "WMD use word embeddings to calculate the distance so that it can calculate even though there is no common word. The assumption is that similar words should have similar vectors.\n",
    "\n",
    "First of all, lower case and removing stopwords is an essential step to reduce complexity and preventing misleading. \n",
    "- Sentence 1: obama speaks media illinois\n",
    "- Sentence 2: president greets press chicago\n",
    "\n",
    "Retrieve vectors from any pre-trained word embeddings models. It can be GloVe, word2vec, fasttext or custom vectors. After that it using normalized bag-of-words (nBOW) to represent the weight or importance. It assumes that higher frequency implies that it is more important.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "It allows transfer every word from sentence 1 to sentence 2 because algorithm does not know \"obama\" should transfer to \"president\". At the end it will choose the minimum transportation cost to transport every word from sentence 1 to sentence 2.\n",
    "\n",
    "# Relaxed Word Moving Distance (RWMD)\n",
    "The best average time of solving WMD is about O(p³ log p) while p is number of unique word. It is a little bit slow so there are two approaches to improve the reduce computation time. First one is __Word Centroid Distance (WCD)__ which is summarizing the lower bound distance between. Second approach is __Relaxed Word Moving Distance (RWMD)__ which is using the closet distance without  considering there are multiple words transforming to single words.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "Taking the previous sentence as an example. Assuming that shortest word in sentence of all word in sentence 1 is \"president\", it will use summarize these score instead of pairing one by one. So that the time complexity reduce to O(p²).\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# WMD Implementation\n",
    "By using gensim, we only need to provide two list of tokens then it will take the rest of calculation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "    News headline get from \n",
    "    \n",
    "    https://www.reuters.com/article/us-musk-tunnel/elon-musks-boring-co-to-build-high-speed-airport-link-in-chicago-idUSKBN1JA224\n",
    "    http://money.cnn.com/2018/06/14/technology/elon-musk-boring-company-chicago/index.html\n",
    "    https://www.theverge.com/2018/6/13/17462496/elon-musk-boring-company-approved-tunnel-chicago\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "news_headline1 = \"Elon Musk's Boring Co to build high-speed airport link in Chicago\"\n",
    "news_headline2 = \"Elon Musk's Boring Company to build high-speed Chicago airport link\"\n",
    "news_headline3 = \"Elon Musk’s Boring Company approved to build high-speed transit between downtown Chicago and O’Hare Airport\"\n",
    "news_headline4 = \"Both apple and orange are fruit\"\n",
    "\n",
    "news_headlines = [news_headline1, news_headline2, news_headline3, news_headline4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "gensim version: 3.4.0\n"
     ]
    }
   ],
   "source": [
    "# Load Word Embedding Model\n",
    "import gensim\n",
    "print('gensim version: %s' % gensim.__version__)\n",
    "glove_model = gensim.models.KeyedVectors.load_word2vec_format('../model/text/stanford/glove/glove.6B.50d.vec')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['elon', 'musk', \"'s\", 'boring', 'co', 'build', 'high', '-', 'speed', 'airport', 'link', 'chicago'], ['elon', 'musk', \"'s\", 'boring', 'company', 'build', 'high', '-', 'speed', 'chicago', 'airport', 'link'], ['elon', 'musk', '’s', 'boring', 'company', 'approved', 'build', 'high', '-', 'speed', 'transit', 'downtown', 'chicago', 'o’hare', 'airport'], ['both', 'apple', 'orange', 'fruit']]\n"
     ]
    }
   ],
   "source": [
    "# Remove stopwords\n",
    "import spacy\n",
    "spacy_nlp = spacy.load('en')\n",
    "\n",
    "headline_tokens = []\n",
    "for news_headline in news_headlines:\n",
    "    headline_tokens.append([token.text.lower() for token in spacy_nlp(news_headline) if not token.is_stop])\n",
    "\n",
    "print(headline_tokens)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Headline:  Elon Musk's Boring Co to build high-speed airport link in Chicago\n",
      "==================================================\n",
      "\n",
      "--------------------------------------------------\n",
      "Comparing to: Elon Musk's Boring Co to build high-speed airport link in Chicago\n",
      "distance = 0.0000\n",
      "--------------------------------------------------\n",
      "Comparing to: Elon Musk's Boring Company to build high-speed Chicago airport link\n",
      "distance = 0.3589\n",
      "--------------------------------------------------\n",
      "Comparing to: Elon Musk’s Boring Company approved to build high-speed transit between downtown Chicago and O’Hare Airport\n",
      "distance = 1.9456\n",
      "--------------------------------------------------\n",
      "Comparing to: Both apple and orange are fruit\n",
      "distance = 5.4350\n"
     ]
    }
   ],
   "source": [
    "subject_headline = news_headlines[0]\n",
    "subject_token = headline_tokens[0]\n",
    "\n",
    "print('Headline: ', subject_headline)\n",
    "print('=' * 50)\n",
    "print()\n",
    "\n",
    "for token, headline in zip(headline_tokens, news_headlines):\n",
    "    print('-' * 50)\n",
    "    print('Comparing to:', headline)\n",
    "    distance = glove_model.wmdistance(subject_token, token)\n",
    "    print('distance = %.4f' % distance)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In gensim implementation, OOV will be removed so that it will not throw an exception or using random vector."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Take Away\n",
    "For source code, you may check out from my github repo.\n",
    "- The advantage of WMD are __hyper-parameter free and overcoming synonym problem__.\n",
    "- Same as those simple approaches, WMD __does not consider ordering__.\n",
    "- The __time complexity is an issue__. The original version is O(p³ log p) while the enhanced version is still O(p²).\n",
    "- __Pre-train vectors may not apply to all scenario__.\n",
    "\n",
    "# Reference\n",
    "[1] Kusner Matt J., Sun Yu, Kolkin Nicholas I., Weinberger Kilian Q. From Word Embeedings To Document Distance. 2015. http://proceedings.mlr.press/v37/kusnerb15.pdf\n",
    "[2] EMD Theory: https://en.wikipedia.org/wiki/Earth_mover%27s_distance"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}