Automatically assigned DDC number: 00631

Manually assigned DDC number: 00631

Number of references: 16

Title: An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution

Author:

Subject: Jeffrey C. Jackson An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution

Description: We present a membership-query algorithm for efficiently learning DNF with respect to the uniform distribution. In fact, the algorithm properly learns with respect to uniform the class TOP of Boolean functions expressed as a majority vote over parity functions. We also describe extensions of this algorithm for learning DNF over certain nonuniform distributions and for learning a class of geometric concepts that generalizes DNF. Furthermore, we show that DNF is weakly learnable with respect to uniform from noisy examples. Our strong learning algorithm utilizes one of Freund's boosting techniques and relies on the fact that boosting does not require a completely distribution-independent weak learner. The boosted weak learner is a nonuniform extension of a parity-finding algorithm discovered by Goldreich and Levin. 3 1 Introduction Consider the following 20-questions-like game between two players, Bob and Alice. Bob has a Disjunctive Normal Form (DNF) expression f in mind. Alice is allo...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1997-03-13

Pubyear: 1994

Format: ps

Identifier: http://citeseer.ist.psu.edu/399260.html

Source: http://www.mathcs.duq.edu/~jackson/J97.ps

Language: en

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/94275.html"   Type="article"   CiteSeer_Book="Machine   Learning"   CiteSeer_Volume="9"   Title="Learning   Conjunctions   of   Horn   Clauses,">

            <identifier   Org="ISBN:0792392787"   Paper_ID="/94275.html"   Extracted="0792392787"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:081862082X"   Paper_ID="/94275.html"   Extracted="081862082X"   />

            <identifier   Org="ISBN:0897916115"   Paper_ID="/94275.html"   Extracted="0897916115"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0898712963"   Paper_ID="/94275.html"   Extracted="0898712963"   DDC="519.2"   Normalized_DDC="5192"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:1581130570"   Paper_ID="/94275.html"   Extracted="1581130570"   />

            <identifier   Org="ISBN:1581131674"   Paper_ID="/94275.html"   Extracted="1581131674"   />

            <identifier   Org="ISBN:3540233563"   Paper_ID="/94275.html"   Extracted="3540233563"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540407200"   Paper_ID="/94275.html"   Extracted="3540407200"   />

            <identifier   Org="ISBN:3540429859"   Paper_ID="/94275.html"   Extracted="3540429859"   DDC="004.015118"   Normalized_DDC="004015118"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540544585"   Paper_ID="/94275.html"   Extracted="3540544585"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540575685"   Paper_ID="/94275.html"   Extracted="3540575685"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540613323"   Paper_ID="/94275.html"   Extracted="3540613323"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540618635"   Paper_ID="/94275.html"   Extracted="3540618635"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540642307"   Paper_ID="/94275.html"   Extracted="3540642307"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:354065013X"   Paper_ID="/94275.html"   Extracted="354065013X"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540657010"   Paper_ID="/94275.html"   Extracted="3540657010"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540667482"   Paper_ID="/94275.html"   Extracted="3540667482"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540729259"   Paper_ID="/94275.html"   Extracted="3540729259"   />

            <identifier   Org="ISBN:3540879862"   Paper_ID="/94275.html"   Extracted="3540879862"   />

            <identifier   Org="ISBN:427490525X"   Paper_ID="/94275.html"   Extracted="427490525X"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

      </rec>

      <rec   ID="/511050.html"   Type="techreport"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="{THE}   {SPECTRAL}   {NORM}   {OF}   {FINITE}   {FUNCTIONS},">

            <identifier   Org="ISBN:0818665823"   Paper_ID="/511050.html"   Extracted="0818665823"   />

            <identifier   Org="ISBN:0897913973"   Paper_ID="/511050.html"   Extracted="0897913973"   />

      </rec>

      <rec   ID="/477497.html"   Type="inproceedings"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="Weakly   learning   {DNF}   and   characterizing   statistical   query   learning   using   {Fourier}   analysis,">

            <identifier   Org="ISBN:0262201070"   Paper_ID="/477497.html"   Extracted="0262201070"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:026251091X"   Paper_ID="/477497.html"   Extracted="026251091X"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:0387301623"   Paper_ID="/477497.html"   Extracted="0387301623"   DDC="518.103"   Normalized_DDC="518103"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:0818680377"   Paper_ID="/477497.html"   Extracted="0818680377"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:0897916638"   Paper_ID="/477497.html"   Extracted="0897916638"   DDC="004.01"   Normalized_DDC="00401"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:0897917235"   Paper_ID="/477497.html"   Extracted="0897917235"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:3540001700"   Paper_ID="/477497.html"   Extracted="3540001700"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:3540233563"   Paper_ID="/477497.html"   Extracted="3540233563"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:3540282394"   Paper_ID="/477497.html"   Extracted="3540282394"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:354029242X"   Paper_ID="/477497.html"   Extracted="354029242X"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:3540407200"   Paper_ID="/477497.html"   Extracted="3540407200"   />

            <identifier   Org="ISBN:3540423435"   Paper_ID="/477497.html"   Extracted="3540423435"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:3540428755"   Paper_ID="/477497.html"   Extracted="3540428755"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:3540591192"   Paper_ID="/477497.html"   Extracted="3540591192"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:3540609229"   Paper_ID="/477497.html"   Extracted="3540609229"   DDC="004/.01/511"   Normalized_DDC="00401511"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:3540613323"   Paper_ID="/477497.html"   Extracted="3540613323"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:3540626859"   Paper_ID="/477497.html"   Extracted="3540626859"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:3540709177"   Paper_ID="/477497.html"   Extracted="3540709177"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:3540735445"   Paper_ID="/477497.html"   Extracted="3540735445"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.05555555555555555"   />

            <identifier   Org="ISBN:3540853626"   Paper_ID="/477497.html"   Extracted="3540853626"   />

      </rec>

      <rec   ID="/602254.html"   Type="article"   CiteSeer_Book="SIAM   Journal   on   Computing"   CiteSeer_Volume="28"   Title="Exact   Learning   of   Discretized   Geometric   Concepts,">

            <identifier   Org="ISBN:0818665823"   Paper_ID="/602254.html"   Extracted="0818665823"   />

            <identifier   Org="ISBN:354043836X"   Paper_ID="/602254.html"   Extracted="354043836X"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:354060216X"   Paper_ID="/602254.html"   Extracted="354060216X"   DDC="004/.01/5116"   Normalized_DDC="004015116"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:3540626859"   Paper_ID="/602254.html"   Extracted="3540626859"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:3540635777"   Paper_ID="/602254.html"   Extracted="3540635777"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:3540879862"   Paper_ID="/602254.html"   Extracted="3540879862"   />

      </rec>

      <rec   ID="/34249.html"   Type="inproceedings"   CiteSeer_Book="COLT   Proceedings   of   the   Workshop   on   Computational   Learning   Theory   Morgan   Kaufmann   Publishers"   CiteSeer_Volume=""   Title="Boosting   a   Weak   Learning   Algorithm   by   Majority,">

            <identifier   Org="ISBN:0262025507"   Paper_ID="/34249.html"   Extracted="0262025507"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0262194503"   Paper_ID="/34249.html"   Extracted="0262194503"   />

            <identifier   Org="ISBN:0262201526"   Paper_ID="/34249.html"   Extracted="0262201526"   />

            <identifier   Org="ISBN:0897916115"   Paper_ID="/34249.html"   Extracted="0897916115"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0898712963"   Paper_ID="/34249.html"   Extracted="0898712963"   DDC="519.2"   Normalized_DDC="5192"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:140201757X"   Paper_ID="/34249.html"   Extracted="140201757X"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:1558604197"   Paper_ID="/34249.html"   Extracted="1558604197"   />

            <identifier   Org="ISBN:1581131674"   Paper_ID="/34249.html"   Extracted="1581131674"   />

            <identifier   Org="ISBN:3211007431"   Paper_ID="/34249.html"   Extracted="3211007431"   DDC="006.3/2"   Normalized_DDC="00632"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540001700"   Paper_ID="/34249.html"   Extracted="3540001700"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540005293"   Paper_ID="/34249.html"   Extracted="3540005293"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540233563"   Paper_ID="/34249.html"   Extracted="3540233563"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540265562"   Paper_ID="/34249.html"   Extracted="3540265562"   />

            <identifier   Org="ISBN:3540287558"   Paper_ID="/34249.html"   Extracted="3540287558"   DDC="006.32"   Normalized_DDC="00632"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:354029242X"   Paper_ID="/34249.html"   Extracted="354029242X"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540403698"   Paper_ID="/34249.html"   Extracted="3540403698"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540429123"   Paper_ID="/34249.html"   Extracted="3540429123"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540667482"   Paper_ID="/34249.html"   Extracted="3540667482"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540879862"   Paper_ID="/34249.html"   Extracted="3540879862"   />

            <identifier   Org="ISBN:9051993552"   Paper_ID="/34249.html"   Extracted="9051993552"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

      </rec>

      <rec   ID="/10394.html"   Type="inproceedings"   CiteSeer_Book="European   Conference   on   Computational   Learning   Theory"   CiteSeer_Volume=""   Title="A   decision-theoretic   generalization   of   on-line   learning   and   an   application   to   boosting,">

            <identifier   Org="ISBN:0262025507"   Paper_ID="/10394.html"   Extracted="0262025507"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0262194503"   Paper_ID="/10394.html"   Extracted="0262194503"   />

            <identifier   Org="ISBN:0262511290"   Paper_ID="/10394.html"   Extracted="0262511290"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0262731444"   Paper_ID="/10394.html"   Extracted="0262731444"   DDC="153.03"   Normalized_DDC="15303"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0821841955"   Paper_ID="/10394.html"   Extracted="0821841955"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:1402078676"   Paper_ID="/10394.html"   Extracted="1402078676"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:1581130570"   Paper_ID="/10394.html"   Extracted="1581130570"   />

            <identifier   Org="ISBN:1852334452"   Paper_ID="/10394.html"   Extracted="1852334452"   DDC="005.3"   Normalized_DDC="0053"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540005293"   Paper_ID="/10394.html"   Extracted="3540005293"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540140409"   Paper_ID="/10394.html"   Extracted="3540140409"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540211098"   Paper_ID="/10394.html"   Extracted="3540211098"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540265562"   Paper_ID="/10394.html"   Extracted="3540265562"   />

            <identifier   Org="ISBN:3540403698"   Paper_ID="/10394.html"   Extracted="3540403698"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540405046"   Paper_ID="/10394.html"   Extracted="3540405046"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540407200"   Paper_ID="/10394.html"   Extracted="3540407200"   />

            <identifier   Org="ISBN:354041066X"   Paper_ID="/10394.html"   Extracted="354041066X"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540421440"   Paper_ID="/10394.html"   Extracted="3540421440"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540618635"   Paper_ID="/10394.html"   Extracted="3540618635"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540742719"   Paper_ID="/10394.html"   Extracted="3540742719"   />

            <identifier   Org="ISBN:3540752242"   Paper_ID="/10394.html"   Extracted="3540752242"   />

      </rec>

      <rec   ID="/36963.html"   Type="inproceedings"   CiteSeer_Book="Computational   Learing   Theory"   CiteSeer_Volume=""   Title="Improved   Learning   of   {AC}   0   Functions,"   />

      <rec   ID="/179845.html"   Type="inproceedings"   CiteSeer_Book="Computational   Learing   Theory"   CiteSeer_Volume=""   Title="Learning   Unions   of   Boxes   with   Membership   and   Equivalence   Queries,">

            <identifier   Org="ISBN:0818665823"   Paper_ID="/179845.html"   Extracted="0818665823"   />

            <identifier   Org="ISBN:0897917235"   Paper_ID="/179845.html"   Extracted="0897917235"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:1558603352"   Paper_ID="/179845.html"   Extracted="1558603352"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:3540591192"   Paper_ID="/179845.html"   Extracted="3540591192"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:3540626859"   Paper_ID="/179845.html"   Extracted="3540626859"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.25"   />

      </rec>

      <rec   ID="/399260.html"   Type="inproceedings"   CiteSeer_Book="IEEE   Symposium   on   Foundations   of   Computer   Science"   CiteSeer_Volume=""   Title="An   Efficient   Membership-Query   Algorithm   for   Learning   {DNF}   with   Respect   to   the   Uniform   Distribution,">

            <identifier   Org="ISBN:0262201070"   Paper_ID="/399260.html"   Extracted="0262201070"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0387301623"   Paper_ID="/399260.html"   Extracted="0387301623"   DDC="518.103"   Normalized_DDC="518103"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0818665823"   Paper_ID="/399260.html"   Extracted="0818665823"   />

            <identifier   Org="ISBN:0818680377"   Paper_ID="/399260.html"   Extracted="0818680377"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0897917235"   Paper_ID="/399260.html"   Extracted="0897917235"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:1581131674"   Paper_ID="/399260.html"   Extracted="1581131674"   />

            <identifier   Org="ISBN:3540282394"   Paper_ID="/399260.html"   Extracted="3540282394"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:354029242X"   Paper_ID="/399260.html"   Extracted="354029242X"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540407200"   Paper_ID="/399260.html"   Extracted="3540407200"   />

            <identifier   Org="ISBN:3540423435"   Paper_ID="/399260.html"   Extracted="3540423435"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540430253"   Paper_ID="/399260.html"   Extracted="3540430253"   DDC="519.23"   Normalized_DDC="51923"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540604545"   Paper_ID="/399260.html"   Extracted="3540604545"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540613323"   Paper_ID="/399260.html"   Extracted="3540613323"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540626859"   Paper_ID="/399260.html"   Extracted="3540626859"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540635777"   Paper_ID="/399260.html"   Extracted="3540635777"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540668225"   Paper_ID="/399260.html"   Extracted="3540668225"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540729259"   Paper_ID="/399260.html"   Extracted="3540729259"   />

            <identifier   Org="ISBN:3540853626"   Paper_ID="/399260.html"   Extracted="3540853626"   />

            <identifier   Org="ISBN:3540879862"   Paper_ID="/399260.html"   Extracted="3540879862"   />

      </rec>

      <rec   ID="/223312.html"   Type="inproceedings"   CiteSeer_Book="Advances   in   Neural   Information   Processing   Systems"   CiteSeer_Volume=""   Title="Learning   Sparse   Perceptrons,">

            <identifier   Org="ISBN:0262195682"   Paper_ID="/223312.html"   Extracted="0262195682"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:0262201070"   Paper_ID="/223312.html"   Extracted="0262201070"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:1558604197"   Paper_ID="/223312.html"   Extracted="1558604197"   />

            <identifier   Org="ISBN:1558604863"   Paper_ID="/223312.html"   Extracted="1558604863"   />

            <identifier   Org="ISBN:2856291562"   Paper_ID="/223312.html"   Extracted="2856291562"   />

            <identifier   Org="ISBN:3540657010"   Paper_ID="/223312.html"   Extracted="3540657010"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:3540667482"   Paper_ID="/223312.html"   Extracted="3540667482"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.25"   />

      </rec>

      <rec   ID="/665710.html"   Type="inproceedings"   CiteSeer_Book="Proceedings   of   the   nineteenth   annual   ACM   Symposium   on   Theory   of   Computing   New   York   City   May   2527   1987"   CiteSeer_Volume=""   Title="On   the   Learnability   of   {Boolean}   Formulae,">

            <identifier   Org="ISBN:0201409836"   Paper_ID="/665710.html"   Extracted="0201409836"   DDC="003/.1"   Normalized_DDC="0031"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0262111527"   Paper_ID="/665710.html"   Extracted="0262111527"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0262510715"   Paper_ID="/665710.html"   Extracted="0262510715"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0805807756"   Paper_ID="/665710.html"   Extracted="0805807756"   />

            <identifier   Org="ISBN:0818619821"   Paper_ID="/665710.html"   Extracted="0818619821"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:081862082X"   Paper_ID="/665710.html"   Extracted="081862082X"   />

            <identifier   Org="ISBN:0897912217"   Paper_ID="/665710.html"   Extracted="0897912217"   />

            <identifier   Org="ISBN:0897913078"   Paper_ID="/665710.html"   Extracted="0897913078"   />

            <identifier   Org="ISBN:0897913973"   Paper_ID="/665710.html"   Extracted="0897913973"   />

            <identifier   Org="ISBN:0897915119"   Paper_ID="/665710.html"   Extracted="0897915119"   />

            <identifier   Org="ISBN:0897916115"   Paper_ID="/665710.html"   Extracted="0897916115"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0897916638"   Paper_ID="/665710.html"   Extracted="0897916638"   DDC="004.01"   Normalized_DDC="00401"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0898712726"   Paper_ID="/665710.html"   Extracted="0898712726"   DDC="004/.072"   Normalized_DDC="004072"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0898712963"   Paper_ID="/665710.html"   Extracted="0898712963"   DDC="519.2"   Normalized_DDC="5192"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0898713293"   Paper_ID="/665710.html"   Extracted="0898713293"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540194886"   Paper_ID="/665710.html"   Extracted="3540194886"   />

            <identifier   Org="ISBN:3540428755"   Paper_ID="/665710.html"   Extracted="3540428755"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540564837"   Paper_ID="/665710.html"   Extracted="3540564837"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540609229"   Paper_ID="/665710.html"   Extracted="3540609229"   DDC="004/.01/511"   Normalized_DDC="00401511"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540653856"   Paper_ID="/665710.html"   Extracted="3540653856"   DDC="004.015118"   Normalized_DDC="004015118"   Normalized_Weight="0.07692307692307693"   />

      </rec>

      <rec   ID="/271923.html"   Type="inproceedings"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="On   the   computational   power   of   depth   2   circuits   with   threshold   and   modulo   gates,">

            <identifier   Org="ISBN:0769510531"   Paper_ID="/271923.html"   Extracted="0769510531"   />

            <identifier   Org="ISBN:0769514685"   Paper_ID="/271923.html"   Extracted="0769514685"   />

            <identifier   Org="ISBN:0780342674"   Paper_ID="/271923.html"   Extracted="0780342674"   DDC="511"   Normalized_DDC="511"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0818665823"   Paper_ID="/271923.html"   Extracted="0818665823"   />

            <identifier   Org="ISBN:0897916638"   Paper_ID="/271923.html"   Extracted="0897916638"   DDC="004.01"   Normalized_DDC="00401"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:1581134959"   Paper_ID="/271923.html"   Extracted="1581134959"   />

            <identifier   Org="ISBN:1595936319"   Paper_ID="/271923.html"   Extracted="1595936319"   />

            <identifier   Org="ISBN:3540275800"   Paper_ID="/271923.html"   Extracted="3540275800"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540287027"   Paper_ID="/271923.html"   Extracted="3540287027"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540430024"   Paper_ID="/271923.html"   Extracted="3540430024"   DDC="005"   Normalized_DDC="005"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:354043836X"   Paper_ID="/271923.html"   Extracted="354043836X"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540590420"   Paper_ID="/271923.html"   Extracted="3540590420"   DDC="004/.01/511"   Normalized_DDC="00401511"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540591753"   Paper_ID="/271923.html"   Extracted="3540591753"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540620346"   Paper_ID="/271923.html"   Extracted="3540620346"   DDC="001.64"   Normalized_DDC="00164"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540626859"   Paper_ID="/271923.html"   Extracted="3540626859"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3765719528"   Paper_ID="/271923.html"   Extracted="3765719528"   />

      </rec>

      <rec   ID="/11864.html"   Type="inproceedings"   CiteSeer_Book="Computational   Learing   Theory"   CiteSeer_Volume=""   Title="On   Learning   Visual   Concepts   and   {DNF}   Formulae,">

            <identifier   Org="ISBN:0780343166"   Paper_ID="/11864.html"   Extracted="0780343166"   />

            <identifier   Org="ISBN:0818665823"   Paper_ID="/11864.html"   Extracted="0818665823"   />

            <identifier   Org="ISBN:0897916115"   Paper_ID="/11864.html"   Extracted="0897916115"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:0897916638"   Paper_ID="/11864.html"   Extracted="0897916638"   DDC="004.01"   Normalized_DDC="00401"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:0897917235"   Paper_ID="/11864.html"   Extracted="0897917235"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:1558604197"   Paper_ID="/11864.html"   Extracted="1558604197"   />

            <identifier   Org="ISBN:1581133499"   Paper_ID="/11864.html"   Extracted="1581133499"   />

            <identifier   Org="ISBN:3540407200"   Paper_ID="/11864.html"   Extracted="3540407200"   />

            <identifier   Org="ISBN:3540407707"   Paper_ID="/11864.html"   Extracted="3540407707"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:3540668225"   Paper_ID="/11864.html"   Extracted="3540668225"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.2"   />

      </rec>

      <rec   ID="/292486.html"   Type="techreport"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="{COMPOSITE}   {GEOMETRIC}   {CONCEPTS}   {AND}   {POLYNOMIAL}   {PREDICTABILITY},">

            <identifier   Org="ISBN:0195085914"   Paper_ID="/292486.html"   Extracted="0195085914"   DDC="005.2"   Normalized_DDC="0052"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0262111934"   Paper_ID="/292486.html"   Extracted="0262111934"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0444891781"   Paper_ID="/292486.html"   Extracted="0444891781"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:079239478X"   Paper_ID="/292486.html"   Extracted="079239478X"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0805812016"   Paper_ID="/292486.html"   Extracted="0805812016"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0818643706"   Paper_ID="/292486.html"   Extracted="0818643706"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0818665823"   Paper_ID="/292486.html"   Extracted="0818665823"   />

            <identifier   Org="ISBN:0818681985"   Paper_ID="/292486.html"   Extracted="0818681985"   />

            <identifier   Org="ISBN:0821837931"   Paper_ID="/292486.html"   Extracted="0821837931"   />

            <identifier   Org="ISBN:0897915119"   Paper_ID="/292486.html"   Extracted="0897915119"   />

            <identifier   Org="ISBN:0897917235"   Paper_ID="/292486.html"   Extracted="0897917235"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0897917855"   Paper_ID="/292486.html"   Extracted="0897917855"   />

            <identifier   Org="ISBN:1558601481"   Paper_ID="/292486.html"   Extracted="1558601481"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:354060216X"   Paper_ID="/292486.html"   Extracted="354060216X"   DDC="004/.01/5116"   Normalized_DDC="004015116"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540626859"   Paper_ID="/292486.html"   Extracted="3540626859"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.1"   />

      </rec>

      <rec   ID="/112411.html"   Type="inproceedings"   CiteSeer_Book="Fifth   Annual   Workshop   on   Computational   Learning   Theory"   CiteSeer_Volume=""   Title="An   $O(n^{log   log   n})$   learning   algorithm   for   {DNF}   under   the   uniform   distribution,"   />

      <rec   ID="/543817.html"   Type="article"   CiteSeer_Book="Machine   Learning"   CiteSeer_Volume="5"   Title="The   Strength   of   Weak   Learnability,">

            <identifier   Org="ISBN:0262731444"   Paper_ID="/543817.html"   Extracted="0262731444"   DDC="153.03"   Normalized_DDC="15303"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0387301623"   Paper_ID="/543817.html"   Extracted="0387301623"   DDC="518.103"   Normalized_DDC="518103"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0805829415"   Paper_ID="/543817.html"   Extracted="0805829415"   />

            <identifier   Org="ISBN:0818619821"   Paper_ID="/543817.html"   Extracted="0818619821"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0824722957"   Paper_ID="/543817.html"   Extracted="0824722957"   />

            <identifier   Org="ISBN:0897916115"   Paper_ID="/543817.html"   Extracted="0897916115"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0898712963"   Paper_ID="/543817.html"   Extracted="0898712963"   DDC="519.2"   Normalized_DDC="5192"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540001700"   Paper_ID="/543817.html"   Extracted="3540001700"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:354000971X"   Paper_ID="/543817.html"   Extracted="354000971X"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540253815"   Paper_ID="/543817.html"   Extracted="3540253815"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540256776"   Paper_ID="/543817.html"   Extracted="3540256776"   DDC="001.01/2"   Normalized_DDC="001012"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540403698"   Paper_ID="/543817.html"   Extracted="3540403698"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:354041066X"   Paper_ID="/543817.html"   Extracted="354041066X"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540414134"   Paper_ID="/543817.html"   Extracted="3540414134"   DDC="005"   Normalized_DDC="005"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540424237"   Paper_ID="/543817.html"   Extracted="3540424237"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540437851"   Paper_ID="/543817.html"   Extracted="3540437851"   DDC="006.3/3"   Normalized_DDC="00633"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540439412"   Paper_ID="/543817.html"   Extracted="3540439412"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540653902"   Paper_ID="/543817.html"   Extracted="3540653902"   DDC="501"   Normalized_DDC="501"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:9051993552"   Paper_ID="/543817.html"   Extracted="9051993552"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.058823529411764705"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="An   Efficient   Membership-Query   Algorithm   for   Learning   DNF   with   Respect   to   the   Uniform   Distribution">

            <identifier   Org="ISBN:0262201070"   Paper_ID="SELF"   Extracted="0262201070"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0387301623"   Paper_ID="SELF"   Extracted="0387301623"   DDC="518.103"   Normalized_DDC="518103"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0818665823"   Paper_ID="SELF"   Extracted="0818665823"   />

            <identifier   Org="ISBN:0818680377"   Paper_ID="SELF"   Extracted="0818680377"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0897917235"   Paper_ID="SELF"   Extracted="0897917235"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:1581131674"   Paper_ID="SELF"   Extracted="1581131674"   />

            <identifier   Org="ISBN:3540282394"   Paper_ID="SELF"   Extracted="3540282394"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:354029242X"   Paper_ID="SELF"   Extracted="354029242X"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540407200"   Paper_ID="SELF"   Extracted="3540407200"   />

            <identifier   Org="ISBN:3540423435"   Paper_ID="SELF"   Extracted="3540423435"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540430253"   Paper_ID="SELF"   Extracted="3540430253"   DDC="519.23"   Normalized_DDC="51923"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540604545"   Paper_ID="SELF"   Extracted="3540604545"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540613323"   Paper_ID="SELF"   Extracted="3540613323"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540626859"   Paper_ID="SELF"   Extracted="3540626859"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540635777"   Paper_ID="SELF"   Extracted="3540635777"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540668225"   Paper_ID="SELF"   Extracted="3540668225"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540729259"   Paper_ID="SELF"   Extracted="3540729259"   />

            <identifier   Org="ISBN:3540853626"   Paper_ID="SELF"   Extracted="3540853626"   />

            <identifier   Org="ISBN:3540879862"   Paper_ID="SELF"   Extracted="3540879862"   />

      </rec>

</references_metadata>