Approximate inference in Bayesian networks using binary probability trees

The present paper introduces a new kind of representation for the potentials in a Bayesian network: Binary Probability Trees. They enable the representation of context-specific independences in more detail than probability trees. This enhanced capability leads to more efficient inference algorithms for some types of Bayesian networks. This paper explains the procedure for building a binary probability tree from a given potential, which is similar to the one employed for building standard probability trees. It also offers a way of pruning a binary tree in order to reduce its size. This allows us to obtain exact or approximate results in inference depending on an input threshold. This paper also provides detailed algorithms for performing the basic operations on potentials (restriction, combination and marginalization) directly to binary trees. Finally, some experiments are described where binary trees are used with the variable elimination algorithm to compare the performance with that obtained for standard probability trees.     

Computing in fault tolerant broadcast networks and noisy decision trees

We consider a fault tolerant broadcast network of n processors each holding one bit of information. The goal is to compute a given Boolean function on the n bits. In each step, a processor may broadcast one bit of information. Each listening processor receives the bit that was broadcast with error probability bounded by a fixed constant ?. The errors in different steps, as well as for different receiving processors in the same step, are mutually independent. The protocols that are considered in this model are oblivious protocols: At each step, the processors that broadcast are fixed in advanced and independent of the input and the outcome of previous steps. We present here the first linear complexity protocols for several classes of Boolean functions. This answer an open question of Yao (Invited talk in the 5th ISTCS Conf., 1997), considering this fault tolerant model that was introduced by El Gamal (Open problems presented at the 1984 workshop on Specific Problems in Communication and Computation sponsored by Bell Communication Research) and studied also by Gallager 10 . © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Dynamic importance sampling in Bayesian networks based on probability trees

In this paper we introduce a new dynamic importance sampling propagation algorithm for Bayesian networks. Importance sampling is based on using an auxiliary sampling distribution from which a set of configurations of the variables in the network is drawn, and the performance of the algorithm depends on the variance of the weights associated with the simulated configurations. The basic idea of dynamic importance sampling is to use the simulation of a configuration to modify the sampling distribution in order to improve its quality and so reducing the variance of the future weights. The paper shows that this can be achieved with a low computational effort. The experiments carried out show that the final results can be very good even in the case that the initial sampling distribution is far away from the optimum.     

Bayesian graphical model determination using decision theory

Bayesian model determination in the complete class of graphical models is considered using a decision theoretic framework within the regular exponential family. The complete class contains both decomposable and non-decomposable graphical models. A utility measure based on a logarithmic score function is introduced under reference priors for the model parameters. The logarithmic utility of a model is decomposed into predictive performance and relative complexity. Axioms of decision theory lead to the judgement of the plausibility of a model in terms of the posterior expected utility. This quantity has an analytic expression for decomposable models when certain reference priors are used and the exponential family is closed under marginalization. For non-decomposable models, a simulation consistent estimate of the expectation can be obtained. Both real and simulated data sets are used to illustrate the introduced methodology.     

Bayesian networks with a logistic regression model for the conditional probabilities

Logistic regression techniques can be used to restrict the conditional probabilities of a Bayesian network for discrete variables. More specifically, each variable of the network can be modeled through a logistic regression model, in which the parents of the variable define the covariates. When all main effects and interactions between the parent variables are incorporated as covariates, the conditional probabilities are estimated without restrictions, as in a traditional Bayesian network. By incorporating interaction terms up to a specific order only, the number of parameters can be drastically reduced. Furthermore, ordered logistic regression can be used when the categories of a variable are ordered, resulting in even more parsimonious models. Parameters are estimated by a modified junction tree algorithm. The approach is illustrated with the Alarm network.     

Existence of solution to a model for gas transportation networks on non-flat topography

In this paper we prove the existence of solution to a mathematical model for gas transportation networks on non-flat topography. Firstly, the network topology is represented by a directed graph and then a nonlinear system of numerical equations is introduced whose unknowns are the pressures at the nodes and the mass flow rates at the edges of the graph. This system is written in a compact vector form in terms of the vector of the square pressures at the nodes and then an existence result is proved under some simplifying assumptions. The proof is done in two steps: the first one uses convex analysis tools and the second one the Brouwer fixed-point theorem.     

An anisotropic continuum model for traffic assignment in mixed transportation networks

This work deals with a two-dimensional continuum model for the problem of congested traffic assignment in an urban transportation system consisting of a set of freeways superimposed over a dense street network. The formulation leads to a system of non-linear differential equations whose unknowns are given by the travel times from arbitrary points of the network to the corresponding destinations. The governing equations are appropriately solved by means of the Finite Element Method. Then, traffic flow on every link of the network can be obtained. Numerical examples are given in order to demonstrate the efficiency of the developed model.     

Bayesian priors in sequential binomial design

The status of sequential analysis in Bayesian inference is revisited. The information on the experimental design, including the stopping rule, is one part of the evidence, prior to the sampling. Consequently this information must be incorporated in the prior distribution. This approach allows to relax the likelihood principle when appropriate. It is illustrated in the case of successive Binomial trials. Using Jeffreys' rule, a prior based on the Fisher information and conditional on the design characteristics is derived. The corrected Jeffreys prior, which involves a new distribution called Beta-J, extends the classical Jeffreys priors for the Binomial and Pascal sampling models to more general stopping rules. As an illustration, we show that the correction induced on the posterior is proportional to the bias induced by the stopping rule on the maximum likelihood estimator. To cite this article: P. Bunouf, B. Lecoutre, C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

Systemic decision making in AHP: a Bayesian approach

Systemic decision making is a new approach for dealing with complex multiactor decision making problems in which the actors’ individual preferences on a fixed set of alternatives are incorporated in a holistic view in accordance with the “principle of tolerance”. The new approach integrates all the preferences, even if they are encapsulated in different individual theoretical models or approaches; the only requirement is that they must be expressed as some kind of probability distribution. In this paper, assuming the analytic hierarchy process (AHP) is the multicriteria technique employed to rank alternatives, the authors present a new methodology based on a Bayesian analysis for dealing with AHP systemic decision making in a local context (a single criterion). The approach integrates the individual visions of reality into a collective one by means of a tolerance distribution, which is defined as the weighted geometric mean of the individual preferences expressed as probability distributions. A mathematical justification of this distribution, a study of its statistical properties and a Monte Carlo method for drawing samples are also provided. The paper further presents a number of decisional tools for the evaluation of the acceptance of the tolerance distribution, the construction of tolerance paths that increase representativeness and the extraction of the relevant knowledge of the subjacent multiactor decisional process from a cognitive perspective. Finally, the proposed methodology is applied to the AHP-multiplicative model with lognormal errors and a case study related to a real-life experience in local participatory budgets for the Zaragoza City Council (Spain).     

弹性需求下路段相互影响的交通网络均衡模型

本文利用网络用户均衡原理,对弹性需求下路段相互影响的交通配流问题进行研究,给了弹性需求下路段相互影响的网络均衡条件,建立了与均衡条件等价的变分不等式模型,论证了模型解的存在性和唯一性.     

Nonparametric adaptive detection in fading channels based on sequential Monte Carlo and Bayesian model averaging

Recently, a Bayesian receiver for blind detection in fading channels has been proposed by Chen, Wang and Liu (200,IEEE Trans. Inform. Theory,46, 2079–2094), based on the sequential Monte Carlo methodology. That work is built on a parametric modelling of the fading process in the form of a state-space model, and assumes the knowledge of the second-order statistics of the fading channel. In this paper, we develop a nonparametric approach to the problem of blind detection in fading channels, without assuming any knowledge of the channel statistics. The basic idea is to decompose the fading process using a wavelet basis, and to use the sequential Monte Carlo technique to track both the wavelet coefficients and the transmitted symbols. Moreover, the algorithm is adaptive to time varying speed/smoothness in the fading process and the uncertainty on the number of wavelet coefficients (shrinkage order) needed. Simulation results are provided to demonstrate the excellent performance of the proposed blind adaptive receivers. This work was supported in part by the U.S. National Science Foundation (NSF) under grants CCR-9875314, CCR-9980599, DMS-9982846, DMS-0073651 and DMS-0073601.     

A rule-based risk decision-making approach and its application in China's customs inspection decision

This paper addresses a kind of risk decision-making problem existing widely in public administration and business management, which is characterized by (1) occurrence probabilities of states of nature can be estimated by analysing historical observations, but historical observations of different objects are unhomogeneous, (2) the relation between observations and occurrence probabilities of states of nature are affected by some qualitative and quantitative indicators, (3) it is a real-time decision-making problem, that is, there are many decisions for different objects to be made in a limited time, (4) considering decision's execution, impact of resource constrains is an important issue in decision-making process. In this paper, we develop a rule-based approach to address the problem. In the proposed approach, a two-step clustering method is employed to classify objects into categories, and observations in each category can be approximately viewed as homogeneous. For objects in each category, occurrence probabilities of states of nature are estimated by logistic regression, and the decision rule is obtained through solving an optimization model, which is to minimize the total decision risks while satisfying resource constrains. Effect and efficacy of our approach are illustrated through its application to China's customs inspection decision.     

Multi-objective evacuation routing in transportation networks

In this paper, the optimal design and analysis of evacuation routes in transportation networks is examined. An methodology for optimal egress route assignment is suggested. An integer programming (IP) formulation for optimal route assignment is presented, which utilizes M/G/c/c state dependent queueing models to cope with congestion and time delays on road links. M/G/c/c simulation software is used to evaluate performance measures of the evacuation plan: clearance time, total travelled distance and blocking probabilities. Extensive experimental results are included.     

Dynamic conditional value-at-risk model for routing and scheduling of hazardous material transportation networks

This paper illustrates a dynamic model of conditional value-at-risk (CVaR) measure for risk assessment and mitigation of hazardous material transportation in supply chain networks. The well-established market risk measure, CVaR, which is commonly used by financial institutions for portfolio optimizations, is investigated. In contrast to previous works, we consider CVaR as the main objective in the optimization of hazardous material (hazmat) transportation network. In addition to CVaR minimization and route planning of a supply chain network, the time scheduling of hazmat shipments is imposed and considered in the present study. Pertaining to the general dynamic risk model, we analyzed several scenarios involving a variety of hazmats and time schedules with respect to optimal route selection and CVaR minimization. A solution algorithm is then proposed for solving the model, with verifications made using numerical examples and sensitivity analysis.     

On essential information in sequential decision processes

This paper provides sufficient conditions when certain information about the past of a stochastic decision processes can be ignored by a controller. We illustrate the results with particular applications to queueing control, control of semi-Markov decision processes with iid sojourn times, and uniformization of continuous-time Markov decision processes. Mathematics Subject Classification (2000): Primary 60K25, Secondary 90C40     

Computing upper and lower bounds in interval decision trees

This article presents algorithms for computing optima in decision trees with imprecise probabilities and utilities. In tree models involving uncertainty expressed as intervals and/or relations, it is necessary for the evaluation to compute the upper and lower bounds of the expected values. Already in its simplest form, computing a maximum of expectancies leads to quadratic programming (QP) problems. Unfortunately, standard optimization methods based on QP (and BLP – bilinear programming) are too slow for the evaluation of decision trees in computer tools with interactive response times. Needless to say, the problems with computational complexity are even more emphasized in multi-linear programming (MLP) problems arising from multi-level decision trees. Since standard techniques are not particularly useful for these purposes, other, non-standard algorithms must be used. The algorithms presented here enable user interaction in decision tools and are equally applicable to all multi-linear programming problems sharing the same structure as a decision tree.     

Integrating transportation and production: an international study case

The problem we study is inspired by the real case of Mesdan S.p.A., an Italian company worldwide leader in the textile machinery sector, which has two production units with two warehouses, one located in Italy (Brescia) and the other in China (Foshan). The critical point in this logistic system is the integration between production and transportation management, given the long distance between Brescia and Foshan. Shipments are performed by the means of different types of vehicles with different unit costs and significantly different lead times. Variable production costs, variable and fixed transportation costs and, possibly, inventory costs are charged in the objective function. Different production policies are compared. Our aim is to determine integrated policies that minimize the total cost of the system. We formulate integer linear programming models for the solution of these problems, and we solve the real instance and carry out a sensitivity analysis of the optimal solution.     

Discovering causes and effects of a given node in Bayesian networks

Causal relationships among variables can be depicted by a causal network of these variables. We propose a local structure learning approach for discovering the direct causes and the direct effects of a given target variable. In the approach, we first find the variable set of parents, children, and maybe some descendants (PCD) of the target variable, but generally we cannot distinguish the parents from the children in the PCD of the target variable. Next, to distinguish the causes from the effects of the target variable, we find the PCD of each variable in the PCD of the target variable, and we repeat the process of finding PCDs along the paths starting from the target variable. Without constructing a whole network over all variables, we find only a local structure around the target variable. Theoretically, we show the correctness of the proposed approach under the assumptions of faithfulness, causal sufficiency, and that conditional independencies are correctly checked.