loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
PAC = PAExact and Other Equivalent Models in Learning
Vancouver, BC, Canada
November 16-November 19
ISBN: 0-7695-1822-2
ASCII Text
x 
 
Nader H. Bshouty, Dmitry Gavinsky, "PAC = PAExact and Other Equivalent Models in Learning," Foundations of Computer Science, IEEE Annual 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, IEEE Annual 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, IEEE Annual 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, IEEE Annual 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/2poly.

    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
    Usage of this product signifies your acceptance of the Terms of Use.