About the Kozinec algorithm

Abstract

In 1964 at the dawn of machine learning, B.N. Kozinec proposed a simple numerical method (algorithm) for solving the following extremal problem. "In $n$-dimensional Euclidean space, two finite sets $P_1$ and $P_2$ are given. It is assumed that the corresponding convex hulls $C_1$ and $C_2$ of these sets do not have common points. It is required to construct a hyperplane separating the sets $P_1$ and $P_2$, i. e. such a hyperplane that does not have common points with the sets $C_1$ and $C_2$ and, in addition, the sets $C_1$ and $C_2$ lie on opposite sides of this hyperplane. In fact, it is desirable, among all the hyperplanes separating the sets $P_1$ and $P_2$, to find a hyperplane whose distance to the set $P_1 \cup P_2$ has the maximum value. Obviously, such a hyperplane will be a hyperplane passing through the middle of the vector connecting any two nearest points of the sets $C_1$ and $C_2$, perpendicular to it". Later this problem was called the problem of hard SVM separation of two finite sets (SVM - abbreviation for Support Vector Machine). The Kozinec algorithm uses a natural geometric version of the optimality criterion for the problem under consideration. This article provides a detailed analysis of the Kozinec algorithm from a modern perspective. In particular, a correct proof of its convergence is given. A working scheme algorithm is proposed. Two examples are considered in which the effectiveness of the conceptual and working schemes is compared.

Keywords:

machine learning, hard SVM-separation, Kozinec algorithm, MDM-algorithm, SMO-algorithm, clipped iterations