Computational learning theory: Difference between revisions

Revision as of 23:09, 30 April 2005

Revision as of 23:10, 30 April 2005

Line 10:

* [[cryptography|Cryptographic]] - [[One-way function]]s exist.

There are several different approaches to computational learning theory, which are often mathematically incompatible. This incompatibility arises from using different [[inference]] principles: principles which tell you how to generalize from limited data. The incompatibility also arises from differing definitions of [[probability]] (see [[frequentistfrequency probability]], [[Bayesian probability]]). The different approaches include:

* [[Probably approximately correct learning]] (PAC learning), proposed by [[Leslie Valiant]];

* [[VC theory]], proposed by [[Vladimir Vapnik]];