nils-herrmann/clean_scirepeval huggingface dataset:
Extended Version of “ Expectation propagation for approximate inference in dynamic Bayesian networks ”

We consider inference in general dynamic Bayesian networks. We are especially interested in models in which exact inference becomes intractable, as, for example, in switching linear dynamical systems. We introduce expectation propagation as a straightforward extension of Pearl’s exact belief propagation. Expectation propagation, is a greedy algorithm, converges in many practical cases, but not always. Our goal is therefore to derive a message propagation scheme that can be guaranteed to converge. Following Minka, we therefore first derive a Bethe-free energy like functional, the fixed points of which correspond to fixed points of expectation propagation. We turn this primal objective into a dual objective in terms of messages or Lagrange multipliers. Approximate inference boils down to a saddle-point problem: maximization with respect to the difference between forward and backward messages, minimization with respect to the sum of the forward and backward messages. We derive several variants, ranging from a double-loop algorithm that guarantees convergence to the saddle point to a damped version of “standard” expectation propagation. We discuss implications for approximate inference in general, treestructured or even loopy, Bayesian networks. This technical report formed the basis of : @inproceedings{Heskes_Zoeter_UAI2002, AUTHOR = "Heskes, T. and Zoeter, O.", YEAR = 2002, TITLE = "Expectation propagation for approximate inference in dynamic {B}ayesian networks", BOOKTITLE = "Proceedings UAI-2002", EDITOR = "Darwiche, A. and Friedman, N.", PAGES = "216--233", URL = "ftp://ftp.snn.kun.nl/pub/snn/pub/reports/Heskes.uai2002.ps.gz"} It is, however, not fully compatible. I tried to update it backwardly, but may not have completely succeeded. If possible, please refer to the published proceedings paper.
Hierarchical Visualization of Time-Series Data Using Switching Linear Dynamical Systems

We propose a novel visualization algorithm for high-dimensional time-series data. In contrast to most visualization techniques, we do not assume consecutive data points to be independent. The basic model is a linear dynamical system which can be seen as a dynamic extension of a probabilistic principal component model. A further extension to a particular switching linear dynamical system allows a representation of complex data onto multiple and even a hierarchy of plots. Using sensible approximations based on expectation propagation, the projections can be performed in essentially the same order of complexity as their static counterpart. We apply our method on a real-world data set with sensor readings from a paper machine.
Visualization of process data with dynamic Bayesian Networks

We describe a novel visualization algorithm for high-dimensional timeseries data. The underlying model is a switching linear dynamical system, a particular variant of a dynamic Bayesian network. An important difference with most existing visualization techniques is the possibility to incorporate time dependencies between data points. Exact inference in switching linear dynamical systems is intractable, but new techniques for approximate inference enable fast computation of accurate posteriors. The model can be learned with a standard EM-algorithm. We illustrate our method on a real-world data set with sensor readings from a paper machine.
Expectation propagation for approximate inference in dynamic bayesian networks

We describe expectation propagation for approximate inference in dynamic Bayesian networks as a natural extension of Pearl's exact belief propagation. Expectation propagation is a greedy algorithm, converges in many practical cases, but not always. We derive a double-loop algorithm, guaranteed to converge to a local minimum of a Bethe free energy. Furthermore, we show that stable fixed points of (damped) expectation propagation correspond to local minima of this free energy, but that the converse need not be the case. We illustrate the algorithms by applying t,hem to switching linear dynamical systems and discuss implications for approximate inference in general Bayesian networks.
Q learning with finite trials

The standard reinforcement learning model is powerful enough to deal with never ending trials. By slightly discounting rewards obtained in the future, an infinite walk in the environment is still guaranteed to have a finite expected future reward. This however comes at a price. The discounting may corrupt estimates of the expected return in ending trials. Also in most cases algorithms that can deal with continuing trials rely heavily on arbitrary initial estimates of the optimal policy Q . If these estimates are off, convergence can be slowed down considerably. In terminal states the expected future return is 0, this can be known exactly after the first visit. so we can expect we can improve the Q learning algorithm by anticipating on terminal states. This thesis investigates MDPs in which discounting is unnecessary. New work is presented for the deterministic case. In deterministic MDPs, the set of undiscounted Bellman equations for Q has a unique solution if and only if from every state there is a path to a terminal state, and if all cycles have negative weight. In this set of MDPs the Q learning algorithm can be optimized by altering it in such a way that the initial estimates are not used. If the agent trains and explores in a fair way, that is, if the agent never fully ignores a state action pair, this improved Q learning algorithm is proven to converge in finite time. The proof gives a worst case guarantee of the performance. To gain insight in the average case performance, and the effect of the exploration strategy, several experiments in the simple three-in-a-row game of tic-tac-toe have been conducted. New performance measures, based on the (precomputed) optimal table Q are introduced to more accurately study the behavior of the algorithm.
Automatic Excursion Detection in Manufacturing: Preliminary Results

In the past decades, high-volume manufacturing processes have grown increasingly complex. If a failure in these systems is not detected in a timely manner, it often results in tremendous costs. Therefore, the demand for methods that automatically detect these failures is high. In this work, we address the problem of automatic excursion detection based on parametric tests. Overlooking the complexity of wafer fabrication processes, we propose two structurally simple excursion detection models: Naive Bayes classifier and boosted decision stumps. We apply these models in the domain of semiconductor manufacturing, compare them to offthe-shelf classification techniques, and show significant gains in the precision and recall of detected excursions. These results encourage our future work that should primarily focus on increasing the recall of our models.
Restructuring Dynamic Causal Systems in Equilibrium

In this paper I consider general obstacles to the recovery of a causal system from its probability distribution. I argue that most of the well-known problems with this task belong in the class of what I call degenerate causal systems. I then consider the task of discovering causality of dynamic systems that have passed through one or more equilibrium points, and show that these systems present a challenge to causal discovery that is fundamentally different from degeneracy. To make this comparison, I consider two operators that are used to transform causal models. The first is the well-known Do operator for modeling manipulation, and the second is the Equilibration operator for modeling a dynamic system that has achieved equilibrium. I consider a set of questions regarding the commutability of these operators i.e., whether or not an equilibrated-manipulated model is necessarily equal to the corresponding manipulated-equilibrated model, and I explore the implications of that commutability on the practice of causal discovery. I provide empirical results showing that (a) these two operators sometimes, but not always, commute, and (b) the manipulatedequilibrated model is the correct one under a common interpretation of manipulation on dynamic systems. I argue that these results have strong implications for causal discovery from equilibrium data.
Use of multiple data streams to conduct Bayesian biologic surveillance.

Emergency department (ED) records and over-the-counter (OTC) sales data are two of the most commonly used sources of data for syndromic surveillance. The majority of detection algorithms monitor these data sources separately and either do not combine them or combine them in an ad hoc fashion. This report outlines a new causal model that combines the two data sources coherently to perform outbreak detection.



This report describes the extension of the Population-wide Anomaly Detection and Assessment (PANDA) Bayesian biologic surveillance algorithm to combine information from multiple data streams. It also outlines the assumptions and techniques used to make this approach scalable for real-time surveillance of a large population.



A causal Bayesian network model used previously was extended to incorporate evidence from daily OTC sales data. At the level of individual persons, the actions that result in the purchase of OTC products and in admission to an ED were modeled.



Preliminary results indicate that this model has a tractable running time consisting of 209 seconds for initialization and approximately 4 seconds for every hour's worth of ED data, as measured on a Pentium-4 three-Gigahertz machine with two Gigabytes of RAM.



Preliminary results for surveillance using a new Bayesian algorithm that models the interaction between ED and OTC data are positive regarding the run time of the algorithm.
Bayesian Biosurveillance of Disease Outbreaks

Early, reliable detection of disease outbreaks is a critical problem today. This paper reports an investigation of the use of causal Bayesian networks to model spatio-temporal patterns of a non-contagious disease (respiratory anthrax infection) in a population of people. The number of parameters in such a network can become enormous, if not carefully managed. Also, inference needs to be performed in real time as population data stream in. We describe techniques we have applied to address both the modeling and inference challenges. A key contribution of this paper is the explication of assumptions and techniques that are sufficient to allow the scaling of Bayesian network modeling and inference to millions of nodes for real-time surveillance applications. The results reported here provide a proof-of-concept that Bayesian networks can serve as the foundation of a system that effectively performs Bayesian biosurveillance of disease outbreaks.
Model Averaging for Prediction with Discrete Bayesian Networks

In this paper we consider the problem of performing Bayesian model-averaging over a class of discrete Bayesian network structures consistent with a partial ordering and with bounded in-degree k. We show that for N nodes this class contains in the worst-case at least distinct network structures, and yet model averaging over these structures can be performed using operations. Furthermore we show that there exists a single Bayesian network that defines a joint distribution over the variables that is equivalent to model averaging over these structures. Although constructing this network is computationally prohibitive, we show that it can be approximated by a tractable network, allowing approximate model-averaged probability calculations to be performed in O(N) time. Our result also leads to an exact and linear-time solution to the problem of averaging over the 2N possible feature sets in a naive Bayes model, providing an exact Bayesian solution to the troublesome feature-selection problem for naive Bayes classifiers. We demonstrate the utility of these techniques in the context of supervised classification, showing empirically that model averaging consistently beats other generative Bayesian-network-based models, even when the generating model is not guaranteed to be a member of the class being averaged over. We characterize the performance over several parameters on simulated and real-world data.
Robust Independence Testing for Constraint-Based Learning of Causal Structure

Constraint-based (CB) learning is a formalism for learning a causal network with a database D by performing a series of conditional-independence tests to infer structural information. This paper considers a new test of independence that combines ideas from Bayesian learning, Bayesian network inference, and classical hypothesis testing to produce a more reliable and robust test. The new test can be calculated in the same asymptotic time and space required for the standard tests such as the chi-squared test, but it allows the specification of a prior distribution over parameters and can be used when the database is incomplete. We prove that the test is correct, and we demonstrate empirically that, when used with a CB causal discovery algorithm with noninformative priors, it recovers structural features more reliably and it produces networks with smaller KL-Divergence, especially as the number of nodes increases or the number of records decreases. Another benefit is the dramatic reduction in the probability that a CB algorithm will stall during the search, providing a remedy for an annoying problem plaguing CB learning when the database is small.
Evaluation of Bayesian networks used for diagnostics

Bayesian networks have been very useful as models for computerized diagnostic assistants, as evidenced by numerous citations in the literature. However. a number of important practical problems in the application of Bayesian networks to diagnostics have still not been properly addressed. One of these is the evaluation of Bayesian network models. The quality of a model determines the quality of diagnostic recommendations obtained using that model. Thus, comprehensive analysis and evaluation of Bayesian models provides a fm basis for estimation of performance of diagnostic tools based on these models. Our approach to Bayesian network evaluation relies on the use of Monte Carlo simulation and the efficient visualization of simulation results. This technique allows us to identify the critical elements of Bayesian models that are responsible for incorrect diagnosis. In this way we can point to components that lack strong observations and therefore cannot be diagnosed convincingly. We can identify strongly coupled components that implicate each other and therefore cannot be effectively separated in diagnosis. We can also identify components whose failures are consistently misinterpreted as failures of other components.
Model Averaging with Bayesian Network Classifiers

This paper considers the problem of performing classification by model-averaging over a class of discrete Bayesian network structures consistent with a partial ordering and with bounded in-degree k. We show that for N nodes this class contains in the worst-case at least Ω( ( N/2 k )N/2 ) distinct network structures, but we show that this summation can be performed in O( ( N k ) · N) time. We use this fact to show that it is possible to efficiently construct a single directed acyclic graph (DAG) whose predictions approximate those of exact model-averaging over this class, allowing approximate model-averaged predictions to be performed in O(N) time. We evaluate the procedure in a supervised classification context, and show empirically that this technique can be beneficial for classification even when the generating distribution is not a member of the class being averaged over, and we characterize the performance over several parameters on simulated and real-world data.
A method for evaluating elicitation schemes for probabilistic models

We present an objective approach for evaluating probability and structure elicitation methods in probabilistic models. The main idea is to use the model derived from the experts' experience rather than the true model as the standard to compare the elicited model. We describe a general procedure by which it is possible to capture the data corresponding to the expert's beliefs, and we present a simple experiment in which we utilize this technique to compare three methods for eliciting discrete probabilities: 1) direct numerical assessment, 2) the probability wheel, and 3) the scaled probability bar. We show that for our domain, the scaled probability bar is the most effective tool for probability elicitation.
Exact model averaging with naive Bayesian classifiers

The naive classifier is a well-established mathematical model whose simplicity, speed and accuracy have made it a popular choice for classification in AI and engineering. In this paper we show that, given N features of interest, it is possible to perform tractable exact model averaging (MA) over all 2 possible feature-set models. In fact, we show that it is possible to calculate parameters for a single naive classifier C∗ such that C∗ produces predictions equivalent to those obtained by the full model-averaging, and we show that C∗ can be constructed using the same time and space complexity required to construct a single naive classifier with MAP parameters. We present experimental results which show that on average the MA classifier typically outperforms the MAP classifier on simulated data, and we characterize how the relative performance varies with number of variables, number of training records, and complexity of the generating distribution. Finally, we examine the performance of the MA naive model on the real-world ALARM and HEPAR networks and show MA improved classification here as well.
A Method for Evaluating Elicitation Schemes for Probabilities

We present an objective approach for evaluating probabilit,, clicitati~m methods in probabilistic models. Our method draw~, tm ideas from research on learning Bayesian etworks: iI ~c assume that the expert’s knowledge is manifested es~,cntially a.,, a database of records that have been collected in the course of the expert’s experience, and if this database of records i available It:, us, then the ~tructure and parameters of the expert’s beliefs could be reliabl)’ constructed using techniques for Bayesian learning from data. This learned model could, m turn. be compared to elicited models to judge the effectiveness of the clicitation process. We describe a general pn~ccdurc by which it is possible to capture the data corre,,ptmding to the expert’s beliefs, and we present a simple experiment in which we utilize this technique to compare three methods t~r eliciting discrete prt~babilities: (I) direct numerteal assc,,smcnt. (2) the probability wheel, and (3) the scaled iwohahihty bar. We show that t’or our domain, the scaled prub:lhlht} bar i~, the retest eflcctive tool for probability clici-
Caveats for Causal Reasoning with Equilibrium Models

In this paper we examine the ability to perform causal reasoning with recursive equilibrium models. We identify a critical postulate, which we term the Manipulation Postulate, that is required in order to perform causal inference, and we prove that there exists a general class F of recursive equilibrium models that violate the Manipulation Postulate. We relate this class to the existing phenomenon of reversibility and show that all models in F display reversible behavior, thereby providing an explanation for reversibility and suggesting that it is a special case of a more general and perhaps widespread problem. We also show that all models in F possess a set of variables V′ whose manipulation will cause an instability such that no equilibrium model will exist for the system. We define the Structural Stability Principle which provides a graphical criterion for stability in causal models. Our theorems suggest that drastically incorrect inferences may be obtained when applying the Manipulation Postulate to equilibrium models, a result which has implications for current work on causal modeling, especially causal discovery from data.
A Hybrid Anytime Algorithm for the Construction of Causal Models From Sparse Data

We present a hybrid constraint-based/ Bayesian algorithm for learning causal networks in the presence of sparse data. The algorithm searches the space of equivalence classes of models (essential graphs) using a heuristic based on conventional constraint-based techniques. Each essential graph is then converted into a directed acyclic graph and scored using a Bayesian scoring metric. Two variants of the algorithm are developed and tested using data from randomly generated networks of sizes from 15 to 45 nodes with data sizes ranging from 250 to 2000 records. Both variations are compared to, and found to consistently outperform two variations of greedy search with restarts.
Problems Related to Causal Reasoning in Equilibrium Models

Causal discovery, for the most part, is concerned with learning causal models in the form of directed acyclic graphs (DAGs) from equilibrium (as opposed to time series) data. Causal reasoning, by contrast, is concerned with using such causal DAGs to perform inferences. In particular, much work on causal reasoning has focused on the ability to predict the new probability distribution over a set of variables, V , given a causal graph G = (V; E) and given the fact that some subset of variables V 0 V has been externally manipulated to some conguration. These types of manipulation inferences contrast with more common diagnostic inferences, in that the former may require the causal graph to be altered prior to performing probabilistic inference. Specically , the ability to perform manipulation inferences is made possible by a critical postulate which we call the Manipulation Postulate. All formalisms for causal reasoning take the manipulation postulate as a fundamental starting point: The Manipulation Postulate. If G = (V; E) is a causal graph and V 0 V is a subset of variables being manipulated, then the causal graph, G 0 , describing the manipulated system is such that G 0 = (V; E 0 ), where E 0 E and E 0 diers from E by at most the set of arcs into V 0 . In other words, manipulating a variable can cause some of its incoming arcs to be removed from the causal graph, but can eect no other change in the causal graph. The Manipulation Theorem of Spirtes, et. al. (1992) proves that given the Manipulation Postulate and the Markov Condition, the probability distribution of the manipulated model can be calculated. Furthermore, the axiomatizations of causal reasoning of Galles and Pearl (1997) and of Halpern (1998) also take the Manipulation Postulate as a fundamental assumption. The question that we pose in this paper is \Are these two lines of research (i.e., equilibrium causal discovery and manipulation reasoning) consistent?" Namely, what would happen if we took an equilibrium causal model (learned from data), and applied the manipulation formalisms to it? Are the resulting inferences guaranteed to be valid? We prove by explicit counterexample that such inferences are not guaranteed to be valid in the sense that conditional independencies in the manipulated model can dier from the conditional independencies in the learned model of the manipulated system. Symbolically, if MS is a learned causal model of system S, and if we use the^operator to denote manipulation, then we show that ^ MS 6 M ^ S . Our general strategy is as follows: We rst present two extremely simple physical systems (an ideal gas trapped in a cylinder with a movable piston and a mass dangling from a damped spring), we show, based on physical laws what the \true" equilibrium causal graphs of these systems are.