Computational learning theory: Difference between revisions

Revision as of 00:02, 8 October 2024

Revision as of 03:41, 9 October 2024

Line 13:

* Positive results{{spaced ndash}}Showing that a certain class of functions is learnable in polynomial time.

* Negative results{{spaced ndash}}Showing that certain classes cannot be learned in polynomial time.<ref>{{Cite book |lastlast1=Kearns |firstfirst1=Michael |title=An Introduction to Computational Learning Theory |last2=Vazirani |first2=Umesh |date=August 15, 1994 |publisher=MIT Press |year=1994 |isbn=978-0262111935}}</ref>

Negative results often rely on commonly believed, but yet unproven assumptions,{{citation needed|date=October 2017}} such as:

Line 25:

* [[Probably approximately correct learning]] (PAC learning), proposed by [[Leslie Valiant]];<ref>{{cite journal |last1=Valiant |first1=Leslie |title=A Theory of the Learnable |journal=Communications of the ACM |date=1984 |volume=27 |issue=11 |pages=1134–1142 |doi=10.1145/1968.1972 |s2cid=12837541 |url=https://www.montefiore.ulg.ac.be/~geurts/Cours/AML/Readings/Valiant.pdf |ref=ValTotL |access-date=2022-11-24 |archive-date=2019-05-17 |archive-url=https://web.archive.org/web/20190517235548/http://www.montefiore.ulg.ac.be/~geurts/Cours/AML/Readings/Valiant.pdf |url-status=dead }}</ref>

* [[VC theory]], proposed by [[Vladimir Vapnik]] and [[Alexey Chervonenkis]];<ref>{{cite journal |last1=Vapnik |first1=V. |last2=Chervonenkis |first2=A. |title=On the uniform convergence of relative frequencies of events to their probabilities |journal=Theory of Probability and Its Applications |date=1971 |volume=16 |issue=2 |pages=264–280 |doi=10.1137/1116025 |url=https://courses.engr.illinois.edu/ece544na/fa2014/vapnik71.pdf |ref=VCdim}}</ref>

* [[Solomonoff's theory of inductive inference|Inductive inference]] as developed by [[Ray Solomonoff]];<ref>{{cite journal |last1=Solomonoff |first1=Ray |title=A Formal Theory of Inductive Inference Part 1 |journal=Information and Control |date=March 1964 |volume=7 |issue=1 |pages=1-221–22 |doi=10.1016/S0019-9958(64)90223-2|doi-access=free }}</ref><ref>{{cite journal |last1=Solomonoff |first1=Ray |title=A Formal Theory of Inductive Inference Part 2 |journal=Information and Control |date=1964 |volume=7 |issue=2 |pages=224-254224–254 |doi=10.1016/S0019-9958(64)90131-7}}</ref>

* [[Algorithmic learning theory]], from the work of [[E. Mark Gold]];<ref>{{Cite journal | last1 = Gold | first1 = E. Mark | year = 1967 | title = Language identification in the limit | journal = Information and Control | volume = 10 | issue = 5 | pages = 447–474 | doi = 10.1016/S0019-9958(67)91165-5 | url=http://web.mit.edu/~6.863/www/spring2009/readings/gold67limit.pdf | doi-access = free }}</ref>

* [[Online machine learning]], from the work of Nick Littlestone{{citation needed|date=October 2017}}.