Bikel et al MLJ 1999

Being edited by Rui Correia

Citation

D. M. Bikel, R. L. Schwartz, and R. M. Weischedel. An algorithm that learns what's in a name. Machine Learning Journal, 34: 211–-231, 1999.

Summary

In this paper the authors present IdentiFinder, an Hidden Markov Model approach to the Named Entity Recognition problem. Most techniques used in Named Entity Recognition until the time of the paper, were mainly based on handcrafted patterns that are completely language dependent, and not flexible to different inputs (speech input, upper case texts, etc).

This was the first paper that addressed Named Entity Recognition with HMM's, recognizing a structure in the identification of named entities, formulating it as a classification problem where a word is either part of some class or not.

Brief Description of the Method

Their solution had a model for each name-class and a model for the not-a-name text. Additionally, there are tow special states, the START-OF-SENTENCE and END-OF-SENTENCE. The figure below provides a graphical representation of the model (the dashed edges assure the completion of the graph).

Each of the regions in the above graph was modeled with a different statistical bigram language model (likelihood of words occurring within that region), meaning that each type of name is considered a different language, with separate bigram probabilities. Formally, one is trying to find the most likely sequence of name classes $NC$ given a sequence of words $NC$:

$\max P(NC|W)=\max {\frac {P(W,NC)}{P(W)}}=\max P(W,NC)$

Additionally, the authors represented words as two-element vectors. $\left\langle w,f\right\rangle$ represents a word occurrence where $w$ is the text of the word and $f$ is a feature that is assigned to it. The set of features as long as the motivation behind them can be found in the figure below. These feature require a language dependent computation, but that is simple and deterministic.

The final model that is presented is divided in two smaller models: the Top Level Model and Back-off Model & Smoothing.

The Top Level Model, the most accurate and powerful, generates the words and name-classes following three steps:

• (1) Select a name-class, conditioning on the previous class and previous word, i.e., $P(NC|NC_{-1},w_{-1})={\frac {c(NC,NC_{-1},w_{-1})}{c(NC_{-1},w_{-1})}}$.

• (2) Generate the first word inside that name-class, conditioning on the current and previous name-classes, i.e., $P(\left\langle w,f\right\rangle |NC,NC_{-1})={\frac {c(\left\langle w,f\right\rangle ,NC,NC_{-1})}{c(NC,NC_{-1})}}$.

• (3) Generate all subsequent words inside that name-class, conditioned on its predecessor, i.e., $P(\left\langle w,f\right\rangle |\left\langle w,f\right\rangle _{-1},NC)={\frac {c(\left\langle w,f\right\rangle ,\left\langle w,f\right\rangle _{-1}NC)}{c(\left\langle w,f\right\rangle _{-1},NC)}}$.

where $c(.)$

Results

• 100k words of training = 90% performance