Demystifying Named Entity Recognition  Part I
Recently I’ve been working on a project related to Named Entity Recognition (NER). At the very beginning, I was trying to find a wellexplained document to get myself started, but couldn’t do so (instead I found redundant pieces here and there on the Internet). My requirement is simple. It should include

what is NER

how to formulate it

what are the traditional and startoftheart models

what are the offtheshelf options

how to build a customized NER model
So this post will try to provide a complete set of explanation on these questions.
1. What is NER
Simply put, Named Entity Recognition is a technology that identifies certain entities from a sentence/paragraph/document. Like the sentence below, NER tries to tag each word with a label; Steve Jobs
and Steve Wozniak
to be PER
(persion entity), Apple
to be ORG
(organization entity) and the rest O
(not an entity).
This is useful in lots of cases. For instance, Apple Mail identifies TIME
entity in emails and makes pulling events from email to calendar much easier than before; Google Search is able to find Headquarters
entity in a relevent document to answer query questions.
So how does it actually work?
2. Mathematical Formulation
Let’s step back and see what NER is doing essentially. For a given sentence \(x_1 ... x_n\), NER decides to tag each word \(x_i\) with an entity label \(y_i\).
One obvious challenge here is one word should be tagged differently depending on its context. E.g., Apple in the example above is an organization entity, but in other contexts might be a fruit entity.
So how can we tag wisely? Basically we need two things.

a score function \(s(y_1...y_n, x_1...x_n)\), which splits out a score measuring how fit a tagging sequence \(y_1 ... y_n\) is to a given sentence \(x_1 ... x_n\). A welldesigned score function should assign a higher score to a tagging sequence that fits better.

a solver, which is able to pick the highestscoring tagging sequence among overwhelmingly large number of possible candidates. Just take a sentence with \(7\) words as an example, we are talking about \(10^7\) tagging candidates if there’s 10 unique entities to choose from. A good solver should be able to efficiently get to the best tagging sequence.
2.1 Score Function
Researchers in the field like to use probability model to build score function: a betterfitting sequence can be given a higher probability. Often times we choose conditional probability (one can use joint probablity as well), like below
\[s(y_1...y_n, x_1...x_n) = p(y_1...y_n  x_1...x_n) = \prod_{i=1}^{n} p(y_i y_1...y_{i1}, x_1...x_n)\]If we make a simplication \(p(y_i y_1...y_{i1}, x_1...x_n) \approx p(y_i  y_{i1}, x_1...x_n)\), then
\[s(y_1...y_n, x_1...x_n) = \prod_{i=1}^{n} p(y_i y_{i1}, x_1...x_n)\]Now the question becomes how do we model
\[p(y_i  y_{i1}, x_1...x_n)\]2.1.1 Model \(p(y_i  y_{i1}, x_1...x_n)\)
Following the above example, we are basically asking how likely Jobs is PER / ORG / MISC / O, if Steve is PER?
A natural thought would be to create a second score function (let’s call it local score function since it looks only at \(y_i, y_{i1}\)) with welldefined local features \(\vec{f}(y_{i1}, y_i, x_1...x_n)\):
\[s_{local}(y_{i1}, y_i, x_1...x_n) = \vec{\theta} \cdot \vec{f}(y_{i1}, y_i, x_1...x_n)\]and define probability based on the local score function:
\[p(y_i  y_{i1}, x_1...x_n) = \frac{\exp{s_{local}(y_{i1}, y_i, x_1...x_n)}}{\sum_{y'}{\exp{s_{local}(y_{i1}, y', x_1...x_n)}}} = \frac{\exp({\vec{\theta} \cdot \vec{f}(y_{i1}, y_i, x_1...x_n)})}{\sum_{y'}{\exp({\vec{\theta} \cdot \vec{f}(y_{i1}, y', x_1...x_n)})}}\]\(\vec{f} \in R^m\), is an mdimension vector, meaning there’s m predefined feature functions \(f_1...f_m\). Some feature examples could be:
\[\begin{align*} f_1(y_{i1}, y_i, x_1...x_n) = \left\{ \begin{array}{ccc} 1 & \text{if $x_{i1}, x_i$ are capitalized, $y_{i1}, y_i=\text{PER}$}\\ 0 & \text{otherwise} \end{array} \right. \end{align*}\] \[\begin{align*} f_2(y_{i1}, y_i, x_1...x_n) = \left\{ \begin{array}{ccc} 1 & \text{if $x_i$ ends in ing, $y_i=\text{O}$}\\ 0 & \text{otherwise} \end{array} \right. \end{align*}\] \[...\]At this point, once we have defined \(\vec{f}\) and picked the weights \(\theta\) for the features, we can readily calculate \(p(y_i  y_{i1}, x_1...x_n)\) and tagging score from
\[p(y_i  y_{i1}, x_1...x_n) = \frac{\exp({\vec{\theta} \cdot \vec{f}(y_{i1}, y_i, x_1...x_n)})}{\sum_{y'}{\exp({\vec{\theta} \cdot \vec{f}(y_{i1}, y', x_1...x_n)})}}\] \[s(y_1...y_n, x_1...x_n) = \prod_{i=1}^{n} \frac{\exp({\vec{\theta} \cdot \vec{f}(y_{i1}, y_i, x_1...x_n)})}{\sum_{y'}{\exp({\vec{\theta} \cdot \vec{f}(y_{i1}, y', x_1...x_n)})}}\]2.1.2 Three remaining questions
Let’s summarize here. With this framework set up, there’s only 3 questions remaining:
 how to design feature functions \(\vec{f}(y_{i1}, y_i, x_1...x_n)\)?
Traditionally it’s kinda art and requires expert knowledge in the problem domain. But recent deep learning approaches such as LSTM, BiLSTM aim to utilize large neural networks and automatically figure out suitable featurization from data.
 how to estimate weights \(\vec{\theta}\)?
\(\vec{\theta}\) can be obtained by training on data. One intuitive and popularly used method is Maximum Likelihood Estimation.
 assuming we already know \(\vec{f}, \vec{\theta}\), how to get the best fitting tag sequence \(y_1^{*}...y_n^{*}\) for a sentence \(x_1...x_n\)?
This will be the central topic in the next section  Solver section.
2.2 Solver
Now let’s assume we’ve determined \(\vec{f}, \vec{\theta}\) from expert knowledge and/or data, so our score function \(s(y_1...y_n, x_1...x_n)\) is finalized.
The job of the solver here is use the score function to efficiently get the best fitting tag sequence \(y_1^{*}...y_n^{*}\) for a given sentence \(x_1...x_n\). It’s an optimization problem:
\[y_1^{*}...y_n^{*} = \text{arg} \max_{y_1...y_n} s(y_1...y_n, x_1...x_n)\]We can definitely solve it by brutal force  it’s just that there’s \(5^7\) possible \(y_1...y_n\) sequences in the example below, meaning we have to evaluate \(5^7\) times of our score function before getting the optimal sequence.
The computation scales badly with the length of sentence.
The computation complexity is exponential  \(O(5^N)\) where \(N\) is the length of sentence.
It turns out the score function exhibits a special mathematic structure that enables us to solve the optimization problem in linear time \(O(N)\). Let’s talk about that.
2.2.1 Viterbi Algorithm
We notice our score function is a product of successive conditional probabilities \(p(y_i y_{i1}, x_1...x_n)\) as below:
\[s(y_1...y_n, x_1...x_n) = \prod_{i=1}^{n} p(y_i y_{i1}, x_1...x_n)\]You’ll see this is a very good property that allows us to optimize step by step via dynamic programming (in this case we call Viterbi Algorithm). So, bear with me for a bit…
Because of this nice and clean form, we can easily define a partial score function \(s_{partial}\)  score of the first \(k\) tags \(y_1...y_k\) for the same given sentence \(x_1...x_n\).
\[s_{partial, k}(y_1...y_k, x_1...x_n) = \prod_{i=1}^{k} p(y_i y_{i1}, x_1...x_n)\]When \(k=n\), the partial score function becomes the original score function.
We can also easily find the recursive form of the partial score function:
\[s_{partial, k}(y_1...y_k, x_1...x_n) = p(y_k y_{k1}, x_1...x_n) \cdot s_{partial, k1}(y_1...y_{k1}, x_1...x_n)\]Now, we only need answer three questions to explain the algorithm.
 How would you find highest partial score where \(k=1\), namely \(s_{partial, 1}(y_1^{*}, x_1...x_n)\)?
This is easy because it’s just a singlevariable optimization and \(y_1\) can only have 5 choices.
We can just evaluate \(s_{partial, 1}(y_1, x_1...x_n)\) for 5 times and pick the highest one. To help answer the following questions, we’ll save the 5 evaluated numbers. Here we carried out \(5\) evalutions to get \(s_{partial, 1}(y_1^{*}, x_1...x_n)\).
 How would you find highest partial score where \(k=2\), namely \(s_{partial, 2}(y_1^{*}, y_2^{*}, x_1...x_n)\)?
It’s just bivariable optimization. We can first keep \(y_2\) fixed and optimize over \(y_1\) dimension.
We can calculate the best \(s_{partial, 2}(y_1^{*},y_2=\text{PER}, x_1...x_n)\) by evaluating the following 5 products and pick the best one.
 \[p(y_2=\text{PER} y_1=\text{PER}, x_1...x_n) \cdot s_{partial, 1}(y_1=\text{PER}, x_1...x_n)\]
 \[p(y_2=\text{PER} y_1=\text{ORG}, x_1...x_n) \cdot s_{partial, 1}(y_1=\text{ORG}, x_1...x_n)\]
 \[p(y_2=\text{PER} y_1=\text{LOC}, x_1...x_n) \cdot s_{partial, 1}(y_1=\text{LOC}, x_1...x_n)\]
 \[p(y_2=\text{PER} y_1=\text{MISC}, x_1...x_n) \cdot s_{partial, 1}(y_1=\text{MISC}, x_1...x_n)\]
 \[p(y_2=\text{PER} y_1=\text{O}, x_1...x_n) \cdot s_{partial, 1}(y_1=\text{O}, x_1...x_n)\]
Note we can reuse \(s_{partial, 1}(y_1, x_1...x_n), y_1 \in \{\text{PER, ORG, LOC, MISC, O}\}\) saved from previous question.
In this manner, we have all of \(s_{partial, 2}(y_1^{*},y_2, x_1...x_n), y_2 \in \{\text{PER, ORG, LOC, MISC, O}\}\) ready and the highest of the five would be the answer. Here we carried out \(5*5=25\) evalutions to get \(s_{partial, 2}(y_1^{*}, y_2^{*}, x_1...x_n)\).
 How about \(k=3\) and beyond?
At this moment, you might have noticed that we could get \(s_{partial, 3}(y_1^{*}, y_2^{*}, y_3^{*}, x_1...x_n)\) by evaluating \(s_{partial, 3}(y_1^{*},y_2^{*}, y_3, x_1...x_n), y_3 \in \{\text{PER, ORG, LOC, MISC, O}\}\) and picking the highest of the five.
Each \(s_{partial, 3}(y_1^{*},y_2^{*}, y_3=u, x_1...x_n)\) can be easily calculated via
\[\max_{y_2} p(y_3=u y_2, x_1...x_n) \cdot s_{partial, 2}(y_1^{*}, y_2, x_1...x_n)\]Note we can reuse \(s_{partial, 2}(y_1^{*}, y_2, x_1...x_n), y_2 \in \{\text{PER, ORG, LOC, MISC, O}\}\) saved from previous question.
Similarly, it takes another 25 evalutions. Basically we can keep rolling to all the way \(k=n\) with each step forward we carry out another 25 evaluations. So the total compuation complexity is around \(25N\), namely \(O(N)\).
This post turns out to be longer than I thought, I was only able to answer the first questions raised in the beginning. And this seemingly natural approach is actually the socalled maximum entropy Markov model (MEMM) approach. There’s many more other ways to solve NER problem, which I’ll talk about in next posts together with the answers to the remaining three questions. See you soon.