Hierarchies of probabilistic and team learning
Kalvis Apsı̄tis, Carl H. Smith · 1998
An inductive inference machine M receives successive values of a recursive function f and tries to learn a program for f. This model has two modifications: (1) A probabilistic machine M flips fair coins and learns a function with probability at least p, (2) A (k, n) team: a collection of n machines receiving values of the same function f so that at least k of these machines learn f. For each particular learning type there is a hierarchy of probabilistic and team learning powers as parameters p, k, n vary. For one-shot learning FIN, this hierarchy was not completely known (DKV92, DK96). This thesis shows that for FIN and for given $k\sb{i}, n\sb{i}$n$\sb{i}$ the problem to determine whether any $\lbrack k\sb1, n\sb1\rbrack$ team can be simulated by an appropriate $\lbrack k\sb2, n\sb2\rbrack$ team is decidable. Using team matrices we can also compare the learning power of intersections, team compositions, pairwise unions and other derivations of the usual teams (k, n).