Newer
Older
"source": [
"# Learning\n",
"\n",
"This notebook serves as supporting material for topics covered in **Chapter 18 - Learning from Examples** , **Chapter 19 - Knowledge in Learning**, **Chapter 20 - Learning Probabilistic Models** from the book *Artificial Intelligence: A Modern Approach*. This notebook uses implementations from [learning.py](https://github.com/aimacode/aima-python/blob/master/learning.py). Let's start by importing everything from the module:"
]
},
{
"cell_type": "code",
},
"outputs": [],
"source": [
"from learning import *"
"## Contents\n",
"\n",
"* Machine Learning Overview\n",
"* Distance Functions\n",
"* Plurality Learner\n",
"* k-Nearest Neighbours\n",
"* Naive Bayes Learner\n",
"* Perceptron\n",
"* MNIST Handwritten Digits\n",
" * Loading and Visualising\n",
" * Testing\n",
" * kNN Classifier"
"source": [
"## Machine Learning Overview\n",
"\n",
"In this notebook, we learn about agents that can improve their behavior through diligent study of their own experiences.\n",
"\n",
"An agent is **learning** if it improves its performance on future tasks after making observations about the world.\n",
"\n",
"There are three types of feedback that determine the three main types of learning:\n",
"\n",
"* **Supervised Learning**:\n",
"\n",
"In Supervised Learning the agent observes some example input-output pairs and learns a function that maps from input to output.\n",
"\n",
"**Example**: Let's think of an agent to classify images containing cats or dogs. If we provide an image containing a cat or a dog, this agent should output a string \"cat\" or \"dog\" for that particular image. To teach this agent, we will give a lot of input-output pairs like {cat image-\"cat\"}, {dog image-\"dog\"} to the agent. The agent then learns a function that maps from an input image to one of those strings.\n",
"\n",
"* **Unsupervised Learning**:\n",
"\n",
"In Unsupervised Learning the agent learns patterns in the input even though no explicit feedback is supplied. The most common type is **clustering**: detecting potential useful clusters of input examples.\n",
"\n",
"**Example**: A taxi agent would develop a concept of *good traffic days* and *bad traffic days* without ever being given labeled examples.\n",
"\n",
"* **Reinforcement Learning**:\n",
"\n",
"In Reinforcement Learning the agent learns from a series of reinforcements—rewards or punishments.\n",
"\n",
"**Example**: Let's talk about an agent to play the popular Atari game—[Pong](http://www.ponggame.org). We will reward a point for every correct move and deduct a point for every wrong move from the agent. Eventually, the agent will figure out its actions prior to reinforcement were most responsible for it."
]
},
{
"cell_type": "markdown",
"source": [
"## Datasets\n",
"\n",
"For the following tutorials we will use a range of datasets, to better showcase the strengths and weaknesses of the algorithms. The datasests are the following:\n",
"\n",
"* [Fisher's Iris](https://github.com/aimacode/aima-data/blob/a21fc108f52ad551344e947b0eb97df82f8d2b2b/iris.csv): Each item represents a flower, with four measurements: the length and the width of the sepals and petals. Each item/flower is categorized into one of three species: Setosa, Versicolor and Virginica.\n",
"* [Zoo](https://github.com/aimacode/aima-data/blob/a21fc108f52ad551344e947b0eb97df82f8d2b2b/zoo.csv): The dataset holds different animals and their classification as \"mammal\", \"fish\", etc. The new animal we want to classify has the following measurements: 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 4, 1, 0, 1 (don't concern yourself with what the measurements mean)."
{
"cell_type": "markdown",
"To make using the datasets easier, we have written a class, `DataSet`, in `learning.py`. The tutorials found here make use of this class.\n",
"Let's have a look at how it works before we get started with the algorithms."
]
},
{
"cell_type": "markdown",
"A lot of the datasets we will work with are .csv files (although other formats are supported too). We have a collection of sample datasets ready to use [on aima-data](https://github.com/aimacode/aima-data/tree/a21fc108f52ad551344e947b0eb97df82f8d2b2b). Two examples are the datasets mentioned above (*iris.csv* and *zoo.csv*). You can find plenty datasets online, and a good repository of such datasets is [UCI Machine Learning Repository](https://archive.ics.uci.edu/ml/datasets.html).\n",
"In such files, each line corresponds to one item/measurement. Each individual value in a line represents a *feature* and usually there is a value denoting the *class* of the item.\n",
"You can find the code for the dataset here:"
]
},
{
"cell_type": "code",
},
"outputs": [],
"source": [
"%psource DataSet"
]
},
{
"cell_type": "markdown",
"source": [
"### Class Attributes\n",
"* **examples**: Holds the items of the dataset. Each item is a list of values.\n",
"* **attrs**: The indexes of the features (by default in the range of [0,f), where *f* is the number of features. For example, `item[i]` returns the feature at index *i* of *item*.\n",
"* **attrnames**: An optional list with attribute names. For example, `item[s]`, where *s* is a feature name, returns the feature of name *s* in *item*.\n",
"* **target**: The attribute a learning algorithm will try to predict. By default the last attribute.\n",
"* **inputs**: This is the list of attributes without the target.\n",
"* **values**: A list of lists which holds the set of possible values for the corresponding attribute/feature. If initially `None`, it gets computed (by the function `setproblem`) from the examples.\n",
"* **distance**: The distance function used in the learner to calculate the distance between two items. By default `mean_boolean_error`.\n",
"* **name**: Name of the dataset.\n",
"\n",
"* **source**: The source of the dataset (url or other). Not used in the code.\n",
"\n",
"* **exclude**: A list of indexes to exclude from `inputs`. The list can include either attribute indexes (attrs) or names (attrnames)."
]
},
{
"cell_type": "markdown",
"source": [
"### Class Helper Functions\n",
"\n",
"These functions help modify a `DataSet` object to your needs.\n",
"\n",
"* **sanitize**: Takes as input an example and returns it with non-input (target) attributes replaced by `None`. Useful for testing. Keep in mind that the example given is not itself sanitized, but instead a sanitized copy is returned.\n",
"\n",
"* **classes_to_numbers**: Maps the class names of a dataset to numbers. If the class names are not given, they are computed from the dataset values. Useful for classifiers that return a numerical value instead of a string.\n",
"\n",
"* **remove_examples**: Removes examples containing a given value. Useful for removing examples with missing values, or for removing classes (needed for binary classifiers)."
]
},
{
"cell_type": "markdown",
"source": [
"### Importing a Dataset\n",
"\n",
"#### Importing from aima-data\n",
"\n",
"Datasets uploaded on aima-data can be imported with the following line:"
]
},
{
"cell_type": "code",
},
"outputs": [],
"source": [
"iris = DataSet(name=\"iris\")"
]
},
{
"cell_type": "markdown",
"source": [
"To check that we imported the correct dataset, we can do the following:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[5.1, 3.5, 1.4, 0.2, 'setosa']\n",
"[0, 1, 2, 3]\n"
]
}
],
"source": [
"print(iris.examples[0])\n",
"print(iris.inputs)"
]
},
{
"cell_type": "markdown",
"source": [
"Which correctly prints the first line in the csv file and the list of attribute indexes."
]
},
{
"cell_type": "markdown",
"source": [
"When importing a dataset, we can specify to exclude an attribute (for example, at index 1) by setting the parameter `exclude` to the attribute index or name."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0, 2, 3]\n"
]
}
],
"source": [
"iris2 = DataSet(name=\"iris\",exclude=[1])\n",
"print(iris2.inputs)"
]
},
{
"cell_type": "markdown",
"source": [
"### Attributes\n",
"\n",
"Here we showcase the attributes.\n",
"\n",
"First we will print the first three items/examples in the dataset."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[5.1, 3.5, 1.4, 0.2, 'setosa'], [4.9, 3.0, 1.4, 0.2, 'setosa'], [4.7, 3.2, 1.3, 0.2, 'setosa']]\n"
]
}
],
"source": [
"print(iris.examples[:3])"
]
},
{
"cell_type": "markdown",
"source": [
"Then we will print `attrs`, `attrnames`, `target`, `input`. Notice how `attrs` holds values in [0,4], but since the fourth attribute is the target, `inputs` holds values in [0,3]."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"attrs: [0, 1, 2, 3, 4]\n",
"attrnames (by default same as attrs): [0, 1, 2, 3, 4]\n",
"target: 4\n",
"inputs: [0, 1, 2, 3]\n"
]
}
],
"source": [
"print(\"attrs:\", iris.attrs)\n",
"print(\"attrnames (by default same as attrs):\", iris.attrnames)\n",
"print(\"target:\", iris.target)\n",
"print(\"inputs:\", iris.inputs)"
]
},
{
"cell_type": "markdown",
"source": [
"Now we will print all the possible values for the first feature/attribute."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[4.7, 5.5, 6.3, 5.0, 4.9, 5.1, 4.6, 5.4, 4.4, 4.8, 5.8, 7.0, 7.1, 4.5, 5.9, 5.6, 6.9, 6.6, 6.5, 6.4, 6.0, 6.1, 7.6, 7.4, 7.9, 4.3, 5.7, 5.3, 5.2, 6.7, 6.2, 6.8, 7.3, 7.2, 7.7]\n"
]
}
],
"source": [
"print(iris.values[0])"
]
},
{
"cell_type": "markdown",
"source": [
"Finally we will print the dataset's name and source. Keep in mind that we have not set a source for the dataset, so in this case it is empty."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"name: iris\n",
"source: \n"
]
}
],
"source": [
"print(\"name:\", iris.name)\n",
"print(\"source:\", iris.source)"
]
},
{
"cell_type": "markdown",
"source": [
"A useful combination of the above is `dataset.values[dataset.target]` which returns the possible values of the target. For classification problems, this will return all the possible classes. Let's try it:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['versicolor', 'virginica', 'setosa']\n"
]
}
],
"source": [
"print(iris.values[iris.target])"
]
},
{
"cell_type": "markdown",
"source": [
"### Helper Functions"
]
},
{
"cell_type": "markdown",
"source": [
"We will now take a look at the auxiliary functions found in the class.\n",
"\n",
"First we will take a look at the `sanitize` function, which sets the non-input values of the given example to `None`.\n",
"\n",
"In this case we want to hide the class of the first example, so we will sanitize it.\n",
"\n",
"Note that the function doesn't actually change the given example; it returns a sanitized *copy* of it."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Sanitized: [5.1, 3.5, 1.4, 0.2, None]\n",
"Original: [5.1, 3.5, 1.4, 0.2, 'setosa']\n"
]
}
],
"source": [
"print(\"Sanitized:\",iris.sanitize(iris.examples[0]))\n",
"print(\"Original:\",iris.examples[0])"
]
},
{
"cell_type": "markdown",
"source": [
"Currently the `iris` dataset has three classes, setosa, virginica and versicolor. We want though to convert it to a binary class dataset (a dataset with two classes). The class we want to remove is \"virginica\". To accomplish that we will utilize the helper function `remove_examples`."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"iris2 = DataSet(name=\"iris\")\n",
"\n",
"iris2.remove_examples(\"virginica\")\n",
"print(iris2.values[iris2.target])"
]
},
{
"cell_type": "markdown",
"We also have `classes_to_numbers`. For a lot of the classifiers in the module (like the Neural Network), classes should have numerical values. With this function we map string class names to numbers."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Class of first example: setosa\n",
"Class of first example: 0\n"
]
}
],
"source": [
"print(\"Class of first example:\",iris2.examples[0][iris2.target])\n",
"iris2.classes_to_numbers()\n",
"print(\"Class of first example:\",iris2.examples[0][iris2.target])"
]
},
{
"cell_type": "markdown",
"source": [
"As you can see \"setosa\" was mapped to 0."
{
"cell_type": "markdown",
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
"metadata": {},
"source": [
"Finally, we take a look at `find_means_and_deviations`. It finds the means and standard deviations of the features for each class."
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Setosa feature means: [5.006, 3.418, 1.464, 0.244]\n",
"Versicolor mean for first feature: 5.936\n",
"Setosa feature deviations: [0.3524896872134513, 0.38102439795469095, 0.17351115943644546, 0.10720950308167838]\n",
"Virginica deviation for second feature: 0.32249663817263746\n"
]
}
],
"source": [
"means, deviations = iris.find_means_and_deviations()\n",
"\n",
"print(\"Setosa feature means:\", means[\"setosa\"])\n",
"print(\"Versicolor mean for first feature:\", means[\"versicolor\"][0])\n",
"\n",
"print(\"Setosa feature deviations:\", deviations[\"setosa\"])\n",
"print(\"Virginica deviation for second feature:\",deviations[\"virginica\"][1])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Distance Functions\n",
"\n",
"In a lot of algorithms (like the *k-Nearest Neighbors* algorithm), there is a need to compare items, finding how *similar* or *close* they are. For that we have many different functions at our disposal. Below are the functions implemented in the module:\n",
"\n",
"### Manhattan Distance (`manhattan_distance`)\n",
"\n",
"One of the simplest distance functions. It calculates the difference between the coordinates/features of two items. To understand how it works, imagine a 2D grid with coordinates *x* and *y*. In that grid we have two items, at the squares positioned at `(1,2)` and `(3,4)`. The difference between their two coordinates is `3-1=2` and `4-2=2`. If we sum these up we get `4`. That means to get from `(1,2)` to `(3,4)` we need four moves; two to the right and two more up. The function works similarly for n-dimensional grids."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Manhattan Distance between (1,2) and (3,4) is 4\n"
]
}
],
"source": [
"def manhattan_distance(X, Y):\n",
" return sum([abs(x - y) for x, y in zip(X, Y)])\n",
"\n",
"\n",
"distance = manhattan_distance([1,2], [3,4])\n",
"print(\"Manhattan Distance between (1,2) and (3,4) is\", distance)"
]
},
{
"cell_type": "markdown",
"source": [
"### Euclidean Distance (`euclidean_distance`)\n",
"\n",
"Probably the most popular distance function. It returns the square root of the sum of the squared differences between individual elements of two items."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Euclidean Distance between (1,2) and (3,4) is 2.8284271247461903\n"
]
}
],
"source": [
"def euclidean_distance(X, Y):\n",
" return math.sqrt(sum([(x - y)**2 for x, y in zip(X,Y)]))\n",
"\n",
"\n",
"distance = euclidean_distance([1,2], [3,4])\n",
"print(\"Euclidean Distance between (1,2) and (3,4) is\", distance)"
]
},
{
"cell_type": "markdown",
"source": [
"### Hamming Distance (`hamming_distance`)\n",
"\n",
"This function counts the number of differences between single elements in two items. For example, if we have two binary strings \"111\" and \"011\" the function will return 1, since the two strings only differ at the first element. The function works the same way for non-binary strings too."
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Hamming Distance between 'abc' and 'abb' is 1\n"
]
}
],
"source": [
"def hamming_distance(X, Y):\n",
" return sum(x != y for x, y in zip(X, Y))\n",
"\n",
"\n",
"distance = hamming_distance(['a','b','c'], ['a','b','b'])\n",
"print(\"Hamming Distance between 'abc' and 'abb' is\", distance)"
]
},
{
"cell_type": "markdown",
"source": [
"### Mean Boolean Error (`mean_boolean_error`)\n",
"\n",
"To calculate this distance, we find the ratio of different elements over all elements of two items. For example, if the two items are `(1,2,3)` and `(1,4,5)`, the ration of different/all elements is 2/3, since they differ in two out of three elements."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Mean Boolean Error Distance between (1,2,3) and (1,4,5) is 0.6666666666666666\n"
]
}
],
"source": [
"def mean_boolean_error(X, Y):\n",
" return mean(int(x != y) for x, y in zip(X, Y))\n",
"\n",
"\n",
"distance = mean_boolean_error([1,2,3], [1,4,5])\n",
"print(\"Mean Boolean Error Distance between (1,2,3) and (1,4,5) is\", distance)"
]
},
{
"cell_type": "markdown",
"source": [
"### Mean Error (`mean_error`)\n",
"\n",
"This function finds the mean difference of single elements between two items. For example, if the two items are `(1,0,5)` and `(3,10,5)`, their error distance is `(3-1) + (10-0) + (5-5) = 2 + 10 + 0 = 12`. The mean error distance therefore is `12/3=4`."
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Mean Error Distance between (1,0,5) and (3,10,5) is 4\n"
]
}
],
"source": [
"def mean_error(X, Y):\n",
" return mean([abs(x - y) for x, y in zip(X, Y)])\n",
"\n",
"\n",
"distance = mean_error([1,0,5], [3,10,5])\n",
"print(\"Mean Error Distance between (1,0,5) and (3,10,5) is\", distance)"
]
},
{
"cell_type": "markdown",
"source": [
"### Mean Square Error (`ms_error`)\n",
"\n",
"This is very similar to the `Mean Error`, but instead of calculating the difference between elements, we are calculating the *square* of the differences."
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Mean Square Distance between (1,0,5) and (3,10,5) is 34.666666666666664\n"
]
}
],
"source": [
"def ms_error(X, Y):\n",
" return mean([(x - y)**2 for x, y in zip(X, Y)])\n",
"\n",
"\n",
"distance = ms_error([1,0,5], [3,10,5])\n",
"print(\"Mean Square Distance between (1,0,5) and (3,10,5) is\", distance)"
]
},
{
"cell_type": "markdown",
"source": [
"### Root of Mean Square Error (`rms_error`)\n",
"\n",
"This is the square root of `Mean Square Error`."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Root of Mean Error Distance between (1,0,5) and (3,10,5) is 5.887840577551898\n"
]
}
],
"source": [
"def rms_error(X, Y):\n",
" return math.sqrt(ms_error(X, Y))\n",
"\n",
"\n",
"distance = rms_error([1,0,5], [3,10,5])\n",
"print(\"Root of Mean Error Distance between (1,0,5) and (3,10,5) is\", distance)"
]
},
{
"cell_type": "markdown",
"## Plurality Learner Classifier\n",
"\n",
"### Overview\n",
"\n",
"The Plurality Learner is a simple algorithm, used mainly as a baseline comparison for other algorithms. It finds the most popular class in the dataset and classifies any subsequent item to that class. Essentially, it classifies every new item to the same class. For that reason, it is not used very often, instead opting for more complicated algorithms when we want accurate classification.\n",
"\n",
"\n",
"\n",
"Let's see how the classifier works with the plot above. There are three classes named **Class A** (orange-colored dots) and **Class B** (blue-colored dots) and **Class C** (green-colored dots). Every point in this plot has two **features** (i.e. X<sub>1</sub>, X<sub>2</sub>). Now, let's say we have a new point, a red star and we want to know which class this red star belongs to. Solving this problem by predicting the class of this new red star is our current classification problem.\n",
"\n",
"The Plurality Learner will find the class most represented in the plot. ***Class A*** has four items, ***Class B*** has three and ***Class C*** has seven. The most popular class is ***Class C***. Therefore, the item will get classified in ***Class C***, despite the fact that it is closer to the other two classes."
},
{
"cell_type": "markdown",
"source": [
"### Implementation\n",
"\n",
"Below follows the implementation of the PluralityLearner algorithm:"
]
},
{
"cell_type": "code",
},
"outputs": [],
"source": [
"def PluralityLearner(dataset):\n",
" \"\"\"A very dumb algorithm: always pick the result that was most popular\n",
" in the training data. Makes a baseline for comparison.\"\"\"\n",
" most_popular = mode([e[dataset.target] for e in dataset.examples])\n",
"\n",
" def predict(example):\n",
" \"Always return same result: the most popular from the training set.\"\n",
" return most_popular\n",
" return predict"
]
},
{
"cell_type": "markdown",
"source": [
"It takes as input a dataset and returns a function. We can later call this function with the item we want to classify as the argument and it returns the class it should be classified in.\n",
"\n",
"The function first finds the most popular class in the dataset and then each time we call its \"predict\" function, it returns it. Note that the input (\"example\") does not matter. The function always returns the same class."
]
},
{
"cell_type": "markdown",
"source": [
"### Example\n",
"\n",
"For this example, we will not use the Iris dataset, since each class is represented the same. This will throw an error. Instead we will use the zoo dataset."
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"mammal\n"
]
}
],
"source": [
"zoo = DataSet(name=\"zoo\")\n",
"\n",
"pL = PluralityLearner(zoo)\n",
"print(pL([1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 4, 1, 0, 1]))"
]
},
{
"cell_type": "markdown",
"source": [
"The output for the above code is \"mammal\", since that is the most popular and common class in the dataset."
]
},
{
"cell_type": "markdown",
"source": [
"## k-Nearest Neighbours (kNN) Classifier\n",
"\n",
"### Overview\n",
"The k-Nearest Neighbors algorithm is a non-parametric method used for classification and regression. We are going to use this to classify Iris flowers. More about kNN on [Scholarpedia](http://www.scholarpedia.org/article/K-nearest_neighbor).\n",
"\n",
""
]
},
{
"cell_type": "markdown",
"source": [
"Let's see how kNN works with a simple plot shown in the above picture.\n",
"\n",
"We have co-ordinates (we call them **features** in Machine Learning) of this red star and we need to predict its class using the kNN algorithm. In this algorithm, the value of **k** is arbitrary. **k** is one of the **hyper parameters** for kNN algorithm. We choose this number based on our dataset and choosing a particular number is known as **hyper parameter tuning/optimising**. We learn more about this in coming topics.\n",
"\n",
"Let's put **k = 3**. It means you need to find 3-Nearest Neighbors of this red star and classify this new point into the majority class. Observe that smaller circle which contains three points other than **test point** (red star). As there are two violet points, which form the majority, we predict the class of red star as **violet- Class B**.\n",
"\n",
"Similarly if we put **k = 5**, you can observe that there are four yellow points, which form the majority. So, we classify our test point as **yellow- Class A**.\n",
"\n",
"In practical tasks, we iterate through a bunch of values for k (like [1, 3, 5, 10, 20, 50, 100]), see how it performs and select the best one. "
]
},
{
"cell_type": "markdown",
"source": [
"### Implementation\n",
"\n",
"Below follows the implementation of the kNN algorithm:"
]
},
{
"cell_type": "code",
},
"outputs": [],
"source": [
"def NearestNeighborLearner(dataset, k=1):\n",
" \"\"\"k-NearestNeighbor: the k nearest neighbors vote.\"\"\"\n",
" def predict(example):\n",
" \"\"\"Find the k closest items, and have them vote for the best.\"\"\"\n",
" best = heapq.nsmallest(k, ((dataset.distance(e, example), e)\n",
" for e in dataset.examples))\n",
" return mode(e[dataset.target] for (d, e) in best)\n",
" return predict"
]
},
{
"cell_type": "markdown",
"It takes as input a dataset and k (default value is 1) and it returns a function, which we can later use to classify a new item.\n",
"To accomplish that, the function uses a heap-queue, where the items of the dataset are sorted according to their distance from *example* (the item to classify). We then take the k smallest elements from the heap-queue and we find the majority class. We classify the item to this class."
]
},
{
"cell_type": "markdown",
"We measured a new flower with the following values: 5.1, 3.0, 1.1, 0.1. We want to classify that item/flower in a class. To do that, we write the following:"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"setosa\n"
]
}
],
"source": [
"iris = DataSet(name=\"iris\")\n",
"\n",
"kNN = NearestNeighborLearner(iris,k=3)\n",
"print(kNN([5.1,3.0,1.1,0.1]))"
]
},
{
"cell_type": "markdown",
"source": [
"The output of the above code is \"setosa\", which means the flower with the above measurements is of the \"setosa\" species."
]
},
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Multilayer Perceptron Classifier\n",
"\n",
"### Overview\n",
"\n",
"Although the Perceptron may seem like a good way to make classifications, it is a linear classifier. A Perceptron can be used to represent both AND and OR boolean functions, but not the XOR one, which is a nonlinear function. In order to solve that, the MultiLayer Perceptron (MLP) or Neural Network can be used.\n",
"\n",
"Different from the Perceptron, the MultiLayer Perceptron is a nonlinear classifier, meaning that it can represent more robust functions. It achieves that by combining the results of linear functions on each layer of the network.\n",
"Similar to the Perceptron, this network also has an input and output layer. However it can also have a number of hidden layers. These hidden layers are responsible for creating the nonlinearity of the MLP. A usual execution of an MLP is to feed the inputs into the first hidden layer. Every neuron on the hidden layer will behave exactly as one neuron on the Perceptron. After that, every value in the hidden layer is fed to the next hidden layer, until we feed the final layer, the output layer, which will be used to generate our classification.\n",
"\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Implementation\n",
"\n",
"First, we need to define a dataset and the number of neurons the hidden layer will have (we currently only support using one hidden layer). After that we will create our neural network in the `network` function. This function will make the necessary connections between the input layer, hidden layer and output layer. With the network ready, we will use the `BackPropagationLearner` to train the weights of our network for the examples provided in the dataset.\n",
"\n",
"The NeuralNetLearner returns the `predict` function, which will receive an example and feed forward it into our network to generate a prediction.\n",
"\n",
"NOTE: Like the PerceptronLearner, NeuralNetLearner is a binary classifier and will not work well for multi-class datasets."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"%psource NeuralNetLearner"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Backpropagation\n",
"In both Perceptron and MLP, we are talking about the Backpropagation algorithm. This algorithm is the one used to train the weights of our learners. Basically it achieves that by propagating the errors from our last layer into our first layer, this is why it is called Backpropagation. In order to use Backpropagation, we need a cost function. This function is responsible for indicating how good our neural network is for a given example. One common cost function is the Mean Squared Error (MSE). This cost function has the following format:\n",
"\n",
"$$MSE=\\frac{1}{2} \\sum_{i=1}^{n}(y - \\hat{y})^{2}$$\n",
"\n",
"Where `n` is the number of training examples, $\\hat{y}$ is our prediction and $y$ is the correct prediction for the example.\n",
"\n",
"Backpropagation basically combines the concept of partial derivatives and the chain rule to generate the gradient for each weight in the network based on the cost function\n",
"\n",
"For example, considering we are using a Neural Network with three layers, the sigmoid function as our activation function and the MSE cost function, we want to find the gradient for the a given weight $w_{j}$, we can compute it like this:\n",
"\n",
"$$\\frac{\\partial MSE(\\hat{y}, y)}{\\partial w_{j}} = \\frac{\\partial MSE(\\hat{y}, y)}{\\partial \\hat{y}}\\times\\frac{\\partial\\hat{y}(in_{j})}{\\partial in_{j}}\\times\\frac{\\partial in_{j}}{\\partial w_{j}}$$\n",
"\n",
"Solving this equation, we have:\n",
"\n",
"$$\\frac{\\partial MSE(\\hat{y}, y)}{\\partial w_{j}} = (\\hat{y} - y)\\times{\\hat{y}}'(in_{j})\\times a_{j}$$\n",
"\n",
"Remember that $\\hat{y}$ is the activation function applied to a neuron in our hidden layer, therefore $$\\hat{y} = sigmoid(\\sum_{i=1}^{num\\_neurons}w_{i}\\times a_{i})$$\n",
"\n",
"Also $a$ is the input generated by feeding the input layer variables into the hidden layer.\n",
"\n",
"We can use the same technique for the weights in the input layer as well. After we have the gradients for both weights, we use gradient descent to update the weights of the network."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Implementation\n",
"\n",
"First, we feed forward the examples in our neural network. After that, we calculate the gradient for each layer weights. Once that is complete, we update all the weights using gradient descent. After running these for a given number of epochs (number of time we will pass over all the training examples), the function returns the trained Neural Network."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"%psource BackPropagationLearner"
]