其他名称：
25-21-00304
项目负责人：
Ushakov Anton
发表日期：
2025
主持机构：
Matrosov Institute for System Dynamics and Control Theory SB RAS,
国家：
俄罗斯
开始日期：
2025
结束日期：
2026
简介：
Currently, machine learning and artificial intelligence methods are attracting tremendous attention from both the scientific community and the public, often acquiring the aureole of universal tools that can solve most of the existing problems in a wide range of application areas. The success and popularity of these approaches in recent years is largely connected not only with the development of mathematical theory in this direction, but also with the rapid growth in the performance of computing systems and the accumulation of big data sets.
The modern field of machine learning is inconceivable without methods of mathematical optimization. Moreover, their significance is often so great that a number of researchers consider machine learning as a subsection of mathematical programming. Moreover, numerous machine learning problems can be represented as mathematical optimization problems, the solution of which in practice seems to be a very non-trivial problem, since most of these problems are NP-hard. In this regard, traditional approaches to many machine learning problems involve the use of simple and fast algorithms (heuristics) for solving optimization problems, such as, for example, greedy algorithms and/or local search procedures (decision trees are a classic example). The choice of such algorithms is due not only to the complexity of the corresponding optimization problem, but also to the limited computing resources when these machine learning methods (MLMs) were developed. However, MLMs have been successfully implemented in many software tools and continue to be extremely popular in practical applications.
In connection with the above, we note that in the last decade, the direction associated with the “revision” of traditional methods and algorithms used in practical optimization problems, including machine learning, from the point of view of modern technologies and algorithmic theory, is gaining popularity. Recalling the above example, we note, in particular, that the development of modern methods of integer programming and computer technology has led to the emergence of so-called optimal classification trees.
This project addresses one of the basic problem in machine learning: the clustering or cluster analysis problem. In the simplest statement, the problem consists in dividing the set of unlabeled data elements (which have no information about class labels) into non-overlapping subsets (clusters) consisting of elements similar to each other. Clustering is one of the basic problems of unsupervised machine learning, since it is assumed that the partitioning of data into clusters occurs without the use of class labels, which are generally unknown. Despite the simplicity of the formulation, the clustering problem is a good example of an ill-posed problem. Currently, there are hundreds of clustering algorithms, different in approaches and principles to defining and searching for clusters, as well as in determining which objects should be considered similar. Despite this, for the past 60 years, the most popular type of algorithms and formulations of the clustering problem involves partitioning data elements into clusters by searching for solutions in some optimization problem (partition-based clustering). The most popular type of such an optimization problem is aimed at finding a fixed number of so-called cluster centers. After that, the data elements are divided into clusters by joining to the center closest to them. By far the best-known clustering algorithm of this type, and the most popular clustering algorithm in general, is the k-means algorithm, which is essentially the so-called location-allocation heuristic for the k-means or the minimum sum-of-squares problem. The latter is a well-known NP-hard problem.
Lately, clustering algorithms are widely used not only as a tool for primary data analysis, but also as an important component of other approaches in machine learning. Despite its huge popularity, the k-means algorithm and its various modifications used in applications and implemented in a large number of machine learning software libraries are mainly simple heuristics (of the local search), often improved by various initial solution choice procedures or/and a metaheuristic. The main advantage of the k-means algorithm, which allows it to remain popular is the ease of implementation, as well as the speed of work for data of relatively small dimensions.
As noted above, an interesting modern direction is the study of classical optimization problems in machine learning using contemporary approaches in mathematical programming and the development of optimization algorithms focused on relevant computing tools. Indeed, even though the k-means problem was formulated as a non-convex mathematical programming problem back in the late 60s, until recently, not many algorithms for finding its solutions based on the theory of mathematical optimization have been proposed. Within the framework of this project, it is planned to consider a number of unsupervised and semi-supervised machine learning problems, somehow related to the k-means problem. We assume to reduce such problems to continuous non-convex optimization formulations and use the methods of the so-called d.c. (DC, difference of convex) optimization to solve them. More precisely, it is proposed to use the global search theory in problems with d.c. structures based on global optimality conditions.
Within the framework of the project, it is planned to study both the classical k-means problem and its variants with a different choice of metrics for calculating distances between elements and cluster centers (for example, Euclidean distance, Bregman divergences, Mahalanobis distances, etc.), as well as with a different set of constraints on clusters (maximum/minimum size) and/or using additional information such as class labels. Such a problem is known as a semi-supervised clustering problem and, to the best of our knowledge, there are not many studies on it at the moment.
In general, in the project, it is planned to make an attempt to develop a certain general unified approach for the machine learning problems under consideration, based on their representation as d.c. optimization problems. Although the classical problem has previously been studied as the d.c. optimization, in the project, it is planned to use a different approach to reduce the k-means problem to a d.c. problem without using Boolean variables.
Thus, the relevance of the proposed research on this project, as well as their scientific novelty and practical significance, is apparent.
专业领域：
信息技术
语种：
英语
