Matrix_Factorization_using_Gradient_Descent.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Matrix Factorization using Gradient Descent\n",
    "\n",
    "We implement a matrix factorization method, specifically [Non-Negative Matrix Factorization (NMF)](https://en.wikipedia.org/wiki/Non-negative_matrix_factorization), using gradient descent. We use this to solve topic modelling.\n",
    "\n",
    "(Please refer to the tutorial on basics of topic modeling, LSI with SVD (Tutorial Set 4), for details on LSI)\n",
    "\n",
    "## Applying NMF to solve Topic Modeling\n",
    "Given a term document matrix $V$, NMF factorizes it into two matrix $W$ and $H$ with the property that all three documents have no negative elements.\n",
    "<img src=\"content/NMF.png\" alt=\"Non-negative matrix factorization\" style=\"width: 80%\">\n",
    "\n",
    "In Non-negative Matrix Factorization, a document-term matrix is approximately factorized into term-feature and feature-document matrices.\n",
    "\n",
    "$V = WH$ Matrix multiplication can be implemented as computing the column vectors of $V$ as linear combinations of the basis vectors (column vectors) in $W$ (or the topics discovered from the documents) using coefficients supplied by columns of $H$ (or the membership weights for the topics in each document). That is, each column of V can be computed as follows:\n",
    "$$ v_i = W h_i$$\n",
    "\n",
    "In what follows, we will first see an example of applying NMF by using [SKLearn NMF API](https://scikit-learn.org/stable/modules/generated/sklearn.decomposition.NMF.html) for the task of topic modeling. Later you will be required to implement NMF using gradient descent.\n",
    "\n",
    "### Scikit-Learn implementation of NMF for topic modeling\n",
    "Given a set of multivariate  $n$-dimensional data vectors, they are put into an  $n\\times m$  matrix  $V$  as its columns, where  $m$  is the number of examples in the data set. This matrix  $V$  is approximately factorized into an  $n \\times t$  matrix  $W$  and an  $t \\times m$  matrix  $H$ , where  $t$  is generally less than  $n$  or  $m$ . Hence, this results in a compression of the original data matrix.\n",
    "\n",
    "In terms of topic modeling, the input document-term matrix  $V$  is factorized into a  $n \\times t$  document-topic matrix and a  $t \\times m$  topic-term matrix, where  $t$  is the number of topics produced. Similar to tutorial 4, we will be using 20 NewsFetch dataset for the task."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn.datasets import fetch_20newsgroups\n",
    "from sklearn.feature_extraction.text import TfidfVectorizer\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Setup data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "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)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Compute document features"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2034, 26576)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vectorizer_tfidf = TfidfVectorizer(stop_words='english')\n",
    "vectors_tfidf = vectorizer_tfidf.fit_transform(newsgroups_train.data).todense() # (documents, vocab)\n",
    "vectors_tfidf.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Compute NMF using Scikit Learn library\n",
    "\n",
    "We will also write a function to display top 8 words for each topic."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_top_words=8\n",
    "vocab = np.array(vectorizer_tfidf.get_feature_names())\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": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import decomposition\n",
    "\n",
    "d = 5 # num topics\n",
    "clf = decomposition.NMF(n_components=d, random_state=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "W1 = clf.fit_transform(vectors_tfidf)\n",
    "H1 = clf.components_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "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": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "show_topics(H1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Excercise"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## NMF using SGD\n",
    "\n",
    "In stochastic gradient descent (SGD), we evaluate our loss function on just a sample of our data (sometimes called a mini-batch). We would get different loss values on different samples of the data, so this is why it is stochastic. It turns out that this is still an effective way to optimize, and it's much more efficient!\n",
    "\n",
    "### Applying SGD to NMF\n",
    "\n",
    "Goal: Decompose $V\\;(m \\times n)$ into\n",
    "$$ V \\approx HW$$\n",
    "where $W\\;(m \\times d)$ and $H\\;(d \\times n)$, $W,\\;H\\; \\geq \\;0$, and we've minimized the Frobenius norm of $V-WH$. The objective function can therefore be written as the following:\n",
    "$$\n",
    "\\min_{H \\geq 0, W \\geq 0} F(H,W) = \\frac{1}{2} ||V - HW||^{2} + \\frac{\\lambda}{2} \\left( ||H||^2 + ||W||^2 \\right)\n",
    "$$\n",
    "\n",
    "### Implementation of NMF using SGD (Excercise)\n",
    "__Approach:__ Given the objective function above, pick random positive $W$ & $H$, and then use SGD to optimize. \n",
    "\n",
    "(Note that the objective function is non-convex in nature, and is convex only if we consider $H$ and $W$ separately. You can directly write the gradient descent rule for the objective function presented above)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Helper functions to calculate the loss, gradients and update the weights.\n",
    "\n",
    "def constraint(x):\n",
    "    return np.where(x >= tol, 0, np.min(x - tol, 0))\n",
    "#Returns an array of values that satisfy the condition.()\n",
    "\n",
    "def gradient(v,w,h):\n",
    "    j=w@h -v\n",
    "    dw=j@h.T + lam * w + l * constraint(w)\n",
    "    dh=w.T@j + lam * h + l * constraint(h)\n",
    "    return dw,dh\n",
    "    #Returns gradients.\n",
    "\n",
    "def descent(v,w,h):\n",
    "    dw,dh=gradient(v,w,h)\n",
    "    w = w - lr * dw\n",
    "    h = h - lr * dh\n",
    "    return np.array(w),np.array(h)\n",
    "    #Performs the update on the weights\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "44.42285365430293\n",
      "44.37458633127484\n",
      "44.34792986067728\n",
      "44.31580670914116\n",
      "44.27701471483896\n"
     ]
    }
   ],
   "source": [
    "m, n = vectors_tfidf.shape\n",
    "\n",
    "h = abs(np.random.normal(scale=0.01,size=(d,n)))\n",
    "w = abs(np.random.normal(scale=0.01,size=(m,d)))\n",
    "\n",
    "lam = 1\n",
    "lr = 0.01\n",
    "l = 1e3\n",
    "tol = 1e-3\n",
    "#Parameters\n",
    "\n",
    "for i in range(50):\n",
    "    w,h = descent(vectors_tfidf,w,h)\n",
    "    if i%10==0:\n",
    "        print(np.linalg.norm(vectors_tfidf-w@h))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['space god people just don like think know',\n",
       " 'space god people just don think know like',\n",
       " 'god people don space just like does think',\n",
       " 'people space god think don know just like',\n",
       " 'god don space people just think like know']"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "show_topics(h)\n",
    "#Prints words that fall under a \"topic\""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}