The Perceptron Algorithm

Why the Margin Matters

The Perceptron is an online learner: it sees one input vector at a time, predicts a label, and receives the true label only afterward. Its central goal is to make as few mistakes as possible. The key question is not only whether it eventually finds a classifier with no mistakes, but also how much work it may require before doing so. The separation margin γ supplies that information.

A training set is separated with margin γ when the positive and negative examples lie on their correct sides of a separating hyperplane, with the minimum signed distance from an example to that separator at least γ. A larger margin means the examples are separated more generously; a smaller positive margin permits examples to lie closer to the boundary.

One Online Round

On round t, the Perceptron receives an input vector x_t from R^d and already has a current weight vector w(t). It uses those two pieces of information to predict. The true label y_t is revealed only after the prediction, so the label is feedback for evaluating the prediction rather than an input used to produce that same prediction.

From Score to Mistake

Updates Before Convergence

When a mistaken example is encountered, the Perceptron updates its weight vector. Repeating this online process changes the current classifier as feedback arrives. For a training set separated with margin γ, the Perceptron makes at most 1/γ² updates before reaching a solution that makes no mistakes on the entire training set. In this context, convergence means obtaining such a mistake-free solution on the whole training set.

Updates as a Compression Set

The same update bound has a second interpretation. Focus on the examples that caused the Perceptron to update. These examples can serve as a compressed representation associated with the learned classifier. Because there are at most 1/γ² updates, the associated compression scheme has size k satisfying k ≤ 1/γ².

When No Finite Guarantee Exists

The margin guarantee is conditional: it applies when the training set is separated with margin γ. It should not be confused with a finite mistake guarantee for every possible online sequence in the hypothesis class. For the stated class when d is at least 2, the Littlestone dimension is infinite. Infinite Littlestone dimension means that few-mistake guarantees are unavailable in general: an adversary can follow a path through a complete mistake tree so that no learner has a finite worst-case mistake bound.

The source supports this conclusion using the density of the real numbers. For d at least 2, it describes vectors such as (1/2, 1, 0, ..., 0), (1/4, 1, 0, ..., 0), and (3/4, 1, 0, ..., 0), together with hypotheses whose parameter vectors have the form (-1, a, 0, ..., 0), where a ranges over [0, 1]. This construction yields a tree shattered by the hypotheses and supports the conclusion that the Littlestone dimension is infinite.

Mistakes in Reasoning

• Treating the true label as available before the prediction

  In the online protocol, y_t is revealed only after the prediction.

  Fix: Compute p_t from w(t) and x_t first, then compare p_t with the revealed y_t.

• Saying that convergence means the Perceptron stops after one update

  Convergence means obtaining a solution with no mistakes on the entire training set.

  Fix: Interpret the update bound as a limit on the total number of updates before reaching a mistake-free solution under margin separation.

• Using 1/γ² as an unconditional mistake bound

  The stated Perceptron guarantee requires a training set separated with margin γ.

  Fix: State the separation condition whenever giving the update guarantee.

• Confusing the update bound with the compression size

  The associated compression scheme is built from update-causing examples, whose number is bounded above by 1/γ².

  Fix: Write the compression bound as k ≤ 1/γ².

• Assuming infinite Littlestone dimension contradicts Perceptron convergence

  The two statements concern different conditions: one uses margin separation, while the other concerns a general worst-case online guarantee for the class.

  Fix: Keep conditional margin-based convergence separate from unrestricted finite mistake guarantees.

Check Your Understanding

Key Takeaways

1. Margin separation means that the examples lie on their correct sides of a separating hyperplane with minimum signed distance at least γ.
2. For a training set separated with margin γ, the Perceptron makes at most 1/γ² updates before reaching a solution with no mistakes on the entire training set.
3. The examples that cause updates form an associated compression scheme of size k ≤ 1/γ².
4. On round t, the Perceptron uses w(t) and x_t to produce p_t = sign(<w(t), x_t>), and only afterward receives y_t to determine whether a mistake occurred.
5. When d is at least 2, infinite Littlestone dimension prevents a finite general worst-case mistake guarantee for the stated class, even though a margin-separated training set has the conditional Perceptron bound.