A computational study on circuit size versus circuit depth


Lappas, G., Frank, R. and Albrecht, A. 2006. A computational study on circuit size versus circuit depth. International Journal on Artificial Intelligence Tools. 15 (2), pp. 143-162. https://doi.org/10.1142/S0218213006002606
TitleA computational study on circuit size versus circuit depth
AuthorsLappas, G., Frank, R. and Albrecht, A.

[Please see the article via the link above for the full abstract including mathematical formulae]. 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. 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.

KeywordsMachine learning; circuit complexity; simulated annealing
JournalInternational Journal on Artificial Intelligence Tools
Publication dates
Publication process dates
Deposited08 Nov 2013
Output statusPublished
Digital Object Identifier (DOI)https://doi.org/10.1142/S0218213006002606
Permalink -


  • 11
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as