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 -