Online machine learning

Online machine learning

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 [1]. 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.

Contents

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

See also

References

  1. ^ Littlestone, Nick; (1988) Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm, Machine Learning 285-318(2), Kluwer Academic Publishers

External link


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Machine Learning — Maschinelles Lernen ist ein Oberbegriff für die „künstliche“ Generierung von Wissen aus Erfahrung: Ein künstliches System lernt aus Beispielen und kann nach Beendigung der Lernphase verallgemeinern. Das heißt, es lernt nicht einfach die Beispiele …   Deutsch Wikipedia

  • Online learning model — In machine learning, an online learning model is a learning model that does not have a separate training and testing phase. The pseudo code for this model is: do retrieve the next example x get prediction from algorithm if prediction is wrong… …   Wikipedia

  • Online algorithm — In 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… …   Wikipedia

  • Machine vision — (MV System) is the application of computer vision to industry and manufacturing. Whereas computer vision is mainly focused on machine based image processing, machine vision most often requires also digital input/output devices and computer… …   Wikipedia

  • Machine translation — Part of a series on Translation Types Language interpretation …   Wikipedia

  • Machine vision glossary — Common definitions related to the machine vision field.Compiled for application on the Society of Manufacturing Engineers interest area.General related fields *Machine vision *Computer vision *Image processing *Signal processing NOTOC 0 9*1394.… …   Wikipedia

  • E-learning — For the term online learning as used in machine learning, see Online machine learning. E learning comprises all forms of electronically supported learning and teaching. The information and communication systems, whether networked learning or not …   Wikipedia

  • Computational learning theory — In theoretical computer science, computational learning theory is a mathematical field related to the analysis of machine learning algorithms. Contents 1 Overview 2 See also 3 References 3.1 Surveys …   Wikipedia

  • Learning object metadata — is a data model, usually encoded in XML, used to describe a learning object and similar digital resources used to support learning. The purpose of learning object metadata is to support the reusability of learning objects, to aid discoverability …   Wikipedia

  • History of virtual learning environments — A virtual learning environment (VLE) is a system that creates an environment designed to facilitate teachers in the management of educational courses for their students, especially a system using computer hardware and software, which involves… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”