Perceptron

The perceptron is the simplest neural network: a linear binary classifier that learns a hyperplane by making “lazy” updates only on mistakes.

• A MLP just stacks multiple of these per layer, and increases the number of layers
• The simplest perceptron doesn’t even have an Activation Function, the output is just $\text{sign}(⟨w,x⟩+b)$

Setup: Binary Classification

Given pairs $(x_1,y_1),\dots ,(x_n,y_n)$ with feature vectors $x_i\in {\mathbf{R}}^d$ and labels $y_i\in \{-1,+1\}$. Learn $h:{\mathbf{R}}^d\to \{-1,+1\}$ such that $h(x)=y$.

Assumption

The data is linearly separable: there exists some hyperplane that perfectly splits the classes.

Algorithm

Weight vector $w$, bias $b$. Typically initialize $w=0,b=0$, set $\delta =0$.

For each $(x_i,y_i)$:

• Predict ${\hat{y}}_i=\text{sign}(⟨w,x_i⟩+b)$
• Lazy update (only on a mistake): if ${\hat{y}}_i\ne y_i$, then $w\leftarrow w+y_i{x}_i$ and $b\leftarrow b+y_i$

Intuition

The update rotates $w$ toward $y_i{x}_i$. If we got the sign wrong on $x_i$, nudging $w$ in the direction of $y_i{x}_i$ increases $⟨w,x_i⟩\cdot y_i$ next time, pushing the hyperplane to put $x_i$ on the right side. It is the minimal local correction that makes this one point less wrong.

Padding + Pre-Multiplication Trick

To absorb the bias into the weight vector and simplify the analysis:

• Let $z=(w,b)$ and replace $x_i$ with $(x_i,1)$. Then $y_i=\text{sign}(⟨z,(x_i,1)⟩)$
• Let $a_i=y_i(x_i,1)$. Then the goal becomes $⟨z,a_i⟩>0$ for all $i$, i.e., $Az>0$ entrywise, where $A$ is the matrix with rows $a_i$

Linear Separability and Margin

The dataset is separable with margin $s>0$ if there exists $z$ such that $⟨a_i,z⟩\ge s$ for all $i$. The (normalized) margin is

$\gamma ={\max }_{\Vert z{\Vert }_2=1}{\min }_i⟨a_i,z⟩$

where:

• $\gamma$ is the (normalized) margin
• $a_i$ are the (padded, signed) data points
• $z$ is a unit-norm candidate separator

Large margin means easy to classify; small margin means hard.

Geometric picture

The margin is the width of the thickest slab you can draw between the two classes. A wide slab means small perturbations in the data cannot flip a point’s side, so any reasonable separator works. A razor-thin slab means the boundary has to be threaded precisely.

Perceptron Convergence Theorem (Mistake Bound)

Theorem. Suppose there exists $z=(w,b)$ such that $Az\ge s\cdot 1$. Then the perceptron correctly classifies the entire dataset after at most

$\frac{R^2\Vert z{\Vert }_2^2}{s^2}$

where:

• $R={\max }_i\Vert a_i{\Vert }_2$ is the largest data-point norm
• $s$ is a margin witness
• $z$ is the corresponding separator

Minimizing over the non-unique $(z,s)$ pairs (note $Az\ge s1\Rightarrow A(2z)\ge (2s)1$) gives the bound in terms of the margin:

$\text{mistakes}\le \frac{R^2}{{\gamma }^2}$

Intuition:

• a large $R$ (points far from the origin) makes each update less effective
• a small margin $\gamma$ means fewer directions work
• mistakes are bounded by $(R/\gamma {)}^2$, not by $n$: feed the algorithm a million easy points and it still halts quickly, while a small but tight dataset can dominate the cost

Termination

When do we stop?

• All points classified correctly (training error stops decreasing)
• Validation error stops decreasing
• Budget exhausted, or weights stop changing

Not linearly separable

The algorithm never halts: perceptron will “cycle.” It is not the right algorithm for non-separable data. Use Logistic Regression or soft-margin SVM instead.

Uniqueness

Perceptron finds some separator, not the best one. SVM picks the max-margin separator, which generalizes better.

Multiclass Extensions

• One-versus-all: train $k$ classifiers (dog vs not dog, etc.), predict $\arg {\max }_i⟨z_i,x⟩$
• One-versus-one: train $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ pairwise classifiers, take majority vote

From CS480 lec1.

Related

• Neural Network
• Logistic Regression
• Support Vector Machine
• CS480