nach oben

Erschienen in:

01.12.2023 | SCIENTIFIC SCHOOLS OF THE KRASOVSKII INSTITUTE OF MATHEMATICS AND MECHANICS OF THE URAL BRANCH OF THE RUSSIAN ACADEMY OF SCIENCES, YEKATERINBURG, THE RUSSIAN FEDERATION

Ural School of Pattern Recognition: Majoritarian Approach to Ensemble Learning

verfasst von: Vl. D. Mazurov, M. I. Poberii, M. Yu. Khachai

Erschienen in: Pattern Recognition and Image Analysis | Ausgabe 4/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This article provides an overview of the significant achievements of the Ural School of Pattern Recognition. The focus is on majoritarian generalized solutions for algebraic equations and inequalities that may not always adhere to standard properties. The paper also delves into the broader applications of these findings in collective machine learning techniques. In the literature, these generalized solutions are frequently referred to as committee generalized solutions or simply committees, leading to the derived learning methods being called committee machines. Our discussion primarily centers on the foundational theorems confirming the existence of such solutions, the intricacies of combinatorial optimization during their exploration, and the subsequent emergence of collective machine learning algorithms.

Vorheriger Artikel Methods and Algorithms for Extracting and Classifying Diagnostic Information from Electroencephalograms and Videos

Nächster Artikel Optimization in Automation Systems for Design and Management: Scientific and Pedagogical School of Dmitry Ivanovich Batishchev

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Hereinafter, we use the standard notation for the binomial coefficient \(\left( {\begin{array}{*{20}{c}} q \\ k \end{array}} \right) = \frac{{q!}}{{k!\left( {q - k} \right)!}}\).

We believe that the number 0 is coprime with any natural number.

In which matching feature descriptions of objects x_i = x_j implies matching labels y_i = y_j, indicating their class affiliation.

It belongs to the class of combinatorial optimization tasks, having polynomial-time approximation algorithms with constant approximation factors.

C. Ablow and D. Kaylor, “A committee solution of the pattern recognition problem,” IEEE Trans. Inf. Theory 11, 453–455 (1965). https://doi.org/10.1109/tit.1965.1053785CrossRef

S. Arora, E. Hazan, and S. Kale, “The multiplicative weights update method: A meta-algorithm and applications,” Theory Comput. 8, 121–164 (2012). https://doi.org/10.4086/toc.2012.v008a006MathSciNetCrossRef

C. M. Bishop, Pattern Recognition and Machine Learning, 2nd ed. (Springer, New York, 2011).

S. Boyd and L. Vandenberghe, Convex Optimization (Cambridge Univ. Press, Cambridge, 2004). https://doi.org/10.1017/cbo9780511804441CrossRef

L. Breiman, “Bagging predictors,” Mach. Learn. 24, 123–140 (1996). https://doi.org/10.1007/bf00058655CrossRef

L. Breiman, “Using iterated bagging to debias regressions,” Mach. Learn. 45, 261–277 (2001). https://doi.org/10.1023/a:1017934522171CrossRef

S. N. Chernikov, Linear Inequalities (Nauka. Glavnaya Redaktsiya Fiziko-Matematicheskoi Literatury, Moscow, 1968).

C. Cortes and V. Vapnik, “Support-vector networks,” Mach. Learn. 20, 273–297 (1995). https://doi.org/10.1007/bf00994018CrossRef

E. V. Dyukova, Yu. I. Zhuravlev, and K. V. Rudakov, “On the algebra-logical synthesis of correct recognition procedures based on elementary algorithms,” Comput. Math. Math. Phys. 36, 1161–1167 (1997).

10.

I. I. Eremin, V. D. Mazurov, and N. N. Astaf ’ev, Improper Problem of Linear and Convex Programming (Nauka, Moscow, 1983).

11.

I. I. Eremin, Theory of Linear Optimization (De Gruyter, 2001).

12.

D. N. Gainanov, V. Yu. Novokshenov, and L. I. Tyagunov, “Graphs generated by inconsistent systems of linear inequalities,” Math. Notes Acad. Sci. USSR 33, 146–150 (1983). https://doi.org/10.1007/bf01160382CrossRef

13.

D. N. Gainanov, “Graphs of maximal consistent subsystems of inconsistent systems of linear equations,” Preprint VINITI No. 229-81 (Inst. of Mechanics and Mathematics, Ural Branch, USSR Academy of Sciences, 1981).

14.

D. Gale, “Neighboring vertices on a convex polyhedron,” in Linear Inequalities and Related Systems, Ed. by H. W. Kuhn and A. W. Tucker, Annals of Mathematical Studies, Vol. 38 (Princeton Univ. Press, 1956), pp. 255–264. https://doi.org/10.1515/9781400881987-016

15.

M. Hachai, “Classification of committee solutions of majority,” Pattern Recognit. Image Anal. 7, 260–265 (1997).

16.

M. Yu. Khachai and M. I. Poberii, “Computational complexity of combinatorial problems related to piece-wise linear committee pattern-recognition learning procedures,” Pattern Recognit. Image Anal. 22, 278–290 (2012). https://doi.org/10.1134/S1054661812020046CrossRef

17.

M. Yu. Khachai and M. I. Poberii, “Scheme of boosting in the problems of combinatorial optimization induced by the collective training algorithms,” Autom. Remote Control 75, 657–667 (2014). https://doi.org/10.1134/S0005117914040067MathSciNetCrossRef

18.

M. Yu. Khachai and A. I. Rybin, “A new estimate of the number of members in a minimum committee of a system of linear inequalities,” Pattern Recognit. Image Anal. 8, 491–496 (1998).

19.

M. Yu. Khachai, “On the existence of majority committee,” Discrete Math. Appl. 7, 383–397 (1997). https://doi.org/10.1515/dma.1997.7.4.383MathSciNetCrossRef

20.

M. Yu. Khachai, “Estimate of the number of members in the minimal committee of a system of linear inequalities,” Comput. Math. Math. Phys. 37, 1356–1361 (1997).MathSciNet

21.

M. Yu. Khachai, “A relation connected with a decision making procedure based on majority vote,” Dokl. Math. 64, 456–459 (2001).

22.

M. Yu. Khachai, “A game against nature related to majority vote decision making,” Comput. Math. Math. Phys. 42, 1547–1555 (2002).MathSciNet

23.

M. Yu. Khachai, “On approximate algorithm for minimal committee of a system of linear inequalities,” Pattern Recognit. Image Anal. 13, 259–464 (2003).

24.

M. Yu. Khachai, “Computational complexity of the minimum committee problem and related problems,” Dokl. Math. 73, 138–141 (2006). https://doi.org/10.1134/S1064562406010376CrossRef

25.

M. Yu. Khachai, “Computational complexity of the minimal committee problem and adjacent problems,” Pattern Recognit. Image Anal. 16, 700–710 (2006). https://doi.org/10.1134/S1054661806040195CrossRef

26.

M. Yu. Khachai, “Computational and approximational complexity of combinatorial problems related to the committee polyhedral separability of finite sets,” Pattern Recognit. Image Anal. 18, 236–242 (2008). https://doi.org/10.1134/S1054661808020089CrossRef

27.

M. Yu. Khachai, “Computational complexity of recognition learning procedures in the class of piece-wise linear committee decision rules,” Autom. Remote Control 72, 528–539 (2010). https://doi.org/10.1134/S0005117910030136CrossRef

28.

M. Yu. Khachai, “Computational complexity of combinatorial optimization problems induced by collective procedures in machine learning,” Proc. Steklov Inst. Math. 272, S46–S54 https://doi.org/10.1134/S0081543811020040

29.

M. Khachay, M. Pobery, and D. Khachay, “Integer partition problem: Theoretical approach to improving accuracy of classifier ensembles,” Int. J. Artif. Intell. 13, 135–146 (2015).

30.

M. Khachay and M. Poberii, “Complexity and approximability of committee polyhedral separability of sets in general position,” Informatica 20, 217–234 (2009). https://doi.org/10.15388/informatica.2009.247MathSciNetCrossRef

31.

M. Yu. Khachay, “On the computational complexity of the minimum committee problem,” J. Math. Modell. Algorithms 6, 547–561 (2007). https://doi.org/10.1007/s10852-006-9056-zMathSciNetCrossRef

32.

M. Khachay, “Committee polyhedral separability: Complexity and polynomial approximation,” Mach. Learn. 101, 231–251 (2015). https://doi.org/10.1007/s10994-015-5505-0MathSciNetCrossRef

33.

K. S. Kobylkin, “Constraint elimination method for the committee problem,” Autom. Remote Control 73, 355–368 (2012). https://doi.org/10.1134/s0005117912020130MathSciNetCrossRef

34.

A. O. Matveev, “Enumerating faces of complexes and valuations on distributive lattices,” Discrete Math. Appl. 10, 403–421 (2000). https://doi.org/10.1515/dma.2000.10.4.403MathSciNetCrossRef

35.

A. O. Matveev, “Relative blocking in posets,” J. Comb. Optim. 13, 379–403 (2007). https://doi.org/10.1007/s10878-006-9028-2MathSciNetCrossRef

36.

Vl. D. Mazurov, M. Yu. Khachai, and M. I. Poberii, “Combinatorial optimization problems related to the committee polyhedral separability of finite sets,” Proc. Steklov Inst. Math. 263, S93–S107 (2008). https://doi.org/10.1134/S0081543808060102

37.

Vl. D. Mazurov, M. Yu. Khachai, and M. I. Poberii, “Committee constructions for solving problems of selection, diagnostics, and prediction,” Proc. Steklov Inst. Math. 8, S67–S101 (2002).

38.

Vl. D. Mazurov and M. Yu. Khachai, “Committees of systems of linear inequalities,” Autom. Remote Control 65, 193–203 (2004). https://doi.org/10.1023/b:aurc.0000014716.77510.61

39.

Vl. D. Mazurov and M. Yu. Khachai, “Parallel computations and committee constructions,” Autom. Remote Control 68, 912–921 (2007). https://doi.org/10.1134/s0005117907050165

40.

Vl. D. Mazurov, “Committees of systems of inequalities and pattern recognition problem,” Kibernetika, No. 3, 140–146 (1971).

41.

Vl. D. Mazurov, Committee Method in Optimization and Classification Problems (Nauka, Moscow, 1990).

42.

N. Nillson, Learning Machines: Foundations of Trainable Pattern Classfying Systems (McGraw-Hill, New York, 1965).

43.

M. Osborne, “Seniority logic: A logic for a committee machine,” IEEE Trans. Comput. C-26, 1302–1306 (1977). https://doi.org/10.1109/tc.1977.1674798CrossRef

44.

L. D. Popov and V. D. Skarin, “Duality and correction of inconsistent constraints for improper linear programming problems,” Proc. Steklov Inst. Math. 299, 165–176 (2017). https://doi.org/10.1134/s008154381709019xMathSciNetCrossRef

45.

K. V. Kudakov and S. V. Trofimov, “An algorithm for synthesizing correct recognition procedures for problems with non-intersecting classes,” USSR Comput. Math. Math. Phys. 28, 102–104 (1988). https://doi.org/10.1016/0041-5553(88)90016-xCrossRef

46.

A. I. Rybin, “On some sufficient conditions of existence of a majority committee,” Pattern Recognit. Image Anal. 10, 297–302 (2000).

47.

R. E. Schapire and Yo. Freund, Boosting: Foundations and Algorithms (The MIT Press, 2012). https://doi.org/10.7551/mitpress/8291.001.0001CrossRef

48.

R. E. Schapire, “The strength of weak learnability,” Mach. Learn. 5, 197–227 (1996). https://doi.org/10.1007/bf00116037CrossRef

49.

B. Schölkopf and A. J. Smola, Learning with Kernels: Support Vector Machines (The MIT Press, 2001). https://doi.org/10.7551/mitpress/4175.001.0001CrossRef

50.

V. D. Skarin, “On the construction of regularizing algorithms for the correction of improper convex programming problems,” Proc. Steklov Inst. Math. 303, 203–212 (2018). https://doi.org/10.1134/s0081543818090213MathSciNetCrossRef

51.

L. I. Tyagunov, “On the extraction of a sequence of maximal consistent subsystems of improper system of linear inequalities,” in Mathematical Methods of Planning and Management in Large Systems (Ural. Nauchnyi Tsentr Akad. Nauk SSSR, Sverdlovsk, 1973), pp. 152–162.

52.

V. N. Vapnik and A. Ya. Chervonenkis, Theory of Pattern Recognition (Nauka, Moscow, 1974).

53.

V. N. Vapnik, Statistical Learning Theory (Wiley-Interscience, 1998).

54.

K. V. Vorontsov, “Optimization methods for linear and monotone correction in an algebraic approach to the recognition problem,” Comput. Math. Math. Phys. 40, 159–168 (2000).MathSciNet

55.

Yu. I. Zhuravlev, “Correct algebras over sets of incorrect (heuristic) algorithms, I,” Cybernetics 13, 489–497 (1977). https://doi.org/10.1007/BF01069539CrossRef

56.

Yu. I. Zhuravlev, “Correct algebras over sets of incorrect (heuristic) algorithms, II,” Cybernetics 13, 814–821 (1977). https://doi.org/10.1007/BF01068848CrossRef

57.

Yu. I. Zhuravlev, “Correct algebras over sets of incorrect (heuristic) algorithms, III,” Cybernetics 14, 188–197 (1978). https://doi.org/10.1007/BF01069349CrossRef

Titel: Ural School of Pattern Recognition: Majoritarian Approach to Ensemble Learning
verfasst von: Vl. D. Mazurov
M. I. Poberii
M. Yu. Khachai
Publikationsdatum: 01.12.2023
Verlag: Pleiades Publishing
Erschienen in: Pattern Recognition and Image Analysis / Ausgabe 4/2023
Print ISSN: 1054-6618
Elektronische ISSN: 1555-6212
DOI: https://doi.org/10.1134/S1054661823040314

SCIENTIFIC SCHOOLS OF THE FEDERAL RESEARCH CENTER “COMPUTER SCIENCE AND CONTROL” OF THE RUSSIAN ACADEMY OF SCIENCES, MOSCOW, THE RUSSIAN FEDERATION

Advances of the Scientific School of V.L. Arlazarov in Dataset Creation and Training Sample Synthesis for Solving Modern Computer Vision Problems

SCIENTIFIC SCHOOL OF THE KOTELNIKOV INSTITUTE OF RADIO ENGINEERING AND ELECTRONICS OF THE RUSSIAN ACADEMY OF SCIENCES, MOSCOW, THE RUSSIAN FEDERATION

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2023

Advances of the Scientific School of V.L. Arlazarov in Dataset Creation and Training Sample Synthesis for Solving Modern Computer Vision Problems

Magnetometric SQUID Systems and Magnetic Measurement Methods for Biomedical Research

From Tsetlin’s School of Learning Automata towards Artificial Intelligence

Methods for Processing and Understanding Image Sequences in Autonomous Navigation Problems

Logic Separation: Discrete Modelling of Pattern Recognition

High-Performance Digital Image Processing

Premium Partner