{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:29:43Z","timestamp":1777645783411,"version":"3.51.4"},"reference-count":0,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2010,10]]},"abstract":"<jats:p>\n                    The paper aims at tight upper bounds on the size of pattern classification circuits that can be used for a priori parameter settings in a machine learning context. The upper bounds relate the circuit size S(C) to n\n                    <jats:sub>L<\/jats:sub>\n                    := [log\n                    <jats:sub>2<\/jats:sub>\n                    m\n                    <jats:sub>L<\/jats:sub>\n                    ], where m\n                    <jats:sub>L<\/jats:sub>\n                    is the number of training samples. In particular, we show that there exist unbounded fan-in threshold circuits with less than (a) S\n                    <jats:sup>\n                      R\n                      <jats:sub>cc<\/jats:sub>\n                    <\/jats:sup>\n                    := 2\u00b7\u221a2\n                    <jats:sup>\n                      n\n                      <jats:sub>L<\/jats:sub>\n                    <\/jats:sup>\n                    + 3 gates for unbounded depth, (b) S\n                    <jats:sup>\n                      L\n                      <jats:sub>cc<\/jats:sub>\n                    <\/jats:sup>\n                    := 34.8 \u00b7 \u221a2\n                    <jats:sup>\n                      n\n                      <jats:sub>L<\/jats:sub>\n                    <\/jats:sup>\n                    + 14 \u00b7 n\n                    <jats:sub>L<\/jats:sub>\n                    \u2212 11 \u00b7 log\n                    <jats:sub>2<\/jats:sub>\n                    n\n                    <jats:sub>L<\/jats:sub>\n                    + 2 gates for small bounded depth, where in both cases all m\n                    <jats:sub>L<\/jats:sub>\n                    samples are classified correctly. We note that the upper bounds do not depend on the length n of input (sample) vectors. Since n\n                    <jats:sub>L<\/jats:sub>\n                    &lt;&lt; n in real-world problem settings, the upper bounds return values that are suitable for practical applications. We provide experimental evidence that the circuit size estimations work well on a number of pattern classification tasks. As a result, we formulate the conjecture that [1.25 \u00b7 S\n                    <jats:sup>\n                      R\n                      <jats:sub>cc<\/jats:sub>\n                    <\/jats:sup>\n                    or [0.07 \u00b7 S\n                    <jats:sup>\n                      L\n                      <jats:sub>cc<\/jats:sub>\n                    <\/jats:sup>\n                    ] gates are sufficient to achieve a high generalization rate of bounded-depth classification circuits.\n                  <\/jats:p>","DOI":"10.3233\/fi-2010-344","type":"journal-article","created":{"date-parts":[[2019,12,2]],"date-time":"2019-12-02T23:20:22Z","timestamp":1575328822000},"page":"201-217","source":"Crossref","is-referenced-by-count":0,"title":["A Note on a priori Estimations of Classification Circuit Complexity"],"prefix":"10.1177","volume":"104","author":[{"given":"Andreas A.","family":"Albrecht","sequence":"first","affiliation":[{"name":"CCRCB, Queen's University Belfast, Belfast, Northern Ireland, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander V.","family":"Chashkin","sequence":"additional","affiliation":[{"name":"Faculty of Mechanics and Mathematics, Moscow State University, Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Costas S.","family":"Iliopoulos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, King's College London, London, England, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oktay M.","family":"Kasim-Zade","sequence":"additional","affiliation":[{"name":"Faculty of Mechanics and Mathematics, Moscow State University, Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georgios","family":"Lappas","sequence":"additional","affiliation":[{"name":"T.E.I. of Western Macedonia, Kastoria, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kathleen K.","family":"Steinh\u00f6fel","sequence":"additional","affiliation":[{"name":"Department of Computer Science, King's College London, London, England, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2010,1,1]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2010-344","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2010-344","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:33:19Z","timestamp":1777444399000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2010-344"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1,1]]},"references-count":0,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["10.3233\/FI-2010-344"],"URL":"https:\/\/doi.org\/10.3233\/fi-2010-344","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1,1]]}}}