PAC Learning Model
Online learning has no separate training phase followed by a separate prediction phase.
The Timing Problem
Imagine that a learner must make a decision before knowing whether the decision is correct. Only afterward does the learner obtain the true answer and use it to make later decisions better. This timing pattern is the central idea of online learning. Learning and prediction are not placed in two separate stages; they are interwoven over a sequence of rounds.
One Online Round
An online learning round has four main events. First, the learner receives an instance. Second, the learner must make a prediction for that instance. Third, the correct label is revealed. Fourth, the learner uses that label to support future predictions. The next round then begins with another instance, so the process continues through consecutive rounds.
The learner predicts before seeing the correct label. The label becomes available only afterward and can then support predictions in later rounds.
Rounds in Sequence
Online learning is not one isolated prediction. It is a sequence of consecutive learning rounds. In each round, the learner receives an instance, predicts, obtains the correct label, and uses that label to support future predictions. The result is a repeated predict-and-learn schedule rather than a single training event followed by all later predictions.
When analyzing an online learning process, write the events in time order. Ask what the learner knows before the prediction, then identify what becomes available after the correct label is revealed.
From Test to Training
Consider the papaya setting. In an online round, a learner receives one papaya and must predict its taste before obtaining the correct label. At that moment, the papaya is functioning as a test example because the learner is being asked to make a prediction about it. After the correct taste label is revealed, the same papaya can contribute to future predictions. It has now also served a training role.
The important point is the change in role. The example is not permanently a test example or permanently a training example. Before its correct label is known, it is used for prediction. After the label is obtained, it can support future learning and prediction.
PAC and Online Schedules
The PAC learning model separates learning from prediction. The learner first receives a batch of training examples, learns a hypothesis from that batch, and then applies the learned hypothesis to new examples. Online learning uses a different schedule: the learner predicts each current instance before obtaining its correct label, and that labeled instance can then contribute to future predictions.
| PAC learning model | Online learning |
|---|---|
| Starts with a batch of training examples | Processes examples through consecutive rounds |
| Learning happens before prediction on new examples | Prediction happens before the current correct label is obtained |
| A learned hypothesis is applied to new examples | The obtained label can support future predictions |
| Training and prediction are separate stages | Learning and prediction are interwoven |
Common Mistakes
Treating online learning as if it had one separate training phase followed by one separate prediction phase.
That schedule describes the separation emphasized in the PAC learning model, not the interleaved schedule of online learning.
Fix:
Place prediction before the current correct label is revealed, then allow that label to support future predictions.Assuming an example is only a test example.
In online learning, the same example can move from a test role to a training role after its correct label is obtained.
Fix:
Track the example across time: it is first used for prediction and later can contribute to future predictions.Putting the correct label before the prediction.
The online round requires a prediction before the correct label is revealed.
Fix:
Use the order instance, prediction, correct label, and support for future predictions.
Check Your Understanding
A learner receives an instance, predicts its label, receives the correct label, and then uses that information when handling later instances. Is this schedule closer to PAC learning or online learning? Explain which event must happen before the correct label is available.
Hints
- Recall whether training and prediction are separate or interwoven.
- List the four events in an online learning round in order.
Identifying the Learning Schedule
A learner first receives a batch of training examples, learns a hypothesis, and then applies that hypothesis to new examples.
Identify the training arrangement: The learner receives a batch before making predictions on new examples.
Identify the prediction arrangement: Prediction occurs after the separate training stage.
Compare with the models: A batch training stage followed by a prediction stage matches the PAC learning model rather than the online schedule.
This is the PAC learning model. Online learning would require the learner to predict each current instance before obtaining its correct label, then use that label to support future predictions.
Key Takeaways
- Online learning proceeds through consecutive learning rounds.
- Each round contains four events: receive an instance, make a prediction, obtain the correct label, and use that label to support future predictions.
- An example can first serve as a test example and later serve as a training example after its correct label is obtained.
- PAC learning separates a batch training stage from a later prediction stage.
- Online learning interweaves prediction and learning across rounds.
Key Takeaways
- Online learning is organized as consecutive rounds rather than separate training and prediction phases.
- The learner predicts before seeing the current instance's correct label.
- Once revealed, the label can support predictions in later rounds.
- The same example can move from a test role to a training role.
- PAC learning uses a batch training stage followed by a prediction stage, unlike online learning.