One of the most important issues in instruction-level parallelism (ILP) processors involves the boosting of instructions across conditional branches for speculative execution. A compiler scheduling technique named LES...
详细信息
One of the most important issues in instruction-level parallelism (ILP) processors involves the boosting of instructions across conditional branches for speculative execution. A compiler scheduling technique named LESS with a renaming function is proposed for the elimination of hazards that incorrectly overwrite a value when the branch is incorrectly predicted during speculative execution. The hardware implementation for this method is relatively simple and rather efficient. Simulation results show that the speedups achieved by LESS are better than other existing methods. For example, under the superscalar execution model, with an issue rate of 8, the average performance improvement by LESS can be expected to be 13% better than that of the CRF scheme, a solution reported recently with a scheduling skeleton similar to LESS.
This paper is a study of the problem of relevance in inductive concept learning. It gives definitions of irrelevant literals and irrelevant examples and presents efficient algorithms that enable their elimination. The...
详细信息
This paper is a study of the problem of relevance in inductive concept learning. It gives definitions of irrelevant literals and irrelevant examples and presents efficient algorithms that enable their elimination. The proposed approach is directly applicable in propositional learning and in relation learning tasks that can be solved using a LINUS transformation approach. A simple inductive logic programming (ILP) problem is used to illustrate the approach to irrelevant literal and example elimination. Results of utility studies show the usefulness of literal reduction applied in LINUS and in the search of refinement graphs. (C) 1999 Elsevier Science Inc. All rights reserved.
作者：
Taylor, KCSIRO
Math & Informat Sci Canberra ACT 2601 Australia
Absorption is one of the so-called inverse resolution operators of inductive logic programming. The paper studies the properties of absorption that make it suitable for incremental generalization of definite clauses u...
详细信息
Absorption is one of the so-called inverse resolution operators of inductive logic programming. The paper studies the properties of absorption that make it suitable for incremental generalization of definite clauses using background knowledge represented by a definite program. The soundness and completeness of the operator are established according to Buntine's model of generalization called generalized subsumption. The completeness argument proceeds by viewing absorption as the inversion of SLD-resolution. In addition, some simplifying techniques are introduced for reducing the non-determinism inherent in usual presentations of absorption. The effect of these simplifications on completeness is discussed. (C) 1999 Elsevier Science Inc. All rights reserved.
作者：
Yamamoto, AHokkaido Univ
Div Elect & Informat Engn Kita Ku Sapporo Hokkaido 0608628 Japan Hokkaido Univ
Meme Media Lab Kita Ku Sapporo Hokkaido 0608628 Japan
We propose in this paper an inference method called Bottom Generalization for inductive logic programming (ILP, for short). We give an inference procedure based on it, and prove that a hypothesis clause H is derived b...
详细信息
We propose in this paper an inference method called Bottom Generalization for inductive logic programming (ILP, for short). We give an inference procedure based on it, and prove that a hypothesis clause H is derived by the procedure from an example E under a background theory B iff H subsumes E relative to B in Plotkin's sense. The theory B can be any clausal theory, and the example E can be any clause which is not implied by B. The derived hypothesis H is a clause, but is not always definite. The result is proved by defining a declarative semantics for arbitrary consistent clausal theories, and showing that SE-resolution, which was originally introduced by Plotkin, gives their complete procedural semantics. We also show that Bottom Generalization is more powerful than both Jung's method based on the V-operator and Saturant Generalization by Rouveirol, but not than Inverse Entailment by Muggleton. At the ILP '97 workshop we called our inference method "Inverse Entailment," but we have renamed it "Bottom Generalization" because we found that it differs from the original definition of Inverse Entailment.
Using problem-specific background knowledge, computer programs developed within the framework of inductive logic programming (ILP) have been used to construct restricted first-order logic solutions to scientific probl...
详细信息
Using problem-specific background knowledge, computer programs developed within the framework of inductive logic programming (ILP) have been used to construct restricted first-order logic solutions to scientific problems. However, their approach to the analysis of data with substantial numerical content has been largely limited to constructing clauses that: (a) provide qualitative descriptions ("high", "low" etc.) of the values of response variables;and (b) contain simple inequalities restricting the ranges of predictor variables. This has precluded the application of such techniques to scientific and engineering problems requiring a more sophisticated approach. A number of specialised methods have been suggested to remedy this. In contrast, we have chosen to take advantage of the fact that the existing theoretical framework for ILP places very few restrictions of the nature of the background knowledge. We describe two issues of implementation that make it possible to use background predicates that implement well-established statistical and numerical analysis procedures. Any improvements in analytical sophistication that result are evaluated empirically using artificial and real-life data. Experiments utilising artificial data are concerned with extracting constraints for response variables in the text-book problem of balancing a pole on a cart. They illustrate the use of clausal definitions of arithmetic and trigonometric functions, inequalities, multiple linear regression, and numerical derivatives. A non-trivial problem concerning the prediction of mutagenic activity of nitroaromatic molecules is also examined. In this case, expert chemists have been unable to devise a model for explaining the data. The result demonstrates the combined use by an ILP program of logical and numerical capabilities to achieve an analysis that includes linear modelling, clustering and classification. In all experiments, the predictions obtained compare favourably against benchmarks se
An efficient algorithm is proposed for reducing glitch power dissipation in CMOS logic circuits. The proposed algorithm takes a path balancing approach that is achieved using gate sizing and buffer insertion methods. ...
详细信息
An efficient algorithm is proposed for reducing glitch power dissipation in CMOS logic circuits. The proposed algorithm takes a path balancing approach that is achieved using gate sizing and buffer insertion methods. The gate sizing technique reduces not only glitches but also the effective circuit capacitance. After gate sizing, buffers are inserted into the remaining unbalanced paths which have not been subjected to gate sizing. ILP has been employed to determine the location of inserted buffers. The proposed algorithm has been tested on LGSynth91 benchmark circuits. Experimental results show that 61.5% of glitches are reduced on average.
The problem of learning universally quantified function free first order Horn expressions is studied. Several models of learning from equivalence and membership queries are considered, including the model where interp...
详细信息
The problem of learning universally quantified function free first order Horn expressions is studied. Several models of learning from equivalence and membership queries are considered, including the model where interpretations are examples (Learning from Interpretations), the model where clauses are examples (Learning from Entailment), models where extensional or intentional background knowledge is given to the learner (as done in inductive logic programming), and the model where the reasoning performance of the learner rather than identification is of interest (Learning to Reason). We present learning algorithms for all these tasks for the class of universally quantified function free Horn expressions. The algorithms are polynomial in the number of predicate symbols in the language and the number of clauses in the target Horn expression but exponential in the arity of predicates and the number of universally quantified variables. We also provide lower bounds for these tasks by way of characterising the VC-dimension of this class of expressions. The exponential dependence on the number of variables is the main gap between the lower and upper bounds.
We propose an approach for the integration of abduction and induction in logicprogramming. We define an Abductive Learning Problem as an extended inductive logic programming problem where both the background and targ...
详细信息
We propose an approach for the integration of abduction and induction in logicprogramming. We define an Abductive Learning Problem as an extended inductive logic programming problem where both the background and target theories are abductive theories and where abductive derivability is used as the coverage relation instead of deductive derivability. The two main benefits of this integration are the possibility of learning in presence of incomplete knowledge and the increased expressive power of the background and target theories. We present the system LAP (Learning Abductive Programs) that is able to solve this extended learning problem and we describe, by means of examples, four different learning tasks that can be performed by the system: learning from incomplete knowledge, learning rules with exceptions, learning from integrity constraints and learning recursive predicates. (C) 1999 Elsevier Science Inc. All rights reserved.
A rule-based program will return a set of answers to each query. An impure program, which includes the Prolog cut "!" and "not(.)" operators, can return different answers if its rules are re-ordere...
详细信息
A rule-based program will return a set of answers to each query. An impure program, which includes the Prolog cut "!" and "not(.)" operators, can return different answers if its rules are re-ordered. There are also many reasoning systems that return only the first answer found for each query;these first answers, too, depend on the rule order, even in pure rule-based systems. A theory revision algorithm, seeking a revised rule-base whose expected accuracy, over the distribution of queries, is optimal, should therefore consider modifying the order of the rules. This paper first shows that a polynomial number of training "labeled queries" (each a query paired with its correct answer) provides the distribution information necessary to identify the optimal ordering. It then proves, however, that the task of determining which ordering is optimal, once given this distributional information, is intractable even in trivial situations;e.g., even if each query is an atomic literal, we are seeking only a "perfect" theory, and the rule base is propositional. We also prove that this task is not even approximable: Unless P = NP, no polynomial time algorithm can produce an ordering of an n-rule theory whose accuracy is within n(gamma) of optimal, for some gamma > 0. We next prove similar hardness and non-approximatability, results for the related tasks of determining, in these impure contexts, (1) the optimal ordering of the antecedents;(2) the optimal set of new rules to add and (3) the optimal set of existing rules to delete. (C) 1999 Elsevier Science Inc. All rights reserved.
The inductive synthesis of recursive logic programs from incomplete information, such as input/output examples, is a challenging subfield both of inductive logic programming (ILP) acid of the synthesis (in general) of...
详细信息
The inductive synthesis of recursive logic programs from incomplete information, such as input/output examples, is a challenging subfield both of inductive logic programming (ILP) acid of the synthesis (in general) of logic programs, from formal specifications. We first overview past and present achievements, focusing on the techniques that were designed specifically for the inductive synthesis of recursive logic programs but also discussing a few general ILP techniques that can also induce non-recursive hypotheses. Then we analyse the prospects of these techniques in this task, investigating their applicability to software engineering as well as to knowledge acquisition and discovery. (C) 1999 Elsevier Science Inc. All rights reserved.
暂无评论