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

From Cohen Courses

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

You do not have permission to edit this page, for the following reason:

---

You can view and copy the source of this page.

== Citation == {{MyCiteconference | booktitle = Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing| coauthors = A. McCallum| date = 2009| first = K.| last = Bellare| pages = 131-140| title = Generalized Expectation Criteria for Bootstrapping Extractors using Record-Text Alignment| url = http://www.cs.umass.edu/~kedarb/papers/dbie_ge_align.pdf }} == Online version == This [[Category::Paper]] is available online [http://www.cs.umass.edu/~kedarb/papers/dbie_ge_align.pdf]. == Summary == This [[Category::paper]] presents a novel approach using [[UsesMethod::Generalized Expectation Criteria]] to train a [[UsesMethod::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 <math>(\mathbf{x}_{1}, \mathbf{y}_{1})=(<{x}_{1}[1], {x}_{1}[2], ..., {x}_{1}[m]>, <{y}_{1}[1], ..., {y}_{1}[m]>)</math>, a text sequence <math>\mathbf{x}_{2}=<{x}_{2}[1], {x}_{2}[2], ..., {x}_{2}[m]></math> and an alignment sequence <math>\mathbf{a}=<a_1, ..., a_n></math> where <math> \quad a_{i}=j </math> indicates <math>\quad(x_1[j], y_1[j]) </math> is assigned to the token <math>\quad x_{2}[i]</math>, the alignment model defines a probability distribution of the alignment sequence conditioned on the database record and the text sequence <math>(\mathbf{x}_{1}, \mathbf{y}_{1}, \mathbf{x}_{2})</math> as <math> 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)} </math> <math> 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)})} </math> <math> {\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)) ] </math> [[File:Bellare 1.png]] 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]. [[http://www.cs.umass.edu/~kedarb/dbie_expts.txt]] is a complete list of expectation criteria. Given expectation criteria <math>\mathcal{C} = <\mathbf{F}, \mathbf{P}, \mathbf{W}></math> where <math>\mathbf{F}=<f_1,...,f_l></math> is a list of binary feature functions, <math>\mathbf{P}=<p_1,...,p_l></math> is target expectations, <math>\mathbf{W}=<w_1,...,w_l></math> is weights, the objective function to optimize is the following: <math> \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}} } </math> where <math> \Delta(f, p, w, \Theta) = w( {E_{p_{\Theta}}(\mathbf{A}_{f}) \over |\mathbf{A}_{f}|} - p)^{2} </math> is the squared divergence and <math> \mathbf{A}_{f} </math> 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 <math>p_{\Lambda}</math>, is trained by minimizing the following objective function using L-BFGS. <math> 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} </math> == Experimental Result == The authors tested this method on [[UsesDataset::DBLP]] bibliographic database on a pruned label set (author, title, date, venue, volume, number, pages, editor, publisher, series, O). AlignCRF clearly outperforms other models, and ExtrCRF also achieves an error reduction of 20~35% compared to other methods. An interesting thing to note is that there is no evident decrease in the performance of AlignCRF compared to ExtrCRF, although AlignCRF is not using DB records. This is due to the benefit of having higher order (first-order) model and using noisy DB records in the test set for alignment. [[File:Bellare 2.png]] [[File:Bellare 3.png]] == Related papers == * [[RelatedPaper::Muslea, Minton and Knoblock, ICML 2002]] * [[RelatedPaper::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/ --[[User:Brendan|Brendan]] 22:51, 13 October 2011 (UTC)

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