Hierarchies of probabilistic and team FIN-learning
Authors: Andris Ambainis^{1}, Kalvis Apsitis^{2},
Rusins Freivalds^{3} and Carl H. Smith^{4}
Source: Theoretical Computer Science Vol. 261, Issue 1, 17 June 2001, pp. 91-117. Abstract. 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_{1}, p_{2} (or team success ratios k_{1}/n_{1}, k_{2}/n_{2}) re 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_{2}> by FIN<p_{1}> impossible whenever p_{2} r < p_{1}. 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_{1},n_{1}]FIN _{} [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 [k_{2},n_{2}]FIN, unions [k_{1},n_{1}]FIN _{} [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} _{} U_{2} 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.
^{1}Part of this work done at the University of Latvia, supported by Latvia Science Council Grant 98.0282. ^{2}Part of this work done at the University of Maryland. ^{3}Supported by Latvia Science Council Grant 96.0282. ^{4}Supported in part by National Science Foundation Grant CCR-9732692. |
©Copyright 2001 Elsevier Science