Bellare 2009 generalized expectation criteria for bootstrapping extractors using record text alignment

A summary is coming soon from Daegunw!

Citation

Generalized Expectation Criteria for Bootstrapping Extractors using Record-Text Alignment, by K. Bellare, A. McCallum. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, 2009.

Online version

This Paper is available online [1].

Summary

This paper presents a novel approach using Generalized Expectation Criteria to train a Conditional Random Field model for an IE task. In a setting where there exists a database

Brief description of the method

The paper present two CRF models: AlignCRF and ExtrCRF. The first is a zero-order CRF model used to predict labels for a text sequence given a matching DB record. The other model is a first-order linear-chain CRF to extract when there is no DB record to match.

Features

• Extraction features (in AlignCRF and ExtrCRF)
  • regular expressions detecting tokens containing all characters, all digits, or all alphanumeric
  • number of characters and digits in the token (ex. [NUMCHAR=3, NUMDIGITS=1])
  • domain-specific patterns for 'date', and 'pages'
  • token identity, prefix/suffix, character n-grams
  • presence of a token in lexicons such as "last names", "publisher names", "cities
  • lexicon features within a window of 10
  • regular expression feature within a window of 10
  • token identity features within a window of 3

• Alignment features (in AlignCRF)
  • exact token match
  • approximate token match after binning Jaro-Winkler edit distance between tokens
  • substring token match
  • prefix/suffix token match (if the prefixes/suffixes match for lengths 1,2,3,4)
  • exact and approximate token matches at offsets (-1,-1) and (+1,+1) around the alignment

AlignCRF

For a database record with token sequence and label sequence $(\mathbf {x} _{1},\mathbf {y} _{1})=(<{x}_{1}[1],{x}_{1}[2],...,{x}_{1}[m]>,<{y}_{1}[1],...,{y}_{1}[m]>)$, a text sequence $\mathbf {x} _{2}=<{x}_{2}[1],{x}_{2}[2],...,{x}_{2}[m]>$ and an alignment sequence $\mathbf {a} =<a_{1},...,a_{n}>$ where $\quad a_{i}=j$ indicates $\quad (x_{1}[j],y_{1}[j])$ is assigned to the token $\quad x_{2}[i]$, the alignment model defines a probability distribution of the alignment sequence conditioned on the database record and the text sequence $(\mathbf {x} _{1},\mathbf {y} _{1},\mathbf {x} _{2})$ as

$p_{\Theta }(\mathbf {a} \vert \mathbf {x} _{1},\mathbf {y} _{1},\mathbf {x} _{2};\Theta )={exp(\sum _{t=1}^{n}{\Theta ^{\mathrm {T} }{\vec {f}}(a',\mathbf {x} _{1},\mathbf {y} _{1},\mathbf {x} _{2},t)}) \over Z_{\Theta }(\mathbf {x} _{1},\mathbf {y} _{1},\mathbf {x} _{2})}$

$p_{\Theta }(a_{t}\vert \mathbf {x} _{1},\mathbf {y} _{1},\mathbf {x} _{2};\Theta )={exp(\Theta ^{\mathrm {T} }{\vec {f}}(a_{t},\mathbf {x} _{1},\mathbf {y} _{1},\mathbf {x} _{2},t)) \over exp(\sum _{a'}{\Theta ^{\mathrm {T} }{\vec {f}}(a_{t},\mathbf {x} _{1},\mathbf {y} _{1},\mathbf {x} _{2},t)})}$

${\partial p_{\Theta }(a_{t}\vert \mathbf {x} _{1},\mathbf {y} _{1},\mathbf {x} _{2};\Theta ) \over \partial \Theta }=p_{\Theta }(a_{t}\vert \mathbf {x} _{1},\mathbf {y} _{1},\mathbf {x} _{2};\Theta )[{\vec {f}}(a_{t},\mathbf {x} _{1},\mathbf {y} _{1},\mathbf {x} _{2},t)-E_{p_{\Theta }(a)}({\vec {f}}(a,\mathbf {x} _{1},\mathbf {y} _{1},\mathbf {x} _{2},t))]$

The expectation criteria is determined in the following manner: for expectation features, for each label, the top N extraction features are selected by mutual information with that label. Also, the top N alignment features that have highest mutual information with correct labeling are selected as alignment criteria. The target expectations of these criteria are binned into 11 bins [0.05, 0.1, 0.2, ..., 0.9, 0.95]. [[2]] is a complete list of expectation criteria.

Given expectation criteria ${\mathcal {C}}=<\mathbf {F} ,\mathbf {P} ,\mathbf {W} >$ where $\mathbf {F} =<f_{1},...,f_{l}>$ is a list of binary feature functions, $\mathbf {P} =<p_{1},...,p_{l}>$ is target expectations, $\mathbf {W} =<w_{1},...,w_{l}>$ is weights, the objective function to optimize is the following:

${\mathcal {O}}(\theta ;{\mathcal {D}},{\mathcal {C}})=\max _{\Theta }{-\sum _{i=1}^{l}{\Delta (f_{i},p_{i},w_{i},\Theta )}-{{||\Theta ||^{2}} \over {2}}}$

where $\Delta (f,p,w,\Theta )=w({E_{p_{\Theta }}(\mathbf {A} _{f}) \over |\mathbf {A} _{f}|}-p)^{2}$ is the squared divergence and $\mathbf {A} _{f}$ is the alignment latent variables to apply expectation criteria. The authors use the L-BFGS algorithm to maximize the objective function.

ExtrCRF

This model, whose probability is denoted by $p_{\Lambda }$, is trained by minimizing the following objective function using L-BFGS.

$O(\Lambda ;{\mathcal {D}},\Theta )=\min _{\Lambda }{\sum _{i=1}^{K}{KL(p_{\Theta }(\mathbf {y} \vert \mathbf {X} _{2}^{(i)})\vert \vert p_{\Lambda }(\mathbf {y} \vert \mathbf {X} _{2}^{(i)}))}+||\Lambda ||^{2}/2}$

Experimental Result

The authors tested this method on DBLP bibliographic database on a pruned label set (author, title, date, venue, volume, number, pages, editor, publisher, series, O).

Related papers

• Muslea, Minton and Knoblock, ICML 2002
• McCallum and Ngiam, ICML 98

Comment

If you're further interested in active learning for NLP, you might want to see Burr Settles' review of active learning: http://active-learning.net/ --Brendan 22:51, 13 October 2011 (UTC)