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
- A new example arrives when a prediction is needed.
- The learner predicts its binary label before the true label is known.
- The true label is revealed.
- The 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.
Receive: The new example arrives. The learner cannot first wait for a complete training set before deciding.
Predict: The learner predicts the example's binary label while the true label is still unknown.
Observe: The true label is revealed after the prediction.
Learn: 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 |
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. |
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.
- Weighted-Majority introduces an important online-learning algorithm.
- Convex loss functions provide a setting for studying online-learning problems through the behavior of loss.
- The 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
Treating online learning as ordinary batch training followed by prediction.
Online learning does not separate training from prediction in that way; each example is predicted before its true label is known.
Fix:
Write the online order explicitly: receive the instance, predict, observe the label, and use the result as training information for later examples.Putting label observation before prediction.
The true label is not known when the online prediction is made.
Fix:
Place prediction before observation of the true label.Using realizable to describe the timing of events.
Prediction-before-label-observation describes the online protocol, not realizability.
Fix:
Use realizable for the condition that one hypothesis can classify the entire sequence perfectly.Treating the three chapter topics as the same concept.
They occupy different roles in the chapter's progression.
Fix:
Identify 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
- PAC learning separates training from prediction, while online learning does not.
- In 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.
- The realizable case is the case in which one hypothesis can classify the entire sequence perfectly; the unrealizable case does not satisfy that condition.
- Weighted-Majority is introduced as an important online-learning algorithm.
- Convex loss functions and the Perceptron follow as later topics, with the Perceptron illustrating surrogate convex loss functions in online learning.
Key Takeaways
- 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.