Boole''s conditions of possible experience and reasoning under uncertainty

Consider a set of logical sentences together with probabilities that they are true. These probabilities must satisfy certain conditions for this system to be consistent. It is shown that an analytical form of these conditions can be obtained by enumerating the extreme rays of a polyhedron. We also consider the cases when (i) intervals of probabilities are given, instead of single values; and (ii) best lower and upper bounds on the probability of an additional logical sentence to be true are sought. Enumeration of vertices and extreme rays is used. Each vertex defines a finear expression and the maximum (minimum) of these defines a best possible lower (upper) bound on the probability of the additional logical sentence to be true. Each extreme ray leads to a constraint on the probabilities assigned to the initial set of logical sentences. Redundancy in these expressions is studied. Illustrations are provided in the domain of reasoning under uncertainty.     

Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem

The column generation approach to large-scale linear programming is extended to the mixed-integer case. Two general algorithms, a dual and a primal one, are presented. Both involve finding k-best solutions to combinatorial optimization subproblems. Algorithms for these subproblems must be tailored to each specific application. Their use is illustrated by applying them to a new combinatorial optimization problem with applications in Artificial Intelligence: Probabilistic Maximum Satisfiability. This problem is defined as follows: consider a set of logical sentences together with probabilities that they are true, assume this set of sentences is not satisfiable in the probabilistic sense, i.e., there is no probability distribution on the set of possible worlds (truth assignments to the sentences corresponding to at least one truth assignment to the logical variables they contain) such that for each sentence the sum of probabilities of the possible worlds in which it is true is equal to its probability of being true; determine a minimum set of sentences to be deleted in order to make the remaining set of sentences satisfiable. Computational experience with both algorithms is reported on.     

A probabilistic logic based on the acceptability of gambles

This article presents a probabilistic logic whose sentences can be interpreted as asserting the acceptability of gambles described in terms of an underlying logic. This probabilistic logic has a concrete syntax and a complete inference procedure, and it handles conditional as well as unconditional probabilities. It synthesizes Nilsson’s probabilistic logic and Frisch and Haddawy’s anytime inference procedure with Wilson and Moral’s logic of gambles.Two distinct semantics can be used for our probabilistic logic: (1) the measure–theoretic semantics used by the prior logics already mentioned and also by the more expressive logic of Fagin, Halpern, and Meggido and (2) a behavioral semantics. Under the measure–theoretic semantics, sentences of our probabilistic logic are interpreted as assertions about a probability distribution over interpretations of the underlying logic. Under the behavioral semantics, these sentences are interpreted only as asserting the acceptability of gambles, and this suggests different directions for generalization.     

Nonmonotonic probabilistic logics under variable-strength inheritance with overriding: Complexity,algorithms, and implementation

In previous work, I have introduced nonmonotonic probabilistic logics under variable-strength inheritance with overriding. They are formalisms for probabilistic reasoning from sets of strict logical, default logical, and default probabilistic sentences, which are parameterized through a value λ ∈ [0, 1] that describes the strength of the inheritance of default probabilistic knowledge. In this paper, I continue this line of research. I give a precise picture of the complexity of deciding consistency of strength λ and of computing tight consequences of strength λ. Furthermore, I present algorithms for these tasks, which are based on reductions to the standard problems of deciding satisfiability and of computing tight logical consequences in model–theoretic probabilistic logic. Finally, I describe the system nmproblog, which includes a prototype implementation of these algorithms.     

On consistency in probabilistic logic for logical formulas represented by B-hypertrees

One of the problems (mainly unsolved) in probabilistic logic is to consistently assign probabilities to logical formulas. In this paper we consider Horn formulas represented by B-hypertrees. We give a set of necessary conditions that any valid assignment of probabilities to the logical formulas should fulfill. If a certain condition is imposed on the B-hypertree, the necessary conditions are also sufficient, thus describing exactly which rules the assigned probabilities should obey to be consistent.     

What is a Logic Translation?

We study logic translations from an abstract perspective, without any commitment to the structure of sentences and the nature of logical entailment, which also means that we cover both proof- theoretic and model-theoretic entailment. We show how logic translations induce notions of logical expressiveness, consistency strength and sublogic, leading to an explanation of paradoxes that have been described in the literature. Connectives and quantifiers, although not present in the definition of logic and logic translation, can be recovered by their abstract properties and are preserved and reflected by translations under suitable conditions. In memoriam Joseph Goguen     

Unifying hidden-variable problems from quantum mechanics by logics of dependence and independence

We study hidden-variable models from quantum mechanics and their abstractions in purely probabilistic and relational frameworks by means of logics of dependence and independence, which are based on team semantics. We show that common desirable properties of hidden-variable models can be defined in an elegant and concise way in dependence and independence logic. The relationship between different properties and their simultaneous realisability can thus be formulated and proven on a purely logical level, as problems of entailment and satisfiability of logical formulae. Connections between probabilistic and relational entailment in dependence and independence logic allow us to simplify proofs. In many cases, we can establish results on both probabilistic and relational hidden-variable models by a single proof, because one case implies the other, depending on purely syntactic criteria. We also discuss the ‘no-go’ theorems by Bell and Kochen-Specker and provide a purely logical variant of the latter, introducing non-contextual choice as a team-semantical property.     

Logic and probabilistic systems

Following some ideas of Roberto Magari, we propose trial and error probabilistic functions, i.e. probability measures on the sentences of arithmetic that evolve in time by trial and error. The set of the sentences that get limit probability 1 is a theory, in fact can be a complete set. We prove incompleteness results for this setting, by showing for instance that for every there are true sentences that get limit probability less than . No set as above can contain the set of all true sentences, although we exhibit some containing all the true sentences. We also consider an approach based on the notions of inner probability and outer probability, and we compare this approach with the one based on trial and error probabilistic functions. Although the two approaches are shown to be different, we single out an important case in which they are equivalent. Received March 20, 1995     

Two results in negation-free logic

Negation-free propositional logic (or first-order logic) is clearly less expressive than the corresponding full system with negation. However, we present two complexity results for logic without negation that are no different from those for the original system. First, the problem of determining logical implication between sentences composed solely of conjunctions and disjunctions is shown to be as difficult as that between arbitrary sentences. Second, we show that the problem of determining a minimum satisfying assignment for a propositional formula in negation-free conjunctive normal form, even with no more than two disjuncts per clause, is NP-complete. We also show that unless P = NP, no polynomial time approximation scheme can exist for this problem.     

Fuzzy inequational logic

We present a logic for reasoning about graded inequalities which generalizes the ordinary inequational logic used in universal algebra. The logic deals with atomic predicate formulas of the form of inequalities between terms and formalizes their semantic entailment and provability in graded setting which allows to draw partially true conclusions from partially true assumptions. We follow the Pavelka approach and define general degrees of semantic entailment and provability using complete residuated lattices as structures of truth degrees. We prove the logic is Pavelka-style complete. Furthermore, we present a logic for reasoning about graded if–then rules which is obtained as particular case of the general result.     

A granularity-based framework of deduction, induction, and abduction

In this paper, we propose a granularity-based framework of deduction, induction, and abduction using variable precision rough set models proposed by Ziarko and measure-based semantics for modal logic proposed by Murai et al. The proposed framework is based on α-level fuzzy measure models on the basis of background knowledge, as described in the paper. In the proposed framework, deduction, induction, and abduction are characterized as reasoning processes based on typical situations about the facts and rules used in these processes. Using variable precision rough set models, we consider β-lower approximation of truth sets of nonmodal sentences as typical situations of the given facts and rules, instead of the truth sets of the sentences as correct representations of the facts and rules. Moreover, we represent deduction, induction, and abduction as relationships between typical situations.     

A belief function classifier based on information provided by noisy and dependent features

A model and method are proposed for dealing with noisy and dependent features in classification problems. The knowledge base consists of uncertain logical rules forming a probabilistic argumentation system. Assumption-based reasoning is the inference mechanism that is used to derive information about the correct class of the object. Given a hypothesis regarding the correct class, the system provides a symbolic expression of the arguments for that hypothesis as a logical disjunctive normal form. These arguments turn into degrees of support for the hypothesis when numerical weights are assigned to them, thereby creating a support function on the set of possible classes. Since a support function is a belief function, the pignistic transformation is then applied to the support function and the object is placed into the class with maximal pignistic probability.     

Exploiting independencies to compute semigraphoid and graphoid structures

We deal with conditional independencies, which have a fundamental role in probability and multivariate statistics. The structure of probabilistic independencies is described by semigraphoids or, for strictly positive probabilities, by graphoids. In this paper, given a set of independencies compatible with a probability, the attention is focused toward the problem of computing efficiently the closure with respect to the semigraphoid and graphoid structures. We introduce a suitable notion of projection in order to provide a new method which properly uses conditional independence statements.     

States in Łukasiewicz logic correspond to probabilities of rational polyhedra

It will be shown that probabilities of infinite-valued events represented by formulas in ?ukasiewicz propositional logic are in one-to-one correspondence with tight probability measures over rational polyhedra in the unit hypercube. This result generalizes a recent work on rational measures of polyhedra and provides an elementary geometric approach to reasoning under uncertainty with states in ?ukasiewicz logic.     

Array approach to fuzzy logic

Promising results from applying an array-based approach to two-valued logic suggests its application to fuzzy logic. The idea is to limit the domain of truth-values to a discrete, finite domain, such that a logical relationship can be evaluated by an exhaustive test of all possible combinations of truth-values. The paper presents a study of the topic from an engineer's viewpoint. As an example 31 logical sentences valid in two-valued logic were tested in three-valued logic using the nested interactive array language, Nial. Out of these, 24 turned out to be valid in a three-valued extension based on the well-known S^* implication operator, also called “Gödel's implication operator”. Applications to automated approximate reasoning and fuzzy control are also illustrated.     

Optimizing Bernoulli Routing Policies for Balancing Loads on Call Centers and Minimizing Transmission Costs

We address the problem of assigning probabilities at discrete time instants for routing toll-free calls to a given set of call centers to minimize a weighted sum of transmission costs and load variability at the call centers during the next time interval.We model the problem as a tripartite graph and decompose the finding of an optimal probability assignment in the graph into the following problems: (i) estimating the true arrival rates at the nodes for the last time period; (ii) computing routing probabilities assuming that the estimates are correct. We use a simple approach for arrival rate estimation and solve the routing probability assignment by formulating it as a convex quadratic program and using the affine scaling algorithm to obtain an optimal solution.We further address a practical variant of the problem that involves changing routing probabilities associated with k nodes in the graph, where k is a prespecified number, to minimize the objective function. This involves deciding which k nodes to select for changing probabilities and determining the optimal value of the probabilities. We solve this problem using a heuristic that ranks all subsets of k nodes using gradient information around a given probability assignment.The routing model and the heuristic are evaluated for speed of computation of optimal probabilities and load balancing performance using a Monte Carlo simulation. Empirical results for load balancing are presented for a tripartite graph with 99 nodes and 17 call center gates.     

几何平均亚式期权定价方法的探析

本文对几何平均亚式期权不同的定价方法进行了详细的论述，从随机偏微分方程途径与概率论途径两个角度仔细描述了亚式期权定价的过程中，每个具体的主要演算步骤．本文采用几何平均法计算资产价格的平均值，并以连续时间的情形为例，用两种不同的方法得到几何平均亚式期权的解析定价公式，并通过比较得出两种结论是完全一致的．     

Learning failure-free PRISM programs

PRISM is a probabilistic logic programming formalism which allows defining a probability distribution over possible worlds. This paper investigates learning a class of generative PRISM programs known as failure-free. The aim is to learn recursive PRISM programs which can be used to model stochastic processes. These programs generalise dynamic Bayesian networks by defining a halting distribution over the generative process. Dynamic Bayesian networks model infinite stochastic processes. Sampling from infinite process can only be done by specifying the length of sequences that the process generates. In this case, only observations of a fixed length of sequences can be obtained. On the other hand, the recursive PRISM programs considered in this paper are self-terminating upon some halting conditions. Thus, they generate observations of different lengths of sequences. The direction taken by this paper is to combine ideas from inductive logic programming and learning Bayesian networks to learn PRISM programs. It builds upon the inductive logic programming approach of learning from entailment.     

A fully subjective approach to modelling inspection maintenance

The fully subjective, or fully Bayesian approach discussed in this paper provides straightforward means of presenting uncertainty related to future events to decision makers. This approach is described in the context of an inspection maintenance decision problem, and is contrasted with the classical probabilistic approach that assumes the existence of true probabilities and probability distributions which have to be estimated. Key features of the fully subjective approach are discussed, including integration of engineering judgements, uncertainty treatment and type of performance measures to be used. An example related to the problem of identifying “optimal” inspection intervals for an extrusion press is used to illustrate the principles described.     

Modified profile likelihood approach for certain intraclass correlation coefficients

In this paper we consider the problem of constructing confidence intervals and confidence lower bounds for the intraclass correlation coefficient in an interrater reliability study where the raters are randomly selected from a population of raters. The likelihood function of the interrater reliability is derived and simplified, and the profile likelihood based approach is readily available for computing the confidence intervals of the interrater reliability. Unfortunately, the confidence intervals computed by using the profile likelihood function are in general too narrow to have the desired coverage probabilities. From the practical point of view, a conservative approach, if at least as precise as any existing method, is preferred since it gives the correct results with a probability higher than claimed. Under this rationale, we propose the so-called modified profile likelihood approach in this paper. Simulation study shows that, the proposed method in general has better performance than currently used methods.