Goto

Collaborating Authors

Results


Inference with System W Satisfies Syntax Splitting

arXiv.org Artificial Intelligence

In this paper, we investigate inductive inference with system W from conditional belief bases with respect to syntax splitting. The concept of syntax splitting for inductive inference states that inferences about independent parts of the signature should not affect each other. This was captured in work by Kern-Isberner, Beierle, and Brewka in the form of postulates for inductive inference operators expressing syntax splitting as a combination of relevance and independence; it was also shown that c-inference fulfils syntax splitting, while system P inference and system Z both fail to satisfy it. System W is a recently introduced inference system for nonmonotonic reasoning that captures and properly extends system Z as well as c-inference. We show that system W fulfils the syntax splitting postulates for inductive inference operators by showing that it satisfies the required properties of relevance and independence. This makes system W another inference operator besides c-inference that fully complies with syntax splitting, while in contrast to c-inference, also extending rational closure.


A Conditional Perspective on the Logic of Iterated Belief Contraction

arXiv.org Artificial Intelligence

In this article, we consider iteration principles for contraction, with the goal of identifying properties for contractions that respect conditional beliefs. Therefore, we investigate and evaluate four groups of iteration principles for contraction which consider the dynamics of conditional beliefs. For all these principles, we provide semantic characterization theorems and provide formulations by postulates which highlight how the change of beliefs and of conditional beliefs is constrained, whenever that is possible. The first group is similar to the syntactic Darwiche-Pearl postulates. As a second group, we consider semantic postulates for iteration of contraction by Chopra, Ghose, Meyer and Wong, and by Konieczny and Pino P\'erez, respectively, and we provide novel syntactic counterparts. Third, we propose a contraction analogue of the independence condition by Jin and Thielscher. For the fourth group, we consider natural and moderate contraction by Nayak. Methodically, we make use of conditionals for contractions, so-called contractionals and furthermore, we propose and employ the novel notion of $ \alpha $-equivalence for formulating some of the new postulates.


Binary Diffing as a Network Alignment Problem via Belief Propagation

arXiv.org Artificial Intelligence

In this paper, we address the problem of finding a correspondence, or matching, between the functions of two programs in binary form, which is one of the most common task in binary diffing. We introduce a new formulation of this problem as a particular instance of a graph edit problem over the call graphs of the programs. In this formulation, the quality of a mapping is evaluated simultaneously with respect to both function content and call graph similarities. We show that this formulation is equivalent to a network alignment problem. We propose a solving strategy for this problem based on max-product belief propagation. Finally, we implement a prototype of our method, called QBinDiff, and propose an extensive evaluation which shows that our approach outperforms state of the art diffing tools.


A Brief History of Updates of Answer-Set Programs

arXiv.org Artificial Intelligence

Over the last couple of decades, there has been a considerable effort devoted to the problem of updating logic programs under the stable model semantics (a.k.a. answer-set programs) or, in other words, the problem of characterising the result of bringing up-to-date a logic program when the world it describes changes. Whereas the state-of-the-art approaches are guided by the same basic intuitions and aspirations as belief updates in the context of classical logic, they build upon fundamentally different principles and methods, which have prevented a unifying framework that could embrace both belief and rule updates. In this paper, we will overview some of the main approaches and results related to answer-set programming updates, while pointing out some of the main challenges that research in this topic has faced.


Relevance in Belief Update

Journal of Artificial Intelligence Research

It has been pointed out by Katsuno and Mendelzon that the so-called AGM revision operators, defined by Alchourrón, Gärdenfors and Makinson, do not behave well in dynamically-changing applications. On that premise, Katsuno and Mendelzon formally characterized a different type of belief-change operators, typically referred to as KM update operators, which, to this date, constitute a benchmark in belief update. In this article, we show that there exist KM update operators that yield the same counter-intuitive results as any AGM revision operator. Against this non-satisfactory background, we prove that a translation of Parikh's relevance-sensitive axiom (P), in the realm of belief update, suffices to block this liberal behaviour of KM update operators. It is shown, both axiomatically and semantically, that axiom (P) for belief update, essentially, encodes a type of relevance that acts at the possible-worlds level, in the context of which each possible world is locally modified, in the light of new information. Interestingly, relevance at the possible-worlds level is shown to be equivalent to a form of relevance that acts at the sentential level, by considering the building blocks of relevance to be the sentences of the language. Furthermore, we concretely demonstrate that Parikh's notion of relevance in belief update can be regarded as (at least a partial) solution to the frame, ramification and qualification problems, encountered in dynamically-changing worlds. Last but not least, a whole new class of well-behaved, relevance-sensitive KM update operators is introduced, which generalize Forbus' update operator and are perfectly-suited for real-world implementations.


Belief propagation for permutations, rankings, and partial orders

arXiv.org Machine Learning

Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA Many datasets give partial information about an ordering or ranking by indicating which team won a game, which item a user prefers, or who infected whom. We define a continuous spin system whose Gibbs distribution is the posterior distribution on permutations, given a probabilistic model of these interactions. Using the cavity method we derive a belief propagation algorithm that computes the marginal distribution of each node's position. In addition, the Bethe free energy lets us approximate the number of linear extensions of a partial order and perform model selection. Ranking or ordering objects is a natural problem in In this case, the energy H(π) is the number of violations, many contexts.


Simultaneous Perception-Action Design via Invariant Finite Belief Sets

arXiv.org Artificial Intelligence

Although perception is an increasingly dominant portion of the overall computational cost for autonomous systems, only a fraction of the information perceived is likely to be relevant to the current task. To alleviate these perception costs, we develop a novel simultaneous perception-action design framework wherein an agent senses only the task-relevant information. This formulation differs from that of a partially observable Markov decision process, since the agent is free to synthesize not only its policy for action selection but also its belief-dependent observation function. The method enables the agent to balance its perception costs with those incurred by operating in its environment. To obtain a computationally tractable solution, we approximate the value function using a novel method of invariant finite belief sets, wherein the agent acts exclusively on a finite subset of the continuous belief space. We solve the approximate problem through value iteration in which a linear program is solved individually for each belief state in the set, in each iteration. Finally, we prove that the value functions, under an assumption on their structure, converge to their continuous state-space values as the sample density increases.


Goal Recognition for Deceptive Human Agents through Planning and Gaze

Journal of Artificial Intelligence Research

Eye gaze has the potential to provide insight into the minds of individuals, and this idea has been used in prior research to improve human goal recognition by combining human's actions and gaze. However, most existing research assumes that people are rational and honest. In adversarial scenarios, people may deliberately alter their actions and gaze, which presents a challenge to goal recognition systems. In this paper, we present new models for goal recognition under deception using a combination of gaze behaviour and observed movements of the agent. These models aim to detect when a person is deceiving by analysing their gaze patterns and use this information to adjust the goal recognition. We evaluated our models in two human-subject studies: (1) using data collected from 30 individuals playing a navigation game inspired by an existing deception study and (2) using data collected from 40 individuals playing a competitive game (Ticket To Ride). We found that one of our models (Modulated Deception Gaze Ontic) offers promising results compared to the previous state-of-the-art model in both studies. Our work complements existing adversarial goal recognition systems by equipping these systems with the ability to tackle ambiguous gaze behaviours.


Knowledge from Probability

arXiv.org Artificial Intelligence

We give a probabilistic analysis of inductive knowledge and belief and explore its predictions concerning knowledge about the future, about laws of nature, and about the values of inexactly measured quantities. The analysis combines a theory of knowledge and belief formulated in terms of relations of comparative normality with a probabilistic reduction of those relations. It predicts that only highly probable propositions are believed, and that many widely held principles of belief-revision fail. How can we have knowledge that goes beyond what we have observed - knowledge about the future, or about lawful regularities, or about the distal causes of the readings of our scientific instruments? Many philosophers think we can't. Nelson Goodman, for example, disparagingly writes that "obviously the genuine problem [of induction] cannot be one of attaining unattainable knowledge or of accounting for knowledge that we do not in fact have" [20, p. 62]. Such philosophers typically hold that the best we can do when it comes to inductive hypotheses is to assign them high probabilities. Here we argue that such pessimism is misplaced.


Streaming Belief Propagation for Community Detection

arXiv.org Machine Learning

The community detection problem requires to cluster the nodes of a network into a small number of well-connected "communities". There has been substantial recent progress in characterizing the fundamental statistical limits of community detection under simple stochastic block models. However, in real-world applications, the network structure is typically dynamic, with nodes that join over time. In this setting, we would like a detection algorithm to perform only a limited number of updates at each node arrival. While standard voting approaches satisfy this constraint, it is unclear whether they exploit the network information optimally. We introduce a simple model for networks growing over time which we refer to as streaming stochastic block model (StSBM). Within this model, we prove that voting algorithms have fundamental limitations. We also develop a streaming belief-propagation (StreamBP) approach, for which we prove optimality in certain regimes. We validate our theoretical findings on synthetic and real data.