Breaking the probability ½ barrier in FIN-type learning

ABSTRACT

We show that for every probabilistic FIN-type learner with success ratio greater than 24/49, there is another probabilistic FIN-type learner with success ratio 1/2 that simulates the former. We will also show that this simulation result is tight. We obtain as a consequence of this work a characterization of FIN-type team learning with success ratio between 24/49 and 1/2. We conjecture that the learning capabilities of probabilistic FIN-type learners for probabilities beginning at probability 1/2 are delimited by the sequence 8n/17n-2 for n > 2, which has an accumulation point at 8/17.

REFERENCES

• DK92a: R. Daley and B. Kalyanasundaram. Capabilities of probabilistic learners with bounded mind changes. Submitted for Publication, 1992.
• DK92b: Robert P. Daley , Bala Kalyanasundaram, Probabilistic and Pluralistic Learners with Mind Changes, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.218-226, August 24-28, 1992
• DKV92: 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
• DPVW91: 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
• Fre79: R. Freivalds. Finite Identification of General Recursive Functions by Probabilistic Strategies. Akademie Verlag, Berlin, 1979.
• Gol67: E.M. Gold. Language identification in the limit. Information and Control, 10:447-474, 1967.
• JS90: 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
• Pit89: L. Pitt, Probabilistic inductive inference, Journal of the ACM (JACM), v.36 n.2, p.383-433, April 1989 [doi>10.1145/62044.62053]
• PS88: 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]
• Smi82: Carl H. Smith, The Power of Pluralism for Automatic Program Synthesis, Journal of the ACM (JACM), v.29 n.4, p.1144-1165, Oct. 1982 [doi>10.1145/322344.322356]
• Vel89: 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:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

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

General Terms:
Theory, Verification