Hypothesis Class Complexity
The Perceptron predicts online from a weight vector and an incoming input vector.
One Decision at a Time
The Perceptron is an online learner. It does not receive a complete training set before making decisions. Instead, it works one round at a time: it receives the current input vector, uses its current weight vector to predict a label, and only afterward receives the true label. This ordering is the key to understanding both its predictions and its mistakes.
The Online Round
- At round t, the learner receives one input vector x_t from R^d.
- The learner uses its current weight vector w(t) together with x_t to produce a label prediction.
- After the prediction has been made, the true label y_t is revealed.
- The learner checks whether its prediction agrees with the revealed true label.
Tracing a Single Round
Describe what the Perceptron knows before and after it predicts on round t.
Before prediction: The Perceptron has its current weight vector w(t) and receives the incoming input vector x_t. The true label y_t has not yet been revealed for this prediction.
Prediction: The Perceptron combines w(t) and x_t through the rule p_t = sign(<w(t), x_t>).
After prediction: The true label y_t is revealed. The learner can now determine whether its prediction was a mistake.
The round has two distinct stages: predict from w(t) and x_t, then evaluate the prediction after y_t is revealed.
From Vectors to Labels
p_t = sign(<w(t), x_t>)The current weight vector and the incoming input vector determine the prediction together. Their inner product produces the score used by the Perceptron's prediction rule, and applying sign to that score produces the label prediction p_t. The true label is not part of this calculation because it is revealed only after the prediction.
Reading the Prediction Rule
What information is required to calculate p_t?
Identify the current state: Use the current weight vector w(t), not a future or later weight vector.
Read the incoming example: Use the input vector x_t received on round t.
Combine the vectors: Compute their inner product, written as <w(t), x_t>.
Convert the score: Apply sign to the inner product to obtain p_t.
The prediction depends on the current weight vector and current input vector through p_t = sign(<w(t), x_t>).
Recognizing a Mistake
A prediction mistake can be evaluated only after the true label is revealed. First, the Perceptron produces p_t from w(t) and x_t. Second, it receives y_t. The prediction is a mistake when p_t and y_t do not agree.
What do you think happens?
The Perceptron has already produced p_t, but y_t has not been revealed yet. Can it already know whether a mistake occurred?
Reveal answer
Answer: No, because the true label is needed
The true label is revealed only after the prediction. The learner evaluates whether a mistake occurred by comparing its prediction with that revealed label.
Why Complexity Matters
The hypothesis class in this setting has infinite Littlestone dimension when d is at least 2. The source explains this using 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 used in the construction have parameter vectors of the form (-1, a, 0, ..., 0), where a ranges over [0, 1]. The density of the real numbers makes this construction possible.
The consequence is a limitation on guarantees. Infinite Littlestone dimension means that few-mistake guarantees are unavailable for the stated class. In particular, there is no finite general worst-case mistake bound supplied by this complexity measure for the setting described here.
Common Reasoning Errors
Treating the true label as an input to the same-round prediction.
The true label is revealed only after the prediction.
Fix:
Calculate p_t from w(t) and x_t first, then use y_t to evaluate correctness.Checking for a mistake before the true label is available.
Correctness requires comparison with the revealed true label.
Fix:
Wait until y_t is revealed, then compare p_t with y_t.Assuming a prediction rule automatically gives a finite mistake bound.
The stated class has infinite Littlestone dimension when d is at least 2.
Fix:
Separate the mechanism for producing predictions from the complexity result about available mistake guarantees.Ignoring the dimension condition in the complexity conclusion.
The source's conclusion is explicitly tied to that dimension condition.
Fix:
State the condition d at least 2 when presenting this result.
Round-by-Round Practice
On a new online round, list the information available before prediction, write the prediction rule, and state what additional information is needed to decide whether a mistake occurred. Then explain why the infinite Littlestone dimension result prevents a finite general few-mistake guarantee for the stated class when d is at least 2.
Hints
- Separate the information available before prediction from the feedback revealed afterward.
- Use p_t = sign(<w(t), x_t>) for the prediction.
- A mistake can be evaluated only after comparing p_t with y_t.
- Connect infinite Littlestone dimension to the absence of a finite general mistake guarantee.
Essential Takeaways
- On round t, the Perceptron receives x_t and uses its current weight vector w(t) before the true label is revealed.
- The prediction is p_t = sign(<w(t), x_t>).
- The true label y_t arrives after the prediction and determines whether a mistake occurred.
- For the stated class, infinite Littlestone dimension when d is at least 2 means that no finite general few-mistake guarantee is available.
- The source supports the infinite-dimension conclusion with a shattered-tree construction using real-valued parameter choices.
Key Takeaways
- The Perceptron is an online learner that predicts before seeing the current true label.
- Its prediction is determined by the sign of the inner product between w(t) and x_t.
- A mistake is identified only after y_t is revealed and compared with p_t.
- When d is at least 2, the stated class has infinite Littlestone dimension, so a finite general few-mistake guarantee is unavailable.