[NER] Foundation of Named Entity Recognition

## Introduction
I have been interesting in the methods of extracting the named entity from given sentence so long. And at work, finally I have got an change to work on this profound domain. Hence I would like to review the domain to work proficiently and be able to distinguish from the good/bad research.
So this article is structured more practical-problem oriented.

## Start with: A survey of named entity recognition and classification
Authors: David Nadeau, Satoshi Sekine
Organisations: National Research Council Canada / New York University (at the time.)
Publish Year: 2007
Link: https://time.mk/trajkovski/thesis/li07.pdf

So, I would like to take off this journey by reviewing the foundational survey of this domain at first, then let's check the latest researches.

### Agenda
1. Observation: 1991 to 2006
    1. Language Factor
    2. Textual Genre or Domain Factor
    3. Entity Type Factor
    4. What's next?
2. Learning Methods
    1. Supervised Learning
    2. Semi-Supervised Learning
    3. Unsupervised Learning
3. Feature Space for NERC
    1. Word-Level Features
    2. List Lookup Features
    3. Document and Corpus Features
4. Evaluation of NERC
    1. MUC-Match Evaluation
    2. ACEvaluation
5. Conclusion

### 1. Observation: 1991 to 2006
MUC: message understanding conference established in 1996, and NLP was coined from this place!
NERC: Named Entity Recognition and Classificaiton

#### 1.1. Language Factor
In 1991, mainly researchers focused on how to extract names from the sentence and the boom was created by the paper by Lisa F.Rau in this year.
While this stream had not change so much and the development speed in this domain was getting slow. Then at the year of 1996, because of the establishment of famous conference, the evolution speeded up and grew rapidly.

#### 1.2. Textual Genre or Domain Factor
It's been neglected so long before 2001 because there was relatively less success case.

#### 1.3. Entity Type Factor
Actually definition of NER was quite vague at the time, and some stick with the extraction of names and others consider NER including miscellaneous objects in the sentence.

#### 1.4. What's next?
ML evolves from manually heuristic approach to fully automated standalone process.
This refinement helped the NLP and its researchers as well, so in section 2, we will be looking the various types of ML.

### 2. Learning Methods
#### 2.1. Supervised Learning
ML gives a generalisation to NER unlike numbers of handcrafted rules.
In fact, SL(supervised learning) approaches back in this time was going well. For instance, HMM(hidden markov model), DT(Decision Tree), Maximum Entropy Models, SVM and CRF.

#### 2.2. Semi-Supervised Learning
Semi-SL is relatively recent. I will describe the paradigm of it below.

- 1998: Regular Expression to extract book titles
- 1999: Mutual Bootstrapping
- 2001: Syntactic Relations
- 2006: Bootstrapping for disease names
- 2006: Mutual Bootstrapping to identify synonyms (e.g. X was born in November/September/December...)
- 2006: Unlabeled data selection is addressed in this year

#### 2.3. Unsupervised Learning
Typical approaches is clustering, requiring huge resources like WordNet.

- 2002: studying the problem of labeling an input word with an appropriate NE type
- 2003: methods for identification of hyponyms(a word of more specific meaning than a general or superordinate term applicable to it. For example, spoon is a hyponym of cutlery.)
- 2004: An observation that NE often appear synchronously in several news articles.
- 2005: Point-wise mutual information and information retrieval is used as a feature to assess NE classifies.

So now we have come to the discussion how to evaluate the classifier of NE.
But I will discuss it later, instead, let's focus on the features of NE at first.

### 3. Feature Space for NERC
#### 3.1. Word-Level Features
Hypothetical NE system contains three types of objects below

1) a Boolean attribute with the value true if the word is capitalized and false otherwise;
2) a numeric attribute corresponding to the length, in characters, of the word;
3) a nominal attribute corresponding to the lowercased version of the word.

And specifically as for word-level features, it contains case, punctuation, digit, character, morphology, part-of-speech and function. I would like to pick some of them to elaborate.

- 1. digit pattern: year, count of something.
- 2. common word ending: e.g. Spanish, Danish, Romanian, journalist, cyclist.

#### 3.2. List Lookup Features
In fact, List is profound definition and always can be interchangeably with the terms like "dictionary" or "lexicon" and so on. List inclusion is a way to express the relation among words, e.g. "A is a B". In this case A is likely to be able to be described by B.

<img width="713" alt="Screen Shot 2018-05-23 at 10.06.35.png" src="https://qiita-image-store.s3.amazonaws.com/0/240801/0884bea5-d40e-10f4-048d-db47e5a58073.png">
The details of this is a out of scope of this paper, so I would like to leave it to you if you are interested further.

#### 3.3. Document and corpus features
Document features are defined over both its content and its structure.
<img width="714" alt="Screen Shot 2018-05-23 at 10.14.50.png" src="https://qiita-image-store.s3.amazonaws.com/0/240801/db9fba72-c692-2992-01f6-6a79c53d2bb6.png">
The details of this is a out of scope of this paper, so I would like to leave it to you if you are interested further.

Finally we have come to the evaluation of NERC task.

### 4. Evaluation of NERC
To evaluate the classifier, many techniques are developed by researchers. And in this section we are going to take a look some of them.

- MUC evaluations: Two axes used in the MUC in 1996, which was named TYPE(finding correct type) and TEXT(extracting the correct word).
- Exact-match evaluations: NER is correct only if it is an exact match of its corresponding answer label.
- ACE evaluation

### 5. Conlusion
The NER domain has been thriving for more than two decades. But still it's growing fast with the power of NN and other techniques, so later on I would like to like this history with the recent achievement of NN models in NE domain.

## Second Paper: 
Link: http://www.cfilt.iitb.ac.in/resources/surveys/rahul-ner-survey.pdf
Author: Rahul Sharnagat
Publish Year: 2014

As for this paper, he spent some pages for explaining the basic algorithms and foundational history, so I would like to pass that part since I have already covered it above. Then directly jump into Section 5 which is about the recent advances in Deep Learning in NE.

### Recent Advances in DL
Along with the invention of deep architecture, autoencoder got an attention because of their great achievement.

1. Autoencoder: https://qiita.com/Rowing0914/items/90e00357248f908d7c6b
2. Denoising Autoencoder: https://qiita.com/Rowing0914/items/c5be9490f37d7a81350a

Then, the format of output got an attention, which is distributed representation of words.

### Variants of Representation
In order to represent the words, we have two methods generally.
1. Localised Representation: like one-hot vector
2. Distributed Representation: like word vector, word2vec

The difference among them is that, in most basic sense, a distributed representation is one that is spread out over a set of features for representation as opposed to localized approach where each feature is independent of each other.

So, based on this preprocessing technique, we have realised more powerful methods to process the words.

### Neural Probabilistic Language Model
Since this paper is a bit... misunderstood, i would like to fill this part after reading other papers.
But let me just share the imagery view of some techniques.

1. CBOW and Skipgram in word2vec
<img width="1108" alt="Screen Shot 2018-05-25 at 16.17.30.png" src="https://qiita-image-store.s3.amazonaws.com/0/240801/7c376685-0e74-dc3b-08fb-22a22429d5ae.png">
2. Deep Neural Language Model using wordEmbddings
<img width="766" alt="Screen Shot 2018-05-25 at 16.17.48.png" src="https://qiita-image-store.s3.amazonaws.com/0/240801/f50f572a-20be-ea42-4daf-7f25ea234f0f.png">

## Neural Architectures for Named Entity Recognition
Authors: Guillaume Lample♠ Miguel Ballesteros♣♠ Sandeep Subramanian♠ Kazuya Kawakami♠ Chris Dyer♠
Link: https://arxiv.org/pdf/1603.01360.pdf
Publish Year: 2016

Mainly this paper aims at introducing state-of-the-art NER technique using LSTM.
So I picked this because I think this does match our demands here!

### Introduction
In this paper they have proposed two approaches.
1. LSTM-CRF (initially proposed by Collobert et al. in 2011)
2. Stack LSTM

But LSTM-CRF outperforms, so I would like to focus on LSTM-CRF firstly.
Then talk about the Stack LSTM

### LSTM-CRF