PAC learning intersections of halfspaces with membership queries (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

PAC learning intersections of halfspaces with membership queries (extended abstract)

Full text

Pdf (1.16 MB)

Source

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

Desenzano del Garda, Italy

Pages: 244 - 254

Year of Publication: 1996

ISBN:0-89791-811-8

Authors

Stephen Kwek	Computer Science Department, University of Illinois, Urbana, IL
Leonard Pitt	Computer Science Department, University of Illinois, Urbana, IL

Sponsors

Univ degli Studi de Milano : Universite degli Studi de Milano
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/238061.238109 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.

	A93	Peter Auer, On-line learning of rectangles in noisy environments, Proceedings of the sixth annual conference on Computational learning theory, p.253-261, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168345]
	AKMW96	Peter Auer , Stephen Kwek , Wolfgang Maass , Manfred K. Warmuth, Learning of depth two neural networks with constant fan-in at the hidden nodes (extended abstract), Proceedings of the ninth annual conference on Computational learning theory, p.333-343, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238164]
	AL88	Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
	AHHP96	Howard Aizenstein , Tibor Hegedűs , Lisa Hellerstein , Leonard Pitt, Complexity theoretic hardness results for query learning, Computational Complexity, v.7 n.1, p.19-53, Jul. 1998 [doi>10.1007/PL00001593]
	B90A	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
	B90B	E. B. Baum, On learning a union of half spaces, Journal of Complexity, v.6 n.1, p.67-101, Mar. 1990 [doi>10.1016/0885-064X(90)90012-3]
	B90C	Eric B. Baum, A polynomial time algorithm that learns two hidden unit nets, Neural Computation, v.2 n.4, p.510-522, Winter 1990 [doi>10.1162/neco.1990.2.4.510]
	B91	E. Baum. Neural Net Algorithms that Learn in Polynomial Time from Examples and Queries. In IEEE Transactzon on Neural Networks, 2:5-19, 1991
	BCGS95	Avrim Blum , Prasad Chalasani , Sally A. Goldman , Donna K. Slonim, Learning with unreliable boundary queries, Proceedings of the eighth annual conference on Computational learning theory, p.98-107, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225310]
	BGM95	Nader H. Bshouty , Sally A. Goldman , H. David Mathias, Noise-tolerant parallel learning of geometric concepts, Proceedings of the eighth annual conference on Computational learning theory, p.345-352, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225340]
	BGMST96	Nader H. Bshouty , Sally A. Goldman , H. David Mathias , Subhash Suri , Hisao Tamaki, Noise-tolerant distribution-free learning of general geometric concepts, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.151-160, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237854]
	BEHW89	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]
	BM91	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
	BR89	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
	CM94	Zhixiang Chen , Wolfgang Maass, On-Line Learning of Rectangles and Unions of Rectangles, Machine Learning, v.17 n.2-3, p.201-223, Nov./Dec. 1994 [doi>10.1007/BF00993471]
	DG95	David P. Dobkin , Dimitrios Gunopulos, Concept learning with geometric hypotheses, Proceedings of the eighth annual conference on Computational learning theory, p.329-336, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225338]
	F95	Paul Fischer, More or less efficient agnostic learning of convex polygons, Proceedings of the eighth annual conference on Computational learning theory, p.337-344, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225339]
	FK96	P. Fischer and S. Kwek. Minimizing Disagreements for Geometric Regions, Using Dynamic Programming, with Applications in Machine Learning. In Electronic Archive for Computational Learnzng Theory Technical Report eC-TR-96-OOJ, 1996.
	H94	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]
	KSS92	Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward efficient agnostic learning, Proceedings of the fifth annual workshop on Computational learning theory, p.341-352, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130424]
	L88	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]
	LW91	P. Long and M. Warmuth. Composite Geometric Concepts and Polynomial Predictability. In Proc of the Fourth Workshop on Computational Learning Theory, pages 167-175. Morgan Kaufmann, San Mateo, CA, 1991.
	MT89	W. Maass and G. Turan. On the Complexity of Learning from Counterexamples. Proceedings of the 30th Annual IEEE symposium on the Foundations of Computer Science, pages 262-267, 1989.
	MT91	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
	MT94	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]
	PB90	Raymond Board , Leonard Pitt, On the necessity of Occam algorithms, Theoretical Computer Science, v.100 n.1, p.157-184, June 22, 1992 [doi>10.1016/0304-3975(92)90367-O]
	PR94	K. Pillaipakkamnatt and V. Raghavan. On the Limits of Proper Learnability of Subclasses of DNF Formula. Machine Learning, pages 1-29, 1(1994).
	PV89	Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
	PW90	Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]
	S87	V. Shevchenko, On Deciphering a Threshold Function of Many-Valued Logic, in Combznatorial-Algebraic Methods and their Applications, Grokii State University 1987, 155-163 (in Russian).
	S92	S. Skiena, Interactive Reconstruction via Geometric Probing. Proc of {EEE, vol 80, 1992, pp 1364-1382.
	V84	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]