Cross-validation is a useful and generally applicable technique often employed in machine learning, including decision tree induction. An important disadvantage of straightforward implementation of the technique is it...
详细信息
Cross-validation is a useful and generally applicable technique often employed in machine learning, including decision tree induction. An important disadvantage of straightforward implementation of the technique is its computational overhead. In this paper we show that, for decision trees, the computational overhead of cross-validation can be reduced significantly by integrating the cross-validation withthe normal decision tree induction process. We discuss how existing decision tree algorithms can be adapted to this aim, and provide an analysis of the speedups these adaptations may yield. We identify a number of parameters that influence the obtainable speedups, and validate and refine our analysis with experiments on a variety of data sets with two different implementations. Besides cross-validation, we also briefly explore the usefulness of these techniques for bagging. We conclude with some guidelines concerning when these optimizations should be considered.
In this paper, we present an abstract framework for learning a finite domain constraint solver modeled by a set of operators enforcing a consistency. the behavior of the consistency to be learned is taken as the set o...
详细信息
In this paper, we present an abstract framework for learning a finite domain constraint solver modeled by a set of operators enforcing a consistency. the behavior of the consistency to be learned is taken as the set of examples on which the learning process is applied. the best possible expression of this operator in a given language is then searched. We instantiate this framework to the learning of bound-consistency in the indexical language of Gnu-Prolog.
this paper concerns formal theories for reasoning about the knowledge and belief of agents. It has seemed attractive to researchers in artificial intelligence to formalise these propositional attitudes as predicates o...
详细信息
this paper concerns formal theories for reasoning about the knowledge and belief of agents. It has seemed attractive to researchers in artificial intelligence to formalise these propositional attitudes as predicates of first-order predicate logic. this allows the agents to express stronger introspective beliefs and engage in stronger meta-rcasoning than in the classical modal operator approach. Results by Montague [1963] and thomason [1980] show, however, that the predicate approach is prone to inconsistency. More recent results by des Rivieres & Levesque [1988] and Morreau & Kraus [1998] show that we can maintain the predicate approach if we make suitable restrictions to our set of epistemic axioms. their results are proved by careful translations from corresponding modal formalisms. In the present paper we show that their results fit nicely into the framework of logicprogramming semantics, in that we show their results to be corollaries of well-known results in this field. this does not only allow us to demonstrate a close connection between consistency problems in the syntactic treatment of propositional attitudes and problems in semantics for logic programs, but it also allows us to strengthen the results of des Rivieres & Levesque [1988] and Morreau & Kraus [1998].
We investigate the combination of answer set programming and qualitative optimization techniques. Answer set optimization programs (ASO programs) have two parts. the generating program Pyen produces answer sets repres...
详细信息
We investigate the combination of answer set programming and qualitative optimization techniques. Answer set optimization programs (ASO programs) have two parts. the generating program Pyen produces answer sets representing possible solutions. the preference program Ppref expresses user preferences. It induces a preference relation on the answer sets of Pyen based on the degree to which rules are satisfied. We discuss possible applications of ASO programming, give complexity results and propose implementation techniques. We also analyze the relationship between A SO programs and CP-networks.
Disjunctive logicprogramming (DLP) is a very expressive formalism: it allows to express every property of finite structures that is decidable in the complexity class E∧ (NPNH). Despite the high expressiveness of DLP...
详细信息
Disjunctive logicprogramming (DLP) is a very expressive formalism: it allows to express every property of finite structures that is decidable in the complexity class E∧ (NPNH). Despite the high expressiveness of DLP, there are some simple properties, often arising in real-world applications, which cannot be encoded in a simple and natural manner. Among these, properties requiring to apply some arithmetic operators (like sum, times, count) on a set of elements satisfying some conditions, cannot be naturally expressed in DLP. To overcome this deficiency, in this paper we extend DLP by aggregate functions. We formally define the semantics of the new language, named DLP-4. We show the usefulness of the new constructs on relevant knowledge-based problems. We analyze the computational complexity of DLP-4, showing that the addition of aggregates does not bring a higher cost in that respect. We provide an implementation of the DLP-4 language in DLV- the state-of-the-art DLP system - and report on experiments which confirm the usefulness of the proposed extension also for the efficiency of the computation.
In this paper we show that the language of declarative logicprogramming (DLP) with answer sets and its extensions can be used to specify database evolution due to updates and active rules, and to verify correctness o...
详细信息
ISBN:
(纸本)0769515312
In this paper we show that the language of declarative logicprogramming (DLP) with answer sets and its extensions can be used to specify database evolution due to updates and active rules, and to verify correctness of active rules with respect to a specification described using temporal logic and aggregate operators. We classify the specification of active rules into four kind of constraints which can be expressed using a particular extension of DLP called Smodels. Smodels allows us to specify the evolution, to specify the constraints, and to enumerate all possible initial database states and initial updates. Together, these can be used to analyze all possible evolution paths of an active database system to verify if they satisfy a set of given constraints.
It is widely accepted that many algorithms can be concisely and clearly expressed as logical inference rules. However, logicprogramming has been inappropriate for the study of the running time of algorithms because t...
详细信息
ISBN:
(纸本)3540439307
It is widely accepted that many algorithms can be concisely and clearly expressed as logical inference rules. However, logicprogramming has been inappropriate for the study of the running time of algorithms because there has not been a clear and precise model of the run time of a logic program. We present a logicprogramming model of computation appropriate for the study of the run time of a wide variety of algorithms.
We provide here a declarative and model-theoretic characterization of the approximations computed by consistency during the resolution of finite domain constraint satisfaction problems.
ISBN:
(纸本)3540439307
We provide here a declarative and model-theoretic characterization of the approximations computed by consistency during the resolution of finite domain constraint satisfaction problems.
A neural implementation which provides an interesting massively parallel model for computing a fixed-point semantics of a program is introduced for multiadjoint logicprogramming [3]. Distinctive features of this prog...
ISBN:
(纸本)3540439307
A neural implementation which provides an interesting massively parallel model for computing a fixed-point semantics of a program is introduced for multiadjoint logicprogramming [3]. Distinctive features of this programming paradigm are that: very general aggregation connectives in the bodies are allowed; by considering different adjoint pairs, it is possible to use several implications in the rules.
暂无评论