Relative least general generalization, proposed by Plotkin, is widely used for generalizing first-order clauses in inductive logic programming, and this paper describes an extension of Plotkin's work to allow vari...
详细信息
Relative least general generalization, proposed by Plotkin, is widely used for generalizing first-order clauses in inductive logic programming, and this paper describes an extension of Plotkin's work to allow various computation domains: Herbrand Universe, sets, numerical data, etc. The theta-subsumption in Plotkin's framework is replaced by a more general constraint-based subsumption. Since this replacement is analogous to that of unification by constraint solving in Constraint logicprogramming, the resultant method can be viewed as a Constraint logicprogramming version of relative least general generalization. Constraint-based subsumption, however, leads to a search on an intractably large hypothesis space. We therefore provide meta-level constraints that are used as semantic bias on the hypothesis language. The constraints functional dependency and monotonicity are introduced by analyzing clausal relationships. Finally, the advantage of the proposed method is demonstrated through a simple layout problem, where geometric constraints used in space planning tasks are produced automatically.
The task of predicate invention in inductive logic programming is to extend the hypothesis language with new predicates if the vocabulary given initially is insufficient for the learning task. However, whether predica...
详细信息
The task of predicate invention in inductive logic programming is to extend the hypothesis language with new predicates if the vocabulary given initially is insufficient for the learning task. However, whether predicate invention really helps to make learning succeed in the extended language depends on the language bias currently employed. In this paper, we investigate for which commonly employed language biases predicate invention is an appropriate shift operation. We prove that for some restricted languages predicate invention does not help when the learning task fails and we characterize the languages for which predicate invention is useful. We investigate the decidability of the bias shift problem for these languages and discuss the capabilities of predicate invention as a bias shift operation.
Several applications of inductive logic programming (ILP) are presented. These belong to various areas of engineering, including mechanical, environmental, software, and dynamical systems engineering. The particular a...
详细信息
Several applications of inductive logic programming (ILP) are presented. These belong to various areas of engineering, including mechanical, environmental, software, and dynamical systems engineering. The particular applications are finite element mesh design, biological classification of river water quality, data reification, inducing program invariants, learning qualitative models of dynamic systems, and learning control rules for dynamic systems. A number of other applications are briefly mentioned. Finally, a discussion of the advantages and disadvantages of ILP as compared to other approaches to machine learning is given.
FOIL is a first-order learning system that uses information in a collection of relations to construct theories expressed in a dialect of Prolog. This paper provides an overview of the principal ideas and methods used ...
详细信息
FOIL is a first-order learning system that uses information in a collection of relations to construct theories expressed in a dialect of Prolog. This paper provides an overview of the principal ideas and methods used in the current version of the system, including two recent additions. We present examples of tasks tackled by FOIL and of systems that adapt and extend its approach.
The finite element method (FEM) is the most successful numerical method, that is used extensively by engineers to analyse stresses and deformations in physical structures. These structures should be represented as a f...
详细信息
The finite element method (FEM) is the most successful numerical method, that is used extensively by engineers to analyse stresses and deformations in physical structures. These structures should be represented as a finite element mesh. Defining an appropriate geometric mesh model that ensures low approximation errors and avoids unnecessary computational overheads is a very difficult and time consuming task. It is the major bottleneck in the FEM analysis process. The inductive logic programming system GOLEM has been employed to construct the rules for deciding about the appropriate mesh resolution. Five cylindrical mesh models have been used as a source of training examples. The evaluation of the resulting knowledge base shows that conditions in the domain are well represented by the rules, which specify the required number of the finite elements on the edges of the structures to be analysed using FEM. A comparison between the results obtained by this knowledge base and conventional mesh generation techniques confirms that the application of inductive logic programming is an effective approach to solving the problem of mesh design.
A central problem in inductive logic programming is theory evaluation. Without some sort of preference criterion, any two theories that explain a set of examples are equally acceptable. This paper presents a scheme fo...
详细信息
A central problem in inductive logic programming is theory evaluation. Without some sort of preference criterion, any two theories that explain a set of examples are equally acceptable. This paper presents a scheme for evaluating alternative inductive theories based on an objective preference criterion. It strives to extract maximal redundancy from examples, transforming structure into randomness. A major strength of the method is its application to learning problems where negative examples of concepts are scarce or unavailable. A new measure called model complexity is introduced, and its use is illustrated and compared with a proof complexity measure on relational learning tasks. The complementarity of model and proof complexity parallels that of model and proof-theoretic semantics. Model complexity, where applicable, seems to be an appropriate measure for evaluating inductivelogic theories.
Two representation changes are presented: the first one, called flattening, transforms a first-order logic program with function symbols into an equivalent logic program without function symbols;the second one, called...
详细信息
Two representation changes are presented: the first one, called flattening, transforms a first-order logic program with function symbols into an equivalent logic program without function symbols;the second one, called saturation, completes an example description with relevant information with respect to both the example and available background knowledge. The properties of these two representation changes are analyzed as well as their influence on a generalization algorithm that takes a single example as input.
inductive logic programming (ILP) involves the synthesis of logic programs from examples. In terms of scientific theory formation ILP systems define observational predicates in terms of a set of theoretical predicates...
详细信息
inductive logic programming (ILP) involves the synthesis of logic programs from examples. In terms of scientific theory formation ILP systems define observational predicates in terms of a set of theoretical predicates. However, certain basic theorems indicate that with an inadequate theoretical vocabulary this is not always possible. Predicate invention is the augmentation of a given theoretical vocabulary to allow finite axiomatization of the observational predicates. New theoretical predicates need to be chosen from a well-defined universe of such predicates. In this paper a partial order of utilization is described over such a universe. This ordering is a special case of a logical translation. The notion of utilization allows the definition of an equivalence relationship over new predicates. In a manner analogous to Plotkin, clause refinement is defined relative to given background knowledge and a universe of new predicates. It is shown that relative least clause refinement is defined and unique whenever there exists a relative least general generalization of a set of clauses. Results of a preliminary implementation of this approach are given.
Concept learning from examples in first-order languages has been widely studied recently. Specifically, many systems that integrate inductive learning and explanation-based learning have been proposed. However, concep...
详细信息
Concept learning from examples in first-order languages has been widely studied recently. Specifically, many systems that integrate inductive learning and explanation-based learning have been proposed. However, concept learning is only a subproblem of the problem of knowledge base (which is referred to as a theory in first-order logic) revision. This is mainly because concept learning methods utilize background knowledge without regard to whether the knowledge is perfect or imperfect, while a knowledge base revision system should revise the knowledge base to be consistent with all environmental changes. This paper presents a real theory revision method that guarantees the revised theory to be correct on all given examples. As a consequence, the problem of concept learning is also solved through the proposed method. The proposed method is a two-phase approach. In the first phase, the input theory is generalized to cover all positive examples. Theoretically, this can be done by existing concept learning systems. The second phase then specializes the theory to exclude negative examples. The specialization must not cause excessive exclusion of covered positive examples. The paper focuses on designing such a specialization algorithm. Experimental results show that the proposed algorithm can mitigate the over-specialization problem.
Most current applications of inductive learning in databases take place in the context of a single extensional relation. This paper puts inductive learning in the context of a set of relations defined either extension...
详细信息
Most current applications of inductive learning in databases take place in the context of a single extensional relation. This paper puts inductive learning in the context of a set of relations defined either extensionally or intentionally in the framework of deductive databases. It presents LINUS, an inductive logic programming system that induces virtual relations from example positive and negative tuples and already defined relations in a deductive database. Based on the idea of transforming the problem of learning relations to attribute-value form, it incorporates several attribute-value learning systems. As the latter handle noisy data successfully, LINUS is able to learn relations from real life noisy databases. The paper illustrates the use of LINUS for learning virtual relations and then presents a study of its performance on noisy data.
暂无评论