Efficient Bayesian network modeling of systems

https://doi.org/10.1016/j.ress.2012.11.017Get rights and content

Abstract

The Bayesian network (BN) is a convenient tool for probabilistic modeling of system performance, particularly when it is of interest to update the reliability of the system or its components in light of observed information. In this paper, BN structures for modeling the performance of systems that are defined in terms of their minimum link or cut sets are investigated. Standard BN structures that define the system node as a child of its constituent components or its minimum link/cut sets lead to converging structures, which are computationally disadvantageous and could severely hamper application of the BN to real systems. A systematic approach to defining an alternative formulation is developed that creates chain-like BN structures that are orders of magnitude more efficient, particularly in terms of computational memory demand. The formulation uses an integer optimization algorithm to identify the most efficient BN structure. Example applications demonstrate the proposed methodology and quantify the gained computational advantage.

Introduction

Engineering decisions often involve probabilistic assessment of the state of a system under evolving and uncertain information. For example, in the immediate aftermath of a natural disaster, such as an earthquake affecting an urban community, decisions must be made regarding dispatch of rescue teams and inspection crews, continued operation or closure of facilities, and prioritization of repair actions and restoration of services, all of which depend on the assessment of the functioning states of various infrastructural systems. Such assessment is strongly influenced by the available information, which in the immediate aftermath of a natural disaster is highly uncertain and rapidly evolves as the states of various system components are observed or measurements of the hazard are made. Another example is the management of a deteriorating system, where decisions need to be made on the frequency and extent of inspections and on maintenance, repair and replacement actions, while future capacities and demands of the system remain uncertain. In both cases, there is need for a method to update the probabilistic assessment of the system state as information, often of uncertain type, becomes available from measurements, inspections, and other observations of the system and its components.

The Bayesian network (BN) is an ideal framework for the analysis of such systems, particularly when updating of the probabilistic model in light of evolving and uncertain information is an important objective. The BN is a graphical model consisting of nodes and directed links, which respectively represent random variables and their probabilistic dependencies [20], [11]. The variables may represent the states of the components of a system, or their capacities and demands. The BN provides a convenient means for modeling dependence between the component states, which is rather difficult in most classical system reliability methods [19]. Furthermore, upon entering evidence on one or more variables, e.g., the observed states, capacities or demands of a subset of the components, the information propagates throughout the network and updates distributions of other random variables, e.g., the states of other components and the system, in accordance with the Bayes' rule. Finally, by addition of decision and utility nodes, the BN renders a decision graph that facilitates decision-making in accordance with the maximum expected utility criterion [22], [11].

This paper focuses on the development of a systematic approach to using BNs for modeling the performance of systems that are defined in terms of their minimum link sets (MLSs) or minimum cut sets (MCSs). The methodology presented in this paper is motivated by our efforts in modeling the performance of spatially distributed civil infrastructure systems (e.g., a highway network or water distribution system) subjected to an earthquake hazard, with particular emphasis on post-earthquake risk assessment and decision making (see Bensi et al. [1]). For such an application, efficient computations and near real-time inference in models of large systems are essential. Furthermore, the considered systems are more easily characterized in terms of their MLSs/MCSs than by other means, such as fault trees, event trees or reliability block diagrams. While this paper was motivated by this specific application, the methods presented are applicable to a broader scope of problems.

The BN has been used in the past for system reliability analysis (see, e.g., [25], [17], [2], [8], [15], [12], [23], [24]). Some of these works consider intuitive approaches to modeling systems as BNs (e.g., [8]). Others consider the fault tree (e.g., [15], [2]) or the reliability block diagram (e.g., [25]) as the native source of system information. Other papers develop BNs for relatively simple systems, for which computational demands are not of particular concern. This work differs from previous efforts by defining a systematic approach to developing an efficient BN structure for modeling the reliability of complex systems when the MLSs or MCSs are the native source of system information. The approach is particularly useful when working with topologically defined systems, in which the system decomposition is commonly done through the MLSs and/or MCSs. While other authors have used BNs to model systems that are topologically defined through a reliability block diagram (e.g., [25]), no systematic attempt has been made to optimize the BN structure, particularly when working with large, multi-state systems. It turns out that conventional BN models rapidly grow in size and density with increasing size of the system, so that even for moderately sized systems the computational and memory demands make the model infeasible, especially when using exact inference algorithms with multi-state nodes. With this shortcoming in mind, in this paper we develop methods for generating efficient BN topologies for modeling systems with binary and multi-state components. A discrete optimization algorithm is developed that minimizes the density of the BN, thereby providing orders of magnitude savings in computational time and memory. This development facilitates consideration of systems, which otherwise could not be solved with conventional BN formulations.

The paper begins with a brief introduction to the BN. The introduction is limited to those aspects that are needed to motivate the remainder of the paper. Next, efficient Bayesian network formulations for modeling series and parallel systems with binary components are presented. These are then extended to general systems with binary and multi-state components. To automate construction of the efficient Bayesian network formulations, a binary integer optimization problem is formulated. Furthermore, two heuristic augmentations are presented to reduce the size of the optimization problem. Several examples demonstrate the proposed methodology and its effectiveness.

Section snippets

Brief introduction to Bayesian networks

A BN is characterized by a directed acyclic graph consisting of a set of nodes representing random variables and a set of links representing probabilistic dependencies. In this paper, we limit the treatment to BNs in which all random variables are discrete; the reader interested in BNs with continuous random variables is referred to Langseth et al. [13]. Consider the simple BN in Fig. 1. The directed links from X1 and X2 to X3 indicate that the distribution of X3 is defined conditioned on X1

Modeling system performance via Bayesian network

Consider a system of Nc components, with component i having ni discrete states. The number of distinct configurations of the system is i=1Ncni. We refer to a BN formulation that defines the system state directly in terms of the states of its constituent components as the naïve BN formulation. Fig. 2 shows one such BN, where node Ci defines the state of component i and node Ssys defines the state of the system. If the system has Ns discrete states, then the CPT associated with the system node

Binary components and system

Consider a system with binary component and system states, say survival/fail states. A minimal link set (MLS) is a minimum set of components whose joint survival constitutes survival of the system. The minimal link set BN formulation introduces intermediate nodes between the component and system nodes, which represent the states of the MLSs, as shown in Fig. 3. Torres-Toledano and Sucar [25] used such a BN formulation for modeling system performance, though with less formality and generality

Motivation

The MLS and MCS formulations described in the preceding section result in converging BN structures. In general, BN structures with nodes arranged in chains are significantly more efficient than those having converging structures. As we will show later, the two BN structures shown in Fig. 5 represent the same system. Fig. 5a shows a converging structure similar to the BN models presented in the previous section, and Fig. 5b illustrates a chain structure. In both BNs, dependence among the

Optimal ordering of survival path events

The aim of this section is to formalize the problem of finding the optimal arrangement of SPEs in SPSs for a general system. Let L(im,jn)=1 indicate the existence of a directed link from node Es,im to node Es,jn in the efficient MLS BN formulation and L(im,jn)=0 indicate the absence of such a link, where i and j are component indices and m and n are indices denoting the instances of these SPE nodes in the BN. Also, let Cim=1 indicate a directed link between the node representing component i and

Heuristic augmentation

As mentioned earlier, the binary optimization problem described above rapidly grows in size due to the requirement to consider all permutations of component indices and instances. To overcome this problem, in this section we present two heuristics: One aims at reducing the number of components that need to be considered, and one aims at reducing the number of permutations. Additional heuristics can be developed to further improve the performance and scalability of the optimization algorithm

Conclusions

This paper develops efficient BN formulations for modeling the performance of general systems for which the MLSs or MCSs are known. We show that BNs with nodes in chain structures are more efficient than when nodes are arranged in converging topologies. We demonstrate how BNs with nodes arranged in chain structures are constructed for series and parallel systems. This idea is then extended to develop similar topologies for general systems. Additionally, the idea is extended to consider

Acknowledgment

This research was supported by the State of California through the Transportation Systems Research Program of the Pacific Earthquake Engineering Research Center (PEER). Additional support was provided by the Taisei Chair in Civil Engineering at the University of California, Berkeley. The first author also gratefully acknowledges support from a National Science Foundation graduate research fellowship. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of

References (27)

  • LR Ford et al.

    Maximal flow through a network

    Canadian Journal of Mathematics

    (1956)
  • Friis-Hansen P, Structuring of complex systems using Bayesian Networks. In O. Ditlevsen & P. Friis-Hansen, eds....
  • Holmström K. Tomlab optimization environment, Available at: 〈http://tomopt.com/tomlab/〉,...
  • Cited by (97)

    • Dynamic Bayesian network model to study under-deposit corrosion

      2023, Reliability Engineering and System Safety
    View all citing articles on Scopus
    1

    Formerly of University of California, Berkeley, CA 94720, USA.

    2

    Disclaimer: Any opinions, findings and conclusions expressed in this paper are those of the author and do not necessarily reflect the views of the United States Nuclear Regulatory Commission.

    View full text