Conditional Random Fields for Modeling Structured Data

Introduction

In statistical science or machine learning, pattern recognition is the task of using measurements from an input domain X to predict their labels from an output domain Y. A typical setting is binary classification where Y ={0,1}, with 0 being the label for “objects of type A” and 1 being the label for “objects of type B.” For example, measurements of sepal and petal length and width from each of many iris plants have been used to predict the species from among the three species of iris studied by Fisher (1936). The inferred label for a specific sample of iris plants as one of three types is independent of the inferred label for another specific sample so this task does not have structure (defined below) in the output domain.

In general, there can be dependence among samples in the input domain, or output domain, or both or neither. For example, fraud detection in credit card transactions relies partly on pattern recognition methods that exploit relations among the samples (transactions), both in the input and output domains (Bolton & Hand, 2002). Pattern recognition is commonly applied to unstructured data for which the samples are independent with respect to both the input and output domains, as in Fisher’s iris data. In contrast, when there is structure in the input and output domain, i.e., sample input and sample labels are not independent, the problem is referred as structured machine learning or structured prediction. Examples, among many others, include fraud detection in credit card transactions, labeling pixel patches in images and named entity recognition (NER) in text. NER is the task of identifying and classifying proper names in text, including locations (e.g., New York, China), names of people, companies and organizations. One challenge in NER is that correctly recognizing named entities requires context – information on co-occurrence of other entities in the surrounding text. Similar situations often occur in higher-level image interpretation. For example, recognizing a scene as an office environment increases the expectation of detecting a computer inside this scene; in contrast, the expectation of a computer inside a grocery store scene is not high as in an office scene.

In addition to providing some general discussion, this chapter mainly uses image analysis applications in which there is dependence among samples (pixels or pixel patches) in the output domain because nearby pixels tend to have similar labels such as “natural” or “manmade,” as explained below. Figure 1 illustrates the role of context in disambiguating object recognition. In Figure 1, a spatial context illustrates the central element, 13 in the context of numbers versus B in the context of letters (Bruner & Minturn, 1955) and in Figure 1b, what may appear as spiders, when viewed alone out of the surrounding context, becomes the top burner grates for gas range, when viewed in the context of the whole scene.

Figure 1.

An illustration of context to improve recognition of:(a) the central element, 13 in the context of numbers vs. B in the context of letters; (b) what may appear as spiders, when viewed alone out of the surrounding context, becomes the top burner grates for gas range, when viewed in the context of the whole scene

Probabilistic graphical models (PGMs) are being increasingly used to model problems having a structured domain. PGMs are represented by two main categories of models. Directed graphical models are known as Bayesian Networks (BNs) and undirected graphical models are known as Markov Random Fields (MRF) and Conditional Random Fields (CRF). PGMs are used to express dependencies between the input and output domains as well as dependencies within domains and to enable probabilistic inferences such as answering queries using the probabilistic model (e.g., a model based on a CRF or a MRF or a BN) of the problem (such as NER in text, image segmentation, or object recognition in images). A key task is to compute the probability distribution over the variables of interest (for a test sample called the query) given the observed values of other random variables (the evidence).