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 ((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)

本文言語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
出版ステータスPublished - 1993
外部発表はい
イベント4th Workshop on Algorithmic Learning Theory, ALT 1993 - Tokyo, Japan
継続期間: 1993 11月 81993 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

Other4th Workshop on Algorithmic Learning Theory, ALT 1993
国/地域Japan
CityTokyo
Period93/11/893/11/10

ASJC Scopus subject areas

  • 理論的コンピュータサイエンス
  • コンピュータ サイエンス(全般)

フィンガープリント

「On the VC-dimension of depth four threshold circuits and the complexity of boolean-valued functions」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル