0. Quick overview¶

This notebook gives an introduction to the Perceptron and Gradient Descent algorithms.

The Perceptron algorithm represents the smallest building block of many modern neural network architectures. Conceptually, it is loosely inspired by the basic processing steps of biological neurons.

The Gradient Descent algorithm, on the other hand, provides the backbone of modern deep learning and allows you to fit the Perceptron (as well as more complex deep learning architectures) to a dataset; By finding the set of parameters that achieve the best performance in a task (e.g., deciding whether an image depicts a flower or not).

1. The iris dataset¶

In this notebook, we will be using the Iris dataset.

This dataset contains three classes with 50 instances each; Each class refers to a type of iris plant (setosa, versicolor, and virginica). For each instance, the width and length of the petal and sepal is given (see below).

Image adapted from: https://www.pexels.com/search/iris%20flower/

We load the data directly from the scikit-learn library:

data is a dictionary with the following keys (or entries):

The iris type is encoded in the target entry:

The corresponding name of each iris type can be found in target_names:

The length and width of the sepal and petal of each instance are given in the data entry:

data contains 4 features (one per column) for each of 150 instances (one per row):

The corresponding name of each feature is given in feature_names:

Let's take a closer look at the data, by plotting the data according to the sepal width and length (left) as well as the petal width and length (right):

2. Distinguishing setosa and versicolor irises by petal length and witdh:¶

For simplicity, we will only focus on setosa and versicolor irises and try to distinguish them by their petal width and length.

To do this, we will first subset our data to the classes 0 and 1 (setosa and versicolor) as well as the feature columns 2 and 3 (petal length and width):

Our data subset now contains 100 instances (50 for each of the two iris types) and 2 features per instance:

Looking at the data, distinguishing the two iris types should be easy (as we could simply draw a line between the yellow and blue dots):

But how can we learn this decision boundary (separating setosa and versicolor irises) with a classifier?

3. The Perceptron¶

In the following, we will use the Perceptron algorithm to learn a decision boundary separating the two iris types.

3.1 Inspired by biological neurons:¶

The Perceptron algorithm is loosely inspired by biological neurons.

A biological neuron receives signals of variable magnitude through its dendrites. These input signals are then accumulated in the cell body; If the accumulated signal exceeds a certain threshold, the neuron outputs a signal through its axon:

source: https://sebastianraschka.com/Articles/2015_singlelayer_neurons.html

3.2 Implementation¶

The Perceptron algorithm implements these basic biological processing steps as follows:

1. It receives an input signal for each feature $x_i$ of a data instance (in our example, the length and width of the petal).

2. These input signals are then scaled through a set of weights $w$ (one for each feature $x_i$ of the input) and summed (mimicking the "cell body" of the neuron; note that we here also add a constant $b$ to the sum (the bias)): $\sum_i w_ix_i + b$

3. Lastly, the weighted sum is scaled through an activation function $\phi$, representing the output of the perceptron.

The activation function $\phi$:¶

The classical Percpetron algorithm uses a step activation function which outputs a value of 1 if the weighted sum is bigger than 0 and -1 otherwise.

Here, we will be using the sigmoid activation function instead. The sigmoid scales its input to a value between 0 and 1. It can thereby be used to estimate a probability that each data instance belongs to class 1 (i.e., versicolor irises).

4. The loss function¶

We have decided on an architecture for our classifcation algorithm.

How do we now determine the set of weights $w$ that allow us to best distinguish between the two iris types?

To do this, we need to define a loss function. Conceptually, a loss function indicates the current error of the model, given a set of parameter weights. For our perceptron algorithm, we can use the binary cross-entropy loss:

$L = -(y \times log(p) + (1-y) \times log(1-p))$

The cross-entropy loss consists of two main components: one applies if $y = 1$ and the other if $y = 0$.

Let's look at these two parts of the loss in more detail:

We can see that the first part of the loss ($-log(p)$; in blue) is minimal when the prediction $p(y=1)$ (or $\phi(x)$) of our model is close to $1$. Similarly, the second part of the loss ($-log(1-p)$; in red) is minimal when the prediction $p(y=1)$ of our model is close to $0$.

Hence, the cross-entropy loss is minimal if our predicted probabilities are as close as possible to the actual target classes (0 and 1). It will thus be our goal to find the set of weights $w$ that overall minimizes the cross-entropy loss.

For our binary classification problem we can actually take a look at how the loss function changes as a function of the two weights of our perceptron (one for each feature of the data (petal width and length) see below).

Note that we fix the bias parameter $b$ for illustrative purposes in this analysis.

To get a better feeling for the slope (or steepness) of the loss surface, let's also look at this in 3D:

Ok! This is a pretty steep descent with a very clear valley; Finding a minimum should be easy!

But how do we find the minimum of our loss surface?

5. (Stochastic) gradient descent¶

Gradient descent is one of the most central techniques of modern machine learning. Its goal is to find a (local) minimum of a loss function, given an input dataset.

We have already seen that our loss function changes with the values of our two Perceptron weights $w$.

To find the weights that minimize the loss function, gradient descent procedes as follows:

1. First, it initializes the weights randomly (here, between -1 and 1).

2. Subsequently, it computes the partial derivative of the loss function with respect to the current weights (we denote this partial dericative by: $\frac{dL}{dw}$). This partial derivative indicates how much the loss function changes at its current value w.r.t. a change in $w$:

   • A negative derivative indicates that the loss decreases with an increase in $w$
   • A positive derivative indicates that the loss increases with an increasing $w$.

3. Thus, to move closer to the minimum of the loss, gradient descent simply subtracts the partial derivative from the current set of weights $w = w - \alpha \times \frac{dL}{dw}$. Note that we also scale the derivative by $\alpha$ (the learning rate), allowing us to adjust the overall size of the step that we take at each iteration.

4. The gradient descent algorithm then procedes to iteratively repeat steps 2 and 3 until it reaches a (local) minimum of the loss function. Typically, we know that we have reached a (local) minimum when the partial derivatives (and thereby the weights) do not change much anymore (as the partial derivatives should be close to 0 at a minimum of the loss function).

Note that the loss function is typically more complex for high-dimensional parameter spaces than indicated by our illustration below. In these high-dimensional settings, there often exist many different local minima of the loss function (each representing a distinct set of paramater weights) which result in a very similar overall loss value. Knowing whether your algorithm has converged on any of these local mimima or the overall global minimum (indicating the overall lowest loss value) is difficult. Therefore it is often advised to repeatedly fit your algorithm to your dataset with different random initializations and to see how this changes the performance of your classifier. For a more detailed review on this, see for example this blog post.

6. Our Perceptron implementation¶

Now that we have learned about the Perceptron and gradient descent, let's put it all together:

7. Applying our implementation¶

Can our Perceptron implementation actually learn a decision boundary that allows us to accurately distinguish between setosa and versicolor irises, given their petal length and width?

To give better insight into the training process, we will perform each gradient descent step manually, by the use of the predict, loss, and gradient_descent_step functions of our Perceptron implementation (This process is otherwise also wrapped in the train function).

Note that we do not use the full dataset to update our weights at each iteration, but instead draw a random sample at each iteration. We use each random sample to compute an estimate of our partial derivatives. This procedure is called stochastic gradient descent and is common in the machine learning literature, especially for large datasets (for which it would be otherwise too costly to compute the partial derivatives for the entire dataset at each iteration).

Ok, lets take a look at the results:

Interesting; It looks like we choose a learning rate that was a bit too large: The first gradient descent step took us all the way across the valley!

Luckily, we then from there traveled safely down to a minimum. Our final weight values are marked by the red cross.

Also note how the individual steps are getting smaller towards the end (traveling the distance between the last two points took 30,000 weight updates).

8. The learned decision function¶

Now that we have a parameter estimate (as marked with the red cross in the plot above), we can test whether our trained Perceptron accurately distinguishes between setosa and versicolor irises!

To do this, we will plot its decision boundary:

Yay! Our perceptron accurately distinguishes the two iris types.

Importantly, the decision boundary of the Perceptron represents a hyperplane (a subspace whose dimension is one less than that of the input data; for two-dimensional data, the decision boundary thus represents a straight line).

9. Your Exercise¶

To give you a more intuitive understanding of the interplay between the number of iterations, the batch size, and the learning rate of the gradient descent algorithm, play around with them in the code below.

The code will output a figure of the loss surface, your gradient descent steps, and final loss value.

1. What would be a good learning rate and batch size for this problem?

2. What is the smallest loss that you can achieve?