Probabilistic and Team PFIN-Type Learning: General Properties
Abstract
We consider the probability hierarchy for Popperian FINite learning and study the general properties of this hierarchy. We prove that the probability hierarchy is decidable, i.e. there exists an algorithm that receives p"1 and p"2 and answers whether PFIN-type learning with the probability of success p"1 is equivalent to PFIN-type learning with the probability of success p"2. To prove our result, we analyze the topological structure of the probability hierarchy. We prove that it is well-ordered in descending ordering and order-equivalent to ordinal @e"0. This shows that the structure of the hierarchy is very complicated. Using similar methods, we also prove that, for PFIN-type learning, team learning and probabilistic learning are of the same power.
Cite
Text
Ambainis. "Probabilistic and Team PFIN-Type Learning: General Properties." Annual Conference on Computational Learning Theory, 1996. doi:10.1145/238061.238087Markdown
[Ambainis. "Probabilistic and Team PFIN-Type Learning: General Properties." Annual Conference on Computational Learning Theory, 1996.](https://mlanthology.org/colt/1996/ambainis1996colt-probabilistic/) doi:10.1145/238061.238087BibTeX
@inproceedings{ambainis1996colt-probabilistic,
title = {{Probabilistic and Team PFIN-Type Learning: General Properties}},
author = {Ambainis, Andris},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1996},
pages = {157-168},
doi = {10.1145/238061.238087},
url = {https://mlanthology.org/colt/1996/ambainis1996colt-probabilistic/}
}