Online Learnability
Online learning proceeds round by round, with the environment choosing instances and revealing labels after the learner predicts.
Learning as a Sequential Game
Online learning is organized as a sequence of rounds rather than as a single pass through a complete training set. The environment chooses an instance, the learner predicts its binary label, and only then does the environment reveal the true binary label. The learner can use that revealed label when making predictions in later rounds.
The central online question is not only whether the hypothesis class contains a good predictor. It is whether a learner can keep making predictions as examples arrive one at a time while keeping the number of mistakes under control.
Tracing a Round
- The environment chooses the current instance x_t.
- The learner predicts a binary label p_t, either 0 or 1.
- The environment reveals the true binary label y_t.
- The learner may use the revealed label when making later predictions.
A mistake occurs when the learner's prediction does not agree with the label revealed by the environment. The sequence of revealed labels matters because each new label extends the history of the game. Online learnability therefore concerns how many mistakes can be controlled across such histories.
Label Histories as Trees
To represent all possible online histories, imagine a branching tree. A node contains the instance chosen for that round. Its outgoing branches represent the possible labels that the environment might reveal next. A path from the root records one possible sequence of revealed labels.
A tree is shattered by a hypothesis class H when every label path through the tree can be made consistent with some hypothesis h* in H. For each path, there must be a hypothesis whose predictions on the instances along that path agree with every label on that path.
Shattering is a path-by-path condition. It is not enough for the class to realize several labels somewhere in the tree; every complete label history must have a matching hypothesis.
Testing a Small Hypothesis Class
Consider the hypothesis class H containing two hypotheses: one always predicts 0, and the other always predicts 1. We can test its shattering ability by listing every label path at a chosen depth and matching each path with a hypothesis.
Depth One Versus Depth Two
Determine whether the class containing the always-0 hypothesis and the always-1 hypothesis shatters a depth-one tree or a depth-two tree.
Test depth one: A depth-one tree has two possible one-label paths: 0 and 1. The always-0 hypothesis matches path 0, and the always-1 hypothesis matches path 1. Therefore every path has a matching hypothesis.
Test depth two: A depth-two tree has four possible label histories: 00, 01, 10, and 11. The always-0 hypothesis matches 00, and the always-1 hypothesis matches 11. Neither constant hypothesis matches the mixed histories 01 or 10.
Compare the results: The class shatters the depth-one tree but does not shatter the depth-two tree. It can realize both labels on one chosen instance, but it cannot realize every two-round label history.
The greatest shattered depth for this class is one.
When checking whether a tree is shattered, identify its depth, enumerate all label histories, and then match every history with a hypothesis. Do not decide from individual nodes alone.
Littlestone's Dimension
Littlestone's Dimension is the greatest depth of a tree shattered by a hypothesis class.
Depth counts how many online rounds are represented along a path. A larger greatest shattered depth means that the class supports a more deeply branching collection of label histories. For the class with the always-0 and always-1 hypotheses, the depth-one test succeeds and the depth-two test fails, so its Littlestone's Dimension is one.
Mistakes Along a Path
Each prediction and revealed label selects a branch of the history tree. The learner moves farther down the tree as rounds proceed. A mistake can occur on a round when the prediction differs from the revealed label, and later predictions can use the newly revealed label.
A shattered tree contains every possible label path at its depth. Littlestone's Dimension measures how long this complete branching can continue, which makes it a complexity measure specifically tied to online learning.
Dimension and Mistake Bounds
Littlestone's Dimension is tied specifically to online learnability and achievable mistake bounds. A greater dimension means that the hypothesis class can support deeper complete collections of label histories. The dimension therefore describes the difficulty of controlling mistakes while predictions are made online.
Checking Your Reasoning
For the class containing only the always-0 and always-1 hypotheses, list every path in a depth-two tree. For each path, identify whether one of the two hypotheses matches all labels on that path. Then state the class's Littlestone's Dimension.
Hints
- A depth-two tree has four possible binary label histories.
- The always-0 hypothesis matches histories made entirely of 0 labels.
- The always-1 hypothesis matches histories made entirely of 1 labels.
- Use the path-by-path test rather than judging isolated nodes. The class fails to shatter depth two because the mixed histories are unmatched, so the greatest shattered depth is one.
Key Takeaways
- Online learning is a round-by-round game: the environment chooses an instance, the learner predicts a binary label, and the environment reveals the true label.
- A tree is shattered when every label path has a hypothesis in the class that agrees with all labels on that path.
- Littlestone's Dimension is the greatest depth of a tree shattered by the hypothesis class.
- For the class containing the always-0 and always-1 hypotheses, depth one is shattered but depth two is not, so the dimension is one.
- The dimension is an online complexity measure tied to achievable mistake bounds.