PACS, simple-PAC and query learning
We study a distribution dependent form of PAC learning that uses probability distributions related to Kolmogorov complexity: the PACS model. We relate the query model and the simple-PAC model with PACS. Using these relationships and previous results in those models we are able to get alternative proofs to all known results in the PACS model in a systematic way. (C) 2000 Published by Elsevier Science B.V. All rights reserved.
query learning pac learning kolmogorov complexity theory of computation