Online learning of conditionally I.I.D. data

ABSTRACT

In this work we consider the task of relaxing the i.i.d assumption in online pattern recognition (or classification), aiming to make existing learning algorithms applicable to a wider range of tasks. Online pattern recognition is predicting a sequence of labels based on objects given for each label and on examples (pairs of objects and labels) learned so far. Traditionally, this task is considered under the assumption that examples are independent and identically distributed. However, it turns out that many results of pattern recognition theory carry over under a much weaker assumption. Namely, under the assumption of conditional independence and identical distribution of objects only, while the only condition on the distribution of labels is that the rate of occurrence of each label should be above some positive threshold.We find a broad class of learning algorithms for which estimations of the probability of a classification error achieved under the classical i.i.d. assumption can be generalised to the similar estimates for the case of conditionally i.i.d. distributed examples.

REFERENCES

• 1: Eric B. Baum , David Haussler, What size net gives valid generalization?, Neural Computation, v.1 n.1, p.151-160, Spring 1990 [doi>10.1162/neco.1989.1.1.151]
• 2: Bottou L., LeCun Y. (2003). Large Scale Online Learning. Advances in Neural Information Processing Systems 16 (proceedings of NIPS 2003)
• 3: Devroye L., Györfi G., Lugosi G (1996). A probabilistic theory of pattern recognition. New York: Springer.
• 4: Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
• 5: Morvai G., Yakowitz S. J., Algoet P. (1997). Weakly Convergent Nonparametric Forecasting of Stationary Time Series IEEE Transactions on Information Theory, Vol. 43, No. 2, pp. 483--498.
• 6: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 7: Vapnik, V. and Chervonenkis, A. (1974) Ordered risk minimisation I. Automation and Remote Control, 35: 1226--1235.
• 8: Vapnik, V. and Chervonenkis, A. (1974). Ordered risk minimisation II. Automation and Remote Control, 35: 1403--1412.
• 9: Vapnik, V. and Chervonenkis, A. (1974) Theory of Pattern Recognition Nauka, Moscow. (in Russian); German translation: Theorie der Zeichenerkennung, Akademie Verlag, Berlin 1979.
• 10: M. Vidyasagar, A Theory of Learning and Generalization: With Applications to Neural Networks and Control Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 11: Vladimir Vovk, On-Line Confidence Machines Are Well-Calibrated, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.187-196, November 16-19, 2002