Conditional Random Fields Complex dependencies and/or feature functions only visible variables visible and invisible variables Markov Chains Markov Random Fields Hidden Markov Models Conditional Random Fields 1 Chains Introduction to probabilities
Conditional Random Fields As in Hidden Markov Models, we have visible and hidden random variables: 2 Hidden variables Visible variables X1 Shrek Shrek Shrek Shrek Puss Puss X2 eats eats eats eats eats eats Y2 OTH LOC OTH LOC PER PER Y1 PER PER PER PER OTH LOC X3 Puss Puss Puss Puss food Puss Y3 OTH OTH LOC LOC PER OTH P( P( P( P( P( P( )= 0.1 )= 0.01 )= 0.1 )= 0.01 )= 0.2 )= 0.012
Conditional Random Fields 3 X1 Shrek Shrek Shrek Shrek X2 eats eats eats eats Y2 OTH LOC OTH LOC Y1 PER PER PER PER X3 Puss Puss Puss Puss Y3 OTH OTH LOC LOC P( P( P( P( )= 0.1 )= 0.01 )= 0.1 )= 0.01 Let us look at the conditional probability
Conditional Random Fields 4 X1 Shrek Shrek Shrek Shrek X2 eats eats eats eats Y2 OTH LOC OTH LOC Y1 PER PER PER PER X3 Puss Puss Puss Puss Y3 OTH OTH LOC LOC P( P( P( P( )= 0.1 )= 0.01 )= 0.1 )= 0.01 Let us look at the conditional probability  does not have an influence!
A set of random variables is a  conditional random field  (CRF), if Def: Conditional Random Fields 5 where   are the neighbors of  . X1 Shrek Shrek Shrek Shrek X2 eats eats eats eats Y2 OTH LOC OTH LOC Y1 PER PER PER PER X3 Puss Puss Puss Puss Y3 OTH OTH LOC LOC P( P( P( P( )= 0.1 )= 0.01 )= 0.1 )= 0.01
Neighbors 6 A set of random variables is a  conditional random field  (CRF), if where   are the neighbors of  . We arrange the neighbors in an undirected graph, where two variables are connected if they are neighbors.   are the maximal cliques in this graph. We define Example:
Strictly positive CRFs can be “factorized”, i.e., there exist functions  such that  are the potentials. They take as input: • the entire vector  • the values of the   that are in    Special case: Factorizable CRFs 7 (We consider only factorizable CRFs) >relation to MRF
A conditional random field is basically a Markov Random Field that has  as additional, fixed, inputs.   CRFs and MRFs 8
Chain CRF  is a CRF where the neighborhood graph is a chain. The  ‐th clique is just   with the preceding  Special case: Chain CRFs Then, the cliques have only 2 elements: 9 (We consider only chain CRFs)
In a chain CRF, we have:   Syntax: Chain CRFs   We already know the projection of the  ‐th clique, it’s  . 10
In a  CRF with identical potentials , all   are the same, but have   as input:   Special case: Identical potentials    has to know  to know the position in  . 11 (We consider only CRFs with identical potentials)
In a CRF with identical potentials, the joint probability is: CRFs and HMMs   12   If   is constant: with   : ... which is the formula for  Hidden Markov Models.
Special case: CRFs with Features We define feature functions 13 ... Then we define the potential as: We define weights for the features: These form a vector  , and we define  . (We consider only CRFs with features)
CRFs with Features     14 We have and which yields
Def: CRF log likelihood   15 The log-likelihood of a CRF is
Maximizing the CRF likelihood We want to compute the best Y for X: *   P is factorized log is monotonic 16
Maximizing the CRF likelihood  does not depend on  * If we consider only singleton cliques,  . 17
Statistical NEA uses the following notations: • a corpus  • class labels  • features  • weights  Statistical NEA learns the weights   on a manually annotated training corpus  , as follows:       Given a new corpus  , it computes the annotations   as        18 Reminder: Statistical NEA This is the CRF formula, just that we considered no dependencies, i.e.,   
Conditional Random Fields Complex dependencies and/or feature functions only visible variables visible and invisible variables Markov Chains Markov Random Fields Hidden Markov Models Conditional Random Fields 19 Chains Introduction to probabilities