The paper presents three methods for data classification and finding the optimal plan: the study of the quadratic programming problem, the double problem and the Support Vector Machine method. It is known that linear programming is used to solve resource allocation problems. Also, its purpose is widely used to determine the highest profit or lowest cost, inventory management, the formation of an optimal transportation plan or to determine research, and so on. An important approach to the application of linear programming problems is the use of the duality principle, which is methodologically related to the theory of systems of dependent inequalities. This aspect better explains the concept of duality in linear programming problems with general mathematical rigor. Quadratic Programming, Problem of the Quadratic Programming, Support Vector Machine COLINS-2021: 5th International Conference on Computational Linguistics and Intelligent Systems, April 22-23, 2021, Kharkiv, Ukraine
Known methods of transition from a primal problem to a dual one are based on qualitative
transformations and are meaningful. Formalization and proof of the correctness of the algorithm for
constructing a dual problem for an arbitrary form of representation of a primal problem will make it
easy to obtain correct pairs of known dual problems. The relevance of research is due to the
requirements for simplification of solutions of linear programming
problems based on the
development of a formal algorithm for the transformation of a primal problem to a dual linear
optimization problem [
Quadratic programming is a area of mathematical programming devoted to the theory of solving
problems characterized by a quadratic dependency between variables [
The paper considers the Support Vector Machine (SVM) method that is taught by examples and
used to classify objects. It is established that SVM can be successfully used to control complex
electromechanical systems, it can ensure the adaptability of control algorithms, perform the functions
of an observer, an identifier of unknown parameters, a reference model, with its help you can control
complex nonlinear objects, as well as objects with stochastic parameters [
The aim of the work is to solve a dual problem by SVM, the comparison with the primal problem and classification of the dataset.
Achieving this goal involves solving specific tasks: determine the problem of the method of SVM for the dual problem; compare dual SVM and primary;
2021 Copyright for this paper by its authors. analyze this method; apply it in practice.
The object of research is to solve a dual problem by the method of SVM.
The purpose of the study is to apply the problems of linear and nonlinear programming to study the properties of the studied problems, to determine their advantages and disadvantages.
Mathematical programming is an applied mathematical discipline that investigates the extremum
of a function (maximum or minimum search problems) and develops methods for solving them. Such
problems are also called optimization [
The area of mathematical programming can be applied to the type of objective function and to the system of constraints. As a result, we obtain a division into: Linear programming - objective function and constraint functions included in the constraint system are linear (first order equation). Nonlinear programming - the objective function or one of the constraint functions included in the constraint system is nonlinear (higher order equations). Integer (discrete) programming - if at least one variable has an integer constaint.
Dynamic programming - if the parameters of the objective function and / or system of constraints
change over time or the objective function has an additive / multiplicative form or the
decisionmaking process itself is multi-step [
Depending on that all the information about the process is known in advance, the field of mathematical programming is divided into: Stochastic programming - not all information about the process is known in advance: the parameters included in the objective function or in the constraint function are random or have to make decisions in conditions of risk. Deterministic programming - all information about the process is known in advance. Depending on the number of objective functions, the tasks are divided into: Single-criteria; Multicriteria.
The optimization problem can be classified as follows: those problems that describe the properties of the constraint system and, accordingly, others that are determined by the objective function: Unconditional optimization problems or problems without restrictions - they do not impose restrictions on quantitative variables. Conditional optimization problems or constrained problems - in these problems, quantitative variables are constrained. Optimization problems for incomplete data - they have a goal function or a system of constraints depend on some parameter p (numerical, vector), the value of which is completely undefined at the time of solving the problem.
The first type includes optimization problems, the task of which is to minimize or maximize the quadratic function of several variables with linear constraints on these variables.
Quadratic programming problems include a special class of NP problems in which the objective
function f (x) is quadratic and concave (or convex), and all constraints are linear [
Each linear programming problem can be matched to another that relates in some way to the original task. Such problems are called dual, or conjugate. Joint consideration of dual pairs of problems is very important in the economic analysis of the optimal plan. The correspondence between the original and dual problems is to build a dual problem on the basis of the first problem (as the source can be considered any of the conjugate pair of problems). Dual problems are symmetric and asymmetric.
The quadratic programming includes the SVM method. He constructs a model in the form of points in space using a binary linear classifier. This model goes through a series of iterations in which new patterns are displayed in a given space and determine the side of the gap. On the basis of these data the forecast of belonging of samples to a certain category is made.
Each linear programming problem corresponds to a dual, formed by certain rules directly from the condition of the primal problem. Comparing these two formulated problems, we conclude that the dual linear programming problem is formed from a primal problem by the following rules: 1. Each constraint of a primal problem corresponds to a variable of a dual problem. The number of unknowns of a dual problem is equal to the number of constraints of the primal problem. 2. For the primary problem, a certain variable corresponds to the specified constraint of the double problem and, accordingly, their number determines the number of unknowns in the primary problem. 3. If the objective function of the primary problem goes to max, then the objective function of the double problem goes to min, and vice versa. 4. In the objective function of a double problem, the coefficients of the variables are free values of the system of constraints for the primary problem. 5. The column of free members of the double problem is the coefficients for the variables in the objective function of the primary problem. 6. The coefficients of variables in the system of constraints of the primary problem are written in the matrix and accordingly it is transposed to determine the coefficients of constraints for the double problem.
As a result of intensive research in the field of machine learning, aimed at improving the quality of
classifiers, a new generation of methods appeared, in particular – SVM. This method refers to
machine learning methods based on vector spatial models, the purpose of which is to find dividing
surfaces between classes as far as possible from all points of the study population (perhaps ignoring
some points such as emissions or noise) [
If the training set contains two classes of data that allow linear division, then there are a large number of linear classifiers with which you can divide this data. It is intuitively clear that a dividing surface passing through the middle of a strip separating two classes. For example, the perceptron allows you to find at least one linear, other methods, such as the naive Bayesian method, find the best linear separator using a certain criterion. In particular, SVM necessarily assumes that the decisive function is completely determined by a subset of data that affect the position of the delimiter. In vector space, a point can be considered as a vector passing through the origin. Consider a dataset of n points in the form (x1 , y1 ),..., (xn , yn ) , where y 1,1 identifies to which class the point x 1 belongs.
Each point is a p-dimensional real vector. SVM means to find the maximum hyperplane that separates groups of points belonging to y 1 from y 1.
In Equation 1 we write a hyperplane through many points that satisfy the condition: w * x b 0 , (1) where w is a optional vector to the hyperplane. Parameter hyperplane from the origin on the normal vector (Figure 1). b w determines the displacement of the
In Equation 2 we define the data that are not linearly separated: max(0,1 y (wx b)) .
i i (2) In Equation 3, we minimize the function: 1 n n i 1 max(0,1 yi (wxi b)) w 2 , (3) where determines the trade-off between the size of the margin and the guarantee that the point lies is very small, the second operand becomes on the correct side of the margin. Hence, if insignificant, and the function will behave as with a hard margin.
The calculation of the soft margin classifier is to minimize the expression of the form (Equation 4): 1 n in 1 max(0,1 yi (wxi b)) w 2 .
Therefore, in a further study, we will consider a classifier with a bounded boundary. 3.1.
2 1 2
Equation 4 presents the minimization of a bounded optimization problem with a differentiated objective function. For each i we enter a variable e - the least positive number that satisfies i y (w * x b) ei and e 0 .
i i i
Equation 5 presents the problem of optimization taking into account additions.
minimize 1 n e w 2 .
i n maxmizef(c 1 ,..., cn ) i1 ci in 1 n y c (x * x ) y c ,
j 1 i i i j j j n i 1 Solving the primary problem for the dual Lagrange, we obtain a simplified problem (Equation 6): 1 n 1 if: yi ci 0 and 0 ci .
j1 2n
The quadratic function solves double maximization problems. its results satisfy linear constraints. Equations 7-8 determine the variables ci to determine the second problem.
n maxmizef(c 1 ,..., cn ) i1 ci in 1 n y c (x * x ) y c .
j 1 i i i j j j n y c x .
w i1 i i i
Moreover, ci 0 just when the point lies on the right side of the field and 0 ci lying on the edge of the field. Equation 9 shows a linear combination of reference vectors, which determines the offset through a point on the field boundary.
y i (wxi b) 1 b wxi yi . (9) 3.2.
Equation (Formula 8) gives the optimal value of w in terms of с . Suppose we have adjusted the parameters of our model to the training set, and now we want to make a prediction for the new point x . Then we will calculate wT x b and forecast y 1, if and only if this value is greater than zero. But, using (Formula 3), this value can also be written as (Equation 10): wT x b in1 ( yi ci (xi ))T x b in1 yi ci (xi , x) b . (10) (4) (5) (6) (7) (8) 1 2n , when
So, if we find ci to make a prediction, we have to calculate a value that depends only on the internal product between x . Moreover, we have previously seen that ci will be equal to all but zero support vectors. Thus, many terms in the above sum will be zero, and we really only need to find the internal products between x and the reference vectors (which are often only a small number) to calculate (Formula 9) and make our prediction.
Considering the dual form of the optimization problem, we got a good idea of the structure of the problem, and we can write the whole algorithm in terms of only the internal products between the vectors of the input functions. This property is important to apply kernels to our classification problem. The obtained algorithm, supporting vector machines, will be able to effectively learn in spaces with high dimensions.
Also dual SVM requires fewer kernel estimates than the primary. Therefore, it gives a more stable result in less computational time (Table 1).
The study requires solving a double problem by the method of reference vectors, comparison with the primary problem and classification of the data set.
Achieving this goal involves solving specific tasks: determine the problem of the method of support vectors for the dual problem; compare dual SVM and primal; analyze the algorithm of the method; apply it in practice.
The Iris dataset was chosen for the implementation of the support vector method. This is a wellknown set of data used in the area of machine learning.
Dataset attribute information: 1. Sepallength. 2. Sepalwidth. 3. Petallength. 4. Petalwidth. 5. Classes: Iris Setosa; Iris Versicolour; Iris Virginica.
The best way to analyze a large data set is to visualize it. Data visualization refers to the approaches used to understand data through visual representation.
The main purpose of visualization – interpretation of a large data set into visual graphics to easily understand complex data relationships and quickly get an imagination of the dataset.
The histogram shown in Figure 2 shows the frequencies of the data set, which can be used to understand the trend of length / width of the petals for each type of plant.
From Figure 2 it is seen that the type of petal virginica is much larger than others and sepals are mostly too, setosa has the smallest size and small range of values, versicolor - medium in size.
The box plot (Figure 3) shows the distribution of data by quartiles, the average values and statistical emissions are highlighted. The vertical lines (whiskers) drawn to the rectangles reflect the variability of the values outside the upper and lower quartiles, any point on these lines is considered a statistical ejection. The other two species are larger and have larger tendrils, which characterize a large scope.
The heatmap (Figure 4) shows the levels of correlation between attributes and their linear dependencies: (-0.09; 0.0)(0.0; 0.09) - linear independence; (-0.3; -0.1)(0.1; 0.3) - low linear dependence; (-0.5; -0.3) (0.3; 0.5) – medium linear dependence; (-1.0; -0.5) (0.5; 1.0) - high linear dependence.
The values of the length of the sepals depend entirely on the values of its width, or vice versa. In the case of a petal, the length and width are independent of each other. It is also interesting that the length of the petal depends on the length and width of the sepals.
In Figure 5 you can see the linear separation between classes.
Setosa is linearly separated from Versicolor and Virginica, and Versicolor and Virginica are not linearly separated. It means that in the first case it is necessary to apply SVM with a hard margin, and in the second - with soft.
From this statistical in the Table 2 it is seen: that the size of the sepals mostly is larger than the size of the petal. Also, since the variance and standard deviation characterize the scattering of values around the distribution center, it can be concluded that the variation of petal size values between plant species is much larger than for the sepals.
Two arbitrary points from the iris dataset are selected for analysis, and the optimal hyperplane is calculated.
Let first arbitrary point – A(12,4.8) , second – B(100,6.3) , where x – index in the dataset, y – length of the sepal (Figure 6).
The point A will be considered negative, B – positive, thus yA 1 , yB 1 .
where w – normal vector to the hyperplane and - perpendicular distance from the hyperplane to w the origin.
To find w and b dual form should be introduced. It contains a quadratic objective function with constraints (equation 12). if iL1ai yi 0, ai 0
i After data substitution:
L max LD ai a i1 1
ai a j yi y j xi , x j , 2 i, j (12) 1 1 12 12 maax LD iL 1 ai 2i, j ai a j yi y j xi , x j a1 a2 2 (a1a1 *1*1* 4.8, 4.8 12 100 100 100 2 * a1a2 *1* (1) * 4.8, 6.3 a2a2 * (1) * (1) * 6.3 , 6.3 )
1 a a (167.04a 2 2460.48a a 10039.69a 2 )
1 2 2 1 1 2 2 Using the Lagrange equation we can solve this problem:
1 L( X , ) x x (167.04x2 2460.48x x 10039.69x2 * (x x 0) .
1 2 2 1 1 2 2 1 2
Under the condition of the extremum of the Lagrange function, we equate the partial derivatives to zero.
Built system: Calculating w and b : w iL1 ai yi xi
25 96837 96837 96837 96837
Figure 7 shows the hyperplane that best classifies our data, and theoretically all positive points will be on the left and negative points on the right. Dark blue color indicates the hyperplane itself, dotted lines form a margin.
Comparing the result of the program and using the SVM of the sklearn library, the following result of the program is given: w 0.02272067 0.00038728
0; 4.8;
Coefficients of the support vector in the decision function 0.00025819 0.00025819 .
The values of w and b are calculated manually and coincide with the help of the program, so the calculations are correct. Also, since we have only two points in this case, they act as reference vectors, one for each class. The coefficients of these reference vectors in the objective function correspond to Lagrange factors calculated manually.
Figure 8 shows the calculated results using the program for the entire dataset:
Figure 8 shows the sepal length of two linearly separated plant species of the iris dataset - y , which must be classified using the SVM algorithm programmatically. We see that the data are linearly separated and easy to classify. Consider the problem is to find the optimal solution.
In Figure 9 two types of plants are classified by the hyperplane calculated programmatically. Since one of the parameters of the classification is the index, and iris dataset takes into account the indexation, namely (setosa - (1; 50), virginica - (50; 100), versicolor - (100; 150)), so the support vectors and their number for each class are found correctly. Plants with an index less than 75 will belong to setosa, and more - to versicolor. But it is necessary to remember about possible cases where the sepal_length value will be considered.
The dual method of support vectors is to solve the Lagrange problem, with found Lagrange multipliers it is easy to calculate the normal vector w and draw a separate hyperplane.
Solving the primary problem, it is obtained the optimal w, but nothing about the Lagrange multipliers. To classify the point x, it is needed to clearly calculate the scalar product wT x , which can be very expensive. Solving the dual problem: obtained Lagrange factors (where ai 0 for all but a few points - support vectors). This problem is very efficiently calculated if there are few support vectors. Also, with a scalar product that includes only data vectors, it is possible to use kernel trick for nonlinear problems.
Dual SVM in nonlinear problems is more stable and faster than the primary because it performs fewer kernel estimates.
Using the Lagrange function helps to distribute the data linearly. The kernel trick is used to separate data in different ways, but not line.
SVM can be successfully used to control complex electromechanical systems, it can ensure the adaptability of control algorithms, perform the functions of an observer, an identifier of unknown parameters, a reference model, it can be used to control complex nonlinear objects.