CS134 (Fall 2016) Programming Assignment 2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# Maximum Entropy Model\n",
    "\n",
    "**Due October 21, 2015**\n",
    "\n",
    "## Overview\n",
    "\n",
    "Maximum Entropy classifier is the most used classifier in natural language processing. It's a strong statement but it's true. It's also used very widely in other fields. The model has many strong points. It handles the case where you have much more features than the number of data points. It also handles the correlation between features really well. In addition, the time and space complexity for the model is not too taxing. All of these reasons make MaxEnt model a very versatile classifier for most NLP tasks. \n",
    "\n",
    "It is hard to go through an NLP class these days and not build a classifier for sentiment analysis. So we are going to use MaxEnt model for sentiment analysis.\n",
    "\n",
    "## Getting ready\n",
    "\n",
    "\n",
    "Download the starter code along with the datasets using the link on latte. If you don’t have the overall idea of how to implement MaxEnt, look at the [slides]() from the office hours (will upload later on latte). There’s quite a bit of disconnect between theory and practice for MaxEnt, so we highly recommend reviewing the slides before starting implementing.\n",
    "\n",
    "## Datasets\n",
    "\n",
    "- **Sentiment analysis on Yelp dataset.** We processed the data from Yelp dataset challenge and put it in the json format. Review class provided in corpus.py reads in the input for you. Each restaurant review is tagged with ‘negative’ (1-2 stars), ‘neutral’ (3 stars), or ‘positive’ (4-5 stars). We are building a classifier that tags a review as one of the three types of sentiments based on the review text. \n",
    "\n",
    "- **Name classification.** Just like the last assignment. This should be used as your test case. You can just use the first character and the last character as your features.\n",
    "\n",
    "## What needs to be done\n",
    "\n",
    "Maximum Entropy model has a lot of moving parts. The list below guides you through what needs to be done. It comes down to The Three Questions that we learn about in class: representation, learning, and inference. \n",
    "\n",
    "### Representation \n",
    "- Choose the feature set. Use something reasonable and make sure the feature set is reasonably small or the learning algorithm will take a long time. \n",
    "- Choose the data structures that hold the features. We recommend sparse feature vectors. Regardless of your choice, cache the features internally within each Document object as the algorithm is iterative. Featurization must be done only once.\n",
    "- Choose the data structures that hold the parameters. We recommend using a kxp matrix where k is the number of labels, and p is the number of linguistic features. \n",
    "\n",
    "### Learning\n",
    "- Compute the negative log-likelihood function given a minibatch of data. You will need this function to track progress of parameter fitting. \n",
    "- Compute the gradient with respect to the parameters. You will need the gradient for updating the parameters given a minibatch of data. \n",
    "- Implement mini-batch gradient descent algorithm to train the model to obtain the best parameters.\n",
    "\n",
    "### Classification/Inference.\n",
    "- Apply the model on the unseen data. The provided test cases will evaluate the model on both datasets, and you must pass those.\n",
    "\n",
    "### Experiments\n",
    "In addition to implementing mini-batch gradient descent and MaxEnt model, you are asked to do the following experiments to understand the algorithms a little more. For both experiments, use the Yelp review dataset as it is a more realistic one (Real People. Real Reviews. or so they claim).\n",
    "\n",
    "**Experiment 1**: \n",
    "\n",
    "Why are we allowed to use mini-batch instead of the whole training set when updating the parameters? This is indeed the dark art of this optimization algorithm, which works well for many complicated models, including neural networks. Computing gradient is always expensive, so we want to know how much we gain from each gradient computation.\n",
    "\n",
    "In this experiment, try minibatch size = {1, 10, 30, 50, 100, 1000}. For each mini-batch size, plot the number of datapoints that you compute the gradient for so far (x-axis) against the accuracy of the dev set (y-axis). Analyze and write up a short paragraph on what you learn or observe from this experiment. \n",
    "\n",
    "\n",
    "**Experiment 2 **: \n",
    "\n",
    "Does size really matter? The mantra of machine learning tells us that the bigger the training set the better the performance. We will investigate how true this is. \n",
    "\n",
    "In this experiment, fix the feature set to something reasonable and fix the dev set and the test set. Vary the size of the training set {1000, 10000, 20000, 50000, 100000, or more} and compare the (peak) accuracy from each training set size. Make a plot size vs accuracy. Analyze and write up a short paragraph on what you learn or observe from this experiment. \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Submission\n",
    "\n",
    "Submit the following on Latte:\n",
    "\n",
    "\n",
    "**All your code.** But don’t include the datasets as we already have those.\n",
    "\n",
    "**Report.** The report should include all the results from the experiments. And it should explain your experiment setting so that other people can replicate it. It should explain clearly what feature set is being used and how you set up mini-batch gradient descent because there can be quite a bit of variation. This should not be more than two pages single-spaced including graphs. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## More on Mini-batch Gradient Descent\n",
    "\n",
    "In this assignment, we will train MaxEnt models using mini-batch gradient descent. Gradient descent learns the parameter by iterative updates given a chunk of data and its gradient. \n",
    "\n",
    "If a chunk of data is the entire training set, we call it batch gradient descent. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "while not converged:\n",
    "    gradient = compute_gradient(parameters, training_set)\n",
    "    parameters += gradient * learning_rate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Batch gradient descent is much slower. Each update requires us to compute gradient from the entire dataset. This is usually not necessary. Computing gradient from the smaller subset of dataset at a time usually gives the same results if done repeatedly. \n",
    "\n",
    "If the data is subset of the training set, we call it mini-batch gradient descent. This approximates the gradient of batch gradient descent. Each update only requires the computation of gradient of a small subset of the data (called mini-batch of data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "while not converged:\n",
    "    minibatches = chop_up(training_set)\n",
    "    for each minibatch in all minibatches:\n",
    "        gradient = compute_gradient(parameters, minibatch)\n",
    "        parameters += gradient * learning_rate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If a chunk of data is just one instance from the training set, we call it stochastic gradient descent (SGD). Each update only requires the computation of gradient of one instance of data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "while not converged:\n",
    "    for each datapoint in training_set:\n",
    "        gradient = compute_gradient(parameters, datapoint)\n",
    "        parameters += gradient * learning_rate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Practical issues with mini-batch gradient descent\n",
    "\n",
    "- How should I initialize the parameters at the first iteration?\n",
    "\n",
    "    Set them all to zero. This is generally not advisable for more complicated model. But for the Maximum Entropy model, zero initialization works perfectly. \n",
    "\n",
    "\n",
    "- How do I introduce the bias term?\n",
    "\n",
    "    Include a feature that exists in ALL data instances. And treat it as a normal feature and proceed as usual. \n",
    "\n",
    "\n",
    "- Why do the posterior P(Y|X) become NaN? \n",
    "\n",
    "    It is very likely that you exponentiate some big number and divide by the same amount i.e. if unnoramlized_score is a vector of unnormalized scores (the sum of lambdas), then:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "             posterior = exp(unnormalized_score) / sum(exp(unnormalized_score)) \n",
    "     \n",
    "   > This is no good. We have to get around by using some math tricks:\n",
    "   \n",
    "             posterior = exp(unnormalized_score - scipy.misc.logsumexp(unnormalized_score))\n",
    "     \n",
    "   > If this confuses you or you are not sure why this is correct, think about it more or ask Chuan or Kahlil. But we are quite confident that you will need to use logsumexp function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "- How do you know that it converges? \n",
    "\n",
    "    It is extremely difficult to know. If you stop too early, the model has not reached its peak yet i.e. underfitting. If you stop too late, the model will fit too well to the training set and not generalize to the unseen data i.e. overfitting. But there are multiple ways to guess the convergence. We suggest this method called early stopping.\n",
    "\n",
    "    Every once in a while evaluate the model on the development set during gradient descent.\n",
    "\n",
    "    - If the performance is better than last evaluation, then save this set of parameters and keep going for a little more. \n",
    "    - If the performance stops going up after a few updates, stop and use the last saved parameters. (How many is a few? Up to you)\n",
    "\n",
    "\n",
    "- How often should I run evaluation on the dev set during training? \n",
    "\n",
    "    Up to you. It is actually OK to run the evaluation on the dev at every update you make to the parameters.\n",
    "\n",
    "\n",
    "- How do I know that my implementation is correct?\n",
    "\n",
    "    Look at the average negative log-likelihood. It should keep going down monotonically i.e. at every single update. You should also see that the gradient should get closer and closer to zero."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}