PAC = PAExact and Other Equivalent Models in Learning

Vancouver, BC, Canada November 16-November 19

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181893

The 43rd Annual IEEE Symposium on Fou ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Nader H. Bshouty Articles by Dmitry Gavinsky

	ASCII Text	x
	Nader H. Bshouty, Dmitry Gavinsky, "PAC = PAExact and Other Equivalent Models in Learning," Foundations of Computer Science, Annual IEEE Symposium on, pp. 167, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002.

	BibTex	x
	@article{ 10.1109/SFCS.2002.1181893, author = {Nader H. Bshouty and Dmitry Gavinsky}, title = {PAC = PAExact and Other Equivalent Models in Learning}, journal ={Foundations of Computer Science, Annual IEEE Symposium on}, volume = {0}, year = {2002}, issn = {0272-5428}, pages = {167}, doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181893}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Foundations of Computer Science, Annual IEEE Symposium on TI - PAC = PAExact and Other Equivalent Models in Learning SN - 0272-5428 SP EP A1 - Nader H. Bshouty, A1 - Dmitry Gavinsky, PY - 2002 KW - null VL - 0 JA - Foundations of Computer Science, Annual IEEE Symposium on ER -

Nader H. Bshouty, Technion

Dmitry Gavinsky, Technion

The Probably Almost Exact model (PAExact) [BJT02] can be viewed as the Exact model relaxed so that:

1. The counterexamples to equivalence queries are distributionally drawn rather than adversarially chosen.

2. The output hypothesis is equal to the target with negligible error (1/w (poly) for any poly)

This model allows studying (Almost) Exact learnability of infinite classes and is in some sense analogous to the Exact-learning model for finite classes.

It is known that PAExact-learnable \Rightarrow PAC-learnable [BJT02]. In this paper we show that if a class is PAC-learnable (in polynomial time) then it is PAExact-learnable (in polynomial time). Therefore, PAExact-learnable = PAC-learnable.

It follows from this result that if a class is PAC-learnable then it is learnable in the Probabilistic Prediction model from examples with an algorithm that runs in polynomial time for each prediction (polynomial in log (the number of trials)) and that after polynomial number of mistakes achieves a hypothesis that predicts the target with probability 1 - 1/2^poly.

We also show that if a class is PAC-learnable in parallel then it is PAExact-learnable in parallel.

Those and other results mentioned in theintroduction answer the open problems posed in [B97, BJT02].

Citation:

Nader H. Bshouty, Dmitry Gavinsky, "PAC = PAExact and Other Equivalent Models in Learning," focs, pp.167, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.