Search

Supervised learning deals with the inference of a distribution over an output or label space $\mathcal{Y}$ conditioned on points in an observation space $\mathcal{X}$, given a training dataset D of pairs in $\mathcal{X} \times \mathcal{Y}$. However, in a lot of applications of interest, acquisition of large amounts of observations is easy, while the process of generating labels is time-consuming or costly. One way to deal with this problem is active learning, where points to be labelled are selected with the aim of creating a model with better performance than that of an model trained on an equal number of randomly sampled points. In this paper, we instead propose to deal with the labelling cost directly: The learning goal is defined as the minimisation of a cost which is a function of the expected model performance and the total cost of the labels used. This allows the development of general strategies and specific algorithms for (a) optimal stopping, where the expected cost dictates whether label acquisition should continue (b) empirical evaluation, where the cost is used as a performance metric for a given combination of inference, stopping and sampling methods. Though the main focus of the paper is optimal stopping, we also aim to provide the background for further developments and discussion in the related field of active learning. [ABSTRACT FROM AUTHOR]

The paper investigates the logic of database transformations based on abstract metafinite state machines. We first introduce a structure model that separates a metafinite state into database and algorithmic spaces with bridge functions providing a connection between them. Then abstract metafinite state machines are developed on top of metafinite states equipped with two kinds of updates: exclusive updates and aggregate updates. In order to characterize both static and dynamic aspects of abstract metafinite state machines, we present a logic which supports reasoning about the side effects of exclusive and aggregate updates in update multisets occurring over database transformations. [ABSTRACT FROM AUTHOR]

The paper presents a sound and strongly complete axiomatization of reasoning about polynomial weight formulas. In addition, the PSPACE decision procedure for polynomial weight formulas developed by Fagin, Halpern and Megiddo works for our logic as well. The introduced formalism allows the expression of qualitative probability statements, conditional probability and Bayesian inference. [ABSTRACT FROM AUTHOR]

Visibly Pushdown Languages (VPLs), recognized by Visibly Pushdown Automata (VPAs), are a nicely behaved family of context-free languages. It has been shown that VPAs are equivalent to Extended Document Type Definitions (EDTDs), and thus, they provide means for elegantly solving various problems on XML. Especially, it has been shown that VPAs are the apt device for streaming XML. One of the important problems about XML that can be addressed using VPAs is the validation problem in which we need to decide whether an XML document conforms to the specification given by an EDTD. In this paper, we are interested in solving the approximate version of this problem, which is to decide whether an XML document can be modified by a tolerable number of edit operations to yield a valid one with respect to a given EDTD. For this, we define Visibly Pushdown Transducers (VPTs) that give us the framework for solving this problem under two different semantics for edit operations on XML. While the first semantics is a generalization of edit operations on strings, the second semantics is new and motivated by the special nature of XML documents. Usings VPTs, we give streaming algorithms that solve the problem under both the semantics. These algorithms use storage space that only depends on the size of the EDTD and the number of tolerable errors. Furthermore, they can check approximate validity of an incoming XML document in a single pass over the document, using auxilliary stack space that is proportional to the depth of the XML document. [ABSTRACT FROM AUTHOR]

The paper presents a new approach to database preferences queries, where preferences are represented in a possibilistic logic manner, using symbolic weights. The symbolic weights may be processed without assessing their precise value, which leaves the freedom for the user to not specify any priority among the preferences. The user may also enforce a (partial) ordering between them, if necessary. The approach can be related to the processing of fuzzy queries whose components are conditionally weighted in terms of importance. Here, importance levels are symbolically processed, and refinements of both Pareto ordering and minimum ordering are used. The representational power of the proposed setting is stressed, while the approach is compared with database Best operator-like methods and with the CP-net approach developed in artificial intelligence. The paper also provides a structured and rather broad overview of the different lines of research in the literature dealing with the handling of preferences in database queries. [ABSTRACT FROM AUTHOR]

In this paper we recast the formalism of argumentation formalism known as DeLP (Defeasible Logic Programming) in game-theoretic terms. By considering a game between a Proponent and an Opponent, in which they present arguments for and against each literal we obtain a bigger gamut of truth values for those literals and their negations as they are defended and attacked. An important role in the determination of warranted literals is assigned to a defeating relation among arguments. We consider first an unrestricted version in which these games may be infinite and then we analyze the underlying assumptions commonly used to make them finite. Under these restrictions the games are always determined -one of the players has a winning strategy. We show how varying the defeating relation may alter the set of truth values reachable under this formalism. We also show how alternative characterizations of the defeating relation may lead to different assignations of truth values to the literals in a DeLP program. [ABSTRACT FROM AUTHOR]

In this paper we present a new rule-based approach for consistency preserving view updating in deductive databases. Based on rule transformations performed during schema design, fixpoint evaluations of these rules at run time compute consistent realizations of view update requests. Alternative realizations are expressed using disjunctive Datalog internally. The approach extends and integrates standard techniques for efficient query answering and integrity checking (based on transformation techniques and fixpoint computation, too). Views may be stratifiably recursive. The set-orientedness of the approach makes it potentially useful in the context of (commercial) SQL systems, too. [ABSTRACT FROM AUTHOR]

This paper investigates an extension of classification trees to deal with uncertain information where uncertainty is encoded in possibility theory framework. Class labels in data sets are no longer singletons but are given in the form of possibility distributions. Such situation may occur in many real-world problems and cannot be dealt with standard decision trees. We propose a new method for assessing the impurity of a set of possibility distributions representing instances's classes belonging to a given training partition. The proposed approach takes into account the mean similarity degree of each set of possibility distributions representing a given training partition. The so-called information closeness index is used to evaluate this similarity. Experimental results show good performance on well-known benchmarks. [ABSTRACT FROM AUTHOR]

This paper analyzes the aggregation of different abstract attack relations over a common set of arguments. Each of those attack relations can be considered as the representation of a criterion of warrant. It is well known in the field of Social Choice Theory that if some "fairness" conditions are imposed over an aggregation of preferences, it becomes impossible to yield a result. When the criteria lead to acyclic attack relations, a positive result may ensue under the same conditions, namely that if the class of winning coalitions in an aggregation process by voting is a proper prefilter an outcome will exist. This outcome may preserve some features of the competing attack relations, such as the highly desirable property of acyclicity which can be associated with the existence of a single extension of an argumentation system. The downside of this is that, in fact, the resulting attack relation must be a portion common to the "hidden dictators" in the system, that is, all the attack relations that belong to all the winning coalitions. [ABSTRACT FROM AUTHOR]

Logic programs under answer-set semantics constitute an important tool for declarative problem solving. In recent years, two research issues received growing attention. On the one hand, concepts like loops and elementary sets have been proposed in order to extend Clark's completion for computing answer sets of logic programs by means of propositional logic. On the other hand, different concepts of program equivalence, like strong and uniform equivalence, have been studied in the context of program optimization and modular programming. In this paper, we bring these two lines of research together and provide alternative characterizations for different conceptions of equivalence in terms of unfounded sets, along with the related concepts of loops and elementary sets. Our results yield new insights into the model theory of equivalence checking. We further exploit these characterizations to develop novel encodings of program equivalence in terms of standard and quantified propositional logic, respectively. [ABSTRACT FROM AUTHOR]

Argumentation-based formalisms provide a way of considering the defeasible nature of reasoning with partial and often erroneous knowledge in a given environment. This problem affects every aspect of a planning process. We will present an argumentation-based formalism that an agent could use for constructing plans starting from a previously introduced formalism. In such a formalism, agents represent their knowledge about their environment in Defeasible Logic Programming, and have a set of actions they can execute to affect their environment. These actions are defined in combination with a defeasible argumentation formalism. We will analyze the interplay of arguments and actions when constructing plans using Partial Order Planning techniques. [ABSTRACT FROM AUTHOR]

For the problem of reflecting an update on a database view to the main schema, the constant-complement strategies are precisely those which avoid all update anomalies, and so define the gold standard for well-behaved solutions to the problem. However, the families of view updates which are supported under such strategies are limited, so it is sometimes necessary to go beyond them, albeit in a systematic fashion. In this work, an investigation of such extended strategies is initiated for relational schemata. The approach is to characterize the information content of a database instance, and then require that the optimal reflection of a view update to the main schema embody the least possible change of information. To illustrate the utility of the idea, sufficient conditions for the existence of optimal insertions in the context of families of extended embedded implicational dependencies (XEIDs) are established. It is furthermore established that all such optimal insertions are equivalent up to a renaming of the new constant symbols which were introduced in support of the insertion. [ABSTRACT FROM AUTHOR]

We refer to the problem of translating schemas from a model to another, in a model independent framework. Specifically, we consider an approach where translations are specified as Datalog programs. In this context we show how it is possible to reason on models and schemas involved as input and output for a translation. The various notions are formalized: (i) concise descriptions of models in terms of sets of constructs, with associated propositional formulas; (ii) a notion of signature for translation rules (with the property that signatures can be automatically computed out of rules); (iii) the "application" of signatures to models. The main result is that the target model of a translation can be completely characterized given the description of the source model and the signatures of the rules. This result is being exploited in the framework of a tool that implements model generic translations. [ABSTRACT FROM AUTHOR]

It is claimed in [45] that first-order theorem provers are not efficient for reasoning with ontologies based on description logics compared to specialised description logic reasoners. However, the development of more expressive ontology languages requires the use of theorem provers able to reason with full first-order logic and even its extensions. So far, theorem provers have extensively been used for running experiments over TPTP containing mainly problems with relatively small axiomatisations. A question arises whether such theorem provers can be used to reason in real time with large axiomatisations used in expressive ontologies such as SUMO. In this paper we answer this question affirmatively by showing that a carefully engineered theorem prover can answer queries to ontologies having over 15,000 first-order axioms with equality. Ontologies used in our experiments are based on the language KIF, whose expressive power goes far beyond the description logic based languages currently used in the Semantic Web. [ABSTRACT FROM AUTHOR]

Clustering is an important tool to explore the hidden structure of large databases. There are several algorithms based on different approaches (hierarchical, partitional, density-based, model-based, etc.). Most of these algorithms have some discrepancies, e.g. they are not able to detect clusters with convex shapes, the number of the clusters should be a priori known, they suffer from numerical problems, like sensitiveness to the initialization, etc. In this paper we introduce a new clustering algorithm based on the sinergistic combination of the hierarchial and graph theoretic minimal spanning tree based clustering and the partitional Gaussian mixture model-based clustering algorithms. The aim of this hybridization is to increase the robustness and consistency of the clustering results and to decrease the number of the heuristically defined parameters of these algorithms to decrease the influence of the user on the clustering results. As the examples used for the illustration of the operation of the new algorithm will show, the proposed algorithm can detect clusters from data with arbitrary shape and does not suffer from the numerical problems of the Gaussian mixture based clustering algorithms. [ABSTRACT FROM AUTHOR]

The user of an information system rarely knows exactly what he is looking for, but once shown a piece of information he can quickly tell whether it is what he needs. Query tuning is the process of searching for the query that best approximates the information need of the user. Typically, navigation and querying are two completely separate processes, and the user usually has to switch often from one to the other-a painstaking process producing a frustrating experience. In this paper, we propose an approach to query tuning that integrates navigation and querying into a single process, thus leading to a more flexible and more user friendly method of query tuning. The proposed approach is based on formal concept analysis, and models the directory of an information source as a formal context in which the underlying concept lattice serves for navigation and the attributes of the formal context serve for query formulation. In order to support the user in coping with a possibly overwhelming number of alternative query tunings, preferences are introduced. [ABSTRACT FROM AUTHOR]

Automatic debugging of UML class diagrams helps in the visual specification of software systems because users cannot detect errors in logical inconsistency easily. This paper focuses on tractable consistency checking of UML class diagrams. We accurately identify inconsistencies in these diagrams by translating them into first-order predicate logic generalized by counting quantifiers and classify their expressivities by eliminating some components. For class diagrams of different expressive powers, we introduce optimized algorithms that compute their respective consistencies in P, NP, PSPACE, or EXPTIME with respect to the size of a class diagram. In particular, for two cases in which class diagrams contain (i) disjointness constraints and overwriting/multiple inheritances and (ii) these components along with completeness constraints, the restriction of attribute value types decreases the complexities from EXPTIME to P and PSPACE. Additionally, we confirm the existence of a meaningful restriction of class diagrams that prevents any logical inconsistency. [ABSTRACT FROM AUTHOR]

An extension of abduction is investigated where explanations for bunches of observations may be jointly computed by sets of interacting agents. At one hand, agents are allowed to partially contribute to the reasoning task, so that joint explanations can be singled out even if each agent does not have enough knowledge for carrying out abduction on its own. At the other hand, agents maintain their autonomy in choosing explanations, each one being equipped with a weighting function reflecting its perception about the reliability of set of hypotheses. Given that different agents may have different and possibly contrasting preferences, some reasonable notions of agents' agreement are introduced, and their computational properties are thoroughly studied. As an example application of the framework discussed in the paper, it is shown how to handle data management issues in Peer-to-Peer systems and, specifically, how to provide a repair-based semantics to inconsistent ones. [ABSTRACT FROM AUTHOR]

Controlled query evaluation for logic-oriented information systems provides a model for the dynamic enforcement of confidentiality policies even if users are able to reason about a priori knowledge and the answers to previous queries. Previous foundational work simply assumes that the control mechanism can solve the arising entailment problems (no matter how complex they may be), and deals only with closed queries. In this paper, we overcome these limitations by refining the abstract model for appropriately represented relational databases. We identify a relational submodel where all instances share a fixed infinite Herbrand domain but have finite base relations, and we require finite and domain-independent query results. Then, via suitable syntactic restrictions on the policy and query languages, each entailment problem occurring in the framework can be equivalently expressed as a universal validity problem within the Bernays-Schönfinkel class, whose (known) decidability in the classical setting is extended to our framework. For both refusal and lying, we design and verify evaluation methods for open queries, exploiting controlled query evaluation of appropriate sequences of closed queries, which include answer completeness tests. Keywords: Controlled query evaluation, Confidentiality, Refusal, Lying, Complete information system, Relational database, Open query, First-order logic, Safe query, Domain-independent query, Implication problem, Finite model theory, Bernays-Schönfinkel class, Guarded fragment, Completeness test. [ABSTRACT FROM AUTHOR]

This paper presents a semantic foundation of temporal conceptual models used to design temporal information systems. We consider a modeling language able to express both timestamping and evolution constraints. We conduct a deeper investigation on evolution constraints, eventually devising a model-theoretic semantics for a full-fledged model with both timestamping and evolution constraints. The proposed formalization is meant both to clarify the meaning of the various temporal constructors appeared in the literature and to give a rigorous definition to notions like satisfiability, subsumption and logical implication. Furthermore, we also show how to express temporal constraints using a subset of first-order temporal logic, i.e., , the description logic extended with the temporal operators Since and Until. We show how is able to capture the various modeling constraints in a succinct way and to perform automated reasoning on temporal conceptual models. [ABSTRACT FROM AUTHOR]

In this paper, we present a syntactic method for solving first-order equational constraints over term algebras. The presented method exploits a novel notion of quasi-solved form that we call answer. By allowing a restricted form of universal quantification, answers provide a more compact way to represent solutions than the purely existential solved forms found in the literature. Answers have been carefully designed to make satisfiability test feasible and also to allow for boolean operations, while maintaining expressiveness and user-friendliness. We present detailed algorithms for (1) satisfiability checking and for performing the boolean operations of (2) negation of one answer and (3) conjunction of nanswers. Based on these three basic operations, our solver turns any equational constraint into a disjunction of answers. We have implemented a prototype that is available on the web. Keywords: equality, constraint satisfaction, solver, term algebra, answer. [ABSTRACT FROM AUTHOR]

We present a novel logic-based approach to automate multi-issue bilateral negotiation in e-marketplaces. In such frameworks issues to negotiate on can be multiple, interrelated, and may not be fixed in advance. We use logic to model relations among issues and to allow agents express their preferences on them. In particular, we introduce the logic $\mathcal{P(N)}$, a fuzzy propositional logic extended with concrete domains in order to handle numerical, as well as non numerical features, and to deal with vagueness in buyer/seller preferences. Hence, agents can express preferences as e.g.,I am searching for a passenger car costing about 25000€ yet if the car has a GPS system and more than two-year warranty I can spend up to 28000€. We illustrate the theoretical framework, the logical language, the protocol we adopt and show that using a mediator with a proactive behavior we can compute Pareto-efficient agreements. [ABSTRACT FROM AUTHOR]

When decomposing database schemas, it is desirable that a decomposition is lossless and dependency preserving. A well-known and frequently used result for the relational model states that a functional dependency preserving decomposition is lossless if and only if it contains a key. We will show that this result does not always hold when domains are allowed to be finite, but provide conditions under which it can be preserved. We then extend our work to a complex-valued data model based on record, list, set and multiset constructor, where finite domains occur naturally for subattributes, even if the domains of flat attributes are infinite. [ABSTRACT FROM AUTHOR]

Dependency discovery is an important technique for relational database design due to numerous applications like normalisation and query optimisation. Similar applications are likely to exist in the context of XML. To date, there are few investigations into dependency discovery in the context of XML. We propose a transversal approach for discovering a class of subgraph-based XML functional dependencies with pre-image semantics (XFDs). We cover all aspects of the discovery process, from determining agree sets to the extraction of an XFD cover. An inherent challenge is the large and complex search space of valid XFDs due to the tree-structure of XML data. [ABSTRACT FROM AUTHOR]

There are a number of frameworks for modelling argumentation in logic. They incorporate a formal representation of individual arguments and techniques for comparing conflicting arguments. A common assumption for logic-based argumentation is that an argument is a pair $\langle\Phi,\alpha\rangle$ where Φ is minimal subset of the knowledgebase such that Φ is consistent and Φ entails the claim α. Different logics provide different definitions for consistency and entailment and hence give us different options for argumentation. Classical propositional logic is an appealing option for argumentation but the computational viability of generating an argument is an issue. Here we propose ameliorating this problem by using connection graphs to give information on the ways that formulae of the knowledgebase can be used to minimally and consistently entail a claim. Using a connection graph allows for a substantially reduced search space to be used when seeking all the arguments for a claim from a knowledgebase. We provide a theoretical framework and algorithms for this proposal, together with some theoretical results and some preliminary experimental results to indicate the potential of the approach. [ABSTRACT FROM AUTHOR]

The area of knowledge merging is concerned with merging conflicting information while preserving as much as possible. Most proposals in the literature work with knowledge bases expressed in propositional logic. We propose a new framework for merging knowledge bases expressed in (subsets of) first-order logic. Dilation operators (a concept originally introduced by Bloch and Lang) are employed and developed, and by combining them with the concept of comparison orderings we obtain a framework that is driven by model-based intuitions but that can be implemented in a syntax-based manner. We demonstrate specific dilation operators and comparison orderings for use in applications. We also show how postulates from the literature on knowledge merging translate into our framework and provide the conditions that dilation operators and comparison orderings must satisfy in order for the respective merging operators to satisfy the new postulates. [ABSTRACT FROM AUTHOR]

Creating mappings between ontologies is a common way of approaching the semantic heterogeneity problem on the Semantic Web. To fit into the landscape of semantic web languages, a suitable, logic-based representation formalism for mappings is needed. We argue that such a formalism has to be able to deal with uncertainty and inconsistencies in automatically created mappings. We analyze the requirements for such a formalism, and we propose a novel approach to probabilistic description logic programs as such a formalism, which tightly combines disjunctive logic programs under the answer set semantics with both description logics and Bayesian probabilities. We define the language, and we show that it can be used to resolve inconsistencies and merge mappings from different matchers based on the level of confidence assigned to different rules. Furthermore, we explore the computational aspects of consistency checking and query processing in tightly integrated probabilistic description logic programs. We show that these problems are decidable and computable, respectively, and that they can be reduced to consistency checking and cautious/brave reasoning, respectively, in tightly integrated disjunctive description logic programs. We also analyze the complexity of consistency checking and query processing in the new probabilistic description logic programs in special cases. In particular, we present a special case of these problems with polynomial data complexity. [ABSTRACT FROM AUTHOR]

The existence of Armstrong-instances of bounded domains is investigated for specific key systems. This leads to the concept of Armstrong(q,k,n)-codes. These are q-ary codes of length n, minimum distance n − k + 1 and have the property that for any possible k − 1 coordinate positions there are two codewords that agree exactly there. We derive upper and lower bounds on the length of the code as function of q and k. The upper bounds use geometric arguments and bounds on spherical codes, the lower bounds are probabilistic. [ABSTRACT FROM AUTHOR]

We present a method for decomposing a hypergraph with certain regularities into smaller hypergraphs. By applying this to the set of all canonical covers of a given set of functional dependencies, we obtain more efficient methods for solving several optimization problems in database design. These include finding one or all "optimal" covers w.r.t. different criteria, which can help to synthesize better decompositions, and to reduce the cost of constraint checking. [ABSTRACT FROM AUTHOR]

We propose an ASM-based method to integrate into current feature-based software design practice modular verification techniques. [ABSTRACT FROM AUTHOR]

We study inference systems for the combined class of functional and full hierarchical dependencies in relational databases. Two notions of implication are considered: the original version in which the underlying set of attributes is fixed, and the alternative notion in which this set is left undetermined. The first main result establishes a finite axiomatisation in fixed universes which clarifies the role of the complementation rule in the combined setting. In fact, we identify inference systems that are appropriate in the following sense: full hierarchical dependencies can be inferred without use of the complementation rule at all or with a single application of the complementation rule at the final step of the inference; and functional dependencies can be inferred without any application of the complementation rule. The second main result establishes a finite axiomatisation for functional and full hierarchical dependencies in undetermined universes. [ABSTRACT FROM AUTHOR]

The practical problem can be described in the following way. Physical objects (credit cards, important documents) should be identified using geometric labels. An optical device reads the label and a simple computation checks whether the label belongs to the given object or not. This could be done by "asking" an authority which stores certain data (e.g. the reading of the label) of the objects in question. This, however, supposes the existence of an online connection which could technically be difficult, on the other hand it would be a source of evedropping. This is why the identification will be done using the label and a 0,1 sequence both placed on the object. The sequence can be determined from the label. This calculation is done first when the document is supplied with them, later each time when identification is needed the reading and calculation are repeated and it is checked whether the result is the 0,1 sequence written on the object or not. Of course the method has practical values only when the label cannot be easily reproduced. Moreover we suppose that the labels are randomly generated. More mathematically, the space S of all possible labels is known and a (deterministic) function f mapping S into { 0,1}n, that is, the set of 0,1 sequences of length n. This function is used first in the "factory" where the labels and the 0,1 sequences are placed on the objects, and later each time when the identification is necessary. The size S of S is either infinite or finite, but even in the latter case S is much larger than the number of 0,1 sequences, 2n. The subset A ⊂ S satisfying A = { a: f(a) = i} for a given 0,1 sequence i is denoted by Ai. Of course, $A_i\cap A_{i^{\prime}}=\emptyset $ must hold for $i\not= i^{\prime}$. The situation however is even more serious. The reading device can read the label only with a certain error. Therefore we have to suppose that the space is endowed with a distance d. (0 ≤ d(a,b)( = d(b,a)) is defined for all pairs a,b ∈ S, where d(a,b) = 0 iff a = b and the triangle inequality d(a,c) ≤ d(a,b) + d(b,c) holds.) The reading device can read the label with an error at most ε> 0. Then if the label is within Ai, the reading device might sense it anywhere in the set n(Ai, ε) = { x ∈ S: d(A,x) ≤ ε}. The function f has to be defined and must have the value i within n(Ai, ε). Therefore these sets must be also disjoint. If a label x is randomly generated it might fall outside of the set $\cup_{i = 1}^{2 ^ n} n (A_i, \varepsilon )$. Then x cannot be used, it is a waste. The proportion of the the waste should be low. Hence we have the condition $\mu(\cup_{i=1}^{2^n} n(A_i, \varepsilon ))\geq \alpha$ for some (not very little) α> 0. If μ(Ai) is too large for some i then the falsifier has a good chance to choose a point randomly which falls in Ai. Therefore μ(Ai) ≤ ρ must hold for a rather small 0 < ρ. Now we are ready to define the geometric identifying codes in S of size n with error tolerance ε, waste-rate α and security ρ as a family of subsets $A_1, \ldots , A_{2^n}$ where n(Ai, ε) are disjoint (1 ≤ i ≤ 2n), $\mu(\cup_{i=1}^{2^n} n(A_i, \varepsilon ))\geq \alpha$, and μ(Ai) ≤ ρ holds for 1 ≤ i ≤ 2n.… [ABSTRACT FROM AUTHOR]