lab7/lab7-trees_and_ensembles_answers.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lab 7: Ensemble Methods\n",
    "\n",
    "This week we will look at how collections of decision trees (or other machine learning models) can be trained on the same dataset and combined to enhance predictive performance. Specifically, we will look at bagging, random forests and boosting which are all related examples of ensemble methods.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1) Bagging\n",
    "The combination of models can often perform much better than the average individual, and sometimes better than the best individual. Ensemble methods are ways of combining multiple models together. For good performance, the models should be diverse to minimise the expected error of the ensemble.\n",
    "\n",
    "Bagging 'bootstrap aggregation' is a simple ensemble method that induces diversity by training M models on different samples of the training set (with replacement) and combining predictions by taking the mean or majority vote. An approximate bagging algorithm is:\n",
    "1. For $m = 1,...,M$ models:\n",
    "    - Randomly sample N data points with replacement from the training set\n",
    "    - Learn a decision tree (CART algorithm) on the subset\n",
    "2. The final prediction is found by a majority vote\n",
    "\n",
    "### 1.1) Train a bagging ensemble\n",
    "\n",
    "Complete the code below to train a bagging ensemble by randomly sampling from the MNIST training dataset to train multiple decision tress. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.datasets import fetch_openml\n",
    "\n",
    "# load the MNIST data\n",
    "X_mnist, y_mnist = fetch_openml(name='mnist_784',return_X_y=True, as_frame=False)\n",
    "frac_of_dataset = 0.5\n",
    "index = int(frac_of_dataset*X_mnist.shape[0])\n",
    "X_train, X_test, y_train, y_test = train_test_split(X_mnist[:index,:], y_mnist[:index], test_size=0.2, random_state=5)\n",
    "\n",
    "num_models = 20\n",
    "sample_size = 2000  # training set size.\n",
    "np.random.seed(0)\n",
    "\n",
    "all_models = []\n",
    "for m in range(num_models):\n",
    "    # TODO\n",
    "    # Sample with replacement from the training set. \n",
    "    # Each sample should contain sample_size data points chosen at random.\n",
    "    # Hint: look at the documentation for numpy.random.choice().\n",
    "    sample_idx = np.random.choice(X_train.shape[0], sample_size)\n",
    "    X_train_sample, y_train_sample = X_train[sample_idx], y_train[sample_idx]\n",
    "    \n",
    "    model = DecisionTreeClassifier()\n",
    "    \n",
    "    # TODO\n",
    "    # train a decision tree classifier on the random sample.\n",
    "    model.fit(X_train_sample,y_train_sample)\n",
    "    \n",
    "    all_models.append(model)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2) Implement bagging prediction\n",
    "\n",
    "Complete the `bagging_predict` function and then run the next cell to create predictions from the bagging ensemble based on majority voting of the individual models. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# count how many classifiers have voted for each class for each point in the test dataset.\n",
    "def bagging_predict(test_data, all_models):\n",
    "    votes = np.zeros((test_data.shape[0], len(all_models)))  # number of classes = 10.\n",
    "    combined_predictions = np.zeros(test_data.shape[0])\n",
    "\n",
    "    for idx, m in enumerate(all_models):\n",
    "        # TODO\n",
    "        # obtain the predictions from model m for the test data and\n",
    "        # populate the votes vector\n",
    "        votes[:, idx] = m.predict(test_data)\n",
    "        \n",
    "    for test_point in range(votes.shape[0]):\n",
    "        # TODO\n",
    "        # determine the class with the most votes for each test point\n",
    "        # and populate the combined_predictions \n",
    "        # hint use np.bincount\n",
    "        combined_predictions[test_point] = np.bincount(np.int64(votes[test_point])).argmax()\n",
    "    \n",
    "    return combined_predictions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prediction = bagging_predict(X_test, all_models)\n",
    "accuracy = np.count_nonzero(prediction==np.int64(y_test))/y_test.shape[0]\n",
    "print(\"Test set accuracy: {}\".format(accuracy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How does the accuracy compare to a single decision tree? \n",
    "\n",
    "Investigate the effect of changing the `sample_size` and `num_models` hyperparameters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2) Random Forests\n",
    "With bagging, the base models (individual decision trees) make similar splits on the same features, meaning that their errors are correlated and this reduces the diversity of the ensemble and limits performance.\n",
    "\n",
    "Random forests improve the diversity of the base models by limiting the number of features considered for determining each split in the decision tree. We can obtain the random forest by modifying the bagging algorithm above so that each split for each model uses only a random subset of features.\n",
    "\n",
    "### 2.1) Implement Random Forest Training\n",
    "\n",
    "Copy in your code for the bagging procedure and modify it to implement random forest. The outline code below shows you where to make the modifications."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_models = 20\n",
    "sample_size = 2000  # training set size.\n",
    "feature_sample_size = 200\n",
    "np.random.seed(0)\n",
    "\n",
    "all_models = []\n",
    "for m in range(num_models):\n",
    "    # TODO\n",
    "    # copy in your code from the bagging exercise here to sample with replacement from the training set. \n",
    "    # Each sample should contain sample_size data points chosen at random.\n",
    "    # Hint: look at the documentation for numpy.random.choice().\n",
    "    sample_idx = np.random.choice(X_train.shape[0], sample_size)\n",
    "    X_train_sample, y_train_sample = X_train[sample_idx], y_train[sample_idx]\n",
    "\n",
    "    # TODO\n",
    "    # create a decision tree classifier with limited features considered\n",
    "    # for each split\n",
    "    model = DecisionTreeClassifier(max_features=feature_sample_size)\n",
    "    \n",
    "    # TODO\n",
    "    # copy in your code from the bagging exercise here to train a decision tree classifier on the random sample.\n",
    "    # Remember to train it only on the random sample of features.\n",
    "    model.fit(X_train_sample, y_train_sample)\n",
    "    \n",
    "    all_models.append(model)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2) Random Forest Prediction\n",
    "\n",
    "Use the `bagging_predict` function from Section 2.2 to generate predictions for the random forest and calculate the accuracy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prediction = bagging_predict(X_test, all_models)\n",
    "accuracy = np.count_nonzero(prediction==np.int64(y_test))/y_test.shape[0]\n",
    "print(\"Test set accuracy: {}\".format(accuracy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How does the performance of the random forest compare to bagging and the single model? Can you improve the performance by changing the hyperparameters?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3) Boosting\n",
    "We can use a decision tree classifier as the base model for the ensemble method known as boosting. Boosting involves training base models in sequence to ensure that each base model addresses the weaknesses of the ensemble. Instead of training a new base model on a random sample, we weight the data points in the training set according to the performance of previous base models.\n",
    "\n",
    "AdaBoost (adaptive boosting) is a popular boosting method, where training examples that are misclassified by one of the base classifiers are given greater weight when used to train the next classifier in the sequence. Once all the classifiers have been trained, their predictions are then combined through a weighted majority voting scheme.\n",
    "\n",
    "The AdaBoost algorithm which you will implement is given below:\n",
    "1. Initialize the data weighting coefficients $w_n$ by setting $w_n^{(1)} = 1/N$ for $ n = 1,...,N$ where $N$ is the number of training examples\n",
    "2. For $m = 1,...,M$ models:\n",
    "    - Fit a classifier $y_m(x)$ to a subset of the training data by minimising the weighted error function (hint: specify the `sample_weight` when fitting the model using scikit-learn).\n",
    "    - Calculate the weighted error, $\\epsilon_m$, where $$\\epsilon_m = 1 - \\text{weighted_accuracy} = 1 - \\frac{\\sum_{n=1}^N{w_nI(y_m(x_n) = t_n)}}{\\sum_{n=1}^N{w_n}}$$\n",
    "    and $I$ is the indicator function that equals $1$ when the condition is true (hint: the computation for the weighted accuracy is done for you if `sample_weight` is specified when calling the [`score`](https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree.DecisionTreeClassifier.score) function).\n",
    "    - Calculate the model weighting coefficients, $\\alpha_m$, where\n",
    "    $$\\alpha_m = ln\\left(\\frac{1-\\epsilon_m}{\\epsilon_m}\\right)$$\n",
    "    - Update the data weighting coefficients\n",
    "    $$w_n^{(m+1)} = w_n^{(m)} exp(\\alpha_m \\space I(y_m(x_n) \\neq t_n))$$ where, again, $I$ is the indicator function.\n",
    "3. The final prediction is a weighted combination of the trained base classifiers weighted by $\\alpha_m$.\n",
    "    \n",
    "For more information on boosting, see Bishop section 14.3.\n",
    "\n",
    "### 3.1) Train an ensemble model using the AdaBoost algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_models = 200 # number of base classifiers\n",
    "sample_size = 2000  # sample training set size.\n",
    "np.random.seed(0)\n",
    "\n",
    "# TODO\n",
    "# initialise the sample weights for all data points in the training set.\n",
    "sample_weights = np.ones(X_train.shape[0])/X_train.shape[0]\n",
    "\n",
    "alphas = []\n",
    "all_models = []\n",
    "for m in range(num_models):\n",
    "    # TODO\n",
    "    # copy in your code from the bagging exercise here to sample with replacement from the training set. \n",
    "    # Each sample should contain sample_size data points chosen at random.\n",
    "    # Hint: look at the documentation for numpy.random.choice().\n",
    "    sample_idx = np.random.choice(X_train.shape[0], sample_size)\n",
    "    X_train_sample, y_train_sample = X_train[sample_idx], y_train[sample_idx]\n",
    "\n",
    "    model = DecisionTreeClassifier(max_depth=10)\n",
    "    # TODO\n",
    "    # train a decision tree classifier on the weighted random sample.\n",
    "    # Hint: fit() takes an additional argument, 'sample_weights'.\n",
    "    model.fit(X_train_sample, y_train_sample, sample_weights[sample_idx])\n",
    "    \n",
    "    # TODO\n",
    "    # compute the model error using weighted accuracy for the sampled training dataset\n",
    "    # Hint: score() score takes an additional argument, 'sample_weight'.\n",
    "    error = 1-model.score(X_train_sample, y_train_sample, sample_weights[sample_idx])\n",
    "\n",
    "    # TODO\n",
    "    # calculate alpha for the model and append alpha to alphas\n",
    "    alpha = np.log((1-error)/error)\n",
    "    alphas.append(alpha)\n",
    "    \n",
    "    # TODO\n",
    "    # update the sample_weights for incorrect predictions using alpha\n",
    "    incorrect_preds = model.predict(X_train_sample) != y_train_sample\n",
    "    sample_weights[sample_idx] *= np.exp(alpha*incorrect_preds)\n",
    "    \n",
    "    all_models.append(model)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2) Adaboost prediction\n",
    "Complete the `boosting_predict` function to produce predictions from the trained models. In addition to the test data and the trained models, the function also takes the list of $\\alpha_m$ as an input which determines the weighting of each individual model on the overall output."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def boosting_predict(test_data, all_models, alphas):\n",
    "    votes = np.zeros((test_data.shape[0], len(all_models))) \n",
    "    combined_predictions = np.zeros(test_data.shape[0])\n",
    "\n",
    "    for idx, m in enumerate(all_models):\n",
    "        # TODO\n",
    "        # write your code here to obtain the predictions from model m and store it in votes.\n",
    "        votes[:, idx] = m.predict(test_data)  \n",
    "        \n",
    "    \n",
    "    for test_point in range(len(votes)):\n",
    "        # TODO\n",
    "        # determine the class with the most votes for each test point and store it in combined_predictions\n",
    "        # hint: remember the weighting alpha\n",
    "        combined_predictions[test_point] = np.bincount(np.int64(votes[test_point]), alphas).argmax()\n",
    "    \n",
    "    return combined_predictions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prediction = boosting_predict(X_test, all_models, alphas)\n",
    "accuracy = np.count_nonzero(prediction==np.int64(y_test))/y_test.shape[0]\n",
    "print(\"Test set accuracy: {}\".format(accuracy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How does performance compare with the other approaches?\n",
    "\n",
    "Try out different values of `sample_size`, `num_models` and `max_depth` of the decision tree.\n",
    "\n",
    "How does training time vary for each approach as you change these ensemble parameters? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Wrap up\n",
    "\n",
    "We then implemented bagging, then extended it to the Random Forest and Boosting methods. This should give some idea of how these three key ensemble methods are related to one another. Random Forest adds random sampling over features, while boosting re-weights the dataset at each iteration to focus on misclassified data points.\n",
    "\n",
    "### References\n",
    "- COMS30035 Machine Learning lecture notes.\n",
    "- Bishop Pattern Recognition and Machine Learning: Chapter 14.\n",
    "\n",
    "#### Materials used to create the lab\n",
    "- https://github.com/TrainingByPackt/Applied-Supervised-Learning-with-Python/blob/master/Chapter%204%20-%20Classification/Exercise%2042%20-%20Iris%20Classification%20Using%20a%20CART%20Decision%20Tree.ipynb\n",
    "- https://plsms.github.io/kaggle/learn/2%20Machine%20Learning/Level%201/11%20Exercise;%20Random%20Forests.html\n",
    "- https://towardsdatascience.com/how-to-visualize-a-decision-tree-from-a-random-forest-in-python-using-scikit-learn-38ad2d75f21c\n",
    "- https://www.kaggle.com/jmohitj/practicing-playing-with-mnist-decision-tree\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}