Simulating access to hidden information while learning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Simulating access to hidden information while learning

Full text

Pdf (1.05 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 263 - 272

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Peter Auer	Institute for Theoretical Computer Science, Technische Universität Graz, Klosterwiesgasse 32/2, A-8010 Graz, Austria
Philip M. Long	Computer Science Department, Duke University, P.O. Box 90129, Durham, NC

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 12, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/195058.195152 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	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	2	Dana Angluin , Michael Kharitonov, When won't membership queries help?, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.444-454, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103420]
	3	P. Auer and P.M. Long. Structural results for on-line learning models with and without queries, 1993. Submitted.
	4	Peter Auer , Philip M. Long , Wolfgang Maass , Gerhard J. Woeginger, On the complexity of function learning, Proceedings of the sixth annual conference on Computational learning theory, p.392-401, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168384]
	5	Gyora M. Benedek , Alon Itai, Learnability with respect to fixed distributions, Theoretical Computer Science, v.86 n.2, p.377-389, Sept. 2, 1991 [doi>10.1016/0304-3975(91)90026-X]
	6	Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
	7	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]
	8	N. Cesa-Bianchi , Y. Freund , D. P. Helmbold , M. Warmuth, On-line prediction and conversion strategies, Proceedings of the first European conference on Computational learning theory, p.205-216, October 1994, Royal Holloway, Univ. of London, United Kingdom
	9	Nicolò Cesa-Bianchi , Yoav Freund , David P. Helmbold , David Haussler , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.382-391, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167198]
	10	Andrzej Ehrenfeucht , David Haussler, A general lower bound on the number of examples needed for learning, Information and Computation, v.82 n.3, p.247-261, Sep. 1989 [doi>10.1016/0890-5401(89)90002-3]
	11	Bonnie Eisenberg , Ronald L. Rivest, On the sample complexity of pac-learning using random and chosen examples, Proceedings of the third annual workshop on Computational learning theory, p.154-162, August 06-08, 1990, Rochester, New York, United States
	12	D. Haussler , N. Littlestone , M. K. Warmuth, PREDICTING {0,1}-FUNCTIONS ON RANDOMLY DRAWN POINTS, University of California at Santa Cruz, Santa Cruz, CA, 1990
	13	S. R. Kulkarni , S. K. Mitter , J. N. Tsitsiklis, Active Learning Using Arbitrary Binary Valued Queries, Machine Learning, v.11 n.1, p.23-35, April 1993 [doi>10.1023/A:1022627018023]
	14	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]
	15	N. Littlestone, Mistake bounds and logarithmic linear-threshold learning algorithms, University of California at Santa Cruz, Santa Cruz, CA, 1990
	16	Nick Littlestone , Manfred K. Warmuth, THE WEIGHTED MAJORITY ALGORITHM (Supersedes 89-16), University of California at Santa Cruz, Santa Cruz, CA, 1992
	17	Wolfgang Maass, On-line learning with an oblivious environment and the power of randomization, Proceedings of the fourth annual workshop on Computational learning theory, p.167-178, August 05-07, 1991, Santa Cruz, California, United States
	18	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]
	19	György Turán, Lower bounds for PAC learning with queries, Proceedings of the sixth annual conference on Computational learning theory, p.384-391, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168382]
	20	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
	21	V.N. Vapnik and A.Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and i$s Applications, 16(2):264-280, 1971.
	22	Volodimir G. Vovk, Aggregating strategies, Proceedings of the third annual workshop on Computational learning theory, p.371-386, August 06-08, 1990, Rochester, New York, United States
	23	V. G. Vovk, Universal forecasting algorithms, Information and Computation, v.96 n.2, p.245-277, Feb. 1992 [doi>10.1016/0890-5401(92)90050-P]

CITED BY 7

	Tibor Hegedűs, Generalized teaching dimensions and the query complexity of learning, Proceedings of the eighth annual conference on Computational learning theory, p.108-117, July 05-08, 1995, Santa Cruz, California, United States
	Robert H. Sloan , György Turán, Learning with queries but incomplete information (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.237-245, July 12-15, 1994, New Brunswick, New Jersey, United States
	Peter L. Bartlett , Philip M. Long , Robert C. Williamson, Fat-shattering and the learnability of real-valued functions, Proceedings of the seventh annual conference on Computational learning theory, p.299-310, July 12-15, 1994, New Brunswick, New Jersey, United States
	V. Vovk, Derandomizing Stochastic Prediction Strategies, Machine Learning, v.35 n.3, p.247-282, June 1999
	Peter Auer , Philip M. Long, Structural Results About On-line Learning Models With and Without Queries, Machine Learning, v.36 n.3, p.147-181, Sept. 1999
	Dana Angluin , Mārtiņš Kriķis , Robert H. Sloan , György Turán, Malicious Omissions and Errors in Answers to Membership Queries, Machine Learning, v.28 n.2-3, p.211-255, Aug./Sept. 1997
	Peter Auer , Nicolò Cesa-Bianchi, On-line learning with malicious noise and the closure algorithm, Annals of Mathematics and Artificial Intelligence, v.23 n.1-2, p.83-99, 1998