Hypothesis Class Complexity
The hypothesis class in this setting has infinite Littlestone dimension when d is at least 2.
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
- 1At round t, the learner receives one input vector x_t from Rd.
- 2The learner uses its current weight vector w(t) together with x_t to produce a label prediction.
- 3After the prediction has been made, the true label y_t is revealed.
- 4The 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.
- 1Before 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.
- 2Prediction
The Perceptron combines w(t) and x_t through the rule p_t = sign(<w(t), x_t>).
- 3After 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?
- 1Identify the current state
Use the current weight vector w(t), not a future or later weight vector.
- 2Read the incoming example
Use the input vector x_t received on round t.
- 3Combine the vectors
Compute their inner product, written as <w(t), x_t>.
- 4Convert 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
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
Common mistake Treating the true label as an input to the same-round prediction.
What it looks likeUsing y_t together with w(t) and x_t to calculate p_t.
Why it failsThe true label is revealed only after the prediction.
Do this insteadCalculate p_t from w(t) and x_t first, then use y_t to evaluate correctness.
Common mistake Checking for a mistake before the true label is available.
What it looks likeDeclaring the prediction correct immediately after computing sign(<w(t), x_t>).
Why it failsCorrectness requires comparison with the revealed true label.
Do this insteadWait until y_t is revealed, then compare p_t with y_t.
Common mistake Assuming a prediction rule automatically gives a finite mistake bound.
What it looks likeConcluding that because the Perceptron has a specified rule, the class must have a finite general guarantee.
Why it failsThe stated class has infinite Littlestone dimension when d is at least 2.
Do this insteadSeparate the mechanism for producing predictions from the complexity result about available mistake guarantees.
Common mistake Ignoring the dimension condition in the complexity conclusion.
What it looks likeApplying the infinite Littlestone dimension conclusion without noting that the source states it for d at least 2.
Why it failsThe source's conclusion is explicitly tied to that dimension condition.
Do this insteadState 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
- 1On round t, the Perceptron receives x_t and uses its current weight vector w(t) before the true label is revealed.
- 2The prediction is p_t = sign(<w(t), x_t>).
- 3The true label y_t arrives after the prediction and determines whether a mistake occurred.
- 4For the stated class, infinite Littlestone dimension when d is at least 2 means that no finite general few-mistake guarantee is available.
- 5The source supports the infinite-dimension conclusion with a shattered-tree construction using real-valued parameter choices.
At a glance
- 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.