Learning sparse multivariate polynomials over a field with queries and counterexamples

Robert E. Schapire, Linda M. Sellie

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Scopus citations

Abstract

We consider the problem of learning a polynomial over an arbitrary field F defined on a set of boolean variables. We present the first probably effective algorithm for exactly identifying such polynomials using membership and equivalence queries. Our algorithm runs in time polynomial in n, the number of variables, and t, the number of nonzero terms appearing in the polynomial. The algorithm makes at most nt+2 equivalence queries, and at most (nt+1)(t2+3t)/2 membership queries. Our algorithm is equally effective for learning a generalized type of polynomial defined on certain kinds of semilattices. We also present an extension of our algorithm for learning multilinear polynomials when the domain of each variable is the entire field F.

Original languageEnglish (US)
Title of host publicationProc 6 Annu ACM Conf Comput Learn Theory
Editors Anon
PublisherPubl by ACM
Pages17-26
Number of pages10
ISBN (Print)0897916115
StatePublished - Dec 1 1993
Externally publishedYes
EventProceedings of the 6th Annual ACM Conference on Computational Learning Theory - Santa Cruz, CA, USA
Duration: Jul 26 1993Jul 28 1993

Publication series

NameProc 6 Annu ACM Conf Comput Learn Theory

Other

OtherProceedings of the 6th Annual ACM Conference on Computational Learning Theory
CitySanta Cruz, CA, USA
Period7/26/937/28/93

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Learning sparse multivariate polynomials over a field with queries and counterexamples'. Together they form a unique fingerprint.

Cite this