On the VC-dimension of depth four threshold circuits and the complexity of boolean-valued functions

Akito Sakurai

doi:10.1007/3-540-57370-4_52

On the VC-dimension of depth four threshold circuits and the complexity of boolean-valued functions

Akito Sakurai

研究成果: Conference contribution

2 被引用数 (Scopus)

抄録

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 ((h²/3)+nh(log h)(1+o(1)) and lower bounded by (1/2)((h²/4)+nh)(log h)(1 − o(1)). We also consider the problem of determining complexity c₃(N) of Boolean-valued functions defined on N-pointsets in Rⁿ, 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)

本文言語	English
ホスト出版物のタイトル	Algorithmic Learning Theory - 4th International Workshop, ALT 1993, Proceedings
編集者	Klaus P. Jantke, Shigenobu Kobayashi, Etsuji Tomita, Takashi Yokomori
出版社	Springer Verlag
ページ	251-264
ページ数	14
ISBN（印刷版）	9783540573708
DOI	https://doi.org/10.1007/3-540-57370-4_52
出版ステータス	Published - 1993
外部発表	はい
イベント	4th Workshop on Algorithmic Learning Theory, ALT 1993 - Tokyo, Japan 継続期間: 1993 11月 8 → 1993 11月 10

出版物シリーズ

名前	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
巻	744 LNAI
ISSN（印刷版）	0302-9743
ISSN（電子版）	1611-3349

Other

Other	4th Workshop on Algorithmic Learning Theory, ALT 1993
国/地域	Japan
City	Tokyo
Period	93/11/8 → 93/11/10

ASJC Scopus subject areas

理論的コンピュータサイエンス
コンピュータサイエンス（全般）

文献へのアクセス

10.1007/3-540-57370-4_52

他のファイルとリンク

引用スタイル

Sakurai, A. (1993). On the VC-dimension of depth four threshold circuits and the complexity of boolean-valued functions. In K. P. Jantke, S. Kobayashi, E. Tomita, & T. Yokomori (Eds.), Algorithmic Learning Theory - 4th International Workshop, ALT 1993, Proceedings (pp. 251-264). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 744 LNAI). Springer Verlag. https://doi.org/10.1007/3-540-57370-4_52

On the VC-dimension of depth four threshold circuits and the complexity of boolean-valued functions. / Sakurai, Akito.
Algorithmic Learning Theory - 4th International Workshop, ALT 1993, Proceedings. ed. / Klaus P. Jantke; Shigenobu Kobayashi; Etsuji Tomita; Takashi Yokomori. Springer Verlag, 1993. p. 251-264 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 744 LNAI).

研究成果: Conference contribution

Sakurai, A 1993, On the VC-dimension of depth four threshold circuits and the complexity of boolean-valued functions. in KP Jantke, S Kobayashi, E Tomita & T Yokomori (eds), Algorithmic Learning Theory - 4th International Workshop, ALT 1993, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 744 LNAI, Springer Verlag, pp. 251-264, 4th Workshop on Algorithmic Learning Theory, ALT 1993, Tokyo, Japan, 93/11/8. https://doi.org/10.1007/3-540-57370-4_52

Sakurai A. On the VC-dimension of depth four threshold circuits and the complexity of boolean-valued functions. In Jantke KP, Kobayashi S, Tomita E, Yokomori T, editors, Algorithmic Learning Theory - 4th International Workshop, ALT 1993, Proceedings. Springer Verlag. 1993. p. 251-264. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-57370-4_52

Sakurai, Akito. / On the VC-dimension of depth four threshold circuits and the complexity of boolean-valued functions. Algorithmic Learning Theory - 4th International Workshop, ALT 1993, Proceedings. editor / Klaus P. Jantke ; Shigenobu Kobayashi ; Etsuji Tomita ; Takashi Yokomori. Springer Verlag, 1993. pp. 251-264 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{582be66eaffa42ba8a4b3c3dae7b8e66,

title = "On the VC-dimension of depth four threshold circuits and the complexity of boolean-valued functions",

abstract = "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)",

author = "Akito Sakurai",

year = "1993",

doi = "10.1007/3-540-57370-4_52",

language = "English",

isbn = "9783540573708",

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

publisher = "Springer Verlag",

pages = "251--264",

editor = "Jantke, {Klaus P.} and Shigenobu Kobayashi and Etsuji Tomita and Takashi Yokomori",

booktitle = "Algorithmic Learning Theory - 4th International Workshop, ALT 1993, Proceedings",

}

TY - GEN

T1 - On the VC-dimension of depth four threshold circuits and the complexity of boolean-valued functions

AU - Sakurai, Akito

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 -

On the VC-dimension of depth four threshold circuits and the complexity of boolean-valued functions

抄録

出版物シリーズ

Other

ASJC Scopus subject areas

文献へのアクセス

他のファイルとリンク

フィンガープリント

引用スタイル