TY - GEN

T1 - Enhanced lower entropy bounds with application to constructive learning

AU - Beiu, Valeriu

PY - 1997

Y1 - 1997

N2 - We prove two new lower bounds for the number of bits required by neural networks for classification problems defined by m examples from IR/sup n/. They are obtained in a constructive way, and can be used for designing constructive learning algorithms. The results rely on upper bounding the space, with an n dimensional ball (V. Beiu, 1996). Recently, a better upper bound was presented by V. Beiu and T. DePauw, 1997) by showing that the volume of the ball can always be replaced by the volume of the intersection of two balls. A lower bound for the case of integer weights in the range [-p, p] was detailed by S. Draghici and I.K. Sethi (1997); it is based on computing the logarithm of the quotient between the volume of the ball containing all the examples and the maximum volume of a polyhedron. One first improvement will come from a tighter upper bound on the maximum volume of the polyhedron by two n dimensional cones (instead of the ball). A second-even better-bound will be obtained by upper bounding the space by the intersection of two balls.

AB - We prove two new lower bounds for the number of bits required by neural networks for classification problems defined by m examples from IR/sup n/. They are obtained in a constructive way, and can be used for designing constructive learning algorithms. The results rely on upper bounding the space, with an n dimensional ball (V. Beiu, 1996). Recently, a better upper bound was presented by V. Beiu and T. DePauw, 1997) by showing that the volume of the ball can always be replaced by the volume of the intersection of two balls. A lower bound for the case of integer weights in the range [-p, p] was detailed by S. Draghici and I.K. Sethi (1997); it is based on computing the logarithm of the quotient between the volume of the ball containing all the examples and the maximum volume of a polyhedron. One first improvement will come from a tighter upper bound on the maximum volume of the polyhedron by two n dimensional cones (instead of the ball). A second-even better-bound will be obtained by upper bounding the space by the intersection of two balls.

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

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

U2 - 10.1109/EURMIC.1997.617371

DO - 10.1109/EURMIC.1997.617371

M3 - Conference contribution

AN - SCOPUS:0030703421

SN - 0818681292

SN - 9780818681295

T3 - Conference Proceedings of the EUROMICRO

SP - 541

EP - 548

BT - Proceedings - 23rd Euromicro Conference

T2 - 23rd EUROMICRO Conference on New Frontiers of Information Technology, EUROMICRO 1997

Y2 - 1 September 1997 through 4 September 1997

ER -