A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Part of a series on |
Machine learning and data mining |
---|
In computational learning theory, Occam learning is a model of algorithmic learning where the objective of the learner is to output a succinct representation of received training data. This is closely related to probably approximately correct (PAC) learning, where the learner is evaluated on its predictive power of a test set.
Occam learnability implies PAC learning, and for a wide variety of concept classes, the converse is also true: PAC learnability implies Occam learnability.
Introduction
Occam Learning is named after Occam's razor, which is a principle stating that, given all other things being equal, a shorter explanation for observed data should be favored over a lengthier explanation. The theory of Occam learning is a formal and mathematical justification for this principle. It was first shown by Blumer, et al.[1] that Occam learning implies PAC learning, which is the standard model of learning in computational learning theory. In other words, parsimony (of the output hypothesis) implies predictive power.
Definition of Occam learning
The succinctness of a concept in concept class can be expressed by the length of the shortest bit string that can represent in . Occam learning connects the succinctness of a learning algorithm's output to its predictive power on unseen data.
Let and be concept classes containing target concepts and hypotheses respectively. Then, for constants and , a learning algorithm is an -Occam algorithm for using iff, given a set of samples labeled according to a concept , outputs a hypothesis such that
where is the maximum length of any sample . An Occam algorithm is called efficient if it runs in time polynomial in , , and We say a concept class is Occam learnable with respect to a hypothesis class if there exists an efficient Occam algorithm for using
The relation between Occam and PAC learning
Occam learnability implies PAC learnability, as the following theorem of Blumer, et al.[2] shows:
Theorem (Occam learning implies PAC learning)
Let be an efficient -Occam algorithm for using . Then there exists a constant such that for any , for any distribution , given
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk