A new heuristic to use least generalizations in ILP. Erdem, E. 1999. Unpublished draftN abstract bibtex The classical least generalization of a set C of clauses is a single clause. Such a unique clause is sometimes too general wrt some over-generality criterion, and this undesired situation may lead to memorization of the clauses in C at the end of learning process. Current ILP systems apply some heuristic algorithms to refine this situation where the classical definition of least generalization is used as an operator in a search space throughout the learning. Our approach to this problem is different: we use the classical least generalization of C in a more declarative way to narrow the search-space at the very beginning of the learning algorithm, that is, we define the concept of least generalization of a set C of clauses in a different way as being a minimal-sized set of clauses, each member of this set being the classical least generalization of some subset of C. The elements of these subsets are two by two compatible, in the sense that their classical least generalizations are not too general according to the over-generality criterion admissibility. We give an efficient algorithm for computing this re-defined concept, providing thus a new approach to disjunctive concept learning. We also prove a few theorems relating the problem-independent concept of compatibility with the problem-specific concept of admissibility: these theorems show how to speed up certain computations for these concepts. Finally, we outline an application of these considerations to a frequently occurring problem in the inductive synthesis of recursive (logic) programs, namely the induction of the operator combining the partial results (obtained through recursion) into the overall result.
@misc{unpub1,
author = {Esra Erdem},
title = { A new heuristic to use least generalizations in {ILP}},
note = {Unpublished draft},
urlN = {lgg.pdf},
year = {1999},
abstract = {The classical least generalization of a set C of clauses is a
single clause. Such a unique clause is sometimes too general wrt
some over-generality criterion, and this undesired situation may
lead to memorization of the clauses in C at the end of learning
process. Current ILP systems apply some heuristic algorithms to
refine this situation where the classical definition of least
generalization is used as an operator in a search space throughout
the learning.
Our approach to this problem is different: we use the classical
least generalization of C in a more declarative way to narrow the
search-space at the very beginning of the learning algorithm, that
is, we define the concept of least generalization of a set C of
clauses in a different way as being a minimal-sized set of clauses,
each member of this set being the classical least generalization of
some subset of C. The elements of these subsets are two by two
compatible, in the sense that their classical least generalizations
are not too general according to the over-generality criterion
admissibility. We give an efficient algorithm for computing this
re-defined concept, providing thus a new approach to disjunctive
concept learning. We also prove a few theorems relating the
problem-independent concept of compatibility with the
problem-specific concept of admissibility: these theorems show how
to speed up certain computations for these concepts. Finally, we
outline an application of these considerations to a frequently
occurring problem in the inductive synthesis of recursive (logic)
programs, namely the induction of the operator combining the
partial results (obtained through recursion) into the overall
result.
},
}
Downloads: 0
{"_id":{"_str":"53424e050e946d920a00066e"},"__v":1,"authorIDs":["5456f0758b01c81930000081","5df0b7a08367c8de010000ce","5df87bbedb7d9ddf01000044","5e4957a916841dde01000031","u493trvfaXuB4g9PZ"],"author_short":["Erdem, E."],"bibbaseid":"erdem-anewheuristictouseleastgeneralizationsinilp-1999","bibdata":{"bibtype":"misc","type":"misc","author":[{"firstnames":["Esra"],"propositions":[],"lastnames":["Erdem"],"suffixes":[]}],"title":"A new heuristic to use least generalizations in ILP","note":"Unpublished draft","urln":"lgg.pdf","year":"1999","abstract":"The classical least generalization of a set C of clauses is a single clause. Such a unique clause is sometimes too general wrt some over-generality criterion, and this undesired situation may lead to memorization of the clauses in C at the end of learning process. Current ILP systems apply some heuristic algorithms to refine this situation where the classical definition of least generalization is used as an operator in a search space throughout the learning. Our approach to this problem is different: we use the classical least generalization of C in a more declarative way to narrow the search-space at the very beginning of the learning algorithm, that is, we define the concept of least generalization of a set C of clauses in a different way as being a minimal-sized set of clauses, each member of this set being the classical least generalization of some subset of C. The elements of these subsets are two by two compatible, in the sense that their classical least generalizations are not too general according to the over-generality criterion admissibility. We give an efficient algorithm for computing this re-defined concept, providing thus a new approach to disjunctive concept learning. We also prove a few theorems relating the problem-independent concept of compatibility with the problem-specific concept of admissibility: these theorems show how to speed up certain computations for these concepts. Finally, we outline an application of these considerations to a frequently occurring problem in the inductive synthesis of recursive (logic) programs, namely the induction of the operator combining the partial results (obtained through recursion) into the overall result. ","bibtex":"@misc{unpub1,\nauthor = {Esra Erdem},\ntitle = { A new heuristic to use least generalizations in {ILP}},\nnote = {Unpublished draft},\nurlN = {lgg.pdf},\nyear = {1999},\nabstract = {The classical least generalization of a set C of clauses is a\nsingle clause. Such a unique clause is sometimes too general wrt\nsome over-generality criterion, and this undesired situation may\nlead to memorization of the clauses in C at the end of learning\nprocess. Current ILP systems apply some heuristic algorithms to\nrefine this situation where the classical definition of least\ngeneralization is used as an operator in a search space throughout\nthe learning.\n\nOur approach to this problem is different: we use the classical\nleast generalization of C in a more declarative way to narrow the\nsearch-space at the very beginning of the learning algorithm, that\nis, we define the concept of least generalization of a set C of\nclauses in a different way as being a minimal-sized set of clauses,\neach member of this set being the classical least generalization of\nsome subset of C. The elements of these subsets are two by two\ncompatible, in the sense that their classical least generalizations\nare not too general according to the over-generality criterion\nadmissibility. We give an efficient algorithm for computing this\nre-defined concept, providing thus a new approach to disjunctive\nconcept learning. We also prove a few theorems relating the\nproblem-independent concept of compatibility with the\nproblem-specific concept of admissibility: these theorems show how\nto speed up certain computations for these concepts. Finally, we\noutline an application of these considerations to a frequently\noccurring problem in the inductive synthesis of recursive (logic)\nprograms, namely the induction of the operator combining the\npartial results (obtained through recursion) into the overall\nresult.\n},\n}\n\n","author_short":["Erdem, E."],"key":"unpub1","id":"unpub1","bibbaseid":"erdem-anewheuristictouseleastgeneralizationsinilp-1999","role":"author","urls":{"N":"http://193.255.135.175/papers/lgg.pdf"},"downloads":0,"html":""},"bibtype":"misc","biburl":"http://193.255.135.175/papers/krrpublications.bib","downloads":0,"keywords":[],"search_terms":["new","heuristic","use","generalizations","ilp","erdem"],"title":"A new heuristic to use least generalizations in ILP","year":1999,"dataSources":["WeBGfagwiP89ve7hM"]}