Geodesic
Learning of monotone functions with single error correction
Diskretnaya Matematika, Tome 31 (2019) no. 4, pp. 53-69.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2019_31_4_a3,
     author = {S. N. Selezneva and Y. Liu},
     title = {Learning of monotone functions with single error correction},
     journal = {Diskretnaya Matematika},
     pages = {53--69},
     publisher = {mathdoc},
     volume = {31},
     number = {4},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2019_31_4_a3/}
}
TY  - JOUR
AU  - S. N. Selezneva
AU  - Y. Liu
TI  - Learning of monotone functions with single error correction
JO  - Diskretnaya Matematika
PY  - 2019
SP  - 53
EP  - 69
VL  - 31
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2019_31_4_a3/
LA  - ru
ID  - DM_2019_31_4_a3
ER  - 
%0 Journal Article
%A S. N. Selezneva
%A Y. Liu
%T Learning of monotone functions with single error correction
%J Diskretnaya Matematika
%D 2019
%P 53-69
%V 31
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2019_31_4_a3/
%G ru
%F DM_2019_31_4_a3
S. N. Selezneva; Y. Liu. Learning of monotone functions with single error correction. Diskretnaya Matematika, Tome 31 (2019) no. 4, pp. 53-69. http://geodesic.mathdoc.fr/item/DM_2019_31_4_a3/

[1] Korobkov V. K., “O monotonnykh funktsiyakh algebry logiki”, Problemy kibernetiki, 1965, no. 13, 5–28 | Zbl

[2] Korobkov V. K., “Otsenka chisla monotonnykh funktsii algebry logiki i slozhnosti algoritma otyskaniya razreshayuschego mnozhestva dlya proizvolnoi monotonnoi funktsii algebry logiki”, Dokl. AN SSSR, 150:4 (1963), 744–747 | Zbl

[3] Hansel G., “Sur le nombre des fonctions booleennes monotones de $n$ variables”, C. R. Acad. Sci. Paris, 262 (1966), 1088–1090 ; Ansel Zh., “O chisle monotonnykh funktsii $n$ peremennykh”, Kiberneticheskii sbornik. Novaya seriya, no. 5, Mir, M., 1968, 53–57 | MR | Zbl

[4] Alekseev V. B., “O rasshifrovke nekotorykh klassov monotonnykh mnogoznachnykh funktsii”, Zh. vychisl. matem. i matem. fiziki, 16:1 (1976), 189–198 | MR | Zbl

[5] Sapozhenko A. A., Goryainov M. V., “O rasshifrovke monotonnykh funktsii na chastichno uporyadochennykh mnozhestvakh”, Diskretnyi analiz i issledovanie operatsii, 2:3 (1995), 79–80

[6] Sapozhenko A. A., Problema Dedekinda i metod granichnykh funktsionalov, Fizmatlit, M., 2009, 152 pp.

[7] Damaschke P., “Adaptive versus nonadaptive attribute-efficient learning”, Machine Learning, 41 (2000), 197–215 | DOI | MR | Zbl

[8] Osokin V. V., “On learning monotone Boolean functions with irrelevant variables”, Discrete Math. Appl., 20:3 (2010), 307–320 | DOI | DOI | MR | Zbl | Zbl

[9] Bshouty N.H., “Exact learning from an honest teacher that answers membership queries”, Theor. Comput. Sci., 733 (2018), 4–43 | DOI | MR | Zbl

[10] Korobkov V. K., “O nekotorykh tselochislennykh zadachakh lineinogo programmirovaniya”, Problemy kibernetiki, 1965, no. 14, 297–299