Volume 24, No 1, 2017, P. 3155
UDC 519.715
E. M. Zamaraeva
On teaching sets for 2threshold 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}
1. Lobachevsky State University,
23 Gagarin Ave., 603950 Nizhny Novgorod, Russia
email: 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 twodimensional threshold functions, SIAM J. Discrete Math., 29, No. 1, 157–165, 2015.
[4] M. Anthony, G. Brightwell, and J. ShaweTaylor, 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 halfspaces 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 kthreshold functions, 2015 (Cornell Univ. Libr. ePrint Archive, arXiv:1502.04340).
