# A note on a priori estimations of classification circuit complexity

Albrecht, Andreas A., Chashkin, Alexander V., Iliopoulos, Costas S., Kasim-Zade, Oktay M., Lappas, Georgios and Steinhofel, Kathleen K. (2010) A note on a priori estimations of classification circuit complexity. Fundamenta Informaticae, 104 (3) . pp. 201-217. ISSN 0169-2968 [Article] (doi:10.3233/FI-2010-344)

## Abstract

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 nL := [log2mL], where mL is the number of training samples. In particular, we show that there exist unbounded fan-in threshold circuits with less than (a) SRcc := 2·√2nL + 3 gates for unbounded depth, (b) SLcc := 34.8 · √2nL + 14 · nL − 11 · log2nL + 2 gates for small bounded depth, where in both cases all mL samples are classified correctly. We note that the upper bounds do not depend on the length n of input (sample) vectors. Since nL << 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 · SRcc or [0.07 · SLcc] gates are sufficient to achieve a high generalization rate of bounded-depth classification circuits.

Item Type: Article A. > School of Science and Technology > Computer Science 12394 Andreas Albrecht 08 Nov 2013 08:33 22 Sep 2022 17:50 https://eprints.mdx.ac.uk/id/eprint/12394 View Item
{"ft_lang_label":"__label__en","ft_lang_prob":0.71395254,"math_prob":0.79449594,"size":1820,"snap":"2022-40-2023-06","text_gpt3_token_len":493,"char_repetition_ratio":0.11013216,"word_repetition_ratio":0.035714287,"special_character_ratio":0.2725275,"punctuation_ratio":0.16045845,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.95763,"pos_list":[0,1,2],"im_url_duplicate_count":[null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-01-29T16:27:48Z\",\"WARC-Record-ID\":\"<urn:uuid:f9d1e6cb-50d4-425d-b896-74f279a12616>\",\"Content-Length\":\"34571\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:c6d2e3ae-666e-4cc3-ad62-24e7034ce6c3>\",\"WARC-Concurrent-To\":\"<urn:uuid:9fe78cf3-31e5-4c05-8c1d-b66a8895a029>\",\"WARC-IP-Address\":\"128.86.237.117\",\"WARC-Target-URI\":\"https://eprints.mdx.ac.uk/12394/\",\"WARC-Payload-Digest\":\"sha1:YDXTSR7OFOODXCR2H5UXYCAXK2NNA6CU\",\"WARC-Block-Digest\":\"sha1:CRBXMJ6R6QFDFILPXHO3AFEIUG5DZUPR\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-06/CC-MAIN-2023-06_segments_1674764499744.74_warc_CC-MAIN-20230129144110-20230129174110-00607.warc.gz\"}"}