[Statistical Learning Methods Notes 02] Perceptron

I. Perceptron Model

The perceptron is a linear binary classification model. Its input is an instance’s feature vector, and its output is the instance’s class. Its goal is to find a separating hyperplane that linearly divides the training data.

Suppose the input space is $X\subseteq R^n$ and the output space is $Y=\{+1,-1\}$. The input $x\in X$ represents an instance’s feature vector, corresponding to a point in the input space. The output $y\in Y$ represents the instance’s class. The function from the input space to the output space is:

$f(x)=sign(w\cdot x+b)$

This function is called a perceptron. Here, $w$ is the weight vector, $b$ is the bias, and sign is the sign function sign(x)= {+1(if x>=0), -1(if x<0)}.

II. Perceptron Learning Strategy

2.1 Linear Separability of a Dataset

Given a dataset, if a hyperplane exists that can correctly place all positive and negative instances on opposite sides of the hyperplane, the dataset is called a linearly separable dataset. Otherwise, it is called linearly inseparable.

2.2 Learning Strategy

The distance from any point $x_0$ in the input space to hyperplane S is: $\frac{1}{||w||}|w\cdot x_0+b|$

Therefore, the distance from a misclassified point to hyperplane S is: $-\frac{1}{||w||}y_i(w\cdot x_0+b)$

The total distance of all misclassified points, namely the loss function, is: $L(w,b)=-\sum_{i=0}^M y_i(w\cdot x_0+b)$

Clearly, the loss function is nonnegative. The perceptron learning strategy is to find the model parameters $w,b$ in the hypothesis space that minimize the loss function.

2.3 Learning Algorithm

The perceptron learning algorithm uses stochastic gradient descent. Each time, it randomly selects a misclassified point and performs a gradient-descent update.

Input: linearly separable dataset T and learning rate $\eta$

Output: perceptron model $w,b$

(1) Choose initial values $w_0,b_0$ (2) Select data $(x_i,y_i)$ from the training set (3) If $y_i(w\cdot x_i+b)\le0$, update the parameters as $w=w+\eta y_i x_i$ and $b=b+\eta y_i$, where $\eta$ is the learning rate and the latter terms are the gradients of the two parameters (4) Repeat the preceding process until there are no misclassified points in the training set

When the training dataset is linearly separable, the perceptron learning algorithm converges. That is, after a finite number of iterations, it can find a separating hyperplane that correctly separates all training data.

III. Exercise

3.1 Why the Perceptron Cannot Represent XOR

Plotting the distribution of the training set makes it easy to see that a single linear plane cannot separate the + and - regions.