A re-definition of least generalizations, and construction modes as a new declarative bias for ILP. Erdem, E. Technical Report BU-CEIS-9718, Bilkent University, 1997. ![A re-definition of least generalizations, and construction modes as a new declarative bias for ILP [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
N abstract bibtex The classical definition of the concept of least generalization of a clause set C is that it is a _single_ clause. Since such a unique clause is sometimes over-general, we re-define this concept 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 some over-generality criterion. We give an algorithm for computing this re-defined concept, providing thus a new approach to disjunctive concept learning. The criterion for over-generality is problem-specific. We introduce a new such criterion: two clauses are compatible, i.e., their classical least generalization is not over-general, if this least generalization is admissible wrt a construction mode capturing the required dataflow of each involved relation. We design a language for expressing such construction modes, and we define a powerful admissibility criterion. We also prove a few theorems relating the problem-independent concept of compatibility with the problem-specific concept of admissibility (our over-generality criterion): 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.
@techreport{ErdFle98,
author = {Esra Erdem},
title = {A re-definition of least generalizations, and construction modes as a new declarative bias for {ILP}},
institution = {Bilkent University},
year = {1997},
number = {BU-CEIS-9718},
urlN = {ErdFle98.pdf},
abstract = {The classical definition of the concept of least generalization of a clause
set C is that it is a _single_ clause. Since such a unique clause is
sometimes over-general, we re-define this concept 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 some over-generality criterion. We give
an algorithm for computing this re-defined concept, providing thus a new
approach to disjunctive concept learning.
The criterion for over-generality is problem-specific. We introduce a new
such criterion: two clauses are compatible, i.e., their classical least
generalization is not over-general, if this least generalization is
admissible wrt a construction mode capturing the required dataflow of each
involved relation. We design a language for expressing such construction
modes, and we define a powerful admissibility criterion. We also prove a
few theorems relating the problem-independent concept of compatibility with
the problem-specific concept of admissibility (our over-generality
criterion): 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":"53424e050e946d920a00067b"},"__v":1,"authorIDs":["5456f0758b01c81930000081","5df0b7a08367c8de010000ce","5df87bbedb7d9ddf01000044","5e4957a916841dde01000031","u493trvfaXuB4g9PZ"],"author_short":["Erdem, E."],"bibbaseid":"erdem-aredefinitionofleastgeneralizationsandconstructionmodesasanewdeclarativebiasforilp-1997","bibdata":{"bibtype":"techreport","type":"techreport","author":[{"firstnames":["Esra"],"propositions":[],"lastnames":["Erdem"],"suffixes":[]}],"title":"A re-definition of least generalizations, and construction modes as a new declarative bias for ILP","institution":"Bilkent University","year":"1997","number":"BU-CEIS-9718","urln":"ErdFle98.pdf","abstract":"The classical definition of the concept of least generalization of a clause set C is that it is a _single_ clause. Since such a unique clause is sometimes over-general, we re-define this concept 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 some over-generality criterion. We give an algorithm for computing this re-defined concept, providing thus a new approach to disjunctive concept learning. The criterion for over-generality is problem-specific. We introduce a new such criterion: two clauses are compatible, i.e., their classical least generalization is not over-general, if this least generalization is admissible wrt a construction mode capturing the required dataflow of each involved relation. We design a language for expressing such construction modes, and we define a powerful admissibility criterion. We also prove a few theorems relating the problem-independent concept of compatibility with the problem-specific concept of admissibility (our over-generality criterion): 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":"@techreport{ErdFle98,\nauthor = {Esra Erdem},\ntitle = {A re-definition of least generalizations, and construction modes as a new declarative bias for {ILP}},\ninstitution = {Bilkent University},\nyear = {1997},\nnumber = {BU-CEIS-9718},\nurlN = {ErdFle98.pdf},\nabstract = {The classical definition of the concept of least generalization of a clause\nset C is that it is a _single_ clause. Since such a unique clause is\nsometimes over-general, we re-define this concept as being a minimal-sized\n_set_ of clauses, each member of this set being the classical least\ngeneralization of some subset of C. The elements of these subsets are two\nby two compatible, in the sense that their classical least generalizations\nare not too general according to some over-generality criterion. We give\nan algorithm for computing this re-defined concept, providing thus a new\napproach to disjunctive concept learning.\n\nThe criterion for over-generality is problem-specific. We introduce a new\nsuch criterion: two clauses are compatible, i.e., their classical least\ngeneralization is not over-general, if this least generalization is\nadmissible wrt a construction mode capturing the required dataflow of each\ninvolved relation. We design a language for expressing such construction\nmodes, and we define a powerful admissibility criterion. We also prove a\nfew theorems relating the problem-independent concept of compatibility with\nthe problem-specific concept of admissibility (our over-generality\ncriterion): these theorems show how to speed up certain computations for\nthese concepts. Finally, we outline an application of these considerations\nto a frequently occurring problem in the inductive synthesis of recursive\n(logic) programs, namely the induction of the operator combining the\npartial results (obtained through recursion) into the overall result.},\n\n}\n\n","author_short":["Erdem, E."],"key":"ErdFle98","id":"ErdFle98","bibbaseid":"erdem-aredefinitionofleastgeneralizationsandconstructionmodesasanewdeclarativebiasforilp-1997","role":"author","urls":{"N":"http://193.255.135.175/papers/ErdFle98.pdf"},"downloads":0,"html":""},"bibtype":"techreport","biburl":"http://193.255.135.175/papers/krrpublications.bib","downloads":0,"keywords":[],"search_terms":["definition","generalizations","construction","modes","new","declarative","bias","ilp","erdem"],"title":"A re-definition of least generalizations, and construction modes as a new declarative bias for ILP","year":1997,"dataSources":["WeBGfagwiP89ve7hM"]}