Learning from a consistently ignorant teacher

ABSTRACT

One view of computational learning theory is that of a learner acquiring the knowledge of a teacher. We introduce a formal model of learning capturing the idea that teachers may have gaps in their knowledge. The goal of the learner is still to acquire the knowledge of the teacher, but now the learner must also identify the gaps. This is the notion of learning from a consistently ignorant teacher. We consider the impact of knowledge gaps on learning, for example, monotone DNF and d-dimensional boxes, and show that learning is still possible. Negatively, we show that knowledge gaps make learning conjunctions of Horn clauses as hard as learning DNF. We also present general results describing when known learning algorithms can be used to obtain learning algorithms using a consistently ignorant teacher.

REFERENCES

• 1: Howard Aizenstein, Lisa Hellerstein, and Leonard Pitt. Read-thrice DNF is hard to learn with membership and equivalence queries. In 8$nd Annual Symposium on Foundations of Computer Science, pages 523-532, October 1992.
• 2: Howard Aizenstein , Leonard Pitt, Exact learning of read-twice DNF formulas (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.170-179, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185366]
• 3: Dana Angluin. Learning k-term DNF formulas using queries and counterexamples. Technical Report YALEU/DCS/RR-559, Yale University, August 1987.
• 4: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• 5: Dana Angluin, Negative Results for Equivalence Queries, Machine Learning, v.5 n.2, p.121-150, Jun. 1990 [doi>10.1023/A:1022692615781]
• 6: Dana Anghin. Exact learning of t*-DNF formulas with malicious membership queries. Technical Report YALEU/DCS/TR-1020, Yale University, March 1994.
• 7: Dana Angluin , Michael Frazier , Leonard Pitt, Learning Conjunctions of Horn Clauses, Machine Learning, v.9 n.2-3, p.147-164, July 1992 [doi>10.1007/BF00992675]
• 8: Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning read-once formulas with queries, Journal of the ACM (JACM), v.40 n.1, p.185-210, Jan. 1993 [doi>10.1145/138027.138061]
• 9: Dana Angluin , Michael Kharitonov, When won't membership queries help?, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.444-454, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103420]
• 10: Dana Angluin , Mārtiņš Kriķis, Learning with malicious membership queries and exceptions (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.57-66, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181015]
• 11: Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
• 12: Dana Angluin , Donna K. Slonim, Randomly Fallible Teachers: Learning Monotone DNF with an Incomplete Membership Oracle, Machine Learning, v.14 n.1, p.7-26, Jan. 1994 [doi>10.1023/A:1022642604085]
• 13: Dana Angluin and Leslie G. Valiant. Past probabilistic algorithms for Hamiltonian circuits and matchings. Journal of Computer and System Sciences, 18(2):155- 193, April 1979.
• 14: Avrim Blum , Steven Rudich, Fast learning of k-term DNF formulas with queries, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.382-389, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129748]
• 15: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 16: Nader H. Bshouty. Exact Learning via the Monotone Theory. In 3~th Annual Symposium on Foundations of Computer Science, pages 302-311, November 1993.
• 17: Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning arithmetic read-once formulas, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.370-381, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129747]
• 18: Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning Boolean read-once formulas with arbitrary symmetric and constant fan-in gates, Proceedings of the fifth annual workshop on Computational learning theory, p.1-15, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130386]
• 19: Zhixiang Chen, Learning unions of two rectangles in the plane with equivalence queries, Proceedings of the sixth annual conference on Computational learning theory, p.243-252, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168342]
• 20: Zhixiang Chen and Steven Homer. Fast learning unions of rectangles with queries. Unpublished manuscript, July 1993.
• 21: Zhixiang Chen , Wolfgang Maass, On-line learning of rectangles, Proceedings of the fifth annual workshop on Computational learning theory, p.16-28, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130387]
• 22: Michael Frazier and Leonard Pitt. Learning from entailments: an application to propositional Horn sentences. In Machine Learning Proceedings o/the Tenth International Conference, pages 120-127, June 1993.
• 23: Michael Frazier , Leonard Pitt, CLASSIC learning, Proceedings of the seventh annual conference on Computational learning theory, p.23-34, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.174994]
• 24: Paul W. Goldberg , Sally A. Goldman , H. David Mathias, Learning unions of boxes with membership and equivalence queries, Proceedings of the seventh annual conference on Computational learning theory, p.198-207, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181102]
• 25: Sally A. Goldman , Michael J. Kearns , Robert E. Schapire, Exact identification of read-once formulas using fixed points of amplification functions, SIAM Journal on Computing, v.22 n.4, p.705-726, Aug. 1993 [doi>10.1137/0222047]
• 26: Sally A. Goldman and Robert H. Sloan. Can PAC learning algorithms tolerate random attribute noise? Technical Report WUCS-92-25, Washington University, Department of Computer Science, July 1992. To appear in Algorthmica.
• 27: Thomas R. Hancock, Learning 2u DNF formulas and ku decision trees, Proceedings of the fourth annual workshop on Computational learning theory, p.199-212, August 05-07, 1991, Santa Cruz, California, United States
• 28: David Haussler. Generalizing the PAC model: sample size bounds from metric dimension-based uniform convergence results. In 30th Annual Symposium on Foundations of Computer Science, pages 40-45, October 1989.
• 29: David Haussler , Michael Kearns, Equivalence of models for polynomial learnability, Information and Computation, v.95 n.2, p.129-161, Dec. 1991 [doi>10.1016/0890-5401(91)90042-Z]
• 30: Michael Kearns , Ming Li, Learning in the presence of malicious errors, SIAM Journal on Computing, v.22 n.4, p.807-837, Aug. 1993 [doi>10.1137/0222052]
• 31: M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
• 32: Michael J. Kearns and Robert E. Schapire. Efficient distribution-free learning of probabilistic concepts. In 31st Annual Symposium on Foundations o/Computer Science, pages 382-391, 1990.
• 33: Philip D. Laird, Learning from good and bad data, Kluwer Academic Publishers, Norwell, MA, 1988
• 34: Nicholas Littlestone, Redundant noisy attributes, attribute errors, and linear-threshold learning using winnow, Proceedings of the fourth annual workshop on Computational learning theory, p.147-156, August 05-07, 1991, Santa Cruz, California, United States
• 35: Philip M. Long , Manfred K. Warmuth, Composite geometric concepts and polynomial predictability, Proceedings of the third annual workshop on Computational learning theory, p.273-287, August 06-08, 1990, Rochester, New York, United States
• 36: Thomas Mitchell. Generalization as Search. Artificial Intelligence, 18:203-226, 1982.
• 37: Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]
• 38: Yasubumi Sakakibara, On learning from queries and counterexamples in the presence of noise, Information Processing Letters, v.37 n.5, p.279-284, March 14, 1991 [doi>10.1016/0020-0190(91)90220-C ]
• 39: George Shackelford , Dennis Volper, Learning k-DNF with noise in the attributes, Proceedings of the first annual workshop on Computational learning theory, p.97-103, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 40: Robert Sloan, Types of noise in data for concept learning, Proceedings of the first annual workshop on Computational learning theory, p.91-96, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 41: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

INDEX TERMS

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

General Terms:
Algorithms, Theory, Verification