Perceptron

Perceptron

This notebook is a part of AI for Beginners Curricula. Visit the repository for complete set of learning materials.

As we have discussed, perceptron allows you to solve binary classification problem, i.e. to classify input examples into two classes - we can call them positive and negative.

First, let's import some required libraries.

Toy Problem

To begin with, let's start with a toy problem, where we have two input features. For example, in medicine we may want to classify tumours into benign and malignant, depending on its size and age.

We will generate a random classification dataset using make_classification function from SciKit Learn library:

Let's also plot the dataset:

Perceptron

Since perceptron is a binary classifier, for each input vector $x$ the output of our perceptron would be either +1 or -1, depending on the class. The output will be computed using the formula

$y(\mathbf{x}) = f(\mathbf{w}^{\mathrm{T}}\mathbf{x})$

where $\mathbf{w}$ is a weight vector, $f$ is a step activation function:

However, a generic linear model should also have a bias, i.e. ideally we should compute $y$ as $y=f(\mathbf{w}^{\mathrm{T}}\mathbf{x}+\mathbf{b})$. To simplify our model, we can get rid of this bias term by adding one more dimension to our input features, which always equals to 1:

Training Algorithm

In order to train the perceptron, we need to find out weights $\mathbf{w}$ that will minimize the error. The error is defined using perceptron criteria:

$E(\mathbf{w}) = -\sum_{n \in \mathcal{M}}\mathbf{w}^{\mathrm{T}}\mathbf{x}_{n}t_{n}$

• $t_{n} \in \{-1, +1\}$ for negative and positive training samples, respectively
• $\mathcal{M}$ - a set of wrongly classified examples

We will use the process of gradient descent. Starting with some initial random weights $\mathbf{w}^{(0)}$, we will adjust weights on each step of the training using the gradient of $E$:

$\mathbf{w}^{\tau + 1}=\mathbf{w}^{\tau} - \eta \nabla E(\mathbf{w}) = \mathbf{w}^{\tau} + \eta\sum_{n \in \mathcal{M}}\mathbf{x}_{n} t_{n}$

where $\eta$ is a learning rate, and $\tau\in\mathbb{N}$ - number of iteration.

Let's define this algorithm in Python:

Note on Learning Rate: The learning_rate parameter (default 0.01) controls how much we adjust the weights during each training step. This implements the gradient descent update formula:

$\mathbf{w}^{\tau + 1}=\mathbf{w}^{\tau} + \eta \mathbf{x}_{n} t_{n}$

• A larger learning rate (e.g., 1.0) makes the perceptron learn faster but may overshoot the optimal solution
• A smaller learning rate (e.g., 0.001) learns more slowly but may converge more precisely
• You can experiment by calling: train(pos_examples, neg_examples, learning_rate=0.1)

Now let's run the training on our dataset:

As you can see, initial accuracy is around 50%, but it quickly increases to higher values close to 90%.

Let's visualize how classes are separated. Our classification function looks like $\mathbf{w}^Tx$, and it is greater than 0 for one class, and is below 0 for another. Thus, class separation line is defined by $\mathbf{w}^Tx = 0$. Since we have only two dimensions $x_0$ and $x_1$, the equation for the line would be $w_0x_0+w_1x_1+w_2 = 0$ (remember that we have explicitly defined an extra dimension $x_2=1$). Let's plot this line:

Experimenting with Learning Rates

Now let's explore how different learning rates affect the training process. The learning rate controls the step size in gradient descent - a crucial hyperparameter that affects both convergence speed and stability.

Interactive Learning Rate Experiment

Use the slider below to interactively experiment with different learning rates and see how they affect the decision boundary:

Evaluate on Test Dataset

In the beginning, we have put apart some data to the test dataset. Let's see how accurate our classifier is on this test dataset. In order to do this, we also expand the test dataset with an extra dimension, multiply by weights matrix, and make sure that the obtained value is of the same sign as the label (+1 or -1). We then add together all boolean values and divide by the length of test sample, to obtain the accuracy:

Observing the training process

We have seen before how the accuracy decreases during training. It would be nice to see how the separation line behaves during training. The code below will visualize everything on one graph, and you should be able to move the slider to "time-travel" through the training process.

Limitations of the Perceptron

As you have seen above, perceptron is a linear classifier. It can distinguish between two classes well if they are linearly separable, i.e. can be separated by a straight line. Otherwise, perceptron training process will not converge.

A most obvious example of a problem that cannot be solved by a perceptron is so-called XOR problem. We want our perceptron to learn the XOR boolean function, which has the following truth table:

Let's try and do that! We will manually populate all positive and negative training samples, and then call our train function defined above:

As you can see from the graph above, the accuracy never goes above 75%, because it is impossible to draw a straight line in such a way as to get all possible examples right.

The XOR problem is a classical example of perceptron limitations, and it was pointed out by Marvin Minsky and Seymour Papert in 1969 in their book Perceptrons. This observation limited research in the area of neural networks for almost 10 years, even though - and we will see this in the next section of our course - multi-layered perceptrons are perfectly capable of solving such problems.

Complex Example - MNIST

Even though perceptron cannot solve XOR problem, it can solve many more complex problems, such as handwritten character recognition.

A dataset that is often used when mastering machine learning is called MNIST. It has been created by Modified National Institute of Standards and Technology, and contains a training set of 60000 handwritten digits, collected from around 250 students and employees of the institute. There is also a test dataset of 10000 digits, collected from different individuals.

All digits are represented by grayscale images of size 28x28 pixels.

MNIST Dataset is available as a training competition on Kaggle, a site that hosts machine learning competitions and contests. Once you learn how to classify MNIST digits, you can submit your solution to Kaggle to see how it is rated among other participants.

We start by loading MNIST dataset:

Let's now plot the dataset:

Because perceptron is a binary classifier, we will limit our problem to recognizing only two digits. The function below will populate positive and negative sample arrays with two given digits (and will also show samples of those digits for clarity).

We will start by trying to classify between 0 and 1:

Please note how accuracy goes up to almost 100% very fast.

Please, move the slider to some position towards the end of the training, and observe the weight matrix plotted on the left. This matrix will allow you to understand how perceptron actually works. You can see the high weight values in the middle of the field, which correspond to pixels that are typically present for digit 1, and low negative values by the sides, where parts of 0 digit are. So, if the digit presented to the perceptron is in fact 1, middle part of it will be mupliplied by high values, producing positive result. On the contrary, when perceptron observes 0, corresponding pixels will be multiplied by negative numbers.

You may notice that if we give our perceptron a digit 1 slightly shifted horizontally, so that its pixels occupy the place where there are vertical parts of 0, we may receive incorrect result. Since the nature of our MNIST dataset is such that all digits are centered and positioned properly, and perceptron relies on this to distinguish between digits.

Now let's try different digits:

Discussion

For some reason, 2 and 5 are not as easily separable. Even though we get relatively high accuracy (above 85%), we can clearly see how perceptron stops learning at some point.

To understand why this happens, we can try to use Principal Component Analysis (PCA). It is a machine learning technique used to lower the dimensionality of the input dataset, in such a way as to obtain the best separability between classes.

In our case, an input image has 784 pixels (input features), and we want to use PCA to reduce the number of parameter to just 2, so that we can plot them on the graph. Those two parameters would be a linear combination of original features, and we can view this procedure as "rotating" our original 784-dimensional space and observing it's projection to our 2D-space, until we get the best view that separates the classes.

As you can see, 0 and 1 can be clearly separated by a straight line. This indicates that in the original 784-dimensional space dots corresponding to digits are also linearly separable. In the case of 2 and 5, we cannot find the good projection that will separate the digits clearly, and thus there are some cases of wrong classification.

Later on this course we will learn how to create non-linear classifiers using Neural Networks, and how to deal with a problem of digits not being properly aligned. Very soon we will reach above 99% accuracy in MNIST digit classification, while classifying them into 10 different classes.

Takeaway

• We have leart about the simplest neural network architecture - one-layer perceptron.
• We have implemented the perceptron "by hand", using simple training procedure based on gradient descent
• Despite simplicity, one-layered perceptron can solve rather complex problems of handwritten digit recognition
• One-layered perceptron is a liner classifier, and thus it provides the same classification power as logistic regression.
• In the sample space, perceptron can separate two classes of input data using hyperplane.

Credits

This notebook is a part of AI for Beginners Curricula, and has been prepared by Dmitry Soshnikov. It is inspired by Neural Network Workshop at Microsoft Research Cambridge. Some code and illustrative materials are taken from presentations by Katja Hoffmann, Matthew Johnson and Ryoto Tomioka, and from NeuroWorkshop repository.