TY - GEN
T1 - On the VC-dimension of depth four threshold circuits and the complexity of boolean-valued functions
AU - Sakurai, Akito
N1 - Publisher Copyright:
© 1993, Springer Verlag. All rights reserved.
PY - 1993
Y1 - 1993
N2 - We consider the problem of determining VC-dimension (Formula Found) of depth four n-input 1-output threshold circuits with h elements. Best known asymptotic lower bounds and upper bounds are proved, that is, when (Formula Found) is upper bounded by ((h2/3)+nh(log h)(1+o(1)) and lower bounded by (1/2)((h2/4)+nh)(log h)(1 − o(1)). We also consider the problem of determining complexity c3(N) of Boolean-valued functions defined on N-pointsets in Rn, measured by the number of threshold elements, with which we can construct a depth four circuit to realize the functions. We also show the best known upper and lower bounds, that is, when N → ∞, the complexity is upper bounded by (Formula Found) and lower bounded by (Formula Found)
AB - We consider the problem of determining VC-dimension (Formula Found) of depth four n-input 1-output threshold circuits with h elements. Best known asymptotic lower bounds and upper bounds are proved, that is, when (Formula Found) is upper bounded by ((h2/3)+nh(log h)(1+o(1)) and lower bounded by (1/2)((h2/4)+nh)(log h)(1 − o(1)). We also consider the problem of determining complexity c3(N) of Boolean-valued functions defined on N-pointsets in Rn, measured by the number of threshold elements, with which we can construct a depth four circuit to realize the functions. We also show the best known upper and lower bounds, that is, when N → ∞, the complexity is upper bounded by (Formula Found) and lower bounded by (Formula Found)
UR - http://www.scopus.com/inward/record.url?scp=84899003901&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84899003901&partnerID=8YFLogxK
U2 - 10.1007/3-540-57370-4_52
DO - 10.1007/3-540-57370-4_52
M3 - Conference contribution
AN - SCOPUS:84899003901
SN - 9783540573708
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 251
EP - 264
BT - Algorithmic Learning Theory - 4th International Workshop, ALT 1993, Proceedings
A2 - Jantke, Klaus P.
A2 - Kobayashi, Shigenobu
A2 - Tomita, Etsuji
A2 - Yokomori, Takashi
PB - Springer Verlag
T2 - 4th Workshop on Algorithmic Learning Theory, ALT 1993
Y2 - 8 November 1993 through 10 November 1993
ER -