Computational learning theory

COLT (COmputational Learning Theory) is a field of machine learning.

In COLT the main interest is the computational aspects of learning, e.g., the time complexity of learning problem. The computational aspects are considered in a learning framework, like the very common one of Probably approximately correct learning.

Note that a computation is considered feasible if it can be done in polynomial time.

There are two kind of results in COLT. Possitive results - Showing the a certain class of function is learnable in polynomial time. Negative results - Showing that certain classes cannot be learned in polynomial time. Negative results were proven only by assumption. The assumptions the are common in negative results are: Computational - P<>NP Cryptographic - One way functions exits.

This is a good survey of COLT:

• [Angluin, 92] Angluin, D. 1992. Computational learning theory: Survey and selected bibliography. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (May 1992), pp. 351--369.

This is a good paper on negative results:

• [KV,89] M. Kearns and L. G. Valiant. 1989. Cryptographic limitations on learning Boolean formulae and finite automata. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 433--444, New York. ACM.

This article is a stub. You can help Wikipedia by fixing it.