Hierarchies of probabilistic and team FIN-learning
A FIN-leaming 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   -leaming. (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(1), p(2) (Or team success ratios k(1)/n(1),k(2)/n(2)) 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 Kalanasundaram, Available from http://www.cs.pitt.edu/(similar to)daley /fin/fin.html, 1996). On the other hand, there are cut-points r which make simulation of FM(p2) by FIN   impossible whenever p(2) less than or equal to r < p(1). Cut-points above (10)/(21) are known (Daley and Kalyanasundaram, Available from http://www.cs.pitt.edu/(similar to)daley/fin/fin.html, 1996). We show that the problem for given k(1),n(1) to determine whether [k(1),n(1)]FIN subset of or equal to [k(2),n(2)]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(1),n(1)]FIN boolean AND [k(2),n(2)]FIN, unions [k(1),n(1)]FIN boolean OR [k(2),n(2)]FIN. and memberwise unions [k(1),n(1)]FIN + [k(2),n(2)]FIN, i.e. collections of all unions U-1 boolean OR U-2 where U-1 is an element of [k(1),n(1)]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. (C) 2001 Elsevier science B.V. All rights reserved.
team learning probabilistic learning inductive inference