Perceptron Algorithm for Halfspaces

The Learner’s Main Loop

The Perceptron is a learner that repeatedly checks labeled training examples against its current weight vector. It starts with a zero vector. If an example fails the required positive condition, the Perceptron changes its weights using that example. If no example fails, it stops and outputs the current weight vector.

Checking the Update Condition

At iteration t, the Perceptron looks for a training example (xi, yi) satisfying yi〈w(t), xi〉 ≤ 0. Here, w(t) is the current weight vector, xi is the selected feature vector, and yi is its label. Finding such an index means the current vector has not achieved the required strictly positive condition for that example, so an update is performed.

yi〈w(t), xi〉 ≤ 0

Tracing One Update

Online Prediction Rounds

The Perceptron can also be viewed as an online learner. On round t, it first receives one input vector xt from R^d. It uses the current weight vector w(t) to predict a label, and only afterward receives the true label yt. The true label is feedback after the prediction, not information used to produce that same prediction.

pt = sign(〈w(t), xt〉)

After the prediction, the learner compares pt with the revealed true label yt. A prediction mistake occurs when the predicted label does not match the true label. The current weight vector and the incoming input therefore determine the prediction, while the later label reveals whether that prediction was correct.

When the Algorithm Converges

For separable data, the Perceptron converges within at most (RB)^2 iterations. The quantity R is the maximum norm of the feature vectors xi. The quantity B is the minimum norm of a vector w satisfying yi〈w, xi〉 ≥ 1 for every training example.

The stopping condition and the convergence statement describe the same successful outcome from two views. Algorithmically, the Perceptron stops when no example satisfies yi〈w(t), xi〉 ≤ 0. Equivalently, every training example then satisfies yi〈w(t), xi〉 > 0.

Mistakes to Catch

• Updating when the condition is not satisfied.

  The Perceptron updates only when some example satisfies yi〈w(t), xi〉 ≤ 0.

  Fix: Check the inequality first, and stop if no example satisfies it.

• Adding xi instead of yi xi.

  The label determines the signed contribution of the selected example.

  Fix: Use w(t+1) = w(t) + yi xi for the same selected index i.

• Stopping immediately after an update.

  An update changes the current vector but does not establish that all examples now satisfy the positive condition.

  Fix: Return to the checking step after every update.

• Using the true label before making an online prediction.

  In the online sequence, xt arrives first, the learner predicts, and yt is revealed afterward.

  Fix: Compute pt from w(t) and xt, then use yt as feedback.

Limits of General Guarantees

The convergence guarantee for separable training data should not be confused with a finite mistake guarantee for every possible online sequence in the stated class. When the dimension d is at least 2, the Littlestone dimension is infinite, so few-mistake guarantees are unavailable for that class.

The source attributes this infinite Littlestone dimension to the density of the real numbers. It describes a shattered tree built from vectors including (1/2, 1, 0, ..., 0), (1/4, 1, 0, ..., 0), and (3/4, 1, 0, ..., 0). The hypotheses use parameter vectors of the form (-1, a, 0, ..., 0), where a ranges over [0, 1]. This construction supports the conclusion that no finite mistake bound applies generally when d is at least 2.

Practice Check

Key Takeaways

1. The Perceptron begins with a zero weight vector and checks whether any example satisfies yi〈w(t), xi〉 ≤ 0.
2. When such an example is found, the update is w(t+1) = w(t) + yi xi using the selected example's label and input.
3. The algorithm checks again after an update and stops only when every example satisfies yi〈w(t), xi〉 > 0.
4. For separable data, convergence occurs within at most (RB)^2 iterations, with R defined from the feature-vector norms and B from the separating-vector condition.
5. In online learning, the learner receives xt, predicts using sign(〈w(t), xt〉), then receives yt and checks for a mistake; when d is at least 2, infinite Littlestone dimension prevents a finite general mistake guarantee.