On the finite convergence of the NN classification learning on mistakes
DOI:
https://doi.org/10.15407/dopovidi2022.01.034Keywords:
classification learning, finite convergence, nearest neighbor method, learning on mistakesAbstract
The paper establishes an analog of well-known Novikoff’s theorem on the perceptron learning algorithm’s finite convergence in linearly separated classes. We obtain a similar result concerning the nearest neighbor classification algorithm in the case of compact classes in a general metric space for the case of non-intersecting classes. The learning process consists of gradual modification of the algorithm in misclassification cases. The process is studied in the deterministic setting. Classes are understood as compacts in complete metric space, and class separation is defined as the non-intersection of compacts. The number of learning steps is bounded by the number of elements in some ε-net for the considered classes.
Downloads
References
Rosenblatt, F. (1962). Principles of Neurodynamics: Perceptron and Theory of Brain Mechanisms. Washington: Spartan Books. 616 p.
Glushkov, V. M. (1963). The theory of instruction for a class of discrete perceptrons. USSR. Comput. Math. and Math. Phys., 2, Iss. 2, pp. 338-355. https: //doi. org/10. 1016/0041-5553(63)90410-5
Novikoff, A. B. J. (1962). On convergence proofs on perceptrons. Proceedings of the Symposium on the Mathematical Theory of Automata, 12, pp. 615-622. New York: Polytechnic Institute of Brooklyn.
Kozinets, V. N. (1973). Recurrent algorithm for separating convex hulls of two sets. Pattern recognition learning algorithms. Moscow: Sovetskoe Radio, pp. 43-50 (in Russian).
Aizerman, M. A., Braverman, E. M., Rozonoer, L. I. (1970). Method of Potential Functions in the Theory of Pattern Recognition. Moscow: Nauka (in Russian).
Schlesinger, M. I. & Hlavác, V. (2002). Ten lectures on statistical and structural pattern recognition. Dordrecht: Kluwer. https: //doi. org/10. 1007/978-94-017-3217-8
Vapnik, V. N. (1998). Statistical learning theory. New York: Wiley.
Cover, T. M. & Hart, P. E. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory. 13, Iss. 1, pp. 21-27. https://doi. org/10.1109/tit.1967.1053964
Devroye, L., Gyorfi, L. & Lugosi, G. (1996). A Probabilistic Theory of Pattern Recognition. New York: Springer.
Vorontsov, K. V. (2010). Metric classification algorithms. Access. http://machinelearning.ru/wiki/images/8/8f/Voron-ML-Metric1.pdf
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Reports of the National Academy of Sciences of Ukraine
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
