Automatically assigned DDC number: 00631
Manually assigned DDC number: 00631

Number of references: 8

Title: Efficient Agnostic Learning of Neural Networks with Bounded Fan-in

Author:

Author:

Author:

Subject: Wee Sun Lee,Peter L. Bartlett,Robert C. Williamson Efficient Agnostic Learning of Neural Networks with Bounded Fan-in

Description: We show that the class of two layer neural networks with bounded fan-in is efficiently learnable in a realistic extension to the Probably Approximately Correct (PAC) learning model. In this model, a joint probability distribution is assumed to exist on the observations and the learner is required to approximate the neural network which minimizes the expected quadratic error. As special cases, the model allows learning real-valued functions with bounded noise, learning probabilistic concepts and learning the best approximation to a target function that cannot be well approximated by the neural network. The networks we consider have real-valued inputs and outputs, an unlimited number of threshold hidden units with bounded fan-in, and a bound on the sum of the absolute values of the output weights. The number of computation This work was supported by the Australian Research Council and the Australian Telecommunications and Electronics Research Board. The material in this paper was pres...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1996-04-22

Pubyear: 1996

Format: ps

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

Source: http://wwwsyseng.anu.edu.au/~bartlett/papers/TR94b.ps.Z

Language: en

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

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

<references_metadata>

<rec ID="/243825.html" Type="inproceedings" CiteSeer_Book="Computational Learing Theory" CiteSeer_Volume="" Title="A Training Algorithm for Optimal Margin Classifiers,">

<identifier Org="ISBN:0123695317" Paper_ID="/243825.html" Extracted="0123695317" DDC="006.4" Normalized_DDC="0064" Normalized_Weight="0.09090909090909091" />

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

<identifier Org="ISBN:0262122413" Paper_ID="/243825.html" Extracted="0262122413" />

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

<identifier Org="ISBN:1586030604" Paper_ID="/243825.html" Extracted="1586030604" DDC="006.3/3" Normalized_DDC="00633" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:1586036424" Paper_ID="/243825.html" Extracted="1586036424" />

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

<identifier Org="ISBN:3540228810" Paper_ID="/243825.html" Extracted="3540228810" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.09090909090909091" />

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

<identifier Org="ISBN:3540292276" Paper_ID="/243825.html" Extracted="3540292276" DDC="005.758" Normalized_DDC="005758" Normalized_Weight="0.09090909090909091" />

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

<identifier Org="ISBN:3540423257" Paper_ID="/243825.html" Extracted="3540423257" DDC="004/.01/9" Normalized_DDC="004019" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540425969" Paper_ID="/243825.html" Extracted="3540425969" DDC="006.4/2" Normalized_DDC="00642" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540437444" Paper_ID="/243825.html" Extracted="3540437444" DDC="006.3/7" Normalized_DDC="00637" Normalized_Weight="0.09090909090909091" />

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

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

<identifier Org="ISBN:3540732721" Paper_ID="/243825.html" Extracted="3540732721" />

<identifier Org="ISBN:3540881913" Paper_ID="/243825.html" Extracted="3540881913" />

<identifier Org="ISBN:3540896384" Paper_ID="/243825.html" Extracted="3540896384" />

<identifier Org="ISBN:3540896880" Paper_ID="/243825.html" Extracted="3540896880" />

</rec>

<rec ID="/128963.html" Type="inproceedings" CiteSeer_Book="Machine Learning From Theory to Applications" CiteSeer_Volume="" Title="Training a 3-Node Neural Network is {NP}-Complete,">

<identifier Org="ISBN:0124790402" Paper_ID="/128963.html" Extracted="0124790402" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:0444894888" Paper_ID="/128963.html" Extracted="0444894888" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

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

<identifier Org="ISBN:0805811583" Paper_ID="/128963.html" Extracted="0805811583" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:0805821252" Paper_ID="/128963.html" Extracted="0805821252" />

<identifier Org="ISBN:0817636706" Paper_ID="/128963.html" Extracted="0817636706" DDC="003/.5" Normalized_DDC="0035" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:0835229777" Paper_ID="/128963.html" Extracted="0835229777" />

<identifier Org="ISBN:089871480X" Paper_ID="/128963.html" Extracted="089871480X" />

<identifier Org="ISBN:140200723X" Paper_ID="/128963.html" Extracted="140200723X" DDC="681/.2" Normalized_DDC="6812" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540238069" Paper_ID="/128963.html" Extracted="3540238069" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540306765" Paper_ID="/128963.html" Extracted="3540306765" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />

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

<identifier Org="ISBN:3540442650" Paper_ID="/128963.html" Extracted="3540442650" DDC="006.3/2" Normalized_DDC="00632" Normalized_Weight="0.06666666666666667" />

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

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

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

<identifier Org="ISBN:3540677046" Paper_ID="/128963.html" Extracted="3540677046" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.06666666666666667" />

<identifier Org="ISBN:3540746897" Paper_ID="/128963.html" Extracted="3540746897" />

<identifier Org="ISBN:981021815X" Paper_ID="/128963.html" Extracted="981021815X" DDC="612.8/2" Normalized_DDC="61282" Normalized_Weight="0.06666666666666667" />

</rec>

<rec ID="/678077.html" Type="incollection" CiteSeer_Book="Computational Learning Theory and Natural Learning Systems Volume I Constraints and Prospect edited by Stephen Jose Hanson George A Drastal and Ronald L Rivest BradfordMIT Press" CiteSeer_Volume="" Title="Efficient Distribution-free Learning of Probabilistic Concepts,">

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

<identifier Org="ISBN:0262201046" Paper_ID="/678077.html" Extracted="0262201046" />

<identifier Org="ISBN:0387564330" Paper_ID="/678077.html" Extracted="0387564330" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />

<identifier Org="ISBN:0444816925" Paper_ID="/678077.html" Extracted="0444816925" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />

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

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

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

<identifier Org="ISBN:0898712718" Paper_ID="/678077.html" Extracted="0898712718" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.0625" />

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

<identifier Org="ISBN:3540222820" Paper_ID="/678077.html" Extracted="3540222820" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.0625" />

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

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

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

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

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

<identifier Org="ISBN:3540573690" Paper_ID="/678077.html" Extracted="3540573690" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.0625" />

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

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

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

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

</rec>

<rec ID="/99782.html" Type="inproceedings" CiteSeer_Book="Computational Learing Theory" CiteSeer_Volume="" Title="Toward Efficient Agnostic Learning,">

<identifier Org="ISBN:0195147677" Paper_ID="/99782.html" Extracted="0195147677" DDC="128/.33" Normalized_DDC="12833" Normalized_Weight="0.07142857142857142" />

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

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

<identifier Org="ISBN:0897917235" Paper_ID="/99782.html" Extracted="0897917235" />

<identifier Org="ISBN:1586034529" Paper_ID="/99782.html" Extracted="1586034529" />

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

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

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

<identifier Org="ISBN:3540428755" Paper_ID="/99782.html" Extracted="3540428755" />

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

<identifier Org="ISBN:3540438629" Paper_ID="/99782.html" Extracted="3540438629" DDC="006.4015116" Normalized_DDC="0064015116" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:354061785X" Paper_ID="/99782.html" Extracted="354061785X" DDC="516/.00285" Normalized_DDC="51600285" Normalized_Weight="0.07142857142857142" />

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

<identifier Org="ISBN:354064380X" Paper_ID="/99782.html" Extracted="354064380X" DDC="004/.01/9" Normalized_DDC="004019" Normalized_Weight="0.07142857142857142" />

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

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

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

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

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

</rec>

<rec ID="/206820.html" Type="inproceedings" CiteSeer_Book="Computational Learing Theory" CiteSeer_Volume="" Title="The Importance of Convexity in Learning with Squared Loss,">

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

<identifier Org="ISBN:0262042061" Paper_ID="/206820.html" Extracted="0262042061" />

<identifier Org="ISBN:026208306X" Paper_ID="/206820.html" Extracted="026208306X" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:0262194163" Paper_ID="/206820.html" Extracted="0262194163" DDC="[E]" Normalized_DDC="" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:0262194759" Paper_ID="/206820.html" Extracted="0262194759" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:0387772413" Paper_ID="/206820.html" Extracted="0387772413" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:052157353X" Paper_ID="/206820.html" Extracted="052157353X" DDC="006.3/2" Normalized_DDC="00632" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:052186559X" Paper_ID="/206820.html" Extracted="052186559X" />

<identifier Org="ISBN:0871692333" Paper_ID="/206820.html" Extracted="0871692333" DDC="520/.938" Normalized_DDC="520938" Normalized_Weight="0.09090909090909091" />

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

<identifier Org="ISBN:1586038982" Paper_ID="/206820.html" Extracted="1586038982" />

<identifier Org="ISBN:3540005293" Paper_ID="/206820.html" Extracted="3540005293" />

<identifier Org="ISBN:3540222820" Paper_ID="/206820.html" Extracted="3540222820" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540223606" Paper_ID="/206820.html" Extracted="3540223606" DDC="510 s" Normalized_DDC="51" Normalized_Weight="0.09090909090909091" />

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

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

</rec>

<rec ID="/79933.html" Type="inproceedings" CiteSeer_Book="Computational Learing Theory" CiteSeer_Volume="" Title="On Efficient Agnostic Learning of Linear Combinations of Basis Functions,">

<identifier Org="ISBN:052157353X" Paper_ID="/79933.html" Extracted="052157353X" DDC="006.3/2" Normalized_DDC="00632" Normalized_Weight="0.5" />

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

</rec>

<rec ID="/224486.html" Type="inproceedings" CiteSeer_Book="Advances in Neural Information Processing Systems" CiteSeer_Volume="" Title="Agnostic {PAC}-Learning of Functions on Analog Neural Nets,">

<identifier Org="ISBN:0198534922" Paper_ID="/224486.html" Extracted="0198534922" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.14285714285714285" />

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

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

<identifier Org="ISBN:1558603778" Paper_ID="/224486.html" Extracted="1558603778" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:185233343X" Paper_ID="/224486.html" Extracted="185233343X" DDC="006.3/2" Normalized_DDC="00632" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:1852333731" Paper_ID="/224486.html" Extracted="1852333731" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:3540761209" Paper_ID="/224486.html" Extracted="3540761209" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.14285714285714285" />

</rec>

<rec ID="/190800.html" Type="misc" CiteSeer_Book="" CiteSeer_Volume="" Title="Uniform ratio limit theorems for empirical processes,">

<identifier Org="ISBN:0387946403" Paper_ID="/190800.html" Extracted="0387946403" DDC="519.2" Normalized_DDC="5192" Normalized_Weight="0.3333333333333333" />

<identifier Org="ISBN:052157353X" Paper_ID="/190800.html" Extracted="052157353X" DDC="006.3/2" Normalized_DDC="00632" Normalized_Weight="0.3333333333333333" />

<identifier Org="ISBN:3764321970" Paper_ID="/190800.html" Extracted="3764321970" DDC="519.2" Normalized_DDC="5192" Normalized_Weight="0.3333333333333333" />

</rec>

<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Efficient Agnostic Learning of Neural Networks with Bounded Fan-in">

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

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

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

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

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

<identifier Org="ISBN:0387954414" Paper_ID="SELF" Extracted="0387954414" DDC="519.5/36" Normalized_DDC="519536" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:0387987452" Paper_ID="SELF" Extracted="0387987452" DDC="006.3/2" Normalized_DDC="00632" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:052157353X" Paper_ID="SELF" Extracted="052157353X" DDC="006.3/2" Normalized_DDC="00632" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:0792381955" Paper_ID="SELF" Extracted="0792381955" DDC="620/.0042/015118" Normalized_DDC="6200042015118" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:0818681845" Paper_ID="SELF" Extracted="0818681845" DDC="621.367" Normalized_DDC="621367" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:0821847988" Paper_ID="SELF" Extracted="0821847988" DDC="511/.4" Normalized_DDC="5114" Normalized_Weight="0.09090909090909091" />

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

<identifier Org="ISBN:1852330449" Paper_ID="SELF" Extracted="1852330449" DDC="003" Normalized_DDC="003" Normalized_Weight="0.09090909090909091" />

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

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

</rec>

</references_metadata>