caa a22 4500 605477825 CHVBK 20210128100402.0 cr unu---uuuuu 210128e20151001xx s 000 0 eng 10.1007/s10994-015-5505-0 doi (NATIONALLICENCE)springer-10.1007/s10994-015-5505-0 Khachay Michael Krasovsky Institute of Mathematics and Mechanics UB RAS, Yekaterinburg, Russia aut Committee polyhedral separability: complexity and polynomial approximation [Elektronische Daten] [Michael Khachay] We consider the minimum affine separating committee (MASC) combinatorial optimization problem, which is related to ensemble machine learning techniques on the class of linear weak classifiers combined by the rule of simple majority. Actually, the MASC problem is a mathematical formalization of the famous Vapnik-Chervonenkis principle of structural risk minimization in the mentioned class of classifiers. According to this principle, it is required to construct a best performance ensemble classifier belonging to a family of the least possible VC-dimension. It is known that the MASC problem is NP-hard and remains intractable in spaces of any fixed dimension $$n>1$$ n > 1 even under an additional constraint on the separated sets to be in general position. This special case of the MASC problem called MASC-GP(n) is the main subject of interest of the present paper. To design polynomial-time approximation algorithms for a class of combinatorial optimization problems containing the MASC problem, we propose a new framework, adjusting the well-known Multiple Weights Update method. Following this approach, we construct polynomial-time approximation algorithms with state-of-the-art approximation guarantee for the MASC-GP(n) problem. The results obtained provide a theoretical framework for learning a high-performance ensembles of affine classifiers. The Author(s), 2015 Polyhedral separability nationallicence Affine committees nationallicence Computational complexity nationallicence Approximability nationallicence Machine Learning Springer US; http://www.springer-ny.com 101/1-3(2015-10-01), 231-251 0885-6125 101:1-3<231 2015 101 10994 https://doi.org/10.1007/s10994-015-5505-0 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10994-015-5505-0 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Khachay Michael Krasovsky Institute of Mathematics and Mechanics UB RAS, Yekaterinburg, Russia aut NATIONALLICENCE 773 0- Machine Learning Springer US; http://www.springer-ny.com 101/1-3(2015-10-01), 231-251 0885-6125 101:1-3<231 2015 101 10994