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. Let's start by importing everything from the module:
In [1]:
from learning import *
In this notebook, we learn about agents that can improve their behavior through diligent study of their own experiences.
An agent is learning if it improves its performance on future tasks after making observations about the world.
There are three types of feedback that determine the three main types of learning:
In Supervised Learning the agent observes some example input-output pairs and learns a function that maps from input to output.
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.
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.
Example: A taxi agent would develop a concept of good traffic days and bad traffic days without ever being given labeled examples.
In Reinforcement Learning the agent learns from a series of reinforcements—rewards or punishments.
Example: Let's talk about an agent to play the popular Atari game—Pong. 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.
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:
Fisher's Iris: 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.
Zoo: 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).
To make using the datasets easier, we have written a class, DataSet, in learning.py. The tutorials found here make use of this class.
Let's have a look at how it works before we get started with the algorithms.
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. 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.
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.
You can find the code for the dataset here:
In [23]:
%psource DataSet
examples: Holds the items of the dataset. Each item is a list of values.
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.
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.
target: The attribute a learning algorithm will try to predict. By default the last attribute.
inputs: This is the list of attributes without the target.
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.
distance: The distance function used in the learner to calculate the distance between two items. By default mean_boolean_error.
name: Name of the dataset.
source: The source of the dataset (url or other). Not used in the code.
exclude: A list of indexes to exclude from inputs. The list can include either attribute indexes (attrs) or names (attrnames).
These functions help modify a DataSet object to your needs.
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.
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.
remove_examples: Removes examples containing a given value. Useful for removing examples with missing values, or for removing classes (needed for binary classifiers).
In [7]:
iris = DataSet(name="iris")
To check that we imported the correct dataset, we can do the following:
In [5]:
print(iris.examples[0])
print(iris.inputs)
Which correctly prints the first line in the csv file and the list of attribute indexes.
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.
In [6]:
iris2 = DataSet(name="iris",exclude=[1])
print(iris2.inputs)
In [4]:
print(iris.examples[:3])
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].
In [12]:
print("attrs:", iris.attrs)
print("attrnames (by default same as attrs):", iris.attrnames)
print("target:", iris.target)
print("inputs:", iris.inputs)
Now we will print all the possible values for the first feature/attribute.
In [15]:
print(iris.values[0])
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.
In [16]:
print("name:", iris.name)
print("source:", iris.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:
In [2]:
print(iris.values[iris.target])
We will now take a look at the auxiliary functions found in the class.
First we will take a look at the sanitize function, which sets the non-input values of the given example to None.
In this case we want to hide the class of the first example, so we will sanitize it.
Note that the function doesn't actually change the given example; it returns a sanitized copy of it.
In [27]:
print("Sanitized:",iris.sanitize(iris.examples[0]))
print("Original:",iris.examples[0])
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.
In [3]:
iris.remove_examples("virginica")
print(iris.values[iris.target])
Finally we take a look at 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.
In [4]:
print("Class of first example:",iris.examples[0][iris.target])
iris.classes_to_numbers()
print("Class of first example:",iris.examples[0][iris.target])
As you can see "setosa" was mapped to 0.
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.
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. X1, X2). 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.
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.
In [2]:
def PluralityLearner(dataset):
"""A very dumb algorithm: always pick the result that was most popular
in the training data. Makes a baseline for comparison."""
most_popular = mode([e[dataset.target] for e in dataset.examples])
def predict(example):
"Always return same result: the most popular from the training set."
return most_popular
return predict
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.
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.
In [3]:
zoo = DataSet(name="zoo")
pL = PluralityLearner(zoo)
print(pL([1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 4, 1, 0, 1]))
The output for the above code is "mammal", since that is the most popular and common class in the dataset.
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.
Let's see how kNN works with a simple plot shown in the above picture.
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.
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.
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.
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.
In [4]:
def NearestNeighborLearner(dataset, k=1):
"""k-NearestNeighbor: the k nearest neighbors vote."""
def predict(example):
"""Find the k closest items, and have them vote for the best."""
best = heapq.nsmallest(k, ((dataset.distance(e, example), e)
for e in dataset.examples))
return mode(e[dataset.target] for (d, e) in best)
return predict
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.
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.
In [5]:
iris = DataSet(name="iris")
kNN = NearestNeighborLearner(iris,k=3)
print(kNN([5.1,3.0,1.1,0.1]))
The output of the above code is "setosa", which means the flower with the above measurements is of the "setosa" species.
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.
You can think of it as a single neuron. It has n synapses, each with its own weight. Each synapse corresponds to one item feature. Perceptron multiplies each item feature with the corresponding synapse weight and then adds them together (aka, the dot product) and checks whether this value is greater than the threshold. If yes, it returns 1. It returns 0 otherwise.
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. If the result is greater than a predefined threshold (usually 0.5, 0 or 1), it returns 1. If it is less than the threshold, it returns 0.
NOTE: The current implementation of the algorithm classifies an item into one of two classes. It is a binary classifier and will not work well for multi-class datasets.
In [6]:
def PerceptronLearner(dataset, learning_rate=0.01, epochs=100):
"""Logistic Regression, NO hidden layer"""
i_units = len(dataset.inputs)
o_units = 1 # As of now, dataset.target gives only one index.
hidden_layer_sizes = []
raw_net = network(i_units, hidden_layer_sizes, o_units)
learned_net = BackPropagationLearner(dataset, raw_net, learning_rate, epochs)
def predict(example):
# Input nodes
i_nodes = learned_net[0]
# Activate input layer
for v, n in zip(example, i_nodes):
n.value = v
# Forward pass
for layer in learned_net[1:]:
for node in layer:
inc = [n.value for n in node.inputs]
in_val = dotproduct(inc, node.weights)
node.value = node.activation(in_val)
# Hypothesis
o_nodes = learned_net[-1]
pred = [o_nodes[i].value for i in range(o_units)]
return 1 if pred[0] >= 0.5 else 0
return predict
The weights are trained from the BackPropagationLearner. 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 node, with the weights calculated.
PerceptronLearner returns predict, a function that can be used to classify a new item.
That function passes the input/example through the network, calculating the dot product of the input and the weights. If that value is greater than or equal to 0.5, it returns 1. Otherwise it returns 0.
We will train the Perceptron on the iris dataset. Because, though, the algorithm is a binary classifier (which means it classifies an item in one of two classes) and the iris dataset has three classes, we need to transform the dataset into a proper form, with only two classes. Therefore, we will remove the third and final class of the dataset, Virginica.
Then, we will try and classify the item/flower with measurements of 5,3,1,0.1.
In [7]:
iris = DataSet(name="iris")
iris.remove_examples("virginica")
iris.classes_to_numbers()
perceptron = PerceptronLearner(iris)
print(perceptron([5,3,1,0.1]))
The output is 0, which means the item is classified in the first class, setosa. This is indeed correct. Note that the Perceptron algorithm is not perfect and may produce false classifications.
The MNIST database, available from this page, is a large database of handwritten digits that is commonly used for training and testing/validating in Machine learning.
The dataset has 60,000 training images each of size 28x28 pixels with labels and 10,000 testing images of size 28x28 pixels with labels.
In this section, we will use this database to compare performances of different learning algorithms.
It is estimated that humans have an error rate of about 0.2% on this problem. Let's see how our algorithms perform!
NOTE: We will be using external libraries to load and visualize the dataset smoothly (numpy for loading and matplotlib for visualization). You do not need previous experience of the libraries to follow along.
In [8]:
import os, struct
import array
import numpy as np
import matplotlib.pyplot as plt
from collections import Counter
%matplotlib inline
plt.rcParams['figure.figsize'] = (10.0, 8.0)
plt.rcParams['image.interpolation'] = 'nearest'
plt.rcParams['image.cmap'] = 'gray'
In [9]:
def load_MNIST(path="aima-data/MNIST"):
"helper function to load MNIST data"
train_img_file = open(os.path.join(path, "train-images-idx3-ubyte"), "rb")
train_lbl_file = open(os.path.join(path, "train-labels-idx1-ubyte"), "rb")
test_img_file = open(os.path.join(path, "t10k-images-idx3-ubyte"), "rb")
test_lbl_file = open(os.path.join(path, 't10k-labels-idx1-ubyte'), "rb")
magic_nr, tr_size, tr_rows, tr_cols = struct.unpack(">IIII", train_img_file.read(16))
tr_img = array.array("B", train_img_file.read())
train_img_file.close()
magic_nr, tr_size = struct.unpack(">II", train_lbl_file.read(8))
tr_lbl = array.array("b", train_lbl_file.read())
train_lbl_file.close()
magic_nr, te_size, te_rows, te_cols = struct.unpack(">IIII", test_img_file.read(16))
te_img = array.array("B", test_img_file.read())
test_img_file.close()
magic_nr, te_size = struct.unpack(">II", test_lbl_file.read(8))
te_lbl = array.array("b", test_lbl_file.read())
test_lbl_file.close()
# print(len(tr_img), len(tr_lbl), tr_size)
# print(len(te_img), len(te_lbl), te_size)
train_img = np.zeros((tr_size, tr_rows*tr_cols), dtype=np.int16)
train_lbl = np.zeros((tr_size,), dtype=np.int8)
for i in range(tr_size):
train_img[i] = np.array(tr_img[i*tr_rows*tr_cols : (i+1)*tr_rows*tr_cols]).reshape((tr_rows*te_cols))
train_lbl[i] = tr_lbl[i]
test_img = np.zeros((te_size, te_rows*te_cols), dtype=np.int16)
test_lbl = np.zeros((te_size,), dtype=np.int8)
for i in range(te_size):
test_img[i] = np.array(te_img[i*te_rows*te_cols : (i+1)*te_rows*te_cols]).reshape((te_rows*te_cols))
test_lbl[i] = te_lbl[i]
return(train_img, train_lbl, test_img, test_lbl)
The function load_MNIST() loads MNIST data from files saved in aima-data/MNIST. It returns four numpy arrays that we are going to use to train and classify hand-written digits in various learning approaches.
In [10]:
train_img, train_lbl, test_img, test_lbl = load_MNIST()
Check the shape of these NumPy arrays to make sure we have loaded the database correctly.
Each 28x28 pixel image is flattened to a 784x1 array and we should have 60,000 of them in training data. Similarly, we should have 10,000 of those 784x1 arrays in testing data.
In [11]:
print("Training images size:", train_img.shape)
print("Training labels size:", train_lbl.shape)
print("Testing images size:", test_img.shape)
print("Training labels size:", test_lbl.shape)
In [12]:
classes = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
num_classes = len(classes)
def show_MNIST(dataset, samples=8):
if dataset == "training":
labels = train_lbl
images = train_img
elif dataset == "testing":
labels = test_lbl
images = test_img
else:
raise ValueError("dataset must be 'testing' or 'training'!")
for y, cls in enumerate(classes):
idxs = np.nonzero([i == y for i in labels])
idxs = np.random.choice(idxs[0], samples, replace=False)
for i , idx in enumerate(idxs):
plt_idx = i * num_classes + y + 1
plt.subplot(samples, num_classes, plt_idx)
plt.imshow(images[idx].reshape((28, 28)))
plt.axis("off")
if i == 0:
plt.title(cls)
plt.show()
In [13]:
# takes 5-10 seconds to execute this
show_MNIST("training")
In [14]:
# takes 5-10 seconds to execute this
show_MNIST("testing")
Let's have a look at the average of all the images of training and testing data.
In [15]:
classes = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
num_classes = len(classes)
def show_ave_MNIST(dataset):
if dataset == "training":
print("Average of all images in training dataset.")
labels = train_lbl
images = train_img
elif dataset == "testing":
print("Average of all images in testing dataset.")
labels = test_lbl
images = test_img
else:
raise ValueError("dataset must be 'testing' or 'training'!")
for y, cls in enumerate(classes):
idxs = np.nonzero([i == y for i in labels])
print("Digit", y, ":", len(idxs[0]), "images.")
ave_img = np.mean(np.vstack([images[i] for i in idxs[0]]), axis = 0)
# print(ave_img.shape)
plt.subplot(1, num_classes, y+1)
plt.imshow(ave_img.reshape((28, 28)))
plt.axis("off")
plt.title(cls)
plt.show()
In [16]:
show_ave_MNIST("training")
show_ave_MNIST("testing")
In [17]:
print(train_img.shape, train_lbl.shape)
temp_train_lbl = train_lbl.reshape((60000,1))
training_examples = np.hstack((train_img, temp_train_lbl))
print(training_examples.shape)
Now, we will initialize a DataSet with our training examples, so we can use it in our algorithms.
In [18]:
# takes ~8 seconds to execute this
MNIST_DataSet = DataSet(examples=training_examples, distance=manhattan_distance)
Moving forward we can use MNIST_DataSet to test our algorithms.
In [19]:
from learning import NearestNeighborLearner
# takes ~20 Secs. to execute this
kNN = NearestNeighborLearner(MNIST_DataSet,k=3)
print(kNN(test_img[211]))
To make sure that the output we got is correct, let's plot that image along with its label.
In [20]:
print("Actual class of test image:", test_lbl[211])
plt.imshow(test_img[211].reshape((28,28)))
Out[20]:
Hurray! We've got it correct. Don't worry if our algorithm predicted a wrong class. With this techinique we have only ~97% accuracy on this dataset. Let's try with a different test image and hope we get it this time.
You might have recognized that our algorithm took ~20 seconds to predict a single image. How would we even predict all 10,000 test images? Yeah, the implementations we have in our learning module are not optimized to run on this particular dataset, as they are written with readability in mind, instead of efficiency.