Email this article On Computational Efficiency of Knowledge Extraction by Probabilistic Algorithms
- Authors: Vinogradov D.V.1
-
Affiliations:
- Computer Science and Control Federal Research Center of the Russian Academy of Sciences
- Issue: No 4 (2023)
- Pages: 29-37
- Section: Computational Intelligence
- URL: https://journal-vniispk.ru/2071-8594/article/view/269741
- DOI: https://doi.org/10.14357/20718594230403
- EDN: https://elibrary.ru/NELPQW
- ID: 269741
Cite item
Full Text
Abstract
The paper demonstrates computational efficiency of probabilistic approach to knowledge extraction through binary similarity operation. In addition to previously proved by the author the result on sufficiency of a polynomial number of hypotheses on causes of investigated target property, the paper contains a polynomial upper bound on mean working time of the algorithm to generate a single candidate for hypothesis. The proven result concerns a family of algorithms based on coupled Markov chains. To obtain a good estimate for the length of the trajectory (before entering the ergodic state) of such a chain, we needed to enrich the training sample by adding negative columns for existing binary features.
About the authors
Dmitry V. Vinogradov
Computer Science and Control Federal Research Center of the Russian Academy of Sciences
Author for correspondence.
Email: KRRGuest@yandex.ru
Doctor of Physical and Mathematical Sciences, Leading Researcher
Russian Federation, MoscowReferences
- Finn V.K., Anshakov O.M. DSM-metod avtomaticheskogo porozhdeniya gipotez: Logicheskie i epistemologicheskie osnovaniya [JSM Method for Automatic Hypotheses Generation: Logical and Epistemological Foundations]. Moscow: Editorial URSS, 2009.
- Mill J.S. A System of Logic. Honolulu: University Press of the Pacific, 2002.
- Gusakova S.M., Finn V.K. Shodstva i pravdopodobnyj vyvod [Similarities and Plausible Inference]. Izvestia AN SSSR, Ser. «Technical cybernetics». 1987. No 5. P. 42–63.
- Ganter B., Wille R. Formal Concept Analysis: Mathematical Foundations. Berlin: Springer, 1999.
- Vinogradov D.V. Random generation of hypotheses in the JSM method using simple Markov chains. Automatic Documentation and Mathematical Linguistics. 2012. No 46(5). P. 221–228.
- Kuznetsov S.O. A Fast Algorithm for Computing All Intersections of Objects in a Finite Semi-Lattice, Automatic Documentation and Mathematical Linguistics. 1993. No 27(5). P. 11-21.
- Vinogradov D.V. Algebraic Machine Learning: Emphasis on Efficiency. Automation and Remote Control. 2022. No 83(6). P. 831–846.
- Kemeny J.G., Snell J.L. Finite Markov chains. New York: Springer, 1976.
- Vinogradov D.V. The VKF Method for Data Mining: a Survey of the State of the Art and Open Problems. Scientific and Technical Information Processing. 2018. No 45(6). P. 411–416.
- Vinogradov D.V. Markov Chains, Law of Total Probability, and Recurrence Relations. Automatic Documentation and Mathematical Linguistics. 2023. No 57(1). P. 68–72.
Supplementary files
