Volume 24, No 1, 2017, P. 31-55
E. M. Zamaraeva
On teaching sets for 2-threshold functions of two variables
We consider $k$-threshold functions of n variables, i. e. the functions representable as the conjunction of $k$ threshold functions. For $n$ = 2, $k$ = 2, we give upper bounds for the cardinality of the minimal teaching set depending on the various properties of the function.
Illustr. 6, bibliogr. 9.
Keywords: machine learning, threshold function, teaching dimension, teaching set.
Elena M. Zamaraeva 1
1. Lobachevsky State University,
23 Gagarin Ave., 603950 Nizhny Novgorod, Russia
Received 31 August 2015
Revised 2 August 2016
 N. Yu. Zolotykh and V. N. Shevchenko, Estimating the complexity of deciphering a threshold function in a $k$-valued logic, Zh. Vychisl. Mat. Mat. Fiz., 39, No. 2, 346–352, 1999 [Russian]. Translated in Comput. Math. Math. Phys., 39, No. 2, 328–334, 1999.
 V. N. Shevchenko and N. Yu. Zolotykh, On the complexity of deciphering the threshold functions of $k$-valued logic, Dokl. Akad. Nauk, 362, No. 5, 606–608, 1998 [Russian]. Translated in Dokl. Math., 58, No. 2, 268–270, 1998.
 M. A. Alekseyev, M. G. Basova, and N. Yu. Zolotykh, On the minimal teaching sets of two-dimensional threshold functions, SIAM J. Discrete Math., 29, No. 1, 157–165, 2015.
 M. Anthony, G. Brightwell, and J. Shawe-Taylor, On specifying Boolean functions by labelled examples, Discrete Appl. Math., 61, No. 1, 1–25, 1995.
 W. J. Bultman and W. Maass, Fast identification of geometric objects with membership queries, Inf. Comput., 118, No. 1, 48–64, 1995.
 A. Yu. Chirkov and N. Yu. Zolotykh, On the number of irreducible points in polyhedra, Graphs Comb., 32, No. 5, 1789–1803, 2016.
 V. N. Shevchenko and N. Yu. Zolotykh, Lower bounds for the complexity of learning half-spaces with membership queries, in Algorithmic Learning Theory (Proc. 9th Int. Conf., Otzenhausen, Germany, Oct. 8–10, 1998), pp. 61–71, Springer, Berlin, 1998 (Lect. Notes Comput. Sci., Vol. 1501).
 J. Trainin, An elementary proof of Pick’s theorem, Math. Gaz., 91, No. 522, 536–540, 2007.
 E. M. Zamaraeva On teaching sets of k-threshold functions, 2015 (Cornell Univ. Libr. e-Print Archive, arXiv:1502.04340).