Hierarchies of probabilistic and team FIN-learning

A FIN-learning machine M receives successive values of the function f it is learning and at some moment outputs a conjecture which should be a correct index of f. FIN learning has two extensions: (1) If M flips fair coins and learns a function with certain probability p, we have FIN〈p〉-learning. (2) When n machines simultaneously try to learn the same function f and at least k of these machines output correct indices of f, we have learning by a [k,n]FIN team. Sometimes a team or a probabilistic learner can simulate another one, if their probabilities p ₁, p ₂ (or team success ratios k ₁/n ₁, k ₂/n ₂) are close enough (Daley et al., in: Valiant, Waranth (Eds.), Proc. 5th Annual Workshop on Computational Learning Theory, ACM Press, New York, 1992, pp. 203-217; Daley and Kalyanasundaram, Available from http://www.cs.pitt.edu/̃daley/fin/fin.html, 1996). On the other hand, there are cut-points r which make simulation of FIN〈p ₂〉 by FIN〈p ₁〉 impossible whenever p ₂ ≤ r < p ₁. Cut-points above 10/21 are known (Daley and Kalyanasundaram, Available from http://www.cs.pitt.edu/̃daley/fin/fin.html, 1996). We show that the problem for given k _i, n _i to determine whether [k ₁, n ₁]FIN ⊆ [k ₂, n ₂]FIN is algorithmically solvable. The set of all FIN cut-points is shown to be well ordered and recursive. Asymmetric teams are introduced and used as both a tool to obtain these results, and are of interest in themselves. The framework of asymmetric teams allows us to characterize intersections [k ₁, n ₁]FIN ∩ [k ₂, n ₂]FIN, unions [k ₁, n ₁]FIN ∪ [k ₂, n ₂]FIN, and memberwise unions [k ₁, n ₁]FIN + [k ₂, n ₂]FIN, i.e. collections of all unions U ₁ ∪ U ₂ where U _i ∈ [k _i, n _i]FIN. Hence, we can compare the learning power of traditional FIN-teams [k, n]FIN as well as all kinds of their set-theoretic combinations.