2-svd-nmf-topic-modeling.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Topic Modeling with NMF and SVD"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Topic modeling is a fun way to start our study of NLP. We will use two popular **matrix decomposition techniques**. \n",
    "\n",
    "We start with a **term-document matrix**:\n",
    "\n",
    "<img src=\"images/document_term.png\" alt=\"term-document matrix\" style=\"width: 80%\"/>\n",
    "\n",
    "source: [Introduction to Information Retrieval](http://player.slideplayer.com/15/4528582/#)\n",
    "\n",
    "We can decompose this into one tall thin matrix times one wide short matrix (possibly with a diagonal matrix in between).\n",
    "\n",
    "Notice that this representation does not take into account word order or sentence structure.  It's an example of a **bag of words** approach."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Latent Semantic Analysis (LSA) uses Singular Value Decomposition (SVD)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Motivation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the most extreme case - reconstructing the matrix using an outer product of two vectors. Clearly, in most cases we won't be able to reconstruct the matrix exactly. But if we had one vector with the relative frequency of each vocabulary word out of the total word count, and one with the average number of words per document, then that outer product would be as close as we can get.\n",
    "\n",
    "Now consider increasing that matrices to two columns and two rows. The optimal decomposition would now be to cluster the documents into two groups, each of which has as different a distribution of words as possible to each other, but as similar as possible amongst the documents in the cluster. We will call those two groups \"topics\". And we would cluster the words into two groups, based on those which most frequently appear in each of the topics. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Getting started"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll take a dataset of documents in several different categories, and find topics (consisting of groups of words) for them.  Knowing the actual categories helps us evaluate if the topics we find make sense.\n",
    "\n",
    "We will try this with two different matrix factorizations: **Singular Value Decomposition (SVD)** and **Non-negative Matrix Factorization (NMF)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn.datasets import fetch_20newsgroups\n",
    "from sklearn import decomposition\n",
    "from scipy import linalg\n",
    "import matplotlib.pyplot as plt\n",
    "import spacy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "np.set_printoptions(suppress=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Additional Resources"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- [Data source](http://scikit-learn.org/stable/datasets/twenty_newsgroups.html): Newsgroups are discussion groups on Usenet, which was popular in the 80s and 90s before the web really took off.  This dataset includes 18,000 newsgroups posts with 20 topics.\n",
    "- [Chris Manning's book chapter](https://nlp.stanford.edu/IR-book/pdf/18lsi.pdf) on matrix factorization and LSI \n",
    "- Scikit learn [truncated SVD LSI details](http://scikit-learn.org/stable/modules/decomposition.html#lsa)\n",
    "\n",
    "### Other Tutorials\n",
    "- [Scikit-Learn: Out-of-core classification of text documents](http://scikit-learn.org/stable/auto_examples/applications/plot_out_of_core_classification.html): uses [Reuters-21578](https://archive.ics.uci.edu/ml/datasets/reuters-21578+text+categorization+collection) dataset (Reuters articles labeled with ~100 categories), HashingVectorizer\n",
    "- [Text Analysis with Topic Models for the Humanities and Social Sciences](https://de.dariah.eu/tatom/index.html): uses [British and French Literature dataset](https://de.dariah.eu/tatom/datasets.html) of Jane Austen, Charlotte Bronte, Victor Hugo, and more"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Look at our data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Scikit Learn comes with a number of built-in datasets, as well as loading utilities to load several standard external datasets. This is a [great resource](http://scikit-learn.org/stable/datasets/), and the datasets include Boston housing prices, face images, patches of forest, diabetes, breast cancer, and more.  We will be using the newsgroups dataset.\n",
    "\n",
    "Newsgroups are discussion groups on Usenet, which was popular in the 80s and 90s before the web really took off.  This dataset includes 18,000 newsgroups posts with 20 topics.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "categories = ['alt.atheism', 'talk.religion.misc', 'comp.graphics', 'sci.space']\n",
    "remove = ('headers', 'footers', 'quotes')\n",
    "newsgroups_train = fetch_20newsgroups(subset='train', categories=categories, remove=remove)\n",
    "newsgroups_test = fetch_20newsgroups(subset='test', categories=categories, remove=remove)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((2034,), (2034,))"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "newsgroups_train.filenames.shape, newsgroups_train.target.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at some of the data.  Can you guess which category these messages are in?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hi,\n",
      "\n",
      "I've noticed that if you only save a model (with all your mapping planes\n",
      "positioned carefully) to a .3DS file that when you reload it after restarting\n",
      "3DS, they are given a default position and orientation.  But if you save\n",
      "to a .PRJ file their positions/orientation are preserved.  Does anyone\n",
      "know why this information is not stored in the .3DS file?  Nothing is\n",
      "explicitly said in the manual about saving texture rules in the .PRJ file. \n",
      "I'd like to be able to read the texture rule information, does anyone have \n",
      "the format for the .PRJ file?\n",
      "\n",
      "Is the .CEL file format available from somewhere?\n",
      "\n",
      "Rych\n",
      "\n",
      "\n",
      "Seems to be, barring evidence to the contrary, that Koresh was simply\n",
      "another deranged fanatic who thought it neccessary to take a whole bunch of\n",
      "folks with him, children and all, to satisfy his delusional mania. Jim\n",
      "Jones, circa 1993.\n",
      "\n",
      "\n",
      "Nope - fruitcakes like Koresh have been demonstrating such evil corruption\n",
      "for centuries.\n",
      "\n",
      " >In article <1993Apr19.020359.26996@sq.sq.com>, msb@sq.sq.com (Mark Brader) \n",
      "\n",
      "MB>                                                             So the\n",
      "MB> 1970 figure seems unlikely to actually be anything but a perijove.\n",
      "\n",
      "JG>Sorry, _perijoves_...I'm not used to talking this language.\n",
      "\n",
      "Couldn't we just say periapsis or apoapsis?\n",
      "\n",
      " \n"
     ]
    }
   ],
   "source": [
    "print(\"\\n\".join(newsgroups_train.data[:3]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "hint: definition of *perijove* is the point in the orbit of a satellite of Jupiter nearest the planet's center "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array(['comp.graphics', 'talk.religion.misc', 'sci.space'], dtype='<U18')"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.array(newsgroups_train.target_names)[newsgroups_train.target[:3]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The target attribute is the integer index of the category."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 3, 2, 0, 2, 0, 2, 1, 2, 1], dtype=int64)"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "newsgroups_train.target[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_topics, num_top_words = 6, 8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stop words, stemming, lemmatization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Stop words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From [Intro to Information Retrieval](https://nlp.stanford.edu/IR-book/html/htmledition/dropping-common-terms-stop-words-1.html):\n",
    "\n",
    "*Some extremely common words which would appear to be of little value in helping select documents matching a user need are excluded from the vocabulary entirely. These words are called stop words.*\n",
    "\n",
    "*The general trend in IR systems over time has been from standard use of quite large stop lists (200-300 terms) to very small stop lists (7-12 terms) to no stop list whatsoever. Web search engines generally do not use stop lists.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### NLTK"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a',\n",
       " 'about',\n",
       " 'above',\n",
       " 'across',\n",
       " 'after',\n",
       " 'afterwards',\n",
       " 'again',\n",
       " 'against',\n",
       " 'all',\n",
       " 'almost',\n",
       " 'alone',\n",
       " 'along',\n",
       " 'already',\n",
       " 'also',\n",
       " 'although',\n",
       " 'always',\n",
       " 'am',\n",
       " 'among',\n",
       " 'amongst',\n",
       " 'amoungst']"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sklearn.feature_extraction import stop_words\n",
    "\n",
    "sklearn_stop_words = sorted(list(stop_words.ENGLISH_STOP_WORDS))\n",
    "\n",
    "# sorted(list(stop_words.ENGLISH_STOP_WORDS))[:20]\n",
    "\n",
    "sklearn_stop_words[:20]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is no single universal list of stop words."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Stemming and Lemmatization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "from [Information Retrieval](https://nlp.stanford.edu/IR-book/html/htmledition/stemming-and-lemmatization-1.html) textbook:\n",
    "\n",
    "Are the below words the same?\n",
    "\n",
    "*organize, organizes, and organizing*\n",
    "\n",
    "*democracy, democratic, and democratization*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Stemming and Lemmatization both generate the root form of the words. \n",
    "\n",
    "Lemmatization uses the rules about a language.  The resulting tokens are all actual words\n",
    "\n",
    "\"Stemming is the poor-man’s lemmatization.\" (Noah Smith, 2011) Stemming is a crude heuristic that chops the ends off of words.  The resulting tokens may not be actual words. Stemming is faster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[nltk_data] Downloading package wordnet to C:\\Users\\cross-\n",
      "[nltk_data]     entropy\\AppData\\Roaming\\nltk_data...\n",
      "[nltk_data]   Package wordnet is already up-to-date!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import nltk\n",
    "nltk.download('wordnet')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk import stem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "wnl = stem.WordNetLemmatizer()\n",
    "porter = stem.porter.PorterStemmer()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "word_list = ['feet', 'foot', 'foots', 'footing']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['foot', 'foot', 'foot', 'footing']"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[wnl.lemmatize(word) for word in word_list]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['feet', 'foot', 'foot', 'foot']"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[porter.stem(word) for word in word_list]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your turn!  Now, try lemmatizing and stemming the following collections of words:\n",
    "\n",
    "- fly, flies, flying\n",
    "- organize, organizes, organizing\n",
    "- universe, university"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "fastai/course-nlp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Stemming and lemmatization are language dependent.  Languages with more complex morphologies may show bigger benefits.  For example, Sanskrit has a very [large number of verb forms](https://en.wikipedia.org/wiki/Sanskrit_verbs). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Spacy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Stemming and lemmatization are implementation dependent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Spacy is a very modern & fast nlp library. Spacy is opinionated, in that it typically offers one highly optimized way to do something (whereas nltk offers a huge variety of ways, although they are usually not as optimized).\n",
    "\n",
    "You will need to install it.\n",
    "\n",
    "if you use conda:\n",
    "```\n",
    "conda install -c conda-forge spacy\n",
    "```\n",
    "if you use pip:\n",
    "```\n",
    "pip install -U spacy\n",
    "```\n",
    "\n",
    "You will then need to download the English model:\n",
    "```\n",
    "spacy -m download en_core_web_sm\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "import spacy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [],
   "source": [
    "from spacy.lemmatizer import Lemmatizer\n",
    "lemmatizer = Lemmatizer()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['feet', 'foot', 'foots', 'footing']"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[lemmatizer.lookup(word) for word in word_list]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Spacy doesn't offer a stemmer (since lemmatization is considered better-- this is an example of being opinionated!)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Stop words vary from library to library"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "nlp = spacy.load(\"en_core_web_sm\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a',\n",
       " 'about',\n",
       " 'above',\n",
       " 'across',\n",
       " 'after',\n",
       " 'afterwards',\n",
       " 'again',\n",
       " 'against',\n",
       " 'all',\n",
       " 'almost',\n",
       " 'alone',\n",
       " 'along',\n",
       " 'already',\n",
       " 'also',\n",
       " 'although',\n",
       " 'always',\n",
       " 'am',\n",
       " 'among',\n",
       " 'amongst',\n",
       " 'amount']"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "spacy_stop_words = sorted(list(nlp.Defaults.stop_words))#[:20]\n",
    "spacy_stop_words[:20]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise: What stop words appear in spacy but not in sklearn?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['ca', 'did', 'does', 'doing', 'just', 'make', 'quite', 'really', 'regarding', 'say', 'unless', 'used', 'using', 'various']\n"
     ]
    }
   ],
   "source": [
    "#Exercise:\n",
    "spacy_but_not_sklearn = [word for word in spacy_stop_words if word not in sklearn_stop_words]\n",
    "print(spacy_but_not_sklearn)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "#### Exercise: And what stop words are in sklearn but not spacy?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['amoungst', 'bill', 'cant', 'co', 'con', 'couldnt', 'cry', 'de', 'describe', 'detail', 'eg', 'etc', 'fill', 'find', 'fire', 'found', 'hasnt', 'ie', 'inc', 'interest', 'ltd', 'mill', 'sincere', 'system', 'thick', 'thin', 'un']\n"
     ]
    }
   ],
   "source": [
    "#Exercise:\n",
    "sklearn_but_not_spacy = [word for word in sklearn_stop_words if word not in spacy_stop_words]\n",
    "print(sklearn_but_not_spacy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "### When to use these?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<img src=\"images/skomoroch.png\" alt=\"\" style=\"width: 65%\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "These were long considered standard techniques, but they can often **hurt** your performance **if using deep learning**. Stemming, lemmatization, and removing stop words all involve throwing away information.\n",
    "\n",
    "However, they can still be useful when working with simpler models."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "### Another approach: sub-word units"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "[SentencePiece](https://github.com/google/sentencepiece) library from Google"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data Processing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, scikit learn has a method that will extract all the word counts for us.  In the next lesson, we'll learn how to write our own version of CountVectorizer, to see what's happening underneath the hood."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.feature_extraction.text import CountVectorizer, TfidfVectorizer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "import nltk\n",
    "# nltk.download('punkt')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "# from nltk import word_tokenize\n",
    "\n",
    "# class LemmaTokenizer(object):\n",
    "#     def __init__(self):\n",
    "#         self.wnl = stem.WordNetLemmatizer()\n",
    "#     def __call__(self, doc):\n",
    "#         return [self.wnl.lemmatize(t) for t in word_tokenize(doc)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "vectorizer = CountVectorizer(stop_words='english') #, tokenizer=LemmaTokenizer())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2034, 26576)"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vectors = vectorizer.fit_transform(newsgroups_train.data).todense() # (documents, vocab)\n",
    "vectors.shape #, vectors.nnz / vectors.shape[0], row_means.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2034 (2034, 26576)\n"
     ]
    }
   ],
   "source": [
    "print(len(newsgroups_train.data), vectors.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [],
   "source": [
    "vocab = np.array(vectorizer.get_feature_names())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(26576,)"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vocab.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array(['cosmonauts', 'cosmos', 'cosponsored', 'cost', 'costa', 'costar',\n",
       "       'costing', 'costly', 'costruction', 'costs', 'cosy', 'cote',\n",
       "       'couched', 'couldn', 'council', 'councils', 'counsel',\n",
       "       'counselees', 'counselor', 'count'], dtype='<U80')"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vocab[7000:7020]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Singular Value Decomposition (SVD)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\"SVD is not nearly as famous as it should be.\" - Gilbert Strang"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We would clearly expect that the words that appear most frequently in one topic would appear less frequently in the other - otherwise that word wouldn't make a good choice to separate out the two topics. Therefore, we expect the topics to be **orthogonal**.\n",
    "\n",
    "The SVD algorithm factorizes a matrix into one matrix with **orthogonal columns** and one with **orthogonal rows** (along with a diagonal matrix, which contains the **relative importance** of each factor).\n",
    "\n",
    "<img src=\"images/svd_fb.png\" alt=\"\" style=\"width: 80%\"/>\n",
    "(source: [Facebook Research: Fast Randomized SVD](https://research.fb.com/fast-randomized-svd/))\n",
    "\n",
    "SVD is an **exact decomposition**, since the matrices it creates are big enough to fully cover the original matrix. SVD is extremely widely used in linear algebra, and specifically in data science, including:\n",
    "\n",
    "- semantic analysis\n",
    "- collaborative filtering/recommendations ([winning entry for Netflix Prize](https://datajobs.com/data-science-repo/Recommender-Systems-%5BNetflix%5D.pdf))\n",
    "- calculate Moore-Penrose pseudoinverse\n",
    "- data compression\n",
    "- principal component analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Latent Semantic Analysis (LSA) uses SVD.  You will sometimes hear topic modelling referred to as LSA."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 8.9 s\n"
     ]
    }
   ],
   "source": [
    "%time U, s, Vh = linalg.svd(vectors, full_matrices=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2034, 2034) (2034,) (2034, 26576)\n"
     ]
    }
   ],
   "source": [
    "print(U.shape, s.shape, Vh.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Confirm this is a decomposition of the input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([433.92698542, 291.51012741, 240.71137677, 220.00048043])"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s[:4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([433.92698542, 291.51012741, 240.71137677, 220.00048043])"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.diag(np.diag(s[:4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Exercise: confrim that U, s, Vh is a decomposition of `vectors`\n",
    "assert(np.allclose(vectors,U@np.diag(s)@Vh))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Confirm that U, V are orthonormal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "#### Answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "#Exercise: Confirm that U, Vh are orthonormal\n",
    "\n",
    "# *Columns* of U are orthogonal\n",
    "identity_matrix = np.eye((U.T@U).shape[0])\n",
    "assert(np.allclose(U.T@U,identity_matrix_U))\n",
    "\n",
    "# *rows* of Vh are orthogonal\n",
    "assert(np.allclose(Vh@Vh.T,identity_matrix))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "#### Topics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "What can we say about the singular values s?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD4CAYAAAAXUaZHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAZTElEQVR4nO3dfZAcd33n8fe3e/ZJ2tXzShaSQDYIsCsVbCOIEgJ1wYljTIKcB185lzvrOAdXKpCDIleJc9TlclVXdfgugcSVlBMndiFTToBAKKsoE3AZ+5yrAtsrP9sylmxsa5GQ1nqW9nFmvvdH/2a3Z6dX+6B56tHnVTXVPb/umfmqZ/Xp3/ymp9vcHRER6SxRqwsQEZH6U7iLiHQghbuISAdSuIuIdCCFu4hIByq0ugCAdevW+datW1tdhohIruzdu/dNdx/MWtYW4b5161aGhoZaXYaISK6Y2etzLdOwjIhIB1K4i4h0IIW7iEgHUriLiHQghbuISAdSuIuIdCCFu4hIB8p1uD/x2nG+8N0fMlkst7oUEZG2kutw3/v6Ce743gGKZYW7iEharsPdwlTXGxERqZbvcA/prmwXEamW73Cf7ruLiEharsO9QteBFRGplutw17CMiEi2XId7hTruIiLVch3upq67iEimfId7mLrSXUSkSr7DvdJxV7aLiFTJd7iHqbJdRKRavsPddJy7iEiWXId7hY5zFxGptuBwN7PYzJ4ys2+F+5ea2WNmtt/Mvmpm3aG9J9w/EJZvbUzpOs5dRGQui+m5fxrYl7p/O/BFd98GnABuCe23ACfc/R3AF8N6DaETh4mIZFtQuJvZZuCjwN+H+wZ8GPh6WGU3cEOY3xnuE5ZfY40aHA9Pq0MhRUSqLbTn/hfAHwKVE6evBU66ezHcHwY2hflNwEGAsPxUWL+Kmd1qZkNmNjQyMrKk4qf3GMp2EZEq84a7mf0KcNTd96abM1b1BSybaXC/y923u/v2wcHBBRVbW9scTy4icpErLGCdDwAfM7PrgV5gBUlPfpWZFULvfDNwKKw/DGwBhs2sAKwEjte9cmZO+asxdxGRavP23N39j919s7tvBW4Cvufuvw08DPxmWG0XcH+Y3xPuE5Z/zxt0rOJMz13pLiKSdiHHuf8R8FkzO0Aypn53aL8bWBvaPwvcdmElzk0/YRIRybaQYZlp7v4I8EiYfxV4f8Y648CNdahtEXU189VERNpfrn+hqi9URUSy5Tvcp79QVbyLiKTlOtzRKX9FRDLlOtz1haqISLZ8h7vpOHcRkSz5Dvcw1XHuIiLV8h3uGpcREcmU63Cv0LCMiEi1XIe7jnMXEcmW73DXce4iIpnyHe7quYuIZMp1uFeo4y4iUi3X4T5z9T6lu4hIWr7DPUzVcxcRqZbvcNdx7iIimXId7hXquIuIVMt1uOsaqiIi2fId7rqGqohIpnyHe5iq5y4iUi3f4a6LdYiIZMp1uFf67hqWERGplutwV89dRCRbvsO91QWIiLSpXIe7iIhky3W46xqqIiLZ8h3uYaovVEVEquU73PWFqohIps4I99aWISLSdvId7rrMnohIplyHO+q5i4hkynW469wyIiLZ8h3uulqHiEimXIf7DHXdRUTSch3uGpYREcmW73DXF6oiIpnyHe66zJ6ISKZ5w93Mes3scTN7xsxeMLP/EdovNbPHzGy/mX3VzLpDe0+4fyAs39qo4md+oap0FxFJW0jPfQL4sLu/B7gSuM7MdgC3A190923ACeCWsP4twAl3fwfwxbBeQ8ycW0ZERNLmDXdPnA13u8LNgQ8DXw/tu4EbwvzOcJ+w/Bpr1DGLOreMiEimBY25m1lsZk8DR4EHgVeAk+5eDKsMA5vC/CbgIEBYfgpYm/Gct5rZkJkNjYyMLKl40+U6REQyLSjc3b3k7lcCm4H3A5dnrRamWYlb07d297vcfbu7bx8cHFxovdn1aWBGRKTKoo6WcfeTwCPADmCVmRXCos3AoTA/DGwBCMtXAsfrUexspkF3EZFMCzlaZtDMVoX5PuAXgX3Aw8BvhtV2AfeH+T3hPmH597xBh7Mo20VEshXmX4WNwG4zi0l2Bl9z92+Z2YvAV8zsfwJPAXeH9e8GvmxmB0h67Dc1oG5Al9kTEZnLvOHu7s8CV2W0v0oy/j67fRy4sS7VzWPmF6pKdxGRtJz/QjWhnruISLV8h7vOLSMikinX4Z591KWIiOQ83BM6t4yISLVch7uGZUREsuU73CszSncRkSr5DvfKce5KdxGRKvkO9zDVkLuISLV8h7tO+Ssikinf4V65zF6L6xARaTf5Dncd5i4ikinX4V6h49xFRKp1Rri3ugARkTaT63DXF6oiItnyHe66XIeISKZ8h7t67iIimToj3FtbhohI28l3uKPL7ImIZMl3uOsyeyIimfId7q0uQESkTeU63Cs0LCMiUi3X4V455W9Z6S4iUiXX4V6IknAvlRXuIiJpuQ73OIR7UeEuIlIl1+FeiNVzFxHJku9wj5Ly1XMXEamW83APPfdSucWViIi0l1yHexxrzF1EJEuuw11Hy4iIZMt1uOtoGRGRbPkO9/AjpmJJ4S4ikpbvcK8My+gXqiIiVXId7mZGZFDWsIyISJVchzskvXf13EVEquU+3CMz9dxFRGbJfbgXItPRMiIis+Q+3KPIdJy7iMgs84a7mW0xs4fNbJ+ZvWBmnw7ta8zsQTPbH6arQ7uZ2R1mdsDMnjWzqxv5D4gj0/ncRURmWUjPvQj8gbtfDuwAPmlmVwC3AQ+5+zbgoXAf4CPAtnC7Fbiz7lWnFNRzFxGpMW+4u/thd38yzJ8B9gGbgJ3A7rDabuCGML8TuNcTPwBWmdnGulceRKZwFxGZbVFj7ma2FbgKeAzY4O6HIdkBAOvDapuAg6mHDYe22c91q5kNmdnQyMjI4isPYvXcRURqLDjczawf+AbwGXc/fb5VM9pq0tfd73L37e6+fXBwcKFl1IhMx7mLiMy2oHA3sy6SYL/P3f85NB+pDLeE6dHQPgxsST18M3CoPuXWKsQ6zl1EZLaFHC1jwN3APnf/QmrRHmBXmN8F3J9qvzkcNbMDOFUZvmmE2HScu4jIbIUFrPMB4D8Az5nZ06HtvwKfB75mZrcAbwA3hmUPANcDB4BR4ON1rXiWSIdCiojUmDfc3f3/kT2ODnBNxvoOfPIC61qwWEfLiIjUyP0vVJOjZVpdhYhIe+mQcFe6i4ik5T7co8jQhZhERKrlPtxjXaxDRKRG7sO9EEX6QlVEZJbch3sUoXAXEZkl9+Guy+yJiNTKfbjrrJAiIrVyH+46n7uISK3ch3scRTq3jIjILLkP965YP2ISEZkt9+EeRzorpIjIbLkPd425i4jUyn24x1FEUecfEBGpkvtw74qNosbcRUSq5D7cdYFsEZFauQ/3gr5QFRGpkftw15i7iEit3Id7QWPuIiI18h/uGnMXEanREeGuMXcRkWq5D/c4inDXOd1FRNJyH+6F2AA07i4ikpL/cI+ScFfPXURkRu7DPY4qPXeFu4hIRe7DvdJz17HuIiIzch/uy3oKAJwem2pxJSIi7SP34b5pVR8Ah0+Nt7gSEZH2kftwH+hNeu7nJootrkREpH3kPtyXh2GZc5MKdxGRityHe38I97PquYuITMt9uE/33BXuIiLTch/uy7piAM5OlFpciYhI+8h9uEeRsWFFDz9681yrSxERaRu5D3eAzauXceLcZKvLEBFpGx0R7su6Y0Z1tIyIyLR5w93M7jGzo2b2fKptjZk9aGb7w3R1aDczu8PMDpjZs2Z2dSOLr0jCXWPuIiIVC+m5fwm4blbbbcBD7r4NeCjcB/gIsC3cbgXurE+Z57e8u6Dj3EVEUuYNd3d/FDg+q3knsDvM7wZuSLXf64kfAKvMbGO9ip1LX3fMmHruIiLTljrmvsHdDwOE6frQvgk4mFpvOLTVMLNbzWzIzIZGRkaWWEZieU+BczoUUkRkWr2/ULWMtsxz8br7Xe6+3d23Dw4OXtCLLuuOGZsq6YIdIiLBUsP9SGW4JUyPhvZhYEtqvc3AoaWXtzDLupMfMo1NqfcuIgJLD/c9wK4wvwu4P9V+czhqZgdwqjJ800jLupNTEOhwSBGRRGG+FczsH4F/A6wzs2HgvwOfB75mZrcAbwA3htUfAK4HDgCjwMcbUHON5T1Jz310ogQDzXhFEZH2Nm+4u/tvzbHomox1HfjkhRa1WH1dOu2viEhaR/xCtdJz1+GQIiKJjgj3ypj7GZ32V0QE6JBwf8uqXgAOnRxrcSUiIu2hI8J9w0Av3YWIN46NtroUEZG20BHhHkXGltV9vK5wFxEBOiTcAdYP9HLs3ESryxARaQsdE+467a+IyIzOCfeegsJdRCTomHBf19/N4VNjjOv8MiIinRPuv/Cu9YxPlfn+K8daXYqISMt1TLj/9OaVALwycrbFlYiItF7HhPvKvi4Gegq8cVyHQ4qIdEy4mxlb1ixTuIuI0EHhDnD5xhU8/qPjlHVFJhG5yHVUuO+4bA2jkyWeeG329bxFRC4uHRXuH353cp3upw+ebHElIiKt1VHhvra/hys2ruDre4dJrhsiInJx6qhwB/jEhy5l/9Gz7Hmm4dflFhFpWx0X7h97zyYu37iC27/9kq7MJCIXrY4L9zgy/ttHL+fQqXH+5P7nW12OiEhLdFy4A/zcO9bxiQ9eyj/tHebhl462uhwRkabryHAH+INr38W29f383n1P8p0XftLqckREmqpjw723K+a+3/kZ3nnJAL//D0/x4ItHWl2SiEjTdGy4A6xf0cuX/uP7uGxwOZ+4d4g7H3ml1SWJiDRFR4c7wOrl3ez51M9z7RUbuP1fXuJ/PbCP0cliq8sSEWmojg93gO5CxJ3//r3c9L4t/O2jr/ILf/YIX3viICWdg0ZEOtRFEe6QHCL5+d/4ab7+uz/LxpV9/OE3nuWjd/wrj7480urSRETq7qIJ94rtW9fwzd/7Of7q313FuckiN9/zODff8zjff+UYxVK51eWJiNSFtcM5WLZv3+5DQ0NNf92JYokvf/917nhoP6fHi6xd3s3OKzdx4/bNvPuSAcys6TWJiCyUme119+2Zyy7mcK84O1Hk0ZdH+Nazh3jwxSNMlZzBgR6uvWID733banZctpaNK3sV9iLSVhTui3Ds7ATfffEI/7p/hIdfGmFsKjk/zbr+bi7fuCLcBnj3JSt4+2A/3YWLbmRLRNqEwn2JSmVn3+HT7H39BM/9+BQv/eQ0Lx85y2QxGZvvio23D/azbcMAm1f3hdsyNq/uY9OqPnq74hb/C0Skk50v3AvNLiZP4sj4qU0r+alNK6fbiqUyr755jn2HT7Pv8Bn2HT7NMwdP8i/PH2aqVL2jXLu8m0tW9nLJil42rOxlw0Av61f0sGFFD+sHelk/0MPq5d10xer9i0h9KdwXqRBHvHPDAO/cMMDOK2faS2XnyOlxfnxyjOEToxw8PsbhU+P85NQYh06N89TBkxw/N5n5nCt6C6zt72Ht8m7WLO9mbX8yXb2sm5V9XawK08ptRV+Bvq5Y3wGIyJwU7nUSR8ZbVvXxllV9vG/rmsx1JotlRs5OcPT0OEdOTzByZpxj5yY5fm4ymZ6d5PVjozz5xglOjE6d90dWXbHR31Ogv7dAf08XA2F+eU+B/p4CA73JDmBZd3Lr6y6Eacyyrphl3QX6uqOkvStp7ylE2mGIdAiFexN1FyI2rUrG4+dTLjtnJoqcGp3i1FhyOzk2yemxIqfHk/vnJoqcGU9uZyemGDkzwY/ePMfZiSJnx4vTXwYvVBwZvYWIvu6Y3q4k7LviiJ5CRHeY7y5EdMcRXYWInnhWe1iWnlYvszCNw7Lkfk/Gc3fHyS2KtLMRWQqFe5uKIpsehlmqctkZmyoxOllibLLE6FRxZn6yxOhkcXo+Wa/I+FSZsakS45MlJoplJktlJoszt7MTxWQ+1T5VmS+Va753uFBdsVUH/xw7m+6aHdHMjqSrYPSExxbiiEJkFGKjEBlxFE3PV5bFkdEVJ8u6wv1knYi4cj8yosim159pj4jNiMNzRjazrkgzNSTczew64C+BGPh7d/98I15Hzi+KjOU9yVBNs5TLzlQ5Hfwegr/EZNFrdgqVHchUaocx3Z6xrGanEu6PjhaZLDmTxVJ4jNc8ppXMSEK/ZscQEUdU7Tim17FkpxJHNv3Y9PL0DqVqR5Oxc4nDa8Y2M40jUvPJuun14ojptjj13FWPmW6jpi39nOnnSj/n9HzlOWratFNcqrr/rzezGPhr4JeAYeAJM9vj7i/W+7Wk/USR0RPF9BTa6zBQd6dYdkplZ6pUDtPkfrFcpliqXV5pL5WdqbJTDO3l1HMl683MV+6Xp9vLlMpQKpeT++6UwmtNP08ptFc9tpz5/JPF8sxjQ20zjy1TLlPz2Eot5bBe3s6XF2fsQGbvHKKMHWdl55j+9BTPakt/KivERldlGief/gpx8umtEFcvr7R3xVHyvVZPgf6e5Lus/tChWr2sq6XfYTWiS/d+4IC7vwpgZl8BdgIKd2kZMwtDPFz0vz9wTwK+lAr8kic7gZl5pndEpemdwsxOplzVNvdzTS+vef7Zr8l0W6k8a3l4jvTrZ9ecPE8ptXOb3sGFnWGxXGa8OPO8lZ16MQwpFsvJdKpUnl5/qUONG1f20r+AT83/+Zpt/Op73rKk1zifRoT7JuBg6v4w8DOzVzKzW4FbAd761rc2oAwRyWJmxJb0iGV+nvpUVQn9qfCpbqpUnv7+6uxEidGJIucmS5w4N8kzwycpL+BHohfyvdr5NCLcs/5iav6F7n4XcBckv1BtQB0iIhfMwlBOIWef+hrx08hhYEvq/mbgUANeR0RE5tCIcH8C2GZml5pZN3ATsKcBryMiInOo+7CMuxfN7FPAd0gOhbzH3V+o9+uIiMjcGnIAtLs/ADzQiOcWEZH56XSEIiIdSOEuItKBFO4iIh1I4S4i0oHa4jJ7ZjYCvL7Eh68D3qxjOfXSjnW1Y03QnnWppoVrx7rasSaof11vc/fBrAVtEe4XwsyG5rqGYCu1Y13tWBO0Z12qaeHasa52rAmaW5eGZUREOpDCXUSkA3VCuN/V6gLm0I51tWNN0J51qaaFa8e62rEmaGJduR9zFxGRWp3QcxcRkVkU7iIiHSjX4W5m15nZD83sgJnd1sTX3WJmD5vZPjN7wcw+Hdr/1Mx+bGZPh9v1qcf8cajzh2b2yw2s7TUzey68/lBoW2NmD5rZ/jBdHdrNzO4IdT1rZlc3oJ53pbbH02Z22sw+04ptZWb3mNlRM3s+1bbobWNmu8L6+81sVwNq+j9m9lJ43W+a2arQvtXMxlLb7G9Sj3lveN8PhLqXfJmlOWpa9PtV7/+fc9T11VRNr5nZ06G9Wdtqrixo6d8VkFxCKo83ktMJvwJcBnQDzwBXNOm1NwJXh/kB4GXgCuBPgf+Ssf4Vob4e4NJQd9yg2l4D1s1q+9/AbWH+NuD2MH898G2Sq2ftAB5rwnv2E+BtrdhWwIeAq4Hnl7ptgDXAq2G6OsyvrnNN1wKFMH97qqat6fVmPc/jwM+Ger8NfKTONS3q/WrE/8+sumYt/3PgT5q8rebKgpb+Xbl7rnvu0xfidvdJoHIh7oZz98Pu/mSYPwPsI7l27Fx2Al9x9wl3/xFwgKT+ZtkJ7A7zu4EbUu33euIHwCoz29jAOq4BXnH38/0auWHbyt0fBY5nvN5its0vAw+6+3F3PwE8CFxXz5rc/bvuXgx3f0ByNbM5hbpWuPv3PUmKe1P/jrrUdB5zvV91//95vrpC7/vfAv94vudowLaaKwta+ncF+R6WyboQ9/kCtiHMbCtwFfBYaPpU+Lh1T+WjGM2t1YHvmtleSy5CDrDB3Q9D8scIrG9BXZBclSv9n6/V2woWv22aXd9/IunpVVxqZk+Z2f81sw+mah1uQk2Leb+avZ0+CBxx9/2ptqZuq1lZ0PK/qzyH+4IuxN3QAsz6gW8An3H308CdwNuBK4HDJB8Tobm1fsDdrwY+AnzSzD50nnWbVpcll1z8GPBPoakdttX5zFVHM7fZ54AicF9oOgy81d2vAj4L/IOZrWhSTYt9v5r9Pv4W1R2Hpm6rjCyYc9U5Xr/udeU53Ft6IW4z6yJ5M+9z938GcPcj7l5y9zLwd8wMJzStVnc/FKZHgW+GGo5UhlvC9Giz6yLZ2Tzp7kdCfS3fVsFit01T6gtfqP0K8Nth+IAw9HEszO8lGdN+Z6gpPXRT95qW8H417X00swLw68BXU/U2bVtlZQFt8HeV53Bv2YW4w/je3cA+d/9Cqj09Xv1rQOVb/T3ATWbWY2aXAttIvtSpd13LzWygMk/yxdzz4fUr377vAu5P1XVz+AZ/B3Cq8lGyAap6Vq3eVimL3TbfAa41s9VhaOLa0FY3ZnYd8EfAx9x9NNU+aGZxmL+MZNu8Guo6Y2Y7wt/mzal/R71qWuz71cz/n78IvOTu08MtzdpWc2UB7fB3dSHfxrb6RvLN88ske+XPNfF1f57kI9OzwNPhdj3wZeC50L4H2Jh6zOdCnT/kAr6dn6euy0iOSngGeKGyTYC1wEPA/jBdE9oN+OtQ13PA9gbVtQw4BqxMtTV9W5HsXA4DUyQ9pVuWsm1IxsEPhNvHG1DTAZLx18rf1t+EdX8jvK/PAE8Cv5p6nu0kgfsK8FeEX5/XsaZFv1/1/v+ZVVdo/xLwu7PWbda2misLWvp35e46/YCISCfK87CMiIjMQeEuItKBFO4iIh1I4S4i0oEU7iIiHUjhLiLSgRTuIiId6P8DIqBT0q3awkAAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(s);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x1ab1aed5240>]"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD4CAYAAAAXUaZHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3deXxV9Z3/8dcn92ZPWJNAyA0GJAgISkJA3HDtqMUWFEPtdB07tc60U7v8utjf/DoznZlHf+2vo63Tza2d9tHWyiYgxaotWsEimBAWWZRIELIACRAgCWS5+f7+uAcFRBLIcnLvfT8fjzxy7znnhnfug7xz8j3nfI855xARkdiS4HcAERHpfSp3EZEYpHIXEYlBKncRkRikchcRiUFBvwMAZGVluYKCAr9jiIhElfLy8gbnXPbZ1g2Ici8oKKCsrMzvGCIiUcXM3n6/dRqWERGJQSp3EZEYpHIXEYlBKncRkRikchcRiUEqdxGRGKRyFxGJQVFd7pUHjvGdZ7bR1tHpdxQRkQElqst9z6EWfvFKFat27Pc7iojIgBLV5T6rMJuczGQWllX7HUVEZECJ6nIPBhK4oziPl96s58CxE37HEREZMKK63AFKp+UT7nQ8vaHG7ygiIgNG1Jf7uJwMikYPYWF5NbofrIhIRNSXO0T23isPNLFxb6PfUUREBoSYKPfbL88lJTGBheU6sCoiAjFS7oNSErltci7PbKrlRHvY7zgiIr6LiXIHKJ0W4tiJDp7bus/vKCIivouZcp85djihoak6511EhBgq94QEY15xiFfeaqCm8bjfcUREfBUz5Q5w17QQzsFiHVgVkTgXU+WePyyNK8cOZ1F5NZ2dOuddROJXTJU7QGlJiD2HWli/+5DfUUREfBNz5X7b5FwykoM6sCoicS3myj01KcDtl+WycksdTa0dfscREfFFzJU7RIZmjreHWbm5zu8oIiK+iMlyLx49lLHZ6Sws3+t3FBERX3S73M0sYGYVZrbCez7GzNaZ2U4ze8rMkrzlyd7zSm99Qd9EP2dW7poW4rXdh6lqaO7vf15ExHfns+d+P7D9lOffAx5yzhUCh4HPeMs/Axx2zo0DHvK263fzikMkGCzS3ruIxKFulbuZhYDZwOPecwNuBBZ5m/wKmOs9nuM9x1t/k7d9vxoxKIVZ47NZXF5DWOe8i0ic6e6e+w+BrwOd3vPhQKNz7uTpKNVAnvc4D9gL4K0/4m1/GjO718zKzKysvr7+AuOfW+m0fPYdPcGayoY++foiIgNVl+VuZrcDB5xz5acuPsumrhvr3l3g3KPOuRLnXEl2dna3wp6vmyflMCQtkQVlGpoRkfjSnT33q4EPm9lu4PdEhmN+CAwxs6C3TQio9R5XA/kA3vrBgC+XiyYHA8y5fBQvbN1PY0ubHxFERHzRZbk75x5wzoWccwXA3cAq59zHgBeBu7zNPgUs8x4v957jrV/lfLy5aWlJPm3hTpZvqu16YxGRGNGT89y/AXzFzCqJjKk/4S1/AhjuLf8K8M2eReyZS0cNYmLuIE1HICJxJdj1Ju9yzr0EvOQ93gXMOMs2J4DSXsjWK8yM0mkhvrNiGzv2HWXCyEF+RxIR6XMxeYXqmeYW5ZEYMO29i0jciItyH5aexE0TRrC0oob2cGfXLxARiXJxUe4QmUzsYHMbq3Yc8DuKiEifi5tyv258NtmZyRqaEZG4EDflHgwkcGdRHi++cYD6Y61+xxER6VNxU+4QGZoJdzqWVtT4HUVEpE/FVbmPy8lkav4QFpbvxcfrqkRE+lxclTtE9t7f3N/E5uojfkcREekzcVfuH7p8FMnBBN2lSURiWtyV+6CURG6dPJLlG2s50R72O46ISJ+Iu3KHyDzvR0908Py2/X5HERHpE3FZ7lddPJy8Iaks1DzvIhKj4rLcExKMecV5rKlsoLbxuN9xRER6XVyWO8Bd0/JxDpZs0BWrIhJ74rbcRw9P44oxw1hUXq1z3kUk5sRtuQPML8ln98EWXtt92O8oIiK9Kq7L/bYpI8lIDurAqojEnLgu97SkILOn5PKHLXU0t3b4HUdEpNfEdblDZDqClrYwK7fU+R1FRKTXxH25T7toKGOz0llYrrNmRCR2xH25mxnzpoVYX3WI3Q3NfscREekVcV/uAPOKQyQYLNLeu4jECJU7MHJwCtcWZrN4QzXhTp3zLiLRr8tyN7MUM1tvZpvMbKuZ/Zu3/H/MrMrMNnofU73lZmYPm1mlmW02s+K+/iZ6Q2lJiLojJ3ilssHvKCIiPRbsxjatwI3OuSYzSwTWmNmz3rqvOecWnbH9bUCh93EF8DPv84B288QRDE5NZGF5NbPGZ/sdR0SkR7rcc3cRTd7TRO/jXGMXc4Bfe697FRhiZrk9j9q3UhIDzJk6iue27uNIS7vfcUREeqRbY+5mFjCzjcAB4AXn3Dpv1X96Qy8PmVmytywPOPWSz2pv2Zlf814zKzOzsvr6+h58C72ndFo+bR2dLN9c63cUEZEe6Va5O+fCzrmpQAiYYWaTgQeACcB0YBjwDW9zO9uXOMvXfNQ5V+KcK8nOHhjDIJPzBjFhZCaLNB2BiES58zpbxjnXCLwE3Oqcq/OGXlqBXwIzvM2qgfxTXhYComJX2My4a1qITdVHeHP/Mb/jiIhcsO6cLZNtZkO8x6nAzcCOk+PoZmbAXOB17yXLgU96Z83MBI4456Lm2v47ivIIJpgmExORqNadPfdc4EUz2wy8RmTMfQXwWzPbAmwBsoD/8LZfCewCKoHHgH/s9dR9aHhGMjdOyOHpihraw51+xxERuSBdngrpnNsMFJ1l+Y3vs70DPt/zaP4pLcnn+W37eemNej4waYTfcUREzpuuUD2L6y/JJisjSUMzIhK1VO5nkRhI4M7iEKt2HKChqdXvOCIi503l/j5Kp4Xo6HQsrajxO4qIyHlTub+PwhGZXJ4/RDfQFpGopHI/h9JpIXbsO8brNUf9jiIicl5U7ufwoctHkRxMYGG5DqyKSHRRuZ/D4NREbrl0JMs21nKiPex3HBGRblO5d6G0JMSR4+38aft+v6OIiHSbyr0LV12cxajBKSws0y34RCR6qNy7EEiI3EB79c569h054XccEZFuUbl3w13TQnQ6WLxBe+8iEh1U7t1w0fB0ZowZpnPeRSRqqNy7qXRaiKqGZsrfPux3FBGRLqncu+mDU3JJSwqwQJOJiUgUULl3U3pykNlTcvnD5jpa2jr8jiMick4q9/NQWpJPc1uYlVv2+R1FROScVO7nYXrBUAqGp2medxEZ8FTu5+HkDbTXVR1iz8EWv+OIiLwvlft5urM4hBks0mRiIjKAqdzP06ghqVxbmM3iDTV0duqcdxEZmFTuF6B0WoiaxuP89a2DfkcRETkrlfsF+MCkEQxKCWqedxEZsLosdzNLMbP1ZrbJzLaa2b95y8eY2Toz22lmT5lZkrc82Xte6a0v6Ntvof+lJAaYMzWPP76+jyPH2/2OIyLyHt3Zc28FbnTOXQ5MBW41s5nA94CHnHOFwGHgM972nwEOO+fGAQ9528Wc0pIQrR2drNhc63cUEZH36LLcXUST9zTR+3DAjcAib/mvgLne4znec7z1N5mZ9VriAWJK3mAuGZGped5FZEDq1pi7mQXMbCNwAHgBeAtodM6dvA6/GsjzHucBewG89UeA4Wf5mveaWZmZldXX1/fsu/CBmVFaEmLj3kYqDxzzO46IyGm6Ve7OubBzbioQAmYAE8+2mff5bHvp7zln0Dn3qHOuxDlXkp2d3d28A8rcojyCCaa9dxEZcM7rbBnnXCPwEjATGGJmQW9VCDg5+FwN5AN46wcDh3oj7ECTlZHMDRNyWFJRQ0e40+84IiLv6M7ZMtlmNsR7nArcDGwHXgTu8jb7FLDMe7zce463fpWL4TtclE4LUX+slb+8GX1DSyISu7qz554LvGhmm4HXgBeccyuAbwBfMbNKImPqT3jbPwEM95Z/Bfhm78ceOG6YkENWRpKGZkRkQAl2tYFzbjNQdJblu4iMv5+5/ARQ2ivpokBiIIF5xSEeXb2LJ9fv4aMzRvsdSUSk63KXrn35A+N5c/8xHliyhaYTHXx21li/I4lInNP0A70gJTHAI58oYfZlufznyu08+PwbupG2iPhKe+69JCmYwMN3F5GZHOThVZUcPdHBt2+fREJCzF2/JSJRQOXeiwIJxnfvnEJGcpDH11TR1NrB/71zCsGA/kASkf6lcu9lZsb/nj2RzJREHvrTmzS3dvDDu6eSHAz4HU1E4oh2KfuAmXH/zYV8+/ZJPPv6Pv7+V2W0tHV0/UIRkV6icu9D91wzhu/Pu4xXKhv45BPrOXpC0wOLSP9Qufex+dPz+e+PFrOpupGPPvoqB5ta/Y4kInFA5d4PZl+Wy2OfLOGt+ibmP7KWuiPH/Y4kIjFO5d5Prr8kh1/fcwX7j7Zy18/Wsruh2e9IIhLDVO79aMaYYTz52Zm0tHVQ+sha3tineeBFpG+o3PvZlNBgFnzuShIM5j+ylo17G/2OJCIxSOXug8IRmSy67yoGpybyscde5a9vNfgdSURijMrdJ/nD0lh435WMGpLKp3/5Gn/att/vSCISQ1TuPhoxKIWnPnclE0Zmct9vylm2scbvSCISI1TuPhuWnsRv//4Kpl00lC89tZHfrdvjdyQRiQEq9wEgMyWRX90zgxsuyeFbT2/hkb+85XckEYlyKvcBIiUxwM8/Po3bL8vlu8/u4AfPaU54EblwmhVyAEkKJvCju4vISA7y4xcraWrVnPAicmFU7gPMyTnhM1OCPLa6imMnOvjePM0JLyLnR+U+AJkZ3/pgZE74B194k6bWdh7+aJHmhBeRbtPu4ABlZnzxpsic8M9t3a854UXkvHRZ7maWb2Yvmtl2M9tqZvd7y//VzGrMbKP38cFTXvOAmVWa2RtmdktffgOx7p5rxvD9uyJzwn/iifUcOa454UWka93Zc+8AvuqcmwjMBD5vZpO8dQ8556Z6HysBvHV3A5cCtwI/NTONJ/TA/JJ8fvy3xWz25oRv0JzwItKFLsvdOVfnnNvgPT4GbAfyzvGSOcDvnXOtzrkqoBKY0Rth49kHp0TmhN/VEJkTvrZRc8KLyPs7rzF3MysAioB13qIvmNlmM/uFmQ31luUBe095WTVn+WVgZveaWZmZldXX15938Hh0ck74+qOtlP58LVWaE15E3ke3y93MMoDFwJecc0eBnwEXA1OBOuC/Tm56lpe/52oc59yjzrkS51xJdnb2eQePVzPGDOPJe2dyvD1M6c/XsmPfUb8jicgA1K1yN7NEIsX+W+fcEgDn3H7nXNg51wk8xrtDL9VA/ikvDwG1vRdZJucNZsHnZhJIgI888ioVew77HUlEBpjunC1jwBPAdufcg6cszz1lszuA173Hy4G7zSzZzMYAhcD63ossAONyTpkT/vF1mhNeRE7TnT33q4FPADeecdrj981si5ltBm4AvgzgnNsKLAC2AX8EPu+cC/dN/Ph2ck740FDNCS8ip7OBMDlVSUmJKysr8ztG1Drc3ManfrmerbVH+T+zJ/KR6aNJTdLZpyKxzszKnXMlZ1unK1RjwFBvTvgrxgzjX5/ZxvT//BMPLNlCxZ7DmllSJE5pzz2GOOdYX3WIBWXVrNxSx/H2MIU5GcwvyeeO4jyyMpL9jigivehce+4q9xh17EQ7KzbXsaBsLxV7GgkmGDdNzGF+ST7Xjc/WLJMiMUDlHud27j/GwvJqlmyopqGpjZzMZOZNC1E6LcTY7Ay/44nIBVK5CwDt4U5W7TjAwrK9vPhGPeFOx/SCoZSW5DN7Si7pyZoBWiSaqNzlPQ4cPcGSihoWvLaXXQ3NpCcFuP2yUcyfHqJ49FAilzeIyECmcpf35Zyj/O3DLCjby4rNdbS0hRmbnc78knzuLM4jJzPF74gi8j5U7tItza0d/GFLHQvL9vLa7sMEEowbLslhfkmIGybkkKiDsCIDispdzttb9U0sLKtm8YZq6o+1kpWRzLziPEpLQozLyfQ7noigcpce6Ah38pc363nqtb2s2nGAjk5H8eghzC/JZ/ZluWSmJPodUSRuqdylV9Qfa2VpRQ1Ple2l8kATqYkBPjgll49Mz2d6gQ7CivQ3lbv0KuccG/c2sqBsL89sqqOptYOC4WmUluQzrzjEyME6CCvSH1Tu0mda2jp4dss+FpTtZV3VIRIscseo+667mBljhvkdTySmqdylX+xuaGZh+V4WllVT39TK318zhq/+zSWkJGqGSpG+oFkhpV8UZKXztVsm8NLXrudjV4zmsdVVfPjHa3i95ojf0UTijspdel1aUpD/mDuF//m76TS2tHPHT1/hJy9W0hHu9DuaSNxQuUufuf6SHJ770iz+5tKR/L/n3mD+I2vZ3dDsdyyRuKBylz41ND2Jn/xtMT+6eyqVB5q47Uer+c2rb+smIiJ9TOUu/WLO1Dye//J1lBQM5Z+Xvs6nf/ka+4+e8DuWSMxSuUu/GTk4hV/fM4PvzLmUdVUHueWHL7Nic63fsURikspd+pWZ8ckrC1j5xWu5aHg6X/hdBV98soIjLe1+RxOJKSp38cXY7AwW33clX/nAeFZuqeOWH77M6p31fscSiRkqd/FNMJDAF28q5Ol/vJqMlCCfeGI93172Osfbwn5HE4l6XZa7meWb2Ytmtt3MtprZ/d7yYWb2gpnt9D4P9ZabmT1sZpVmttnMivv6m5DoNiU0mBX/dA33XD2GX699m9kPr6Ziz2G/Y4lEte7suXcAX3XOTQRmAp83s0nAN4E/O+cKgT97zwFuAwq9j3uBn/V6aok5KYkBvv2hSfzus1dwoj3MXT9fy4PPv0G7LnwSuSBdlrtzrs45t8F7fAzYDuQBc4BfeZv9CpjrPZ4D/NpFvAoMMbPcXk8uMemqi7P445dnMWfqKB5eVckdP32FnfuP+R1LJOqc15i7mRUARcA6YIRzrg4ivwCAHG+zPGDvKS+r9pad+bXuNbMyMyurr9eBNHnXoJREHpw/lZ9/vJjaxhPM/u81PLGmis5OXfgk0l3dLnczywAWA19yzh0916ZnWfaen0rn3KPOuRLnXEl2dnZ3Y0gcuXVyLn/80rVcOy6Lf1+xjY89vo6axuN+xxKJCt0qdzNLJFLsv3XOLfEW7z853OJ9PuAtrwbyT3l5CNCVKnJBcjJTePxTJXxv3hQ2Vzdy60Mvs7i8WtMXiHShO2fLGPAEsN059+Apq5YDn/IefwpYdsryT3pnzcwEjpwcvhG5EGbGR6aP5tn7ZzEhN5OvLtzEP/xmAwebWv2OJjJgdXmzDjO7BlgNbAFOnrrwLSLj7guA0cAeoNQ5d8j7ZfBj4FagBfg759w578Shm3VId4U7HY+v3sV/Pf8mg1IT+d68Kdw0cYTfsUR8oTsxSczZXneULz+1kR37jnH39Hz++fZJZCQH/Y4l0q90JyaJORNzB7HsC1fzD9dfzIKyvdz2o5dZX3XI71giA4bKXaJWcjDAN26dwILPXYlhfOTRtXz32e20dmj6AhGVu0S9koJhPHv/tdw9fTSP/GUXc378Cttqz3W2rkjsU7lLTEhPDvLdO6fwi0+X0NDUxpyfrOGnL1VqL17ilg6oSsw51NzGPy/dwsot+0hNDDBjzDCuLczi2sJsxo/IIHJCl0j009kyEnecc6ze2cCft+9n9c4Gdnk35s7JTOaacVlcUxj5yMlM8TmpyIU7V7nr3DGJSWbGrPHZzBofmdqipvE4a3bWs3pnAy++cYAlFTUATBiZ+U7ZXzFmOKlJAT9ji/Qa7blL3OnsdGyrO8rLO+tZs7OBst2HaQt3khRIoKRgKNcUZnHtuGwuHTWIhAQN4cjApWEZkXM43hZm/e5D7+zZ79gXmWJ4aFoiV43LYlZhFtcUZpM3JNXnpCKn07CMyDmkJgW4bnw213lDOAeOneCVygZW72xgzc4G/rA5MjXS2Kz0yF59YTYzxw4jMyXRz9gi56Q9d5FzcM6x80ATL79Zz5rKBtbtOsTx9jCBBKMof4hX9llcHhpCMKAzi6V/aVhGpJe0doTZ8HYjayoj4/Wba47gHGQmB7ny4uFc6w3hFAxP0ymX0udU7iJ95HBzG3996yBrKiPj9dWHIzcTCQ1NjRT9uGyuHjecIWlJPieVWKRyF+kHzjnePtjCau/A7Nq3DnKstYMEg2sKs5lXnMctl44kJVGnW0rvULmL+KAj3Mmm6iOs2rGfpRW11DQeJzM5yOzLcpk3LUTJRUM1dCM9onIX8Vlnp+PVqoMsLq/h2dfraGkLM3pYGncW5zGvOET+sDS/I0oUUrmLDCDNrR388fV9LN5QzdpdB3EOZowZxl3FIW6bMlKnWEq3qdxFBqiaxuM8vaGaxRtqqGpoJiUxgVsuHcm84hBXj8sioCtk5RxU7iIDnHOOir2NLC6v5plNtRw90cHIQSnMLcrjrml5jMvJ9DuiDEAqd5EocqI9zKodB1hcXs1Lb9YT7nRcHhrMncUhPnz5KIam67RKiVC5i0Sp+mOtLNtYw+INNWyvO0piwLhxQg7zikNcf0kOSUFdFRvPVO4iMWBb7VGWbKhm6cZaGppaGZaexIcvH8W84hCT8wbptMo41KNyN7NfALcDB5xzk71l/wp8Fqj3NvuWc26lt+4B4DNAGPiic+65rgKq3EW6ryPcycs761lcXsML2/bTFu5k/IgM5hWHmFuUx4hBugFJvOhpuc8CmoBfn1HuTc65H5yx7STgSWAGMAr4EzDeOXfOG1mq3EUuzJGWdp7ZXMuSDdVs2NOoq2HjTI+m/HXOvWxmBd38t+YAv3fOtQJVZlZJpOjXdvP1InIeBqcl8vGZF/HxmRexq76JJRtqWLKhmvt/v/Gdq2HvLA4xvUBXw8abnszn/gUz+yRQBnzVOXcYyANePWWbam/Ze5jZvcC9AKNHj+5BDBEBGJudwf+65RK+8oHxvLrrIIs2VLN8Uy2/f23vO1fD3lGUx0XD0/2OKv2gWwdUvT33FacMy4wAGgAH/DuQ65y7x8x+Aqx1zv3G2+4JYKVzbvG5vr6GZUT6xtmuhi0aPYQ7ivKYPSWX4RnJfkeUHuj1OzE55/af8sUfA1Z4T6uB/FM2DQG1F/JviEjPpScHmTctxLxpIWobj7N8Uy1Pb6jh28u28p1ntnHd+GzmFuVx88QRujl4jLmgcjezXOdcnff0DuB17/Fy4Hdm9iCRA6qFwPoepxSRHhs1JJX7rruY+667mO11R1laUcOyjbX8eccBMpKD3Dp5JHOn5nHlxcM17UEM6LLczexJ4Hogy8yqgX8BrjezqUSGZXYDnwNwzm01swXANqAD+HxXZ8qISP+bmDuIibmD+PqtE1hXdZClFTU8u2Ufi8qryclMZs7UUcwtymNSrs6fj1a6iElEgMi0B3/efoCnK2r4y5sHaA87xo/IYG5RHnOm5pE3JNXviHIGXaEqIuflcHMbf9hSx9KKGsrePgxEpiW+oyiPD07OZXCapiUeCFTuInLB9hxsYdnGGp7eWMOu+maSAgncOCGHuUV53DAhm+SgDsT6ReUuIj3mnGNLzRGWVtSyfFNkfptBKUFmXzaKuVNHMb1gGAk6ENuvVO4i0qs6wp288lbkQOxzW/fR0hYmb0gqc6aO4o6iPApHaP75/qByF5E+09LWwQvb9vN0RQ2rdzYQ7nRcOmoQdxTl8aHLR2kisz6kcheRflF/rJUVm2tZWlHDpuojJBhcdXEWc4vyuHXySDKSezLjiZxJ5S4i/e6t+iaWVdSwdGMtew61kJKYwAcmjWRWYRaZKUFSk4KkJQVITQyQlhQgLSlIqvdcNyHpHpW7iPjGOceGPY0srahhxeZaDre0d/maYIKRmnRK6Xu/AE4uS00MvPPL4Z3lie/+gnh3m8iyU1+bEgzEzIFflbuIDAjt4U5qDh+npS3M8fYOWtrCkccnP7eHOd52xvIzlp1oD5+yvoOW9jDnW2OpiQGyM5MZk5XO2Ox0xmalMzY7g7HZ6YwclBI1V+X2+sRhIiIXIjGQQEFW70457JyjtaPTK/yOM35RhN9dfsYvhX1HW9lV38Rruw/R0vbuLCmpiYH3lP7J55kp0XPxlspdRKKamZGSGCAlMcCw9KTzfr1zjv1e0b/V0ExVfTO7GprYUnOElVvq6Dzlr4KTe/sXZ6dHCj8rsrefPyyNxMDAOk6gcheRuGZmjBycwsjBKVw1Luu0da0dYfYcbGFXQzO76pupamhiV30zz23dz6Hmtne2CyYYo4elvbOHP8Yr/bHZ6WRnJPsyzKNyFxF5H8nBAIUjMs96UVZjS9t7Sr+qoZk1lQ20dnS+s11mcpAxZ+zpn/wlkJbUdxWschcRuQBD0pIoHp1E8eihpy3v7HTUNB6nqqGZXfVNkc8NzZTtPsyyjaffu2jkoBQ+c80YPjtrbK/nU7mLiPSihAQjf1ga+cPSmDU++7R1J9rDVDU0v1P8u+qbyRnUN7c6VLmLiPSTlMTAOzdK6WsD6/CuiIj0CpW7iEgMUrmLiMQglbuISAxSuYuIxCCVu4hIDFK5i4jEIJW7iEgMGhDzuZtZPfD2Bb48C2joxTjRTu/H6fR+vEvvxeli4f24yDmXfbYVA6Lce8LMyt5vsvp4pPfjdHo/3qX34nSx/n5oWEZEJAap3EVEYlAslPujfgcYYPR+nE7vx7v0Xpwupt+PqB9zFxGR94qFPXcRETmDyl1EJAZFdbmb2a1m9oaZVZrZN/3O4yczyzezF81su5ltNbP7/c7kNzMLmFmFma3wO4vfzGyImS0ysx3e/5Er/c7kFzP7svcz8rqZPWlmKX5n6gtRW+5mFgB+AtwGTAI+amaT/E3lqw7gq865icBM4PNx/n4A3A9s9zvEAPEj4I/OuQnA5cTp+2JmecAXgRLn3GQgANztb6q+EbXlDswAKp1zu5xzbcDvgTk+Z/KNc67OObfBe3yMyA9vnr+p/GNmIWA28LjfWfxmZoOAWcATAM65Nudco7+pfBUEUs0sCKQBtV1sH5WiudzzgL2nPK8mjsvsVGZWABQB6/xN4qsfAl8HOv0OMgCMBeqBX3rDVI+bWbrfofzgnKsBftKwZhAAAAFpSURBVADsAeqAI8655/1N1TeiudztLMvi/rxOM8sAFgNfcs4d9TuPH8zsduCAc67c7ywDRBAoBn7mnCsCmoG4PEZlZkOJ/IU/BhgFpJvZx/1N1TeiudyrgfxTnoeI0T+vusvMEokU+2+dc0v8zuOjq4EPm9luIsN1N5rZb/yN5KtqoNo5d/IvuUVEyj4e3QxUOefqnXPtwBLgKp8z9YloLvfXgEIzG2NmSUQOiiz3OZNvzMyIjKlud8496HcePznnHnDOhZxzBUT+X6xyzsXk3ll3OOf2AXvN7BJv0U3ANh8j+WkPMNPM0ryfmZuI0YPLQb8DXCjnXIeZfQF4jsgR718457b6HMtPVwOfALaY2UZv2beccyt9zCQDxz8Bv/V2hHYBf+dzHl8459aZ2SJgA5EzzCqI0WkINP2AiEgMiuZhGREReR8qdxGRGKRyFxGJQSp3EZEYpHIXEYlBKncRkRikchcRiUH/H6TYx3jFD6iEAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(s[:10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "num_top_words=8\n",
    "\n",
    "def show_topics(a):\n",
    "    top_words = lambda t: [vocab[i] for i in np.argsort(t)[:-num_top_words-1:-1]]\n",
    "    topic_words = ([top_words(t) for t in a])\n",
    "    return [' '.join(t) for t in topic_words]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['ditto critus propagandist surname galacticentric kindergarten surreal imaginative',\n",
       " 'jpeg gif file color quality image jfif format',\n",
       " 'graphics edu pub mail 128 3d ray ftp',\n",
       " 'jesus god matthew people atheists atheism does graphics',\n",
       " 'image data processing analysis software available tools display',\n",
       " 'god atheists atheism religious believe religion argument true',\n",
       " 'space nasa lunar mars probe moon missions probes',\n",
       " 'image probe surface lunar mars probes moon orbit',\n",
       " 'argument fallacy conclusion example true ad argumentum premises',\n",
       " 'space larson image theory universe physical nasa material']"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "show_topics(Vh[:10])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "We get topics that match the kinds of clusters we would expect! This is despite the fact that this is an **unsupervised algorithm** - which is to say, we never actually told the algorithm how our documents are grouped."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "We will return to SVD in **much more detail** later.  For now, the important takeaway is that we have a tool that allows us to exactly factor a matrix into orthogonal columns and orthogonal rows."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Non-negative Matrix Factorization (NMF)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Motivation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/face_pca.png\" alt=\"PCA on faces\" style=\"width: 80%\"/>\n",
    "\n",
    "(source: [NMF Tutorial](http://perso.telecom-paristech.fr/~essid/teach/NMF_tutorial_ICME-2014.pdf))\n",
    "\n",
    "A more interpretable approach:\n",
    "\n",
    "<img src=\"images/face_outputs.png\" alt=\"NMF on Faces\" style=\"width: 80%\"/>\n",
    "\n",
    "(source: [NMF Tutorial](http://perso.telecom-paristech.fr/~essid/teach/NMF_tutorial_ICME-2014.pdf))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Idea"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rather than constraining our factors to be *orthogonal*, another idea would to constrain them to be *non-negative*. NMF is a factorization of a non-negative data set $V$: $$ V = W H$$ into non-negative matrices $W,\\; H$. Often positive factors will be **more easily interpretable** (and this is the reason behind NMF's popularity). \n",
    "\n",
    "<img src=\"images/face_nmf.png\" alt=\"NMF on faces\" style=\"width: 80%\"/>\n",
    "\n",
    "(source: [NMF Tutorial](http://perso.telecom-paristech.fr/~essid/teach/NMF_tutorial_ICME-2014.pdf))\n",
    "\n",
    "Nonnegative matrix factorization (NMF) is a non-exact factorization that factors into one skinny positive matrix and one short positive matrix.  NMF is NP-hard and non-unique.  There are a number of variations on it, created by adding different constraints. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Applications of NMF"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- [Face Decompositions](http://scikit-learn.org/stable/auto_examples/decomposition/plot_faces_decomposition.html#sphx-glr-auto-examples-decomposition-plot-faces-decomposition-py)\n",
    "- [Collaborative Filtering, eg movie recommendations](http://www.quuxlabs.com/blog/2010/09/matrix-factorization-a-simple-tutorial-and-implementation-in-python/)\n",
    "- [Audio source separation](https://pdfs.semanticscholar.org/cc88/0b24791349df39c5d9b8c352911a0417df34.pdf)\n",
    "- [Chemistry](http://ieeexplore.ieee.org/document/1532909/)\n",
    "- [Bioinformatics](https://bmcbioinformatics.biomedcentral.com/articles/10.1186/s12859-015-0485-4) and [Gene Expression](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2623306/)\n",
    "- Topic Modeling (our problem!)\n",
    "\n",
    "<img src=\"images/nmf_doc.png\" alt=\"NMF on documents\" style=\"width: 80%\"/>\n",
    "\n",
    "(source: [NMF Tutorial](http://perso.telecom-paristech.fr/~essid/teach/NMF_tutorial_ICME-2014.pdf))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**More Reading**:\n",
    "\n",
    "- [The Why and How of Nonnegative Matrix Factorization](https://arxiv.org/pdf/1401.5226.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### NMF from sklearn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will use [scikit-learn's implementation of NMF](http://scikit-learn.org/stable/modules/generated/sklearn.decomposition.NMF.html):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "m,n=vectors.shape\n",
    "d=5  # num topics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "clf = decomposition.NMF(n_components=d, random_state=1)\n",
    "\n",
    "W1 = clf.fit_transform(vectors)\n",
    "H1 = clf.components_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['jpeg image gif file color images format quality',\n",
       " 'edu graphics pub mail 128 ray ftp send',\n",
       " 'space launch satellite nasa commercial satellites year market',\n",
       " 'jesus god people matthew atheists does atheism said',\n",
       " 'image data available software processing ftp edu analysis']"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "show_topics(H1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### TF-IDF"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Topic Frequency-Inverse Document Frequency](http://www.tfidf.com/) (TF-IDF) is a way to normalize term counts by taking into account how often they appear in a document, how long the document is, and how commmon/rare the term is.\n",
    "\n",
    "TF = (# occurrences of term t in document) / (# of words in documents)\n",
    "\n",
    "IDF = log(# of documents / # documents with term t in it)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "vectorizer_tfidf = TfidfVectorizer(stop_words='english')\n",
    "vectors_tfidf = vectorizer_tfidf.fit_transform(newsgroups_train.data) # (documents, vocab)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"a\\n\\nWhat about positional uncertainties in S-L 1993e?   I assume we know where\\nand what Galileo is doing within a few meters.   But without the\\nHGA,  don't we have to have some pretty good ideas, of where to look\\nbefore imaging?  If the HGA was working,  they could slew around\\nin near real time (Less speed of light delay).  But when they were\\nimaging toutatis????  didn't someone have to get lucky on a guess to\\nfind the first images?   \\n\\nAlso, I imagine S-L 1993e will be mostly a visual image.  so how will\\nthat affect the other imaging missions.  with the LGA,  there is a real\\ntight allocation of bandwidth.   It may be premature to hope for answers,\\nbut I thought i'd throw it on the floor.\",\n",
       " \"I would like to program Tseng ET4000 to nonstandard 1024x768 mode by\\nswitching to standard 1024x768 mode using BIOS and than changing some\\ntiming details (0x3D4 registers 0x00-0x1F) but I don't know how to\\nselect 36 MHz pixel clock I need. The BIOS function selects 40 MHz.\\n\\nIs there anybody who knows where to obtain technical info about this.\\nI am also interested in any other technical information about Tseng ET4000\\nand Trident 8900 and 9000 chipsets.\\n\\n\\t\\t\\tthanks very much\",\n",
       " 'In-Reply-To: <20APR199312262902@rigel.tamu.edu> lmp8913@rigel.tamu.edu (PRESTON, LISA M)',\n",
       " \"\\n\\n\\n\\nI'm not sure, but it almost sounds like they can't figure out where the \\n_nucleus_ is within the coma. If they're off by a couple hundred\\nmiles, well, you can imagine the rest...\\n\",\n",
       " \"Hello,\\n     I am looking to add voice input capability to a user interface I am\\ndeveloping on an HP730 (UNIX) workstation.  I would greatly appreciate \\ninformation anyone would care to offer about voice input systems that are \\neasily accessible from the UNIX environment. \\n\\n     The names or adresses of applicable vendors, as well as any \\nexperiences you have had with specific systems, would be very helpful.\\n\\n     Please respond via email; I will post a summary if there is \\nsufficient interest.\\n\\n\\nThanks,\\nKen\\n\\n\\nP.S.  I have found several impressive systems for IBM PC's, but I would \\nlike to avoid the hassle of purchasing and maintaining a separate PC if \\nat all possible.\\n\\n-------------------------------------------------------------------------------\\nKen Hinckley (kph2q@virginia.edu)\\nUniversity of Virginia \\nNeurosurgical Visualization Laboratory\",\n",
       " '\\nIt was a test of the first reusable tool.\\n\\n\\nPointy so they can find them or so they will stick into their pants better, and\\nbe closer to their brains?',\n",
       " '\\nSize of armies, duration, numbers of casualties both absolute and as a\\npercentage of those involved, geographical area and numbers of countries\\ntoo, are all measures of size.  In this case I\\'d say the relevant\\nstatistic would be the number of combatants (total troops) compared to\\ntotal casualties from among the total civilian population in the\\naffected geographical area.\\n\\n\\nVietnam and Korea might make good comparisons.\\n\\n\\nWestern news in general, but in particular the American \"mass media\":\\nCBS, NBC, ABC, etc.  The general tone of the news during the whole\\nwar was one of \"those poor, poor Iraqis\" along with \"look how precisely\\nthis cruise missile blew this building to bits\".\\n\\n\\nI agree.\\n\\n\\nPerhaps so.  And maybe the atomic bomb was a mistake too.  But that\\'s easy\\nto say from our \"enlightened\" viewpoint here in the 90\\'s, right?  Back\\nthen, it was *all-out* war, and Germany and Japan had to be squashed.\\nAfter all, a million or more British had already died, hundreds of \\nthousands of French, a couple hundread thousand or so Americans, and \\nmillions of Russians, not to mention a few million Jews, Poles, and \\nother people of slavic descent in German concentration camps.  All \\nthings considered, the fire-bombings and the atomic bomb were\\nessential (and therefore justified) in bringing the war to a quick\\nend to avoid even greater allied losses.\\n\\nI, for one, don\\'t regret it.\\n\\n\\nSure.  And it\\'s the people who suffer because of them.  All the more\\nreason to depose these \"entrenched political rulers operating in their\\nown selfish interests\"!  Or do you mean that this applies to the allies\\nas well??\\n\\n\\nI make no claim or effort to justify the misguided foreign policy of the\\nWest before the war.  It is evident that the West, especially America,\\nmisjudged Hussein drastically.  But once Hussein invaded Kuwait and \\nthreatened to militarily corner a significant portion of the world\\'s\\noil supply, he had to be stopped.  Sure the war could have been\\nprevented by judicious and concerted effort on the part of the West\\nbefore Hussein invaded Kuwait, but it is still *Hussein* who is\\nresponsible for his decision to invade.  And once he did so, a\\nstrong response from the West was required.\\n\\n\\nWell, it\\'s not very \"loving\" to allow a Hussein or a Hitler to gobble up\\nnearby countries and keep them.  Or to allow them to continue with mass\\nslaughter of certain peoples under their dominion.  So, I\\'d have to\\nsay yes, stopping Hussein was the most \"loving\" thing to do for the\\nmost people involved once he set his mind on military conquest.\\n\\nI mentioned it.\\n\\nIf we hadn\\'t intervened, allowing Hussein to keep Kuwait, then it would\\nhave been appeasement.  It is precisely the lessons the world learned\\nin WW2 that motivated the Western alliance to war.  Letting Hitler take\\nAustria and Czechoslavkia did not stop WW2 from happening, and letting\\nHussein keep Kuwait would not have stopped an eventual Gulf War to\\nprotect Saudi Arabia.\\n\\n\\nSure.  What was truly unfortunate was that they followed Hitler in\\nhis grandiose quest for a \"Thousand Year Reich\".  The consequences\\nstemmed from that.\\n\\nWhat should I say about them?  Anything in particular?\\n\\n\\n\\nSo?  It was the *policemen* on trial not Rodney King!!  And under American\\nlaw they deserved a jury of *their* peers!  If there had been black\\nofficers involved, I\\'m sure their would have been black jurors too.\\nThis point (of allegedly racial motivations) is really shallow.\\n\\n\\nSo?  It\\'s \"hard to imagine\"?  So when has Argument from Incredulity\\ngained acceptance from the revered author of \"Constructing a Logical\\nArgument\"?  Can we expect another revision soon??  :)  (Just kidding.)\\n\\n\\nI have to admit that I wonder this too.  But *neither* the prosecution\\nnor the defense is talking.  So one cannot conclude either way due to\\nthe silence of the principals.  \\n\\n\\nOK.  It certainly seemed to me that there was excessive force involved.\\nAnd frankly, the original \"not guilty\" verdict baffled me too.  But then\\nI learned that the prosecution in the first case did not try to convict\\non a charge of excessive force or simple assault which they probably\\nwould have won, they tried to get a conviction on a charge of aggravated\\nassault with intent to inflict serious bodily harm.  A charge, which\\nnews commentators said, was akin to attempted murder under California\\nlaw.  Based on what the prosecution was asking for, it\\'s evident that \\nthe first jury decided that the officers were \"not guilty\".  Note, \\nnot \"not guilty\" of doing wrong, but \"not guilty\" of aggravated assault \\nwith the *intent* of inflicting serious bodily harm.  The seeds of the \\nprosecutions defeat were in their own overconfidence in obtaining a \\nverdict such that they went for the most extreme charge they could.\\n\\nIf the facts as the news commentators presented them are true, then\\nI feel the \"not guilty\" verdict was a reasonable one.\\n\\n\\nThanks mathew, I like the quote.  Pretty funny actually.  (I\\'m a \\nMonty Python fan, you know.  Kind of seems in that vein.)\\n\\nOf course, oversimplifying any moral argument can make it seem\\ncontradictory.  But then, you know that already.  \\n\\nRegards,',\n",
       " \"<stuff deleted>\\n\\nYou mean like: seconds, minutes, hours, days, months, years. . .  :-)\\n\\nRemember,  the Fahrenheit temperature scale is also a centigrade scale.  Some\\nrevisionists tell the history something like this:  The coldest point in a\\nparticular Russian winter was marked on the thermometer as was the body\\ntemperature of a volunteer (turns out he was sick, but you can't win 'em all).\\nThen the space in between the marks on the thermometer was then divided into\\nhundredths.\\n\\t\\t\\t\\t\\t\\t\\t\\t:-)\\n\\nFWIW,\\n\\nDoug Page\\n\",\n",
       " \"\\nIt wasn't especially prominent, as I recall.  However, quite possibly it's\\nno longer on display; NASM, like most museums, has much more stuff than it\\ncan display at once, and does rotate the displays occasionally.\",\n",
       " \"DM> Fact or rumor....?  Madalyn Murray O'Hare an atheist who eliminated the\\nDM> use of the bible reading and prayer in public schools 15 years ago is now\\nDM> going to appear before the FCC with a petition to stop the reading of the\\nDM> Gospel on the airways of America.  And she is also campaigning to remove\\nDM> Christmas programs, songs, etc from the public schools.  If it is true\\nDM> then mail to Federal Communications Commission 1919 H Street Washington DC\\nDM> 20054 expressing your opposition to her request.  Reference Petition number\\n\\nDM> 2493.\\n\\nFalse.  This story has been going around for years.  There's not a drop of\\ntruth.  Note that I don't care for O'Hare (O'Hair?) myself, but this\\nis one thing she's not guilty of.\\n\"]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "newsgroups_train.data[10:20]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "W1 = clf.fit_transform(vectors_tfidf)\n",
    "H1 = clf.components_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['people don think just like objective say morality',\n",
       " 'graphics thanks files image file program windows know',\n",
       " 'space nasa launch shuttle orbit moon lunar earth',\n",
       " 'ico bobbe tek beauchaine bronx manhattan sank queens',\n",
       " 'god jesus bible believe christian atheism does belief']"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "show_topics(H1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x1ab1b029630>]"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD4CAYAAAD8Zh1EAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3de5gcVZ038O+PYNhHxFcwcV8fQIJsXDeuCDoiu66uNySgJuKN4GXB1eXV1zy6r7puAIkYUBAFFQgugQQRhBBEkpAMhCQEyIVJZnKbJDOZzGQySSaTZCbJZCaZ++X3/tHVk5qequ5T3VVTl/5+nidPuqtrqs/pqvrVqVPnIqoKIiKKv9PCTgAREfmDAZ2IKCEY0ImIEoIBnYgoIRjQiYgS4vSwvnjcuHE6YcKEsL6eiCiWNm7ceERVxzt9FlpAnzBhAioqKsL6eiKiWBKRvW6fscqFiCghGNCJiBKCAZ2IKCEY0ImIEoIBnYgoIRjQiYgSggGdiCghjAK6iEwWkRoRqRORGS7rfEVEqkRkh4g86W8yiahQm/e1YvuBtrCTQQHK2bFIRMYAmA3gCgCNAMpFZLGqVtnWmQjgJgAfVtVWEXlbUAkmovxc8+A6AEDDXZ8JOSUUFJMS+mUA6lS1XlV7AcwHMDVjnf8AMFtVWwFAVZv9TSYREeViEtDPBbDf9r7RWmb3LgDvEpG1IlImIpOdNiQiN4pIhYhUtLS05JdiIiJyZBLQxWFZ5rx1pwOYCOBjAK4D8IiIvGXEH6nOUdUSVS0ZP95xbBkiIsqTSUBvBHC+7f15AJoc1lmkqn2qugdADVIBnhJKVfGbZTVoONIRdlKIyGIS0MsBTBSRC0VkLIBpABZnrLMQwMcBQETGIVUFU+9nQilaGlu78MCqOnzzj+VhJ4WILDkDuqr2A5gOYBmAagALVHWHiMwSkSnWassAHBWRKgCrAPyXqh4NKtEUHX0Dg2EngYgsRuOhq2opgNKMZTNtrxXAD61/REQUAvYUJSJKCAZ0Iio6g4OK9u6+sJPhOwZ0Iio6v12xCxff9hJaO3rDToqvGNCJqOgsrTwIADjWyYBOREQRxIBORJQQDOhERAnBgE5ElBAM6ERECcGATkSUEAzoREQJwYBORJQQDOhEVLQ0c6qemGNAJ6Li4zQPWwIwoBMRJQQDOpEH2w+0QZN2n06JwYBOZOi1XS347P1r8ETZ3rCTQuSIAZ3I0N5jnQCAnYdOhJwSImcM6ERECcGATkSUEAzoREQJwYBORJQQDOhERAnBgE5ElBBGAV1EJotIjYjUicgMh89vEJEWEdli/fu2/0klIqJsTs+1goiMATAbwBUAGgGUi8hiVa3KWPVpVZ0eQBqJiMiASQn9MgB1qlqvqr0A5gOYGmyyiIjIK5OAfi6A/bb3jdayTF8UkUoR+YuInO+0IRG5UUQqRKSipaUlj+QSEZEbk4DuNNBk5uhEzwOYoKoXA1gB4DGnDanqHFUtUdWS8ePHe0spERFlZRLQGwHYS9znAWiyr6CqR1W1x3r7MIAP+JM8IiIyZRLQywFMFJELRWQsgGkAFttXEJG3295OAVDtXxKJooWD51JU5Wzloqr9IjIdwDIAYwDMU9UdIjILQIWqLgbwfRGZAqAfwDEANwSYZqJQJHSSG0qQnAEdAFS1FEBpxrKZttc3AbjJ36QREZEX7ClKREUsWRVoDOhEVHSSWn3GgE5ElBAM6ERECcGATkSUEAzoREQJwYBORJQQDOhERAnBgE5ElBAM6ERECcGATkSUEAzoREQJwYBO5JEma/gPShAGdCJDktQBQCgxGNCJiBKCAZ2IKCEY0ImIEoIBnYgoIRjQiYgSggGdiCghGNCJiBKCAZ2IilbSOokxoBNR0ZGE9hIzCugiMllEakSkTkRmZFnvSyKiIlLiXxKJiMhEzoAuImMAzAZwFYBJAK4TkUkO650F4PsA1vudSCIiys2khH4ZgDpVrVfVXgDzAUx1WO92AHcD6PYxfUREZMgkoJ8LYL/tfaO1bIiIXArgfFVd4mPaiCIqYU/SKDFMArrT04OhI1pETgPwWwA/yrkhkRtFpEJEKlpaWsxTSRQB4ngqEEWHSUBvBHC+7f15AJps788C8I8AXhGRBgCXA1js9GBUVeeoaomqlowfPz7/VBMR0QgmAb0cwEQRuVBExgKYBmBx+kNVbVPVcao6QVUnACgDMEVVKwJJMREROcoZ0FW1H8B0AMsAVANYoKo7RGSWiEwJOoFERGTmdJOVVLUUQGnGspku636s8GQREZFX7ClKRJQQDOhERAnBgE5ElBAM6ERECcGATkSUEAzoREQJwYBORJQQDOhERAnBgE5ElBAM6ERECcGATkRFK2kj2zOgE1HRSerI9gzoREQJwYBORJQQDOhEPhoYVPzznSuxeGtT7pWJfMaATuSjjt5+NLV145a/bgs7KVSEGNCJiBKCAZ2IKCEY0ImIEoIBnSgASeuwQvHAgE7ko9HusHLrwu2YMGPpKH8rRRUDOlGMPV62N+wkUIQwoBMRJQQDOpFHygpyiiijgC4ik0WkRkTqRGSGw+ffEZFtIrJFRNaIyCT/k0oULvFQQa6M+hSCnAFdRMYAmA3gKgCTAFznELCfVNX3quolAO4GcK/vKSWKAfES9Yl8ZlJCvwxAnarWq2ovgPkAptpXUNV229szwVZbRESj7nSDdc4FsN/2vhHAhzJXEpHvAfghgLEAPuG0IRG5EcCNAPCOd7zDa1qJiCgLkxK60z3kiBK4qs5W1YsA/DeAnzptSFXnqGqJqpaMHz/eW0qJiCgrk4DeCOB82/vzAGQbG3Q+gM8XkiiiuGOdI4XBJKCXA5goIheKyFgA0wAstq8gIhNtbz8DoNa/JBLFBx+JUphyBnRV7QcwHcAyANUAFqjqDhGZJSJTrNWmi8gOEdmCVD369YGlmIgSYf+xTsxdsyfUNCStdanJQ1GoaimA0oxlM22vf+Bzuogo4b4+dz32Hu3ENZeei3POHDuq353U1qXsKUoUgKSV/IJworsfADth+YkBnchHSS35UTwwoBMRJQQDOlEENbZ2oubQibCTMSpY4eIfo4eiRDS6/uVXqwAADXd9JuSUBIe1U/5jCZ3II5NneMpyJ4WAAZ3IkL1EuXlfK0ruWI62zr6MdVjupPAwoBPl4b6VtThyshcb9x0LOymxx1aL/mFAJ6JQsImn/xjQiYgSggGdKADFWo3Q0dOPjp7+sJNRtNhskchHxV6N8J6fLQPgrbklWwT5hyV0IgpJkV/9AsCATjmtqT2Cy3+5El29A2EnhYiyYECnnH5ZWo1D7d3Y3XIy7KQQURYM6EQBYK2wB/yxfMOATkShKPYHyEFgQCciSggGdCIij5ZUNuHjv3kFg4PRqi9iO3SKpb6BQQDAG8aMfpnEpN00axPMhRkS820D/1/PVKKrbwDd/QN449johFGW0CmWPviLFbj4tpdG9Tu91PlGq9wWTWFe9NKjYvb1K/qtwkESMKBTLB3v7ENXX/jt4ou1i39SfO6BNfj0b18LOxm+YUAnyoOwiUZi1B/pCDsJvmFAJxoFJ3v68cjqeiiL9CMk6SdZX38Uc9fsCe37jQK6iEwWkRoRqRORGQ6f/1BEqkSkUkRWisgF/ieVKEYygtTtz1fhjqXVWFXTHE56AnLFva/iW38sz+tvk3iTc+2cMty+pCq0788Z0EVkDIDZAK4CMAnAdSIyKWO1zQBKVPViAH8BcLffCSWKs7au1FR1PX3JeQAHALXNJ7FyZ7IuUnFmUkK/DECdqtarai+A+QCm2ldQ1VWq2mm9LQNwnr/JJEqGBNUuGKtrPolHVteHnYyiYBLQzwWw3/a+0Vrm5lsAXnD6QERuFJEKEaloaWkxTyVRzCWxesHUNQ+uxR1Lq12bB3I8dP+YBHSnQ9FxD4jI1wGUAPi10+eqOkdVS1S1ZPz48eapJIqJJD3g80t6BqPMlkHC7le+M+ni1AjgfNv78wA0Za4kIp8CcAuAf1XVHn+SRxQv88v3AQB63UqjRRzwUy18GMSDZFJCLwcwUUQuFJGxAKYBWGxfQUQuBfAQgCmqyickVLRWVB92XF7MVS5ubfZZ1eK/nAFdVfsBTAewDEA1gAWqukNEZonIFGu1XwN4E4BnRGSLiCx22RxRUSrmknncdPcNoDsCvZDzYTSqjKqWAijNWDbT9vpTPqeLiBIm85oW1Tr0d9/6Is5+4xuweeanw06KZ+wpSmSokFJ2UVe5hJ2APLR29hmtF7U7LwZ0ykvT8a6wkxBJUS11kr+ieoFmQM9DV+8AVro8/CoW184pAwD0D0SsiBIgP07iKD4IPNjWhaMng2+Y5laajVopN84Y0PNw66Lt+NZjFahqag87KbFy/8paLNpyIOxkhCLKJfd/uvNlfOCOFYFt3+1CGNVSbpxFZ6qNGNl7NDXc5kmrwwSZuWf5LgDA1EuydTSON3uQenVXC/7h7WfhbWf9TXgJotDtP9aJgUHFhHFnBv5dLKEXgEOhUjbXz9uAr/zP68OWFfMhE8XqpqCt2tmMj9y9Ch/7zSuj8n0M6HmI8u0z+aerdwDPbmws6MLdcLQz90oJ53S+/OuvV+FgWzeAZA9YNtpD6TKgE7mYtaQKP3pmK8rqj4WdlESwXxf3hnyhC6P+vqqpHYu3jhg1xVcM6AVwK1kcOdmDb8xdj9aO3lFND/mruT1Vguzw41lJMd/UFXPeba6+bzW+/9TmQL+DAT0fOQ7QuWv2YHXtETy5Yd/opIdolKgq1u0+UvTPj6KafQb0AkR1p5K//NzN6W2pKsrqj8YuMD61YT+++vB6PF950LdtBvUbHD3Zg/3Hgq3asVfdRGH8Fwb0POS6gxzNc3Td7iP43p83hRYYirHlQj4yj5mFWw5g2pwyPLspXu3y9x5LNdk90GreUzisGpfL71yJj9y9KpBtdzkE75v/ui2Q7/KCAb0AuYLZaDx4uWFeOZZuO+g6/jYVzstudBsqNlP6oeC+gEuQxawvoF7Mq2udZ1vbtK81kO/zggE9D+zhRr6JWZVLIZKS1ZpDJ8JOgisG9JioPtiOCTOWYsv+446fJ+VkKRZR78ugqvg/j1fg1V3OpVEvVW25CkA8dv3DgG7oWEcvHlldP7yu2m2wIcODfVVNMybMWIq65pM51315Z2oiqGU7Dg3/INpxIZGyBaCk7I5BBZbtOIxvPrph2HL7hcj0uU2SA7Y9b6bVbUHiWC6GfrRgC1bVtKBkwjnGpatc6y21Wgps2teKv3vbm4y2meSTI+qc9qfX/ZEZBOO8O4PuJEPesYRuqL071bmk3/bw0fVk9HqWGqzvOmKdx6+KClXFTX/dFokHSbk47R63391tV46Y8T7EHXf/ylpfttNywmzI3QgUXIsGA3oe/DpA89mMW3VO3EruXX0DeGrDPnzt4fVhJyVUYey39KiXhZi/Yb/nv0lKE9coVK24YUAPydq6I3hmYyMAswPdrfpmNI6t/sHUXUmjh7bHppJykqe57Y7M5dsOtAWdlECkjzcvzS39egD84vZDON4Z3eE0ohDmGdALkKt0lS3Yzl2zx9+0BBgYdx1OPbS95Tn/Ok5EvZWHn5yC0PKq1IxXSbugBaW5vRvfeWIjvvvEprCTEukjlwE9ACanqP2g8HTbnbFu3ANj3KqKsukfGMTxrpGTCwfVwSVuCtnXPf2pu8QodMSKcI0LA3qQsu13+0FhdAGI8EGUj3R+khTqfrpwO7Y69BNI2r7zKlf+P3L3KrR3j7wQ+qmjpx+dvf04cLwLbQ4XXV9EYD8bBXQRmSwiNSJSJyIzHD7/qIhsEpF+EfmS/8mMDoX5CaoAFpTvx4fvetnh0/z2vlsAjFNJt+m4/3XxUfB8Hs344rTfgOBi1uZ9zh3mhr63wC9+z8+W4ZKfL8eH73oZn7r3VQwM5v/DRyBuu8oZ0EVkDIDZAK4CMAnAdSIyKWO1fQBuAPCk3wmMglnPV2Hj3uzN63Y0teFz969BZ+/wsbN/8mwlDjgEsGEldJNmi27L8zi6PnHPK/j4KE2J5aTPPu5MzAJaPkyq17Y1tuHxsr2jkh4389bswa7DwXVrz7ar0+3zH3i5FhNmLM25Xj7S4x21nOjBYNyupIZMSuiXAahT1XpV7QUwH8BU+wqq2qCqlQASOULUvLXODzDtD7TuLN2JbQfahgX+bLH2NNuHNz+3bcTck276BgaxtPKgaweVrz5chhsyevdlqm/pwJ4jHUbfZ+dX1YGqvcrF+4nV1hns7bkXMxdtN1rP7bdL5/5zD6zBrQvNthWUWUuq8Nn71mRdJ58waHLYpLf7m5ecm1Smmwo2tXUPm5y9f2AQC8r3Y9Aqcd++pApX/va1PFLpki5VvFLTbHQhiULJ3SSgnwvA3ui00VrmmYjcKCIVIlLR0uI8RkQcOD2ITF/xVd1LEdUH2/H52WvR2ds/YhsbGrJPc5YOCI+ubcD3ntyEF7cfstIy3LrdR/FKTTC/rZ+Fmnwf5u5uOYn3zXrJv4Rk4RaE27v7sNIaiqHJmhczKXoHBtHVO4CLbi4NOynD2HfFt/5YPvR63to9+MmzlXi6IhWi5q7Zgxof7zKe23wANzxajqds7e7j3g7dKfV5ndqqOkdVS1S1ZPz48flsIlLSAS41i8vR1Gvb55n7/RdLq7Fl/3Fs3NtacGn3aIDT23X1DmDDHrN5NA+3m/UWtCurP4rNVg9RrxeJPS3D7yyaT3RjwoylmG/NDvW1R8pw8W3LPKcpl1U1zeiz2uMv23HY09/aA0Acmim2ZmnrXchhm7WU6+Fnsd8Fp8+D4wHdtaWf9xw4nmpdM3fNHrzmOmBZ+EzGcmkEcL7t/XkAinoQh8xgnM/zFa8BvZDmiTsPtWPcm87AuDedYbT+jL9WYtGWJqz+ycdx/jlvzPt73bd/qj27InWCnnnGGLz7f7/Z87YajqROtGc3NeKSd7wFa+uOOq63pLIJrZ19WFt7BB951zh87UMXGH/Hut1H8OjaBow/y+z3yxTd8pwzvwOTSYlWodieT2crW2L7PcwJkG8p+/YlVZ7Wr8+jarMQJiX0cgATReRCERkLYBqAxcEmKx6cDnyTujbVwtuPK1JVOB29Azm/d/LvVuOT97xqvO2dB1O3rB0ZD3iDuNMcGFR88Q/rMPl3q/P6e3u+s21j+pObcevC7XhxxyHc8py3uuojJ1OlQLexS1bXtuDyX65Ed3/ugOJ1v3/3iY2e1n92Y2PB4+PYf9Mgpt9z89n7R9bfP7K6HvuPdRode50BTgHndnoNuyMP7NvN5QzoqtoPYDqAZQCqASxQ1R0iMktEpgCAiHxQRBoBfBnAQyKyI8hER82wVgxw3/n2g9JzCT1j/YPHu3DV782DYGBtb0dZ5u/wmjV7TJAdrHJt+RdLq3GovduoKVxmlUuu6/8L2w9lXyHDj57Zii88uM7T3wTN6KGoZr5XNLd3446l1bj+0Q2hdaCLcn25E6N26KpaqqrvUtWLVPUX1rKZqrrYel2uquep6pmq+lZVfU+QiY669Vb9c7Y7wEIPlAdf2e35b77/1GZP68ehZVeDNZVbkOd7rl1lsi8LTd6X/rAON3mYs9LeEsQrt/3+Sk0zmg1HWCz0O1VPVWV29PTn7IgXdNyNwakAgD1Fc8pWlZH+bNgaemrgpSMnnQ9+hf/xx+SAMx2/OiqFkk37WrGqpnnYshFpszLuVh2yamdz1nbNfsj1c2Xrc2DykPTp8n2o2NuKpzbsQ1tXn1Fd8dJK/x9z3fBoOf5iDSiXD78KCAODWvA0cG7nZiGiUJpnQM/h/z29ZcSybDvOtBXD6/UjH9719A+M6JhUzL7w4Dp889HyrOukf2+3dvULtxxwXD44qMadVLwEbOe/F08ne2bp+r+fPVUyf9/PXxr2UDntRLdZoA+FQdYz90Tm+8xNXPm7VFvzrY2pHqap51LmgmoVEzYG9BwWbnEv6eQKB24jKl4/b4NjifKq36/GpJnOTe5yNSP0o/Rz7/Jd+IdbXyx8Q6MoW7437j2GRS777503lxpXYeQKxl4LZrmqQx54uS7r5ws3j7xIvfe2l/CjZ7Z6S4iLKFS1mV5sy+pT50XQBSHX52KBfqt3DOh5yLYTs843mePMr29xb+L0UpW3ts/5uG9lLbpsLQWicGJnynw4lq0L97UPlWXd1vzyU51FTvb0Y03tEZfvzO60HPvVftemCtz/cq39wxHyLWm7Xby8CqytfLZm6DnHovY3KaYiUIviCQN6QpQbdgRyU8gYGWHKVpfqJUc/fHoLvj53fV4Dh5mc8+k7rFd3taCvP56/db5Mfp/HXm8Y9t7rLxSFsVmiEPsZ0D0adtyEfwwN+fafKgr6+0Ptp7qw7z3qNuZ0FA7Z4Rpc0+rtIlXbnJrEo8upLXOhlejA0ABtr9Q0DxsqNp9DqH9Q8aFfrsDLOwu7a8s1EBaQPevHDHsrm+Rxff3wAknmrov7uP+jhQE9D4fbh4/fMawjhsvROziorl2Go8CebseghtQYJhfdXIrVtaOfjw/+YgU+cPtyT39jEkhMglKuYJIr1Nh/2/bu/oJaiqQdbu/B7UuqjdataDiGuuaRdzJuozuaXgezjcy432EiinRVziGH8W8yS9j2ap/D7T042pG9VUoECuiRYNL1nzLstG7zm9pG3p47LQOAl3c2Oy6PCpO6wl6rJ2Suh3ZBSD9Ermw06x5+rKPX6CRv7ezFOWeOLSRpBdWzFlLVZfq3XzIcydP797t/1m0VCtq6+oZd8DbsOYavPGSWnupD7UOvZzyb/QF20PHcaN7fCNxEsIRegMFBxa0Ltw81nQKAmYucO8n2GHQLj4uge51e+9DrWOTS3PCVXWYXRtNhbdMPNNPBMZ9zcluOi0xQwabQ7brdefiRXgWwsvow3vfzl9DenWqBopoarsJJZidbVWBp5cGh91scZoLKXL8QX33Y+QF6rruzmYt2BN7PwQsG9AJ09g7g8bK9uG7O+rCTUjCnA9etVLIz40Gk3zOxr99zDD+YP7L9P5B7Zps00wvoaRnZnvLAWgDAoi0HsKI6dfHI9cCtv4DZbx5evQcNGW3oTbdWaBBzHaPdh/qLQdWhHtP5bHt3y8kR+yYbhRbUsSc9WqpXz24qvPrMTwzoHjWfGFn/F4chUZ0ssfUmdOtpaeKSWcvR0x/cwEj5MJ1i7MXthzD9yVMzyafbiNsvKM85tPv203/k+UB7NCdMNgnEvbaLqFtHH9Nr369erMnZHNTuoVfr8Y8/83fY5Akzlg4N8xyXU5wB3aPpT54aD2Vo1p0I7uxHVtc7LrfP9mPPy/Iqb4NAZerNKBFv3tea33CoPjF9ZnHnCzuxxHZrH4RcJfx0C5u00aqKdfuefGazAoYPLaEKVGVUryi83H0UVuLO3Fa+0v0/ntt8wNNMWQOD6lptGCQG9AKkqylM2sDme2wODCp+/rz3wSt/v6LWcbnrbD8FnjyZJa9rHlznOBxqMXpsXUPYSfDktytOTQOX3q1Oh3jmoswOUaszOmp19w0YB9cDx7tQ69PMQ7caPk9pbneffar5RA/+82n3we0y8/XVh8tcqw2DxIDugwKqUHNKT67glWmSmo534cXtziVUTwWbLOt29PTjDo8TA4w2e5XTcp975To14YuyfAu09vPAqRrylufMR4usb+lARY6J2QcNT7wnyvYZrfflHK1vss3OlZkUp+cHo4HNFgsQdN354q1Nnoe8tdu8r3Vo7lE3X3hwHQ61d+MHn5yY9/cAqbuUhZsPoK75JH585d8P++ynC7cXVA896/ngLwbpiUKA/Ou03RQylG0hNu5tdW1VArgPReEUJ02OdPudqtNFofrgCfzzReMMtmTmdyud70JT3+/93Nx7tDOvnsJA6k46ClWvRRfQN+w5hpILzsZpXh6hh+TJ9c4dP0yc7OnHNQYTHaR7iBbasuFSW6efzIBuGswPt3fjb9/8NyOWz1vrPMhZXKRby4y2L/4hv4kuMjvK9fYPnno46KK3f9DoGPKzi/59WQJ6vvKp3gRS+YrC8ANFVeWyurYFX3nodcxxeWDolZfuyO7d6Z3dsaRqaCQ5Uye6828ffp9DZ6GKhmO42sOsSE68XCg+9MuVBX1XUhzIs5Rol2t8rwUV+42/58fPbMW1c0a207bv2+vnbRjWsshptx9q78aCiv0jPwjArsMnc6/kIFvLmswpGe1Uo9E4oqgC+kGry3Fdc347O5OXK/KvXtxpvO5vltXgEZehd7P583qzukJTtz1fNaKlglcX3lTqU2qKh9dp55zcnKO++id/qXT9LLOfgdvEKKtqTg0B8Xr90Zx16ACwO8uIon5Kj5fuVbaAnq1QNqDRaLwcu4B+vLMXK/J8aJXeWX7dGt35gnmQ9uKBVfl1rb8roPSMpikPFHfLmEvdWiHFQIftWUFmC5e4KKQ1mmnfhyDFLqB/94lN+PafKvKaQuq0CLcbpxTTsVqSqjXGM+ncs/xUc8dfL6sJMSX589KZyU5VjTt6mbbOyUfsAvreo6lbtu0H2jx3gLCX0Hc0tWHCjKVY7zAVHJAaO+KZUarvS5rKRrPu+URRM5Bnac9L6fydN5cGVpqPXSuXdOuUG6y5Jhvu+ozR323df3yo9+CgAmvrUreEK6oP40PvfOuI9T8/e60fyS1K6fFQiOJmaZ69hk3buqf1DQxizGlj8vqubGJXQh+Tpblh/8AgHi/b6ziF19TZa4ce7gwO6tADHKe2uE5jRxMRubH3rjUR1HDasQvomXVcJ7r7ULrtIJpPdOM7T2zErQu3D03OrKrYc6RjxO1Ne3ffUD36nNfqh7okp+u2PnVvfk/IiYhMFDIYXjZGVS4iMhnA7wGMAfCIqt6V8fkZAP4E4AMAjgK4VlUb/E1qSmYB/b23jWwVsGX/cSze2oSXdhzCksqDuPQdbxn2+eraI6hqOtUc7922me5v+9wkfxNMRJShkCGXs5FcHT9EZAyAXQCuANAIoBzAdapaZVvn/wK4WFW/IyLTAFyjqtdm225JSYlWVHjvYn3Fva+OGJ2OiChOzjlzLDbdekVefysiG1W1xOkzkyqXywDUqWq9qvYCmA9gasY6UwE8ZmmFB3AAAAVLSURBVL3+C4BPil9jX2bIVodORBQHphNse2US0M8FYG+/12gtc1xHVfsBtAEY0XRERG4UkQoRqWhpyW+i4a9dfkFef0dEFBX3fPl9gWzXpA7dqUicWU9jsg5UdQ6AOUCqysXgu0f4xuUX4BsM6kREI5iU0BsBnG97fx6AzMEdhtYRkdMB/C8A4QwITERUpEwCejmAiSJyoYiMBTANwOKMdRYDuN56/SUAL6sfM80SEZGxnFUuqtovItMBLEOq2eI8Vd0hIrMAVKjqYgBzATwuInVIlcynBZloIiIayagduqqWAijNWDbT9robwJf9TRoREXkRu56iRETkjAGdiCghGNCJiBKCAZ2IKCFyjuUS2BeLtADId1r7cQDiOceVN8WQT+YxGYohj0A08nmBqo53+iC0gF4IEalwG5wmSYohn8xjMhRDHoHo55NVLkRECcGATkSUEHEN6HPCTsAoKYZ8Mo/JUAx5BCKez1jWoRMR0UhxLaETEVEGBnQiooSIXUAXkckiUiMidSIyI+z0eCUiDSKyTUS2iEiFtewcEVkuIrXW/2dby0VE7rPyWiki77dt53pr/VoRud7t+0aDiMwTkWYR2W5b5lueROQD1m9WZ/3tqM9D6JLH20TkgLUvt4jI1bbPbrLSWyMiV9qWOx6/1vDU6628P20NVT2qROR8EVklItUiskNEfmAtT9q+dMtn/PenqsbmH1LD9+4G8E4AYwFsBTAp7HR5zEMDgHEZy+4GMMN6PQPAr6zXVwN4AakZoS4HsN5afg6Aeuv/s63XZ4eYp48CeD+A7UHkCcAGAP9k/c0LAK6KSB5vA/Bjh3UnWcfmGQAutI7ZMdmOXwALAEyzXv8PgO+GkMe3A3i/9fospCaHn5TAfemWz9jvz7iV0E0mrI4j+yTbjwH4vG35nzSlDMBbROTtAK4EsFxVj6lqK4DlACaPdqLTVPU1jJyhypc8WZ+9WVVf19TZ8SfbtkaNSx7dTAUwX1V7VHUPgDqkjl3H49cqpX4CqQnWgeG/16hR1YOqusl6fQJANVLzBSdtX7rl001s9mfcArrJhNVRpwBeEpGNInKjtexvVfUgkDrYALzNWu6W3zj8Dn7l6VzrdebyqJhuVTfMS1dFwHse3wrguKYmWLcvD42ITABwKYD1SPC+zMgnEPP9GbeAbjQZdcR9WFXfD+AqAN8TkY9mWdctv3H+HbzmKcp5/QOAiwBcAuAggHus5bHOo4i8CcCzAP5TVduzreqwLM75jP3+jFtAN5mwOtJUtcn6vxnAc0jdth22bkdh/d9sre6W3zj8Dn7lqdF6nbk8dKp6WFUHVHUQwMNI7UvAex6PIFVdcXrG8lEnIm9AKsj9WVX/ai1O3L50ymcS9mfcArrJhNWRJSJnishZ6dcAPg1gO4ZPsn09gEXW68UA/s1qTXA5gDbrlncZgE+LyNnWbeGnrWVR4kuerM9OiMjlVt3kv9m2Fap0kLNcg9S+BFJ5nCYiZ4jIhQAmIvUw0PH4teqTVyE1wTow/PcaNdbvOxdAtarea/soUfvSLZ+J2J+j8eTVz39IPVnfhdTT5VvCTo/HtL8TqSfhWwHsSKcfqTq3lQBqrf/PsZYLgNlWXrcBKLFt69+RejhTB+CbIefrKaRuUfuQKrV8y888AShB6uTaDeABWD2cI5DHx608VCJ10r/dtv4tVnprYGvJ4Xb8WsfGBivvzwA4I4Q8/gtSVQOVALZY/65O4L50y2fs9ye7/hMRJUTcqlyIiMgFAzoRUUIwoBMRJQQDOhFRQjCgExElBAM6EVFCMKATESXE/wcC1VAfLOGkQAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(clf.components_[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "43.71292605795277"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf.reconstruction_err_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### NMF in summary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Benefits: Fast and easy to use!\n",
    "\n",
    "Downsides: took years of research and expertise to create"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notes:\n",
    "- For NMF, matrix needs to be at least as tall as it is wide, or we get an error with fit_transform\n",
    "- Can use df_min in CountVectorizer to only look at words that were in at least k of the split texts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Truncated SVD"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We saved a lot of time when we calculated NMF by only calculating the subset of columns we were interested in. Is there a way to get this benefit with SVD? Yes there is! It's called truncated SVD.  We are just interested in the vectors corresponding to the **largest** singular values."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/svd_fb.png\" alt=\"\" style=\"width: 80%\"/>\n",
    "\n",
    "(source: [Facebook Research: Fast Randomized SVD](https://research.fb.com/fast-randomized-svd/))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Shortcomings of classical algorithms for decomposition:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Matrices are \"stupendously big\"\n",
    "- Data are often **missing or inaccurate**.  Why spend extra computational resources when imprecision of input limits precision of the output?\n",
    "- **Data transfer** now plays a major role in time of algorithms.  Techniques the require fewer passes over the data may be substantially faster, even if they require more flops (flops = floating point operations).\n",
    "- Important to take advantage of **GPUs**.\n",
    "\n",
    "(source: [Halko](https://arxiv.org/abs/0909.4061))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Advantages of randomized algorithms:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- inherently stable\n",
    "- performance guarantees do not depend on subtle spectral properties\n",
    "- needed matrix-vector products can be done in parallel\n",
    "\n",
    "(source: [Halko](https://arxiv.org/abs/0909.4061))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Timing comparison"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 9.87 s\n"
     ]
    }
   ],
   "source": [
    "%time u, s, v = np.linalg.svd(vectors, full_matrices=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import decomposition\n",
    "import fbpca"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 4.5 s\n"
     ]
    }
   ],
   "source": [
    "%time u, s, v = decomposition.randomized_svd(vectors, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Randomized SVD from Facebook's library fbpca:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 1.68 s\n"
     ]
    }
   ],
   "source": [
    "%time u, s, v = fbpca.pca(vectors, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For more on randomized SVD, check out my [PyBay 2017 talk](https://www.youtube.com/watch?v=7i6kBz1kZ-A&list=PLtmWHNX-gukLQlMvtRJ19s7-8MrnRV6h6&index=7).\n",
    "\n",
    "For significantly more on randomized SVD, check out the [Computational Linear Algebra course](https://github.com/fastai/numerical-linear-algebra)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## End"
   ]
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}