Geodesic
Computational complexity of combinatorial optimization problems induced by collective procedures in machine learning
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 3, pp. 276-284
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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.
Keywords: empirical risk minimization, committee decision rule, computational complexity. 
@article{TIMM_2010_16_3_a28,
     author = {M. Yu. Khachai},
     title = {Computational complexity of combinatorial optimization problems induced by collective procedures in machine learning},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {276--284},
     year = {2010},
     volume = {16},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a28/}
}
TY  - JOUR
AU  - M. Yu. Khachai
TI  - Computational complexity of combinatorial optimization problems induced by collective procedures in machine learning
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2010
SP  - 276
EP  - 284
VL  - 16
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a28/
LA  - ru
ID  - TIMM_2010_16_3_a28
ER  - 
%0 Journal Article
%A M. Yu. Khachai
%T Computational complexity of combinatorial optimization problems induced by collective procedures in machine learning
%J Trudy Instituta matematiki i mehaniki
%D 2010
%P 276-284
%V 16
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a28/
%G ru
%F TIMM_2010_16_3_a28
M. Yu. Khachai. Computational complexity of combinatorial optimization problems induced by collective procedures in machine learning. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 3, pp. 276-284. http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a28/

[1] Borovkov A. A., Matematicheskaya statistika, Nauka, Novosibirsk, 1997, 772 pp. | MR | Zbl

[2] Vapnik V. N., Statistical learning theory, Wiley, New York, 1998, 740 pp. | MR | Zbl

[3] Blum A., Rivest R. L., “Training a 3-node neural network is $NP$-complete”, Advances in neural information processing systems, ed. D. S. Touretzky, M. Kaufmann, San Mateo, 1988, 830 pp.

[4] Lin J. H., Vitter J. S., “Complexity results on learning by neural nets”, Machine Learning, 6 (1991), 211–230

[5] Khachay M., “On the computational complexity of the minimum committee problem”, J. Math. Model. Algor., 6:4 (2007), 547–561 | DOI | MR | Zbl

[6] Khachai M., Poberii M., “Complexity and approximability of committee polyhedral separability of sets in general position”, Informatica, 20:2 (2009), 217–234 | MR

[7] Dinur I., “The PCP theorem by gap amplification”, J. of the ACM, 54:3 (2007), Art. 12, 44 pp. | DOI | MR

[8] Mazurov Vl. D., “Komitety sistem neravenstv i zadacha raspoznavaniya obrazov”, Kibernetika, 1971, no. 3, 140–146 | MR | Zbl

[9] Khachai M., Mazurov V., Rybin A., “Committee construction for solving problems of selection, diagnostics, and prediction”, Proc. Steklov Inst. Math., 2002, S67–S101 | MR | Zbl

[10] Khachai M., “Computational and approximational complexity of combinatorial problems related to the committee polyhedral separability of finite sets”, Pattern Recognition and Image Analysis, 18:2 (2008), 237–242 | DOI | MR

[11] Megiddo N., Tamir A., “On the complexity of locating linear facilities in the plane”, Oper. Res. Let., 1:5 (1982), 194–197 | DOI | MR | Zbl

[12] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, M., 1986, 384 pp. | MR

[13] Johnson D. S., Preparata F. P., “The densest hemisphere problem”, Theor. Comput. Sci., 1978, no. 6, 93–107 | DOI | MR | Zbl

[14] Khachai M. Yu., “Ob odnoi igre s prirodoi, svyazannoi s prinyatiem reshenii bolshinstvom golosov”, Zhurn. vychisl. matematiki i mat. fiziki, 42:10 (2002), 1609–1616 | MR | Zbl