About the Kozinec algorithm
Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy · 2025 · 12 (1) · 48-63
DOI: 10.21638/spbu01.2025.104 ↗Kurz gefasst
Fachartikel in der Zeitschrift Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 2025. Verfasst von Vassili N. Malozemov und 2 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Malozemov, V. N., Solovyeva, N. A., & Tamasyan, G. S. (2025). About the Kozinec algorithm. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 12(1), 48-63. https://doi.org/10.21638/spbu01.2025.104
Vancouver
Malozemov VN, Solovyeva NA, Tamasyan GS. About the Kozinec algorithm. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy. 2025;12(1):48-63. doi:10.21638/spbu01.2025.104
BibTeX
@article{Malozemov2025,
author = {Malozemov, Vassili N. and Solovyeva, Natalya A. and Tamasyan, Grigoriy Sh.},
title = {About the Kozinec algorithm},
journal = {Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy},
year = {2025},
volume = {12},
number = {1},
pages = {48--63},
doi = {10.21638/spbu01.2025.104}
}
EUVIMED