This paper investigates the challenge of integrating intelligent systems into varying computational platforms and application mixes while providing reactive (or soft real-time) response. We integrate Bayesian network computation with feedback control, thereby achieving our reactive objective. As a case study we investigate fault diagnosis using Bayesian networks. While we consider the likelihood weighting and junction tree propagation Bayesian network inference algorithms in some detail, we hypothesize that the techniques developed can be broadly applied to achieve reactive intelligent systems. In this papers empirical study we demonstrate reactive fault diagnosis for an electrical power system.
Substantial progress has been made over the last few
decades in the areas of learning and reasoning using
Bayesian networks (BNs) [
The proliferation of computers of highly varying
capability provides new opportunities for AI systems and
also raises several interesting research questions [
While the architecture is general, we have for
validation purposes used experimental data from an
electrical power network located at the NASA Ames
Research Center [
By integrating control theoretic techniques and
uncertainty processing using BNs, this research aims
to: improve the reactivity and adaptability of
uncertainty processing in di¤erent applications; improve the
timeliness of computation under dynamic workloads
on varying computational platforms (smart phones,
GPUs, multi-core CPUs, Hadoop clusters, ...); and
reduce the e¤ort and cost associated with developing and
deploying BN-based software applications. Our goals
are similar to those of anytime algorithms [
We are investigating control theory as it applies to
software and our actuators are computational actuators
rather than control surfaces on an aircraft or wheels
on a robotic vehicle. For example, our actuators may
change the number of processes being handled by a
computer or the input parameters to C or Java
programs that implement algorithms for BN computation.
In contrast, the great majority of previous control
theory research has, with several notable exceptions in
computing and software [
The approach developed in this paper applies in situations where the computational load on a computer running AI (here, BN) applications is a key concern and where, simultaneously, we can prioritize and control the computational processes. Speci cally, we partition computational processes into highcriticality, medium-criticality, and low-criticality ; the high-critical processes are reactive. Our experiments are in the area of electrical power system diagnosis. However, the techniques are more widely applicable and we now outline a few areas where this approach may prove powerful. Examples of high-criticality tasks in which Bayesian networks (and similar probabilistic graphical models) can be used and for which one might want to provide a reactive response include medical monitoring, sensor fusion, speech recognition on a smartphone, gesture recognition, and video recognition. Examples of low-criticality tasks, which would be down-prioritized, suspended or killed by our approach (depending on circumstances) include virus scanning, backups, disk defragmentation, software updates, and volunteer computing (such as Seti@Home and Folding@Home).
What these applications have in common is that reactivity is important for some computational processes. However, reactivity is not important enough to warrant the use of a hard real-time operating system, which is often used in aerospace and other applications where safety is paramount. Our approach is tailored to soft real-time settings where low-criticality tasks can, if needed, be down-prioritized, suspended or terminated in order to provide reactive response for high-criticality tasks.
The rest of this paper is organized as follows. In Section 2 we provide background on Bayesian network computation, feedback control, and anytime algorithms. Section 3 discusses our architecture integrating feedback control and BN inference algorithms. In Section 4 we present the experimental setting and electrical power system data, while Section 5 discusses empirical results. We conclude and outline future research in Section 6. 2 2.1
BNs represent multivariate probability distributions
and are used for reasoning and learning under
uncertainty [
Di¤erent BN inference algorithms can be used to
perform the above BEL, MPE, and MAP computations.
We distinguish between exact and inexact algorithms.
Exact algorithms for BEL and MPE computation
include belief propagation in singly connected BNs
[
An anytime algorithm improves its solutions
according to the computational resource allocated to it, and
returns an (approximate) answer if interrupted [8].
Fundamentally, this iterative improvement algorithm
framework provides a way to trade o¤ between
computation time and solution quality. Anytime algorithms
are a useful tool for real-time system design, and there
are also results on the composition of anytime
algorithms [37]. Originally, the anytime approach was
developed for single agents, recently it was extended
to handle multiple agents [
Among BN inference algorithms, stochastic local
search [
Feedback control involves the manipulation of a
system in which data, either measured or estimated, is
transformed and utilized to modify the behavior of the
system. This behavior is typically de
ned in terms of
metrics such as stability, boundedness, response time,
or over-shoot. Improving such metrics by means of
feedback control is typically motivated by the desire
1 Pearls main emphasis was originally on exact
propagation in singly connected BNs, however he also mentioned
inexact propagation in arbitrary BNs [29, Exercise 4.7],
to achieve some higher level objective such as
ensuring a comfortable ride on a passenger transport jet, an
average production rate on a robotic assembly line, or
a maximal duration of a credit card transaction.
Recently, control theory has been applied to
computing systems including control of HTTP servers [
Our goal is to support the application of both nonanytime and anytime BN inference algorithms in reactive settings by introducing techniques from feedback control. A key concept in feedback control is the plant. Here, the plant to be controlled is a dynamic system operating in the discrete time domain. This de nition encompasses computers including mobile phones, tablets, laptops, desktops, and multi-core systems. In this paper, the plant is a digital computer performing a high-criticality (or reactive) process. The reactive process runs, in our case, a BN used for diagnosis. We also assume that on this computer, lowand medium-criticality (or background ) processes are running and are competing for CPU cycles, memory, and other computer resources. The impact that these background processes have on the reactive process and its ultimate outcome (detection of a failure event) depends on a number of parameters such as operating system, RAM, processor type and clock-speed, CPU cache, etc. Since hardware and software vary immensely, this represents a source of signi cant uncertainty and presents challenges for both modeling and control.
We introduce the control system framework illustrated
in Figure 1. The framework supports both anytime
(and inexact) as well as non-anytime (and typically
exact) algorithms, and distinguishes between inner and
outer control loops because their objectives di¤er.
Inner Loop: The goal of the inner loop, which is
traditional to feedback control, is to make careful
adjustments according to the parameters set by the outer
loop. These are key parameters in our integrated
approach: r(k) is desired completion time (or Setpoint )
for sample time k. We would like the computational
process to
nish within this time. y(k) is the actual
completion time (or just Actual ) for sample time k.
e(k) = r(k) - y(k) is the error signal at time k; u(k)
is the maximal number of low-criticality processes (or
Max Processes). u(k), also known as the control law,
is taken to be a proportional-derivative controller [
Our approach uses simple black-box prediction techniques, as detailed below. It is the combination of this black-box approach with the use of a desired computation time (setpoint r(k) in Figure 1) and an actual computation time (output y(k) in Figure 1) that makes it work. The actual computation time is just a measurement of how long a BN computation took. The desired computation time depends on the frequency of our reactive process and other factors. For example, a frequency of 10 Hz means that the desired computation time is upper-bounded by 100 milliseconds. Outer Loop: The goal of the outer loop is to jointly optimize speed of inference, resource allocation, accuracy, and other factors. Unlike inexact anytime algorithms, which have a similar objective, our approach can use exact algorithms. If, for example, the exact junction tree propagation and variable elimination algorithms are employed, reduced accuracy is not an issue. However, accuracy is in general important, and accuracy versus computation time trade-o¤s are performed in the outer loop of the framework. For inexact particle-based algorithms such as likelihood weighting and particle ltering, p(k) the number of particles is an example of such a parameter. One would like to use a very large number of particles for simulation, since this improves the accuracy of the estimate of the posterior P (H(k) j e(k)), however this may take too much time and one needs to carefully restrict the number of particles. In most experimental results with likelihood weighting reported in this paper, we assume that p(k) = p and r(k) = r are xed (or stationary).2 4
System health management, which may utilize
Bayesian network, can integrate information from
heterogenous sensors and perform computation for the
purpose of fault diagnosis, prognosis, and mitigation
[
tal data from a real-world electrical power network,
known as ADAPT, located at the NASA Ames
Re2 However, in Section 5.3 (see Figure 6) we discuss how
and why r(k) can be changed over time.
Win7
Win7
Win7
Win7
Suse11
Suse11
Ubu9
Ubu9
Ubu11
Ubu11
search Center [
ers, representing a broad spectrum of computing capability, were used. The Laptop computer is a 2.40GHz Intel i5 M520 with 4 cores, 8 GB of RAM, and 3 MB cache memory. The Desktop computer is a 3.20GHz AMD Phenom II X6 1090T with 6 cores, 8 GB of RAM, and 3 MB cache memory. The High End computer is a 2.00GHz Intel Xeon X7550 with 64 cores, 126 GB of RAM, and 18 MB cache memory. The Server computer is a 2.50GHz Intel Core 2 Quad Q8300 with 4 cores, 8GB GB of RAM, and 2 MB cache memory. The Old Server computer is a 2.80GHz Intel Xeon with 4 cores, 4 GB of RAM, and 1 MB cache memory. Broadly speaking, the High End computer is most 3 http://www.dx-competition.org/ 4 http://code.google.com/p/bnt/ 5 The speci c BNT functions we use are pearl_inf_engine (PBP), belprop_inf_engine (LBP), likelihood_weighting_inf_engine (LW), jtree_inf_engine (JT), and var_elim_inf_engine (VE).
6 http://www.dx-competition.org/ powerful, due to its many cores and large memories, while the Old Server is least powerful due to its comparatively small memories. As reected in Table 1, the operating systems Windows 7 (Win7) and several Linux variantsUbuntu (Ubu9 and Ubu11) and Suse (Suse11) were employed in experiments.
Disturbance Generation: In the following, we model for simplicity low-criticality process disturbances to a computer (including user disturbances) as a Poisson process with rate . In the experiments, the low-criticality OS processes are CPU-intensive and execute mathematical operations in a tight loop; there is no I/O. This introduces a stochastic delay in the actuation of the plant: even if the control input u(k) increases at the next time step, u(k + 1) > u(k), the probability of the number of processes actually increasing is low. The Poisson disturbance term is regarded as unmodeled dynamics and is not explicitly compensated for in the error term of the ARX model (1). It is of interest to model this phenomenon by a stochastic delay in the control input to the plant.
Note that our approach handles situations in which the resource consumption of low-criticality processes varies dramatically. For example, there can be many low-criticality processes (executing in parallel) that are mostly idle. On the other hand, even a few resourcehungry low-criticality processes could be too much to handle. If many mostly idle processes are present, our controller automatically sets the Max number of processes parameter u(k) higher than if there are a few resource-hungry low-criticality processes. See Figure 6 and Figure 5 for how u(k) is varied by our controller, due to the varying computational load of lowcriticality and Bayesian network processes. The controller maps, see Figure 1, from a setpoint r(k) (Computation time) to a control signal u(k) (Max number of processes), and so is able to handle the varying resource use of di¤erent processes. 5
In this section we present experimental results on ADAPT data for our reactive approach, as enabled by feedback control and summarized in Figure 1. 5.1
Control Input: The input to the plant (i.e., the computer in Figure 1), which ultimately is computed by a control algorithm, is denoted by u(k). This input determines the number of low-criticality processes that are allowed to run at any given sample time. Denote the actual number of low-criticality processes by v(k) where k denotes a sampling index. In the exam(a) Junction tree propagation (JTP) (b) Likelihood weighting (LW) ples that are used in this paper, if v(k) u(k), then processes are terminated until v(k) < u(k).7 The termination process is nearly instantaneous with respect to the sampling period.
Plant Modeling: There are several approaches to the modeling of computation for control applications. The approach taken here is termed linear Auto-Regressive modeling with eXogenous input (linear ARX). Nonlinear approaches, such as discrete time neural networks, may also be used. Nonlinear modeling is more complex yet may be able to capture inherent nonlinear behavior otherwise unaccounted for in ARX modeling. On the other hand, linear modeling is generally simpler to understand and implement.8 Suppose the plant is described by an ARX model with an additive noise term. Denote P (i), y(i)(k), u(k), and (k), the plant operator, scalar output, input, and noise at sample time k, respectively. The integer i denotes a speci c plant or device, such as a particular laptop or desktop. In general, we will assume that we have a nite class of plants P (i) for i 2 [1; M ]. In general, the relationship between these quantities is given by: y(i)(k) = P (i)u(k) =
T (k d) (i) + (k) (1) where T (k d) denotes the regression vector and consists of a tapped delay line of input and output measurements, and (i) denotes a vector of real-valued parameters corresponding to the ith plant. A number of 7 Currently, we randomly terminate one of the lowcriticality OS processes. Additional information, such as process priority, can easily be used to guide termination.
8 The ARX model was chosen for several reasons; most
importantly it gave solid system identi
cation
performance. Allowing the plant model itself to be a probabilistic
graphical model would be interesting, and stochastic
approaches (based on stochastic di¤erential equations) have
been developed in control theory [
From the control engineering perspective, there are
several key issues: (1) Static uncertainty in plant
parameters: A tablet PC running Windows Vista will
behave di¤erently from a High Performance Computing
(HPC) cluster running openSUSE Linux. A control
system designed for one computer may not perform
well on another. In other words, the control system
parameters are uncertain and need to be estimated. (2)
Stochastic disturbances: The process that determines
when a low-criticality process is generated by a user
is, in general, stochastic. This is, in itself, an active
area of research [
Our proposed research is based on controlling BN computation in an inner loop as well as in an outer loop (see Figure 1); so far we discussed the inner loop. We now briey discuss the outer loop, where the output BEL(Q; e) of BN computation, as well as other factors external to the inner loop, may change desired completion time and also plant behavior (sampling frequency, BN computation algorithm, number of particles assuming a simulation algorithm, etc.).
Figure 1(c)): Table 1 summarizes results of running likelihood weighting on the ADAPT BN, using ve di¤erent computers and three di¤erent operating systems. System identi cation was performed on all computers using the two input data sets shown in Figure 3(a). Batch least squares was used to determine the parameters of a rst order linear ARX model. Table 1 shows the resulting R2 and mean squared error (MSE) of the parameter t for the various computers and operating systems. In most cases, we observed a low MSE.10
10 It is important to note the underlying variations in the ARX model parameters, which are used by the control design process. The diverse set of parameters, omitted here to save space, illustrate the bene t of using techniques from adaptive feedback control, speci cally learning from
Figure 1(b)): In Figure 4, we show the steady state computation time results for the ve BN inference algorithms discussed above. Here, steady state is de ned loosely as the time k such that y(k + 1) = y(k) = yss for all k k . Plugging this into (2) yields yss = c2u1ssc+1c3 , where u(k) = uss 8k k . Thus, the linear gain coe¢ cient (slopes in Figure 4) for each algorithm is given by 1 c2c1 .
The results fall into three groups: fast (JTP), medium (VE and LW), and slow (LBP and PBP) computations. Also, the standard error in computation time varies between the algorithms, with JTP again being the best with a very small standard error.
While JTP is exact and fast, its Achillesheel is memory consumption [23]. Consequently, it can be necessary, when running other memory-intensive processes, to use a less memory-intensive but inexact algorithm like LW. How should one switch between two algorithms, say the non-anytime algorithm JTP and the anytime algorithm LW, that have very di¤erent computational resource requirements but operate on the same BN? Feedback control can help in this regard, see Figure 5. From a control perspective, this is considered dynamic uncertainty in plant parameters: Given a computer P (i), a change in the BN algorithm will impact the way the plant, P (i), responds. Here, we switch from JTP to LW around 12:20, while maintaining the setpoint (on average) after a transient period lasting around 10 seconds.11 This is, to the best of the computational environment and adapt to changes.
11 Note, our approach does not make any hard real-time guarantees, only soft ones, and consequently the actual computation time is sometimes greater than the setpoint. our knowledge, the rst demonstration of a successful on-line switch between two very di¤erent inference algorithms (from JTP to LW) while a desired completion time is maintained.
is both a supply side and a demand side in computing.
On the supply side, one can control the supply of
computational resources, in the form of computers, CPUs,
CPU threads, or GPU threads. On the demand side,
the outer loop can vary the Setpoint r(k), perhaps in
combination with varying other outer loop parameters
such as sampling frequency fC (k) and number of
particles p(k) used in likelihood weighting [34] or particle
ltering [
One reason for the outer loop to vary the computational resources allocated to the high-criticality process is illustrated in the following. Suppose, for k < k , that P (H(k) j e(k)) suggested that there was one or more faults in the ADAPT electrical power system, while P (H(k ) j e(k )) indicated that this was a false alarm. In this case, we may want to be less stringent about ensuring that computation of P (H(k + 1) j e(k + 1)), P (H(k + 2) j e(k + 2)), etc. nishes in a timely fashion, in other words it makes sense to put r(k + 1) > r(k ). Figure 6(b) shows how this type of step change, at k 23:28, is supported by our controltheoretic framework. The baseline of not varying r(k) is shown in Figure 6(a). We here assume that sample frequency fC (k) = fC is constant, and consider (i) r(k 1) = r(k) < 1=fC (as when r(k) = 2 sec in both Figure 6(a) and Figure 6(b)) versus (ii) r(k) 1=fC (as when r(k) = 4 sec Figure 6(b)). The advantage of (i) is that there is a much greater chance that BN computation nishes before a new computational cycle starts, which is essential when EPS faults are more likely. The advantage of (ii), on the other hand, is that more low-criticality processes are allowed to run. The trade-o¤ between fast inference for the highcriticality process versus running many low-criticality processes is illustrated in Figure 6. Figure 6(b)s bottom panel shows an increase in the number of processes, on average, as a result of the increase in r(k) at k 23:28; no similar increase can be found in Figure 6(a)s bottom panel. 6
Deploying BN algorithms and other resource-intensive AI algorithms can be a challenge when there are nontrivial constraints on computational resources in applications. In this paper, we have focused on supporting requirements for reactive response without requiring dedicated hard real-time computational resources according to worst-case computational requirements. We have focused on reactive diagnosis using BNs, motivated by domains with some but uncertain domain knowledge (hence probabilistic graphical models, speci cally BNs) as well as uncertainty with respect to the computational platform and environment (hence feedback control).
An alternative approach to achieving reactive response
is the use of anytime algorithms. The motivation
behind anytime inference namely the goal of intelligent
and reactive systems and our work is quite similar.
However, the approaches are very di¤erent. Anytime
algorithms are inherently inexact and produce
solutions whose quality gradually improve with
computation time [37]. We focus on what can done, on the
computing system level, for a broad range of existing
Bayesian network inference algorithms including both
exact and inexact algorithms. As a consequence, our
approach enables the use of exact but non-anytime
algorithms (like variable elimination [
We are in this paper using rather basic control theory ideas. This enables new results and many opportunities for future work, both theoretical and experimental, and we invite other researchers to participate in the exploration of this exciting area of reseach. We are, for example, developing adaptive control methods that leverage online system identi cation of the process. There are also many interesting research opportunities related to the use of BN posteriors as well as their accuracy, and perhaps multiple BNs at different levels of detail, in the outer control loop. In this area, there is a strong connection to anytime algorithms and metareasoning that can be further investigated, enabling more reactive and more capable intelligent systems.
This material is based upon work supported, in part, by NSF awards CCF0937044 and ECCS0931978.