We propose a dynamic logic of lying, wherein a 'lie that phi' (where phi is a formula in the logic) is an action in the sense of dynamic modal logic, that is interpreted as a state transformer relative to the formula phi. The states that are being transformed are pointed Kripke models encoding the uncertainty of agents about their beliefs. Lies can be about factual propositions but also about modal formulas, such as the beliefs of other agents or the belief consequences of the lies of other agents. We distinguish (i) an outside observer who is lying to an agent that is modelled in the system, from (ii) one agent who is lying to another agent, and where both are modelled in the system. For either case, we further distinguish (iii) the agent who believes everything that it is told (even at the price of inconsistency), from (iv) the agent who only believes what it is told if that is consistent with its current beliefs, and from (v) the agent who believes everything that it is told by consistently revising its current beliefs. The logics have complete axiomatizations, which can most elegantly be shown by way of their embedding in what is known as action model logic or the extension of that logic to belief revision.

It is known that fixed points of loopy belief propagation (BP) correspond to stationary points of the Bethe variational problem, where we minimize the Bethe free energy subject to normalization and marginalization constraints. Unfortunately, this does not entirely explain BP because BP is a dual rather than primal algorithm to solve the Bethe variational problem -- beliefs are infeasible before convergence. Thus, we have no better understanding of BP than as an algorithm to seek for a common zero of a system of non-linear functions, not explicitly related to each other. In this theoretical paper, we show that these functions are in fact explicitly related -- they are the partial derivatives of a single function of reparameterizations. That means, BP seeks for a stationary point of a single function, without any constraints. This function has a very natural form: it is a linear combination of local log-partition functions, exactly as the Bethe entropy is the same linear combination of local entropies.

We introduce a new class of lower bounds on the log partition function of a Markov random field which makes use of a reversed Jensen's inequality. In particular, our method approximates the intractable distribution using a linear combination of spanning trees with negative weights. This technique is a lower-bound counterpart to the tree-reweighted belief propagation algorithm, which uses a convex combination of spanning trees with positive weights to provide corresponding upper bounds. We develop algorithms to optimize and tighten the lower bounds over the non-convex set of valid parameter values. Our algorithm generalizes mean field approaches (including naïve and structured mean field approximations), which it includes as a limiting case.

Compiling Bayesian networks (BNs) to junction trees and performing belief propagation over them is among the most prominent approaches to computing posteriors in BNs. However, belief propagation over junction tree is known to be computationally intensive in the general case. Its complexity may increase dramatically with the connectivity and state space cardinality of Bayesian network nodes. In this paper, we address this computational challenge using GPU parallelization. We develop data structures and algorithms that extend existing junction tree techniques, and specifically develop a novel approach to computing each belief propagation message in parallel. We implement our approach on an NVIDIA GPU and test it using BNs from several applications. Experimentally, we study how junction tree parameters affect parallelization opportunities and hence the performance of our algorithm. We achieve speedups ranging from 0.68 to 9.18 for the BNs studied.

Situation calculus has been applied widely in artificial intelligence to model and reason about actions and changes in dynamic systems. Since actions carried out by agents will cause constant changes of the agents' beliefs, how to manage these changes is a very important issue. Shapiro et al. [22] is one of the studies that considered this issue. However, in this framework, the problem of noisy sensing, which often presents in real-world applications, is not considered. As a consequence, noisy sensing actions in this framework will lead to an agent facing inconsistent situation and subsequently the agent cannot proceed further. In this paper, we investigate how noisy sensing actions can be handled in iterated belief change within the situation calculus formalism. We extend the framework proposed in [22] with the capability of managing noisy sensings. We demonstrate that an agent can still detect the actual situation when the ratio of noisy sensing actions vs. accurate sensing actions is limited. We prove that our framework subsumes the iterated belief change strategy in [22] when all sensing actions are accurate. Furthermore, we prove that our framework can adequately handle belief introspection, mistaken beliefs, belief revision and belief update even with noisy sensing, as done in [22] with accurate sensing actions only.

Belief revision studies strategies about how agents revise their belief states when receiving new evidence.  Both in classical belief revision and in epistemic revision, a new input is either in the form of a (weighted) propositional formula or a total pre-order (where the total pre-order is considered as a whole).  However, in some real-world applications, a new input can be a partial pre-order where each unit that constitutes the partial pre-order is important and should be considered individually. To address this issue,  in this paper, we study how a partial pre-order representing the prior epistemic state can be revised by another partial pre-order (the new input) from a different perspective, where the revision is conducted recursively on the individual units of partial pre-orders.  We propose different revision operators (rules), dubbed the extension, match, inner and outer revision operators, from different revision points of view. We also analyze several properties for these operators.

Belief merging aims at extracting a coherent and informative view from a set of belief bases. A first requirement for belief merging operators is to obey basic rationality conditions. Another expected property is to preserve as much information as possible from the input bases. In this paper, we show how new merging operators, called compositional operators, can be defined from existing ones. Such operators aim at offering a higher discriminative power than the merging operators on which they are based, without leading to a complexity shift or losing rationality postulates. We identify some sufficient conditions for ensuring that rationality is fully preserved by composition.

A bipolar framework is introduced for combining agents' beliefs so as to enable them to reach a common shared position or viewpoint. Our approach exploits the truth-gaps inherent to propositions involving vague concepts, by allowing agents to soften directly conflicting opinions. To this end we adopt a bipolar truth-model for propositional logic characterised by lower and upper valuations on the sentences of the language. According to this model sentences may be absolutely true, absolutely false or borderline (i.e. neither absolutely true nor absolutely false). The added flexibility of a possible truth-gap between absolutely true and absolutely false allows agents with inconsistent viewpoints, in which a proposition p is absolutely true according to one view and absolutely false according to the other, to reach a compromise position in which p is borderline. Within this framework four combination operators are proposed for combining different viewpoints as represented by different valuation pairs. Intuitively, these correspond to compromise positions with different levels of semantic precision (or vagueness). Kleene belief pairs are then introduced as lower and upper measures quantifying epistemic uncertainty about the sentences of the language when valuation pairs provide the underlying truth model. The combination operators on valuation pairs are then extended to belief pairs using a general schema incorporating a probabilistic model of the interaction between agents. The properties of the four operators are then investigated within this extended framework.

Following the recent trend of adapting the AGM (Alchourron and Makinson 1985) framework to propositional Horn logic, Delgrande and Peppas (Delgrande and Peppas 2011) give a model theoretic account for revision in the Horn logic set- ting. The current paper complements their work by studying the model theoretic approach for contraction. A model based Horn contraction is constructed and shown to give a model theoretic account to the transitively relational partial meet Horn contraction studied in (Zhuang and Pagnucco 2011). Significantly however, in contrast to (Delgrande and Pep- pas 2011), our model-based characterisation of Horn contrac- tion does not require the property of Horn compliance and totality over preorders. The model based contraction, upon proper restriction, also gives a model theoretic account for the epistemic entrenchment based Horn contraction studied in (Zhuang and Pagnucco 2010a).

Existing methods for dealing with knowledge updates differ greatly depending on the underlying knowledge representation formalism. When Classical Logic is used, update operators are typically based on manipulating the knowledge base on the model-theoretic level. On the opposite side of the spectrum stand the semantics for updating Answer-Set Programs where most approaches need to rely on rule syntax. Yet, a unifying perspective that could embrace all these approaches is of great importance as it enables a deeper understanding of all involved methods and principles and creates room for their cross-fertilisation, ripening and further development. This paper bridges these seemingly irreconcilable approaches to updates. It introduces a novel monotonic characterisation of rules, dubbed \emph{\RE-models}, and shows it to be a more suitable semantic foundation for rule updates than \SE-models. A generic framework for defining semantic rule update operators is then proposed. It is based on the idea of viewing a program as the \emph{set of sets of \RE-models} of its rules; updates are performed by introducing additional interpretations to the sets of \RE-models of rules in the original program. It is shown that particular instances of the framework are closely related to both belief update principles and traditional approaches to rule updates and enjoy a range of plausible syntactic as well as semantic properties.