Deep Learning From Scratch - Theory and Implementation

DanielSabinasz

360.3K views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

Previous: Computational Graphs Next: Training Criterion

Perceptrons

A motivating example

Perceptrons are a miniature form of neural network and a basic building block of more complex architectures. Before going into the details, let's motivate them by an example. Assume that we are given a dataset consisting of 100 points in the plane. Half of the points are red and half of the points are blue.

Example

As we can see, the red points are centered at $(- 2, - 2)$ and the blue points are centered at $(2, 2)$ . Now, having seen this data, we can ask ourselves whether there is a way to determine if a point should be red or blue. For example, if someone asks us what the color of the point $(3, 2)$ should be, we'd best respond with blue. Even though this point was not part of the data we have seen, we can infer this since it is located in the blue region of the space.

But what is the general rule to determine if a point is more likely to be blue than red? Apparently, we can draw a line $y = - x$ that nicely separates the space into a red region and a blue region:

Example

We can implicitly represent this line using a weight vector $w$ and a bias $b$ . The line then corresponds to the set of points $x$ where

w^{T} x + b = 0

In the case above, we have $w = (1, 1)^{T}$ and $b = 0$ . Now, in order to test whether the point is blue or red, we just have to check whether it is above or below the line. This can be achieved by checking the sign of $w^{T} x + b$ . If it is positive, then $x$ is above the line. If it is negative, then $x$ is below the line. Let's perform this test for our example point $(3, 2)^{T}$ :

(\begin{matrix} 1 & 1 \end{matrix}) \cdot (\begin{matrix} 3 \\ 2 \end{matrix}) = 5

Since 5 > 0, we know that the point is above the line and, therefore, should be classified as blue.

Perceptron definition

In general terms, a classifier is a function $\hat{c} : R^{d} \to {1, 2, . . ., C}$ that maps a point onto one of $C$ classes. A binary classifier is a classifier where $C = 2$ , i.e. we have two classes. A perceptron with weight $w \in R^{d}$ and bias $b \in R^{d}$ is a binary classifier where

\hat{c} (x) = {\begin{cases} 1, & if w^{T} x + b \geq 0 \\ 2, & if w^{T} x + b < 0 \end{cases}

$\hat{c}$ partitions $R^{d}$ into two half-spaces, each corresponding to one of the two classes. In the 2-dimensional example above, the partitioning is along a line. In general, the partitioning is along a $d - 1$ dimensional hyperplane.

From classes to probabilities

Depending on the application, we may be interested not only in determining the most likely class of a point, but also the probability with which it belongs to that class. Note that the higher the value of $w^{T} x + b$ , the higher is its distance to the separating line and, therefore, the higher is our confidence that it belongs to the blue class. But this value can be arbitrarily high. In order to turn this value into a probability, we need to "squash" the values to lie between 0 and 1. One way to do this is by applying the sigmoid function $σ$ :

p (\hat{c} (x) = 1 ∣ x) = σ (w^{T} x + b) where σ (a) = \frac{1}{1 + e^{- a}}

Let's take a look at what the sigmoid function looks like:

Sigmoid plot

As we can see, the sigmoid function assigns a probability of 0.5 to values where $w^{T} x + b = 0$ (i.e. points on the line) and asymptotes towards 1 the higher the value of $w^{T} x + b$ becomes, and towards 0 the lower it becomes, which is exactly what we want.

Let's now define the sigmoid function as an operation, since we'll need it later:

Sigmoid

class sigmoid(Operation):
    """Returns the sigmoid of x element-wise.
    """
    def __init__(self, a):
        """Construct sigmoid
        Args:
          a: Input node
        """
        super().__init__([a])
    def compute(self, a_value):
        """Compute the output of the sigmoid operation
        Args:
          a_value: Input value
        """
        return 1 / (1 + np.exp(-a_value))

The entire computational graph of the perceptron now looks as follows:

Example

Using what we have learned, we can now build a perceptron for the red/blue example in Python.

Building a Perceptron

Let's use this perceptron to compute the probability that $(3, 2)^{T}$ is a blue point:

Using the Perceptron

Multi-class perceptron

So far, we have used the perceptron as a binary classifier, telling us the probability $p$ that a point $x$ belongs to one of two classes. The probability of $x$ belonging to the respective other class is then given by $1 - p$ . Generally, however, we have more than two classes. For example, when classifying an image, there may be numerous output classes (dog, chair, human, house, ...). We can extend the perceptron to compute multiple output probabilities.

Let $C$ denote the number of output classes. Instead of a weight vector $w$ , we introduce a weight matrix $W \in R^{d \times C}$ . Each column of the weight matrix contains the weights of a separate linear classifier - one for each class. Instead of the dot product $w^{T} x$ , we compute $x W$ , which returns a vector in $R^{C}$ , each of whose entries can be seen as the output of the dot product for a different column of the weight matrix. To this, we add a bias vector $b \in R^{C}$ , containing a distinct bias for each output class. This then yields a vector in $R^{C}$ containing the probabilities for each of the $C$ classes.

While this procedure may seem complicated, the matrix multiplication actually just performs multiple linear classifications in parallel, one for each of the $C$ classes - each one with its own separating line, given by a weight vector (one column of $W$ ) and a bias (one entry of $b$ ).

Softmax

While the original perceptron yielded a single scalar value that we squashed through a sigmoid to obtain a probability between 0 and 1, the multi-class perceptron yields a vector $a \in R^{m}$ . The higher the i-th entry of $a$ , the higher is our confidence that the input point belongs to the i-th class. We would like to turn $a$ into a vector of probabilities, such that the probability for every class lies between 0 and 1 and the probabilities for all classes sum up to 1.

A common way to do this is to use the softmax function, which is a generalization of the sigmoid to multiple output classes:

σ (a)_{i} = \frac{e^{a_{i}}}{\sum_{j = 1}^{C} e^{a_{j}}}

Softmax

class softmax(Operation):
    """Returns the softmax of a.
    """
    def __init__(self, a):
        """Construct softmax
        Args:
          a: Input node
        """
        super().__init__([a])
    def compute(self, a_value):
        """Compute the output of the softmax operation
        Args:
          a_value: Input value
        """
        return np.exp(a_value) / np.sum(np.exp(a_value), axis=1)[:, None]

Batch computation

The matrix form allows us to feed in more than one point at a time. That is, instead of a single point $x$ , we could feed in a matrix $X \in R^{N \times d}$ containing one point per row (i.e. $N$ rows of $d$ -dimensional points). We refer to such a matrix as a batch. Instead of $x W$ , we compute $X W$ . This returns an $N \times C$ matrix, each of whose rows contains $x W$ for one point $x$ . To each row, we add a bias vector $b$ , which is now an $1 \times m$ row vector. The whole procedure thus computes a function $f : R^{N \times d} \to R^{m}$ where $f (X) = σ (X W + b)$ . The computational graph looks as follows:

Example

Let's now generalize our red/blue perceptron to allow for batch computation and multiple output classes.

Multi-class Perceptron

# Create a new graph
Graph().as_default()
X = placeholder()
# Create a weight matrix for 2 output classes:
# One with a weight vector (1, 1) for blue and one with a weight vector (-1, -1) for red
W = Variable([
    [1, -1],
    [1, -1]
])
b = Variable([0, 0])
p = softmax( add(matmul(X, W), b) )
# Create a session and run the perceptron on our blue/red points
session = Session()
output_probabilities = session.run(p, {
    X: np.concatenate((blue_points, red_points))
})
# Print the first 10 lines, corresponding to the probabilities of the first 10 points
print(output_probabilities[:10])

Since the first 10 points in our data are all blue, the perceptron outputs high probabilities for blue (left column) and low probabilities for red (right column), as expected.

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content

Open Source Your Knowledge, Become a Contributor

2/6 Perceptrons

Perceptrons

A motivating example

Perceptron definition

From classes to probabilities

Example

Multi-class perceptron

Softmax

Batch computation

Example

Handwritten Digit Recognition Using scikit-learn

PYTHON: BEGINNER QUIZ (10 Questions)

PYTHON STRING METHODS: center(), rjust() and ljust().

Python from Zero to Hero