Parallel computations and committee constructions / Mazurov V.D., Khachai M.Yu. // Automation and Remote Control. - 2007. - V. 68, l. 5. - P. 912-921.

ISSN:
00051179
Type:
Article
Abstract:
The paper reviewed the results bearing out the deep-seated relation between the parallel computations and learning procedures for the laminated neural networks one of whose formalizations is represented by the theory of committee constructions. Additionally, consideration was given to two combinatorial problems concerned with learning pattern recognition in the class of affine committees-the problem of verifying existence of a three-element affine separating committee and that of element-minimal affine separating committee. The first problem was shown to be N P-complete, whereas the second problem is N P-hard and does not belong to the Apx class. © Nauka/Interperiodica 2007.
Author keywords:
Index keywords:
Combinatorial mathematics; Computational complexity; Learning algorithms; Neural networks; Pattern recognition; Problem solving; Combinatorial problems; Committee constructions; Learning pattern recog
DOI:
10.1134/S0005117907050165
Смотреть в Scopus:
https://www.scopus.com/inward/record.uri?eid=2-s2.0-34249863291&doi=10.1134%2fS0005117907050165&partnerID=40&md5=1d1b7e8c5fb2463fc39e8d1eb3ad5b11
Соавторы в МНС:
Другие поля
Поле Значение
Link https://www.scopus.com/inward/record.uri?eid=2-s2.0-34249863291&doi=10.1134%2fS0005117907050165&partnerID=40&md5=1d1b7e8c5fb2463fc39e8d1eb3ad5b11
References Mazurov, V.D., On the Committee of a System of Convex Inequalities (1966) Proc. Int. Math. Congr, (14), p. 41. , Moscow: Mosk. Gos. Univ; Mazurov, V.D., (1990) Metod komitetov v zadachakh optimizatsii i klassifikatsii (Method of Committees in the Problems of Optimization and Classification), , Moscow: Nauka; Mazurov, V.D., Consistent Completion of Systems of Algorithms to Committee Technologies (1998) Pattern Recognit. Image Anal, 8 (4), pp. 501-506; Ablow, C.M., Kaylor, D.J., Inconsistent Homogeneous Linear Inequalities (1965) Bull. Am. Math. Soc, 71 (5), p. 724; Judd, J.S., (1990) Neural Network Design and Complexity of Learning, , New York: MIT Press; Lin, J.H., Vitter, J.S., Complexity Results on Learning by Neural Nets (1991) Machine Learning, 6, pp. 211-230; Blum, A.L., Rivest, R.L., Training a 3-node Neural Network is NP-complete (1992) Neural Networks, 5, pp. 117-127; Mazurov, V.D., Committees of Inequality Systems and the Problem of Recognition (1971) Kibernetika, (3), pp. 140-146; Khachai, M.Y., On Computational Complexity of the Minimal Committee and Related Problems (2006) Dokl. Ross. Akad. Nauk, 406 (6), pp. 742-745; Hastad, J., Clique is Hard to Approximate within n1-ε (1999) Acta Mathematica, 182 (13), pp. 105-142; Dinur, I., Regev, O., Smyth, C., The Hardness of 3-uniform Hypergraph Coloring (2002) Proc. 43rd Ann. IEEE Sympos. Foundat. Comput. Sci; Khachai, M.Y., On the Computational and Approximational Complexity of the Problem of Minimal Separating Committee (2006) Tavrich. Vest. Informatiki i Mat, (1), pp. 34-43
Language of Original Document English
Abbreviated Source Title Autom. Remote Control
Source Scopus