MDM method for solving the general quadratic problem of mathematical diagnostics
DOI:
https://doi.org/10.21638/spbu01.2023.306Abstract
The term mathematical diagnostics was introduced by V. F. Demyanov in the early 2000s. The simplest problem of mathematical diagnostics is to determine the relative position of a certain point p and the convex hull C of a finite number of given points in n-dimensional Euclidean space. Of interest is the answer to the following questions: does the point p belong to the set C or not? If p does not belong to C, then what is the distance from p to C? In general problem of mathematical diagnostics two convex hulls are considered. The question is whether they have common points. If there are no common points, then it is required to find the distance between these hulls. From an algorithmic point of view, the problems of mathematical diagnostics are reduced to special problems of linear or quadratic programming, for the solution of which there are finite methods. However, when implementing this approach in the case of large data arrays, serious computational difficulties arise. Infinite but easily implemented methods come to the rescue, which allow obtaining an approximate solution with the required accuracy in a finite number of iterations. These methods include the MDM method. It was developed by Mitchell, Demyanov and Malozemov in 1971 for other purposes, but later found application in machine learning. From a modern point of view, the original version of the MDM method can be used to solve the simplest problems of mathematical diagnostics. This article gives a natural generalization of the MDM-method, oriented towards solving general problems of mathematical diagnostics. The equivalence of the general problem of mathematical diagnostics and the problem of linear separation of two finite sets with the largest width of the margin is established.Keywords:
mathematical diagnostics, simplest problem of mathematical diagnostics, general problem of mathematical diagnostics, machine learning, MDM-algorithm
Downloads
Download data is not yet available.
References
Литература
1. Митчелл Б. Ф., Демьянов В. Ф., Малоземов В. Н. Нахождение ближайшей к началу коор- динат точки многогранника. Вестник Лениград. ун-та 19, 38-45 (1971).
2. Barbero A., Lopez J., Dorronsoro J. R. An accelerated MDM algorithm for SVM training. European Symposium on Artificial Neural Networks - Advances in Computational Intelligence and Learning. Bruges (Belgium). April 23-25, 2008, 421-426. Proceedings (2008).
3. Lopez J. On the relationship among the MDM, SMO and SVM-Light algorithms for training support vector machines. Master’s thesis. Universidad Autonoma de Madrid, 54 (2008).
4. Lopez J., Barbero A., Dorronsoro J. R. On the equivalence of the SMO and MDM algorithms for SVM training. W. Daelemans et al. (еds.). Berlin, Heidelberg, Springer-Verlag, ECML PKDD. Part I, LNAI 5211, 288-300 (2008).
5. Lopez J., Dorronsoro J. R. A Сommon framework for the convergence of the GSK, MDM and SMO algorithms. K. Diamantaras, W. Duch, L. S. Iliadis (еds.). Berlin; Heidelberg, Springer-Verlag. ICANN 2010, Part II, LNCS 6353, 82-87 (2010).
6. Lopez J., Dorronsoro J. R. Linear convergence rate for the MDM algorithm for the nearest point problem. Pattern Recognition 48, 1510-1522 (2015).
7. Ming Zeng, Yu Yang, Junsheng Cheng. A generalized Mitchell-Dem’yanov-Malozemov algorithm for one-class support vector machine. Knowledge-Based Systems 109, 17-24 (2016).
8. Deisenroth M. P., Faisal A. A., Ong C. S. Mathematics for machine learning. Cambridge, Cambridge University Press (2020) (https://mml-book.com).
9. Platt J. C. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Technical Report MSR-TR-98-14. April 21, 1998 (1998).
10. Lopez J., Dorronsoro J. R. A Simple Proof of the Convergence of the SMO Algorithm for Linearly Separable Problems. ICANN 2009, Part I, LNCS 5768, 904-912 (2009).
11. Lazaro J. L. Analysis and Convergence of SMO-like Decomposition and Geometrical Algorithms for Support Vector Machines. A thesis submitted in partial fulfillment for the degree of Doctor of Philosophy. Universidad Autonoma de Madrid (2011).
References
1. Mitchell B. F., Dem’yanov V. F., Malozemov V. N. Finding the point of a polyhedron closest to the origin. Vestnik of Leningrad University 19, 38-45 (1971). (In Russian) [Engl. trans.: SIAM J. Control 12 (1), 19-26 (1974)].
2. Barbero A., Lopez J., Dorronsoro J. R. An accelerated MDM algorithm for SVM training. European Symposium on Artificial Neural Networks - Advances in Computational Intelligence and Learning. Bruges (Belgium). April 23-25, 2008, 421-426. Proceedings (2008).
3. Lopez J. On the relationship among the MDM, SMO and SVM-Light algorithms for training support vector machines. Master’s thesis. Universidad Autonoma de Madrid, 54 (2008).
4. Lopez J., Barbero A., Dorronsoro J. R. On the equivalence of the SMO and MDM algorithms for SVM training. W. Daelemans et al. (еds.). Berlin, Heidelberg, Springer-Verlag, ECML PKDD. Part I, LNAI 5211, 288-300 (2008).
5. Lopez J., Dorronsoro J. R. A Сommon framework for the convergence of the GSK, MDM and SMO algorithms. K. Diamantaras, W. Duch, L. S. Iliadis (еds.). Berlin; Heidelberg, Springer-Verlag. ICANN 2010, Part II, LNCS 6353, 82-87 (2010).
6. Lopez J., Dorronsoro J. R. Linear convergence rate for the MDM algorithm for the nearest point problem. Pattern Recognition 48, 1510-1522 (2015).
7. Ming Zeng, Yu Yang, Junsheng Cheng. A generalized Mitchell-Dem’yanov-Malozemov algorithm for one-class support vector machine. Knowledge-Based Systems 109, 17-24 (2016).
8. Deisenroth M. P., Faisal A. A., Ong C. S. Mathematics for machine learning. Cambridge, Cambridge University Press (2020) (https://mml-book.com).
9. Platt J. C. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Technical Report MSR-TR-98-14. April 21, 1998 (1998).
10. Lopez J., Dorronsoro J. R. A Simple Proof of the Convergence of the SMO Algorithm for Linearly Separable Problems. ICANN 2009, Part I, LNCS 5768, 904-912 (2009).
11. Lazaro J. L. Analysis and Convergence of SMO-like Decomposition and Geometrical Algorithms for Support Vector Machines. A thesis submitted in partial fulfillment for the degree of Doctor of Philosophy. Universidad Autonoma de Madrid (2011).
Downloads
Published
2023-09-23
How to Cite
Malozemov, V. N., & Solovyeva, N. A. (2023). MDM method for solving the general quadratic problem of mathematical diagnostics. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 10(3), 516–529. https://doi.org/10.21638/spbu01.2023.306
Issue
Section
Mathematics
License
Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.
