Volume 24, No 1, 2017, P. 31-55

UDC 519.715
E. M. Zamaraeva
On teaching sets for 2-threshold functions of two variables

Abstract:
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.

DOI: 10.17377/daio.2017.24.508

Elena M. Zamaraeva ¹
1. Lobachevsky State University,
23 Gagarin Ave., 603950 Nizhny Novgorod, Russia
e-mail: elena.zamaraeva@gmail.com

Received 31 August 2015
Revised 2 August 2016

References

[1] 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.

[2] 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.

[3] 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.

[4] M. Anthony, G. Brightwell, and J. Shawe-Taylor, On specifying Boolean functions by labelled examples, Discrete Appl. Math., 61, No. 1, 1–25, 1995.

[5] W. J. Bultman and W. Maass, Fast identification of geometric objects with membership queries, Inf. Comput., 118, No. 1, 48–64, 1995.

[6] A. Yu. Chirkov and N. Yu. Zolotykh, On the number of irreducible points in polyhedra, Graphs Comb., 32, No. 5, 1789–1803, 2016.

[7] 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).

[8] J. Trainin, An elementary proof of Pick’s theorem, Math. Gaz., 91, No. 522, 536–540, 2007.

[9] E. M. Zamaraeva On teaching sets of k-threshold functions, 2015 (Cornell Univ. Libr. e-Print Archive, arXiv:1502.04340).