Article

Free access

How many queries are needed to learn?

Authors:

Lisa Hellerstein,

Vijay Raghavan,

Krishnan Pillaipakkamnatt,

Dawn WilkinsAuthors Info & Claims

STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing

Pages 190 - 199

https://doi.org/10.1145/225058.225114

Published: 29 May 1995 Publication History

PDF eReader

References

[1]

H. Aizenstein, L. Hellerstein, and L. Pitt. Read-thrice DNF is Hard to Learn with Membership and Equiva-lence Queries. Proceedings of the 33rd IEEE Conference on the Foundations of Computer Science, 1992.

Google Scholar

[2]

D. Angluin. Learning Regular Sets from Queries and Counterexamples. Information and Computation, 75:87-106, 1987.

Digital Library

Google Scholar

[3]

D. Angluin. Queries and Concept Learning. Machine Learning, 2:319-342, 1988.

Digital Library

Google Scholar

[4]

D. Angluin. Negative Results for Equivalence Queries. &fachtne Learning, 5:121-150, 1990.

Digital Library

Google Scholar

[5]

D. Angluin, M. Frazier, and L. Pitt. Learning Conjunc-tions of Horn Clauses. Proceedings of the 31.rt Annual IEEE Symposium on the Foundations of Computer Sci-ence, pages 186-192, 1990.

Google Scholar

[6]

D. Angluin, L. Hellerstein, and M. Karpinski. Learn-ing Read-Once Formulas wit h Queries. Journal of the ACM, pages 185-210, 1993.

Digital Library

Google Scholar

[7]

D. Angluin and M. Kharitonov. When Won't Member-ship Queries Help? Proceedings of the ACM Symposium on Theory of Computing, pages 444-454, 1991.

Digital Library

Google Scholar

[8]

M. Anthony, G. Brightwell, and J. Shawe-Taylor. On Specifying Boolean Functions by Labelled Examples. Technical report, London School of Economics, London, U. K., 1992.

Google Scholar

[9]

J. C. Bioch and T. Ibaraki. Complexity of Identification and DusJization of Positive Boolean Functions. Tech-nical report RRR 25-93, Rutgers Center for Operations Research, 1993.

Google Scholar

[10]

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. War-muth. Learnability and the Vapnik-Chervonenkis Di-mension. Journal of the AC'.V, 36(4):929-965, 1989.

Digital Library

Google Scholar

[11]

N. Bshouty. Exact Learning ~ia the Monotone Theory. Proceedings of the 3Jth Annual IEEE Symposium on the Foundations of Computer Science, pages 302-311, 1993.

Google Scholar

[12]

N. Bshouty. Personal communication, November 1994.

Google Scholar

[13]

N. Bshouty, R. Cleve, S. Kannan, and C. Tamon. Ora-cles and Queries that are Sufficient for Exact Learning. Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, pages 130-139, 1994.

Digital Library

Google Scholar

[14]

P. Erd& and J. Spencer. Probabilistic Methods in Com-binatorics. Probability and Mathematical Statistics A Series of Monographs and Textbooks. Academic Press, 1974.

Google Scholar

[15]

R. GavaJd& On the Power of Equivalence Queries. Pro-ceedings of EUROCOLT '93, pages 193-203, 1993.

Digital Library

Google Scholar

[16]

S. Goldman and M. Kearns. On the Complexity of Teaching. Proceedings of the Fourth .4 nnual Work-shop on Computational Learning Theory, pages 303- 314, 1991.

Digital Library

Google Scholar

[17]

T. Hancock. Identifying p-Formula Decision Trees with Queries. Proceedings of the Third Annual JVork.shop on Computational Learning Theory, pages 23-37, 1990.

Digital Library

Google Scholar

[18]

T. Hegedtis. Personal communication, November 1994.

Google Scholar

[19]

John Hopcroft and Jeffrey Unman. Introduction to Au-tomata Theory, Languages and Computation. Addison-Wesley, 1979.

Digital Library

Google Scholar

[20]

S. Kannan. On the Query Complexity of Learning. Pro-ceedings of the Sixth Annual ACM Conference on Com-putational Learning Theory, pages 58-66, 1993.

Digital Library

Google Scholar

[21]

J. Kaneps and R. Frievalds. Running Time to Recog-nize Nonregular Languages by 2-way Probabilistic Fi-nite Automata. In J. Leach Albert, B. Monien, and hf. Rodriguez Artalejo, editors. ICALP '91, Vol. 510 of Lecture Notes in Computer Science, pages 355-361. Springer-Verlag, 1991.

Crossref

Google Scholar

[22]

E. Kushilevitz and Y. Mansour. Learning Decision Trees Using the Fourier Spectrum. 51A M JournaZ of Computing, ZZ(6):1331-1348, 1993.

Digital Library

Google Scholar

[23]

J. Naor and hf. Naor. Small-bias Probability Spaces: Efficient Constructions and Applications. Proceedings of the 22nd Annual A C,}f Symposium on Theory of Computing, pages 213-223, 1990.

Digital Library

Google Scholar

[24]

K. Pillaipakkamnatt and v. Raghavan. On the Limits of Proper Learnability of Subclasses of DNF Formulas. Proceedings of the Seventh Annual A CM Conference on Computational Learning Theory, pages 118-129, 1994.

Digital Library

Google Scholar

[25]

R. Rivest and R. Schapire. Inference of Finite Au-tomata Using Homing Sequences. Proceedings of the 21st Annual ACM Symposium on Theory oj Comput-tng, pages 411-420, 1989.

Digital Library

Google Scholar

[26]

A. Shinohara and S. lliyano. Teachability in Compu-tational Learning. New Generation Computing, 8:337- 347, 1991.

Digital Library

Google Scholar

[27]

L. Stockmeyer. On Approximation Algorithms for #P. SIAM Journal on Computing, 14:849-861, 1985.

Crossref

Google Scholar

[28]

L. Valiant. A Theory of the Learnable. Communica-tions of the ACM, 27(11):1134-1142, 1984.

Digital Library

Google Scholar

Cited By

View all

Pillaipakkamnatt KRaghavan V(2018)On the limits of proper learnability of subclasses of DNF formulasMachine Language10.1007/BF0011401125:2-3(237-263)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/BF00114011
Becerra-Bonache LJiménez-López M(2014)An Overview of the Interrelation Among Agent Systems, Learning Models and Formal LanguagesTransactions on Computational Collective Intelligence XVII10.1007/978-3-662-44994-3_3(46-65)Online publication date: 23-Nov-2014
https://doi.org/10.1007/978-3-662-44994-3_3
Balcan MBlum A(2008)Clustering with Interactive FeedbackProceedings of the 19th international conference on Algorithmic Learning Theory10.1007/978-3-540-87987-9_27(316-328)Online publication date: 12-Oct-2008
https://dl.acm.org/doi/10.1007/978-3-540-87987-9_27
Show More Cited By

Index Terms

How many queries are needed to learn?

Recommendations

How many queries are needed to learn?

We investigate the query complexity of exact learning in the membership and (proper) equivalence query model. We give a complete characterization of concept classes that are learnable with a polynomial number of polynomial sized queries in this model. ...
How Many Queries Are Needed to Learn One Bit of Information?

In this paper we study the question how many queries are needed to “halve a given version space”. In other words: how many queries are needed to extract from the learning environment the one bit of information that rules out fifty percent of the ...
Write-and-learn: promoting meaningful learning through concept map-based formative feedback on writing assignments
LAK '17: Proceedings of the Seventh International Learning Analytics & Knowledge Conference

A primary goal of higher education is to promote meaningful learning: the delivery of core academic content to students in innovative ways that allow them to learn and then apply what they have learned. As a pedagogical strategy, Writing-to-Learn (WTL) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing

May 1995

776 pages

ISBN:0897917189

DOI:10.1145/225058

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 May 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC95

Sponsor:

SIGACT

STOC95: Symposium on Theory of Computing

May 29 - June 1, 1995

Nevada, Las Vegas, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
376
Total Downloads

Downloads (Last 12 months)40
Downloads (Last 6 weeks)8

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Pillaipakkamnatt KRaghavan V(2018)On the limits of proper learnability of subclasses of DNF formulasMachine Language10.1007/BF0011401125:2-3(237-263)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/BF00114011
Becerra-Bonache LJiménez-López M(2014)An Overview of the Interrelation Among Agent Systems, Learning Models and Formal LanguagesTransactions on Computational Collective Intelligence XVII10.1007/978-3-662-44994-3_3(46-65)Online publication date: 23-Nov-2014
https://doi.org/10.1007/978-3-662-44994-3_3
Balcan MBlum A(2008)Clustering with Interactive FeedbackProceedings of the 19th international conference on Algorithmic Learning Theory10.1007/978-3-540-87987-9_27(316-328)Online publication date: 12-Oct-2008
https://dl.acm.org/doi/10.1007/978-3-540-87987-9_27
Arvind VVinodchandran N(2005)Exact learning via teaching assistants (Extended abstract)Algorithmic Learning Theory10.1007/3-540-63577-7_50(291-306)Online publication date: 9-Jun-2005
https://doi.org/10.1007/3-540-63577-7_50
Arvind VVinodchandran N(2005)The complexity of exactly learning algebraic conceptsAlgorithmic Learning Theory10.1007/3-540-61863-5_38(100-112)Online publication date: 3-Jun-2005
https://doi.org/10.1007/3-540-61863-5_38
Angluin D(2001)Queries RevisitedAlgorithmic Learning Theory10.1007/3-540-45583-3_3(12-31)Online publication date: 31-Oct-2001
https://doi.org/10.1007/3-540-45583-3_3
Guijarro DLavín VRaghavan V(1999)Exact Learning when Irrelevant Variables AboundComputational Learning Theory10.1007/3-540-49097-3_8(91-100)Online publication date: 19-Nov-1999
https://doi.org/10.1007/3-540-49097-3_8
Feigelson AHellerstein LBlum AKearns M(1996)Learning conjunctions of two unate DNF formulas (extended abstract)Proceedings of the ninth annual conference on Computational learning theory10.1145/238061.238112(255-265)Online publication date: 1-Jan-1996
https://dl.acm.org/doi/10.1145/238061.238112
Hegedűs TMaass W(1995)Generalized teaching dimensions and the query complexity of learningProceedings of the eighth annual conference on Computational learning theory10.1145/225298.225311(108-117)Online publication date: 5-Jul-1995
https://dl.acm.org/doi/10.1145/225298.225311

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

How many queries are needed to learn?

How Many Queries Are Needed to Learn One Bit of Information?

Write-and-learn: promoting meaningful learning through concept map-based formative feedback on writing assignments