online learning
In plain wordsLearning from data that arrive one piece at a time, updating the model after each new example instead of training once on a fixed collection, as a spam filter does while emails stream in.
A learning setting organized as repeated rounds of predict, observe, update: the learner makes a prediction, sees the true outcome or incurs a loss, and adjusts the model before the next example (or small batch) arrives, using bounded memory and computation per round. Unlike batch (offline) learning, which fits a model once to a complete dataset, it keeps adapting, which suits systems that must track a moving target (concept driftconcept drift, n.: When the real-world link between what a model sees and the right answer changes over time — as when spammers change tactics — so lessons the model learned no longer hold.), such as click prediction, fraud detection and recommendation, and data streams too large to store. Stochastic gradient descentstochastic gradient descent, n.: A faster version of gradient descent that estimates which way is downhill from a small random sample of the training data at each step, instead of checking the whole dataset. applied one example at a time is the archetypal online algorithm. The theory makes no statistical assumptions about the data, which may even be chosen by an adversary, and measures performance by regretregret, n.: How much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying.: cumulative loss compared with the best fixed predictor in hindsight. Landmark results include mistake bounds for the perceptronperceptron, n.: One of the first learning machines: a single artificial neuron that sorts inputs into two groups by drawing a straight dividing line, nudging its weights whenever it guesses wrong. and Winnow, the weighted-majority and multiplicative-weights algorithms for prediction with expert advice, and online convex optimization, where online gradient descent achieves regret growing with the square root of the number of rounds; banditsmulti-armed bandit, n.: A puzzle named after a gambler choosing between slot machines: you must keep picking among options whose payoffs are unknown, learning which is best while wasting as few tries as possible on the others. are the partial-feedback case.
The fraud model learns online: every confirmed chargeback updates its weights within minutes.
Origin
Frank Rosenblatt's perceptron (1958) learned one example at a time, and Bernard Widrow and Ted Hoff's LMS rule (1960) was an early online regression method. The theory took shape with Nick Littlestone's mistake-bound model and Winnow algorithm (1988), the weighted majority algorithm of Littlestone and Manfred Warmuth (1989; journal version 1994) and Martin Zinkevich's online convex optimization (2003).
Usage note
Not to be confused with e-learning. Distinct from continual learningcontinual learning, n.: The ability of an AI to keep learning new things over time from a stream of experience, without forgetting what it already knew and without being retrained from scratch., which stresses accumulating new tasks without catastrophic forgettingcatastrophic forgetting, n.: When a neural network trained on something new gets suddenly and badly worse at what it could already do, because the new training rewrites the internal settings the old skills relied on., though the terms overlap in practice.
Related
- stochastic gradient descentstochastic gradient descent, n.: A faster version of gradient descent that estimates which way is downhill from a small random sample of the training data at each step, instead of checking the whole dataset.
- regretregret, n.: How much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying.
- multi-armed banditmulti-armed bandit, n.: A puzzle named after a gambler choosing between slot machines: you must keep picking among options whose payoffs are unknown, learning which is best while wasting as few tries as possible on the others.
- concept driftconcept drift, n.: When the real-world link between what a model sees and the right answer changes over time — as when spammers change tactics — so lessons the model learned no longer hold.
- continual learningcontinual learning, n.: The ability of an AI to keep learning new things over time from a stream of experience, without forgetting what it already knew and without being retrained from scratch.
- perceptronperceptron, n.: One of the first learning machines: a single artificial neuron that sorts inputs into two groups by drawing a straight dividing line, nudging its weights whenever it guesses wrong.
- active learningactive learning, n.: A way to train a model with fewer labeled examples by letting it choose which unlabeled examples a person should label next, usually the ones it is most unsure about.
Sources
- Littlestone, N. (1988). Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm. Machine Learning 2(4).
- Cesa-Bianchi, N. & Lugosi, G. (2006). Prediction, Learning, and Games. Cambridge University Press.
- Zinkevich, M. (2003). Online Convex Programming and Generalized Infinitesimal Gradient Ascent. Proc. ICML 2003.
Mentioned in
active learningactive learning, n.: A way to train a model with fewer labeled examples by letting it choose which unlabeled examples a person should label next, usually the ones it is most unsure about., click-through rate predictionclick-through rate prediction, n.: Estimating how likely a particular person is to click on a particular ad, search result or recommended item: a prediction made billions of times a day to decide what each user is shown., concept driftconcept drift, n.: When the real-world link between what a model sees and the right answer changes over time — as when spammers change tactics — so lessons the model learned no longer hold., continual learningcontinual learning, n.: The ability of an AI to keep learning new things over time from a stream of experience, without forgetting what it already knew and without being retrained from scratch., i.i.d.i.i.d., abbr.: Short for 'independent and identically distributed': every data point is produced the same way, and none influences any other — like repeated rolls of one fair die., learninglearning, n.: Getting better at something through experience. For a machine, it means changing its internal settings based on data so that it performs a task better than before., Bernard WidrowBernard Widrow, prop. n.: An American electrical engineer who in 1960 built ADALINE, an early trainable neural unit, and invented a learning rule that adjusts weights to reduce errors, still at the heart of adaptive filters., regretregret, n.: How much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying.