2014-10-10-Classifying_Wikipedia_Changes.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:3bd5a2290eb9cf39ac8b1da45cc83a21e3fe298b571cecc8fc1e8e6dc73d0fea"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Classifying Wikipedia Changes"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "I recently joined a Kaggle competition on [multilabel text classification](http://www.kaggle.com/c/tradeshift-text-classification) \n",
      "and have learned a ton from basic code that one of the competitors \n",
      "[shared in the forums](http://www.kaggle.com/c/tradeshift-text-classification/forums/t/10537/beat-the-benchmark-with-less-than-400mb-of-memory).\n",
      "\n",
      "The code of the genereous competitor does logistic regression classification for multiple classes with stochastic gradient ascent.\n",
      "It is further well-suited for online learning as it uses the hashing trick to one-hot encode boolean, string, and categorial features.\n",
      "\n",
      "To better understand these methods and tricks I here apply some of them to a multilabel problem I chose mostly for the easy access to a constant stream of training data:\n",
      "\n",
      "All recent changes on Wikipedia are tracked on [this special page](http://en.wikipedia.org/wiki/Special:RecentChanges)\n",
      "where we can see a number of interesting features such as the length of the change, the contributor's username,\n",
      "the title of the changed article, and the contributor's comment for a given change.\n",
      "\n",
      "Using the Wikipedia API to look at this stream of changes we can also see how contributors classify their changes as **bot**, **minor**, and **new**.\n",
      "Multiple label assignments are possible, so that one contribution may be classified as both bot and new.\n",
      "\n",
      "Here I will listen to this stream of changes, extract four features (length of change, comment string, username, and article title), and train three logistic regression classifiers (one for each class) to predict the likelihood of a change belonging to each one of them.\n",
      "The training is done with the stochastic gradient ascent method.\n",
      "\n",
      "One caveat: I am a complete novice when it comes to most of this stuff so please take everything that follows with a grain of salt - on the same note I would be forever grateful for any feedback especially of the critical kind so that I can learn and improve."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%matplotlib inline\n",
      "import matplotlib\n",
      "from matplotlib import pyplot as pt\n",
      "import requests\n",
      "import json\n",
      "from math import log, exp, sqrt\n",
      "from datetime import datetime, timedelta\n",
      "import itertools\n",
      "from collections import defaultdict"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The API that Wikipedia offer to listen to the stream of recent changes is described \n",
      "[here](http://www.mediawiki.org/wiki/API:Recentchanges)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "URL = ('http://en.wikipedia.org/w/api.php?format=json&action=query&list=recentchanges&rcprop=parsedcomment'\n",
      "      '%7Ctimestamp%7Ctitle%7Cflags%7Cids%7Csizes%7Cflags%7Cuser&rclimit=100')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The logistic regression classifier requires us to compute the dot product between a feature vector $\\mathbf{x}$\n",
      "and a weight vector $\\mathbf{w}$.\n",
      "\n",
      "$$\\mathbf{w}^\\text{T} \\mathbf{x} = w_0 x_0 + w_1 x_1 + w_2 x_2 + \\ldots + w_N x_N.$$\n",
      "\n",
      "As by convention, the bias of the model is encoded with feature $x_0 = 1$ for all observations -\n",
      "the only thing that will change about the $w_0 x_0$-term is weight $w_0$ upon training.\n",
      "The length of the article change is tracked with numerical feature $x_1$ which equals the number of character changes\n",
      "(hence $x_1$ is either positive or negative for text addition and removal respectively).\n",
      "\n",
      "As in the Kaggle code that our code is mostly based upon, string features are one-hot encoded using the\n",
      "[hashing trick](https://en.wikipedia.org/wiki/Feature_hashing):\n",
      "\n",
      "The string features extracted for each observed article change are username, a parse of the comment, and the title of article.\n",
      "Since this is an online learning problem there is no way of knowing how many unique usernames, comment strings, and article titles\n",
      "are going to be observed.\n",
      "\n",
      "With the hashing trick we decide *ab initio* that `D_sparse`-many unique values across these three features are sufficient to care about:\n",
      "Our one-hot encoded feature space has dimension `D_sparse` and can be represented as a `D_sparse`-dimensional vector filled\n",
      "with `0`'s and `1`'s (feature not present / present respectively).\n",
      "\n",
      "The *hash* in *hashing trick* comes from the fact that we use a hash function to convert strings to integers.\n",
      "Suppose now that we chose `D_sparse = 3` and our hash function produces\n",
      "`hash(\"georg\") = 0`, `hash(\"georgwalther\") = 2`, and `hash(\"walther\") = 3` for three observed usernames.\n",
      "\n",
      "For username `georg` we get feature vector $[1, 0, 0]$ and for username `georgwalther` we get $[0, 0, 1]$.\n",
      "The hash function maps username `walther` outside our 3-dimensional feature space and to close this loop we not only\n",
      "use the `hash` function but also the `modulus` (which defines an [equivalence relation](https://en.wikipedia.org/wiki/Equivalence_relation)?):\n",
      "\n",
      "`hash(\"georg\") % D_sparse = 0`, `hash(\"georgwalther\") % D_sparse = 2`, and `hash(\"walther\") % D_sparse = 0`\n",
      "\n",
      "This illustrates one downside of using the hashing trick since we will now map usernames `georg` and `walther` to the same feature vector $[1, 0, 0]$.\n",
      "We are therefore best adviced to choose a big `D_sparse` to avoid mapping different feature values to the same one-hot-encoded feature - but probably not too big to preserve memory.\n",
      "\n",
      "For each article change observation we only map three string features into this `D_sparse`-dimensional one-hot-encoded feature space - out of `D_sparse`-many vector elements there will only ever be three ones among (`D_sparse`-3) zeros (if we do not map to the same vector index multiple times).\n",
      "We will therefore use sparse encoding for these feature vectors (hence the `sparse` in `D_sparse`).\n",
      "\n",
      "We will also normalize the length of change on the fly using\n",
      "an \n",
      "[online algorithm for mean and variance estimation](https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Incremental_algorithm)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "D = 2  # number of non-sparse features\n",
      "D_sparse = 2**18  # number of sparsely-encoded features"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def get_length_statistics(length, n, mean, M2):\n",
      "    \"\"\" https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Incremental_algorithm \"\"\"\n",
      "    n += 1\n",
      "    delta = length-mean\n",
      "    mean += float(delta)/n\n",
      "    M2 += delta*(length - mean)\n",
      "    \n",
      "    if n < 2:\n",
      "        return mean, 0., M2\n",
      "\n",
      "    variance = float(M2)/(n - 1)\n",
      "    std = sqrt(variance)\n",
      "    return mean, std, M2\n",
      "\n",
      "def get_data():\n",
      "    X = [1., 0.]  # bias term, length of edit\n",
      "    X_sparse = [0, 0, 0]  # hash of comment, hash of username, hash of title\n",
      "    Y = [0, 0, 0]  # bot, minor, new\n",
      "\n",
      "    length_n = 0\n",
      "    length_mean = 0.\n",
      "    length_M2 = 0.\n",
      "    \n",
      "    while True:\n",
      "        r = requests.get(URL)\n",
      "        r_json = json.loads(r.text)['query']['recentchanges']\n",
      "        for el in r_json:\n",
      "            length = abs(el['newlen'] - el['oldlen'])\n",
      "            length_n += 1\n",
      "            length_mean, length_std, length_M2 = get_length_statistics(length, length_n, length_mean, length_M2)\n",
      "            X[1] = (length - length_mean)/length_std if length_std > 0. else length\n",
      "\n",
      "            X_sparse[0] = abs(hash('comment_' + el['parsedcomment'])) % D_sparse\n",
      "            X_sparse[1] = abs(hash('username_' + el['user'])) % D_sparse\n",
      "            X_sparse[2] = abs(hash('title_' + el['title'])) % D_sparse\n",
      "\n",
      "            Y[0] = 0 if el.get('bot') is None else 1\n",
      "            Y[1] = 0 if el.get('minor') is None else 1\n",
      "            Y[2] = 0 if el.get('new') is None else 1\n",
      "\n",
      "            yield Y, X, X_sparse"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def predict(w, w_sparse, x, x_sparse):\n",
      "    \"\"\" P(y = 1 | (x, x_sparse), (w, w_sparse)) \"\"\"\n",
      "    wTx = 0.\n",
      "    for i, val in enumerate(x):\n",
      "        wTx += w[i] * val\n",
      "\n",
      "    for i in x_sparse:\n",
      "        wTx += w_sparse[i]  # *1 if i in x_sparse\n",
      "\n",
      "    try:\n",
      "        wTx = min(max(wTx, -100.), 100.)\n",
      "        res = 1./(1. + exp(-wTx))\n",
      "    except OverflowError:\n",
      "        print wTx\n",
      "        raise\n",
      "        \n",
      "    return res"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def update(alpha, w, w_sparse, x, x_sparse, p, y):\n",
      "    for i, val in enumerate(x):\n",
      "        w[i] += (y - p) * alpha * val\n",
      "    for i in x_sparse:\n",
      "        w_sparse[i] += (y - p) * alpha  # * feature[i] but feature[i] == 1 if i in x"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "K = 3\n",
      "w = [[0.] * D for k in range(K)]\n",
      "w_sparse = [[0.] * D_sparse for k in range(K)]\n",
      "predictions = [0.] * K\n",
      "alpha = .1"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "time0 = datetime.now()\n",
      "training_time = timedelta(minutes=10)\n",
      "\n",
      "ctr = 0\n",
      "for y, x, x_sparse in get_data():\n",
      "    for k in range(K):\n",
      "        p = predict(w[k], w_sparse[k], x, x_sparse)\n",
      "        predictions[k] = float(p)\n",
      "        update(alpha, w[k], w_sparse[k], x, x_sparse, p, y[k])\n",
      "\n",
      "    ctr += 1\n",
      "    \n",
      "    # if ctr % 10000 == 0:\n",
      "        # print 'samples seen', ctr\n",
      "        # print 'sample', y\n",
      "        # print 'predicted', predictions\n",
      "        # print ''\n",
      "\n",
      "    if (datetime.now() - time0) > training_time:\n",
      "        break"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "ctr"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "As we can see, we crunched through 106,401 article changes during our ten-minute online training."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It would be fairly hard to understand the link between the `D_sparse`-dimensional one-hot-encoded feature space and\n",
      "the observed / predicted classes.\n",
      "However we can still look at the influence that the length of the article change has on our classification problem"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print w[0]\n",
      "print w[1]\n",
      "print w[2]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Here we can see that the weight of the length of change for class `0` (**bot**) is `-1.12`, for class `1` (**minor**) is `-0.97`, and for class `2` (**new**) is `2.11`.\n",
      "\n",
      "Intuitively this makes sense since many added characters (big positive change) should make classification as a **minor** change\n",
      "less likely and classification as a **new** article more likely:\n",
      "For an observed positive character count change $C$, $2.11 C$ will place us further to the right, and $-0.97 C$ further to the left along the $x$-axis of the sigmoid function:\n",
      "\n",
      "![img](http://gaelvaroquaux.github.io/scikit-learn-tutorial/_images/logistic_regression1.png)\n",
      "(from http://gaelvaroquaux.github.io/scikit-learn-tutorial/supervised_learning.html#classification)\n",
      "\n",
      "Further below we will see that the vast majority of **bot** changes are classified as **minor** changes hence we would expect to see correlation between the weights of this feature for these two classes."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "To further evaluate our three classifiers, we observe another 10,000 Wikipedia changes and construct a confusion matrix."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "no_test = 10000\n",
      "test_ctr = 0\n",
      "\n",
      "classes = {c: c_i for c_i, c in enumerate(list(itertools.product([0, 1], repeat=3)))}\n",
      "confusion_matrix = [[0 for j in range(len(classes))] for i in range(len(classes))]\n",
      "\n",
      "predicted = [0, 0, 0]\n",
      "for y, x, x_sparse in get_data():\n",
      "    for k in range(K):\n",
      "        p = predict(w[k], w_sparse[k], x, x_sparse)\n",
      "        predicted[k] = 1 if p > .5 else 0\n",
      "    i = classes[tuple(y)]\n",
      "    j = classes[tuple(predicted)]\n",
      "    confusion_matrix[i][j] += 1\n",
      "    test_ctr +=1\n",
      "    \n",
      "    if test_ctr >= no_test:\n",
      "        break"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "matplotlib.rcParams['font.size'] = 15\n",
      "fig = pt.figure(figsize=(11, 11))\n",
      "pt.clf()\n",
      "ax = fig.add_subplot(111)\n",
      "ax.set_aspect(1)\n",
      "res = ax.imshow(confusion_matrix, cmap=pt.cm.jet, interpolation='nearest')\n",
      "cb = fig.colorbar(res)\n",
      "labels = [{v: k for k, v in classes.iteritems()}[i] for i in range(len(classes))]\n",
      "pt.xticks(range(len(classes)), labels)\n",
      "pt.yticks(range(len(classes)), labels)\n",
      "pt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The confusion matrix shows actual classes along the vertical and predicted classes along the horizontal axis.\n",
      "\n",
      "The vast majority of observed classes are $(0, 0, 0)$ and our classifiers get most of these right except that some\n",
      "are misclassified as $(0, 0, 1)$ and $(0, 1, 0)$.\n",
      "\n",
      "All observed bot-related changes (classes starting with a $1$) are $(1, 1, 0)$ (i.e. minor bot-effected changes) and\n",
      "our classifiers get all of those right."
     ]
    }
   ],
   "metadata": {}
  }
 ]
}