Assignment methods for incidence calculus

Incidence calculus is a mechanism for probabilistic reasoning in which sets of possible worlds, called incidences, are associated with axioms, and probabilities are then associated with these sets. Inference rules are used to deduce bounds on the incidence of formulae which are not axioms, and bounds for the probability of such a formula can then be obtained. In practice an assignment of probabilities directly to axioms may be given, and it is then necessary to find an assignment of incidence which will reproduce these probabilities. We show that this task of assigning incidences can be viewed as a tree searching problem, and two techniques for performing this research are discussed. One of these is a new proposal involving a depth first search, while the other incorporates a random element. A Prolog implementation of these methods has been developed. The two approaches are compared for efficiency and the significance of their results are discussed. Finally we discuss a new proposal for applying techniques from linear programming to incidence calculus.

A comprehensive comparison between generalized incidence calculus and Dempster-Shafer theory of evidence.

Dealing with uncertainty problems in intelligent systems has attracted a lot of attention in the AI community. Quite a few techniques have been proposed. Among them, the Dempster-Shafer theory of evidence (DS theory) has been widely appreciated. In DS theory, Dempster's combination rule plays a major role. However, it has been pointed out that the application domains of the rule are rather limited and the application of the theory sometimes gives unexpected results. We have previously explored the problem with Dempster's combination rule and proposed an alternative combination mechanism in generalized incidence calculus. In this paper we give a comprehensive comparison between generalized incidence calculus and the Dempster-Shafer theory of evidence. We first prove that these two theories have the same ability in representing evidence and combining DS-independent evidence. We then show that the new approach can deal with some dependent situations while Dempster's combination rule cannot. Various examples in the paper show the ways of using generalized incidence calculus in expert systems.

Constructing probabilistic ATMS using extended incidence calculus

This paper discusses the relations between extended incidence calculus and assumption-based truth maintenance systems (ATMSs). We first prove that managing labels for statements (nodes) in an ATMS is equivalent to producing incidence sets of these statements in extended incidence calculus. We then demonstrate that the justification set for a node is functionally equivalent to the implication relation set for the same node in extended incidence calculus. As a consequence, extended incidence calculus can provide justifications for an ATMS, because implication relation sets are discovered by the system automatically. We also show that extended incidence calculus provides a theoretical basis for constructing a probabilistic ATMS by associating proper probability distributions on assumptions. In this way, we can not only produce labels for all nodes in the system, but also calculate the probability of any of such nodes in it. The nogood environments can also be obtained automatically. Therefore, extended incidence calculus and the ATMS are equivalent in carrying out inferences at both the symbolic level and the numerical level. This extends a result due to Laskey and Lehner.

Model categories for orthogonal calculus

We restate the notion of orthogonal calculus in terms of model categories. This provides a cleaner set of results and makes the role of O(n)-equivariance clearer. Thus we develop model structures for the category of n-polynomial and n-homogeneous functors, along with Quillen pairs relating them. We then classify n-homogeneous functors, via a zig-zag of Quillen equivalences, in terms of spectra with an O(n)-action. This improves upon the classification theorem of Weiss. As an application, we develop a variant of orthogonal calculus by replacing topological spaces with orthogonal spectra.

Propositional and Relational Bayesian Networks Associated with Imprecise and Qualitative Probabilistic Assessments

This paper investigates a representation language with flexibility inspired by probabilistic logic and compactness inspired by relational Bayesian networks. The goal is to handle propositional and first-order constructs together with precise, imprecise, indeterminate and qualitative probabilistic assessments. The paper shows how this can be achieved through the theory of credal networks. New exact and approximate inference algorithms based on multilinear programming and iterated/loopy propagation of interval probabilities are presented; their superior performance, compared to existing ones, is shown empirically.

Belief change with noisy sensing in the situation calculus

Situation calculus has been applied widely in arti?cial 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.

Reduced K-theory for Azumaya algebras

Abstract In the theory of central simple algebras, often we are dealing with abelian groups which arise from the kernel or co-kernel of functors which respect transfer maps (for example K-functors). Since a central simple algebra splits and the functors above are “trivial” in the split case, one can prove certain calculus on these functors. The common examples are kernel or co-kernel of the maps Ki(F)?Ki(D), where Ki are Quillen K-groups, D is a division algebra and F its center, or the homotopy fiber arising from the long exact sequence of above map, or the reduced Whitehead group SK1. In this note we introduce an abstract functor over the category of Azumaya algebras which covers all the functors mentioned above and prove the usual calculus for it. This, for example, immediately shows that K-theory of an Azumaya algebra over a local ring is “almost” the same as K-theory of the base ring. The main result is to prove that reduced K-theory of an Azumaya algebra over a Henselian ring coincides with reduced K-theory of its residue central simple algebra. The note ends with some calculation trying to determine the homotopy fibers mentioned above.

tts: A SAT-Solver for Small, Difficult Instances

The Ternary Tree Solver (tts) is a complete solver for propositional satisfiability which was designed to have good performance on the most difficult small instances. It uses a static ternary tree data structure to represent the simplified proposition under all permissible partial assignments and maintains a database of derived propositions known to be unsatisfiable. In the SAT2007 competition version 4.0 won the silver medal for the category handmade, speciality UNSAT solvers and was the top qualifier for the second stage for handmade benchmarks, solving 11 benchmarks which were not solved by any other entrant. We describe the methods used by the solver and analyse the competition Phase 1 results on small benchmarks. We propose a first version of a comprehensive suite of small difficult satisfiability benchmarks (sdsb) and compare the worst-case performance of the competition medallists on these benchmarks.

Two-stage mixed discrete-continuous identification of radial basis function (RBF) neural models for nonlinear systems

The identification of nonlinear dynamic systems using radial basis function (RBF) neural models is studied in this paper. Given a model selection criterion, the main objective is to effectively and efficiently build a parsimonious compact neural model that generalizes well over unseen data. This is achieved by simultaneous model structure selection and optimization of the parameters over the continuous parameter space. It is a mixed-integer hard problem, and a unified analytic framework is proposed to enable an effective and efficient two-stage mixed discrete-continuous; identification procedure. This novel framework combines the advantages of an iterative discrete two-stage subset selection technique for model structure determination and the calculus-based continuous optimization of the model parameters. Computational complexity analysis and simulation studies confirm the efficacy of the proposed algorithm.

Distinguished algebraic semantics for t-norm based fuzzy logics:Methods and algebraic equivalencies

This paper is a contribution to Mathematical fuzzy logic, in particular to the algebraic study of t-norm based fuzzy logics. In the general framework of propositional core and ?-core fuzzy logics we consider three properties of completeness with respect to any semantics of linearly ordered algebras. Useful algebraic characterizations of these completeness properties are obtained and their relations are studied. Moreover, we concentrate on five kinds of distinguished semantics for these logics-namely the class of algebras defined over the real unit interval, the rational unit interval, the hyperreals (all ultrapowers of the real unit interval), the strict hyperreals (only ultrapowers giving a proper extension of the real unit interval) and finite chains, respectively-and we survey the known completeness methods and results for prominent logics. We also obtain new interesting relations between the real, rational and (strict) hyperreal semantics, and good characterizations for the completeness with respect to the semantics of finite chains. Finally, all completeness properties and distinguished semantics are also considered for the first-order versions of the logics where a number of new results are proved. © 2009 Elsevier B.V. All rights reserved.

Merging Knowledge Bases in Possibilistic Logic by Lexicographic Aggregation

Belief merging is an important but difficult problem in Artificial Intelligence, especially when sources of information are pervaded with uncertainty. Many merging operators have been proposed to deal with this problem in possibilistic logic, a weighted logic which is powerful for handling inconsistency and deal-ing with uncertainty. They often result in a possibilistic knowledge base which is a set of weighted formulas. Although possibilistic logic is inconsistency tolerant, it suffers from the well-known "drowning effect". Therefore, we may still want to obtain a consistent possibilistic knowledge base as the result of merging. In such a case, we argue that it is not always necessary to keep weighted information after merging. In this paper, we define a merging operator that maps a set of possibilistic knowledge bases and a formula representing the integrity constraints to a classical knowledge base by using lexicographic ordering. We show that it satisfies nine postulates that generalize basic postulates for propositional merging given in [11]. These postulates capture the principle of minimal change in some sense. We then provide an algorithm for generating the resulting knowledge base of our merging operator. Finally, we discuss the compatibility of our merging operator with propositional merging and establish the advantage of our merging operator over existing semantic merging operators in the propositional case.

The Analogical Peacock Hypothesis: The Sexual Selection of Mind-Reading and Relational Cognition in Human Communication

This integrative review presents a novel hypothesis as a basis for integrating two evolutionary viewpoints on the origins of human cognition and communication, the sexual selection of human mental capacities, and the social brain hypothesis. This new account suggests that mind-reading social skills increased reproductive success and consequently became targets for sexual selection. The hypothesis proposes that human communication has three purposes: displaying mind-reading abilities, aligning and maintaining representational parity between individuals to enable displays, and the exchange of propositional information. Intelligence, creativity, language, and humor are mental fitness indicators that signal an individual’s quality to potential mates, rivals, and allies. Five features central to the proposed display mechanism unify these indicators, the relational combination of concepts, large conceptual knowledge networks, processing speed, contextualization, and receiver knowledge. Sufficient between-mind alignment of conceptual networks allows displays based upon within-mind conceptual mappings. Creative displays communicate previously unnoticed relational connections and novel conceptual combinations demonstrating an ability to read a receiver’s mind. Displays are costly signals of mate quality with costs incurred in the developmental production of the neural apparatus required to engage in complex displays and opportunity costs incurred through time spent acquiring cultural knowledge. Displays that are fast, novel, spontaneous, contextual, topical, and relevant are hard-to-fake for lower quality individuals. Successful displays result in elevated social status and increased mating options. The review addresses literatures on costly signaling, sexual selection, mental fitness indicators, and the social brain hypothesis; drawing implications for nonverbal and verbal communication.