Perceptrons and Classification

Notes about perceptrons and sigmoid neurons

Perceptron

A Perceptron behaves like a classifier. Suppose we have an input $\mathbf{x}$ which we want to classify as either belonging to a category (labeled as 1) or another category (labeled as 0).

Its inner formula is given by

$$\begin{equation} score=\sum w_{i}x_{i}+b=\mathbf{w^{T}\cdot x}+b\label{eq:Perceptron} \end{equation}$$

Given an input $\mathbf{x}$ , for example $\mathbf{x}=\left(x_{1},x_{2}\right)$ , the Perceptron calculates a score: when $\mathbf{w^{T}\cdot x}+b\geq0$ the input belongs to the category labeled as 1, if $\mathbf{w^{T}\cdot x}+b<0$ the input belongs to a category labeled as 0.

Visually, when the score is positive the input $\mathbf{x}$ lays on the positive side of the half-hyperplane $\mathbf{w^{T}\cdot x}+b\geq0$ , when negative it lays on the other side. The bigger the score the further the input from the line $\mathbf{w^{T\cdot}x}+b=0.$

A common way to define a Perceptron is using a the $sign$ function on the top of the previous score

$$\begin{equation} y=\begin{cases} 1 & \mathbf{w^{T}\cdot x}+b\geq0\\ 0 & otherwise \end{cases}\label{eq:PerceptronFormula} \end{equation}$$

where $y$ represents the expected category. Unfortunately this function is not continuous so we cannot use any known minimization algorithm like Gradient Descent to devise the best parameters $\mathbf{w}$ and b.

Perceptron Learning Rule

If we consider an input vector $\mathbf{x}=\left(x_{1},x_{2},\ldots x_{n},1\right)$ and the weights $\mathbf{w}=\left(w_{1},w_{2},\ldots,w_{n},-b\right)$ we can still write the the Perceptron formula like $\mathbf{w^{T}\cdot x}\geq0$ which is a half-plane divided by a line through the origin, with $\mathbf{w}$ the normal vector to it.

If an input $\tilde{\mathbf{x}}$ is incorrectly classified we can rotate the line, forcing the normal vector $\mathbf{w}$ to move into the same direction of vector $\tilde{\mathbf{x}}$ by adding a small vector $η\tilde{\mathbf{x}}$ .

$$\mathbf{w}'=\mathbf{w}+η\tilde{\mathbf{x}}$$ If we apply this step rule several times, at some time the half-plane will include the input $\tilde{\mathbf{x}}$ and it will be classified correctly. We can also rotate in the opposite direction subtracting the same quantity.

One important thing to notice is that the more a point is mis-classified, the more it takes to realign the weight vector which means a Perceptron is very slow to learn.

Figure 1 Perceptron Learning Rule

This rule is very important because it is very close to what happens when we apply Gradient Descend to a Sigmoid neuron to minimize the Cross-Entropy cost function described later. We can prove that if $y$ is the expected value and $\hat{y}$ is the value predicted by the Sigmoid Neuron for the input $\tilde{\mathbf{x}}$ , in order to better classify the input we need to add to the weight vector $\boldsymbol{w}$ the quantity $\eta\left(y-\hat{y}\right)\tilde{\mathbf{x}}$ $$\mathbf{w}'=\mathbf{w}+η\left(y-\hat{y}\right)\tilde{\mathbf{x}}$$

Please note that $y$ is either 0 or 1 while $\tilde{y}$ can assume any values between 0 and 1.

In this case the learning rate is proportional to the mis-classification, the difference between the expected value and the predicted value, so a Sigmoid Neuron together with a Cross-Entropy cost function is faster to learn.

Sigmoid Neuron

We notice that the original formula gives a very high positive score the more likely is for the input $\mathbf{x}$ to be classified in category 1 and a very negative score the more likely to be classified in category 0. Using this idea we can apply a function on the top of the score to covert all possible scores from the domain $\left[-\infty,\infty\right]$ into the domain $\left[0,1\right]$ . Such formula is the sigmoid function $$\sigma\left(score\right)=\frac{1}{1+e^{-score}}$$

When score is very negative this function becomes 0 and when very positive this function becomes 1. Using this idea we can convert the formula (2) into a continuous function which return a classification probability $\hat{y}$ instead.

$$\hat{y}=\sigma\left(\mathbf{w^{T}\cdot x}+b\right)$$

If we have an input $\mathbf{x}$ which we know belongs to category 1, the probability for this input to be correctly classified will be

$$P\left(\mathbf{x}\in1\right)=\hat{y}$$

If we have an input $\mathbf{x}$ which we know belongs to category 0, the probability of being correctly classified becomes

$$P\left(\mathbf{x}\in0\right)=1-\hat{y}$$

Classification of multiple inputs

Assume now we have a series of inputs and expected categories $\left\{ \left(\mathbf{x_{1}},y_{1}\right),\left(\mathbf{x_{2}},y_{2}\right),\ldots,\left(\mathbf{x_{m}},y_{m}\right)\right\}$ . We want the Perceptron to properly classify all the inputs, i.e. we want to find the weights $\mathbf{w}$ and bias $b$ which maximize the probability for each input to be correctly classified. We create a new probability function multiplying the probability functions for each input.

$$\prod_{i=1}^{m}P\left(\mathbf{x_{i}}\in y_{i}\right)$$

There is a numerical problem with this approach: we multiply a lot of small number all less than 1 which is not a good idea with floating point numbers. A better approach is to use the logarithmic notation and convert the above multiplication into the summation

$$\sum_{i=1}^{m}\ln\left(P\left(\mathbf{x_{i}}\in y_{i}\right)\right)$$

Cross-Entropy cost function

Let’s define $\hat{y}_{i}$ as follows

$$\hat{y}_{i}=\sigma\left(\mathbf{w^{T}\cdot x_{i}}+b\right)$$

When the expected value for the input $\mathbf{x_{i}}$ is $y_{i}=1$ we can write $$\ln\left(P\left(\mathbf{x_{i}}\in y_{i}\right)\right)=y_{i}\ln\left(\hat{y}_{i}\right)$$ When the expected value for the input $\mathbf{x_{i}}$ is $y_{i}=0$ we can write $$\ln\left(P\left(\mathbf{x_{i}}\in y_{i}\right)\right)=\left(1-y_{i}\right)\ln\left(1-\hat{y}_{i}\right)$$

The above summation becomes $$\sum_{i=1}^{m}y_{i}\ln\left(\hat{y}_{i}\right)+\left(1-y_{i}\right)\ln\left(1-\hat{y}_{i}\right)$$

To convert the problem into a minimization problem we can add a minus sign in front of the formula and we obtain what is called Cross-Entropy cost function $$C=-\sum_{i=1}^{m}y_{i}\ln\left(\hat{y}_{i}\right)+\left(1-y_{i}\right)\ln\left(1-\hat{y}_{i}\right)$$

which is the negative logarithm of the probability for each input $\mathbf{x}_{i}$ to be correctly classified.

Softmax Activation Function and Softmax Function

Softmax Activation Function and Softmax Function are two different functions. Softmax Function represents a smoothing version of the $max$ function and it is defined as follows $$sofmax\left(\mathbf{z}\right)=\ln\left(\sum_{i=1}^{n}e^{z_{i}}\right)$$

where $\mathbf{z}=\left(z_{1},z_{2},\ldots,z_{n}\right)$ is the input vector. For example, the discontinuous function $x^{+}=max\left(0,x\right)$ can be approximated by the softplus function $\ln\left(1+e^{x}\right)$ . The derivative of the softplus function is the logistic function $$\sigma\left(x\right)=\frac{1}{1+e^{-x}}$$

The Softmax Activation Function is a generalization of the logistic function. It is used to convert a vector of scores in $\left(-\infty,\infty\right)$ into a vector of probabilities in $\left(0,1\right)$ . It is defined as follows

$$\mathbf{\sigma}\left(\mathbf{z}\right)=\frac{1}{\sum_{i=1}^{n}e^{z_{i}}}\left(e^{z_{1}},e^{z_{2}},\ldots,e^{z_{n}}\right)$$

It is normally used in a multi classification problem, at the output layer of a neural network, to convert output scores into output probabilities like the logistic function.

Derivative of the logistic function

Theorem

The derivative of the logistic $\sigma\left(x\right)$ is

$$\sigma^{'}\left(x\right)=\sigma\left(x\right)\left(1-\sigma\left(x\right)\right)$$

Proof

Let $\sigma\left(x\right)$ be the logistic function defined as $$\sigma\left(x\right)=\frac{1}{1+e^{-x}}$$

We calculate the derivative as follows $$\begin{align*} \sigma^{'}\left(x\right) & =\frac{e^{-x}}{\left(1+e^{-x}\right)^{2}}=\frac{1}{1+e^{-x}}\frac{e^{-x}}{1+e^{-x}}=\frac{1}{1+e^{-x}}\left(1-\frac{1}{1+e^{-x}}\right)\\ & =\sigma\left(x\right)\left(1-\sigma\left(x\right)\right) \end{align*}$$

Training-Loss function

The more training data the bigger is the Cross-Entropy Cost Function. Dividing the Cross-Entropy Cost Function by the number of training data we obtain the Training-Loss Function which is a better measure of the classification error.

Theorem

Assume we have a series of inputs vectors $\mathbf{x}^{\left(1\right)},\mathbf{x}^{\left(2\right)},\ldots,\mathbf{x}^{\left(m\right)}$ with $$\mathbf{x}^{\left(i\right)}=\left(x_{1}^{\left(i\right)},x_{2}^{\left(i\right)},\ldots,x_{n}^{\left(i\right)}\right)^{T}$$ Suppose $y_{i}\in\left\{ 0,1\right\}$ is the expected label for the input $x^{\left(i\right)}$ , $\mathbf{w}=\left(w_{1},w_{2},\ldots w_{n}\right)^{T}$ the weights vector and $\hat{y}_{i}\in\left[0,1\right]$ the prediction value given by $$\hat{y_{i}}=\sigma\left(\mathbf{w}^{T}\mathbf{\cdot x}^{\left(i\right)}+b\right)$$

The gradient of the training-loss function (the average of the cross-entropy cost function) $$E\left(\hat{\mathbf{y}}\right)=-\frac{1}{m}\sum_{i=1}^{m}\left(y_{i}\ln\left(\hat{y}_{i}\right)+\left(1-y_{i}\right)\ln\left(1-\hat{y}_{i}\right)\right)$$

is given by

$$\nabla E=-\frac{1}{m}\sum_{i=1}^{m}\left(y_{i}-\hat{y_{i}}\right)\left(\mathbf{x}^{\left(i\right)},1\right)$$

Proof

The gradient of $E$ is given by the partial derivatives

$$\nabla E=\left(\frac{\partial E}{\partial w_{1}},\frac{\partial E}{\partial w_{2}},\ldots,\frac{\partial E}{\partial b}\right)$$

Using Gradient Descend we can use $\nabla E$ to change $\mathbf{w}$ and $b$ to minimize the error function $E$

$$\left(\mathbf{w}',b'\right)=\left(\mathbf{w},b\right)+\alpha\nabla E$$

Let’s call $E_{i}$ the i-th element of the summary above

$$E_{i}\left(\hat{y_{i}}\right)=y_{i}\ln\left(\hat{y}_{i}\right)+\left(1-y_{i}\right)\ln\left(1-\hat{y}_{i}\right)$$

We first calculate the derivative of $E_{i}$ with respect to $\hat{y}_{j}$

$$\frac{\partial E_{i}}{\partial\hat{y}_{i}}=\frac{y_{i}}{\hat{y_{i}}}-\frac{1-y_{i}}{1-\hat{y_{i}}}=\frac{y_{i}-y_{i}\hat{y}-\hat{y_{i}}+y_{i}\hat{y}}{\hat{y_{i}}\left(1-\hat{y_{i}}\right)}=\frac{y_{i}-\hat{y_{i}}}{\hat{y_{i}}\left(1-\hat{y_{i}}\right)}$$

Then we calculate the derivatives of the prediction $\hat{y}_{i}$ with respect to $w_{j}$ and $b$

$$\begin{align*} \frac{\partial\hat{y_{i}}}{\partial w_{j}} & =\frac{\partial}{\partial w_{j}}\sigma\left(\mathbf{w}^{T}\mathbf{\cdot}\mathbf{x}^{\left(i\right)}+b\right)\\ & =\sigma\left(\mathbf{w}^{T}\mathbf{}\mathbf{x}^{\left(i\right)}+b\right)\left(1-\sigma\left(\mathbf{w}^{T}\mathbf{\cdot x}^{\left(i\right)}+b\right)\right)\frac{\partial}{\partial w_{j}}\left(\mathbf{w}^{T}\mathbf{\cdot x}^{\left(i\right)}+b\right)\\ & =\hat{y_{i}}\left(1-\hat{y_{i}}\right)\frac{\partial}{\partial w_{j}}\left(\mathbf{w}^{T}\mathbf{\cdot x}^{\left(i\right)}+b\right)\\ & =\hat{y_{i}}\left(1-\hat{y_{i}}\right)\left(w_{1}x_{1}^{\left(i\right)}+w_{2}x_{2}^{\left(i\right)}+\ldots+w_{j}x_{j}^{\left(i\right)}+\ldots+w_{n}x_{n}^{\left(i\right)}+b\right)\\ & =\hat{y_{i}}\left(1-\hat{y_{i}}\right)x_{j}^{\left(i\right)}\\ \\ \frac{\partial\hat{y_{i}}}{\partial b} & =\hat{y_{i}}\left(1-\hat{y_{i}}\right) \end{align*}$$

Combining the two using the chain rule we obtain

$$\begin{align*} \frac{\partial E_{i}}{\partial w_{j}} & =\frac{\partial E_{i}}{\partial\hat{y}_{i}}\frac{\partial\hat{y_{i}}}{\partial w_{j}}=\left(y_{i}-\hat{y_{i}}\right)x_{j}^{\left(i\right)}\\ \\ \frac{\partial E_{i}}{\partial b} & =\frac{\partial E_{i}}{\partial\hat{y}_{i}}\frac{\partial\hat{y_{i}}}{\partial b}=\left(y_{i}-\hat{y_{i}}\right) \end{align*}$$

From this it follows that

$$\begin{align*} \frac{\partial E}{\partial w_{j}} & =-\frac{1}{m}\sum_{i=1}^{m}\frac{\partial E_{i}}{\partial\hat{y}_{i}}\frac{\partial\hat{y_{i}}}{\partial w_{j}}=-\frac{1}{m}\sum_{i=1}^{m}\left(y_{i}-\hat{y_{i}}\right)x_{j}^{\left(i\right)}\\ \\ \frac{\partial E}{\partial b} & =-\frac{1}{m}\sum_{i=1}^{m}\frac{\partial E_{i}}{\partial\hat{y}_{i}}\frac{\partial\hat{y_{i}}}{\partial b}=-\frac{1}{m}\sum_{i=1}^{m}\left(y_{i}-\hat{y_{i}}\right) \end{align*}$$

$$\begin{align*} \nabla E & =-\frac{1}{m}\sum_{i=1}^{m}\left(\frac{\partial E_{i}}{\partial w_{1}},\frac{\partial E_{i}}{\partial w_{2}},\ldots,\frac{\partial E_{i}}{\partial b}\right)\\ & =-\frac{1}{m}\sum_{i=1}^{m}\left(\left(y_{i}-\hat{y_{i}}\right)x_{1}^{\left(i\right)},\left(y_{i}-\hat{y_{i}}\right)x_{2}^{\left(i\right)},\ldots,\left(y_{i}-\hat{y_{i}}\right)x_{n}^{\left(i\right)},\left(y_{i}-\hat{y_{i}}\right)\right)\\ & =-\frac{1}{m}\sum_{i=1}^{m}\left(y_{i}-\hat{y_{i}}\right)\left(x_{1}^{\left(i\right)},x_{2}^{\left(i\right)},\ldots,x_{n}^{\left(i\right)},1\right)\\ & =-\frac{1}{m}\sum_{i=1}^{m}\left(y_{i}-\hat{y_{i}}\right)\left(\mathbf{x}^{\left(i\right)},1\right) \end{align*}$$

Validation Accuracy and Test Accuracy

Let define $\mathbf{\hat{Y}}$ as the matrix where each row represents the classification probabilities for a given sample. In the example below we have 7 classes and 5 samples. $\mathbf{Y}$ is the matrix where each row represents the correct classifications with one‑hot labels. $\mathbf{V}$ is the vector indicating with 1 a correct prediction and with 0 a wrong prediction.

$$\begin{array}{cc} \mathbf{\hat{Y}}=\left[\begin{array}{ccccccc} 0.1 & 0.0 & 0.2 & 0.0 & 0.7 & 0.0 & 0.0\\ 0.0 & 0.0 & 0.9 & 0.1 & 0.0 & 0.0 & 0.0\\ 0.0 & 0.1 & 0.1 & 0.2 & 0.6 & 0.0 & 0.0\\ 0.1 & 0.2 & 0.6 & 0.0 & 0.0 & 0.0 & 0.1\\ 0.2 & 0.0 & 0.0 & 0.0 & 0.0 & 0.8 & 0.0 \end{array}\right] & \mathbf{Y}=\left[\begin{array}{ccccccc} 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right]\end{array}$$

$$\mathbf{V}=\left[\begin{array}{c} 1\\ 0\\ 1\\ 1\\ 0 \end{array}\right]$$

The validation accuracy, measured on the given validation samples, is the average of all values of $\mathbf{V}$ .

In our example $$validation~accuracy=\left(1+0+1+1+0\right)/5=3/5=60\%$$

The validation accuracy is 100% only when all predictions made on the given validation samples are correct. The test accuracy follows the same idea but it is measured on all test samples instead.