6533b860fe1ef96bd12c3956

RESEARCH PRODUCT

Hierarchies of probabilistic and team FIN-learning

subject

description

AbstractA 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 p1,p2 (or team success ratios k1/n1,k2/n2) 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〈p2〉 by FIN〈p1〉 impossible whenever p2⩽r<p1. Cut-points above 1021 are known (Daley and Kalyanasundaram, Available from http://www.cs.pitt.edu/ ̃daley/fin/fin.html, 1996). We show that the problem for given ki,ni to determine whether [k1,n1]FIN⊆[k2,n2]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 [k1,n1]FIN∩[k2,n2]FIN, unions [k1,n1]FIN∪[k2,n2]FIN, and memberwise unions [k1,n1]FIN+[k2,n2]FIN, i.e. collections of all unions U1∪U2 where Ui∈[ki,ni]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.