A Note on a priori Estimations of Classification Circuit Complexity
Andreas A. Albrecht, Alexander Viktorovich Chashkin, Costas S. Iliopoulos, O. M. Kasim-Zade, Georgios Lappas, Kathleen K. Steinhöfel · Fundamenta Informaticae · 2010
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 L := [log 2 m L ], where m L is the number of training samples. In particular, we show that there exist unbounded fan-in threshold circuits with less than (a) S R cc := 2·√2 n L + 3 gates for unbounded depth, (b) S L cc := 34.8 · √2 n L + 14 · n L − 11 · log 2 n L + 2 gates for small bounded depth, where in both cases all m L samples are classified correctly. We note that the upper bounds do not depend on the length n of input (sample) vectors. Since n L << 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 · S R cc or [0.07 · S L cc ] gates are sufficient to achieve a high generalization rate of bounded-depth classification circuits.