Learning with unreliable boundary queries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning with unreliable boundary queries

Full text

Pdf (1.15 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: 98 - 107

Year of Publication: 1995

ISBN:0-89791-723-5

Authors

Avrim Blum	School of Computer Science, Carnegie Mellon University, Pittsburgh, PA
Prasad Chalasani	Los Alamos National Lab., Los Alamos, NM
Sally A. Goldman	Dept. of Computer Science, Washington University, St. Louis, MO
Donna K. Slonim	MIT Lab. for CS, 545 Technology Square, Cambridge, MA

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): 3, Downloads (12 Months): 12, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

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.225310 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	D. Angluin. Exact learning of p-DNF formulas with malicious membership queries. Technical Report YALEU/DCS/TR- 1020, Yale University Department of Computer Science, March 1994.
	2	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	3	Dana Angluin , Mārtiņš Kriķis, Learning with malicious membership queries and exceptions (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.57-66, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181015]
	4	Dana Angluin , Donna K. Slonim, Randomly Fallible Teachers: Learning Monotone DNF with an Incomplete Membership Oracle, Machine Learning, v.14 n.1, p.7-26, Jan. 1994 [doi>10.1023/A:1022642604085]
	5	E. Baum. Neural net algorithms that learn in polynomial time from examples and queries. IEEE Transactions on Neural Networks, 2:5-19, 1991.
	6	Eric B. Baum, Polynomial time algorithms for learning neural nets, Proceedings of the third annual workshop on Computational learning theory, p.258-272, August 06-08, 1990, Rochester, New York, United States
	7	Avrim Blum , Ronald L. Rivest, Training a 3-node neural network in NP-complete, Advances in neural information processing systems 1, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
	8	Michael Frazier , Sally Goldman , Nina Mishra , Leonard Pitt, Learning from a consistently ignorant teacher, Proceedings of the seventh annual conference on Computational learning theory, p.328-339, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181170]
	9	Michael Frazier , Leonard Pitt, CLASSIC learning, Proceedings of the seventh annual conference on Computational learning theory, p.23-34, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.174994]
	10	S. Goldman and R, Sloan. Can PAC learning algorithms tolerate random noise? Technical Report WUCS-92- 25, Washington University Department of Computer Science, July 1992. To appear, Algorithmica.
	11	Sally A. Goldman , Michael J. Kearns , Robert E. Schapire, Exact identification of read-once formulas using fixed points of amplification functions, SIAM Journal on Computing, v.22 n.4, p.705-726, Aug. 1993 [doi>10.1137/0222047]
	12	Sally A. Goldman , H. David Mathias, Learning k-term DNF formulas with an incomplete membership oracle, Proceedings of the fifth annual workshop on Computational learning theory, p.77-84, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130394]
	13	Michael Kearns , Ming Li, Learning in the presence of malicious errors, SIAM Journal on Computing, v.22 n.4, p.807-837, Aug. 1993 [doi>10.1137/0222052]
	14	M. J. Kearns and R. E. Schapire. Efficient distributionfree learning of probabilistic concepts. In Proc. of the 31st Symposium on the Foundations of Comp. Sci., pages 382-391. IEEE Computer Society Press, Los Alamitos, CA, 1990.
	15	Philip D. Laird, Learning from good and bad data, Kluwer Academic Publishers, Norwell, MA, 1988
	16	K.J. Lang and E.B. Baum. Query learning can work poorly when a human oracle is used. In Proceedings of International Joint Conference on Neural Networks, IEEE, 1992.
	17	Nicholas Littlestone, Redundant noisy attributes, attribute errors, and linear-threshold learning using winnow, Proceedings of the fourth annual workshop on Computational learning theory, p.147-156, August 05-07, 1991, Santa Cruz, California, United States
	18	Yasubumi Sakakibara, On learning from queries and counterexamples in the presence of noise, Information Processing Letters, v.37 n.5, p.279-284, March 14, 1991 [doi>10.1016/0020-0190(91)90220-C]
	19	George Shackelford , Dennis Volper, Learning k-DNF with noise in the attributes, Proceedings of the first annual workshop on Computational learning theory, p.97-103, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	20	Robert Sloan, Types of noise in data for concept learning, Proceedings of the first annual workshop on Computational learning theory, p.91-96, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	21	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 [doi>10.1145/180139.181128]
	22	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]

CITED BY 5

	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
	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
	Stephen Kwek , Leonard Pitt, PAC learning intersections of halfspaces with membership queries (extended abstract), Proceedings of the ninth annual conference on Computational learning theory, p.244-254, June 28-July 01, 1996, Desenzano del Garda, Italy
	Nader H. Bshouty , Nadav Eiron , Eyal Kushilevitz, PAC learning with nasty noise, Theoretical Computer Science, v.288 n.2, p.255-275, 16 October 2002
	Sally A. Goldman , Stephen S. Kwek , Stephen D. Scott, Learning from examples with unspecified attribute values (extended abstract), Proceedings of the tenth annual conference on Computational learning theory, p.231-242, July 06-09, 1997, Nashville, Tennessee, United States