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

Graph

<?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>

www.000webhost.com