Grapical Models — Methods for Data Analysis and Mining

Chapter Abstracts

back to the main page 

Contents

1 Introduction

Keywords: data and knowledge, knowledge discovery, data mining

Abstract: Due to the huge amount of data available today, we face the challenge to develop methods that can help humans to discover useful patterns in their data. In this chapter we characterize this challenge by distinguishing carefully between data and knowledge and by explaining the knowledge discovery process. We identify a set of data mining tasks and list methods that can be used to solve these tasks. Finally, we give an overview of the book, which focuses on the special method of learning graphical models from data.

back to the top 

2 Imprecision and Uncertainty

Keywords: imprecision, uncertainty, reasoning, inference, possibility theory, context model

Abstract: One of the key objectives when using graphical models is to draw inferences from observations, exploiting background knowledge. Therefore, in this chapter, we review drawing inferences in general and which problems occur if imprecision and/or uncertainty is involved. As a basis for the exposition of possibilistic graphical models in later chapters, we provide a detailed introduction to possibility theory, an alternative to probability theory. This introduction is based on the context model interpretation of a degree of possibility, which provides well-founded semantics.

back to the top 

3 Decomposition

Keywords: multivariate distribution, decomposition, reasoning with decompositions

Abstract: The main idea underlying graphical models is that under certain conditions a multivariate distribution (a relation or a probability or possibility distribution) can be decomposed into smaller distributions on subspaces. This decomposition can then be used to simplify reasoning. In this chapter we illustrate this idea with some examples, starting from the relational case, which makes it possible to study the surprisingly simple mechanisms without the disguise of specific numerical relations (for probabilities or degrees of possibility). The results are then transferred to the probabilistic and the possibilistic case.

back to the top 

4 Graphical Representation

Keywords: conditional independence graph, separation in graphs, Markov properties, evidence propagation

Abstract: Decompositions of multivariate distributions and reasoning with such decompositions can conveniently be described with the help of so-called conditional independence graphs, which represent conditional independences between attributes describing a domain of interest, but also identify the distributions needed in a decomposition. In this chapter we explain in detail the connection between decompositions and graphical representations and discuss how graph structures can be used to derive efficient evidence propagation algorithms.

back to the top 

5 Computing Projections

Keywords: projection, marginal distribution, estimation, quantitative learning, expectation maximization

Abstract: A basic operation for learning graphical models from data is the estimation of marginal distributions (projections) from a dataset of sample cases. This operation is trivial in the relational and the probabilistic case, at least if the database to learn from is precise. If it is not, we may rely on the expectation maximization algorithm in the probabilistic case. The possibilistic case, however, is more difficult. Therefore a large part of this chapter is devoted to the development of a preprocessing method which makes computing maximum projections (marginal possibility distributions) efficient.

back to the top 

6 Naive Classifiers

Keywords: naive Bayes classifier, naive possibilistic classifier, classifier simplification

Abstract: Naive classifiers are graphical models with a star-like structure, where the class attribute is at the center and all other attributes surround it. The best known example is the naive Bayes classifier, which is reviewed in this chapter, together with some straightforward simplification methods. In addition, we develop a possibilistic analog of the naive Bayes classifier and compare it to its probabilistic counterpart.

back to the top 

7 Learning Global Structure

Keywords: structure learning, learning algorithm, evaluation measure, search method

Abstract: Learning the global structure of a graphical model means to determine the structure of its conditional independence graph. This is the main task when learning a graphical model from data and therefore this is the core chapter of this book. After an introduction to the problem of structure learning, which continues the simple examples of Chapter 3, we turn to general learning algorithms. All such algorithms consist of two parts: an evaluation measure to assess the model quality and a search method, which determines the candidate models that are inspected. We discuss a variety of evaluation methods and search methods, which are based on a large number of different ideas.

back to the top 

8 Learning Local Structure

Keywords: local network structure, learning local structure, decision tree, decision graph

Abstract: Learning the local structure of a graphical models means to exploit regularities in the (conditional) probability tables that form the quantitative part of a graphical model. In this chapter we study two approaches to learning local structure that are based on a decision graph representation of conditional distributions, which appears to be one of the most flexible representations.

back to the top 

9 Inductive Causation

Keywords: causation, correlation, stability, latent variable, inductive causation algorithm

Abstract: Bayesian networks are often called probabilistic causal models, because the direction of their edges can be used to indicate the direction of a causal dependence between the connected attributes. While this may be justified if the network is constructed manually by a human expert, it is less clear whether the result of a learning algorithm can be interpreted in this way. To clarify the matter, we review the inductive causation algorithm and discuss in detail the assumptions underlying it.

back to the top 

10 Applications

Keywords: telecommunications, fraud detection, automotive industry, supply prediction, fault diagnosis

Abstract: In order to illustrate the usefulness of the approaches described in this book, we study three applications of learning graphical models from data. In the first application an enhanced naive Bayes classifier is learned for fraud detection in telecommunications. In the second application a Markov network is constructed for supply prediction in the automotive industry. In the third application it is tried to find weaknesses of cars and utility vehicles by learning Bayesian networks from data.

back to the top 

Last updated: Mon Aug 28 16:10:20 CEST 2006 - christian@borgelt.net