Solving linear-quadratic conditional Gaussian influence diagrams

This paper considers the problem of solving Bayesian decision problems with a mixture of continuous and discrete variables. We focus on exact evaluation of linear-quadratic conditional Gaussian influence diagrams (LQCG influence diagrams) with additively decomposing utility functions. Based on new and existing representations of probability and utility potentials, we derive a method for solving LQCG influence diagrams based on variable elimination. We show how the computations performed during evaluation of a LQCG influence diagram can be organized in message passing schemes based on Shenoy–Shafer and Lazy propagation. The proposed architectures are the first architectures for efficient exact solution of LQCG influence diagrams exploiting an additively decomposing utility function.     

Inference in hybrid Bayesian networks using mixtures of polynomials

The main goal of this paper is to describe inference in hybrid Bayesian networks (BNs) using mixture of polynomials (MOP) approximations of probability density functions (PDFs). Hybrid BNs contain a mix of discrete, continuous, and conditionally deterministic random variables. The conditionals for continuous variables are typically described by conditional PDFs. A major hurdle in making inference in hybrid BNs is marginalization of continuous variables, which involves integrating combinations of conditional PDFs. In this paper, we suggest the use of MOP approximations of PDFs, which are similar in spirit to using mixtures of truncated exponentials (MTEs) approximations. MOP functions can be easily integrated, and are closed under combination and marginalization. This enables us to propagate MOP potentials in the extended Shenoy-Shafer architecture for inference in hybrid BNs that can include deterministic variables. MOP approximations have several advantages over MTE approximations of PDFs. They are easier to find, even for multi-dimensional conditional PDFs, and are applicable for a larger class of deterministic functions in hybrid BNs.     

Qualitative possibilistic influence diagrams based on qualitative possibilistic utilities

This paper proposes a new approach for decision making under uncertainty based on influence diagrams and possibility theory. The so-called qualitative possibilistic influence diagrams extend standard influence diagrams in order to avoid difficulties attached to the specification of both probability distributions relative to chance nodes and utilities relative to value nodes. In fact, generally, it is easier for experts to quantify dependencies between chance nodes qualitatively via possibility distributions and to provide a preferential relation between different consequences. In such a case, the possibility theory offers a suitable modeling framework. Different combinations of the quantification between chance and utility nodes offer several kinds of possibilistic influence diagrams. This paper focuses on qualitative ones and proposes an indirect evaluation method based on their transformation into possibilistic networks. The proposed approach is implemented via a possibilistic influence diagram toolbox (PIDT).     

Extended Shenoy-Shafer architecture for inference in hybrid bayesian networks with deterministic conditionals

The main goal of this paper is to describe an architecture for solving large general hybrid Bayesian networks (BNs) with deterministic conditionals for continuous variables using local computation. In the presence of deterministic conditionals for continuous variables, we have to deal with the non-existence of the joint density function for the continuous variables. We represent deterministic conditional distributions for continuous variables using Dirac delta functions. Using the properties of Dirac delta functions, we can deal with a large class of deterministic functions. The architecture we develop is an extension of the Shenoy-Shafer architecture for discrete BNs. We extend the definitions of potentials to include conditional probability density functions and deterministic conditionals for continuous variables. We keep track of the units of continuous potentials. Inference in hybrid BNs is then done in the same way as in discrete BNs but by using discrete and continuous potentials and the extended definitions of combination and marginalization. We describe several small examples to illustrate our architecture. In addition, we solve exactly an extended version of the crop problem that includes non-conditional linear Gaussian distributions and non-linear deterministic functions.     

Inference in hybrid Bayesian networks with mixtures of truncated exponentials

Mixtures of truncated exponentials (MTE) potentials are an alternative to discretization for solving hybrid Bayesian networks. Any probability density function (PDF) can be approximated with an MTE potential, which can always be marginalized in closed form. This allows propagation to be done exactly using the Shenoy–Shafer architecture for computing marginals, with no restrictions on the construction of a join tree. This paper presents MTE potentials that approximate an arbitrary normal PDF with any mean and a positive variance. The properties of these MTE potentials are presented, along with examples that demonstrate their use in solving hybrid Bayesian networks. Assuming that the joint density exists, MTE potentials can be used for inference in hybrid Bayesian networks that do not fit the restrictive assumptions of the conditional linear Gaussian (CLG) model, such as networks containing discrete nodes with continuous parents.     

A latent variables approach for clustering mixed binary and continuous variables within a Gaussian mixture model

For clustering objects, we often collect not only continuous variables, but binary attributes as well. This paper proposes a model-based clustering approach with mixed binary and continuous variables where each binary attribute is generated by a latent continuous variable that is dichotomized with a suitable threshold value, and where the scores of the latent variables are estimated from the binary data. In economics, such variables are called utility functions and the assumption is that the binary attributes (the presence or the absence of a public service or utility) are determined by low and high values of these functions. In genetics, the latent response is interpreted as the ??liability?? to develop a qualitative trait or phenotype. The estimated scores of the latent variables, together with the observed continuous ones, allow to use a multivariate Gaussian mixture model for clustering, instead of using a mixture of discrete and continuous distributions. After describing the method, this paper presents the results of both simulated and real-case data and compares the performances of the multivariate Gaussian mixture model and of a mixture of joint multivariate and multinomial distributions. Results show that the former model outperforms the mixture model for variables with different scales, both in terms of classification error rate and reproduction of the clusters means.     

Solving influence diagrams with fuzzy chance and value nodes

In this paper we discuss how influence diagrams are affected by the presence of fuzziness in chance and value nodes. In this way, by modelling fuzzy-valued random variables and utilities in terms of fuzzy random variables, we analyze the statistical rules corresponding to the affected value-preserving transformations, namely: chance node removal and decision node removal. Some supporting results on fuzzy random variables introduced in this paper will provide us with the required mathematical tool to formalize the new statistical rules. Finally, an example is included to illustrate the study in the paper.     

离散型与连续型分布互为对偶的根源

互为对偶的离散型分布与连续型分布,可以看作是由同一个函数——源函数产生的。源函数的正线性组合、乘积和负导数,仍然是源函数。源函数揭示了互为对偶的分布的分布函数之间的相互关系,并能用来求随机变量的数字特征、特征函数、概率母函数、分布的最大值和参数的极大似然估计.     

Application of multiroot decision diagrams for integer functions

New data structures for representation of integer functions and matrices are proposed, namely, multiroot binary decision diagrams (MRBDD). Algorithms for performing standard operations on functions and matrices represented by MRBDDs are presented. Thanks to the more efficient reuse of structural elements, representation by multiroot binary decision diagrams is more efficient than the widely used multiterminal binary decision diagrams (MTBDD). Experimental results are given, which show that multiroot binary decision diagrams are a promising alternative to multiterminal binary decision diagrams, in particular, in probabilistic verification, manipulation of probability distributions, analysis of Petri nets, and other computational models.     

Variable elimination for influence diagrams with super value nodes

In the original formulation of influence diagrams (IDs), each model contained exactly one utility node. In 1990, Tatman and Shachtar introduced the possibility of having super value nodes that represent a combination of their parents’ utility functions. They also proposed an arc-reversal algorithm for IDs with super value nodes. In this paper we propose a variable-elimination algorithm for influence diagrams with super value nodes which is faster in most cases, requires less memory in general, introduces much fewer redundant (i.e., unnecessary) variables in the resulting policies, may simplify sensitivity analysis, and can speed up inference in IDs containing canonical models, such as the noisy OR.     

Parameter estimation and model selection for mixtures of truncated exponentials

Bayesian networks with mixtures of truncated exponentials (MTEs) support efficient inference algorithms and provide a flexible way of modeling hybrid domains (domains containing both discrete and continuous variables). On the other hand, estimating an MTE from data has turned out to be a difficult task, and most prevalent learning methods treat parameter estimation as a regression problem. The drawback of this approach is that by not directly attempting to find the parameter estimates that maximize the likelihood, there is no principled way of performing subsequent model selection using those parameter estimates. In this paper we describe an estimation method that directly aims at learning the parameters of an MTE potential following a maximum likelihood approach. Empirical results demonstrate that the proposed method yields significantly better likelihood results than existing regression-based methods. We also show how model selection, which in the case of univariate MTEs amounts to partitioning the domain and selecting the number of exponential terms, can be performed using the BIC score.     

Supermodular Functions on Finite Lattices

The supermodular order on multivariate distributions has many applications in financial and actuarial mathematics. In the particular case of finite, discrete distributions, we generalize the order to distributions on finite lattices. In this setting, we focus on the generating cone of supermodular functions because the extreme rays of that cone (modulo the modular functions) can be used as test functions to determine whether two random variables are ordered under the supermodular order. We completely determine the extreme supermodular functions in some special cases.     

Nonnormal deterministic equivalents and a transformation in stochastic mathematical programming

This paper considers random variables of the continuous type in a stochastic programming problem and presents (1) a general approach to the development of deterministic equivalents of constraints to be satisfied within certain probability limits, and (2) a deterministic transformation of a stochastic programming problem with random variables in the objective function. Deterministic equivalents are developed for constraints containing uniform random variables, but the approach used can be applied to other types of continuous random variables, as well. When the random variables appear in the objective function, a deterministic transformation of the stochastic programming problem is obtained to yield a closed-form solution without resort to a Monte Carlo computer simulation. Extension of this approach to stochastic problems with discrete random variables and integer decision variables is discussed briefly. A numerical example is presented.     

Stochastic chance constrained mixed-integer nonlinear programming models and the solution approaches for refinery short-term crude oil scheduling problem

Stochastic chance constrained mixed-integer nonlinear programming (SCC-MINLP) models are developed in this paper to solve the refinery short-term crude oil scheduling problem which concerns crude oil unloading, mixing, transferring and multilevel inventory control under demands uncertainty of distillation units. The objective of these models is the minimum expected value of total operation cost. It is the first time that the uncertain demands of Crude oil Distillation Units (CDUs) in these problems are set as random variables which have discrete and continuous joint probability distributions. This situation is close to the real world industry use. To reduce the computation complexity, these SCC-MINLP models are transformed into their equivalent stochastic chance constrained mixed-integer linear programming models (SCC-MILP). Stochastic simulation and stochastic sampling technologies are introduced in detail to solve these complex SCC-MILP models. Finally, case studies are effectively solved with the proposed approaches.     

Stochastic programming problems with generalized integrated chance constraints

If the constraints in an optimization problem are dependent on a random parameter, we would like to ensure that they are fulfilled with a high level of reliability. The most natural way is to employ chance constraints. However, the resulting problem is very hard to solve. We propose an alternative formulation of stochastic programs using penalty functions. The expectations of penalties can be left as constraints leading to generalized integrated chance constraints, or incorporated into the objective as a penalty term. We show that the penalty problems are asymptotically equivalent under quite mild conditions. We discuss applications of sample-approximation techniques to the problems with generalized integrated chance constraints and propose rates of convergence for the set of feasible solutions. We will direct our attention to the case when the set of feasible solutions is finite, which can appear in integer programming. The results are then extended to the bounded sets with continuous variables. Additional binary variables are necessary to solve sample-approximated chance-constrained problems, leading to a large mixed-integer non-linear program. On the other hand, the problems with penalties can be solved without adding binary variables; just continuous variables are necessary to model the penalties. The introduced approaches are applied to the blending problem leading to comparably reliable solutions.     

Cycle-transitive comparison of independent random variables

The discrete dice model, previously introduced by the present authors, essentially amounts to the pairwise comparison of a collection of independent discrete random variables that are uniformly distributed on finite integer multisets. This pairwise comparison results in a probabilistic relation that exhibits a particular type of transitivity, called dice-transitivity. In this paper, the discrete dice model is generalized with the purpose of pairwisely comparing independent discrete or continuous random variables with arbitrary probability distributions. It is shown that the probabilistic relation generated by a collection of arbitrary independent random variables is still dice-transitive. Interestingly, this probabilistic relation can be seen as a graded alternative to the concept of stochastic dominance. Furthermore, when the marginal distributions of the random variables belong to the same parametric family of distributions, the probabilistic relation exhibits interesting types of isostochastic transitivity, such as multiplicative transitivity. Finally, the probabilistic relation generated by a collection of independent normal random variables is proven to be moderately stochastic transitive.     

Pseudo-criteria versus linear utility function in stochastic multi-criteria acceptability analysis

Stochastic multi-criteria acceptability analysis (SMAA) is a multi-criteria decision support method for multiple decision-makers (DMs) in discrete problems. SMAA does not require explicit or implicit preference information from the DMs. Instead, the method is based on exploring the weight space in order to describe the valuations that would make each alternative the preferred one. Partial preference information can be represented in the weight space analysis through weight distributions. In this paper we compare two variants of the SMAA method using randomly generated test problems with 2–12 criteria and 4–12 alternatives. In the original SMAA, a utility or value function models the DMs' preference structure, and the inaccuracy or uncertainty of the criteria is represented by probability distributions. In SMAA-3, ELECTRE III-type pseudo-criteria are used instead. Both methods compute for each alternative an acceptability index measuring the variety of different valuations that supports this alternative, and a central weight vector representing the typical valuations resulting in this decision. We seek answers to three questions: (1) how similar are the results provided by the decision models, (2) what kind of systematic differences exists between the models, and (3) how could one select indifference and preference thresholds of the pseudo-criteria model to match a utility model with given probability distributions?     

Dynamic project selection and funding under risk: A decision tree based MILP approach

This paper presents a mixed integer linear programming (MILP) model for a new class of dynamic project selection and funding problems under risk given multiple scarce resources of different qualifications. The underlying stochastic decision tree concept extends classical approaches mainly in that it adds a novel node type that allows for the continuous control of discrete branching probability distributions. The control functions are piecewise linear and are convex for the costs and concave for the benefits. The MILP-model has been embedded in a prototype Decision Support System (DSS). With respect to the proposed solution the DSS provides complete probability distributions for both costs and benefits.     

A model for dynamic chance constraints in hydro power reservoir management

In this paper, a model for (joint) dynamic chance constraints is proposed and applied to an optimization problem in water reservoir management. The model relies on discretization of the decision variables but keeps the probability distribution continuous. Our approach relies on calculating probabilities of rectangles which is particularly useful in the presence of independent random variables but works equally well in the case of correlated variables. Numerical results are provided for two and three stages.     

A model for decision problems with continuous time parameter

The concept of statistical decision theory concerning sequential observations is generalized to decision problems, which are based upon a continuous stochastic process.

In this model decision functions are introduced, consisting of a stopping time and a terminal decision rule. A method of discretization shows the connections between the discrete sequential and the continuous model. Concerning Bayes problems we find, that under certain assumptions the decision problem can be viewed as an optimal stopping problem with continuous time parameter.