{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T00:05:13Z","timestamp":1649030713048},"reference-count":39,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Artif. Intell. Tools"],"published-print":{"date-parts":[[2006,4]]},"abstract":"<jats:p> We investigate the circuit complexity of classification problems in a machine learning setting, i.e. we attempt to find some rule that allows us to calculate a priori the number of threshold gates that is sufficient to achieve a small error rate after training a circuit on sample data [Formula: see text]. The particular threshold gates are computed by a combination of the classical perceptron algorithm with a specific type of stochastic local search. The circuit complexity is analysed for depth-two and depth-four threshold circuits, where we introduce a novel approach to compute depth-four circuits. For the problems from the UCI Machine Learning Repository we selected and investigated, we obtain approximately the same size of depth-two and depth-four circuits for the best classification rates on test samples, where the rates differ only marginally for the two types of circuits. Based on classical results from threshold circuit theory and our experimental observations on problems that are not linearly separable, we suggest an upper bound of [Formula: see text] threshold gates as sufficient for a small error rate, where [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0218213006002606","type":"journal-article","created":{"date-parts":[[2006,3,21]],"date-time":"2006-03-21T10:41:10Z","timestamp":1142937670000},"page":"143-161","source":"Crossref","is-referenced-by-count":3,"title":["A COMPUTATIONAL STUDY ON CIRCUIT SIZE VERSUS CIRCUIT DEPTH"],"prefix":"10.1142","volume":"15","author":[{"given":"G.","family":"LAPPAS","sequence":"first","affiliation":[{"name":"T.E.I. of Western Macedonia, P.O.B. 30, 52100 Kastoria, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R. J.","family":"FRANK","sequence":"additional","affiliation":[{"name":"University of Hertfordshire, School of Computer Science, Hatfield, Herts AL10 9AB, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. A.","family":"ALBRECHT","sequence":"additional","affiliation":[{"name":"University of Hertfordshire, School of Computer Science, Hatfield, Herts AL10 9AB, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","volume-title":"Local Search in Combinatorial Optimization","author":"Aarts E. H. L.","year":"1998"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1954-037-2"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011369322571"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2004.11.016"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1990.2.2.248"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1109\/72.125861"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/PL00013833"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0893-6080(05)80010-3"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00126-6"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1995.7.2.370"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1588"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/BF00940812"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1109\/72.286926"},{"key":"rf18","volume-title":"An Introduction to Support Vector Machines","author":"Cristianini N.","year":"2000"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1109\/72.80230"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012487302797"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1287\/moor.13.2.311"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1109\/21.47810"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"rf27","first-page":"31","volume":"14","author":"Lupanov O. B.","journal-title":"Problemy Kibernetiki"},{"key":"rf28","first-page":"109","volume":"26","author":"Lupanov O. B.","journal-title":"Problemy Kibernetiki"},{"key":"rf32","series-title":"Operations Research\/Computer Science Interfaces series","volume-title":"Mathematics of Neural Networks: Models, Algorithms & Applications","author":"Magoulas G. D.","year":"1997"},{"key":"rf33","volume-title":"Perceptrons","author":"Minsky M. L.","year":"1969"},{"key":"rf34","volume-title":"Machine Learning","author":"Mitchell T. M.","year":"1997"},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016545907026"},{"key":"rf37","doi-asserted-by":"publisher","DOI":"10.1109\/91.963759"},{"key":"rf38","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/14.8.676"},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90041-7"},{"key":"rf40","volume-title":"Principles of Neurodynamics","author":"Rosenblatt F.","year":"1962"},{"key":"rf41","doi-asserted-by":"publisher","DOI":"10.1109\/72.839020"},{"key":"rf42","doi-asserted-by":"publisher","DOI":"10.1016\/S0933-3657(99)00041-X"},{"key":"rf43","first-page":"111","volume":"6","author":"Shavlik J.","journal-title":"Machine Learning"},{"key":"rf44","series-title":"Prentice Hall Information and System Sciences Series","volume-title":"Discrete Neural Computation: A Theoretical Foundation","author":"Siu K.-Y.","year":"1995"},{"key":"rf45","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1939.0012"},{"key":"rf46","first-page":"1745","volume":"26","author":"Tom D. J.","journal-title":"Electronics Letters"},{"key":"rf47","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90105-8"},{"key":"rf48","volume-title":"Statistical Learning Theory","author":"Vapnik V. N.","year":"1998"},{"key":"rf50","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.87.23.9193"},{"key":"rf51","doi-asserted-by":"publisher","DOI":"10.1109\/4235.585893"}],"container-title":["International Journal on Artificial Intelligence Tools"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218213006002606","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T16:53:55Z","timestamp":1565196835000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218213006002606"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,4]]},"references-count":39,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2006,4]]}},"alternative-id":["10.1142\/S0218213006002606"],"URL":"https:\/\/doi.org\/10.1142\/s0218213006002606","relation":{},"ISSN":["0218-2130","1793-6349"],"issn-type":[{"value":"0218-2130","type":"print"},{"value":"1793-6349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,4]]}}}