Efficient Bayesian network modeling of systems
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 . 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 to node 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 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)
Improving the analysis of dependable systems by mapping fault trees into Bayesian networks
Reliability Engineering & System Safety
(2001)- et al.
Multi-scale reliability analysis and updating of complex systems by use of linear programming
Reliability Engineering & System Safety
(2008) Inference in hybrid Bayesian networks
Reliability Engineering & System Safety
(2009)Belief update in CLG Bayesian networks with lazy propagation
International Journal of Approximate Reasoning
(2008)- et al.
Bayesian networks for system reliability reassessment
Structural Safety
(2001) - et al.
Importance sampling algorithms for Bayesian networks: principles and performance
Mathematical and Computer Modelling
(2006) - Bensi M, Der Kiureghian A, Straub D. A Bayesian network methodology for infrastructure seismic risk assessment and...
Bucket elimination: a unifying framework for probabilistic inference
Uncertainty in Artificial Intelligence
(1996)- DSL. GeNIe 2.0 by Decision Systems Laboratory, Available at: 〈http://genie.sis.pitt.edu/〉...
- et al.
A note on the maximum flow through a network
Information Theory, IRE Transactions on
(1956)
Maximal flow through a network
Canadian Journal of Mathematics
Cited by (97)
Dynamic risk analysis of allision in port areas using DBN based on HFACS-PV
2024, Ocean EngineeringComputationally efficient approach for risk-informed decision making
2024, Progress in Nuclear EnergyTemporal noisy-adder of bayesian network for scalable consecutive-k-out-of-n:F system reliability analysis
2024, Reliability Engineering and System SafetyDynamic Bayesian network model to study under-deposit corrosion
2023, Reliability Engineering and System SafetyMulti-unit seismic probabilistic risk assessment: A Bayesian network perspective
2023, Reliability Engineering and System SafetyAnalyzing connectivity reliability and critical units for highway networks in high-intensity seismic region using Bayesian network
2022, Journal of Infrastructure Intelligence and Resilience
- 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.