Online machine learning
Encyclopedia
In machine learning
, online learning is a model of induction
that learns one instance at a
time. The goal in online learning is to predict labels for instances.
For example, the instances could describe the current conditions of
the stock market
, and an online algorithm predicts tomorrow's value of
a particular stock. The key defining characteristic of online
learning is that soon after the prediction is made, the true label of
the instance is discovered. This information can then be used to
refine the prediction hypothesis used by the algorithm. The goal of
the algorithm is to make predictions that are close to the true
labels.
More formally, an online algorithm proceeds in a sequence of trials.
Each trial can be decomposed into three steps. First the algorithm
receives an instance. Second the algorithm predicts the label of the
instance. Third the algorithm receives the true label of the
instance . The third stage is the most crucial as the algorithm can
use this label feedback to update its hypothesis for future trials.
The goal of the algorithm is to minimize some performance criteria.
For example, with stock market prediction the algorithm may attempt to
minimize sum of the square distances between the predicted and true
value of a stock. Another popular performance criterion is to minimize
the number of mistakes when dealing with classification problems.
Because online learning algorithms continually receive label feedback,
the algorithms are able to adapt and learn in difficult situations.
Many online algorithms can give strong guarantees on performance even
when the instances are not generated by a distribution. As long as a
reasonably good classifier exists, the online algorithm will learn to
predict correct labels. This good classifier must come from a
previously determined set that depends on the algorithm. For example,
two popular on-line algorithms perceptron
and winnow
can perform well
when a hyperplane
exists that splits the data into two categories.
These algorithms can even be modified to do provably well even if the
hyperplane is allowed to infrequently change during the online learning
trials.
Unfortunately, the main difficulty of online learning is also a result
of the requirement for continual label feedback. For many problems it
is not possible to guarantee that accurate label feedback will be
available in the near future. For example, when designing a system
that learns how to do optical character recognition
, typically some
expert must label previous instances to help train the algorithm. In
actual use of the OCR application, the expert is no longer
available and no inexpensive outside source of accurate labels is
available. Fortunately, there is a large class of problems where
label feedback is always available. For any problem that consists of
predicting the future, an online learning algorithm just needs to wait
for the label to become available. This is true in our previous
example of stock market prediction and many other problems.
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
, online learning is a model of induction
Inductive reasoning
Inductive reasoning, also known as induction or inductive logic, is a kind of reasoning that constructs or evaluates propositions that are abstractions of observations. It is commonly construed as a form of reasoning that makes generalizations based on individual instances...
that learns one instance at a
time. The goal in online learning is to predict labels for instances.
For example, the instances could describe the current conditions of
the stock market
Stock market
A stock market or equity market is a public entity for the trading of company stock and derivatives at an agreed price; these are securities listed on a stock exchange as well as those only traded privately.The size of the world stock market was estimated at about $36.6 trillion...
, and an online algorithm predicts tomorrow's value of
a particular stock. The key defining characteristic of online
learning is that soon after the prediction is made, the true label of
the instance is discovered. This information can then be used to
refine the prediction hypothesis used by the algorithm. The goal of
the algorithm is to make predictions that are close to the true
labels.
More formally, an online algorithm proceeds in a sequence of trials.
Each trial can be decomposed into three steps. First the algorithm
receives an instance. Second the algorithm predicts the label of the
instance. Third the algorithm receives the true label of the
instance . The third stage is the most crucial as the algorithm can
use this label feedback to update its hypothesis for future trials.
The goal of the algorithm is to minimize some performance criteria.
For example, with stock market prediction the algorithm may attempt to
minimize sum of the square distances between the predicted and true
value of a stock. Another popular performance criterion is to minimize
the number of mistakes when dealing with classification problems.
Because online learning algorithms continually receive label feedback,
the algorithms are able to adapt and learn in difficult situations.
Many online algorithms can give strong guarantees on performance even
when the instances are not generated by a distribution. As long as a
reasonably good classifier exists, the online algorithm will learn to
predict correct labels. This good classifier must come from a
previously determined set that depends on the algorithm. For example,
two popular on-line algorithms perceptron
Perceptron
The perceptron is a type of artificial neural network invented in 1957 at the Cornell Aeronautical Laboratory by Frank Rosenblatt. It can be seen as the simplest kind of feedforward neural network: a linear classifier.- Definition :...
and winnow
Winnow (algorithm)
The winnow algorithm is a technique from machine learning for learning a linear classifier from labeled examples. It is very similar to the perceptron algorithm. However, the perceptron algorithm uses an additive weight-update scheme, while Winnow uses a multiplicative scheme that allows it to...
can perform well
when a hyperplane
Hyperplane
A hyperplane is a concept in geometry. It is a generalization of the plane into a different number of dimensions.A hyperplane of an n-dimensional space is a flat subset with dimension n − 1...
exists that splits the data into two categories.
These algorithms can even be modified to do provably well even if the
hyperplane is allowed to infrequently change during the online learning
trials.
Unfortunately, the main difficulty of online learning is also a result
of the requirement for continual label feedback. For many problems it
is not possible to guarantee that accurate label feedback will be
available in the near future. For example, when designing a system
that learns how to do optical character recognition
Optical character recognition
Optical character recognition, usually abbreviated to OCR, is the mechanical or electronic translation of scanned images of handwritten, typewritten or printed text into machine-encoded text. It is widely used to convert books and documents into electronic files, to computerize a record-keeping...
, typically some
expert must label previous instances to help train the algorithm. In
actual use of the OCR application, the expert is no longer
available and no inexpensive outside source of accurate labels is
available. Fortunately, there is a large class of problems where
label feedback is always available. For any problem that consists of
predicting the future, an online learning algorithm just needs to wait
for the label to become available. This is true in our previous
example of stock market prediction and many other problems.
Books with substantial treatment of online learning
- Algorithmic Learning in a Random World by Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Published by Springer Science+Business Media, Inc. 2005 ISBN 0-387-00152-2
- Prediction, learning, and games by Nicolò Cesa-BianchiNicolò Cesa-BianchiNicolò Cesa-Bianchi is a computer scientist and Professor of Computer Science at the "Dipartimento di Scienze dell'Informazione" of the University of Milan....
and Gábor Lugosi. Cambridge University Press, 2006 ISBN 0521841089
See also
- k-nearest neighbor algorithmK-nearest neighbor algorithmIn pattern recognition, the k-nearest neighbor algorithm is a method for classifying objects based on closest training examples in the feature space. k-NN is a type of instance-based learning, or lazy learning where the function is only approximated locally and all computation is deferred until...
- Lazy learningLazy learningIn artificial intelligence, lazy learning is a learning method in which generalization beyond the training data is delayed until a query is made to the system, as opposed to in eager learning, where the system tries to generalize the training data before receiving queries.The main advantage gained...
- Learning Vector Quantization
- Offline learningOffline learningIn machine learning, systems which employ offline learning do not change their approximation of the target function once the initial training phase has been absolved. These systems are also typically examples of eager learning.-See also:...
, the opposite model - Online algorithmOnline algorithmIn computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from...
- PerceptronPerceptronThe perceptron is a type of artificial neural network invented in 1957 at the Cornell Aeronautical Laboratory by Frank Rosenblatt. It can be seen as the simplest kind of feedforward neural network: a linear classifier.- Definition :...