Abstract
The complexity of exact learning of bounded-weight Boolean functions is considered in the paper separately using four types of queries: membership queries, equivalence queries, extended equivalence queries, and comparation queries. The values of the complexity for the first three types are obtained for all classes of functions at consideration. Upper and lower bounds of the complexity for comparation queries being of the same order are presented. Moreover, the exact value of the complexity of learning upper bounded-weight Boolean functions with the help of comparation queries is obtained.
Similar content being viewed by others
REFERENCES
D. Angluin, ‘‘Queries and concept learning,’’ Mach. Learning 2, 319–342 (1988). https://doi.org/10.1023/A:1022821128753
D. Angluin, ‘‘Queries revisited,’’ Theor. Comput. Sci. 313, 175–194 (2004). https://doi.org/10.1016/j.tcs.2003.11.004
A. B. Bistrigova, ‘‘Attribute-efficient learning of Boolean functions from Post closed classes,’’ Discrete Math. Appl. 30, 285–301 (2020). https://doi.org/10.1515/dma-2020-0025
A. V. Bistrigova, ‘‘Using comparation queries in attribute-efficient learning of Boolean functions,’’ Intell. Sist. Teriya Prilozh. 23 (4), 115–124 (2019).
A. V. Bistrigova, ‘‘Learning of Boolean fixed-weight functions,’’ Intell. Sist. Teoriya Prilozh. 24 (3), 63–96 (2019).
ACKNOWLEDGMENTS
The author thanks her scientific advisor Professor E.E. Gasanov for the problem formulation and assistance in her work.
Funding
The study is supported by the Interdisciplinary Scientific and Educational School on Brain, Cognitive Systems, and Artificial Intelligence of the Lomonosov Moscow State University.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
The author declares that she has no conflicts of interest.
Additional information
Translated by E. Oborin
About this article
Cite this article
Bystrygova, A.V. Learning of Bounded-Weight Boolean Functions. Moscow Univ. Math. Bull. 76, 251–258 (2021). https://doi.org/10.3103/S0027132221060036
Received:
Published:
Issue Date:
DOI: https://doi.org/10.3103/S0027132221060036