Online Binary Classification
PAC learning separates training from prediction, whereas online learning does not.
A Decision Before the Answer
Imagine that examples arrive one at a time, exactly when a prediction is needed. The learner must predict the label of the current example before its true label is known. Only afterward does the correct label become available, and that experience can provide training information for what comes next. This interleaving of prediction and learning is the central setting of online binary classification.
The Online Round
- 1A new example arrives when a prediction is needed.
- 2The learner predicts its binary label before the true label is known.
- 3The true label is revealed.
- 4The example and its revealed label can become training information for later examples.
One Example at a Time
Tracing an online example
A learner receives a new example at the moment a prediction is required. Describe the learner's actions in the correct order.
- 1Receive
The new example arrives. The learner cannot first wait for a complete training set before deciding.
- 2Predict
The learner predicts the example's binary label while the true label is still unknown.
- 3Observe
The true label is revealed after the prediction.
- 4Learn
The labeled example can now become training information that influences the learner's treatment of later examples.
The online order is receive the instance, predict, observe the true label, and learn from the result for what follows.
| Setting | Training information | Prediction timing |
|---|---|---|
| PAC learning | A batch of training examples is received first | Predictions are made afterward for new examples |
| Online learning | Each revealed labeled example can inform later examples | Each prediction is made before that example's true label is known |
The distinction is the relationship between training and prediction.
Two Sequence Assumptions
Online binary classification is studied under realizable and unrealizable assumptions. These assumptions concern whether the examples in the sequence can be handled perfectly by a single hypothesis.
| Case | Meaning for the sequence |
|---|---|
| Realizable | One hypothesis can classify the entire sequence perfectly. |
| Unrealizable | The sequence does not satisfy the condition that one hypothesis classify the entire sequence perfectly. |
Realizability describes whether perfect classification by one hypothesis is available.
The Chapter's Algorithmic Progression
The chapter develops online learning through a sequence of ideas. It first presents Weighted-Majority as an important online-learning algorithm. It then studies online-learning problems with convex loss functions. Finally, it presents the Perceptron as an example of using surrogate convex loss functions in the online-learning model.
- 1Weighted-Majority introduces an important online-learning algorithm.
- 2Convex loss functions provide a setting for studying online-learning problems through the behavior of loss.
- 3The Perceptron demonstrates the use of surrogate convex loss functions in the online-learning model.
These topics are connected by the online setting, but they are not interchangeable terms. Weighted-Majority is an algorithm, convex loss functions describe a class of loss functions studied in online learning, and the Perceptron is an algorithm presented through surrogate convex loss functions.
Common Misreadings
Common mistake Treating online learning as ordinary batch training followed by prediction.
What it looks likeThe learner collects all examples first and postpones every prediction.
Why it failsOnline learning does not separate training from prediction in that way; each example is predicted before its true label is known.
Do this insteadWrite the online order explicitly: receive the instance, predict, observe the label, and use the result as training information for later examples.
Common mistake Putting label observation before prediction.
What it looks likeThe learner sees the correct label and then chooses its prediction.
Why it failsThe true label is not known when the online prediction is made.
Do this insteadPlace prediction before observation of the true label.
Common mistake Using realizable to describe the timing of events.
What it looks likeCalling a sequence realizable because the learner predicts before seeing the label.
Why it failsPrediction-before-label-observation describes the online protocol, not realizability.
Do this insteadUse realizable for the condition that one hypothesis can classify the entire sequence perfectly.
Common mistake Treating the three chapter topics as the same concept.
What it looks likeDescribing Weighted-Majority, convex loss functions, and the Perceptron as alternative names for one algorithm.
Why it failsThey occupy different roles in the chapter's progression.
Do this insteadIdentify Weighted-Majority as an algorithm, convex loss functions as a studied problem setting, and the Perceptron as an example involving surrogate convex loss functions.
Check the Sequence
Classify each description as online learning or PAC learning. Then explain which event comes first, second, and third.
A. The learner receives a batch of training examples, learns a hypothesis, and later predicts labels for new examples.
B. The learner predicts the label of each arriving example before the true label is known, then uses the revealed label as training information for later examples.
C. A sequence can be perfectly classified by one hypothesis.
Finally, state whether item C describes the online event order or a realizability assumption.
Hints
- PAC learning separates training from prediction.
- Online learning puts prediction before observation of the true label.
- Realizability concerns whether one hypothesis can classify the entire sequence perfectly.
The expected classifications are PAC learning for A, online learning for B, and a realizability condition for C. A useful diagnostic is to write the event order instead of relying on labels alone.
Essential Takeaways
- 1PAC learning separates training from prediction, while online learning does not.
- 2In online binary classification, the learner predicts before the true label is known, observes the label afterward, and can use the labeled example as training information for later examples.
- 3The realizable case is the case in which one hypothesis can classify the entire sequence perfectly; the unrealizable case does not satisfy that condition.
- 4Weighted-Majority is introduced as an important online-learning algorithm.
- 5Convex loss functions and the Perceptron follow as later topics, with the Perceptron illustrating surrogate convex loss functions in online learning.
At a glance
- Online learning interleaves prediction and learning instead of separating batch training from later prediction.
- The online protocol is: receive an instance, predict its label, observe the true label, and use the result for later examples.
- Realizable and unrealizable describe whether one hypothesis can classify the complete sequence perfectly.
- Weighted-Majority, convex loss functions, and the Perceptron form a progression in the study of online learning.