Computational complexity of combinatorial optimization problems induced by collective procedures in machine learning / Khachai M.Y. // Proceedings of the Steklov Institute of Mathematics. - 2011. - V. 272, l. SUPPL. 1. - P. S46-S54.

ISSN:

00815438

Type:

Article

Abstract:

The computational complexity of a new class of combinatorial optimization problems that are induced by optimal machine learning procedures in the class of collective piecewise linear classifiers of committee type is studied. © 2011 Pleiades Publishing, Ltd.

Author keywords:

committee classifier; computational complexity; empirical risk minimization

Index keywords:

нет данных

DOI:

10.1134/S0081543811020040

Смотреть в Scopus:

https://www.scopus.com/inward/record.uri?eid=2-s2.0-79954617326&doi=10.1134%2fS0081543811020040&partnerID=40&md5=294015693abcce6b1ec32e89883df9a6

Соавторы в МНС:

—

Другие поля

Поле	Значение
Link	https://www.scopus.com/inward/record.uri?eid=2-s2.0-79954617326&doi=10.1134%2fS0081543811020040&partnerID=40&md5=294015693abcce6b1ec32e89883df9a6
Affiliations	Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg 620990, Russian Federation
Author Keywords	committee classifier; computational complexity; empirical risk minimization
References	Borovkov, A.A., (1997) Mathematical Statistics, , Novosibirsk: Nauka; Vapnik, V.N., (1998) Statistical Learning Theory, , New York: Wiley; Blum, A., Rivest, R.L., (1988) Advances in Neural Information Processing Systems, pp. 494-501. , D. S. Touretzky (Ed.), San Mateo: M. Kaufmann; Lin, J.H., Vitter, J.S., (1991) Machine Learning, 6, p. 211; Khachay, M., (2007) J. Math. Model. Algorithms, 6 (4), p. 547; Khachai, M., Poberii, M., (2009) Informatica, 20 (2), p. 217; Dinur, I., (2007) J. ACM, 54 (3). , Paper 12; Mazurov, V.D., (1971) Kibernetika, 3, p. 140; Khachai, M., Mazurov, V., Rybin, A., (2002) Proc. Steklov Inst. Math., Suppl., 1, pp. S67; Khachai, M., (2008) Pattern Recogn. Image Anal., 18 (2), p. 237; Megiddo, N., Tamir, A., (1982) Oper. Res. Lett., 1 (5), p. 194; Yablonskii, S.V., (1986) Introduction to Discrete Mathematics, , Moscow: Nauka; Johnson, D.S., Preparata, F.P., (1978) Theor. Comput. Sci., 6, p. 93; Khachai, M.Y., (2002) Zh. Vychisl. Mat. Mat. Fiz., 42 (10), p. 1609
Correspondence Address	Khachai, M. Y.; Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg 620990, Russian Federation; email: mkhachay@imm.uran.ru
Language of Original Document	English
Abbreviated Source Title	Proc. Steklov Inst. Math.
Source	Scopus