578051
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.
8251892
Optimal Reinsertion: A New Search Operator for Accelerated and More Accurate Bayesian Network Structure Learning
We show how a conceptually simple search operator called Optimal Reinsertion can be applied to learning Bayesian Network structure from data. On each step we pick a node called the target. We delete all arcs entering or exiting the target. We then find, subject to some constraints, the globally optimal combination of in-arcs and out-arcs with which to reinsert it. The heart of the paper is a new algorithm called ORSearch which allows each optimal reinsertion step to be computed efficiently on large datasets. Our empirical results compare Optimal Reinsertion against a highly tuned implementation of multirestart hill climbing. The results typically show one to two orders of magnitude speed-up on a variety of datasets. They usually show better final results, both in terms of BDEU score and in modeling of future data drawn from the same distribution.
5661913
Distributed Value Functions
Many interesting problems, such as power grids, network switches, and tra c ow, that are candidates for solving with reinforcement learning (RL), also have properties that make distributed solutions desirable. We propose an algorithm for distributed reinforcement learning based on distributing the representation of the value function across nodes. Each node in the system only has the ability to sense state locally, choose actions locally, and receive reward locally (the goal of the system is to maximize the sum of the rewards over all nodes and over all time). However each node is allowed to give its neighbors the current estimate of its value function for the states it passes through. We present a value function learning rule, using that information, that allows each node to learn a value function that is an estimate of a weighted sum of future rewards for all the nodes in the network. With this representation, each node can choose actions to improve the performance of the overall system. We demonstrate our algorithm on the distributed control of a simulated power grid. We compare it against other methods including: use of a global reward signal, nodes that act locally with no communication, and nodes that share rewards (but not value function) information with each other. Our results show that the distributed value function algorithm outperforms the others, and we conclude with an analysis of what problems are best suited for distributed value functions and the new research directions opened up by this work.
7323513
Coverage Testing Embedded Software on Symbian/OMAP
1444557
Conditional entropy coding of VQ indexes for image compression
Block sizes of practical vector quantization (VQ) image coders are not large enough to exploit all high-order statistical dependencies among pixels. Therefore, adaptive entropy coding of VQ indexes via statistical context modeling can significantly reduce the bit rate of VQ coders for given distortion. Address VQ was a pioneer work in this direction. In this paper we develop a framework of conditional entropy coding of VQ indexes (CECOVI) based on a simple Bayesian-type method of estimating probabilities conditioned on causal contexts, CECOVI is conceptually cleaner and algorithmically more efficient than address VQ, with address-VQ technique being its special case. It reduces the bit rate of address VQ by more than 20% for the same distortion, and does so at only a tiny fraction of address VQ's computational cost.
3467496
Compiler orchestrated prefetching via speculation and predication
This paper introduces a compiler orchestrated prefetching system as a unified framework geared toward ameliorating the gap between processing speeds and memory access latencies. We focus the scope of the optimization on specific subsets of the program dependence graph that succinctly characterize the memory access pattern of both regular array-based applications and irregular pointer-intensive programs. We illustrate how program embedded precomputation via speculative execution can accurately predict and effectively prefetch future memory references with negligible overhead. The proposed techniques reduce the total running time of seven SPEC benchmarks and two OLDEN benchmarks by 27% on an Itanium 2 processor. The improvements are in addition to several state-of-the-art optimizations including software pipelining and data prefetching. In addition, we use cycle-accurate simulations to identify important and lightweight architectural innovations that further mitigate the memory system bottleneck. In particular, we focus on the notoriously challenging class of pointer-chasing applications, and demonstrate how they may benefit from a novel scheme of it sentineled prefetching. Our results for twelve SPEC benchmarks demonstrate that 45% of the processor stalls that are caused by the memory system are avoidable. The techniques in this paper can effectively mask long memory latencies with little instruction overhead, and can readily contribute to the performance of processors today.
6934221
Mining System Tests to Aid Software Maintenance
Maintainers can use information from test analysis tools to help them understand, debug, and retest programs. The authors describe techniques and tools in Bellcore's /spl chi/Suds, a system for understanding and diagnosing software bugs, including Y2K problems in legacy applications.
21945290
Statistical cerebrovascular segmentation in three-dimensional rotational angiography based on maximum intensity projections
Segmentation of three-dimensional rotational angiography (3D-RA) can provide quantitative 3D morphological information of vasculature. The expectation maximization-(EM-) based segmentation techniques have been widely used in the medical image processing community, because of the implementation simplicity, and computational efficiency of the approach. In a brain 3D-RA, vascular regions usually occupy a very small proportion (around 1%) inside an entire image volume. This severe imbalance between the intensity distributions of vessels and background can lead to inaccurate statistical modeling in the EM-based segmentation methods, and thus adversely affect the segmentation quality for 3D-RA. In this paper we present a new method for the extraction of vasculature in 3D-RA images. The new method is fully automatic and computationally efficient. As compared with the original 3D-RA volume, there is a larger proportion (around 20%) of vessels in its corresponding maximum intensity projection (MIP) image. The proposed method exploits this property to increase the accuracy of statistical modeling with the EM algorithm. The algorithm takes an iterative approach to compiling the 3D vascular segmentation progressively with the segmentation of MIP images along the three principal axes, and use a winner-takes-all strategy to combine the results obtained along individual axes. Experimental results on 12 3D-RA clinical datasets indicate that the segmentations obtained by the new method exhibit a high degree of agreement to the ground truth segmentations and are comparable to those produced by the manual optimal global thresholding method.