UDC 519.85
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
 zhurbnick@gmail.com
|
|
LINEAR CLASSIFIER AND PROJECTION ONTO A POLYTOPE
Abstract. An algorithm for constructing linear binary classifiers is proposed.
Recognition objects are represented by points
of n-dimensional Euclidean space.
The algorithm is based on solving the problem of projecting zero onto the convex hull of a finite number of points of Euclidean space.
Keywords: linear classifier, convex hull, projection on polytope, penalty functions.
FULL TEXT
REFERENCES
- Schlesinger M., Glavach V. Ten lectures on statistical and structural recognition [in Russian]. Kiev: Nauk. dumka. 2004. 545 p.
- Vorontsov K.V. Mathematical teaching methods on precedents (machine learning theory). URL: http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf.
- Leuchtweiss K. Convex sets [Russian translation]. Moscow: Nauka, 1985. 336 p.
- Carver W.B. Systems of linear inequalities. Ann. Math. 1921. Vol. 23, N 2. P. 212–220.
- Charin V.S. Linear transforms and convex sets [in Russian]. Kyiv: Vishcha shkola, 1978. 192 p.
- Polyak B.T. Introduction to optimization [in Russian]. Moscow: Nauka, 1983. 384 p.
- Polyak B.T. On the rate of convergence of the penalty function method. Zhurn. vychisl. matematiki i mat. fiziki. 1971. Vol. 11, № 1. P. 3–11.
- Kozinets B.N. A recurrent algorithm for separating convex hulls of two sets. Vapnik V.N. (Ed.) Pattern recognition learning algorithms [in Russian]. Moscow: Soviet Radio, 1973. 200 p.
- Nemirovsky A.S., Yudin D.B. The complexity of the problems and the effectiveness of optimization methods [in Russian]. Moscow: Nauka, 1979. 384 p.
- Laptin Yu.P., Zhuravlev Yu.I., Vinogradov A.P. Minimization of empirical risk and the problem of constructing linear classifiers. Kibernetika i sistemnyj analiz. 2011. Vol. 47, N 4. P. 155–164.
- Wolfe P. Finding the nearest point in a polytope. Math. Program. 1976. Vol. 11, N 2. P. 128–149.
- Nurminsky E.A. On the convergence of the method of suitable affine subspaces for solving the problem of least distance to a simplex. Zhurn. vychisl. matematiki i mat. fiziki. 2005. Vol. 45, Iss. 11. P. 1996–2004.
- Zhurbenko N.G. Polytope design algorithm. Teoriya optymalʹnykh rishenʹ. 2008. N 7. P. 125–131.
