Automatically assigned DDC number: 00631
Manually assigned DDC number: 00631
Number of references: 4
Title: Bounds on the Sample Complexity of Bayesian Learning Using Information Theory and the VC Dimension
Author:
Author:
Author:
Subject: David Haussler,Michael Kearns,Robert Schapire Bounds on the Sample Complexity of Bayesian Learning Using Information Theory and the VC Dimension
Description: In this paper we study a Bayesian or average-case model of concept learning with a twofold goal: to provide more precise characterizations of learning curve (sample complexity) behavior that depend on properties of both the prior distribution over concepts and the sequence of instances seen by the learner, and to smoothly unite in a common framework the popular statistical physics and VC dimension theories of learning curves. To achieve this, we undertake a systematic investigation and comparison of two fundamental quantities in learning and information theory: the probability of an incorrect prediction for an optimal learning algorithm, and the Shannon information gain. This study leads to a new understanding of the sample complexity of learning in several existing models. 1 Introduction Consider a simple concept learning model in which the learner attempts to infer an unknown target concept f , chosen from a known concept class F of f0; 1g-valued functions over an instance space X....
Contributor: The Pennsylvania State University CiteSeer Archives
Publisher: unknown
Date: 1992-07-09
Pubyear: 1992
Format: ps
Identifier: http://citeseer.ist.psu.edu/142690.html
Source: ftp://ftp.cse.ucsc.edu/pub/tr/ucsc-crl-91-44.ps.Z
Language: en
Relation:
Relation:
Relation:
Relation:
Rights: unrestricted
<?xml version="1.0" encoding="UTF-8"?>
<references_metadata>
<rec ID="/186344.html" Type="phdthesis" CiteSeer_Book="" CiteSeer_Volume="" Title="A Theory of Learning Classification Rules,">
<identifier Org="ISBN:0198538677" Paper_ID="/186344.html" Extracted="0198538677" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0201409852" Paper_ID="/186344.html" Extracted="0201409852" DDC="003/.1" Normalized_DDC="0031" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0262600323" Paper_ID="/186344.html" Extracted="0262600323" DDC="519.5" Normalized_DDC="5195" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0387244352" Paper_ID="/186344.html" Extracted="0387244352" DDC="006.3/12" Normalized_DDC="006312" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0387947361" Paper_ID="/186344.html" Extracted="0387947361" DDC="006.3/01/5195" Normalized_DDC="0063015195" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0897917235" Paper_ID="/186344.html" Extracted="0897917235" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.0625" />
<identifier Org="ISBN:155860412X" Paper_ID="/186344.html" Extracted="155860412X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:1558604863" Paper_ID="/186344.html" Extracted="1558604863" />
<identifier Org="ISBN:158488360X" Paper_ID="/186344.html" Extracted="158488360X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540403698" Paper_ID="/186344.html" Extracted="3540403698" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540422897" Paper_ID="/186344.html" Extracted="3540422897" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540578684" Paper_ID="/186344.html" Extracted="3540578684" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540591192" Paper_ID="/186344.html" Extracted="3540591192" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540633464" Paper_ID="/186344.html" Extracted="3540633464" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540858350" Paper_ID="/186344.html" Extracted="3540858350" />
<identifier Org="ISBN:9051992424" Paper_ID="/186344.html" Extracted="9051992424" />
<identifier Org="ISBN:9812387188" Paper_ID="/186344.html" Extracted="9812387188" DDC="368.01" Normalized_DDC="36801" Normalized_Weight="0.0625" />
<identifier Org="ISBN:9812560793" Paper_ID="/186344.html" Extracted="9812560793" DDC="518" Normalized_DDC="518" Normalized_Weight="0.0625" />
<identifier Org="ISBN:9812771719" Paper_ID="/186344.html" Extracted="9812771719" DDC="006.312" Normalized_DDC="006312" Normalized_Weight="0.0625" />
</rec>
<rec ID="/291274.html" Type="techreport" CiteSeer_Book="" CiteSeer_Volume="" Title="{SPHERE} {PACKING} {NUMBERS} {FOR} {SUBSETS} {OF} {THE} {BOOLEAN} n-{CUBE} {WITH} {BOUNDED} {VAPNIK}-{CHERVONENKIS} {DIMENSION},">
<identifier Org="ISBN:0262195682" Paper_ID="/291274.html" Extracted="0262195682" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:0387946187" Paper_ID="/291274.html" Extracted="0387946187" DDC="003/.52/015192" Normalized_DDC="00352015192" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:0387946403" Paper_ID="/291274.html" Extracted="0387946403" DDC="519.2" Normalized_DDC="5192" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:0387951172" Paper_ID="/291274.html" Extracted="0387951172" DDC="512.2/4" Normalized_DDC="51224" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:0471370460" Paper_ID="/291274.html" Extracted="0471370460" DDC="511/.6" Normalized_DDC="5116" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:0521461022" Paper_ID="/291274.html" Extracted="0521461022" DDC="519.2" Normalized_DDC="5192" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:052157353X" Paper_ID="/291274.html" Extracted="052157353X" DDC="006.3/2" Normalized_DDC="00632" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:0546662277" Paper_ID="/291274.html" Extracted="0546662277" />
<identifier Org="ISBN:0805812016" Paper_ID="/291274.html" Extracted="0805812016" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:0817636579" Paper_ID="/291274.html" Extracted="0817636579" DDC="519.2" Normalized_DDC="5192" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:1581130570" Paper_ID="/291274.html" Extracted="1581130570" />
<identifier Org="ISBN:1584883014" Paper_ID="/291274.html" Extracted="1584883014" DDC="516/.13" Normalized_DDC="51613" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540222820" Paper_ID="/291274.html" Extracted="3540222820" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540231226" Paper_ID="/291274.html" Extracted="3540231226" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540265562" Paper_ID="/291274.html" Extracted="3540265562" />
<identifier Org="ISBN:3540424237" Paper_ID="/291274.html" Extracted="3540424237" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:354065528X" Paper_ID="/291274.html" Extracted="354065528X" DDC="512/.7" Normalized_DDC="5127" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3764354984" Paper_ID="/291274.html" Extracted="3764354984" DDC="510" Normalized_DDC="51" Normalized_Weight="0.06666666666666667" />
</rec>
<rec ID="/101913.html" Type="inproceedings" CiteSeer_Book="" CiteSeer_Volume="" Title="On-line learning of linear functions,">
<identifier Org="ISBN:0198534922" Paper_ID="/101913.html" Extracted="0198534922" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0201409852" Paper_ID="/101913.html" Extracted="0201409852" DDC="003/.1" Normalized_DDC="0031" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0521841089" Paper_ID="/101913.html" Extracted="0521841089" DDC="519.3" Normalized_DDC="5193" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0792392787" Paper_ID="/101913.html" Extracted="0792392787" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0897913973" Paper_ID="/101913.html" Extracted="0897913973" />
<identifier Org="ISBN:0897915917" Paper_ID="/101913.html" Extracted="0897915917" />
<identifier Org="ISBN:0897916115" Paper_ID="/101913.html" Extracted="0897916115" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0897917189" Paper_ID="/101913.html" Extracted="0897917189" DDC="004" Normalized_DDC="004" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0897917235" Paper_ID="/101913.html" Extracted="0897917235" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0897918916" Paper_ID="/101913.html" Extracted="0897918916" />
<identifier Org="ISBN:1581130570" Paper_ID="/101913.html" Extracted="1581130570" />
<identifier Org="ISBN:1581131674" Paper_ID="/101913.html" Extracted="1581131674" />
<identifier Org="ISBN:3540005293" Paper_ID="/101913.html" Extracted="3540005293" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540258787" Paper_ID="/101913.html" Extracted="3540258787" DDC="006.33" Normalized_DDC="00633" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540430806" Paper_ID="/101913.html" Extracted="3540430806" />
<identifier Org="ISBN:3540591192" Paper_ID="/101913.html" Extracted="3540591192" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540635777" Paper_ID="/101913.html" Extracted="3540635777" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.09090909090909091" />
</rec>
<rec ID="/299808.html" Type="inproceedings" CiteSeer_Book="Proceedings of the Fourth Annual Workshop on Computational Learning Theory" CiteSeer_Volume="" Title="Calculation of the learning curve of {B}ayes optimal classification algorithm for learning a perceptron with noise," />
<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Bounds on the Sample Complexity of Bayesian Learning Using Information Theory and the VC Dimension">
<identifier Org="ISBN:0201409836" Paper_ID="SELF" Extracted="0201409836" DDC="003/.1" Normalized_DDC="0031" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0262112450" Paper_ID="SELF" Extracted="0262112450" />
<identifier Org="ISBN:0262194503" Paper_ID="SELF" Extracted="0262194503" />
<identifier Org="ISBN:0412465302" Paper_ID="SELF" Extracted="0412465302" DDC="515/.352" Normalized_DDC="515352" Normalized_Weight="0.0625" />
<identifier Org="ISBN:079232031X" Paper_ID="SELF" Extracted="079232031X" DDC="502.8" Normalized_DDC="5028" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0817638253" Paper_ID="SELF" Extracted="0817638253" DDC="006.3/7" Normalized_DDC="00637" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0897917235" Paper_ID="SELF" Extracted="0897917235" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0898712963" Paper_ID="SELF" Extracted="0898712963" DDC="519.2" Normalized_DDC="5192" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0898713358" Paper_ID="SELF" Extracted="0898713358" DDC="006.3/7" Normalized_DDC="00637" Normalized_Weight="0.0625" />
<identifier Org="ISBN:1581130570" Paper_ID="SELF" Extracted="1581130570" />
<identifier Org="ISBN:1841500062" Paper_ID="SELF" Extracted="1841500062" DDC="006.3/2" Normalized_DDC="00632" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540222820" Paper_ID="SELF" Extracted="3540222820" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540424865" Paper_ID="SELF" Extracted="3540424865" DDC="006.3/2" Normalized_DDC="00632" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540425365" Paper_ID="SELF" Extracted="3540425365" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540591192" Paper_ID="SELF" Extracted="3540591192" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540657010" Paper_ID="SELF" Extracted="3540657010" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540660690" Paper_ID="SELF" Extracted="3540660690" DDC="573/.8" Normalized_DDC="5738" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3764354984" Paper_ID="SELF" Extracted="3764354984" DDC="510" Normalized_DDC="51" Normalized_Weight="0.0625" />
<identifier Org="ISBN:9051992424" Paper_ID="SELF" Extracted="9051992424" DDC="005.1/15" Normalized_DDC="005115" Normalized_Weight="0.0625" />
</rec>
</references_metadata>