×

zbMATH — the first resource for mathematics

On learning monotone Boolean functions with irrelevant variables. (English. Russian original) Zbl 1200.68131
Discrete Math. Appl. 20, No. 3, 307-320 (2010); translation from Diskretn. Mat. 22, No. 3, 134-145 (2010).
Summary: The problem of learning a function in the context of the exact model of learning using membership queries consists in reconstruction of this function table of values using membership queries. Here we obtain the order of complexity of learning monotone Boolean functions with irrelevant variables.

MSC:
68Q32 Computational learning theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Korobkov V. K., Probl. Kibern. 13 pp 5– (1965)
[2] Hansel G., Acad. Sci., Paris, Sér. B 262 pp 1088– (1966)
[3] Valiant L., Comm. ACM 27 pp 1134– (1984) · Zbl 0587.68077
[4] Angluin D., Mach. Learn. 2 pp 319– (1988)
[5] Damaschke P., Mach. Learn. 41 pp 197– (2000) · Zbl 0965.68029
[6] Damaschke P., J. Comput. Syst. Sci. 67 pp 46– (2003) · Zbl 1055.68060
[7] Damaschke P., Lect. Notes Comput. Sci. 1851 pp 504– (2000)
[8] Gilbert E. N., J. Math. Phys. 33 pp 57– (1954)
[9] Osokin V. V., Intelligent Systems 11 pp 587– (2007)
[10] Osokin V. V., Discrete Math. Appl. 18 pp 155– (2008) · Zbl 1192.68230
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.