{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## April 6 - More Learning - Ensemble and Adaboost\n", "\n", "Mostly chapter 18 and 20 from AIMA" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from learning import *\n", "from notebook import *" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## ENSEMBLE LEARNER\n", "\n", "### Overview\n", "\n", "Ensemble Learning improves the performance of our model by combining several learners. It improves the stability and predictive power of the model. Ensemble methods are meta-algorithms that combine several machine learning techniques into one predictive model in order to decrease variance, bias, or improve predictions. \n", "\n", "\n", "\n", "![ensemble_learner.jpg](images/ensemble_learner.jpg)\n", "\n", "\n", "Some commonly used Ensemble Learning techniques are : \n", "\n", "1. Bagging : Bagging tries to implement similar learners on small sample populations and then takes a mean of all the predictions. It helps us to reduce variance error.\n", "\n", "2. Boosting : Boosting is an iterative technique which adjusts the weight of an observation based on the last classification. If an observation was classified incorrectly, it tries to increase the weight of this observation and vice versa. It helps us to reduce bias error.\n", "\n", "3. Stacking : This is a very interesting way of combining models. Here we use a learner to combine output from different learners. It can either decrease bias or variance error depending on the learners we use.\n", "\n", "### Implementation\n", "\n", "Below mentioned is the implementation of Ensemble Learner." ] }, { "cell_type": "code", "execution_count": 225, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "

def EnsembleLearner(learners):\n",
       "    """Given a list of learning algorithms, have them vote."""\n",
       "    def train(dataset):\n",
       "        predictors = [learner(dataset) for learner in learners]\n",
       "\n",
       "        def predict(example):\n",
       "            return mode(predictor(example) for predictor in predictors)\n",
       "        return predict\n",
       "    return train\n",
       "

\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(EnsembleLearner)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This algorithm takes input as a list of learning algorithms, have them vote and then finally returns the predicted result." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## LEARNER EVALUATION\n", "\n", "In this section we will evaluate and compare algorithm performance. The dataset we will use will again be the iris one." ] }, { "cell_type": "code", "execution_count": 226, "metadata": {}, "outputs": [], "source": [ "iris = DataSet(name=\"iris\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Naive Bayes\n", "\n", "First up we have the Naive Bayes algorithm. First we will test how well the Discrete Naive Bayes works, and then how the Continuous fares." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Error ratio for Discrete: 0.033333333333333326\n", "Error ratio for Continuous: 0.040000000000000036\n" ] } ], "source": [ "nBD = NaiveBayesLearner(iris, continuous=False)\n", "print(\"Error ratio for Discrete:\", err_ratio(nBD, iris))\n", "\n", "nBC = NaiveBayesLearner(iris, continuous=True)\n", "print(\"Error ratio for Continuous:\", err_ratio(nBC, iris))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The error for the Naive Bayes algorithm is very, very low; close to 0. There is also very little difference between the discrete and continuous version of the algorithm." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## k-Nearest Neighbors\n", "\n", "Now we will take a look at kNN, for different values of k. Note that k should have odd values, to break any ties between two classes." ] }, { "cell_type": "code", "execution_count": 228, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Error ratio for k=1: 0.0\n", "Error ratio for k=3: 0.06000000000000005\n", "Error ratio for k=5: 0.1266666666666667\n", "Error ratio for k=7: 0.19999999999999996\n" ] } ], "source": [ "kNN_1 = NearestNeighborLearner(iris, k=1)\n", "kNN_3 = NearestNeighborLearner(iris, k=3)\n", "kNN_5 = NearestNeighborLearner(iris, k=5)\n", "kNN_7 = NearestNeighborLearner(iris, k=7)\n", "\n", "print(\"Error ratio for k=1:\", err_ratio(kNN_1, iris))\n", "print(\"Error ratio for k=3:\", err_ratio(kNN_3, iris))\n", "print(\"Error ratio for k=5:\", err_ratio(kNN_5, iris))\n", "print(\"Error ratio for k=7:\", err_ratio(kNN_7, iris))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notice how the error became larger and larger as k increased. This is generally the case with datasets where classes are spaced out, as is the case with the iris dataset. If items from different classes were closer together, classification would be more difficult. Usually a value of 1, 3 or 5 for *k* suffices.\n", "\n", "Also note that since the training set is also the testing set, for *k* equal to 1 we get a perfect score, since the item we want to classify each time is already in the dataset and its closest neighbor is itself." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Perceptron\n", "\n", "For the Perceptron, we first need to convert class names to integers. Let's see how it performs in the dataset." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Error ratio for Perceptron: 0.31333333333333335\n" ] } ], "source": [ "iris2 = DataSet(name=\"iris\")\n", "iris2.classes_to_numbers()\n", "\n", "perceptron = PerceptronLearner(iris2)\n", "print(\"Error ratio for Perceptron:\", err_ratio(perceptron, iris2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Perceptron didn't fare very well mainly because the dataset is not linearly separated. On simpler datasets the algorithm performs much better, but unfortunately such datasets are rare in real life scenarios." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## AdaBoost\n", "\n", "### Overview\n", "\n", "**AdaBoost** is an algorithm which uses **ensemble learning**. In ensemble learning the hypotheses in the collection, or ensemble, vote for what the output should be and the output with the majority votes is selected as the final answer.\n", "\n", "AdaBoost algorithm, as mentioned in the book, works with a **weighted training set** and **weak learners** (classifiers that have about 50%+epsilon accuracy i.e slightly better than random guessing). It manipulates the weights attached to the examples that are shown to it. Importance is given to the examples with higher weights.\n", "\n", "

\n", "One way to think about this is that you have more to learn from your mistakes than\n", "from your success. If you predict X and are correct, you have nothing to learn.\n", "\n", "
\n", "If you predict X and are wrong, you made a mistake. You need to update your model. You have something to learn.\n", " \n", "In the cognitive science world, this is known as failure-driven learning.\n", "It is a powerful notion.\n", "\n", "Think about it. How do you know that you have something to learn? You make a \n", "mistake. You expected one outcome and something else happened.\n", "\n", "Actually, you do not need to make a mistake. Suppose you try something and expect\n", "to fail. If you actually succeed, you still have something to learn because \n", "you had an **expectation failure**.\n", " \n", "

\n", "\n", "All the examples start with equal weights and a hypothesis is generated using these examples. Examples which are incorrectly classified, their weights are increased so that they can be classified correctly by the next hypothesis. The examples that are correctly classified, their weights are reduced. This process is repeated K times (here K is an input to the algorithm) and hence, K hypotheses are generated.\n", "\n", "These K hypotheses are also assigned weights according to their performance on the weighted training set. The final ensemble hypothesis is the weighted-majority combination of these K hypotheses.\n", "\n", "The speciality of AdaBoost is that by using weak learners and a sufficiently large *K*, a highly accurate classifier can be learned irrespective of the complexity of the function being learned or the dullness of the hypothesis space.\n", "\n", "### Implementation\n", "\n", "As seen in the previous section, the `PerceptronLearner` does not perform that well on the iris dataset. We'll use perceptron as the learner for the AdaBoost algorithm and try to increase the accuracy. \n", "\n", "Let's first see what AdaBoost is exactly:" ] }, { "cell_type": "code", "execution_count": 230, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "

def AdaBoost(L, K):\n",
       "    """[Figure 18.34]"""\n",
       "\n",
       "    def train(dataset):\n",
       "        examples, target = dataset.examples, dataset.target\n",
       "        N = len(examples)\n",
       "        epsilon = 1/(2*N)\n",
       "        w = [1/N]*N\n",
       "        h, z = [], []\n",
       "        for k in range(K):\n",
       "            h_k = L(dataset, w)\n",
       "            h.append(h_k)\n",
       "            error = sum(weight for example, weight in zip(examples, w)\n",
       "                        if example[target] != h_k(example))\n",
       "\n",
       "            # Avoid divide-by-0 from either 0% or 100% error rates:\n",
       "            error = clip(error, epsilon, 1 - epsilon)\n",
       "            for j, example in enumerate(examples):\n",
       "                if example[target] == h_k(example):\n",
       "                    w[j] *= error/(1 - error)\n",
       "            w = normalize(w)\n",
       "            z.append(math.log((1 - error)/error))\n",
       "        return WeightedMajority(h, z)\n",
       "    return train\n",
       "

\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(AdaBoost)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "AdaBoost takes as inputs: L and K where L is the learner and K is the number of hypotheses to be generated. The learner L takes in as inputs: a dataset and the weights associated with the examples in the dataset. But the `PerceptronLearner` does not handle weights and only takes a dataset as its input. \n", "To remedy that we will give as input to the PerceptronLearner a modified dataset in which the examples will be repeated according to the weights associated to them. Intuitively, what this will do is force the learner to repeatedly learn the same example again and again until it can classify it correctly. \n", "\n", "To convert `PerceptronLearner` so that it can take weights as input too, we will have to pass it through the **`WeightedLearner`** function." ] }, { "cell_type": "code", "execution_count": 175, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "

def WeightedLearner(unweighted_learner):\n",
       "    """Given a learner that takes just an unweighted dataset, return\n",
       "    one that takes also a weight for each example. [p. 749 footnote 14]"""\n",
       "    def train(dataset, weights):\n",
       "        return unweighted_learner(replicated_dataset(dataset, weights))\n",
       "    return train\n",
       "

\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(WeightedLearner)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The `WeightedLearner` function will then call the `PerceptronLearner`, during each iteration, with the modified dataset which contains the examples according to the weights associated with them.\n", "\n", "### Example\n", "\n", "We will pass the `PerceptronLearner` through `WeightedLearner` function. Then we will create an `AdaboostLearner` classifier with number of hypotheses or *K* equal to 5." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "WeightedPerceptron = WeightedLearner(PerceptronLearner)\n", "AdaboostLearner = AdaBoost(WeightedPerceptron, 5)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "iris2 = DataSet(name=\"iris\")\n", "iris2.classes_to_numbers()\n", "\n", "adaboost = AdaboostLearner(iris2)\n", "\n", "adaboost([5, 3, 1, 0.1])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "That is the correct answer. Let's check the error rate of adaboost with perceptron." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Error ratio for adaboost: 0.040000000000000036\n" ] } ], "source": [ "print(\"Error ratio for adaboost: \", err_ratio(adaboost, iris2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It reduced the error rate considerably. Unlike the `PerceptronLearner`, `AdaBoost` was able to learn the complexity in the iris dataset." ] }, { "cell_type": "code", "execution_count": 179, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "

def err_ratio(predict, dataset, examples=None, verbose=0):\n",
       "    """Return the proportion of the examples that are NOT correctly predicted.\n",
       "    verbose - 0: No output; 1: Output wrong; 2 (or greater): Output correct"""\n",
       "    examples = examples or dataset.examples\n",
       "    if len(examples) == 0:\n",
       "        return 0.0\n",
       "    right = 0\n",
       "    for example in examples:\n",
       "        desired = example[dataset.target]\n",
       "        output = predict(dataset.sanitize(example))\n",
       "        if output == desired:\n",
       "            right += 1\n",
       "            if verbose >= 2:\n",
       "                print('   OK: got {} for {}'.format(desired, example))\n",
       "        elif verbose:\n",
       "            print('WRONG: got {}, expected {} for {}'.format(\n",
       "                output, desired, example))\n",
       "    return 1 - (right/len(examples))\n",
       "

\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(err_ratio)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "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.6" } }, "nbformat": 4, "nbformat_minor": 2 }