This chapter presents a number of algorithms for particular pattern analysis tasks such as novelty-detection, classification and regression. We consider criteria for choosing particular pattern functions, in many cases derived from stability analysis of the corresponding tasks they aim to solve. The optimisation of the derived criteria can be cast in the framework of convex optimization, either as linear or convex quadratic programs. This ensures that as with the algorithms of the last chapter the methods developed here do not suffer from the problem of local minima. They include such celebrated methods as support vector machines for both classification and regression.

We start, however, by describing how to find the smallest hypersphere containing the training data in the embedding space, together with the use and analysis of this algorithm for detecting anomalous or novel data. The techniques introduced for this problem are easily adapted to the task of finding the maximal margin hyperplane or support vector solution that separates two sets of points again possibly allowing some fraction of points to be exceptions. This in turn leads to algorithms for the case of regression.

An important feature of many of these systems is that, while enforcing the learning biases suggested by the stability analysis, they also produce ‘sparse’ dual representations of the hypothesis, resulting in efficient algorithms for both training and test point evaluation. This is a result of the Karush–Kuhn–Tucker conditions, which play a crucial role in the practical implementation and analysis of these algorithms.

It is often the case that we know something about the process generating the data. For example, DNA sequences have been generated through evolution in a series of modifications from ancestor sequences, text can be viewed as being generated by a source of words perhaps reflecting the topic of the document, a time series may have been generated by a dynamical system of a certain type, 2-dimensional images by projections of a 3-dimensional scene, and so on.

For all of these data sources we have some, albeit imperfect, knowledge about the source generating the data, and hence of the type of invariances, features and similarities (in a word, patterns) that we can expect it to contain. Even simple and approximate models of the data can be used to create kernels that take account of the insight thus afforded.

Models of data can be either deterministic or probabilistic and there are also several different ways of turning them into kernels. In fact some of the kernels we have already encountered can be regarded as derived from generative data models.

However in this chapter we put the emphasis on generative models of the data that are frequently pre-existing. We aim to show how these models can be exploited to provide features for an embedding function for which the corresponding kernel can be efficiently evaluated.

Although the emphasis will be mainly on two classes of kernels induced by probabilistic models, P-kernels and Fisher kernels, other methods exist to incorporate generative information into kernel design.

As we have seen in Chapter 2, the use of kernel functions provides a powerful and principled way of detecting nonlinear relations using well-understood linear algorithms in an appropriate feature space. The approach decouples the design of the algorithm from the specification of the feature space. This inherent modularity not only increases the flexibility of the approach, it also makes both the learning algorithms and the kernel design more amenable to formal analysis. Regardless of which pattern analysis algorithm is being used, the theoretical properties of a given kernel remain the same. It is the purpose of this chapter to introduce the properties that characterise kernel functions.

We present the fundamental properties of kernels, thus formalising the intuitive concepts introduced in Chapter 2. We provide a characterization of kernel functions, derive their properties, and discuss methods for designing them. We will also discuss the role of prior knowledge in kernel-based learning machines, showing that a universal machine is not possible, and that kernels must be chosen for the problem at hand with a view to capturing our prior belief of the relatedness of different examples. We also give a framework for quantifying the match between a kernel and a learning task.

Given a kernel and a training set, we can form the matrix known as the kernel, or Gram matrix: the matrix containing the evaluation of the kernel function on all pairs of data points.

The study of patterns in data is as old as science. Consider, for example, the astronomical breakthroughs of Johannes Kepler formulated in his three famous laws of planetary motion. They can be viewed as relations that he detected in a large set of observational data compiled by Tycho Brahe.

Equally the wish to automate the search for patterns is at least as old as computing. The problem has been attacked using methods of statistics, machine learning, data mining and many other branches of science and engineering.

Pattern analysis deals with the problem of (automatically) detecting and characterising relations in data. Most statistical and machine learning methods of pattern analysis assume that the data is in vectorial form and that the relations can be expressed as classification rules, regression functions or cluster structures; these approaches often go under the general heading of ‘statistical pattern recognition’. ‘Syntactical’ or ‘structural pattern recognition’ represents an alternative approach that aims to detect rules among, for example, strings, often in the form of grammars or equivalent abstractions.

The evolution of automated algorithms for pattern analysis has undergone three revolutions. In the 1960s efficient algorithms for detecting linear relations within sets of vectors were introduced. Their computational and statistical behaviour was also analysed. The Perceptron algorithm introduced in 1957 is one example. The question of how to detect nonlinear relations was posed as a major research goal at that time.

As discussed in Chapter 1 perhaps the most important property of a pattern analysis algorithm is that it should identify statistically stable patterns. A stable relation is one that reflects some property of the source generating the data, and is therefore not a chance feature of the particular dataset. Proving that a given pattern is indeed significant is the concern of ‘learning theory’, a body of principles and methods that estimate the reliability of pattern functions under appropriate assumptions about the way in which the data was generated. The most common assumption is that the individual training examples are generated independently according to a fixed distribution, being the same distribution under which the expected value of the pattern function is small. Statistical analysis of the problem can therefore make use of the law of large numbers through the ‘concentration’ of certain random variables.

Concentration would be all that we need if we were only to consider one pattern function. Pattern analysis algorithms typically search for pattern functions over whole classes of functions, by choosing the function that best fits the particular training sample. We must therefore be able to prove stability not of a pre-defined pattern, but of one deliberately chosen for its fit to the data.

Clearly the more pattern functions at our disposal, the more likely that this choice could be a spurious pattern. The critical factor that controls how much our choice may have compromised the stability of the resulting pattern is the ‘capacity’ of the function class.

Chapter 2 introduced several methods using message passing as a mechanism for effective belief updating in BNs. The λ – π message passing method along the arcs of a BN produces exact posteriors only in tree-structured BNs. Loop cutset conditioning requires converting a nontree BN into multiple tree-structured BNs and carrying out λ – π message passing in each of them. The stochastic simulation can be applied directly to a nontree BN to compute approximate posteriors but requires massive message passing in the BN. In this chapter, we focus on concise message passing and will drop the word concise when there is no confusion. We explore the opportunities presented by reorganizing the DAG structure of a BN into a cluster graph structure. The objective is to develop an alternative exact method that uses concise message passing in a single cluster graph structure for belief updating with nontree BNs. A cluster graph consists of an interconnected set of clusters. Each cluster is a subset of nodes (variables) in the original BN. Message passing is performed between adjacent clusters in the cluster graph. We investigate under what conditions such message passing leads to correct belief updating.

Section 3.2 introduces cluster graphs. A set of conventions on how a cluster graph constrains message passing is outlined in Section 3.3.

In Chapter 7, we developed algorithms to compile a given MSBN into an LJF, and in Chapter 8, we described multiagent belief updating by message passing. We have not discussed how an MSBN is constructed. In this chapter, we address issues related to the construction of MSBNs. In particular, we study how to integrate an MSBN-based multiagent system from agents developed by independent vendors. As detailed in Chapter 6, an MSBN is characterized by a set of technical conditions. Because independently developed subnets may not satisfy these conditions collectively, automatic verification is required to avoid the “garbage in and garbage out” scenario. The verification process becomes subtle when agents are built by independent vendors and the vendors' know-how needs to be protected. We develop a set of distributed algorithms that verify the integrity of an integrated multiagent system against the technical requirements of an MSBN.

The motivations for multiagent distributed verification are presented in Section 9.2. Section 9.3 addresses the verification of subdomain division among agents. The concept of the interface graph is introduced to capture the knowledge of the system integrator about the public aspects of multiple agents. A simple method to verify the subdomain division using the interface graph is presented. Constructing the hypertree of the MSBN at the logical level once the subdomain division is validated is also described.

Chapter 4 discussed the conversion of the DAG structure of a BN into a junction tree. In a BN, the strength of probabilistic dependence between variables is encoded by conditional probability distributions. This quantitative knowledge is encoded in a junction tree model in terms of probability distributions over clusters. For flexibility, these distributions are often unnormalized and are termed potentials. This chapter addresses conversion of the conditional probability distributions of a BN into potentials in a junction tree model and how to perform belief updating by passing potentials as concise messages in a junction tree.

Section 5.2 defines basic operations over potentials: product, quotient, and marginal. Important properties of mixed operations are discussed, including associativity, order independence, and reversibility. These basic and mixed operations form the basis of message manipulation during concise message passing. Initializing of potentials in a junction tree according to the Bayesian network from which it is derived is then considered in Section 5.3. Section 5.4 presents an algorithm for message passing over a separator in a junction tree and discusses the algorithm's consequences. Extending this algorithm, Section 5.5 addresses belief updating by message passing in a junction tree model and formally establishes the correctness of the resultant belief. Processing observations is described in Section 5.6.

Guide to Chapter 5

Given a BN, its DAG structure provides the qualitative knowledge about the dependence among domain variables.

Chapters 2 through 5 studied exact probabilistic reasoning using a junction tree representation converted from a Bayesian network. The single-agent paradigm is followed in the study. Under this paradigm, a single computational entity, an agent, has access to a BN over a problem domain, converts the BN into a JT, acquires observations from the domain, reasons about the state of the domain by concise message passing over the JT, and takes actions accordingly. Such a paradigm has its limitations: A problem domain may be too complex, and thus building a single agent capable of being in charge of the reasoning task for the entire domain becomes too difficult. Examples of complex domains include designing intricate machines such as an aircraft and monitoring and troubleshooting complicated mechanisms such as chemical processes. The problem domain may spread over a large geographical area, and thus transmitting observations from many regions to a central location for processing is undesirable owing to communications cost, delay, and unreliability.

This and subsequent chapters consider the uncertain reasoning task under the multiagent paradigm in which a set of cooperating computational agents takes charge of the reasoning task of a large and complex uncertain problem domain. This chapter deals with the knowledge representation. A set of five basic assumptions is introduced to describe some ideal knowledge representation formalisms for multiagent uncertain reasoning. These assumptions are shown to give rise to a particular knowledge representation formalism termed multiply sectioned Bayesian networks (MSBNs).

This book investigates opportunities for building intelligent decision support systems offered by multiagent, distributed probabilistic reasoning. Probabilistic reasoning with graphical models, known as Bayesian networks or belief networks, has become an active field of research and practice in artificial intelligence, operations research, and statistics in the last two decades. Inspired by the success of Bayesian networks and other graphical dependence models under the centralized and single-agent paradigm, this book extends them to representation formalisms under the distributed and multiagent paradigm. The major technical challenges to such an endeavor are identified and the results from a decade's research are presented. The framework developed allows distributed representation of uncertain knowledge on a large and complex environment embedded in multiple cooperative agents and effective, exact, and distributed probabilistic inference.

Under the single-agent paradigm, many exact or approximate methods have been proposed for probabilistic reasoning using graphical models. Not all of them admit effective extension into the multiagent paradigm. Concise message passing in a compiled, treelike graphical structure has emerged from a decade's research as one class of methods that extends well into the multiagent paradigm. How to structure multiple agents' diverse knowledge on a complex environment as a set of coherent probabilistic graphical models, how to compile these models into graphical structures that support concise message passing, and how to perform concise message passing to accomplish tasks in model verification, model compilation, and distributed inference are the foci of the book. The advantages of concise message passing over alternative methods are also analyzed.

To act in a complex problem domain, a decision maker needs to know the current state of the domain in order to choose the most appropriate action. In a domain about which the decision maker has only uncertain knowledge and partial observations, it is often impossible to estimate the state of the domain with certainty. We introduce Bayesian networks as a concise graphical representation of a decision maker's probabilistic knowledge of an uncertain domain. We raise the issue of how to use such knowledge to estimate the current state of the domain effectively. To accomplish this task, the idea of message passing in graphical models is illustrated with several alternative methods. Subsequent chapters will present representational and computational techniques to address the limitation of these methods.

The basics of Bayesian probability theory are reviewed in Section 2.2. This is followed in Section 2.3 by a demonstration of the intractability of traditional belief updating using joint probability distributions. The necessary background in graph theory is then provided in Section 2.4. Section 2.5 introduces Bayesian networks as a concise graphical model for probabilistic knowledge. In Section 2.6, the fundamental idea of local computation and message passing in modern probabilistic inference using graphical models is illustrated using so-called λ – π message passing in tree-structured models. The limitation of λ – π message passing is discussed followed by the presentation of an alternative exact inference method, loop cutset conditioning, in Section 2.7 and an alternative approximate inference method, forward stochastic sampling, in Section 2.8.

In Chapters 6 through 9, we studied in detail why a set of agents over a large and complex domain should be organized into an MSBN and how. We studied how they can perform probabilistic reasoning exactly, effectively, and distributively. In this chapter, we discuss other important issues that have not yet been addressed but will merit research effort in the near future.

Multiagent Reasoning in Dynamic Domains

Practical problem domains can be static or dynamic. In a static domain, each domain variable takes a value from its space and will not change its value with time. Hence, at what instant in time an agent observes the variable makes no difference. On the other hand, in a dynamic domain, a variable may take different values from its space at different times. The temperature of a house changes after heating is turned on. The pressure of a sealed boiler at a chemical plant increases after the liquid inside boils. A patient suffers from a disease and recovers after the proper treatment. A device in a piece of equipment behaves normally until it wears out. Dynamic domains are more general, and a static domain can be viewed as a snapshot of a dynamic domain at a particular instant in time or within a time period in which the changes of variable values are ignorable.

A Bayesian network can be used to model static and dynamic domains.

Chapter 3 has shown that, in order to use concise message passing in a single cluster graph for exact belief updating with a nontree BN, one must reorganize the DAG into a junction tree. Graphical representations of probabilistic knowledge result in efficiency through the exploration of conditional independence in terms of graphical separation, as seen in Chapter 2. Therefore, the reorganization needs to preserve the independence–separation relations of the BN as much as possible. This chapter formally describes how independence is mapped into separation in different graphical structures and presents algorithms for converting a DAG dependence structure into a junction tree while preserving graphical separation to the extent possible.

Section 4.2 defines the graphical separation in three types of graphs commonly used for modeling probabilistic knowledge: u-separation in undirected graphs, d-separation in directed acyclic graphs, and h-separation in junction trees. The relation between conditional independence and the sufficient content of a message in concise message passing is established in Section 4.3. In Section 4.4, the concept of the independence map or I-map, which ties a graphical model to a problem domain based on the extent to which the model captures the conditional independence of the domain, is introduced. The concept of a moral graph is also introduced as an intermediate undirected graphical model to facilitate the conversion of a DAG model to a junction tree model. Section 4.5 introduces a class of undirected graphs known as chordal graphs and establishes the relation between chordal graphs and junction trees.