{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# ML-Fundamentals - Exercise - Mutual Information for Feature Selection" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Table of Contents\n", "* [Introduction](#Introduction)\n", "* [Requirements](#Requirements) \n", " * [Knowledge](#Knowledge)\n", " * [Modules](#Python-Modules)\n", "* [Teaching Content](#Teaching-Content)\n", " * [Expected Mutual Information and Kullback Leibler Divergence](#Expected-Mutual-Information-and-Kullback-Leibler-Divergence)\n", " * [Information Gain](#Information-Gain)\n", "* [Preparing the Documents](#Preparing-the-Documents)\n", " * [Loading the Dataset](#Loading-the-Dataset)\n", " * [Vectorization](#From-Documents-to-Feature-Vectors)\n", " * [Review](#Review)\n", "* [Exercise - Mutual Information](#Exercise---Mutual-Information)\n", "* [Training a Feature Selector](#Training-a-Feature-Selector)\n", " * [Testing our Selection](#Testing-our-Selection)\n", "* [Literature](#Literature)\n", "* [Licenses](#Licenses)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Introduction\n", "\n", "In this notebook you will be dealing with feature selection. You will be presented with a binary classification problem in which documents belong to one of two categories. We will be using the presence or absence of terms from a document to predict its category. \n", "\n", "Our aim is to avoid checking for the presence or absence of each possible term in a given document. Some features carry more weight in making a prediction that others, so ideally using only a selected subset of terms in our classification should suffice.\n", "\n", "This process is called **feature selection**. One of the ways to measure how much a feature contributes to the classification is **mutual information**.\n", "\n", "Your task will be to work out the terms we ought to select when using only a limited number of features." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Requirements\n", "\n", "### Knowledge\n", "\n", "To complete this exercise notebook you should possess knowledge about the following topics.\n", "* Feature selection\n", "* Mutual information\n", "* optional: Kullback Leibler Divergence\n", "\n", "The following literature can help you to acquire this knowledge:\n", "* Chapter 13.5 \"Feature Selection\" of *Introduction to Information Retrieval* [[IIR]](#IIR). The introduction defines and discusses the motivation behind feature selection. 13.5.1 in particular explains the approach of mutual information.\n", "* For a review of the state-of-the-art of feature selection methods based\n", "on mutual information see [[VER14]](#VER14).\n", "* Later in the notebook we use Bernoulli Naive Bayes for classification from scikit learn. If you want to learn \n", "more about this kind of classifier study Chapter 13.3 \"The Bernoulli model\" of *Introduction to Information Retrieval* [[IIR]](#IIR)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Python Modules" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "# External Modules\n", "import numpy as np\n", "from sklearn.datasets import fetch_20newsgroups\n", "from sklearn.feature_extraction.text import CountVectorizer\n", "\n", "%matplotlib inline\n", "import matplotlib.pyplot as plt\n", "\n", "from matplotlib.ticker import ScalarFormatter\n", "from sklearn.naive_bayes import MultinomialNB, BernoulliNB\n", "from sklearn.pipeline import Pipeline" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Teaching Content" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Expected Mutual Information and Kullback Leibler Divergence\n", "\n", "The Kullback Leibler Divergence between two probability distributions $p$ and $q$ is\n", "\n", "$$\n", " \\mathcal D_{KL} (p({\\bf z}) \\mid\\mid q({\\bf z}))= \\sum_{{\\bf z} \\in \\mathcal Z} p({\\bf z}) \\log\\frac{p({\\bf z})}{q({\\bf z})}\n", "$$\n", "\n", "\n", "The _expected_ __mutual information (eMI)__ is the Kullback Leiber Divergence \n", "between the joint probability $p(x,y)$ and the product of the marginal distributions $p(x)p(y)$, i.e.\n", "- ${\\bf z} = (x,y)$\n", "- $p({\\bf z}) = p(x, y)$\n", "- $q({\\bf z}) = p(x)p(y)$ \n", "\n", "$$\n", " eMI(X; Y) := \\mathcal D_{KL} (p(X,Y) \\mid\\mid p(X)p(Y))= \\sum_{{x,y} \\in \\mathcal{X,Y}} p(x,y) \\log\\frac{p(x,y)}{p(x)p(y)}\n", "$$\n", "\n", "So if the two random variables $x$ and $y$ are statistically independent the eMI is zero.\n", "\n", "The stronger the difference between $p(x\\mid y)$ and $p(x)$ the larger the MI, which can be\n", "easily seen from $p(x,y) = p(x \\mid y) p(y)$. \n", "So it's a measure about the information which $y$ has about $x$ (and vice versa). \n", "\n", "**Note:**\n", "$$\n", "\\sum_{{x,y} \\in \\mathcal{X,Y}} = \\sum_{{x} \\in \\mathcal{X}} \\sum_{{y} \\in \\mathcal{Y}}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Information Gain\n", "\n", "Sometimes you find the definition of Information Gain as $I(X; Y) := H(Y) - H(Y \\mid X)$ \n", "with the entropy $H(Y)$ and the conditional entropy $H(Y\\mid X)$, so we have\n", "\n", "\n", "\\begin{align}\n", "I(X; Y) &= H(Y) - H(Y \\mid X)\\\\\n", "&= - \\sum_y p(y) \\log p(y) + \\sum_{x,y} p(x) p(y\\mid x) \\log p(y\\mid x)\\\\\n", "&= \\sum_{x,y} p(x, y) \\log{p(y\\mid x)} - \\sum_{y}\\left(\\sum_x p(x,y)\\right) \\log p(y)\\\\\n", "&= \\sum_{x,y} p(x, y) \\log{p(y\\mid x)} - \\sum_{x,y}p(x,y) \\log p(y)\\\\\n", "&= \\sum_{x,y} p(x, y) \\log \\frac{p(y\\mid x)}{p(y)}\\\\\n", "&= \\sum_{x,y} p(x, y) \\log \\frac{p(y\\mid x)p(x)}{p(y)p(x)}\\\\\n", "&= \\sum_{x,y} p(x, y) \\log \\frac{p(x, y)}{p(y)p(x)}\\\\\n", "&= eMI(X; Y)\n", "\\end{align}\n", "\n", "\n", "\n", "With the definitions above the expected Mutual Information and the Information Gain are the same.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Preparing the documents\n", "\n", "### Loading the dataset\n", "Scikit Learn[SL](#SL) provides [Working With Text Data](https://scikit-learn.org/stable/tutorial/text_analytics/working_with_text_data.html) as a guide on how to load, preprocess and analyse text data.\n", "\n", "To start things off, we fetch a training set of text documents from the 20 Newsgroup dataset. We only include two of the twenty categories which reduces our problem to binary classification." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "categories = ['alt.atheism', 'sci.med' ]\n", "twenty_train = fetch_20newsgroups('./newsgroups_dataset',\n", " subset='train',\n", " categories=categories,\n", " shuffle=True,\n", " random_state=42)\n", "print('(Down)load complete!')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### From Documents to Feature Vectors\n", "We use a [CountVectorizer](https://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.text.CountVectorizer.html) to transform text documents into numerical feature vectors that we can analyse. The transformation comprises these steps:\n", "1. Extract the lexicon. The vectorizer identifies each term that occurs anywhere in the documents and gives it a fixed integer id.\n", "2. Create a document-term matrix. In this matrix, each row represents a document and each column represents a term. Each cell indicates whether or not a given term is present in a given document.\n", "\n", "Remark: For other tasks, we may have to store more information in the document-term matrix, e.g. the number of occurrences." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# MultinomialNB works with occurrence counts, BernoulliNB is designed for binary/boolean features.\n", "# see [IIR] for details. Here we use binary features:\n", "binary = True; classifier = BernoulliNB()\n", "\n", "# ignore words with lower document frequency -> against overfitting\n", "min_df=5\n", "# remove english stop words (words that most likely do not have \n", "# anything to do with the document class because they occur everywhere, e.g. 'and') \n", "stop_words=\"english\" \n", "stop_words=None\n", "vectorizer = CountVectorizer(binary=binary, stop_words=stop_words, min_df=min_df)\n", "X_train = vectorizer.fit_transform(twenty_train.data)\n", "y_train = np.array(twenty_train.target).reshape((-1,))\n", "lexicon = vectorizer.get_feature_names()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "### Review\n", "At this point we've prepared all the data we need to calculate the mutual information of each term.\n", "\n", "* **X_train : *sparse matrix, shape = (n_documents, n_features)***\n", "
Indicates whether or not a term is present in a document.
\n", "
X_train[i,j] is $1$ if $document_i$ contains $term_j$, otherwise it is $0$\n", " \n", " \n", "* **y_train : *array, shape = (n_documents,)***\n", "
The target vector indicating the category of each document. There are two distinct categories, $0$ and $1$.
\n", "
y_train[i] is the category of $document_i$\n", " \n", "
\n", " \n", "* **lexicon : *list, \\_\\_len\\_\\_ = n_features***\n", "
A list of strings that stores the actual term corresponding to each term id. Useful if you've identified some term ids as significant and want to understand what they actually mean.
\n", "
E.g. lexicon[5247] == \"chicken\"\n", " \n", "The following code snippet provides an example of obtaining information about a single document." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def doc_info(idx):\n", " doc = X_train[idx,:].toarray().reshape((-1,))\n", " cat_idx = y_train[idx]\n", " cat_name = twenty_train.target_names[cat_idx]\n", " term_count = np.array(lexicon)[np.where(doc>0)].shape[0]\n", " return locals()\n", "doc_info(123)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "## Exercise - Mutual Information\n", "Calculate the mutual information of each term and return a dict that maps each term id to the mutual information of the term. Later, this function will be invoked with X_train and y_train as arguments. Refer to the docstring for details.\n", "\n", "**Task:**\n", "\n", "Implement the following python function.\n", "\n", "**Hint:**\n", "\n", "When dealing with text classifiaction and binary features, here is an example with concrete values and their meaning:\n", "- $p(y=0)$: The probability that a document is in class $0$. Computed with number of documents in class $0$ divided by the total number of documents.\n", "- $p(x=1)$: The probability that a document contains term $x$.\n", "- $p(x=1, y=0)$: The probability a document contains term $x$ and is in class $0$.\n", "\n", "Further: To avoid division by $0$ when calculating the mutual information, it is common practice to always add $1$ when counting the number of any documents." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def select_features(X, y):\n", " \"\"\"Calculate the mutual information of all terms.\n", " Assumes y comprises two distinct categories 0 and 1.\n", "\n", " :param X: A document-term matrix\n", " :param y: A target vector\n", " :return: A dictionary containg n_features items. Each entry maps\n", " the term id (int) to the mutual information of the term (float or\n", " float-like)\n", " \"\"\"\n", " raise NotImplementedError()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "X_train[:,3].toarray().flatten()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a = np.array([[0,1,1],[1,0,0]])\n", "a[a == 0]\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ex_mi = select_features(X_train, y_train)\n", "best_terms = sorted(ex_mi.items(), key=lambda kv : kv[1], reverse=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If your implementation is correct, the output of the cell below should look similar to the following (depending on what base for the logarithm is used, numbers may vary, but the order should be the same):\n", "\n", "\n", "Terms with the greatest mutual information\n", "god................. 0.19173825649655832\n", "atheists............ 0.17111409529128105\n", "keith............... 0.11713774078039724\n", "cco................. 0.10858678795625454\n", "atheism............. 0.10115308769302479\n", "schneider........... 0.0986931815614237\n", "pitt................ 0.09657796740920438\n", "religion............ 0.0962422171570431\n", "allan............... 0.09502007881084548\n", "gordon.............. 0.08813798072387438\n", "" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print('Terms with the greatest mutual information')\n", "for (term_idx, score) in best_terms[:10]:\n", " print('{} {}'.format(lexicon[term_idx].ljust(20,\".\"), score))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Training a feature selector\n", "This segment defines a feature selector class which implements two methods:\n", "* **fit(X,y)**\n", "
Takes a document-term matrix and a target vector. It learns the mutual information of each term using the function you just implemented.\n", " \n", "* **transform(X)**\n", "
Takes a document-term matrix and returns a subset of it. The shape of the subset is (n_samples, self.k_features) and only represents the k best features in the column vectors." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from sklearn.base import BaseEstimator\n", "\n", "class MutualInformation(BaseEstimator):\n", " cached_best_indices = None\n", "\n", " def __init__(self, k_features=10):\n", " self.k_features=k_features\n", "\n", " def fit(self, X, y=None):\n", " \"\"\"Upon fitting, calculate the best features. The result is cached in a\n", " static map.\"\"\"\n", " if MutualInformation.cached_best_indices is None:\n", " mi = select_features(X,y)\n", " mi_sorted = sorted(mi.keys(), key=mi.__getitem__, reverse=True)\n", " MutualInformation.cached_best_indices = mi_sorted\n", " return self\n", "\n", " def transform(self, X):\n", " \"\"\"Return a subset of X which contains only the best columns.\"\"\"\n", " indices = MutualInformation.cached_best_indices\n", " selected_terms = indices[:self.k_features]\n", " subset = X[:,selected_terms]\n", " return subset\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Testing our Selection\n", "Now that we have a way to identify the k best features, the question arises what value k should be.\n", "In the concluding part of this notebook, we set up a [pipeline](https://scikit-learn.org/stable/modules/compose.html) to streamline the task of Vectorization → Feature selection → Classification and predict the categories of the training set. We increase the value of k in each iteration and observe how the number of features selected affects the accuracy of the prediction.\n", "\n", "As classifier we use Multinominal Naive Bayes from the scikit learn library." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# First we download the test set\n", "twenty_test = fetch_20newsgroups('./newsgroups_dataset',\n", " subset='test',\n", " categories=categories,\n", " shuffle=True,\n", " random_state=42)\n", "print('(Down)load complete!')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "min_zoom = 600\n", "accuracies = []\n", "\n", "# log distribuition from 1 to n_features\n", "k_values = set(np.geomspace(1,len(lexicon), dtype=np.int))\n", "k_values = sorted(k_values.union(set(np.geomspace(min_zoom,len(lexicon), dtype=np.int))))\n", "\n", "for k in k_values:\n", " pipe = Pipeline([\n", " ('vectorizer', CountVectorizer(binary=binary, stop_words=stop_words, min_df=min_df)),\n", " #('class_mapper', ),\n", " ('feature_selector', MutualInformation(k_features = k)),\n", " ('classifier', classifier) # \n", " ])\n", " pipe.fit(twenty_train.data, twenty_train.target)\n", " prediction = pipe.predict(twenty_test.data)\n", " accuracy = np.mean(prediction == twenty_test.target)# or use sklearn.metrics.accuracy_score(twenty_test.target, prediction)\n", " accuracies.append(accuracy)\n", " \n", "k_values = np.array(k_values)\n", "accuracies = np.array(accuracies)\n", "\n", "print('highest accuracy of {} achieved with top {} features used'.format(accuracies.max(), k_values[accuracies.argmax()]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "When the calculation is done, draw the plot." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "plt.figure(figsize=(10,8))\n", "plt.plot(k_values, accuracies, marker='.')\n", "plt.xscale('log')\n", "plt.xlabel('k features used')\n", "plt.minorticks_off()\n", "plt.gca().get_xaxis().set_major_formatter(ScalarFormatter())\n", "plt.ylabel('Accuracy')\n", "using_all = accuracies[-1]\n", "plt.plot(k_values,using_all*np.ones_like(k_values), color='orange', label='Using all features')\n", "plt.legend()\n", "plt.show()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "plt.figure(figsize=(10,8))\n", "plt.plot(k_values[k_values>min_zoom], accuracies[k_values>min_zoom], marker='.')\n", "plt.xscale('log')\n", "plt.xlabel('k features used')\n", "plt.minorticks_off()\n", "plt.gca().get_xaxis().set_major_formatter(ScalarFormatter())\n", "plt.ylabel('Accuracy')\n", "using_all = accuracies[-1]\n", "plt.plot(k_values[k_values>min_zoom], using_all*np.ones_like(k_values[k_values>min_zoom]), color='orange', label='Using all features')\n", "plt.legend()\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Literature\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "\n", "
 \n", " [IIR]\n", " \n", " Introduction To Information Retrieval\n", "Christopher Manning-Prabhakar Raghavan-Hinrich Schütze - Cambridge University Press - 2009Online version: https://nlp.stanford.edu/IR-book/information-retrieval-book.html\n", " \n", " [SL]\n", " \n", " Scikit-learn: Machine Learning in Python\n", "Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vanderplas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, Édouard Duchesnay; 12(Oct):2825−2830, 2011.\n", " Website: https://scikit-learn.org\n", " \n", " [VER14]\n", " \n", " Jorge R. Vergara, Pablo A. Estevez: A review of feature selection methods based on mutual information, Neural Comput & Applic (2014) 24:175–186\n", " Website: http://repositorio.uchile.cl/bitstream/handle/2250/126533/A-review-of-feature-selection-methods-based-on-mutual-information.pdf\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Licenses\n", "\n", "### Notebook License (CC-BY-SA 4.0)\n", "\n", "*The following license applies to the complete notebook, including code cells. It does however not apply to any referenced external media (e.g., images).*\n", "\n", "Exercise - Mutual Information
\n", "by Diyar Oktay, Christian Herta, Klaus Strohmenger