jmlr jmlr2005 jmlr2005-59 jmlr2005-59-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Judy Goldsmith, Robert H. Sloan
Abstract: A revision algorithm is a learning algorithm that identifies the target concept, starting from an initial concept. Such an algorithm is considered efficient if its complexity (in terms of the measured resource) is polynomial in the syntactic distance between the initial and the target concept, but only polylogarithmic in the number of variables in the universe. We give efficient revision algorithms in the model of learning with equivalence and membership queries. The algorithms work in a general revision model where both deletion and addition revision operators are allowed. In this model one of the main open problems is the efficient revision of Horn formulas. Two revision algorithms are presented for special cases of this problem: for depth-1 acyclic Horn formulas, and for definite Horn formulas with unique heads. Keywords: theory revision, Horn formulas, query learning, exact learning, computational learning theory
Dana Angluin. Learning propositional Horn sentences with hints. Technical Report YALEU/DCS/RR-590, Department of Computer Science, Yale University, December 1987a. Dana Angluin. Learning regular sets from queries and counterexamples. Inform. Comput., 75(2): 87–106, November 1987b. Dana Angluin. Queries and concept learning. Machine Learning, 2(4):319–342, April 1988. Dana Angluin, Michael Frazier, and Leonard Pitt. Learning conjunctions of Horn clauses. Machine Learning, 9:147–164, 1992. Krzysztof R. Apt, Howard Blair, and Adrian Walker. Towards a theory of declarative knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 193–216. Morgan Kaufmann, Los Altos, CA, 1988. Hiroki Arimura. Learning acyclic first-order Horn sentences from entailment. In Algorithmic Learning Theory, 8th International Workshop, ALT ’97, Sendai, Japan, October 1997, Proceedings, volume 1316 of Lecture Notes in Artificial Intelligence, pages 432–445. Springer, 1997. Peter Auer and Philip M. Long. Structural results about on-line learning models with and without queries. Machine Learning, 36(3):147–181, 1999. Avrim Blum, Lisa Hellerstein, and Nick Littlestone. Learning in the presence of finitely or infinitely many irrelevant attributes. J. of Comput. Syst. Sci., 50(1):32–40, 1995. Earlier version in 4th COLT, 1991. Avrim Blum, Jeffrey Jackson, Tuomas Sandholm, and Martin Zinkevich. Preference elicitation and query learning. Journal of Machine Learning Research, 5:649–667, 2004. Nader Bshouty. Exact learning Boolean function via the monotone theory. Information and Computation, 123:146–153, 1995. Nader Bshouty and Lisa Hellerstein. Attribute-efficient learning in query and mistake-bound models. J. of Comput. Syst. Sci., 56(3):310–319, 1998. Ashok K. Chandra and David Harel. Horn clause queries and generalizations. Journal of Logic Programming, 2:1–15, 1985. Jignesh Umesh Doshi. Revising Horn formulas. Master’s thesis, Dept. of Computer Science, University of Kentucky, 2003. 1937 G OLDSMITH AND S LOAN Judy Goldsmith, Robert H. Sloan, and Gy¨ rgy Tur´ n. Theory revision with queries: DNF formulas. o a Machine Learning, 47(2/3):257–295, 2002. Judy Goldsmith, Robert H. Sloan, Bal´ zs Sz¨ r´ nyi, and Gy¨ rgy Tur´ n. New revision algorithms. a oe o a In Algorithmic Learning Theory, 15th International Conference, ALT 2004, Padova, Italy, October 2004, Proceedings, volume 3244 of Lecture Notes in Artificial Intelligence, pages 395–409. Springer, 2004a. Judy Goldsmith, Robert H. Sloan, Bal´ zs Sz¨ r´ nyi, and Gy¨ rgy Tur´ n. Theory revision with a oe o a queries: Horn, read-once, and parity formulas. Artificial Intelligence, 156:139–176, 2004b. Russell Greiner. The complexity of theory revision. Artificial Intelligence, 107:175–217, 1999a. Russell Greiner. The complexity of revising logic programs. J. Logic Programming, 40:273–298, 1999b. Peter L. Hammer and Alexander Kogan. Quasi-acyclic propositional Horn knowledge bases: optimal compression. IEEE Trans. Knowl. Data Eng., 7:751–762, 1995. Moshe Koppel, Ronen Feldman, and Alberto Maria Segre. Bias-driven revision of logical domain theories. Journal of Artificial Intelligence Research, 1:159–208, 1994. Evelina Lamma, Fabrizio Riguzzi, and Lu´s Moniz Pereira. Belief revision via Lamarckian evoluı tion. New Generation Computing, 21:247–275, 2003. Raymond J. Mooney. A preliminary PAC analysis of theory revision. In Thomas Petsche, editor, Computational Learning Theory and Natural Learning Systems, volume III: Selecting Good Models, chapter 3, pages 43–53. MIT Press, 1995. Dirk Ourston and Raymond J. Mooney. Theory refinement combining analytical and empirical methods. Artificial Intelligence, 66:273–309, 1994. Bradley L. Richards and Raymond J. Mooney. Automated refinement of first-order Horn-clause domain theories. Machine Learning, 19:95–131, 1995. Robert H. Sloan, Bal´ zs Sz¨ r´ nyi, and Gy¨ rgy Tur´ n. Projective DNF formulae and their revision. a oe o a In Learning Theory and Kernel Machines, 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, volume 2777 of Lecture Notes in Artificial Intelligence, pages 625–639. Springer, 2003. Geoffrey G. Towell and Jude W. Shavlik. Extracting refined rules from knowledge-based neural networks. Machine Learning, 13:71–101, 1993. Allen Van Gelder. Negation as failure using tight derivations for general logic programs. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 149–176. Morgan Kaufmann, Los Altos, CA, 1988. Stefan Wrobel. First order theory refinement. In L. De Raedt, editor, Advances in ILP, pages 14–33. IOS Press, Amsterdam, 1995. Stefan Wrobel. Concept Formation and Knowledge Revision. Kluwer, 1994. 1938