|
This article is cited in 1 scientific paper (total in 1 paper)
Learning of monotone functions with single error correction
S. N. Selezneva, Y. Liu Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics
Abstract:
Learning of monotone functions is a well-known problem. Results obtained by V. K. Korobkov and G. Hansel imply that the complexity $\varphi_M(n)$ of learning of monotone Boolean functions equals $C_n^{\lfloor n/2\rfloor} + C_n^{\lfloor n/2\rfloor+1}$ ($\varphi_M(n)$ denotes the least number of queries on the value of an unknown monotone function on a given input sufficient to identify an arbitrary $n$-ary monotone function). In our paper we consider learning of monotone functions in the case when the teacher is allowed to return an incorrect response to at most one query on the value of an unknown function so that it is still possible to correctly identify the function. We show that learning complexity in case of the possibility of a single error is equal to the complexity in the situation when all responses are correct.
Keywords:
Boolean function, monotone function, learning of functions, learning complexity, $n$-dimensional Boolean cube, chain, chain partition, Hansel chains, error, error correction.
Received: 22.07.2019 Revised: 07.11.2019
Citation:
S. N. Selezneva, Y. Liu, “Learning of monotone functions with single error correction”, Diskr. Mat., 31:4 (2019), 53–69; Discrete Math. Appl., 31:3 (2021), 193–205
Linking options:
https://www.mathnet.ru/eng/dm1585https://doi.org/10.4213/dm1585 https://www.mathnet.ru/eng/dm/v31/i4/p53
|
Statistics & downloads: |
Abstract page: | 362 | Full-text PDF : | 39 | References: | 48 | First page: | 20 |
|