Generalized teaching dimensions and the query complexity of learning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Generalized teaching dimensions and the query complexity of learning

Full text

Pdf (1.11 MB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the eighth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 108 - 117

Year of Publication: 1995

ISBN:0-89791-723-5

Author

Tibor Hegedűs

Department of Computer Science, Comenius University, 84215 Bratislava, Slovakia

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
University of California : University of California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 24, Citation Count: 17

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/225298.225311 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	H. Aizenstein, T. Hegedfis, L. HeUerstein, L. Pitt, "Complexity Theoretic Hardness Results for Query Learning", submitted for publication.
	2	H. Aizenstein, L. Hellerstein, L. Pitt, "Read-Thrice DNF is Hard to Learn with Membership and Equivalence Queries", in: Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'92), IEEE Press, Los Alamitos, CA, 1992, pp. 523-532.
	3	Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
	4	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	5	Dana Angluin, Negative Results for Equivalence Queries, Machine Learning, v.5 n.2, p.121-150, Jun. 1990 [doi>10.1023/A:1022692615781]
	6	Dana Angluin , Michael Frazier , Leonard Pitt, Learning Conjunctions of Horn Clauses, Machine Learning, v.9 n.2-3, p.147-164, July 1992 [doi>10.1007/BF00992675]
	7	Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning read-once formulas with queries, Journal of the ACM (JACM), v.40 n.1, p.185-210, Jan. 1993 [doi>10.1145/138027.138061]
	8	Peter Auer , Philip M. Long, Simulating access to hidden information while learning, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.263-272, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195152]
	9	N. Bshouty, R. Cleve, "On the Exact Learning of Formulas in Parallel", in: Proceedings of the 33rd Annual Symposzum on Foundations of Computer Science (FOCS'92), IEEE Press, Los Alamitos, CA, 1992, pp. 513-522.
	10	Nader H. Bshouty , Sally A. Goldman , Thomas R. Hancock , Sleiman Matar, Asking questions to minimize errors, Proceedings of the sixth annual conference on Computational learning theory, p.41-50, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168310]
	11	Nader H. Bshouty , Richard Cleve , Sampath Kannan , Christino Tamon, Oracles and queries that are sufficient for exact learning (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.130-139, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181067]
	12	William J. Bultman , Wolfgang Maass, Fast identification of geometric objects with membership queries, Proceedings of the fourth annual workshop on Computational learning theory, p.337-353, August 05-07, 1991, Santa Cruz, California, United States
	13	T. Cover, "Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition", IEEE Transaetion~ on Electronic Computers 14 (1965) 326-334.
	14	L. Danzer, B. Grfinbaum, V. Klee, "Helly's Theomin and its Relatives", in: Convexity, Proc. of Symposia in Pure Mathematics, vol. 7, AMS, Providence, 1963, pp. 101-180.
	15	Ricard Gavaldà, On the power of equivalence queries, Proceedings of the first European conference on Computational learning theory, p.193-203, October 1994, Royal Holloway, Univ. of London, United Kingdom
	16	Sally A. Goldman , Michael J. Kearns, On the complexity of teaching, Proceedings of the fourth annual workshop on Computational learning theory, p.303-314, August 05-07, 1991, Santa Cruz, California, United States
	17	Tibor Hegedűs, On training simple neural networks and small-weight neurons, Proceedings of the first European conference on Computational learning theory, p.69-82, October 1994, Royal Holloway, Univ. of London, United Kingdom
	18	Tibor Hegedűs, Geometrical concept learning and convex polytopes, Proceedings of the seventh annual conference on Computational learning theory, p.228-236, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181124]
	19	Lisa Hellerstein , Vijay Raghavan , Krishnan Pillaipakkamnatt , Dawn Wilkins, How many queries are needed to learn?, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.190-199, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225114]
	20	E. Helly, "0bet Mengen Konvexer KSrper mit Gemeinschaftlichen Punkten", Jahresbericht der Deutschen Mathematiker- Vereinigung 32 (1923) 175-176.
	21	Yoshiyasu Ishigami , Sei'ichi Tani, The VC-Dimensions of Finite Automata with n States, Proceedings of the 4th International Workshop on Algorithmic Learning Theory, p.328-341, November 08-10, 1993
	22	Sampath K. Kannan, On the query complexity of learning, Proceedings of the sixth annual conference on Computational learning theory, p.58-66, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168312]
	23	M. Karchmer , N. Linial , I. Newman , M. Saks , A. Wigderson, Combinatorial characterization of read-once formulae, Discrete Mathematics, v.114 n.1-3, p.275-282, April 28, 1993 [doi>10.1016/0012-365X(93)90372-Z]
	24	Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
	25	W. Maass, Gy. TurS. n, "On the Complexity of Learning from Counterexamples", in: Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS'89), IEEE Computer Society Press, Los Angeles, CA, 1989, pp. 262-267.
	26	IV. Maass, Gy. Turgn, "On the Complexity of Learning from Counterexalnples and Membership Queries", in: Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS'90), IEEE Computer Society Press, Washington, DC, 1990, pp. 203-210.
	27	Wolfgang Maass , György Turán, Lower Bound Methods and Separation Results for On-Line Learning Models, Machine Learning, v.9 n.2-3, p.107-145, July 1992 [doi>10.1007/BF00992674]
	28	Wolfgang Maass , György Turán, How fast can a threshold gate learn?, Proceedings of a workshop on Computational learning theory and natural learning systems (vol. 1) : constraints and prospects: constraints and prospects, p.381-414, August 1994, Princeton, New Jersey, United States
	29	Wolfgang Maass , György Turán, Algorithms and Lower Bounds for On-Line Learning of Geometrical Concepts, Machine Learning, v.14 n.3, p.251-269, March 1994 [doi>10.1023/A:1022653511837]
	30	M. Yu. MoM&ov, "Conditional Test~", Problcmy Kibcrnet~k~40 (1983) 131-170 (in Russian).
	31	J. Myhill, "Finite Automata and the Representation of Events", WADC TR 57-624, 1957, pp. 112-137.
	32	A. Nerode, "Linear Automaton Transformations", Proceedings of the American Mathematical Society 9 (1958) 541-544.
	33	Krishnan Pillaipakkamnatt , Vijay Raghavan, On the limits of proper learnability of subclasses of DNF formulas, Proceedings of the seventh annual conference on Computational learning theory, p.118-129, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181063]
	34	R. L. Rivest , R. E. Schapire, Inference of finite automata using homing sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.411-420, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73047]

CITED BY 17

	Robert H. Sloan , Balázs Szörényi , György Turán, Projective DNF formulae and their revision, Discrete Applied Mathematics, v.156 n.4, p.530-544, February, 2008
	Marta Arias , Roni Khardon, Learning closed horn expressions, Information and Computation, v.178 n.1, p.214-240, October 10, 2002
	Yosuke Hayashi , Satoshi Matsumoto , Ayumi Shinohara , Masayuki Takeda, Uniform characterizations of polynomial-query learnabilities, Theoretical Computer Science, v.292 n.2, p.377-385, 27 January 2003
	Sanjoy Dasgupta , Wee Sun Lee , Philip M. Long, A Theoretical Analysis of Query Selection for Collaborative Filtering, Machine Learning, v.51 n.3, p.283-298, June 2003
	Dana Angluin, Queries revisited, Theoretical Computer Science, v.313 n.2, p.175-194, 17 February 2004
	Marta Arias , Roni Khardon, Complexity parameters for first order classes, Machine Learning, v.64 n.1-3, p.121-144, September 2006
	Alp Atici , Rocco A. Servedio, Improved Bounds on Quantum Learning Algorithms, Quantum Information Processing, v.4 n.5, p.355-386, November 2005
	Lisa Hellerstein , Vijay Raghavan, Exact learning of DNF formulas using DNF hypotheses, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Frank J. Balbach, Measuring teachability using variants of the teaching dimension, Theoretical Computer Science, v.397 n.1-3, p.94-113, May, 2008
	Lisa Hellerstein , Vijay Raghavan, Exact learning of DNF formulas using DNF hypotheses, Journal of Computer and System Sciences, v.70 n.4, p.435-470, June 2005
	Lisa Hellerstein , Krishnan Pillaipakkamnatt , Vijay Raghavan , Dawn Wilkins, How many queries are needed to learn?, Journal of the ACM (JACM), v.43 n.5, p.840-862, Sept. 1996
	José L. Balcázar , Jorge Castro , David Guijarro , Johannes Köbler , Wolfgang Lindner, A general dimension for query learning, Journal of Computer and System Sciences, v.73 n.6, p.924-940, September, 2007
	Marta Arias , Aaron Feigelson , Roni Khardon , Rocco A. Servedio, Polynomial certificates for propositional classes, Information and Computation, v.204 n.5, p.816-834, May 2006
	Amos Beimel , Felix Geller , Eyal Kushilevitz, The query complexity of finding local minima in the lattice, Information and Computation, v.171 n.1, p.69-83, November 25, 2001
	Amos Beimel , Felix Geller , Eyal Kushilevitz, The query complexity of finding local minima in the lattice, Proceedings of the eleventh annual conference on Computational learning theory, p.294-302, July 24-26, 1998, Madison, Wisconsin, United States
	Lane A. Hemaspaandra, SIGACT News complexity theory column 32, ACM SIGACT News, v.32 n.2, June 2001
	Josef Dujnič , Norbert Frištacký , Ludovít Molnár , Ivan Plander , Branislav Rovan, On the History of Computer Science, Computer Engineering, and Computer Technology Development in Slovakia, IEEE Annals of the History of Computing, v.21 n.3, p.38-48, July 1999