Inclusion Problems in Parallel Learning and Games

摘要

In a recent paper Kinber, Smith, Velauthapillai, and Wiehagen introduced a new notion of “parallel learning.” They call a setSof functions (m, n)-learnableif there is a learning machine which for any n-tuple of pairwise distinct functions fromSlearns at leastmfunctions correctly from examples of their behavior after seeing some finite amount of input. One of the basic open questions in this area is the “inclusion problem,” i.e., the question for whichm,n,h,k, every (m, n)-learnable class is also (h, k)-learnable. In this paper we develop a general approach to solve this problem. The idea is to associate with eachm,n,h,kin a uniform way a finite 2-player game such that the first player has a winning strategy in this game iff every (m, n)-learnable class is (h, k)-learnable. In this way we take the recursion theoretic disguise off the problem and isolate its combinatorial core. We also explicitly characterize the “strength” of each particular noninclusion by the complexity of an oracle which is needed to overcome it. It turns out that there are exactly three different types of noninclusions.