| Abstract |
|
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].
|
 Additional Information
|
Citation:
Nader H. Bshouty, Dmitry Gavinsky,
"PAC = PAExact and Other Equivalent Models in Learning,"
focs,
p. 167,
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02),
2002
|
