Том 24, номер 1, 2017 г., Стр. 31-55

УДК 519.715
Замараева Е. М.
О разрешающем множестве 2-пороговой функции двух переменных

Аннотация:
Рассматриваются $k$-пороговые функции $n$ переменных, т. е. функции, представимые в виде конъюнкции $k$ пороговых функций. Для случая $n$ = 2, $k$ = 2 даются верхние оценки мощности тупикового разрешающего множества функции в зависимости от eё различных свойств.
Ил. 6, библ. 9.

Ключевые слова: машинное обучение, пороговая функция, длина обучения, разрешающее множество.

DOI: 10.17377/daio.2017.24.508

Замараева Елена Михайловна ¹
1. Нижегородский гос. университет им. Н. И. Лобачевского,
пр. Гагарина, 23, 603950 Нижний Новгород, Россия
е-mail: elena.zamaraeva@gmail.com

Статья поступила 31 августа 2015 г.
Исправленный вариант — 2 августа 2016 г.

Литература

[1] Золотых Н. Ю., Шевченко В. Н. Об оценке сложности расшифровки пороговых функций $k$-значной логики // Журн. вычисл. математики и мат. физики. 1999. Т. 39, №. 2. С. 346–352.

[2] Шевченко В. Н., Золотых Н. Ю. О сложности расшифровки пороговых функций $k$-значной логики // Докл. АН. 1998. Т. 362, № 5. С. 606–608.

[3] Alekseyev M. A., Basova M. G., Zolotykh N. Yu. On the minimal teaching sets of two-dimensional threshold functions // SIAM J. Discrete Math. 2015. Vol. 29, No. 1. P. 157–165.

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

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

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

[7] Shevchenko V. N., Zolotykh N. Yu. Lower bounds for the complexity of learning half-spaces with membership queries // Algorithmic Learning Theory. Proc. 9th Int. Conf. (Otzenhausen, Germany, Oct. 8–10, 1998). Berlin: Springer, 1998. P. 61–71. (Lect. Notes Comput. Sci.; Vol. 1501).

[8] Trainin J. An elementary proof of Pick’s theorem // Math. Gaz. 2007. Vol. 91. P. 536–540.

[9] Zamaraeva E. On teaching sets of k-threshold functions // ArXiv e-prints (arXiv:1502.04340). 2015.