МДМ-метод для решения общей квадратичной задачи математической диагностики
DOI:
https://doi.org/10.21638/spbu01.2023.306Аннотация
Термин математическая диагностика был введен В. Ф. Демьяновым в начале 2000-х годов. Простейшая задача математической диагностики заключается в вы- яснении взаимного положения некоторой точки p и выпуклой оболочки C конечного числа заданных точек в n-мерном евклидовом пространстве. Интерес представляет ответ на следующие вопросы: принадлежит ли точка p множеству C или нет? Если p не принадлежит C, то каково расстояние от p до C? В общей задаче математической диагностики рассматриваются две выпуклые оболочки. Решается вопрос о наличии у них общих точек. Если общих точек нет, то требуется найти расстояние между данными оболочками. С алгоритмической точки зрения задачи математической диагностики сводятся к специальным задачам линейного или квадратичного программирования, для решения которых существуют конечные методы. Однако при реализации такого подхода в случае больших массивов данных возникают серьезные вычислительные трудности. На помощь приходят бесконечные, но легко реализуемые методы, которые позволяют за конечное число итераций получить приближенное решение с требуемой точностью. К таким методам относится МДМ-метод. Он был разработан Митчеллом, Демьяновым и Малоземовым в 1971 г. для других целей, но в дальнейшем нашел применение в машинном обучении. С современной точки зрения оригинальный вариант МДМ-метода можно использовать для решения только простейших задач математической диагностики. В данной статье дается естественное обобщение МДМ-метода, ориентированное на решение общих задач математической диагностики. Дополнительно показано, как с помощью обобщенного МДМ-метода можно находить решение задачи линейного отделения двух конечных множеств, при котором отделяющая полоса имеет наибольшую ширину.Ключевые слова:
математическая диагностика, простейшая задача математической диагностики, общая задача математической диагностики, машинное обучение, МДМ-алгоритм
Скачивания
Данные скачивания пока недоступны.
Библиографические ссылки
Литература
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).
Загрузки
Опубликован
23.09.2023
Как цитировать
Малозёмов, В. Н., & Соловьева, Н. А. (2023). МДМ-метод для решения общей квадратичной задачи математической диагностики. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 10(3), 516–529. https://doi.org/10.21638/spbu01.2023.306
Выпуск
Раздел
Математика
Лицензия
Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.
