The strength of noninclusions for teams of finite learners (extended abstract)

ABSTRACT

In team learning one considers a set of n learning machines and requires that m out of n must be successful. Comparing the power of different teams of learning machines is a major topic of inductive inference. It is centered around the “inclusion problem”: When is an (m,n)-team more powerful than an (m′,n′)-team? In this paper we show that there are noninclusions of different strength for teams of finite learners (i.e., EX0-teams). We measure the strength of a noninclusion [m,n]EX0 ⊈ [m′n′]EX0-team. If any such A exists then we may take A = K where K is the halting problem, and for Popperian learners a K-oracle is also necessary. In contrast, for the noninclusion [29,49]EX0&nsube[2,4]EX0 weaker oracles suffice, and we characterize them as exactly those sets which are Turing-equivalent to a complete and consistent extension of Peano Arithmetic.

REFERENCES

• 1: Richard Beigel , William I. Gasarch , John Gill , James C. Owings, Terse, superterse, and verbose sets, Information and Computation, v.103 n.1, p.68-85, March 1993 [doi>10.1006/inco.1993.1014]
• 2: J. Case, C. Smith. Identification criteria for machine inductive inference.Theoretical Computer Science, 25:193-220, 1983.
• 3: Robert P. Daley , Bala Kalyanasundaram, Use of Reduction Arguments in Determining Popperian FIN-Type Learning Capabilities, Proceedings of the 4th International Workshop on Algorithmic Learning Theory, p.173-186, November 08-10, 1993
• 4: Robert Daley , Bala Kalyanasundaram , Mahendran Velauthapillai, Breaking the probability ½ barrier in FIN-type learning, Proceedings of the fifth annual workshop on Computational learning theory, p.203-217, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130408]
• 5: Robert P. Daley , Bala Kalyanasundaram , Mahendran Velauthapillai, The Power of Probabilism in Popperian FINite Learning (extended abstract), Proceedings of the International Workshop on Analogical and Inductive Inference, p.151-169, October 05-09, 1992
• 6: Robert Daley , Leonard Pitt , Mahendran Velauthapillai , Todd Will, Relations between probabilistic and team one-shot learners (extended abstract), Proceedings of the fourth annual workshop on Computational learning theory, p.228-239, August 05-07, 1991, Santa Cruz, California, United States
• 7: L. Fortnow, W. Gasarch, S. Jain, E. Kinber, M. Kummer, S. Kurtz, M. Pleszkoch, T. Slaman, R. Solovay, F. Stephan. Extremes in the degrees of inferability. To appear in: Annals of Pure and Applied Logic.
• 8: R. Freivalds. Finite identification of general recursive functions by probabilistic strategies. In: Fundamentals of Computation Theory-FUT'79, Ed.: L. Budach, pp. 138-145, Akademie Verlag, Berlin, 1979.
• 9: W. Gasarch. Impromptu talk at COLT'93.
• 10: Sanjay Jain , Arun Sharma, Finite learning by a “team”, Proceedings of the third annual workshop on Computational learning theory, p.163-177, August 06-08, 1990, Rochester, New York, United States
• 11: C. G. Jockusch, Jr. Degrees of functions with no fixed points. In: Logic, Methodology and Philosopher of Science VIII, pp. 191-201, Elsevier, Amsterdam, 1989.
• 12: Martin Kummer , Frank Stephan, On the structure of degrees of inferability, Proceedings of the sixth annual conference on Computational learning theory, p.117-126, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168319]
• 13: M. Kummer, F. Stephan. Inclusion problems in parallel learning and games. In: These Proceedings.
• 14: P. Odifreddi. Classical recursion theory. North- Holland, Amsterdam, 1989.
• 15: Leonard Pitt , Carl H. Smith, Probability and plurality for aggregations of learning machines, Information and Computation, v.77 n.1, p.77-92, April 1988 [doi>10.1016/0890-5401(88)90046-6]
• 16: Robert I. Soare, Recursively enumerable sets and degrees, Springer-Verlag New York, Inc., New York, NY, 1987
• 17: Mahendran Velauthapillai, Inductive inference with bounded number of mind changes, Proceedings of the second annual workshop on Computational learning theory, p.200-213, December 1989, Santa Cruz, California, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Theory, Verification