Projects

 

Carnegie Mellon University

Parallel and Distributed Algorithms for Intelligent Systems


In the area of parallel and distributed algorithms for intelligent systems, we take advantage of opportunities that have emerged due to recent dramatic improvements in parallel and distributed hardware and software. The emergence of graphics processing units (GPUs) as a general computing platform is one important trend; another is the introduction of the MapReduce architecture along with its open-source Hadoop implementation. We have taken advantage of GPUs to perform faster junction tree propagation through parallelism.  Compiling Bayesian networks (BNs) to junction trees and performing belief propagation over them is among the most prominent approaches to computing posteriors in BNs. We develop data structures and algorithms that extend existing junction tree techniques, and specifically develop a novel approach to computing each belief propagation message in parallel. We have so far achieved speedups up to approximately 10x; however the speedup depends strongly on the structure of the junction tree. Using MapReduce and Hadoop, we have developed developed Bayesian network parameter learning algorithms and shown how they can dramatically speed up machine learning, both for complete and incompleted data sets. We have also developed a distributed variant of the text mining system Unsupervised Semantic Parsing (USP), which we call Distributed Unsupervised Semantic Parsing (DUSP). DUS improves on USP's ability to handle large text corpora by distributing several of USP’s key algorithmic steps over a cluster of commodity computers. In experiments with DUSP we processed a corpus that was over 13 times larger than the largest corpus we were able to handle using USP.


Related Papers:

  1. •Belief Propagation by Message Passing in Junction Trees: Computing Each Message Faster Using GPU Parallelization: http://works.bepress.com/ole_mengshoel/8/

  2. •Distributed Unsupervised Semantic Parsing of Large-Scale Document Corpora:

  3. •Accelerating Bayesian Network Parameter Learning Using Hadoop and MapReduce:

 

Social Networks:  Data Analysis and Machine Learning


Social network analytics, machine learning, and visualizaiton is one of our research areas. We have analyzed a large mobile phone dataset, consisting of millions of call data records (CDRs), provided by one of the major telecom operators. Using this dataset, we have investigated the different social connections or ties that are reflected in such datasets. 

Social ties defined by phone calls made between people can be grouped to various affinity networks, such as family members, utility network, friends, coworkers, etc. An understanding of call behaviour within each social affinity network and the ability to infer the type of a social tie from call patterns is invaluable for various industrial purposes. We analyzed the 

patterns of 4.3 million phone call data records produced by 360,000 subscribers from two California cities, San Francisco and Modesto, and found features that are highly predictive of the type of social tie, independent of the city. Armed with this knowledge we also  have identified promising machine learning classification approaches as well as several potential applications in telecom and security. 


Related Papers:

  1. •The Impact of Social Affinity on Phone Calling Patterns: Categorizing Social Ties From Call Data Records:

 

Understanding the Complexity of Bayesian Network Computation


This Project presents and analyzes algorithms that systematically generate random Bayesian networks of varying difficulty levels, with respect to inference using tree clustering. Our generation algorithms, called BPART and MPART, support controlled but random construction of bipartite and multipartite Bayesian networks. The results are relevant to research on efficient Bayesian network inference, such as computing a most probable explanation or belief updating. The results are also relevant to research on machine learning of Bayesian networks, since they support controlled generation of a large number of data sets at a given difficulty level. One of the main approaches to performing computation in Bayesian networks (BNs) is clique tree clustering and propagation we improve this understanding by developing an approach to characterizing clique tree growth as a function of parameters that can be computed in polynomial time from BNs, specifically the ratio of the number of a BN’s non-root nodes to the number of root nodes, and the expected number of moral edges in their moral graphs. Surprisingly, root clique growth is well-approximated by Gompertz growth curves, an S-shaped family of curves that has previously been used to describe growth processes in biology, medicine, and neuroscience. As well in this project we are concerned with the conceptual design of large-scale diagnostic and health management systems that use Bayesian networks.While they are potentially powerful, improperly designed Bayesian networks can result in too high memory requirements or too long inference times We investigate the clique tree clustering approach to Bayesian network inference, where increasing the size and connectivity of a Bayesian network typically also increases clique tree size. We provide both theoretical and experimental results.


Related Papers:

  1. •Controlled Generation of Hard and Easy Bayesian Networks: Impact on Maximal Clique Size in Tree Clustering: http://works.bepress.com/ole_mengshoel/9/

  2. •Understanding the Scalability of Bayesian Network Interference Using Clique Tree Growth Curves: http://works.bepress.com/ole_mengshoel/5/

  3. •Designing Resource-Bounded Reasoners using Bayesian Networks: System Health Monitoring and Diagnosis: http://works.bepress.com/ole_mengshoel/10/

 

Stochastic Optimization Using Stochastic Local Search


Portfolio methods support the combination of different algorithms and heuristics, including stochastic local search (SLS) heuristics, and have been identified as a promising approach to solve computationally hard problems. While successful in experiments, theoretical foundations and analytical results for portfolio-based SLS heuristics are less developed. Analytically, we introduce a novel Markov chain model tailored to portfolio-based SLS algorithms including SGS, thereby enabling us to analytically form expected hitting time results that explain empirical run time results.For hard computational problems, stochastic local search has proven to be a competitive approach to finding optimal or approximately optimal problem solutions. We introduce a novel approach, based on the Viterbi algorithm, to explanation initialization in BNs. While the Viterbi algorithm works on sequences and trees, our approach works on BNs with arbitrary topologies. We also give a novel formalization of stochastic local search, with focus on initialization and restart, using probability theory and mixture models. Experimentally, we apply our methods to the problem of MPE computation, using a stochastic local search algorithm known as Stochastic Greedy Search. On several BNs from applications, the performance of Stochastic Greedy Search is competitive with clique tree clustering, a state-of-the-art exact algorithm used for MPE computation in BNs. Stochastic local search (SLS) algorithms have recently been proven to be among the best approaches to solving computationally hard problems. SLS algorithms typically have a number of parameters, optimized empirically, that characterize and determine their performance. To complement existing experimental results, we formulate and analyze several Markov chain models of SLS in this article. In particular, we compute expected hitting times and show that they are rational functions for individual problem instances as well as their mixtures.We believe that our results provide an improved theoretical understanding of the role of noise in stochastic local search, thereby providing a foundation for further progress in this area.


Related Papers:

  1. •Portfolios in Stochastic Local Search: Efficiently Computing Most Probable Explanations in Bayesian Networks: http://works.bepress.com/ole_mengshoel/3/

  2. •Initialization and Restart in Stochastic Local Search: Computing a Most Probable Explanation in Bayesian Networks: http://works.bepress.com/ole_mengshoel/11/

  3. •Understanding the Role of Noise in Stochastic Local Search: Analysis and Experiments: http://works.bepress.com/ole_mengshoel/2/

 

Stochastic Optimization Using Genetic Algorithms


Crowding is a techn
ique used in genetic algorithms to preserve diversity in the population and to prevent premature convergence to local optima.The present work focuses on the replacement phase of crowding, which usually has been carried out by one of the following three approaches: Deterministic, Probabilistic, and Simulated Annealing. Theoretical analysis using Markov chains and empirical evaluation using Bayesian networks demonstrate the potential of this novel Generalized Crowding approach.This project also includes a novel niching algorithm probabilistic crowding.This project also identifies probabilistic crowding as a member of a family of algorithms, which we call integrated tournament algorithms. We also focus on niching using crowding techniques in the context of what we call local tournament algorithms. In addition to deterministic and probabilistic crowding, the family of local tournament algorithms includes the Metropolis algorithm, simulated annealing, restricted tournament selection, and parallel recombinative simulated annealing.In probabilistic crowding, sub-populations are maintained reliably, and we show that it is possible to analyze and predict how this maintenance takes place. We also provide novel results for deterministic crowding, show how different crowding replacement rules can be combined in portfolios, and discuss population sizing. A problem with the traditional evolutionary approach is this: As the number of constraints determined by the zeros in the conditional probability tables grows, performance deteriorates because the number of explanations whose probability is greater than zero decreases. To minimize this problem, we present and analyze a new evolutionary approach to abductive inference in BNs. Genetic algorithms typically use crossover, which relies on mating a set of selected parents. As part of crossover, random mating is often carried out. A novel approach to parent mating is presented in this work. Our novel approach can be applied in combination with a traditional similarity based criterion to measure distance between individuals or with a fitness-based criterion.In the domain of real function optimization, the experiments show that, as the degree of multimodality of the function at hand grows, it is convenient to increase the mating index in order to obtain good performance.


Related Papers:

  1. •Generalized Crowding for Genetic Algorithms: http://works.bepress.com/ole_mengshoel/20/

  2. •Probabilistic Crowding: Deterministic Crowding with Probabilistic Replacement: http://works.bepress.com/ole_mengshoel/14/

  3. •The Crowding Approach to Niching in Genetic Algorithms: http://works.bepress.com/ole_mengshoel/15/

  4. •Constraint Handling Using Tournament Selection: Abductive Inference in Partly Deterministic Bayesian Network: http://works.bepress.com/ole_mengshoel/21/

  5. •A Novel Mating Approach for Genetic Algorithms:

 

Fault Diagnosis Using Bayesian Networks


Bayesian networks ha
ve established themselves as an indispensable tool in artificial intelligence, and are being used effectively by researchers and practitioners more broadly in science and engineering. The domain of system health management, including diagnosis, is no exception. In fact, diagnostic applications have driven much of the developments in Bayesian networks over the past few decades. In this chapter, we provide a gentle and accessible introduction to modeling and reasoning with Bayesian networks, with the domain of system health management in mind.Bayesian networks, which may be compiled to arithmetic circuits in the interest of speed and predictability, provide a probabilistic method for system fault diagnosis. Currently, there is a limitation in arithmetic circuits in that they can only represent discrete random variables, while important fault types such as drift and offset faults are continuous and induce continuous sensor data. In this project, we investigate how to handle continuous behavior while using discrete random variables with a small number of states.We demonstrate that PRODIAGNOSE, augmented with the CUSUM technique, is successful in diagnosing faults that are small in magnitude (offset faults) or drift linearly from a nominal state (drift faults). In one of these experiments, detection accuracy dramatically improved when CUSUM was used, jumping from 46.15% (CUSUM disabled) to 92.31% (CUSUM enabled).


Related Papers

  1. •Integrating Probabilistic Reasoning and Statistical Quality Control Techniques for fault Diagnosis in Hybrid Domains: http://works.bepress.com/ole_mengshoel/18/

  2. •Probabilistic Model-Based Diagnosis: an Electrical Power System Case Study: http://works.bepress.com/ole_mengshoel/4/

  3. •A Tutorial on Bayesian Networks for System Health Management: http://works.bepress.com/ole_mengshoel/24/

  4. •Diagnosis Faults in Electrical Power Systems of Spacecraft and Aircraft: http://works.bepress.com/ole_mengshoel/1/

  5. •Diagnosing Intermittent and Persistent Faults Using Static Bayesian Networks: http://works.bepress.com/ole_mengshoel/7/

  6. •Developing Large-Scale Bayesian Networks by Computation: Fault Diagnosis of Electrical Power Systems in Aircraft and Spacecraft: http://works.bepress.com/ole_mengshoel/26/

  7. •Methods for Probabilistic Fault Diagnosis: An Electrical Power System Case Study:

  8. •Diagnosis and Reconfiguration using Bayesian Networks : An Electrical Power System Case Study: http://works.bepress.com/ole_mengshoel/25/

  9. •Using Bayesian Networks for Candidate Generation in Consistency-Based Diagnosis:

 

Visual Analytics for Networks

Bayesian networks are a theoretically well-founded approach to represent large multi-variate probability
distributions, and have proven useful in a broad range of applications. While several software tools for visualizing and editing Bayesian networks exist, they have important weaknesses when it comes to enabling users to clearly understand and compare conditional probability tables in the context of network topology, especially in large-scale networks. One focus of this project describes a system for improving the ability for computers to work with people to develop intelligent systems through the con- struction of high-performing Bayesian networks. It uses a “thought bubble line” to connect nodes in a graph representation and their internal information at the side of the graph. The tool seeks to improve the ability of experts to analyze and debug large Bayesian network models, and to help people to understand how alternative algorithms and Bayesian networks operate, providing insights into how to improve them. By selectively zooming in and zooming out visualizations,the fisheye technique allows users to study details while maintaining context. In this project, we introduce a multifisheye technique, which amounts to introducing several fisheyes in a visualization at the same time. Our multi-fisheye technique is based on partitioning the visualization’s display area and applying a fisheye algorithm inside each partition. We have demonstrate the potential of applying our multifisheye technique on social networks and Bayesian networks.


Related Papers:

  1. •Visualizing and Understanding Large-Scale Bayesian Networks: http://works.bepress.com/ole_mengshoel/23/

  2. •Multi-Fisheye for Interactive Visualization of Large Graphs:

 

Verification and Validation

System Health
Management (SHM) systems have found their way into many safety-critical aerospace and industrial applications. A SHM system processes readings from sensors throughout the system and uses a Health Management (HM) model to detect and identify potential faults (diagnosis) and to predict possible failures in the near future In this paper, we will describe an advanced technique for the analysis and V&V of Health Management models.We are investigating the use of Parametric Testing (PT), which uses a combination of n-factor and Monte Carlo methods, to exercise our HM model with variations of perturbed parameters.Our approach can yield valuable insights regarding the sensitivity of parameters and helps to detect safety margins and boundaries.In this project we also present an architecture and a formal frame-work to be used for systematic benchmarking of monitoring and diagnosis systems and for producing comparable performance assessments of different diagnosis technologies. In this project we focus on the Advanced Diagnostics and Prognostics Testbed (ADAPT) at NASA Ames Research Center. The purpose of the testbed is to measure, evaluate, and mature diagnostic and prognostic health management technologies. This project also includes the testbed’s hardware, software architecture, and concept of operations. A simulation testbed that accompanies ADAPT, and some of the diagnostic and decision support approaches being investigated are also discussed.





Related Papers:

  1. •Verification and Validation of System Health Management Models using Parametric Testing: http://works.bepress.com/ole_mengshoel/13/

  2. •A Framework for Systematic Benchmarking of Monitoring and Diagnostic Systems: http://works.bepress.com/ole_mengshoel/27/

  3. •Who Guards the Guardians?: Toward Verification and Validation of health Management Software:

  4. •Advanced Diagnostics and Prognostics Testbed:

 

Software and Sensor Health Management


In this project, we focus on the use of Bayesian networks (BNs) to monitor the health of on-board software and sensor systems, and to perform advanced on-board diagnostic reasoning. Advanced compilation techniques are used to obtain a compact SSHM (Software and Sensor Health Management) system with a powerful reasoning engine, which can run in an embedded software environment and is amenable to V&V. We successfully demonstrate our approach using an OSEK-compliant operating system kernel, and discuss in detail several nominal and fault scenarios for a small satellite simulation with a simple bang-bang controller. In this project we use Bayesian networks to 1) monitor the health of the on-board software and sensor system and 2) perform advanced on-board diagnostic reasoning.We focus on the development of reliable and robust health models for combined software and sensor systems, with application to guidance, navigation, and control (GN&C).We propose that iSWHM (Integrated SoftWare Health Management) can increase safety and reliability of high-assurance software systems. iSWHM uses advanced techniques from the area of system health management in order to continuously monitor the behaviour of the software during operation, quickly detect anomalies and perform automatic and reliable root-cause analysis, while not replacing traditional V&V. Information provided by the iSWHM system can be used for automatic mitigation mechanisms (e.g., recovery, dynamic reconfiguration) or presented to a human operator. In this project a probabilistic approach, using Bayesian networks, to diagnosis and sensor validation, and investigate several relevant but slightly different Bayesian network queries.


Related Papers:

  1. •Integrated Software and Sensor Health Management for Small Spacecraft: http://works.bepress.com/ole_mengshoel/16/

  2. •Bayesian Software Health Management for Aircraft Guidance, Navigation, and Control: http://works.bepress.com/ole_mengshoel/17/

  3. •Software Health Management with Bayesian Networks: http://works.bepress.com/ole_mengshoel/19/

  4. •Towards Software Health Management with Bayesian Networks: http://works.bepress.com/ole_mengshoel/12/

  5. •Sensor Validation Using Bayesian Networks: http://works.bepress.com/ole_mengshoel/22/

  6. •Software Health Management: A Short Review of Challenges and Existing Techniques:

 
Learning and Control In this work we focus on machine learning and feedback control, including the integration of machine learning into feedback control (also known as adaptive control).  One area of research is the family of expectation maximization (EM) algorithms. The expectation maximization algorithm is a popular algorithm for parameter estimation in models with hidden variables. However, the algorithm has several non-trivial limitations, a significant one being variation in eventual solutions found, due to local optima. Several techniques have been proposed to allay this problem, for example initializing  EM from multiple random starting points and selecting the highest likelihood out of all runs. In this work, we a) show that this method can be very expensive computationally for difficult Bayesian Networks, and b) in response we propose an age-layered EM approach (ALEM) that efficiently discards less promising runs well before convergence. Our experiments show a significant reduction in  solution quality, indicating the potential for ALEM to streamline parameter estimation in Bayesian networks. Another research focus is 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. We have empirically demonstrated reactive fault diagnosis for an electrical power system, and also the use of techniques to adapt to the compuational environment at hand.  Related Papers: Age Layered Expectation Maximization for Parameter Learning In Bayesian Networks: Reactive Bayesian Network Computation using Feedback Control: An Empirical Study Adaptive Control of Bayesian Network Computation: