Definitions
| Protocol | Main constraint on algorithm design |
| Success Measure | sometimes impossible to practically measure. May serve as a guide for designing algorithms |
| Type of Analysis | what we want to prove |
| Data generation mechanism | Only relevant for the analysis, not for designing an algorithm |
| Further Restrictive Assumptions | used for designing algorithms or proving restricted results |
Examples
- Off-line supervised learning: training pairs are given, the goal is to produce a
- Semi-supervised: training pairs and unlabeled data are given, the goal
is to produce a model that predicts well
- Transductive: training pairs and unlabeled data are given, the goal is
to predict well on the unlabeled examples
- On-line: repeated transductive learning (one new example
at a time, prediction to be performed at each step)
- Variants of on-line: actions instead of predictions (e.g.
General framework
Predictor receives x, takes an action y, and gets reward r.
It is possible to combine r with x.
A prediction function takes a history of pairs ((x,r), y) and a new x to predict y.
Classification
| Name | X | Y |
| Fixed design | fixed | iid |
| Random design | iid | iid |
| Sequence prediction | fixed | worst-case |
| Online learning | worst-case | worst-case |
| Online compression | fixed | iid |
Comments (0)
You don't have permission to comment on this page.