1,721,204 research outputs found
Learning from Polyhedral Sets
No full textParameterized linear systems allow for modelling
and reasoning over classes of polyhedra. Collections
of squares, rectangles, polytopes, and so on,
can readily be defined by means of linear systems
with parameters. In this paper, we investigate the
problem of learning a parameterized linear system
whose class of polyhedra includes a given set of example
polyhedral sets and it is minimal
Deciding Membership in a Class of Polyhedra
No full textParameterized linear systems allow for modelling and reasoning over classes of polyhedra. Collections of squares, rectangles, polytopes, and so on can readily be defined by means of linear systems with parameters in constant terms. In this paper, we consider the membership problem of deciding whether a given polyhedron belongs to the class defined by a parameterized linear system. As an example, we are interested in questions such as: “does a given polytope belong to the class of hypercubes?” We show that the membership problem is NP-complete, even when restricting to the 2-dimensional plane. Despite the negative result, the constructive proof allows us to devise a concise decision procedure using constraint logic programming over the reals, namely CLP(R), which searches for a characterization of all instances of a parameterized system that are equivalent to a given polyhedron
Using t-closeness anonymity to control for non-discrimination
No full textWe investigate the relation between t-closeness, a well-known model of data anonymization
against attribute disclosure, and α-protection, a model of the social discrimination hidden in
data. We show that t-closeness implies bdf (t)-protection, for a bound function bdf () depending on
the discrimination measure f() at hand. This allows us to adapt inference control methods, such
as the Mondrian multidimensional generalization technique and the Sabre bucketization and redistribution
framework, to the purpose of non-discrimination data protection. The parallel between
the two analytical models raises intriguing issues on the interplay between data anonymization and
non-discrimination research in data protection
YaDT: Yet another Decision Tree builder
No full textYaDT is a from-scratch main-memory implementation of the C4.5-like decision tree algorithm. Our presentation would be focused on the design principles that allowed for obtaining an extremely efficient system. Experimental results are reported comparing YaDT with Weka, dti, Xelopes and (E)C4.5
Introduction to the special issue on Artificial Intelligence for Society and Economy
Full text linkIntroduction to special issue on Artificial Intelligence for Society and Econom
A Complete Declarative Debugger of Missing Answers
No full textWe propose two declarative debuggers of missing answers with respect to C- and S-semantics. The debuggers are proved correct for every logic program. Moreover, they are complete and terminating with respect to a large class of programs, namely acceptable logic programs. The debuggers enhance existing proposals, which suffer from a problem due to the implementation of negation as failure. The proposed solution exploits decision procedures for C- and S-semantics introduced in [9]
Efficient C4.5
No full textWe present an analytic evaluation of the runtime behavior of the C4.5 algorithm which highlights some efficiency improvements. Based on the analytic evaluation, we have implemented a more efficient version of the algorithm, called EC4.5. It improves on C4.5 by adopting the best among three strategies for computing the information gain of continuous attributes. All the strategies adopt a binary search of the threshold in the whole training set starting from the local threshold computed at a node. The first strategy computes the local threshold using the algorithm of C4.5, which, in particular, sorts cases by means of the quicksoft method. The second strategy also uses the algorithm of C4.5, but adopts a counting sort method. The third strategy calculates the local threshold using a main-memory version of the RainForest algorithm, which does not need sorting. Our implementation computes the same decision trees as C4.5 with a performance gain of up to five times
On computing the semi-sum of two integers
No full textWe derive a sound program for computing the semi-sum of two integers using only integer operators and without incurring overflow
Decidability of logic program semantics and applications to testing
No full textIn this paper, we investigate the decidability problem of logic program semantics and observables, focusing in particular on the least Herbrand model (or M-semantics), the C-semantics, and the S-semantics. We introduce bounded logic programs, and show that they coincide with programs such that every ground query has finitely many SLD-refutations via any selection rule. In particular, bounded programs strictly include the well-studied class of acceptable logic programs. We show that the mentioned declarative semantics are decidable when considering acceptable programs and programs bounded by recursive level mappings. Interestingly, the decision procedures have direct implementations in the logic programming paradigm itself as Prolog meta-programs. We relate semantics decidability to program testing. In our terminology, the testing problem consists of checking whether or not the formal semantics of a program includes a given finite set of atoms. With this definition, semantics decidability and the testing problem are equivalent. The decision procedures are then recognized to be automatic tools for testing logic programs. The meta-programming approach reveals to be successful in modeling extensions such as arithmetic built-in's, negation, modular programming and some other declarative semantics. Also, we present some preliminary experimental results and an efficient compilation-oriented approach that overcome the overhead due to meta-programming
Termination of Constraint Logic Programs
No full textIn this paper, we introduce a method for proving universal termination of constraint logic programs by strictly extending the approach of Apt and Pedreschi [1]. Taking into account a generic constraint domain instead of the standard Herbrand univers, acceptable (CLP) programs are defined. We prove correctness and completeness of the method w.r.t. the leftmost selection rule for the class of ideal constraint systems, including CLP(R lin ), CLP(RT), and CLP(FT) among the others. Moreover, we investigate the problems arising in extending those results to non-ideal constraint system, by specifically designing sufficient conditions for termination of CLP(R) programs
- …
