Notebooks/addressing_overfitting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "NHsZE6aZwyVD"
   },
   "source": [
    "# Today's Dataset\n",
    "\n",
    "..... 20 newsgroups!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 53
    },
    "colab_type": "code",
    "id": "V9Y2bRSYU4WF",
    "outputId": "c4a3ebe4-236a-4a44-ea20-71f18347f818"
   },
   "outputs": [],
   "source": [
    "from sklearn.datasets import fetch_20newsgroups\n",
    "\n",
    "# new categories!!\n",
    "cats = ['comp.sys.mac.hardware', 'rec.motorcycles', 'rec.sport.baseball', \n",
    "        'sci.electronics', 'sci.med', 'talk.politics.guns', 'talk.religion.misc']\n",
    "\n",
    "all_data = fetch_20newsgroups(subset='all', categories=cats)\n",
    "train_set = fetch_20newsgroups(subset='train', categories=cats)\n",
    "test_set = fetch_20newsgroups(subset='test', categories=cats)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Uc7ZxUBbAtGZ"
   },
   "source": [
    "First we will turn the provided train/test sets into tf-idf vectors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ZA-IsYFXXji1"
   },
   "outputs": [],
   "source": [
    "from sklearn.feature_extraction.text import TfidfVectorizer\n",
    "\n",
    "vectorizer = TfidfVectorizer(min_df=3, stop_words='english')\n",
    "\n",
    "X_train = vectorizer.fit_transform(train_set.data)\n",
    "y_train = train_set.target\n",
    "\n",
    "# Prepare test data. Only transformation needed. \n",
    "X_test = vectorizer.transform(test_set.data)\n",
    "y_test = test_set.target\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Crr0aea40Buj"
   },
   "source": [
    "# the Problem of Overfitting\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "iSvR3fb47Fdx"
   },
   "source": [
    "\n",
    "![alt text](https://cdn-images-1.medium.com/max/1600/1*SBUK2QEfCP-zvJmKm14wGQ.png)\n",
    "\n",
    "The model fits to small, irrelevant intricacies in the dataset and has good performance, but does not generalize well.\n",
    "\n",
    "Common signs of overfitting:\n",
    "* Significantly better performance on training set than on testing set\n",
    "* Worse than expected performance\n",
    "\n",
    "Many ways to deal with this, but a few are:\n",
    "* getting more data\n",
    "* dimensionality reduction\n",
    "* cross validation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "e4TdV9qtvKG7"
   },
   "source": [
    "# Dimensionality Reduction\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "hrwqjf6h703U"
   },
   "source": [
    "Problems with high-dimension features:\n",
    "\n",
    "* Higher risk of overfitting to sparse data\n",
    "* Redundant correlated variables\n",
    "*  Computationally intensive\n",
    "\n",
    "Solution: use fewer dimensions! (This does not necessarily eliminate overfitting)\n",
    "\n",
    "## Principal Component Analysis (PCA)\n",
    "One form of dimensionality reduction\n",
    "\n",
    "* This is NOT choosing a subset of the features to use\n",
    "* Compute a few _new_ features that summarize most of the variance of the original ones\n",
    "\n",
    "### PCA Intuition with example from textbook\n",
    "\n",
    "[textbook link](https://jakevdp.github.io/PythonDataScienceHandbook/05.09-principal-component-analysis.html)\n",
    "\n",
    "2D - dataset |  2 principal component vectors | \n",
    "- | - \n",
    "![2D - dataset](https://i.imgur.com/4GAQdxs.png) | ![vectors](https://i.imgur.com/nTAzIhB.png) \n",
    "\n",
    "\n",
    "Transformation to principal component axes | Original data with projected data (darker)\n",
    "- | - \n",
    "![transformed](https://i.imgur.com/9wa8T7W.png) | ![projected](https://i.imgur.com/uPXWvpU.png)\n",
    "\n",
    "[Cool PCA visuals](http://setosa.io/ev/principal-component-analysis/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "3czz3oQs-O3J"
   },
   "source": [
    "[PCA in sklearn](https://scikit-learn.org/stable/modules/generated/sklearn.decomposition.PCA.html)\n",
    "\n",
    "[TruncatedSVD in sklearn](https://scikit-learn.org/stable/modules/generated/sklearn.decomposition.TruncatedSVD.html#sklearn.decomposition.TruncatedSVD)\n",
    "\n",
    "[StackOverflow explanation of the difference](https://stats.stackexchange.com/a/239537)\n",
    "\n",
    "\n",
    "Essentially, TruncatedSVD does not center the data, so it can work with sparse arrays (where centering the data is very expensive). This is useful in NLP where we often operate on tf-idf arrays.\n",
    "\n",
    "Using Truncated SVD on a tf-idf array is known as *Latent Semantic Analysis* (LSA). \n",
    "* Supposedly helps when dealing with synonymy and polysemy\n",
    "\n",
    "[LSA wikipedia page](https://en.wikipedia.org/wiki/Latent_semantic_analysis)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 35
    },
    "colab_type": "code",
    "id": "BVS4a5OddOez",
    "outputId": "ef10e2bf-4e63-4660-c203-e9128ae71613"
   },
   "outputs": [],
   "source": [
    "print(X_train[0].shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "y9gGQb4udenb"
   },
   "outputs": [],
   "source": [
    "N_COMPONENTS = 25"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 460
    },
    "colab_type": "code",
    "id": "YGGthwNwXSvx",
    "outputId": "741dbc34-4fb5-4281-c7f6-e46c99099258"
   },
   "outputs": [],
   "source": [
    "from sklearn.decomposition import PCA, TruncatedSVD\n",
    "pca = PCA(n_components=N_COMPONENTS)\n",
    "pca.fit(X_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 35
    },
    "colab_type": "code",
    "id": "CelFwrs4XUnK",
    "outputId": "5bab3f1c-7e2b-4983-ab2d-6dde2292fbb2"
   },
   "outputs": [],
   "source": [
    "from sklearn.decomposition import TruncatedSVD\n",
    "svd = TruncatedSVD(n_components=N_COMPONENTS)\n",
    "\n",
    "X_train_svd = svd.fit_transform(X_train)\n",
    "X_test_svd = svd.transform(X_test)\n",
    "\n",
    "print(X_train.shape, X_train_svd.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 35
    },
    "colab_type": "code",
    "id": "cn1KwjvsaN49",
    "outputId": "c6aa0e8a-764a-4a0b-bda2-845f6fa17e13"
   },
   "outputs": [],
   "source": [
    "print(svd.explained_variance_ratio_.sum()) # total amount of variance explained by all N_COMPONENTS components"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "zKzLXBQQPXn8"
   },
   "source": [
    "# K-Nearest-Neighbors (KNN)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "jhLyTelffkJq"
   },
   "source": [
    "\n",
    "Simple, intuitive algorithm, a form of \"lazy learning\" (as opposed to \"eager learning\", which has a separate training/fitting step).\n",
    "\n",
    "![knn](https://www.fromthegenesis.com/wp-content/uploads/2018/09/K_NN_Ad.jpg)\n",
    "\n",
    "[KNN in sklearn](https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "JFZFZQWUflh3"
   },
   "outputs": [],
   "source": [
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "from sklearn.metrics import confusion_matrix, accuracy_score, f1_score\n",
    "\n",
    "import seaborn as sns\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "plt.rc('font', size=16)          # controls default text sizes\n",
    "plt.rc('axes', titlesize=20)     # fontsize of the axes title\n",
    "plt.rc('axes', labelsize=20)    # fontsize of the x and y labels\n",
    "plt.rc('xtick', labelsize=20)    # fontsize of the tick labels\n",
    "plt.rc('ytick', labelsize=20)\n",
    "\n",
    "def classify_and_plot(x_train, y_train, x_test, y_test, num_neighbors=5):\n",
    "  \"\"\"\n",
    "  Arguments:\n",
    "    - x_train (np.ndarray): training data\n",
    "    - y_train (np.ndarray): training data labels\n",
    "    - x_test (np.ndarray): testing data\n",
    "    - y_test (np.ndarray): testing data labels\n",
    "    - num_neighbors (int, default 5): number of neighbors for KNN\n",
    "  \"\"\"\n",
    "  \n",
    "  knn = KNeighborsClassifier(n_neighbors=5, algorithm='brute')\n",
    "  \n",
    "  \n",
    "  knn.fit(x_train, y_train)\n",
    "  y_pred = knn.predict(x_test)\n",
    "  \n",
    "  cm = confusion_matrix(y_test, y_pred)\n",
    "  ax = sns.heatmap(cm, annot=True, fmt='d', square=True, \n",
    "              xticklabels=train_set.target_names, \n",
    "              yticklabels=test_set.target_names)\n",
    "  bottom, top = ax.get_ylim()\n",
    "  ax.set_ylim(bottom + 0.5, top - 0.5) # Since my matplotlib cuts off the y-axis...\n",
    "  plt.xlabel('Predicted')\n",
    "  plt.ylabel('Truth')\n",
    "  plt.show()\n",
    "  print('accuracy:', accuracy_score(y_test, y_pred))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 596
    },
    "colab_type": "code",
    "id": "tNGPqqpWhnv4",
    "outputId": "9321f708-c15f-43a3-c821-21e86fa21cfd"
   },
   "outputs": [],
   "source": [
    "classify_and_plot(X_train, y_train, X_test, y_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 596
    },
    "colab_type": "code",
    "id": "A9xSF1sTn554",
    "outputId": "d2d5c975-d2b7-4f18-b6ae-e8a0ca7a80cb"
   },
   "outputs": [],
   "source": [
    "classify_and_plot(X_train_svd, y_train, X_test_svd, y_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "jHwyIOlwziXY"
   },
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "_Ejz1IQy0MJ6"
   },
   "source": [
    "# Cross Validation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "GoGB953gV16N"
   },
   "source": [
    "![alt text](https://kevinzakka.github.io/assets/knn/k-fold.png )\n",
    "\n",
    "\n",
    "\n",
    "K-fold CV is the most popular type of cross validation.\n",
    "\n",
    "* Thoroughly test your model and evaluate it more realistically\n",
    "* Helps with tuning model hyperparameters\n",
    "\n",
    "\n",
    "Stratified K-fold cross validation takes _**class imbalance**_ into account, ensuring all splits have equal representation of all of your classes. We will use this.\n",
    "\n",
    "[Stratified K-fold CV in sklearn](https://scikit-learn.org/stable/modules/generated/sklearn.model_selection.StratifiedKFold.html#sklearn.model_selection.StratifiedKFold)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Z52vv8rt6Pyo"
   },
   "outputs": [],
   "source": [
    "X = np.array(all_data.data)\n",
    "y = all_data.target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ykl3huf60gbo"
   },
   "outputs": [],
   "source": [
    "from tqdm import tqdm # Arabic taqaddum (تقدّم)\n",
    "\n",
    "from sklearn.model_selection import StratifiedKFold, KFold\n",
    "# sklearn has nice functions to simplify this process\n",
    "\n",
    "skf = StratifiedKFold(n_splits=5)\n",
    "\n",
    "knn = KNeighborsClassifier(n_neighbors=5, algorithm='brute')\n",
    "\n",
    "def run_kf(knn, kf, X, y):\n",
    "  \"\"\"\n",
    "  Arguments:\n",
    "    - knn (sklearn.neighbors.KNeighborsClassifier): knn classifier \n",
    "    - skf (sklearn.model_selection._split.StratifiedKFold): stratified k fold splitter\n",
    "    - X (np.ndarray): data\n",
    "    - y (np.ndarray): labels\n",
    "    \n",
    "  Returns:\n",
    "    - scores (list[float]): list of accuracy scores for each CV split\n",
    "  \"\"\"\n",
    "  scores = []\n",
    "  \n",
    "  for train_index, test_index in tqdm(kf.split(X, y)):\n",
    "    X_train, X_test = X[train_index], X[test_index]\n",
    "    y_train, y_test = y[train_index], y[test_index]\n",
    "    \n",
    "    X_train_tfidf = vectorizer.fit_transform(X_train)\n",
    "    X_test_tfidf = vectorizer.transform(X_test)\n",
    "    X_train_svd = svd.fit_transform(X_train_tfidf)\n",
    "    X_test_svd = svd.transform(X_test_tfidf)\n",
    "    knn.fit(X_train_svd, y_train)\n",
    "\n",
    "    y_pred = knn.predict(X_test_svd)\n",
    "\n",
    "    scores.append(accuracy_score(y_test, y_pred))\n",
    "\n",
    "  return scores\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 35
    },
    "colab_type": "code",
    "id": "2BociaCJ-uU1",
    "outputId": "1c6d8075-5ed7-4540-a1f4-d84b76808e05"
   },
   "outputs": [],
   "source": [
    "scores = run_kf(knn, skf, X, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 71
    },
    "colab_type": "code",
    "id": "FeEzAU4_y8uu",
    "outputId": "9bd1fd47-f0c2-46e7-b595-54e4d1326a25"
   },
   "outputs": [],
   "source": [
    "print('scores', scores)\n",
    "print('mean score', np.mean(scores))\n",
    "print('min score', min(scores))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 89
    },
    "colab_type": "code",
    "id": "HyJYZm2MAdHJ",
    "outputId": "c9d50fdd-6d3d-4e50-cfcf-c18d99e8a82b"
   },
   "outputs": [],
   "source": [
    "# Why are these all significantly higher than the accuracy scores we got from before?\n",
    "print('length of all data', len(all_data.data))\n",
    "print('length of given training data', len(train_set.data))\n",
    "print('length of given testing data', len(test_set.data))\n",
    "print('percentage training data', len(train_set.data)/len(all_data.data))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 603
    },
    "colab_type": "code",
    "id": "4j7BGH7PCkpR",
    "outputId": "11a6b75d-1e67-458c-99b1-50639535d243"
   },
   "outputs": [],
   "source": [
    "_, train_counts = np.unique(train_set.target, return_counts=True)\n",
    "_, test_counts = np.unique(test_set.target, return_counts=True)\n",
    "\n",
    "\n",
    "plt.figure(figsize=(24, 6))\n",
    "\n",
    "plt.subplot(121)\n",
    "plt.bar(train_set.target_names, train_counts)\n",
    "plt.xticks(rotation=90)\n",
    "plt.title('train')\n",
    "\n",
    "plt.subplot(122)\n",
    "plt.bar(test_set.target_names, test_counts)\n",
    "plt.xticks(rotation=90)\n",
    "plt.title('test')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "wpnbfhaIQXCK"
   },
   "source": [
    "It looks like they are properly stratified! So what gives?\n",
    "\n",
    "The amount of training data is a factor, as when you use a 5-fold split, each iteration has a train-test split of 80-20, providing more training data than the provided training subset (which was split 60-40 train-test).\n",
    "\n",
    "But if we change to a 2-fold split, with 50-50 train-test, it still does better...\n",
    "\n",
    "It turns out that when you select the provided train/test subsets with sklearn's `fetch_20newsgroups` function, the split between the train and test set is based on messages from before and after a specific date. [source](https://scikit-learn.org/0.19/datasets/twenty_newsgroups.html)\n",
    "\n",
    "Which way of splitting is better?\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "include_colab_link": true,
   "name": "ling1340_ml_intro_3",
   "provenance": [],
   "toc_visible": true,
   "version": "0.3.2"
  },
  "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}