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., 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.

2 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. 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. 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.

3 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].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. Unlike linear-chain models, general CRFs can capture longdistance dependencies between labels.

4 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. Every variablev Vtakes outcomes froma setV, which can be either continuous or discrete, although we discuss only thediscrete case in this chapter.

5 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. 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.

6 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}. 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).

7 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. Essentially, a generative model is one that directly describes howthe outputs probabilistically generate the Introduction to Conditional Random Fields for Relational LearningxyxyFigure naive Bayes classifier, as a directed model (left), and as a factorgraph (right). Applications of graphical modelsIn this section we discuss a few applications of graphical models to natural languageprocessing. Although these examples are well-known, they serve both to clarify thedefinitions in the previous section, and to illustrate some ideas that will arise againin our discussion of Conditional Random Fields .

8 We devote special attention to thehidden Markov model (HMM), because it is closely related to the linear-chain ClassificationFirst we discuss the problem ofclassification, that is, predicting a single classvariableygiven a vector of featuresx= (x1, x2, .. , xK). One simple way toaccomplish this is to assume that once the class label is known, all the featuresare independent. The resulting classifier is called thenaive Bayes classifier. It isbased on a joint probability model of the form:p(y,x) =p(y)K k=1p(xk|y).( )This model can be described by the directed model shown in Figure (left). Wecan also write this model as a factor graph, by defining a factor (y) =p(y), anda factor k(y, xk) =p(xk|y) for each featurexk. This factor graph is shown inFigure (right).Another well-known classifier that is naturally represented as a graphical model islogistic regression (sometimes known as themaximum entropy classifierin the NLPcommunity).

9 In statistics, this classifier is motivated by the assumption that the logprobability, logp(y|x), of each class is a linear function ofx, plus a normalizationconstant. This leads to the Conditional distribution:p(y|x) =1Z(x)exp y+K j=1 y,jxj ,( )whereZ(x) = yexp{ y+ Kj=1 y,jxj}is a normalizing constant, and yis abias weight that acts like logp(y) in naive Bayes. Rather than using one vector perclass, as in ( ), we can use a different notation in which a single set of weights isshared across all the classes. The trick is to define a set offeature functionsthat Graphical Models5nonzero only for a single class. To do this, the feature functions can be defined asfy ,j(y,x) =1{y =y}xjfor the feature weights andfy (y,x) =1{y =y}for the biasweights. Now we can usefkto index each feature functionfy ,j, and kto indexits corresponding weight y ,j. Using this notational trick, the logistic regressionmodel becomes:p(y|x) =1Z(x)exp{K k=1 kfk(y,x)}.

10 ( )We introduce this notation because it mirrors the usual notation for conditionalrandom Sequence ModelsClassifiers predict only a single class variable, but the true power of graphicalmodels lies in their ability to model many variables that are interdependent. In thissection, we discuss perhaps the simplest form of dependency, in which the outputvariables are arranged in a sequence. To motivate this kind of model, we discuss anapplication from natural language processing, the task ofnamed-entity recognition(NER). NER is the problem of identifying and classifying proper names in text,including locations, such asChina; people, such asGeorge Bush; and organizations,such as theUnited Nations. The named-entity recognition task is, given a sentence,first to segment which words are part of entities, and then to classify each entityby type (person, organization, location, and so on). The challenge of this problemis that many named entities are too rare to appear even in a large training set, andtherefore the system must identify them based only on approach to NER is to classify each word independently as one of eitherPerson,Location,Organization, orOther(meaning not an entity).