bluuebunny/crossref_metadata_2025 huggingface dataset:
Query Rewriting for DL-Lite with n-ary Concrete Domains
Authors: Baader Franz , Borgwardt Stefan , Lippmann Marcel
Published: July 2017

We investigate ontology-based query answering (OBQA) in a setting where both the ontology and the query can refer to concrete values such as numbers and strings. In contrast to previous work on this topic, the built-in predicates used to compare values are not restricted to being unary. We introduce restrictions on these predicates and on the ontology language that allow us to reduce OBQA to query answering in databases using the so-called combined rewriting approach. Though at first sight our restrictions are different from the ones used in previous work, we show that our results strictly subsume some of the existing first-order rewritability results for unary predicates.
An Abstraction-Refinement Methodology for Reasoning about Network Games
Authors: Avni Guy , Guha Shibashis , Kupferman Orna
Published: July 2017

Network games (NGs) are played on directed graphs and are extensively used in network design and analysis. Search problems for NGs include finding special strategy profiles such as a Nash equilibrium and a globally optimal solution. The networks modeled by NGs may be huge. In formal verification, abstraction has proven to be an extremely effective technique for reasoning about systems with big and even infinite state spaces. We describe an abstraction-refinement methodology for reasoning about NGs. Our methodology is based on an abstraction function that maps the state space of an NG to a much smaller state space. We search for a global optimum and a Nash equilibrium by reasoning on an under- and an over-approximation defined on top of this smaller state space. When the approximations are too coarse to find such profiles, we refine the abstraction function. Our experimental results demonstrate the efficiency of the methodology.
A Model for Accountable Ordinal Sorting
Authors: Belahcene Khaled , Labreuche Christophe , Maudet Nicolas , Mousseau Vincent , Ouerdane Wassila
Published: July 2017

We address the problem of multicriteria ordinalsorting through the lens of accountability, i.e. theability of a human decision-maker to own a recommendationmade by the system. We put forward anumber of model features that would favor the capabilityto support the recommendation with a convincingexplanation. To account for that, we designa recommender system implementing and formalizingsuch features. This system outputs explanationsdefined under the form of specific argumentschemes tailored to represent the specific rules ofthe model. At the end, we discuss possible andpromising argumentative perspectives.
Dynamic Logic for Data-aware Systems: Decidability Results
Authors: Belardinelli Francesco , Herzig Andreas
Published: July 2017

We introduce a first-order extension of dynamic logic (FO-DL), suitable to represent and reason about the behaviour of Data-aware Systems (DaS), which are systems whose data content is explicitly exhibited in the system’s description. We illustrate the expressivity of the formal framework by modelling English auctions as DaS, and by specifying relevant properties in FO-DL. Most importantly, we develop an abstraction-based verification procedure, thus proving that the model checking problem for DaS against FO-DL is actually decidable, provided some mild assumptions on the interpretationdomain.
Reasoning about Probabilities in Unbounded First-Order Dynamical Domains
Authors: Belle Vaishak , Lakemeyer Gerhard
Published: July 2017

When it comes to robotic agents operating in an uncertain world, a major concern in knowledge representation is to better relate high-level logical accounts of belief and action to the low-level probabilistic sensorimotor data. Perhaps the most general formalism for dealing with degrees of belief and, in particular, how such beliefs should evolve in the presence of noisy sensing and acting is the account by Bacchus, Halpern, and Levesque.

In this paper, we reconsider that model of belief, and propose a new logical variant that has much of the expressive power of the original, but goes beyond it in novel ways. In particular, by moving to a semantical account of a modal variant of the situation calculus based on possible worlds with unbounded domains and probabilistic distributions over them, we are able to capture the beliefs of a fully introspective knowledge base with uncertainty by way of an only-believing operator. The paper introduces the new logic and discusses key properties as well as examples that demonstrate how the beliefs of a knowledge base change as a result of noisy actions.
Reformulating Queries: Theory and Practice
Authors: Benedikt Michael , Kostylev Egor V. , Mogavero Fabio , Tsamoura Efthymia
Published: July 2017

We consider a setting where a user wants to pose a query against a dataset where background knowledge, expressed as logical sentences, is available, but only a subset of the information can be used to answer the query. We thus want to reformulate the user query against the subvocabulary, arriving at a query equivalent to the user’s query assuming the background theory, but using only the restricted vocabulary. We consider two variations of the problem, one where we want any such reformulation and another where we restrict the size. We present a classification of the complexity of the problem, then provide algorithms for solving the problems in practice and evaluate their performance.
Safe Inductions: An Algebraic Study
Authors: Bogaerts Bart , Vennekens Joost , Denecker Marc
Published: July 2017

In many knowledge representation formalisms, a constructive semantics is defined based on sequential applications of rules or of a semantic operator. These constructions often share the property that rule applications must be delayed until it is safe to

do so: until it is known that the condition that triggers the rule will remain to hold. This intuition occurs for instance in the well-founded semantics of logic programs and in autoepistemic logic.

In this paper, we formally define the safety criterion algebraically. We study properties of so-called safe inductions and apply our theory to logic programming and autoepistemic logic. For the latter, we show that safe inductions manage to capture the intended meaning of a class of theories on which all classical constructive semantics fail.
Semantics for Active Integrity Constraints Using Approximation Fixpoint Theory
Authors: Bogaerts Bart , Cruz-Filipe Luís
Published: July 2017

Active integrity constraints (AICs) constitute a formalism to associate with a database not just the constraints it should adhere to, but also how to fix the database in case one or more of these constraints are violated. The intuitions regarding which repairs are “good” given such a description are closely related to intuitions that live in various areas of non-monotonic reasoning.

In this paper, we apply approximation fixpoint theory, an algebraic framework that unifies semantics of non-monotonic logics, to the field of AICs.

This results in a new family of semantics for AICs, of which we study semantics and relationships to existing semantics. We argue that the AFT-well-founded semantics has some desirable properties.
Generalized Planning: Non-Deterministic Abstractions and Trajectory Constraints
Authors: Bonet Blai , De Giacomo Giuseppe , Geffner Hector , Rubin Sasha
Published: July 2017

We study the characterization and computation of general policies for families of problems that share a structure characterized by a common reduction into a single abstract problem. Policies mu that solve the abstract problem P have been shown to solve all problems Q that reduce to P provided that mu terminates in Q. In this work, we shed light on why this termination condition is needed and how it can be removed. The key observation is that the abstract problem P captures the common structure among the concrete problems Q that is local (Markovian) but misses common structure that is global. We show how such global structure can be captured by means of trajectory constraints that in many cases can be expressed as LTL formulas, thus reducing generalized planning to LTL synthesis. Moreover, for a broad class of problems that involve integer variables that can be increased or decreased, trajectory constraints can be compiled away, reducing generalized planning to fully observable non-deterministic planning.
Making Cross Products and Guarded Ontology Languages Compatible
Authors: Bourhis Pierre , Morak Michael , Pieris Andreas
Published: July 2017

Cross products form a useful modelling tool that allows us to express natural statements such as "elephants are bigger than mice", or, more generally, to define relations that connect every instance in a relation with every instance in another relation. Despite their usefulness, cross products cannot be expressed using existing guarded ontology languages, such as description logics (DLs) and guarded existential rules. The question that comes up is whether cross products are compatible with guarded ontology languages, and, if not, whether there is a way of making them compatible. This has been already studied for DLs, while for guarded existential rules remains unanswered. Our goal is to give an answer to the above question. To this end, we focus on the guarded fragment of first-order logic (which serves as a unifying framework that subsumes many of the aforementioned ontology languages) extended with cross products, and we investigate the standard tasks of satisfiability and query answering. Interestingly, we isolate relevant fragments that are compatible with cross products.
Classical Generalized Probabilistic Satisfiability
Authors: Caleiro Carlos , Casal Filipe , Mordido Andreia
Published: July 2017

We analyze a classical generalized probabilistic satisfiability problem (GGenPSAT) which consists in deciding the satisfiability of Boolean combinations of linear inequalities involving probabilities of classical propositional formulas. GGenPSAT coincides precisely with the satisfiability problem of the probabilistic logic of Fagin et al. and was proved to be NP-complete. Here, we present a polynomial reduction of GGenPSAT to SMT over the quantifier-free theory of linear integer and real arithmetic. Capitalizing on this translation, we implement and test a solver for the GGenPSAT problem. As previously observed for many other NP-complete problems, we are able to detect a phase transition behavior for GGenPSAT.
Budget-Constrained Dynamics in Multiagent Systems
Authors: Cao Rui , Naumov Pavel
Published: July 2017

The paper introduces a notion of a budget-constrained multiagent transition system that associates two financial parameters with each transition: a pre-transition minimal budget requirement and a post-transition profit. The paper also proposes a new modal language for reasoning about such a system. The language uses a modality labeled by agent as well as by budget and profit constraints. The main technical result is a sound and complete logical system that describes all universal properties of this modality. Among these properties is a form of Transitivity axiom that captures the interplay between the budget and profit constraints.
Belief Change in a Preferential Non-monotonic Framework
Authors: Casini Giovanni , Meyer Thomas
Published: July 2017

Belief change and non-monotonic reasoning are usually viewed as two sides of the same coin, with results showing that one can formally be defined in terms of the other. In this paper we show that it also makes sense to analyse belief change within a (preferential) non-monotonic framework. We consider belief change operators in a non-monotonic propositional setting with a view towards preserving consistency. We show that the results obtained can also be applied to the preservation of coherence— an important notion within the field of logic-based ontologies. We adopt the AGM approach to belief change and show that standard AGM can be adapted to a preferential non-monotonic framework, with the definition of expansion, contraction, and revision operators, and corresponding representation results.
The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality
Authors: Aziz Haris , Elkind Edith , Faliszewski Piotr , Lackner Martin , Skowron Piotr
Published: July 2017

We study two notions of stability in multiwinner elections that are based on the Condorcet criterion. The first notion was introduced by Gehrlein and is majoritarian in spirit. The second one, local stability, is introduced in this paper, and focuses on voter representation. The goal of this paper is to explore these two notions, their implications on restricted domains, and the computational complexity of rules that are consistent with them.
Discriminative Dictionary Learning With Ranking Metric Embedded for Person Re-Identification
Authors: Cheng De , Chang Xiaojun , Liu Li , Hauptmann Alexander G. , Gong Yihong , Zheng Nanning
Published: July 2017

The goal of person re-identification (Re-Id) is to match pedestrians captured from multiple non-overlapping cameras. In this paper, we propose a novel dictionary learning based method with the ranking metric embedded, for person Re-Id. A new and essential ranking graph Laplacian term is introduced, which minimizes the intra-personal compactness and maximizes the inter-personal dispersion in the objective. Different from the traditional dictionary learning based approaches and their extensions, which just use the same or not information, our proposed method can explore the ranking relationship among the person images, which is essential for such retrieval related tasks. Simultaneously, one distance measurement has been explicitly learned in the model to further improve the performance. Since we have reformulated these ranking constraints into the graph Laplacian form, the proposed method is easy-to-implement but effective. We conduct extensive experiments on three widely used person Re-Id benchmark datasets, and achieve state-of-the-art performances.
Handling non-local dead-ends in Agent Planning Programs
Authors: Chrpa Lukas , Lipovetzky Nir , Sardina Sebastian
Published: July 2017

We propose an approach to reason about agent planning programs with global information. Agent planning programs can be understood as a network of planning tasks, accommodating long-term goals, non-terminating behaviors, and interactive execution. We provide a technique that relies on reasoning about ``global" dead-ends and that can be incorporated to any planning-based approach to agent planning problems. In doing so, we also introduce the notion of online execution of such planning structures. We provide experimental evidence suggesting the technique yields significant benefits.
Inferring Implicit Event Locations from Context with Distributional Similarities
Authors: Chung Jin-Woo , Yang Wonsuk , You Jinseon , Park Jong C.
Published: July 2017

Automatic event location extraction from text plays a crucial role in many applications such as infectious disease surveillance and natural disaster monitoring. The fundamental limitation of previous work such as SpaceEval is the limited scope of extraction, targeting only at locations that are explicitly stated in a syntactic structure. This leads to missing a lot of implicit information inferable from context in a document, which amounts to nearly 40% of the entire location information. To overcome this limitation for the first time, we present a system that infers the implicit event locations from a given document. Our system exploits distributional semantics, based on the hypothesis that if two events are described by similar expressions, it is likely that they occur in the same location. For example, if “A bomb exploded causing 30 victims” and “many people died from terrorist attack in Boston” are reported in the same document, it is highly likely that the bomb exploded in Boston. Our system shows good performance of a 0.58 F1-score, where state-of-the-art classifiers for intra-sentential spatiotemporal relations achieve around 0.60 F1-scores.
On Querying Incomplete Information in Databases under Bag Semantics
Authors: Console Marco , Guagliardo Paolo , Libkin Leonid
Published: July 2017

Querying incomplete data is an important task both in data management, and in many AI applications that use query rewriting to take advantage of relational database technology. Usually one looks for answers that are certain, i.e., true in every possible world represented by an incomplete database. For positive queries, expressed either in positive relational algebra or as unions of conjunctive queries, finding such answers can be done efficiently when databases and query answers are sets. Real-life databases however use bag, rather than set, semantics. For bags, instead of saying that a tuple is certainly in the answer, we have more detailed information: namely, the range of the numbers of occurrences of the tuple in query answers. We show that the behavior of positive queries is different under bag semantics: finding the minimum number of occurrences can still be done efficiently, but for maximum it becomes intractable. We use these results to investigate approximation schemes for computing certain answers to arbitrary first-order queries that have been proposed for set semantics. One of them cannot be adapted to bags, as it relies on the intractable maxima of occurrences, but another scheme only deals with minima, and we show how to adapt it to bag semantics without losing efficiency.
Lazy-Grounding for Answer Set Programs with External Source Access
Authors: Eiter Thomas , Kaminski Tobias , Weinzierl Antonius
Published: July 2017

HEX-programs enrich the well-known Answer Set Programming (ASP) paradigm. In HEX, problems are solved using nonmonotonic logic programs with bidirectional access to external sources. ASP evaluation is traditionally based on grounding the input program first, but recent advances in lazy-grounding make the latter also interesting for HEX, as the grounding bottleneck of ASP may be avoided. We explore this issue and present a new evaluation algorithm for HEX-programs based on lazy-grounding solving for ASP. Nonmonotonic dependencies and value invention (i.e., import of new constants) from external sources make an efficient solution nontrivial. However, illustrative benchmarks show a clear advantage of the new algorithm for grounding-intense programs, which is a new perspective to make HEX more suitable for real-world application needs.
Process Plan Controllers for Non-Deterministic Manufacturing Systems
Authors: Felli Paolo , de Silva Lavindra , Logan Brian , Ratchev Svetan
Published: July 2017

Determining the most appropriate means of producing a given product, i.e., which manufacturing and assembly tasks need to be performed in which order and how, is termed process planning. In process planning, abstract manufacturing tasks in a process recipe are matched to available manufacturing resources, e.g., CNC machines and robots, to give an executable process plan. A process plan controller then delegates each operation in the plan to specific manufacturing resources. In this paper we present an approach to the automated computation of process plans and process plan controllers. We extend previous work to support both non-deterministic (i.e., partially controllable) resources, and to allow operations to be performed in parallel on the same part. We show how implicit fairness assumptions can be captured in this setting, and how this impacts the definition of process plans.
Strategically knowing how
Authors: Fervari Raul , Herzig Andreas , Li Yanjun , Wang Yanjing
Published: July 2017

In this paper, we propose a single-agent logic of goal-directed knowing how extending the standard epistemic logic of knowing that with a new knowing how operator. The semantics of the new operator is based on the idea that knowing how to achieve phi means that there exists a (uniform) strategy such that the agent knows that it can make sure phi. We give an intuitive axiomatisation of our logic and prove the soundness, completeness, and decidability of the logic. The crucial axioms relating knowing that and knowing how illustrate our understanding of knowing how in this setting. This logic can be used in representing and reasoning about knowledge-how.
Non-Determinism and the Dynamics of Knowledge
Authors: Grossi Davide , Herzig Andreas , van der Hoek Wiebe , Moyzes Christos
Published: July 2017

In this paper we attempt to shed light on the concept of an agent’s knowledge after a non-deterministic action is executed. We start by making a comparison between notions of non-deterministic choice, and between notions of sequential composition, of settings with dynamic and/or epistemic character; namely Propositional Dynamic Logic (PDL), Dynamic Epistemic Logic (DEL), and the more recent logic of Semi-Public Environments (SPE). These logics represent two different approaches for defining the aforementioned actions, and in order to provide unified frameworks that encompass both, we define the logics DELVO (DEL+Vision+Ontic change) and PDLVE (PDL+Vision+Epistemic operators). DELVO is given a sound and complete axiomatisation.
Nash Equilibria in Concurrent Games with Lexicographic Preferences
Authors: Gutierrez Julian , Murano Aniello , Perelli Giuseppe , Rubin Sasha , Wooldridge Michael
Published: July 2017

We study concurrent games with finite-memory strategies where players are given a Buchi and a mean-payoff objective, which are related by a lexicographic order: a player first prefers to satisfy its Buchi objective, and then prefers to minimise costs, which are given by a mean-payoff function. In particular, we show that deciding the existence of a strict Nash equilibrium in such games is decidable, even if players' deviations are implemented as infinite memory strategies.
ATL Strategic Reasoning Meets Correlated Equilibrium
Authors: Huang Xiaowei , Ruan Ji
Published: July 2017

This paper is motivated by analysing a Google self-driving car accident, i.e., the car hit a bus, with the framework and the tools of strategic reasoning by model checking. First of all, we find that existing ATL model checking may find a solution to the accident with {\it irrational} joint strategy of the bus and the car. This leads to a restriction of treating both the bus and the car as rational agents, by which their joint strategy is an equilibrium of certain solution concepts.

Second, we find that a randomly-selected joint strategy from the set of equilibria may result in the collision of the two agents, i.e., the accident.

Based on these, we suggest taking Correlated Equilibrium (CE) as agents' joint stratgey and optimising over the utilitarian value which is the expected sum of the agents' total rewards. The language ATL is extended with two new modalities to express the existence of an CE and a unique CE, respectively.

We implement the extension into a software model checker and use the tool to analyse the examples in the paper. We also study the complexity of the model checking problems.
Belief Manipulation Through Propositional Announcements
Authors: Hunter Aaron , Schwarzentruber François , Tsang Eric
Published: July 2017

Public announcements cause each agent in a group to modify their beliefs to incorporate some new piece of information, while simultaneously being aware that all other agents are doing the same. Given a set of agents and a set of epistemic goals, it is natural to ask if there is a single announcement that will make each agent believe the corresponding goal. This problem is known to be undecidable in a general modal setting, where the presence of nested beliefs can lead to complex dynamics. In this paper, we consider not necessarily truthful public announcements in the setting of AGM belief revision. We prove that announcement finding in this setting is not only decidable, but that it is simpler than the corresponding problem in the most simplified modal logics. We then describe AnnB, an implemented tool that uses announcement finding as the basis for controlling robot behaviour through belief manipulation.
Strong Syntax Splitting for Iterated Belief Revision
Authors: Kern-Isberner Gabriele , Brewka Gerhard
Published: July 2017

AGM theory is the most influential formal account of belief revision. Nevertheless, there are some issues with the original proposal. In particular, Parikh has pointed out that completely irrelevant information may be affected in AGM revision. To remedy this, he proposed an additional axiom (P) aiming to capture (ir)relevance by a notion of syntax splitting. In this paper we generalize syntax splitting from logical sentences to epistemic states, a step which is necessary to cover iterated revision. The generalization is based on the notion of marginalization of epistemic states. Furthermore, we study epistemic syntax splitting in the context of ordinal conditional functions. Our approach substantially generalizes the semantical treatment of (P) in terms of faithful preorders recently presented by Peppas and colleagues.
Model Checking Multi-Agent Systems against LDLK Specifications
Authors: Kong Jeremy , Lomuscio Alessio
Published: July 2017

We define the logic LDLK, a formalism for specifying multi-agent systems. LDLK extends LDL with epistemic modalities, including common knowledge, for reasoning about the evolution of knowledge states of the agents in the system. We study the complexity of verifying a multi-agent system against LDLK specifications and show this to be in PSPACE. We give an algorithm for the practical verification of multi-agent systems specified in LDLK. We show that the model checking algorithm, based on alternating-automata and nFA, is amenable to symbolic implementation on OBDDs. We introduce MCMAS LDLK , an extension of the open-source model checker MCMAS, implementing the algorithm and discuss the experimental results obtained.
Equilibria in Ordinal Games: A Framework based on Possibility Theory.
Authors: Ben Amor Nahla , Fargier Helene , Sabbadin Régis
Published: July 2017

The present paper proposes the first definition of mixed equilibrium for ordinal games. This definition naturally extends possibilistic (single agent) decision theory. This allows us to provide a unifying view of single and multi-agent qualitative decision theory. Our first contribution is to show that ordinal games always admit a possibilistic mixed equilibrium, which can be seen as a qualitative counterpart to mixed (probabilistic) equilibrium.Then, we show that a possibilistic mixed equilibrium can be computed in polynomial time (wrt the size of the game), which contrasts with pure Nash or mixed probabilistic equilibrium computation in cardinal game theory.The definition we propose is thus operational in two ways: (i) it tackles the case when no pure Nash equilibrium exists in an ordinal game; and (ii) it allows an efficient computation of a mixed equilibrium.
A Data-Driven Approach to Infer Knowledge Base Representation for Natural Language Relations
Authors: Luo Kangqi , Luo Xusheng , Chen Xianyang , Zhu Kenny Q.
Published: July 2017

This paper studies the problem of discovering the structured knowledge representation of binary natural language relations.The representation, known as the schema, generalizes the traditional path of predicates to support more complex semantics.We present a search algorithm to generate schemas over a knowledge base, and propose a data-driven learning approach to discover the most suitable representations to one relation. Evaluation results show that inferred schemas are able to represent precise semantics, and can be used to enrich manually crafted knowledge bases.
Ontology-Mediated Querying with the Description Logic EL: Trichotomy and Linear Datalog Rewritability
Authors: Lutz Carsten , Sabellek Leif
Published: July 2017

We consider ontology-mediated queries (OMQs) based on an EL

ontology and an atomic query (AQ), provide an ultimately

fine-grained analysis of data complexity and study rewritability

into linear Datalog-aiming to capture linear recursion in SQL.

Our main results are that every such OMQ is in AC0,

NL-complete or PTime-complete, and that containment in NL

coincides with rewritability into linear Datalog (whereas

containment in AC0 coincides with rewritability into first-order

logic). We establish natural characterizations of the three cases,

show that deciding linear Datalog rewritability (as well as the

mentioned complexities) is ExpTime-complete, give a way to

construct linear Datalog rewritings when they exist, and prove that

there is no constant bound on the arity of IDB relations in linear

Datalog rewritings.
Aggressive, Tense or Shy? Identifying Personality Traits from Crowd Videos
Authors: Bera Aniket , Randhavane Tanmay , Manocha Dinesh
Published: July 2017

We present a real-time algorithm to automatically classify the behavior or personality of a pedestrian based on his or her movements in a crowd video. Our classification criterion is based on Personality Trait theory. We present a statistical scheme that dynamically learns the behavior of every pedestrian and computes its motion model. This model is combined with global crowd characteristics to compute the movement patterns and motion dynamics and use them for crowd prediction. Our learning scheme is general and we highlight its performance in identifying the personality of different pedestrians in low and high density crowd videos. We also evaluate the accuracy by comparing the results with a user study.
A Reasoning System for a First-Order Logic of Limited Belief
Authors: Schwering Christoph
Published: July 2017

Logics of limited belief aim at enabling computationally feasible reasoning in highly expressive representation languages. These languages are often dialects of first-order logic with a weaker form of logical entailment that keeps reasoning decidable or even tractable. While a number of such logics have been proposed in the past, they tend to remain for theoretical analysis only and their practical relevance is very limited. In this paper, we aim to go beyond the theory. Building on earlier work by Liu, Lakemeyer, and Levesque, we develop a logic of limited belief that is highly expressive but remains decidable in the first-order and tractable in the propositional case and exhibits some characteristics that make it attractive for an implementation. We introduce a reasoning system that employs this logic as representation language and present experimental results that showcase the benefit of limited belief.
Fair Allocation based on Diminishing Differences
Authors: Segal-Halevi Erel , Aziz Haris , Hassidim Avinatan
Published: July 2017

Ranking alternatives is a natural way for humans to explain their preferences. It is being used in many settings, such as school choice (NY, Boston), Course allocations, and the Israeli medical lottery. In some cases (such as the latter two), several ``items'' are given to each participant. Without having any information on the underlying cardinal utilities, arguing about fairness of allocation requires extending the ordinal item ranking to ordinal bundle ranking. The most commonly used such extension is stochastic dominance (SD), where a bundle X is preferred over a bundle Y if its score is better according to all additive score functions. SD is a very conservative extension, by which few allocations are necessarily fair while many allocations are possibly fair. We propose to make a natural assumption on the underlying cardinal utilities of the players, namely that the difference between two items at the top is larger than the difference between two items at the bottom. This assumption implies a preference extension which we call diminishing differences (DD), where a X is preferred over Y if its score is better according to all additive score functions satisfying the DD assumption. We give a full characterization of allocations that are necessarily-proportional or possibly-proportional according to this assumption. Based on this characterization, we present a polynomial-time algorithm for finding a necessarily-DD-proportional allocation if it exists. Using simulations, we show that with high probability, a necessarily-proportional allocation does not exist but a necessarily-DD-proportional allocation exists, and moreover, that allocation is proportional according to the underlying cardinal utilities.
Efficiently Enforcing Path Consistency on Qualitative Constraint Networks by Use of Abstraction
Authors: Sioutis Michael , Condotta Jean-François
Published: July 2017

Partial closure under weak composition, or partial weak path-consistency for short, is essential for tackling fundamental reasoning problems associated with qualitative constraint networks, such as the satisfiability checking problem, and therefore it is crucial to be able to enforce it as fast as possible. To this end, we propose a new algorithm, called PWCα, for efficiently enforcing partial weak path-consistency on qualitative constraint networks, that exploits the notion of abstraction for qualitative constraint networks, utilizes certain properties of partial weak path-consistency,and adapts the functionalities of some state-of-the-art algorithms to its design. It is worth noting that, as opposed to a related approach in the recent literature, algorithm PWCα is complete for arbitrary qualitative constraint networks. The evaluation that we conducted with qualitative constraint networks of the Region Connection Calculus against a competing state-of-the-art generic algorithm for enforcing partial weak path-consistency, demonstrates the usefulness and efficiency of algorithm PWCα.
On Computing World Views of Epistemic Logic Programs
Authors: Son Tran Cao , Le Tiep , Kahl Patrick , Leclerc Anthony
Published: July 2017

This paper presents a novel algorithm for computing world views of different semantics of epistemic logic programs (ELP) and two of its realization, called Ep-asp (for an older semantics) and Ep-asp^{se} (for the newest semantics), whose implementation builds on the theoretical advancement in the study of ELPs and takes advantage of the multi-shot computation paradigm of the answer set solver Clingo. The new algorithm differs from the majority of earlier algorithms in its strategy. Specifically, it computes one world view at a time and utilizes properties of world views to reduce its search space. It starts by computing an answer set and then determines whether or not a world view containing this answer set exists. In addition, it allows for the computation to focus on world views satisfying certain properties. The paper includes an experimental analysis of the performance of the two solvers comparing against a recently developed solver. It also contains an analysis of their performance in goal directed computing against a logic programming based conformant planning system, dlv-k. It concludes with some final remarks and discussion on the future work.
Proposing a Highly Accurate Hybrid Component-Based Factorised Preference Model in Recommender Systems
Authors: Zafari Farhad , Rahmani Rasoul , Moser Irene
Published: July 2017

Recommender systems play an important role in today's electronic markets due to the large benefits they bring by helping businesses understand their customers' needs and preferences. The major preference components modelled by current recommender systems include user and item biases, feature value preferences, conditional dependencies, temporal preference drifts, and social influence on preferences. In this paper, we introduce a new hybrid latent factor model that achieves great accuracy by integrating all these preference components in a unified model efficiently. The proposed model employs gradient descent to optimise the model parameters, and an evolutionary algorithm to optimise the hyper-parameters and gradient descent learning rates. Using two popular datasets, we investigate the interaction effects of the preference components with each other.We conclude that depending on the dataset, different interactions exist between the preference components. Therefore, understanding these interaction effects is crucial in designing an accurate preference model in every preference dataset and domain.Our results show that on both datasets, different combinations of components result in different accuracies of recommendation, suggesting that some parts of the model interact strongly. Moreover, these effects are highly dataset-dependent, suggesting the need for exploring these effects before choosing the appropriate combination of components.
Causal Discovery from Nonstationary/Heterogeneous Data: Skeleton Estimation and Orientation Determination
Authors: Zhang Kun , Huang Biwei , Zhang Jiji , Glymour Clark , Schölkopf Bernhard
Published: July 2017

It is commonplace to encounter nonstationary or heterogeneous data, of which the underlying generating process changes over time or across data sets (the data sets may have different experimental conditions or data collection conditions). Such a distribution shift feature presents both challenges and opportunities for causal discovery. In this paper we develop a principled framework for causal discovery from such data, called Constraint-based causal Discovery from Nonstationary/heterogeneous Data (CD-NOD), which addresses two important questions. First, we propose an enhanced constraint-based procedure to detect variables whose local mechanisms change and recover the skeleton of the causal structure over observed variables. Second, we present a way to determine causal orientations by making use of independence changes in the data distribution implied by the underlying causal model, benefiting from information carried by changing distributions. Experimental results on various synthetic and real-world data sets are presented to demonstrate the efficacy of our methods.
Role Forgetting for ALCOQH(universal role)-Ontologies Using an Ackermann-Based Approach
Authors: Zhao Yizheng , Schmidt Renate A.
Published: July 2017

Forgetting refers to a non-standard reasoning problem concerned with eliminating concept and role symbols from description logic-based ontologies while preserving all logical consequences up to the remaining symbols. Whereas previous research has primarily focused on forgetting concept symbols, in this paper, we turn our attention to role symbol forgetting. In particular, we present a practical method for semantic role forgetting for ontologies expressible in the description logic ALCOQH(universal role), i.e., the basic description logic ALC extended with nominals, qualified number restrictions, role inclusions and the universal role. Being based on an Ackermann approach, the method is the only approach so far for forgetting role symbols in description logics with qualified number restrictions. The method is goal-oriented and incremental. It always terminates and is sound in the sense that the forgetting solution is equivalent to the original ontology up to the forgotten symbols possibly with new concept definer symbols. Despite our method not being complete, performance results of an evaluation with a prototypical implementation have shown very good success rates on real-world ontologies.
Contextual Covariance Matrix Adaptation Evolutionary Strategies
Authors: Abdolmaleki Abbas , Price Bob , Lau Nuno , Paulo Reis Luis , Neumann Gerhard
Published: July 2017

Many stochastic search algorithms are designed to optimize a fixed objective function to learn a task,

i.e., if the objective function changes slightly, for example, due to a change in the situation or context of the task,

relearning is required to adapt to the new context. For instance, if we want to learn a kicking movement for a soccer robot,

we have to relearn the movement for different ball locations. Such relearning is undesired as it is highly inefficient

and many applications require a fast adaptation to a new context/situation. Therefore, we investigate contextual stochastic search

algorithms that can learn multiple, similar tasks simultaneously. Current contextual stochastic search methods are based

on policy search algorithms and suffer from premature convergence and the need for parameter tuning.

In this paper, we extend the well known CMA-ES algorithm to the contextual setting and illustrate its performance on several contextual tasks.

Our new algorithm, called contextual CMA-ES, leverages from contextual learning while it preserves all the features of standard CMA-ES such

as stability, avoidance of premature convergence, step size control and a minimal amount of parameter tuning.
RHash: Robust Hashing via L_infinity-norm Distortion
Authors: Aghazadeh Amirali , Lan Andrew , Shrivastava Anshumali , Baraniuk Richard
Published: July 2017

Hashing is an important tool in large-scale machine learning. Unfortunately, current data-dependent hashing algorithms are not robust to small perturbations of the data points, which degrades the performance of nearest neighbor (NN) search. The culprit is the minimization of the L_2-norm, average distortion among pairs of points to find the hash function. Inspired by recent progress in robust optimization, we develop a novel hashing algorithm, dubbed RHash, that instead minimizes the L_1-norm, worst-case distortion among pairs of points. We develop practical and efficient implementations of RHash that couple the alternating direction method of multipliers (ADMM) framework with column generation to scale well to large datasets. A range of experimental evaluations demonstrate the superiority of RHash over ten state-of-the-art binary hashing schemes. In particular, we show that RHash achieves the same retrieval performance as the state-of-the-art algorithms in terms of average precision while using up to 60% fewer bits.
Efficient Reinforcement Learning with Hierarchies of Machines by Leveraging Internal Transitions
Authors: Bai Aijun , Russell Stuart
Published: July 2017

In the context of hierarchical reinforcement learning, the idea of hierarchies of abstract machines (HAMs) is to write a partial policy as a set of hierarchical finite state machines with unspecified choice states, and use reinforcement learning to learn an optimal completion of this partial policy. Given a HAM with potentially deep hierarchical structure, there often exist many internal transitions where a machine calls another machine with the environment state unchanged. In this paper, we propose a new hierarchical reinforcement learning algorithm that discovers such internal transitions automatically, and shortcircuits them recursively in computation of Q values. The resulting HAMQ-INT algorithm outperforms the state of the art significantly on the benchmark Taxi domain and a much more complex RoboCup Keepaway domain.
Handling Noise in Boolean Matrix Factorization
Authors: Belohlavek Radim , Trnecka Martin
Published: July 2017

We critically examine and point out weaknesses of the existing considerations in Boolean matrix factorization (BMF) regarding noise and the algorithms' ability to deal with noise. We argue that the current understanding is underdeveloped and that the current approaches are missing an important aspect. We provide a new, quantitative way to assess the ability of an algorithm to handle noise. Our approach is based on a common-sense definition of robustness requiring that the computed factorizations should not be affected much by varying the noise in data. We present an experimental evaluation of several existing algorithms and compare the results to the observations available in the literature. In addition to providing justification of some properties claimed in the literature without proper justification, our experiments reveal properties which were not reported as well as properties which counter certain claims made in the literature. Importantly, our approach reveals a line separating robust-to-noise from sensitive-to-noise algorithms, which has not been revealed by the previous approaches.
AccGenSVM: Selectively Transferring from Previous Hypotheses
Authors: Benavides-Prado Diana , Koh Yun Sing , Riddle Patricia
Published: July 2017

In our research, we consider transfer learning scenarios where a target learner does not have access to the source data, but instead to hypotheses or models induced from it. This is called the Hypothesis Transfer Learning (HTL) problem. Previous approaches concentrated on transferring source hypotheses as a whole. We introduce a novel method for selectively transferring elements from previous hypotheses learned with Support Vector Machines. The representation of an SVM hypothesis as a set of support vectors allows us to treat this information as privileged to aid learning during a new task. Given a possibly large number of source hypotheses, our approach selects the source support vectors that more closely resemble the target data, and transfers their learned coefficients as constraints on the coefficients to be learned. This strategy increases the importance of relevant target data points based on their similarity to source support vectors, while learning from the target data. Our method shows important improvements on the convergence rate on three classification datasets of varying sizes, decreasing the number of iterations by up to 56% on average compared to learning with no transfer and up to 92% compared to regular HTL, while maintaining similar accuracy levels.
Unsupervised Learning of Deep Feature Representation for Clustering Egocentric Actions
Authors: Bhatnagar Bharat Lal , Singh Suriya , Arora Chetan , Jawahar C.V.
Published: July 2017

Popularity of wearable cameras in life logging, law enforcement, assistive vision and other similar applications is leading to explosion in generation of egocentric video content. First person action recognition is an important aspect of automatic analysis of such videos. Annotating such videos is hard, not only because of obvious scalability constraints, but also because of privacy issues often associated with egocentric videos. This motivates the use of unsupervised methods for egocentric video analysis. In this work, we propose a robust and generic unsupervised approach for first person action clustering. Unlike the contemporary approaches, our technique is neither limited to any particular class of actions nor requires priors such as pre-training, fine-tuning, etc. We learn time sequenced visual and flow features from an array of weak feature extractors based on convolutional and LSTM autoencoder networks. We demonstrate that clustering of such features leads to the discovery of semantically meaningful actions present in the video. We validate our approach on four disparate public egocentric actions datasets amounting to approximately 50 hours of videos. We show that our approach surpasses the supervised state of the art accuracies without using the action labels.
Using Graphs of Classifiers to Impose Declarative Constraints on Semi-supervised Learning
Authors: Bing Lidong , Cohen William W. , Dhingra Bhuwan
Published: July 2017

We propose a general approach to modeling semi-supervised learning (SSL) algorithms. Specifically, we present a declarative language for modeling both traditional supervised classification tasks and many SSL heuristics, including both well-known heuristics such as co-training and novel domain-specific heuristics. In addition to representing individual SSL heuristics, we show that multiple heuristics can be automatically combined using Bayesian optimization methods. We experiment with two classes of tasks, link-based text classification and relation extraction. We show modest improvements on well-studied link-based classification benchmarks, and state-of-the-art results on relation-extraction tasks for two realistic domains.