Totally, I collect approximate 50 papers including those of basic model description such as HMM, MEMM, and CRFs and those of application oriented papers such as IE and NER, as well those of model selection related papers.
The papers are mainly gathered from ICML, ACL, NIPS, KDD, and some AI/CL related conference or journals.
1. Probabilistic Model for Information Extraction
1.1 Directed Graph Model
1.1.1 HMM
- Generative model.
- Joint probability p(x, s)
- Graph structure
Figure 1. Dependency graph structure for first-order HMM for sequences
- Independent assumption
- Labeling sequential data (by Viterbi algorithm)
Model:
Leonard E. Baum and Ted Petrie. Statistical inference for probabilistic functions of finite state Markov chains. Annual of Mathematical statistics, 37:1554-1563, 1966
Christopher Manning and Hinrich Schutze. Markov Models. Chapter 9. 1999.
Applications:
- POS Tagging
J. Kupiec. Robust part-of-speech tagging using a hidden Markov model. Computer Speech and Language, 6:225.242, 1992.
- Shallow parsing
Antonio Molina and Ferran Pla. Shallow parsing using specialized hmms. Journal of Machine Learning Research, 2:595.613, March 2002.
Ferran Pla, Antonio Molina, and Natividad Prieto. Improving text chunking by means of lexical-contextual information in statistical language models. In Proceedings of CoNLL-2000, Lisbon, Portugal, 2000.
GuoDong Zhou, Jian Su, and TongGuan Tey. Hybrid text chunking. In Proceedings of CoNLL-2000, Lisbon, Portugal, 2000.
- Speech recognition
L.R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257.285, 1989.
L. Rabiner and B.-H. Juang. Fundamentals of Speech Recognition. Prentice Hall Signal Processing Series. Prentice-Hall, Inc., 1993.
- Gene sequence analysis
R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological sequence analysis: Probabilistic models of proteins and nucleic acids. Cambridge University Press, 1998.
- Information extraction
Many papers…
Limitation:
- Joint probability distribution p(x, s). It is useful if the trained model is to be used to generate data. However, defining a joint distribution over label and observation sequences means that all possible observation sequences must be enumerated. (A task is intractable when considering long distance dependencies.)
- Cannot represent overlapping features. These features are not necessary independent.
1.1.2. MEMM
- Conditional model.
- Joint probability p(x, y)
- Graph structure
Figure 2. Dependency graph structure for first-order MEMM for sequences
- Probability of each transition may depend on non-independent, interacting features of the observation sequence.
- State-observation transition function
- Parameter estimation by using GIS and IIS.
- Labeling sequential data (by dynamic programming algorithm)
Model:
A. Berger, S. Della Pietra, and V. Della Pietra. A maximum entropy approach to natural language processing. Computational Linguistics, 22(1):39-71, 1996.
A. Ratnaparkhi. A simple introduction to maximum entropy models for natural language processing, 1997b.
A. Ratnaparkhi. Maximum Entropy Models for Natural Language Ambiguity Resolution. PhD thesis, University of Pennsylvania, 1998.
Applications:
- Information extraction
Andrew McCallum, Dayne Freitag, and Fernando Pereira. Maximum entropy Markov models for information extraction and segmentation. In Proc. ICML 2000, 2000.
- Text segmentation
McCallum, A., Freitag, D., & Pereira, F. (2000). Maximum entropy Markov models for information extraction and segmentation. Proc. 17th International Conf. on Machine Learning (pp. 591–598). Morgan Kaufmann, San Francisco, CA.
Limitation:
The Label Bias Problem
Figure 3. Finite-state acceptor for shallow parsing two sentences
The finite-state acceptor is designed to shallow parse the sentences (chunk/phrase parsing)
1) the robot wheels Fred round
2) the robot wheels are round
Decoding it by:
0123456
0127896
Assuming the probabilities of each of the transitions out of state 2 are approximately equal, the label bias problem means that the probability of each of these chunk sequences given an observation sequence x will also be roughly equal irrespective of the observation sequence x.
On the other hand, had one of the transitions out of state 2 occurred more frequently in the training data, the probability of that transition would always be greater. This situation would result in the sequence of chunk tags associated with that path being preferred irrespective of the observation sentence.
- Generative models such as HMM do not suffer from the label bias problem.
1.2 Undirected Graph Model
1.2.1 CRF
- Conditional model.
- Conditional independence.
The two variables A and B are conditional independent given C.
In the undirected graph, conditional independence means that every path from a node in A to a node in B must pass through at least one node in C.
- Graph structure
Figure 1. Graph structure of the first-order chain-structure case of CRFs for sequences
- Local function
- Potential function.
- CRFs definition. Let X and Y be jointly distributed random variables respectively ranging over observation sequences to be labeled and their corresponding label sequences, a conditional random field (X, Y) is an undirected graphical model globally conditioned on X.
- Given an undirected graph G=(V, E) such that Y={Yv|v∈V}, if
is equal to the probability 
, the
probability of Yv given X and those random variables
corresponding to nodes neighboring v in G. Then (X, Y)
is a conditional random field.
- Labeling sequential data (by dynamic programming algorithm)
Model:
John Lafferty, Andrew McCallum, and Fernando Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. ICML 2001, 2001.
University of Massachusetts
Hanna M. Wallach. Conditional Random Fields: An Introduction. Technique Report
University of Pennsylvania
- Efficient training
Hanna Wallach. Efficient Training of Conditional Random Field. Master Thesis.
University of Edinburgh
Limited memory variable-metric methods for training
University of Edinburgh
Thomas G. Dietterich. Training Conditional Random Fields via Gradient Tree Boosting. ICML 2004.
Oregon State University
The paper applies the Friedman’s gradient tree boosting method for training CRFs. In tree boosting, the CRF potential functions are represented as weighted sums of regression trees. Regression trees are learned by stage-wise optimizations similar to Adaboost, but with the objective of maximizing the conditional likelihood P(Y|X) of the CRF model.
By growing regression trees, interactions among features are introduced only as needed. As a result, gradient tree boosting scales linearly in the order of the Markov model and in the order of the feature interactions.
Yuan Qi, Martin Szummer, Thomas P. Minka. Bayesian Conditional Random Fields. AISTATS 2005.
MIT, MICROSOFT, MICROSOFT.
The BCRF is proposed for classifying interdependent and structured data, such as sequences, images, or webs. ML has the problem of overfitting. The paper proposes a method to train and inference on CRFs. In training, BCRFs approximate the posterior distribution of the parameters using a variant of the power EP model. BCRFs flatten approximation structures to increase the algorithmic stability, efficiency, and prediction accuracy. In testing, BCRFs use approximate model averaging.
Applications:
- Name entity
Andrew McCallum and Wei Li. Early Results for Named Entity Recognition with Conditional Random Fields, Feature Induction and Web-Enhanced Lexicons. Seventh Conference on Natural Language Learning (CoNLL), 2003.
The paper has investigated named entity extraction with CRFs.
- Shallow parsing
Fei Sha and Fernando Pereira. Shallow Parsing with Conditional Random Fields. Proceedings of HLT-NAACL.
University of Pennsylvania
Using CRFs for shallow parsing.
Using voted perceptron for training.
- Table extraction
Pinto, D., McCallum, A., Wei, X., & Croft, W. B. (2003). Table extraction using conditional random fields. Proceedings of the ACM SIGIR.
University of Massachusetts
Objectives:
1) Locate the table
2) Identify the row positions and types
3) Identify the column positions and types
4) Segment the table into cells
5) Tag the cells as data or headers
6) Associate data cells with their corresponding headers
- Information extraction
Trausti Kristjansson, Aron Culotta, Paul Viola, and Andrew McCallum. Interactive Information Extraction with Constrained Conditional Random Fields.
Microsoft
University of Massachusetts
1) Interactive information extraction system: the user can select the correctly extracted data, correct the mistakenly extracted data, and fill the missing data.
2) Using linear-chain random fields with two extension: a) a constrained Viterbi decoding which finds the optimal field assignments consistent with the fields explicitly specified or corrected by the user; b) a mechanism for estimating the confidence of each extracted field, so that low-confidence extractions can be highlight.
Fuchun Peng and Andrew McCallum. Accurate Information Extraction from Research Papers using Conditional Random Fields. Proceedings of Human Language Technology Conference and North American Chapter of the Association for Computational Linguistics (HLT-NAACL), 2004.
University of Massachusetts
Applies CRFs to extraction from research paper headers and reference sections, to obtain current best-in-the-world accuracy. Also compares some simple regularization methods.
- Object Recognition
Ariadna Quattoni, Michael Collins, and Trevor Darrell. Conditional Random Fields for Object Recognition. NIPS 2004
MIT
The authors present a discriminative part-based approach for the recognition of object classes from unsegmented cluttered scenes. Objects are modeled as flexible constellations of parts conditioned on local observations found by an interest operator. For each object class the probability of a given assignment of parts to local features is modeled by a Conditional Random Field (CRF). They propose an extension of the CRF framework that incorporates hidden variables and combines class conditional CRFs into a unified framework for part-based object recognition. The parameters of the CRF are estimated in a maximum likelihood framework and recognition proceeds by finding the most likely class under our model. The main advantage of the proposed CRF framework is that it allows us to relax the assumption of conditional independence of the observed data (i.e. local features) often used in generative approaches, an assumption that might be too restrictive for a considerable number of object classes. They illustrate the potential of the model in the task of recognizing cars from rear and side views.
Given a training set of n pairs (xi, yi), where xi is the ith image and yi is the category of the object present in xi, the goal is to learn a model that maps images to object categories.
They add hidden variables h into the CRFs model.
Parameter estimation using belief propagation.
- Biomedical Named Entities identification.
Tzong-han Tsai, Wen-Chi Chou, Shih-Hung Wu, Ting-Yi Sung, Sunita Sarawagi, Jieh Hsiang, and Wen-Lian Hsu. Integrating Linguistic Knowledge into a Conditional Random Field Framework to Identify Biomedical Named Entities. Journal of Expert Systems with Applications. 2005
Institute of Information Science, Acdemia Sinica, TaiPei.
The paper makes use of CRFs for solving biomedical named entities identification. In this work, they try to utilize available resources including dictionaries, web corpora, and lexical analyzers, and represent them as linguistic features in the CRFs model.
Limitation:
Huge computational cost in parameter estimation
2. Model Selection
2.1 Bi-directional Dependency Network
1．Kristina Toutanova, Dan Klein, Christopher D. Manning, and Yoram Singer. Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network. In Proc. of HLT-NAACL. 2003, pages 252-259.
The paper proposes a new POS tagger. In the tagger, the authors make use of both preceding and following tag context via a dependency network representation. By dependency network, they mean bidirectional dependency relationships. That is, the current state can be dependent on the preceding states and the following states.
For example, in the dependency network, the state TO is dependent on t1 and t3.
They also use broad lexical features. For example, the current state is not only predicted by the current word, but also the preceding words and the following words.
For example: t denotes the state, and w denotes the word.
In experiments, they tested kinds of features combination
Their experiments show that rich features based MEMM outperforms the traditional MEMM for the task of POS tagging.
For example:
|
Model |
Features |
Token |
Unknown |
Sentence |
|
L+L2 |
32,935 |
96.05% |
85.92% |
44.04% |
|
R+R2 |
33,423 |
95.25% |
84.49% |
37.20% |
|
L+R |
32,610 |
96.57% |
87.15% |
49.50% |
|
Model |
Features |
Token |
Unknown |
Sentence |
|
L+LL+LLL |
118,752 |
96.20% |
86.52% |
45.14% |
|
L+LL+LR+R+RR |
81,049 |
96.92% |
87.91% |
53.23% |
2. Bidirectional Inference with the Easiest-First Strategy for Tagging Sequence Data
The paper follows the above work. It tries all possible feature combination (so called decomposition structure) for the local classifier and finds the ‘best’ one.
Except for finding the best decomposition structure, the idea of the paper is similar to that in the above paper.
2.1 The paper extends the decoding algorithm in dependency networks so as to support the structure decomposition. (However, there are some faults in its decomposition formula and the algorithms for bidirectional inference for the first-order conditional markov models.)
2.2 The paper also proposes a decoding method by using the easiest-first strategy. The algorithm can be described as follows:
1) Find the “easiest” word to tag.
2) Tag the word.
3) Go back to step 1), until all the words are tagged.
The “easiest” word to tag is the word for which the local classifier outputs the highest probability.
The algorithm, in its first iteration, selects the word by P(s|xi). And then, in the second iteration, it selects the second “easiest” word by P(s|s’xi), where s’ is the tag to the first “easiest” word.
The algorithm uses maximum entropy classifier as the local classifier.
Thinking:
1) Whether it is useful to replace the local classifier (ME) by the SVMs.
2.2 Variable Markov Model
1. Dana Ron, Yoram Singer, and Naftali Tishby. Learning Probabilistic Automata with Variable Memory Length. COLT’94.
Hebrew University, Israel.
2. Gill Bejerano. Algorithm for variable length Markov chain modeling.
3. Gill Bejerano. Automata Learning and Stochastic Modeling for Biosequence Analysis. Ph.D. Thesis.
Hebrew University, Israel.
For probability prediction, the VMM model matches the longest memorized context at every point in the observation sequence.
For learning models, there are two phrases:
1) choosing the high-confidence symbol, and add it to the string set.
2) constructing the PST by the string set.
4. Yevgeny Seldin, Gill Bejerano, and Naftali Tishby. Unsupervised Sequence Segmentation by a Mixture of Switching Variable Memory Markov Sources.
Hebrew University, Israel.
The paper presents an application of VMM.
The authors make use of MDL for learning the PSTs (Prediction Suffix Trees).
Then the goal is to minimize TotalSize(λ) which is the total description length of the whole tree together with all coded data (as all data passes through the root node λ, also denoted as e in some other papers).
The algorithm works in two steps:
1) Extending all the nodes that are potentially beneficial, i.e. by using them, the description length may be decreased. In this way, those nodes whose description size is smaller than the code length of data passing through them when that data is coded using the parent node distribution are of interest.
2) Pruning nodes. If a child subtree Ts of some node s gives better compression than that of its parent nodes, keep the subtree, otherwise prune it.
Sequence Segmentation Algorithm
Given a string x generated by repeatedly switching between several different k PST models with some upper bound on the alternation rate. The task it to segment the string x into l>=k contiguous segments, with length of each segment greater than some constant value L.
They aim to find the optimal segmentation via minimizing the mutual information between x and T
Repeat until convergence:
, and to
choose the candidate h having the largest gain.
. Then 
. Here, the
functional derivative of R at f in the direction h is computed as 
is
the empirical expectation and 
is
the model expectation conditioned on x, combined with the
empirical distribution on x. The idea is that in directions h
where the functional gradient dR(f, h) is large, the model
is mismatched with the labeled data; this direction should be added to the
model to make a correction.
having
the largest gradient direction. Set 
.
for
each active f by minimizing R(f) by using quasi-Newton
method.
, and the
hidden variables 
which
take values from {1, …, K}, which are the indices of the clusters, the
goal is to search for 
having
the maximum probability. 
