{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## April 3 - More Learning - Statistics and Naive Bayes\n", "\n", "Mostly chapter 18 and 20 from AIMA" ] }, { "cell_type": "code", "execution_count": 235, "metadata": {}, "outputs": [], "source": [ "from learning import *\n", "from notebook import *" ] }, { "cell_type": "code", "execution_count": 236, "metadata": {}, "outputs": [], "source": [ "iris = DataSet(name=\"iris\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## NAIVE BAYES LEARNER\n", "\n", "### Overview\n", "\n", "#### Theory of Probabilities\n", "\n", "The Naive Bayes algorithm is a probabilistic classifier, making use of [Bayes' Theorem](https://en.wikipedia.org/wiki/Bayes%27_theorem). The theorem states that the conditional probability of A given B equals the conditional probability of B given A multiplied by the probability of A, divided by the probability of B.\n", "\n", "$$P(A|B) = \\dfrac{P(B|A)*P(A)}{P(B)}$$\n", "\n", "From the theory of Probabilities we have the Multiplication Rule, if the events *X* are independent the following is true:\n", "\n", "$$P(X_{1} \\cap X_{2} \\cap ... \\cap X_{n}) = P(X_{1})*P(X_{2})*...*P(X_{n})$$\n", "\n", "For conditional probabilities this becomes:\n", "\n", "$$P(X_{1}, X_{2}, ..., X_{n}|Y) = P(X_{1}|Y)*P(X_{2}|Y)*...*P(X_{n}|Y)$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Classifying an Item\n", "\n", "How can we use the above to classify an item though?\n", "\n", "We have a dataset with a set of classes (C) and we want to classify an item with a set of features (F). Essentially what we want to do is predict the class of an item given the features.\n", "\n", "For a specific class, Class, we will find the conditional probability given the item features:\n", "\n", "$$P(Class|F) = \\dfrac{P(F|Class)*P(Class)}{P(F)}$$\n", "\n", "We will do this for every class and we will pick the maximum. This will be the class the item is classified in.\n", "\n", "The features though are a vector with many elements. We need to break the probabilities up using the multiplication rule. Thus the above equation becomes:\n", "\n", "$$P(Class|F) = \\dfrac{P(Class)*P(F_{1}|Class)*P(F_{2}|Class)*...*P(F_{n}|Class)}{P(F_{1})*P(F_{2})*...*P(F_{n})}$$\n", "\n", "The calculation of the conditional probability then depends on the calculation of the following:\n", "\n", "*a)* The probability of Class in the dataset.\n", "\n", "*b)* The conditional probability of each feature occurring in an item classified in Class.\n", "\n", "*c)* The probabilities of each individual feature.\n", "\n", "For *a)*, we will count how many times Class occurs in the dataset (aka how many items are classified in a particular class).\n", "\n", "For *b)*, if the feature values are discrete ('Blue', '3', 'Tall', etc.), we will count how many times a feature value occurs in items of each class. If the feature values are not discrete, we will go a different route. We will use a distribution function to calculate the probability of values for a given class and feature. If we know the distribution function of the dataset, then great, we will use it to compute the probabilities. If we don't know the function, we can assume the dataset follows the normal (Gaussian) distribution without much loss of accuracy. In fact, it can be proven that any distribution tends to the Gaussian the larger the population gets (see [Central Limit Theorem](https://en.wikipedia.org/wiki/Central_limit_theorem)).\n", "\n", "*NOTE:* If the values are continuous but use the discrete approach, there might be issues if we are not lucky. For one, if we have two values, '5.0 and 5.1', with the discrete approach they will be two completely different values, despite being so close. Second, if we are trying to classify an item with a feature value of '5.15', if the value does not appear for the feature, its probability will be 0. This might lead to misclassification. Generally, the continuous approach is more accurate and more useful, despite the overhead of calculating the distribution function.\n", "\n", "The last one, *c)*, is tricky. If feature values are discrete, we can count how many times they occur in the dataset. But what if the feature values are continuous? Imagine a dataset with a height feature. Is it worth it to count how many times each value occurs? Most of the time it is not, since there can be miscellaneous differences in the values (for example, 1.7 meters and 1.700001 meters are practically equal, but they count as different values).\n", "\n", "So as we cannot calculate the feature value probabilities, what are we going to do?\n", "\n", "Let's take a step back and rethink exactly what we are doing. We are essentially comparing conditional probabilities of all the classes. For two classes, A and B, we want to know which one is greater:\n", "\n", "$$\\dfrac{P(F|A)*P(A)}{P(F)} vs. \\dfrac{P(F|B)*P(B)}{P(F)}$$\n", "\n", "Wait, P(F) is the same for both the classes! In fact, it is the same for every combination of classes. That is because P(F) does not depend on a class, thus being independent of the classes.\n", "\n", "So, for *c)*, we actually don't need to calculate it at all." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Wrapping It Up\n", "\n", "Classifying an item to a class then becomes a matter of calculating the conditional probabilities of feature values and the probabilities of classes. This is something very desirable and computationally delicious.\n", "\n", "Remember though that all the above are true because we made the assumption that the features are independent. In most real-world cases that is not true though. Is that an issue here? Fret not, for the the algorithm is very efficient even with that assumption. That is why the algorithm is called **Naive** Bayes Classifier. We (naively) assume that the features are independent to make computations easier." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Implementation\n", "\n", "The implementation of the Naive Bayes Classifier is split in two; *Learning* and *Simple*. The *learning* classifier takes as input a dataset and learns the needed distributions from that. It is itself split into two, for discrete and continuous features. The *simple* classifier takes as input not a dataset, but already calculated distributions (a dictionary of `CountingProbDist` objects)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Discrete\n", "\n", "The implementation for discrete values counts how many times each feature value occurs for each class, and how many times each class occurs. The results are stored in a `CountinProbDist` object." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "With the below code you can see the probabilities of the class \"Setosa\" appearing in the dataset and the probability of the first feature (at index 0) of the same class having a value of 5. Notice that the second probability is relatively small, even though if we observe the dataset we will find that a lot of values are around 5. The issue arises because the features in the Iris dataset are continuous, and we are assuming they are discrete. If the features were discrete (for example, \"Tall\", \"3\", etc.) this probably wouldn't have been the case and we would see a much nicer probability distribution." ] }, { "cell_type": "code", "execution_count": 237, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
class CountingProbDist:\n",
       "    """A probability distribution formed by observing and counting examples.\n",
       "    If p is an instance of this class and o is an observed value, then\n",
       "    there are 3 main operations:\n",
       "    p.add(o) increments the count for observation o by 1.\n",
       "    p.sample() returns a random element from the distribution.\n",
       "    p[o] returns the probability for o (as in a regular ProbDist)."""\n",
       "\n",
       "    def __init__(self, observations=None, default=0):\n",
       "        """Create a distribution, and optionally add in some observations.\n",
       "        By default this is an unsmoothed distribution, but saying default=1,\n",
       "        for example, gives you add-one smoothing."""\n",
       "        if observations is None:\n",
       "            observations = []\n",
       "        self.dictionary = {}\n",
       "        self.n_obs = 0\n",
       "        self.default = default\n",
       "        self.sampler = None\n",
       "\n",
       "        for o in observations:\n",
       "            self.add(o)\n",
       "\n",
       "    def add(self, o):\n",
       "        """Add an observation o to the distribution."""\n",
       "        self.smooth_for(o)\n",
       "        self.dictionary[o] += 1\n",
       "        self.n_obs += 1\n",
       "        self.sampler = None\n",
       "\n",
       "    def smooth_for(self, o):\n",
       "        """Include o among the possible observations, whether or not\n",
       "        it's been observed yet."""\n",
       "        if o not in self.dictionary:\n",
       "            self.dictionary[o] = self.default\n",
       "            self.n_obs += self.default\n",
       "            self.sampler = None\n",
       "\n",
       "    def __getitem__(self, item):\n",
       "        """Return an estimate of the probability of item."""\n",
       "        self.smooth_for(item)\n",
       "        return self.dictionary[item] / self.n_obs\n",
       "\n",
       "    # (top() and sample() are not used in this module, but elsewhere.)\n",
       "\n",
       "    def top(self, n):\n",
       "        """Return (count, obs) tuples for the n most frequent observations."""\n",
       "        return heapq.nlargest(n, [(v, k) for (k, v) in self.dictionary.items()])\n",
       "\n",
       "    def sample(self):\n",
       "        """Return a random sample from the distribution."""\n",
       "        if self.sampler is None:\n",
       "            self.sampler = weighted_sampler(list(self.dictionary.keys()),\n",
       "                                            list(self.dictionary.values()))\n",
       "        return self.sampler()\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(CountingProbDist)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Statistical Learning\n", "\n", "Chapter 20, page 802\n", "\n", "We briefly digress from the iris dataset.\n", "\n", "There are five types of bags of candies. Each bag has 100 pieces, individually wrapped. One bag has all cherry (yum).\n", "One bag has all lime (yuck). The wrapping paper is identical and opaque.\n", "\n", "Three other bags have a mixture: (75 cherry, 25 lime), (50 each), (25 cherry, 75 lime).\n", "\n", "The bags themselves are not evenly distributed. 10% are all cherry and 10% are all lime. 40% are 50/50, and 20% are either 25% lime or 25% cherry.\n", "\n", "If I give you a bag at random, you can randomly sample one candy at a time (and then rewrap it put it back in the bag).\n", "\n", "You pick a random bag and start sampling. If you select one lime candy, what is the most likely bag? What if you pick two in row? Three in row? Four in a row?\n", "\n", "We can use the CountingProbDist() to model this problem." ] }, { "cell_type": "code", "execution_count": 238, "metadata": {}, "outputs": [], "source": [ "h1 = CountingProbDist('c'*100)\n", "h2 = CountingProbDist('c'*75+'l'*25)\n", "h3 = CountingProbDist('c'*50+'l'*50)\n", "h4 = CountingProbDist('c'*25+'l'*75)\n", "h5 = CountingProbDist('l'*100)\n", "dist = {('h1', 0.1): h1, ('h2', 0.2): h2, ('h3', 0.4): h3, \n", " ('h4', 0.2): h4, ('h5', 0.1): h5}\n", "nBS = NaiveBayesLearner(dist, simple=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The NaiveBayesLearner is actually three functions. Here we are using the simple one." ] }, { "cell_type": "code", "execution_count": 239, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc'" ] }, "execution_count": 239, "metadata": {}, "output_type": "execute_result" } ], "source": [ "'c'*100" ] }, { "cell_type": "code", "execution_count": 240, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'c': 75, 'l': 25}" ] }, "execution_count": 240, "metadata": {}, "output_type": "execute_result" } ], "source": [ "h2.dictionary" ] }, { "cell_type": "code", "execution_count": 241, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
def NaiveBayesLearner(dataset, continuous=True, simple=False):\n",
       "    if simple:\n",
       "        return NaiveBayesSimple(dataset)\n",
       "    if continuous:\n",
       "        return NaiveBayesContinuous(dataset)\n",
       "    else:\n",
       "        return NaiveBayesDiscrete(dataset)\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(NaiveBayesLearner)" ] }, { "cell_type": "code", "execution_count": 242, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['__class__',\n", " '__delattr__',\n", " '__dict__',\n", " '__dir__',\n", " '__doc__',\n", " '__eq__',\n", " '__format__',\n", " '__ge__',\n", " '__getattribute__',\n", " '__getitem__',\n", " '__gt__',\n", " '__hash__',\n", " '__init__',\n", " '__init_subclass__',\n", " '__le__',\n", " '__lt__',\n", " '__module__',\n", " '__ne__',\n", " '__new__',\n", " '__reduce__',\n", " '__reduce_ex__',\n", " '__repr__',\n", " '__setattr__',\n", " '__sizeof__',\n", " '__str__',\n", " '__subclasshook__',\n", " '__weakref__',\n", " 'add',\n", " 'default',\n", " 'dictionary',\n", " 'n_obs',\n", " 'sample',\n", " 'sampler',\n", " 'smooth_for',\n", " 'top']" ] }, "execution_count": 242, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dir(h1)" ] }, { "cell_type": "code", "execution_count": 243, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'c': 100}" ] }, "execution_count": 243, "metadata": {}, "output_type": "execute_result" } ], "source": [ "h1.dictionary" ] }, { "cell_type": "code", "execution_count": 244, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'c'" ] }, "execution_count": 244, "metadata": {}, "output_type": "execute_result" } ], "source": [ "h1.sample()" ] }, { "cell_type": "code", "execution_count": 245, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'c': 50, 'l': 50}" ] }, "execution_count": 245, "metadata": {}, "output_type": "execute_result" } ], "source": [ "h3.dictionary" ] }, { "cell_type": "code", "execution_count": 246, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'c'" ] }, "execution_count": 246, "metadata": {}, "output_type": "execute_result" } ], "source": [ "h3.sample()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can practice our $\\LaTeX{}$\n", "\n", "$ h1: 100\\%$ cherry\n", "\n", "$ h2: 75\\%$ cherry $+ 25\\%$ lime,\n", "\n", "$ h3: 50\\%$ cherry $+ 50\\%$ lime,\n", "\n", "$ h4: 25\\%$ cherry $+ 75\\%$ lime,\n", "\n", "$ h5: 100\\%$ lime.\n", "\n", "$$P(h1) = 10\\%$$\n", "$$P(h2) = 20\\%$$\n", "$$P(h3) = 40\\%$$\n", "$$P(h4) = 20\\%$$\n", "$$P(h5) = 10\\%$$\n", "\n", "$$P(h_{i}|lime) = \\alpha{}P(lime|h_{i}) P(h_{i}) $$\n", "\n", "**Bayesian learning** simply calculates the probability of each hypothesis, given the data, and makes predictions on that basis.\n", "\n", "So, if we pick a random bag of candy and draw a lime flavored treat, we can calculate which bag is most likely.\n", "\n", "$$P(h_{1}|lime) = \\alpha{}P(lime|h_{1}) P(h_{1}) = 0 * .1 = 0 $$\n", "$$P(h_{2}|lime) = \\alpha{}P(lime|h_{2}) P(h_{2}) = .25 * .2 = .125 $$\n", "$$P(h_{3}|lime) = \\alpha{}P(lime|h_{3}) P(h_{3}) = .5 * .4 = .2 $$\n", "$$P(h_{4}|lime) = \\alpha{}P(lime|h_{4}) P(h_{4}) = .25 * .2 = .125 $$\n", "$$P(h_{5}|lime) = \\alpha{}P(lime|h_{5}) P(h_{5}) = 1 * .1 = .1$$\n", "\n", "Thus, the most likely hypothesis is $h_3$ at 20%." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "See Figure 20.1 on page 804" ] }, { "cell_type": "code", "execution_count": 247, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "h3\n", "h4\n", "h5\n", "h5\n" ] } ], "source": [ "print (nBS('l'))\n", "print (nBS('ll'))\n", "print (nBS('lll'))\n", "print (nBS('llll'))" ] }, { "cell_type": "code", "execution_count": 248, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
def NaiveBayesSimple(distribution):\n",
       "    """A simple naive bayes classifier that takes as input a dictionary of\n",
       "    CountingProbDist objects and classifies items according to these distributions.\n",
       "    The input dictionary is in the following form:\n",
       "        (ClassName, ClassProb): CountingProbDist"""\n",
       "    target_dist = {c_name: prob for c_name, prob in distribution.keys()}\n",
       "    attr_dists = {c_name: count_prob for (c_name, _), count_prob in distribution.items()}\n",
       "\n",
       "    def predict(example):\n",
       "        """Predict the target value for example. Calculate probabilities for each\n",
       "        class and pick the max."""\n",
       "        def class_probability(targetval):\n",
       "            attr_dist = attr_dists[targetval]\n",
       "            return target_dist[targetval] * product(attr_dist[a] for a in example)\n",
       "\n",
       "        return argmax(target_dist.keys(), key=class_probability)\n",
       "\n",
       "    return predict\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(NaiveBayesSimple)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we will disect the code. The point is there is no magic. We are just performing vanilla probability calculations." ] }, { "cell_type": "code", "execution_count": 249, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'h1': 0.1, 'h2': 0.2, 'h3': 0.4, 'h4': 0.2, 'h5': 0.1}" ] }, "execution_count": 249, "metadata": {}, "output_type": "execute_result" } ], "source": [ "target_dist = {c_name: prob for c_name, prob in dist.keys()}\n", "target_dist" ] }, { "cell_type": "code", "execution_count": 250, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'h1': ,\n", " 'h2': ,\n", " 'h3': ,\n", " 'h4': ,\n", " 'h5': }" ] }, "execution_count": 250, "metadata": {}, "output_type": "execute_result" } ], "source": [ "attr_dists = {c_name: count_prob for (c_name, _), count_prob in dist.items()}\n", "attr_dists" ] }, { "cell_type": "code", "execution_count": 251, "metadata": {}, "outputs": [], "source": [ "def class_probability(targetval):\n", " attr_dist = attr_dists[targetval]\n", " return target_dist[targetval] * product(attr_dist[a] for a in example)" ] }, { "cell_type": "code", "execution_count": 252, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'h4'" ] }, "execution_count": 252, "metadata": {}, "output_type": "execute_result" } ], "source": [ "example = 'll'\n", "argmax(target_dist.keys(), key=class_probability)" ] }, { "cell_type": "code", "execution_count": 255, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0.0, 0.0125, 0.1, 0.1125, 0.1]" ] }, "execution_count": 255, "metadata": {}, "output_type": "execute_result" } ], "source": [ "example = 'll'\n", "list(map(class_probability, target_dist.keys()))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Back to the flowers\n", "\n", "It is spring, you know.\n" ] }, { "cell_type": "code", "execution_count": 256, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.3333333333333333\n", "0.10588235294117647\n", "0.011764705882352941\n" ] } ], "source": [ "dataset = iris\n", "\n", "target_vals = dataset.values[dataset.target]\n", "target_dist = CountingProbDist(target_vals)\n", "attr_dists = {(gv, attr): CountingProbDist(dataset.values[attr])\n", " for gv in target_vals\n", " for attr in dataset.inputs}\n", "for example in dataset.examples:\n", " targetval = example[dataset.target]\n", " target_dist.add(targetval)\n", " for attr in dataset.inputs:\n", " attr_dists[targetval, attr].add(example[attr])\n", "\n", "\n", "print(target_dist['setosa'])\n", "print(attr_dists['setosa', 0][5.0])\n", "print(attr_dists['setosa', 0][6.0])" ] }, { "cell_type": "code", "execution_count": 197, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{('virginica', 0): ,\n", " ('virginica', 1): ,\n", " ('virginica', 2): ,\n", " ('virginica', 3): ,\n", " ('versicolor', 0): ,\n", " ('versicolor', 1): ,\n", " ('versicolor', 2): ,\n", " ('versicolor', 3): ,\n", " ('setosa', 0): ,\n", " ('setosa', 1): ,\n", " ('setosa', 2): ,\n", " ('setosa', 3): }" ] }, "execution_count": 197, "metadata": {}, "output_type": "execute_result" } ], "source": [ "attr_dists" ] }, { "cell_type": "code", "execution_count": 198, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 198, "metadata": {}, "output_type": "execute_result" } ], "source": [ "target_dist" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "First we found the different values for the classes (called targets here) and calculated their distribution. Next we initialized a dictionary of `CountingProbDist` objects, one for each class and feature. Finally, we iterated through the examples in the dataset and calculated the needed probabilites.\n", "\n", "Having calculated the different probabilities, we will move on to the predicting function. It will receive as input an item and output the most likely class. Using the above formula, it will multiply the probability of the class appearing, with the probability of each feature value appearing in the class. It will return the max result." ] }, { "cell_type": "code", "execution_count": 257, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "setosa\n" ] } ], "source": [ "def predict(example):\n", " def class_probability(targetval):\n", " return (target_dist[targetval] *\n", " product(attr_dists[targetval, attr][example[attr]]\n", " for attr in dataset.inputs))\n", " return argmax(target_vals, key=class_probability)\n", "\n", "\n", "print(predict([5, 3, 1, 0.1]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can view the complete code by executing the next line, which combines the above code:" ] }, { "cell_type": "code", "execution_count": 200, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
def NaiveBayesDiscrete(dataset):\n",
       "    """Just count how many times each value of each input attribute\n",
       "    occurs, conditional on the target value. Count the different\n",
       "    target values too."""\n",
       "\n",
       "    target_vals = dataset.values[dataset.target]\n",
       "    target_dist = CountingProbDist(target_vals)\n",
       "    attr_dists = {(gv, attr): CountingProbDist(dataset.values[attr])\n",
       "                  for gv in target_vals\n",
       "                  for attr in dataset.inputs}\n",
       "    for example in dataset.examples:\n",
       "        targetval = example[dataset.target]\n",
       "        target_dist.add(targetval)\n",
       "        for attr in dataset.inputs:\n",
       "            attr_dists[targetval, attr].add(example[attr])\n",
       "\n",
       "    def predict(example):\n",
       "        """Predict the target value for example. Consider each possible value,\n",
       "        and pick the most likely by looking at each attribute independently."""\n",
       "        def class_probability(targetval):\n",
       "            return (target_dist[targetval] *\n",
       "                    product(attr_dists[targetval, attr][example[attr]]\n",
       "                            for attr in dataset.inputs))\n",
       "        return argmax(target_vals, key=class_probability)\n",
       "\n",
       "    return predict\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(NaiveBayesDiscrete)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Continuous\n", "\n", "In the implementation we use the Gaussian/Normal distribution function. To make it work, we need to find the means and standard deviations of features for each class. We make use of the `find_means_and_deviations` Dataset method. On top of that, we will also calculate the class probabilities as we did with the Discrete approach." ] }, { "cell_type": "code", "execution_count": 201, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
class DataSet:\n",
       "    """A data set for a machine learning problem. It has the following fields:\n",
       "\n",
       "    d.examples   A list of examples. Each one is a list of attribute values.\n",
       "    d.attrs      A list of integers to index into an example, so example[attr]\n",
       "                 gives a value. Normally the same as range(len(d.examples[0])).\n",
       "    d.attrnames  Optional list of mnemonic names for corresponding attrs.\n",
       "    d.target     The attribute that a learning algorithm will try to predict.\n",
       "                 By default the final attribute.\n",
       "    d.inputs     The list of attrs without the target.\n",
       "    d.values     A list of lists: each sublist is the set of possible\n",
       "                 values for the corresponding attribute. If initially None,\n",
       "                 it is computed from the known examples by self.setproblem.\n",
       "                 If not None, an erroneous value raises ValueError.\n",
       "    d.distance   A function from a pair of examples to a nonnegative number.\n",
       "                 Should be symmetric, etc. Defaults to mean_boolean_error\n",
       "                 since that can handle any field types.\n",
       "    d.name       Name of the data set (for output display only).\n",
       "    d.source     URL or other source where the data came from.\n",
       "    d.exclude    A list of attribute indexes to exclude from d.inputs. Elements\n",
       "                 of this list can either be integers (attrs) or attrnames.\n",
       "\n",
       "    Normally, you call the constructor and you're done; then you just\n",
       "    access fields like d.examples and d.target and d.inputs."""\n",
       "\n",
       "    def __init__(self, examples=None, attrs=None, attrnames=None, target=-1,\n",
       "                 inputs=None, values=None, distance=mean_boolean_error,\n",
       "                 name='', source='', exclude=()):\n",
       "        """Accepts any of DataSet's fields. Examples can also be a\n",
       "        string or file from which to parse examples using parse_csv.\n",
       "        Optional parameter: exclude, as documented in .setproblem().\n",
       "        >>> DataSet(examples='1, 2, 3')\n",
       "        <DataSet(): 1 examples, 3 attributes>\n",
       "        """\n",
       "        self.name = name\n",
       "        self.source = source\n",
       "        self.values = values\n",
       "        self.distance = distance\n",
       "        self.got_values_flag = bool(values)\n",
       "\n",
       "        # Initialize .examples from string or list or data directory\n",
       "        if isinstance(examples, str):\n",
       "            self.examples = parse_csv(examples)\n",
       "        elif examples is None:\n",
       "            self.examples = parse_csv(open_data(name + '.csv').read())\n",
       "        else:\n",
       "            self.examples = examples\n",
       "\n",
       "        # Attrs are the indices of examples, unless otherwise stated.   \n",
       "        if self.examples is not None and attrs is None:\n",
       "            attrs = list(range(len(self.examples[0])))\n",
       "\n",
       "        self.attrs = attrs\n",
       "\n",
       "        # Initialize .attrnames from string, list, or by default\n",
       "        if isinstance(attrnames, str):\n",
       "            self.attrnames = attrnames.split()\n",
       "        else:\n",
       "            self.attrnames = attrnames or attrs\n",
       "        self.setproblem(target, inputs=inputs, exclude=exclude)\n",
       "\n",
       "    def setproblem(self, target, inputs=None, exclude=()):\n",
       "        """Set (or change) the target and/or inputs.\n",
       "        This way, one DataSet can be used multiple ways. inputs, if specified,\n",
       "        is a list of attributes, or specify exclude as a list of attributes\n",
       "        to not use in inputs. Attributes can be -n .. n, or an attrname.\n",
       "        Also computes the list of possible values, if that wasn't done yet."""\n",
       "        self.target = self.attrnum(target)\n",
       "        exclude = list(map(self.attrnum, exclude))\n",
       "        if inputs:\n",
       "            self.inputs = removeall(self.target, inputs)\n",
       "        else:\n",
       "            self.inputs = [a for a in self.attrs\n",
       "                           if a != self.target and a not in exclude]\n",
       "        if not self.values:\n",
       "            self.update_values()\n",
       "        self.check_me()\n",
       "\n",
       "    def check_me(self):\n",
       "        """Check that my fields make sense."""\n",
       "        assert len(self.attrnames) == len(self.attrs)\n",
       "        assert self.target in self.attrs\n",
       "        assert self.target not in self.inputs\n",
       "        assert set(self.inputs).issubset(set(self.attrs))\n",
       "        if self.got_values_flag:\n",
       "            # only check if values are provided while initializing DataSet\n",
       "            list(map(self.check_example, self.examples))\n",
       "\n",
       "    def add_example(self, example):\n",
       "        """Add an example to the list of examples, checking it first."""\n",
       "        self.check_example(example)\n",
       "        self.examples.append(example)\n",
       "\n",
       "    def check_example(self, example):\n",
       "        """Raise ValueError if example has any invalid values."""\n",
       "        if self.values:\n",
       "            for a in self.attrs:\n",
       "                if example[a] not in self.values[a]:\n",
       "                    raise ValueError('Bad value {} for attribute {} in {}'\n",
       "                                     .format(example[a], self.attrnames[a], example))\n",
       "\n",
       "    def attrnum(self, attr):\n",
       "        """Returns the number used for attr, which can be a name, or -n .. n-1."""\n",
       "        if isinstance(attr, str):\n",
       "            return self.attrnames.index(attr)\n",
       "        elif attr < 0:\n",
       "            return len(self.attrs) + attr\n",
       "        else:\n",
       "            return attr\n",
       "\n",
       "    def update_values(self):\n",
       "        self.values = list(map(unique, zip(*self.examples)))\n",
       "\n",
       "    def sanitize(self, example):\n",
       "        """Return a copy of example, with non-input attributes replaced by None."""\n",
       "        return [attr_i if i in self.inputs else None\n",
       "                for i, attr_i in enumerate(example)]\n",
       "\n",
       "    def classes_to_numbers(self, classes=None):\n",
       "        """Converts class names to numbers."""\n",
       "        if not classes:\n",
       "            # If classes were not given, extract them from values\n",
       "            classes = sorted(self.values[self.target])\n",
       "        for item in self.examples:\n",
       "            item[self.target] = classes.index(item[self.target])\n",
       "\n",
       "    def remove_examples(self, value=''):\n",
       "        """Remove examples that contain given value."""\n",
       "        self.examples = [x for x in self.examples if value not in x]\n",
       "        self.update_values()\n",
       "\n",
       "    def split_values_by_classes(self):\n",
       "        """Split values into buckets according to their class."""\n",
       "        buckets = defaultdict(lambda: [])\n",
       "        target_names = self.values[self.target]\n",
       "\n",
       "        for v in self.examples:\n",
       "            item = [a for a in v if a not in target_names]  # Remove target from item\n",
       "            buckets[v[self.target]].append(item)  # Add item to bucket of its class\n",
       "\n",
       "        return buckets\n",
       "\n",
       "    def find_means_and_deviations(self):\n",
       "        """Finds the means and standard deviations of self.dataset.\n",
       "        means     : A dictionary for each class/target. Holds a list of the means\n",
       "                    of the features for the class.\n",
       "        deviations: A dictionary for each class/target. Holds a list of the sample\n",
       "                    standard deviations of the features for the class."""\n",
       "        target_names = self.values[self.target]\n",
       "        feature_numbers = len(self.inputs)\n",
       "\n",
       "        item_buckets = self.split_values_by_classes()\n",
       "\n",
       "        means = defaultdict(lambda: [0] * feature_numbers)\n",
       "        deviations = defaultdict(lambda: [0] * feature_numbers)\n",
       "\n",
       "        for t in target_names:\n",
       "            # Find all the item feature values for item in class t\n",
       "            features = [[] for i in range(feature_numbers)]\n",
       "            for item in item_buckets[t]:\n",
       "                for i in range(feature_numbers):\n",
       "                    features[i].append(item[i])\n",
       "\n",
       "            # Calculate means and deviations fo the class\n",
       "            for i in range(feature_numbers):\n",
       "                means[t][i] = mean(features[i])\n",
       "                deviations[t][i] = stdev(features[i])\n",
       "\n",
       "        return means, deviations\n",
       "\n",
       "    def __repr__(self):\n",
       "        return '<DataSet({}): {:d} examples, {:d} attributes>'.format(\n",
       "            self.name, len(self.examples), len(self.attrs))\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource (DataSet)" ] }, { "cell_type": "code", "execution_count": 258, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "setosa:\n", "means: [5.006, 3.418, 1.464, 0.244]\n", "deviations: [0.3524896872134513, 0.38102439795469095, 0.17351115943644546, 0.10720950308167838]\n", "versicolor:\n", "means: [5.936, 2.77, 4.26, 1.326]\n", "deviations: [0.5161711470638634, 0.3137983233784114, 0.46991097723995795, 0.19775268000454405]\n" ] } ], "source": [ "means, deviations = dataset.find_means_and_deviations()\n", "\n", "target_vals = dataset.values[dataset.target]\n", "target_dist = CountingProbDist(target_vals)\n", "\n", "print ('setosa:')\n", "print('means: ' + str(means[\"setosa\"]))\n", "print('deviations: ' + str(deviations[\"setosa\"]))\n", "print ('versicolor:')\n", "print('means: ' + str(means[\"versicolor\"]))\n", "print('deviations: ' + str(deviations[\"versicolor\"]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can see the means of the features for the \"Setosa\" class and the deviations for \"Versicolor\".\n", "\n", "The prediction function will work similarly to the Discrete algorithm. It will multiply the probability of the class occurring with the conditional probabilities of the feature values for the class.\n", "\n", "Since we are using the Gaussian distribution, we will input the value for each feature into the Gaussian function, together with the mean and deviation of the feature. This will return the probability of the particular feature value for the given class. We will repeat for each class and pick the max value." ] }, { "cell_type": "code", "execution_count": 259, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "setosa\n" ] } ], "source": [ "def predict(example):\n", " def class_probability(targetval):\n", " prob = target_dist[targetval]\n", " for attr in dataset.inputs:\n", " prob *= gaussian(means[targetval][attr], deviations[targetval][attr], example[attr])\n", " return prob\n", "\n", " return argmax(target_vals, key=class_probability)\n", "\n", "\n", "print(predict([5, 3, 1, 0.1]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The complete code of the continuous algorithm:" ] }, { "cell_type": "code", "execution_count": 204, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
def NaiveBayesContinuous(dataset):\n",
       "    """Count how many times each target value occurs.\n",
       "    Also, find the means and deviations of input attribute values for each target value."""\n",
       "    means, deviations = dataset.find_means_and_deviations()\n",
       "\n",
       "    target_vals = dataset.values[dataset.target]\n",
       "    target_dist = CountingProbDist(target_vals)\n",
       "\n",
       "    def predict(example):\n",
       "        """Predict the target value for example. Consider each possible value,\n",
       "        and pick the most likely by looking at each attribute independently."""\n",
       "        def class_probability(targetval):\n",
       "            prob = target_dist[targetval]\n",
       "            for attr in dataset.inputs:\n",
       "                prob *= gaussian(means[targetval][attr], deviations[targetval][attr], example[attr])\n",
       "            return prob\n",
       "\n",
       "        return argmax(target_vals, key=class_probability)\n",
       "\n",
       "    return predict\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(NaiveBayesContinuous)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Simple\n", "\n", "The simple classifier (chosen with the argument `simple`) does not learn from a dataset, instead it takes as input a dictionary of already calculated `CountingProbDist` objects and returns a predictor function. The dictionary is in the following form: `(Class Name, Class Probability): CountingProbDist Object`.\n", "\n", "Each class has its own probability distribution. The classifier given a list of features calculates the probability of the input for each class and returns the max. The only pre-processing work is to create dictionaries for the distribution of classes (named `targets`) and attributes/features.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This classifier is useful when you already have calculated the distributions and you need to predict future items.\n", "\n", "### Examples\n", "\n", "We will now use the Naive Bayes Classifier (Discrete and Continuous) to classify items:" ] }, { "cell_type": "code", "execution_count": 260, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Discrete Classifier\n", "setosa\n", "virginica\n", "virginica\n", "\n", "Continuous Classifier\n", "setosa\n", "versicolor\n", "virginica\n" ] } ], "source": [ "nBD = NaiveBayesLearner(iris, continuous=False)\n", "print(\"Discrete Classifier\")\n", "print(nBD([5, 3, 1, 0.1]))\n", "print(nBD([6, 5, 3, 1.5]))\n", "print(nBD([7, 3, 6.5, 2]))\n", "\n", "\n", "nBC = NaiveBayesLearner(iris, continuous=True)\n", "print(\"\\nContinuous Classifier\")\n", "print(nBC([5, 3, 1, 0.1]))\n", "print(nBC([6, 5, 3, 1.5]))\n", "print(nBC([7, 3, 6.5, 2]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notice how the Discrete Classifier misclassified the second item, while the Continuous one had no problem.\n", "\n", "Let's now take a look at the simple classifier. First we will come up with a sample problem to solve. Say we are given three bags. Each bag contains three letters ('a', 'b' and 'c') of different quantities. We are given a string of letters and we are tasked with finding from which bag the string of letters came.\n", "\n", "Since we know the probability distribution of the letters for each bag, we can use the naive bayes classifier to make our prediction." ] }, { "cell_type": "code", "execution_count": 261, "metadata": {}, "outputs": [], "source": [ "bag1 = 'a'*50 + 'b'*30 + 'c'*15\n", "dist1 = CountingProbDist(bag1)\n", "bag2 = 'a'*30 + 'b'*45 + 'c'*20\n", "dist2 = CountingProbDist(bag2)\n", "bag3 = 'a'*20 + 'b'*20 + 'c'*35\n", "dist3 = CountingProbDist(bag3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now that we have the `CountingProbDist` objects for each bag/class, we will create the dictionary. We assume that it is equally probable that we will pick from any bag." ] }, { "cell_type": "code", "execution_count": 262, "metadata": {}, "outputs": [], "source": [ "dist = {('First', 0.5): dist1, ('Second', 0.3): dist2, ('Third', 0.2): dist3}\n", "nBS = NaiveBayesLearner(dist, simple=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we can start making predictions:" ] }, { "cell_type": "code", "execution_count": 263, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "First\n", "Second\n", "Third\n" ] } ], "source": [ "print(nBS('aab')) # We can handle strings\n", "print(nBS(['b', 'b'])) # And lists!\n", "print(nBS('ccbcc'))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The results make intuitive sense. The first bag has a high amount of 'a's, the second has a high amount of 'b's and the third has a high amount of 'c's. The classifier seems to confirm this intuition.\n", "\n", "Note that the simple classifier doesn't distinguish between discrete and continuous values. It just takes whatever it is given. Also, the `simple` option on the `NaiveBayesLearner` overrides the `continuous` argument. `NaiveBayesLearner(d, simple=True, continuous=False)` just creates a simple classifier." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## PERCEPTRON CLASSIFIER\n", "\n", "### Overview\n", "\n", "The Perceptron is a linear classifier. It works the same way as a neural network with no hidden layers (just input and output). First it trains its weights given a dataset and then it can classify a new item by running it through the network.\n", "\n", "Its input layer consists of the item features, while the output layer consists of nodes (also called neurons). Each node in the output layer has *n* synapses (for every item feature), each with its own weight. Then, the nodes find the dot product of the item features and the synapse weights. These values then pass through an activation function (usually a sigmoid). Finally, we pick the largest of the values and we return its index.\n", "\n", "Note that in classification problems each node represents a class. The final classification is the class/node with the max output value.\n", "\n", "Below you can see a single node/neuron in the outer layer. With f we denote the item features, with *w* the synapse weights, then inside the node we have the dot product and the activation function, g." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![perceptron](images/perceptron.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Implementation\n", "\n", "First, we train (calculate) the weights given a dataset, using the `BackPropagationLearner` function of `learning.py`. We then return a function, `predict`, which we will use in the future to classify a new item. The function computes the (algebraic) dot product of the item with the calculated weights for each node in the outer layer. Then it picks the greatest value and classifies the item in the corresponding class." ] }, { "cell_type": "code", "execution_count": 209, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
def network(input_units, hidden_layer_sizes, output_units, activation=sigmoid):\n",
       "    """Create Directed Acyclic Network of given number layers.\n",
       "    hidden_layers_sizes : List number of neuron units in each hidden layer\n",
       "    excluding input and output layers\n",
       "    """\n",
       "    layers_sizes = [input_units] + hidden_layer_sizes + [output_units]\n",
       "\n",
       "    net = [[NNUnit(activation) for n in range(size)]\n",
       "           for size in layers_sizes]\n",
       "    n_layers = len(net)\n",
       "\n",
       "    # Make Connection\n",
       "    for i in range(1, n_layers):\n",
       "        for n in net[i]:\n",
       "            for k in net[i-1]:\n",
       "                n.inputs.append(k)\n",
       "                n.weights.append(0)\n",
       "    return net\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(network)" ] }, { "cell_type": "code", "execution_count": 210, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
class NNUnit:\n",
       "    """Single Unit of Multiple Layer Neural Network\n",
       "    inputs: Incoming connections\n",
       "    weights: Weights to incoming connections\n",
       "    """\n",
       "\n",
       "    def __init__(self, activation=sigmoid, weights=None, inputs=None):\n",
       "        self.weights = weights or []\n",
       "        self.inputs = inputs or []\n",
       "        self.value = None\n",
       "        self.activation = activation\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(NNUnit)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will write a little function to show us what is going on inside a neural network unit." ] }, { "cell_type": "code", "execution_count": 211, "metadata": {}, "outputs": [], "source": [ "def showNN(unit):\n", " return (unit.weights, unit.inputs, unit.value, unit.activation)" ] }, { "cell_type": "code", "execution_count": 265, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
def PerceptronLearner(dataset, learning_rate=0.01, epochs=100):\n",
       "    """Logistic Regression, NO hidden layer"""\n",
       "    i_units = len(dataset.inputs)\n",
       "    o_units = len(dataset.values[dataset.target])\n",
       "    hidden_layer_sizes = []\n",
       "    raw_net = network(i_units, hidden_layer_sizes, o_units)\n",
       "    learned_net = BackPropagationLearner(dataset, raw_net, learning_rate, epochs)\n",
       "\n",
       "    def predict(example):\n",
       "        o_nodes = learned_net[1]\n",
       "\n",
       "        # Forward pass\n",
       "        for node in o_nodes:\n",
       "            in_val = dotproduct(example, node.weights)\n",
       "            node.value = node.activation(in_val)\n",
       "\n",
       "        # Hypothesis\n",
       "        return find_max_node(o_nodes)\n",
       "\n",
       "    return predict\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(PerceptronLearner)" ] }, { "cell_type": "code", "execution_count": 264, "metadata": {}, "outputs": [], "source": [ "def PerceptronLearnerStub(dataset, learning_rate=0.01, epochs=100):\n", " \"\"\"Logistic Regression, NO hidden layer\"\"\"\n", " i_units = len(dataset.inputs)\n", " o_units = len(dataset.values[dataset.target])\n", " hidden_layer_sizes = []\n", " raw_net = network(i_units, hidden_layer_sizes, o_units)\n", " learned_net = BackPropagationLearner(dataset, raw_net, learning_rate, epochs)\n", " \n", " return raw_net, learned_net" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that the Perceptron is a one-layer neural network, without any hidden layers. So, in `BackPropagationLearner`, we will pass no hidden layers. From that function we get our network, which is just one layer, with the weights calculated.\n", "\n", "That function `predict` passes the input/example through the network, calculating the dot product of the input and the weights for each node and returns the class with the max dot product." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example\n", "\n", "We will train the Perceptron on the iris dataset. Because though the `BackPropagationLearner` works with integer indexes and not strings, we need to convert class names to integers. Then, we will try and classify the item/flower with measurements of 5, 3, 1, 0.1." ] }, { "cell_type": "code", "execution_count": 266, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0\n" ] } ], "source": [ "iris = DataSet(name=\"iris\")\n", "iris.classes_to_numbers()\n", "\n", "perceptron = PerceptronLearner(iris)\n", "print(perceptron([5, 3, 1, 0.1]))\n", "raw_stub, learned_stub = PerceptronLearnerStub(iris)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The correct output is 0, which means the item belongs in the first class, \"setosa\". Note that the Perceptron algorithm is not perfect and may produce false classifications." ] }, { "cell_type": "code", "execution_count": 215, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[,\n", " ,\n", " ,\n", " ],\n", " [,\n", " ,\n", " ]]" ] }, "execution_count": 215, "metadata": {}, "output_type": "execute_result" } ], "source": [ "raw_stub" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Returned by showNN: (weights, inputs, value, activation)" ] }, { "cell_type": "code", "execution_count": 216, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[([], [], 5.9, ),\n", " ([], [], 3.0, ),\n", " ([], [], 5.1, ),\n", " ([], [], 1.8, )]" ] }, "execution_count": 216, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(map(showNN, raw_stub[0]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "raw_stub[1] is the learned network. Notice that the input units are themselves NNUnits." ] }, { "cell_type": "code", "execution_count": 217, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[((0.2737810389749918,\n", " 1.1152308748510247,\n", " -1.543260339282533,\n", " -0.9099540533153505),\n", " [,\n", " ,\n", " ,\n", " ],\n", " 0.010482971183120342,\n", " ),\n", " ((0.28446859792661994,\n", " -0.7426785326773424,\n", " 0.006563536532696342,\n", " -0.7236381177742321),\n", " [,\n", " ,\n", " ,\n", " ],\n", " 0.1410915282457729,\n", " ),\n", " ((-1.1937395158303523,\n", " -0.9863025882400674,\n", " 1.8655398919571222,\n", " 1.253005921954526),\n", " [,\n", " ,\n", " ,\n", " ],\n", " 0.8524739962604119,\n", " )]" ] }, "execution_count": 217, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(map(showNN, raw_stub[1]))" ] }, { "cell_type": "code", "execution_count": 218, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['__class__',\n", " '__delattr__',\n", " '__dict__',\n", " '__dir__',\n", " '__doc__',\n", " '__eq__',\n", " '__format__',\n", " '__ge__',\n", " '__getattribute__',\n", " '__gt__',\n", " '__hash__',\n", " '__init__',\n", " '__init_subclass__',\n", " '__le__',\n", " '__lt__',\n", " '__module__',\n", " '__ne__',\n", " '__new__',\n", " '__reduce__',\n", " '__reduce_ex__',\n", " '__repr__',\n", " '__setattr__',\n", " '__sizeof__',\n", " '__str__',\n", " '__subclasshook__',\n", " '__weakref__',\n", " 'activation',\n", " 'inputs',\n", " 'value',\n", " 'weights']" ] }, "execution_count": 218, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dir(raw_stub[0][0])" ] }, { "cell_type": "code", "execution_count": 219, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5.1" ] }, "execution_count": 219, "metadata": {}, "output_type": "execute_result" } ], "source": [ "raw_stub[0][2].value" ] }, { "cell_type": "code", "execution_count": 220, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[,\n", " ,\n", " ,\n", " ],\n", " [,\n", " ,\n", " ]]" ] }, "execution_count": 220, "metadata": {}, "output_type": "execute_result" } ], "source": [ "learned_stub" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## LINEAR LEARNER\n", "\n", "### Overview\n", "\n", "Linear Learner is a model that assumes a linear relationship between the input variables x and the single output variable y. More specifically, that y can be calculated from a linear combination of the input variables x. Linear learner is a quite simple model as the representation of this model is a linear equation. \n", "\n", "The linear equation assigns one scaler factor to each input value or column, called coefficients or weights. One additional coefficient is also added, giving additional degree of freedom and is often called the intercept or the bias coefficient. \n", "For example : y = ax1 + bx2 + c . \n", "\n", "### Implementation\n", "\n", "Below mentioned is the implementation of Linear Learner." ] }, { "cell_type": "code", "execution_count": 221, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
def LinearLearner(dataset, learning_rate=0.01, epochs=100):\n",
       "    """Define with learner = LinearLearner(data); infer with learner(x)."""\n",
       "    idx_i = dataset.inputs\n",
       "    idx_t = dataset.target  # As of now, dataset.target gives only one index.\n",
       "    examples = dataset.examples\n",
       "    num_examples = len(examples)\n",
       "\n",
       "    # X transpose\n",
       "    X_col = [dataset.values[i] for i in idx_i]  # vertical columns of X\n",
       "\n",
       "    # Add dummy\n",
       "    ones = [1 for _ in range(len(examples))]\n",
       "    X_col = [ones] + X_col\n",
       "\n",
       "    # Initialize random weigts\n",
       "    num_weights = len(idx_i) + 1\n",
       "    w = random_weights(min_value=-0.5, max_value=0.5, num_weights=num_weights)\n",
       "\n",
       "    for epoch in range(epochs):\n",
       "        err = []\n",
       "        # Pass over all examples\n",
       "        for example in examples:\n",
       "            x = [1] + example\n",
       "            y = dotproduct(w, x)\n",
       "            t = example[idx_t]\n",
       "            err.append(t - y)\n",
       "\n",
       "        # update weights\n",
       "        for i in range(len(w)):\n",
       "            w[i] = w[i] + learning_rate * (dotproduct(err, X_col[i]) / num_examples)\n",
       "\n",
       "    def predict(example):\n",
       "        x = [1] + example\n",
       "        return dotproduct(w, x)\n",
       "    return predict\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(LinearLearner)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This algorithm first assigns some random weights to the input variables and then based on the error calculated updates the weight for each variable. Finally the prediction is made with the updated weights. \n", "\n", "### Implementation\n", "\n", "We will now use the Linear Learner to classify a sample with values: 5.1, 3.0, 1.1, 0.1." ] }, { "cell_type": "code", "execution_count": 271, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.10590907746514296\n" ] } ], "source": [ "iris = DataSet(name=\"iris\")\n", "iris.classes_to_numbers()\n", "\n", "linear_learner = LinearLearner(iris)\n", "print(linear_learner([5, 3, 1, 0.1]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we will try some experiments, varying the learning rate and the epochs. The learning rate show how much to change the weight each time and the epochs are the number of learning cycles. \n", "\n", "Note that the learner starts with random weights, so the results vary from run to run." ] }, { "cell_type": "code", "execution_count": 275, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2.121753043130544\n" ] } ], "source": [ "iris = DataSet(name=\"iris\")\n", "iris.classes_to_numbers()\n", "\n", "linear_learner2 = LinearLearner(iris, learning_rate=.05)\n", "print(linear_learner2([5, 3, 1, 0.1]))" ] }, { "cell_type": "code", "execution_count": 278, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7.100597551535986\n" ] } ], "source": [ "iris = DataSet(name=\"iris\")\n", "iris.classes_to_numbers()\n", "\n", "linear_learner3 = LinearLearner(iris, epochs=1000)\n", "print(linear_learner3([5, 3, 1, 0.1]))" ] }, { "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 adjust 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": 227, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Error ratio for Discrete: 0.040000000000000036\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": 229, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Error ratio for Perceptron: 0.31999999999999995\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 showed 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` doesnot 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": 231, "metadata": {}, "outputs": [], "source": [ "WeightedPerceptron = WeightedLearner(PerceptronLearner)\n", "AdaboostLearner = AdaBoost(WeightedPerceptron, 5)" ] }, { "cell_type": "code", "execution_count": 232, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 232, "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": 233, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Error ratio for adaboost: 0.033333333333333326\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 }