Tight bounds on the size of neural networks for classification problems

Valeriu Beiu; Thierry De Pauw

doi:10.1007/bfb0032533

Tight bounds on the size of neural networks for classification problems

Valeriu Beiu, Thierry De Pauw

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Citations (Scopus)

Abstract

This paper relies on the entropy of a data-set (i.e., number-of-bits) to prove tight bounds on the size of neural networks solving a classification problem. First, based on a sequence of geometrical steps, we constructively compute an upper bound of O(mn) on the number-of-bits for a given dataset- here m is the number of examples and n is the number of dimensions (i.e., IR ⁿ). This result is used further in a nonconstructive way to bound the size of neural networks which correctly classify that data-set.

Original language	English
Title of host publication	Biological and Artificial Computation
Subtitle of host publication	From Neuroscience to Technology - International Work-Conference on Artificial and Natural Neural Networks, IWANN 1997, Proceedings
Publisher	Springer Verlag
Pages	743-752
Number of pages	10
ISBN (Print)	3540630473, 9783540630470
DOIs	https://doi.org/10.1007/bfb0032533
Publication status	Published - 1997
Externally published	Yes
Event	4th International Work-Conference on Artificial and Natural Neural Networks, IWANN 1997 - Lanzarote, Canary Islands, Spain Duration: Jun 4 1997 → Jun 6 1997

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1240 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	4th International Work-Conference on Artificial and Natural Neural Networks, IWANN 1997
Country/Territory	Spain
City	Lanzarote, Canary Islands
Period	6/4/97 → 6/6/97

Keywords

Boolean functions
Classification problems
Entropy
Neural networks
Size complexity

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/bfb0032533

Cite this

Beiu, V., & De Pauw, T. (1997). Tight bounds on the size of neural networks for classification problems. In Biological and Artificial Computation: From Neuroscience to Technology - International Work-Conference on Artificial and Natural Neural Networks, IWANN 1997, Proceedings (pp. 743-752). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1240 LNCS). Springer Verlag. https://doi.org/10.1007/bfb0032533

Tight bounds on the size of neural networks for classification problems. / Beiu, Valeriu; De Pauw, Thierry.
Biological and Artificial Computation: From Neuroscience to Technology - International Work-Conference on Artificial and Natural Neural Networks, IWANN 1997, Proceedings. Springer Verlag, 1997. p. 743-752 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1240 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Beiu, V & De Pauw, T 1997, Tight bounds on the size of neural networks for classification problems. in Biological and Artificial Computation: From Neuroscience to Technology - International Work-Conference on Artificial and Natural Neural Networks, IWANN 1997, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1240 LNCS, Springer Verlag, pp. 743-752, 4th International Work-Conference on Artificial and Natural Neural Networks, IWANN 1997, Lanzarote, Canary Islands, Spain, 6/4/97. https://doi.org/10.1007/bfb0032533

Beiu V, De Pauw T. Tight bounds on the size of neural networks for classification problems. In Biological and Artificial Computation: From Neuroscience to Technology - International Work-Conference on Artificial and Natural Neural Networks, IWANN 1997, Proceedings. Springer Verlag. 1997. p. 743-752. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0032533

Beiu, Valeriu ; De Pauw, Thierry. / Tight bounds on the size of neural networks for classification problems. Biological and Artificial Computation: From Neuroscience to Technology - International Work-Conference on Artificial and Natural Neural Networks, IWANN 1997, Proceedings. Springer Verlag, 1997. pp. 743-752 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b2bc5316e1994f5ea331a6394a8684ee,

title = "Tight bounds on the size of neural networks for classification problems",

abstract = "This paper relies on the entropy of a data-set (i.e., number-of-bits) to prove tight bounds on the size of neural networks solving a classification problem. First, based on a sequence of geometrical steps, we constructively compute an upper bound of O(mn) on the number-of-bits for a given dataset- here m is the number of examples and n is the number of dimensions (i.e., IR n). This result is used further in a nonconstructive way to bound the size of neural networks which correctly classify that data-set.",

keywords = "Boolean functions, Classification problems, Entropy, Neural networks, Size complexity",

author = "Valeriu Beiu and {De Pauw}, Thierry",

year = "1997",

doi = "10.1007/bfb0032533",

language = "English",

isbn = "3540630473",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "743--752",

booktitle = "Biological and Artificial Computation",

note = "4th International Work-Conference on Artificial and Natural Neural Networks, IWANN 1997 ; Conference date: 04-06-1997 Through 06-06-1997",

}

TY - GEN

T1 - Tight bounds on the size of neural networks for classification problems

AU - Beiu, Valeriu

AU - De Pauw, Thierry

PY - 1997

Y1 - 1997

N2 - This paper relies on the entropy of a data-set (i.e., number-of-bits) to prove tight bounds on the size of neural networks solving a classification problem. First, based on a sequence of geometrical steps, we constructively compute an upper bound of O(mn) on the number-of-bits for a given dataset- here m is the number of examples and n is the number of dimensions (i.e., IR n). This result is used further in a nonconstructive way to bound the size of neural networks which correctly classify that data-set.

AB - This paper relies on the entropy of a data-set (i.e., number-of-bits) to prove tight bounds on the size of neural networks solving a classification problem. First, based on a sequence of geometrical steps, we constructively compute an upper bound of O(mn) on the number-of-bits for a given dataset- here m is the number of examples and n is the number of dimensions (i.e., IR n). This result is used further in a nonconstructive way to bound the size of neural networks which correctly classify that data-set.

KW - Boolean functions

KW - Classification problems

KW - Entropy

KW - Neural networks

KW - Size complexity

UR - http://www.scopus.com/inward/record.url?scp=84902189013&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902189013&partnerID=8YFLogxK

U2 - 10.1007/bfb0032533

DO - 10.1007/bfb0032533

M3 - Conference contribution

AN - SCOPUS:84902189013

SN - 3540630473

SN - 9783540630470

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 743

EP - 752

BT - Biological and Artificial Computation

PB - Springer Verlag

T2 - 4th International Work-Conference on Artificial and Natural Neural Networks, IWANN 1997

Y2 - 4 June 1997 through 6 June 1997

ER -

Tight bounds on the size of neural networks for classification problems

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this