1 An Introduction to Conditional Random Fields for ...

1 1 An Introduction to Conditional RandomFields for Relational LearningCharles SuttonDepartment of Computer ScienceUniversity of Massachusetts, casuttonAndrew McCallumDepartment of Computer ScienceUniversity of Massachusetts, IntroductionRelational data has two characteristics: first, statistical dependencies exist betweenthe entities we wish to model, and second, each entity often has a rich set of featuresthat can aid classification. For example, when classifying Web documents, thepage s text provides much information about the class label, but hyperlinks definea relationship between pages that can improve classification [Taskar et al.]

2 , 2002].Graphical models are a natural formalism for exploiting the dependence structureamong entities. Traditionally, graphical models have been used to represent thejoint probability distributionp(y,x), where the variablesyrepresent the attributesof the entities that we wish to predict, and the input variablesxrepresent ourobserved knowledge about the entities. But modeling the joint distribution canlead to difficulties when using the rich local features that can occur in relationaldata, because it requires modeling the distributionp(x), which can include complexdependencies.

3 Modeling these dependencies among inputs can lead to intractablemodels, but ignoring them can lead to reduced solution to this problem is to directly model the Conditional distributionp(y|x),which is sufficient for classification. This is the approach taken byconditional ran-dom Fields [Lafferty et al., 2001]. A Conditional Random field is simply a conditionaldistributionp(y|x) with an associated graphical structure. Because the model is2An Introduction to Conditional Random Fields for Relational Learningconditional, dependencies among the input variablesxdo not need to be explicitlyrepresented, affording the use of rich, global features of the input.

4 For example,in natural language tasks, useful features include neighboring words and word bi-grams, prefixes and suffixes, capitalization, membership in domain-specific lexicons,and semantic information from sources such as WordNet. Recently there has beenan explosion of interest in CRFs, with successful applications including text process-ing [Taskar et al., 2002, Peng and McCallum, 2004, Settles, 2005, Sha and Pereira,2003], bioinformatics [Sato and Sakakibara, 2005, Liu et al., 2005], and computervision [He et al., 2004, Kumar and Hebert, 2003].

5 This chapter is divided into two parts. First, we present a tutorial on currenttraining and inference techniques for Conditional Random Fields . We discuss theimportant special case of linear-chain CRFs, and then we generalize these toarbitrary graphical structures. We include a brief discussion of techniques forpractical CRF , we present an example of applying a general CRF to a practical relationallearning problem. In particular, we discuss the problem ofinformation extraction,that is, automatically building a relational database from information containedin unstructured text.

6 Unlike linear-chain models, general CRFs can capture longdistance dependencies between labels. For example, if the same name is mentionedmore than once in a document, all mentions probably have the same label, and itis useful to extract them all, because each mention may contain different comple-mentary information about the underlying entity. To represent these long-distancedependencies, we propose askip-chain CRF, a model that jointly performs seg-mentation and collective labeling of extracted mentions. On a standard problemof extracting speaker names from seminar announcements, the skip-chain CRF hasbetter performance than a linear-chain Graphical DefinitionsWe consider probability distributions over sets of Random variablesV=X Y,whereXis a set ofinput variablesthat we assume are observed, andYis a set ofoutput variablesthat we wish to predict.

7 Every variablev Vtakes outcomes froma setV, which can be either continuous or discrete, although we discuss only thediscrete case in this chapter. We denote an assignment toXbyx, and we denotean assignment to a setA XbyxA, and similarly forY. We use the notation1{x=x }to denote an indicator function ofxwhich takes the value 1 whenx=x and 0 graphical model is a family of probability distributions that factorize accordingto an underlying graph. The main idea is to represent a distribution over a largenumber of Random variables by a product of local functions that each depend ononly a small number of variables.

8 Given a collection of subsetsA V, we Graphical Models3anundirected graphical modelas the set of all distributions that can be written inthe formp(x,y) =1Z A A(xA,yA),( )for any choice offactorsF={ A}, where A:Vn <+. (These functions arealso calledlocal functionsorcompatibility functions.) We will occasionally use thetermrandom fieldto refer to a particular distribution among those defined by anundirected model. To reiterate, we will consistently use the termmodelto refer to afamily of distributions, andrandom field(or more commonly, distribution) to referto a single constantZis a normalization factor defined asZ= x,y A A(xA,yA),( )which ensures that the distribution sums to 1.

9 The quantityZ, considered as afunction of the setFof factors, is called thepartition functionin the statisticalphysics and graphical models communities. ComputingZis intractable in general,but much work exists on how to approximate , we represent the factorization ( ) by afactor graph[Kschischanget al., 2001]. A factor graph is a bipartite graphG= (V, F, E) in which a variablenodevs Vis connected to a factor node A Fifvsis an argument to A. Anexample of a factor graph is shown graphically in Figure (right). In that figure,the circles are variable nodes, and the shaded boxes are factor this chapter, we will assume that each local function has the form A(xA,yA) = exp{ k AkfAk(xA,yA)},( )for some real-valued parameter vector A, and for some set offeature functionsorsufficient statistics{fAk}.

10 This form ensures that the family of distributions overVparameterized by is an exponential family. Much of the discussion in this chapteractually applies to exponential families in graphical model, also known as a Bayesian network, is based on a directedgraphG= (V, E). A directed model is a family of distributions that factorize as:p(y,x) = v Vp(v| (v)),( )where (v) are the parents ofvinG. An example of a directed model is shown inFigure (left).We use the termgenerative modelto refer to a directed graphical model in whichthe outputs topologically precede the inputs, that is, nox Xcan be a parent ofan outputy Y.