Informatics and Applications
2026, Volume 20, Issue 2, pp 25-34
REDUCTIONS ALGORITHM OF THE SMALLEST TRAINING SAMPLE FOR FACTOR-LATTICE
Abstract
The paper presents a polynomial-time algorithm (with respect to the size of the initial training sample) for constructing the smallest training set for a factor-lattice of the lattice of candidates for the smallest training sample through a sequence of reductions of this sample. The structure of the smallest training sample is described alongside a proof of its minimality. The proposed algorithm can be useful for consistently reducing the space of features describing training examples so as to preserve the relationships between the elements of the lattice as much as possible. Then, if necessary, it will be possible to return to the original representation and explore the local neighborhood of the element of interest. The construction is based on the well-known characterization of lattice congruences, a simple proof of this fact is also given in the article. The correctness and completeness theorems for the algorithm are proved. The examples are given to demonstrate the subtleties of the application and operation of the algorithm presented in the work.
[+] References (15)
- Ganter, B., and R. Wille. 2024. Formal concept analysis: Mathematical foundations. 2nd ed. Cham, Switzerland: Springer. 370 p. doi: 10.1007/978-3-031-63422-2.
- Davey, B. A., and H. A. Priestley. 2012. Introduction to lattices and order. 2nded. Cambridge, U.K.: Cambridge University Press. 298 p. doi: 10.1017/CBO9780511809088.
- Finn, V. K. 2011. J. S. Mill's inductive methods in artificial intelligence systems. Part I. Scientific Technical Information Processing 38(6):385-402. doi: 10.3103/ S0147688211060037. EDN: PEQWYD.
- Finn, V. K. 2012. J. S. Mill's inductive methods in artificial intelligence systems. Part II. Scientific Technical Information Processing 39(5):241-260. doi: 10.3103/ S0147688212050036. EDN: XZVFBO
- Vinogradov, D. V. 2024. The nonpolynomiality of the number of similarities for random training sets. Pattern Recognition Image Analysis 34(3):570-573. doi: 10.1134/ S1054661824700378. EDN: AJOZUQ.
- Wille, R. 1982. Restructuring lattice theory: An approach based on hierarchies of concepts. Ordered sets. Ed. I. Rival. NATO Advanced Study Institutes ser. Netherlands: Springer. 83:445-470. doi: 10.1007/978-94-009-7798- 3.15.
- Vinogradov, D. V. 2022. Algebraic machine learning: Emphasis on efficiency. Automat. Rem. Contr. 83(6):831-846. doi: 10.1134/S0005117922060029. EDN: BAPXFM.
- Dasgupta, S., C. H. Papadimitriou, and U. V. Vazirani. 2006. Algorithms. New York, NY: McGraw-Hill. 336 p. doi: 10.5555/1177299.
- Grusho, A. A., N. A. Grusho, M. I. Zabezhailo, V. V. Kulchenkov, E. E. Timonina, and S.Ya. Shorgin. 2023. Prichinno-sledstvennye svyazi v zadachakh klassifikatsii [Causal relationships in classification problems]. Infor- matika i ee Primeneniya - Inform. Appl. 17(1):43-49. doi: 10.14357/19922264230106. EDN: DTQZPK.
- Grusho, A. A., N. A. Grusho, M. I. Zabezhailo, E. E. Timonina, and S.Ya. Shorgin. 2023. Slozhnye prichinno- sledstvennye svyazi [Complex cause-and-effect relationships]. Informatika i ee Primeneniya - Inform. Appl. 17(2):84-89.doi: 10.14357/19922264230212. EDN: TGXQIW.
- Grusho, A. A., N.A. Grusho, M.I. Zabezhailo, D. V. Smirnov, and E. E. Timonina. 2023. Klassifikatsiya s pomoshch'yu prichinno-sledstvennykh svyazey [Classification by cause-and-effect relationships]. Informati- ka i ee Primeneniya - Inform. Appl. 17(3):71-75. doi: 10.14357/19922264230310. EDN: AKWBZD.
- Grusho, A. A., N. A. Grusho, M. I. Zabezhailo, V. O. Piskovski, and E. E. Timonina. 2025. Mashinnoe obuchenie i doverie k rezul'tatam klassifikatsii [Machine learning and trust in classification results], Informatika i ee Primeneniya - Inform. Appl. 19(2):63-68, doi: 10,14357/ 19922264250208, EDN: CXRNNK,
- Lamsaf, A,, R, Carrilho, J, C, Neves, and H, Proenga, 2025, Causality, machine learning, and feature selection: A survey, Sensors - Basel 25(8):2373, 25 p, doi: 10,3390/s25082373,
- Vinogradov, D, V. 2023, Minimization of empirical risk as a means of choosing the number of hypotheses in algebraic machine learning, Pattern Recognition Image Analysis 33(3):525-528, doi: 10,1134/S1054661823030458, EDN: AJWVAK,
- Vinogradov, D,V. and L,A, lakimova, 2024, Probabilistic approach to good old-fashioned artificial intelligence, Automatic Documentation Mathematical Linguistics 58(2): 135-140, doi: 10,3103/s000510552470002x, EDN: VZATPA,
[+] About this article
Title
REDUCTIONS ALGORITHM OF THE SMALLEST TRAINING SAMPLE FOR FACTOR-LATTICE
Journal
Informatics and Applications
2026, Volume 20, Issue 2, pp 25-34
Cover Date
2026-10-07
DOI
10.14357/19922264260202
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
lattice; irreducible elements; training sample; candidate; congruence; factor-lattice
Authors
D. V. Vinogradov 
Author Affiliations
Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
|