crf-tutorial

1 An Introduction to Conditional RandomFields for Relational LearningCharles SuttonDepartment of Computer ScienceUniversity of Massachusetts, USAcasutton@cs.umass.eduhttp://www.cs.umass.edu/∼casuttonAndrew McCallumDepartment of Computer ScienceUniversity of Massachusetts, USAmccallum@cs.umass.eduhttp://www.cs.umass.edu/∼mccallum1.1 IntroductionRelational data has two characteristics: first, statistical dependencies exist betweentheentitieswewishtomodel,andsecond,eachentityoftenhasarichsetoffeaturesthat 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 thejointprobabilitydistributionp(y,x),wherethevariablesy representtheattributesof the entities that we wish to predict, and the input variables x represent ourobserved knowledge about the entities. But modeling the joint distribution canlead to difficulties when using the rich local features that can occur in relationaldata,becauseitrequiresmodelingthedistributionp(x),whichcanincludecomplexdependencies. Modeling these dependencies among inputs can lead to intractablemodels, but ignoring them can lead to reduced performance.A solution to this problem is to directly ...