A Note on a priori Estimations of Classification Circuit Complexity

• Autorzy: Albrecht, A.A. , Chashkin, A.V. , Iliopoulos, C.S. , Kasim-Zade, O.M. , Lappas, G. , Steinhöfel, K.K.
• Języki publikacji: EN

Abstrakty

EN

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_2mL., where mL is the number of training samples. In particular, we show that there exist unbounded fan-in threshold circuits with less than (a) [formula] gates for unbounded depth, (b) SL [formula] 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 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 [formula] gates are sufficient to achieve a high generalization rate of bounded-depth classification circuits.

Słowa kluczowe

EN

threshold circuits; neural network synthesis; pattern classification; circuit complexity; sample size

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 3
• Strony: 201-217
• Opis fizyczny: Bibliogr. 26 poz., tab.

Twórcy

autor

Albrecht, A.A.

autor

Chashkin, A.V.

autor

Iliopoulos, C.S.

autor

Kasim-Zade, O.M.

autor

Lappas, G.

autor

Steinhöfel, K.K.

• Department of Computer Science, King’s College London, London WC2R 2LS, England, UK

Bibliografia

• [1] Ahmad, A., Dey, L.: A feature selection technique for classificatory analysis, Pattern Recognition Letters, 26, 2005, 43-56.
• [2] Anthony, M.: Boolean functions and artificial neural networks, CDAM Research Report LSE-CDAM-2003-01, Department of Mathematics and Centre for Discrete and Applicable Mathematics, The London School of Economics and Political Science, 2003.
• [3] Bartlett, P. L.: The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network, IEEE Transactions on Information Theory, 44, 1998, 525-536.
• [4] Chen, W., Lin, F., Li, J., Zhang, B.: A new prosodic phrasing model for Chinese TTS systems, Proc. 6th Natural Language Processing Pacific Rim Symposium, 2001.
• [5] Eklund, P. W.: A performance survey of public domain supervised machine learning algorithms, KVO Technical Report, University of Queensland, 2002.
• [6] Fisher, R. A.: The use of multiple measurements in taxonomic problems, Annals of Eugenics, 7, 1936, 179-188.
• [7] Gil-Pita, R., Jarabo-Amores, P., Vicen-Bueno, R., Rosa-Zurera, M.: Neural solutions for high range resolution radar classification, Proc. 7th InternationalWork-Conference on Artificial and Natural Neural Networks, LNCS 2687, Springer-Verlag Berlin, 2003.
• [8] Gletsos, M., Mougiakakou, S. G., Matsopoulos, G. K., Nikita, K. S., Nikita, A. S., Kelekis, D.: A computeraided diagnostic system to characterize CT focal liver lesions: design and optimization of a neural network classifier, IEEE Transactions on Information Technology in Biomedicine, 7, 2003, 153-162.
• [9] Hagan, M. T., Menhaj, M. B.: (1994) Training feedforward networks with the Marquardt algorithm, IEEE Transactions on Neural Networks, 5, 1994, 989-993.
• [10] Ingrassia, S., Morlini, I.: Neural network modeling for small datasets, Technometrics, 47, 2005, 297-311.
• [11] Karayiannis, N. B., Xiong, Y.: Training reformulated radial basis function neural networks capable of identifying uncertainty in data classification, IEEE Transactions on Neural Networks, 17, 2006, 1222-1234.
• [12] Lappas, G., Frank, R. J., Albrecht, A. A.: A computational study on circuit size vs. circuit depth, International Journal on Artificial Intelligence Tools, 15, 2006, 143-162.
• [13] Lupanov, O. B.: On a method to design control systems - The local encoding approach (in Russian), Problem Kibernetiki, 14, 1965, 31-110.
• [14] Lupanov, O. B.: On the design of circuits by threshold elements (in Russian), Problemy Kibernetiki, 26, 1973, 109-140.
• [15] Maass,W.: Bounds for the computational power and learning complexity of analog neural nets, SIAM Journal on Computing, 26, 1997, 708-732.
• [16] Maass, W., Schnitger, G., Sontag, E.: On the computational power of sigmoid versus boolean threshold circuits, Proc. 32nd Annual IEEE Symposium on Foundations of Computer Science, IEEE Press, 1991.
• [17] Paul, S., Kumar, S.: Subsethood-product fuzzy neural inference system (SuPFuNIS), IEEE Transactions on Neural Networks, 13, 2002, 578-599.
• [18] Pena-Reyes, C. A., Sipper, M.: Fuzzy CoCo: a cooperative coevolutionary approach to fuzzy modeling, IEEE Transactions on Fuzzy Systems, 9, 2001, 727-737.
• [19] Rampone, S.: Recognition of splice junctions on DNA sequences by BRAIN learning algorithm, Bioinformatics, 14, 1998, 676-684.
• [20] Redkin, N. P.: On the synthesis of threshold circuits for some specific classes of Boolean functions (in Russian), Kibernetika, 5, 1970, 6-9.
• [21] Setiono, R.: Extracting M-of-N rules from trained neural networks, IEEE Transactions on Neural Networks, 11, 2000, 512-519.
• [22] Setiono, R.: Generating concise and accurate classification rules for breast cancer diagnosis, Artificial Intelligence in Medicine, 18, 2000, 205-217.
• [23] Towell, G., Shavlik, J.: Knowledge-based artificial neural networks, Artificial Intelligence, 70, 1994, 119-165.
• [24] Tsoumakas, G., Angelis, L., Vlahavas, I.: Selective fusion of heterogeneous classifiers, Intelligent Data Analysis, 9, 2005, 511-525.
• [25] Vicen-Bueno, R., Gil-Pita, R., Rosa-Zurera, M., Utrilla-Manso, M., Lopez-Ferreras, F.: Multilayer perceptrons applied to traffic sign recognition tasks, Proc. 8th International Workshop on Artificial Neural Networks, LNCS 3512, Springer-Verlag, 2005.
• [26] Wolberg,W. H., Mangasarian, O. L.: Multisurface method of pattern separation for medical diagnosis applied to breast cytology, Proc. National Academy of Sciences USA, 87, 1990, 9193-9196.