Semi-supervised learning for Natural Language

See link.
"In the spirit of (Miller et al., 2004), our basic strategy for taking advantage of
unlabeled data is to first derive features from unlabeled data|in our case, word
clustering or mutual information features|and then use these features in a supervised
learning algorithm. (Miller et al., 2004) achieved signicant performance gains in
named-entity recognition by using word clustering features and active learning. In
this thesis, we show that another type of unlabeled data feature based on mutual
information can also signicantly improve performance."
"(Shi and Sarkar, 2005) takes a similar approach for the problem of extracting
course names from web pages. They rst solve the easier problem of identifying
course numbers on web pages and then use features based on course numbers to solve
the original problem of identifying course names. Using EM, they show that adding
those features leads to signicant improvements."
The results were not that great.

Intimate Learning: A Novel Approach for Combining Labelled and Unlabelled Data

This paper describes a bootstrapping method
closely related to co-training and scoped-learning and is used for Web information extraction task -learning course names from web pages in which we use very few labelled items as seed data (10 web pages) and combine with an unlabelled set (174 web pages). The overall performance improved the precision/recall from 3.11%/0.31% for a baseline EM-based method to 44.7%/44.1% for intimate learning. They used the WebKB dataset.

In co-training there are two views of the same data but one class - but in their approach - there's one view but labeled into two classes (target and intimate classes)

Link: Introduction to SSL

See link.
The presentation focuses on semi-supervised classification. This is a good presentation. He focuses on ssl classification algorithms. For each algorithm he describes the assumptions, details and pros/cons.

Some highlights from the presentation:
Basic objective of SSL: How does one use unlabeled data to improve classification?
Approach: Use labeled and unlabeled data to build better learners (contrast with supervised and unsupervised approaches).
Note that it is not always the case that unlabeled data will help.

Types of semi-supervised learning algorithms:
(1) Self-training:
They are easy and widely used. However, early mistakes could reinforce themselves and can't predict convergence.

(2) Generative Models: Assume one has the full generative model: p(X,Y|O). Marginalize over the labels of the unlabeled instances to estimate the parameters O. Then use MLE/MAP/Bayesian techniques. E.g. Mixture of Gaussians, Mixture of Multinomials (Naive Bayes) and HMMs. (EM, Baum-Welch). Relies heavily on EM. If the model is correct, this can be very effective and is a nice probabilistic framework. But unlabeled data might hurt if the generative model is wrong. Need to use heuristics to reduce the impact of unlabeled data.

(3) Cluster and label approach: Use cluster labels to label unlabeled data.

(4) Semi-supervised SVMs: Also known as Transductive SVMs. Maximize unlabeled data margins. Makes an assumption that unlabeled data from different classes are separated by a margin.

(5) Graph-based algorithms: Labels propagate using similar unlabeled instances. A graph is given on the labeled and unlabeled data. Instances connected by heavy edge tend to have the same label. Graph-based algorithms: mincut, harmonic
local and global consistency and manifold regularization. Can be extended to directed graphs. Performance is good if the graph is good - bad otherwise.

(6) Multiview algorithms: Split the features for an instance. Train classifiers on each split and get the classifiers to teach each other. It assumes that the feature splits are conditionally independent given the class. Less sensitive to mistakes than self-training. Models using BOTH features should do better

Final analysis: (more in the presentation):
Use the right model for the job
no pain, no gain
no model assumption, no gain
wrong model assumption, no gain, a lot of pain

Semisupervised Learning for Computational Linguistics

Semisupervised Learning for Computational Linguistics book looks interesting. The Math has been tamed down - to help build intuition.
See the review here.

What is parser adaptation?

As per this paper: Leverage labeled data from one domain and create a parser capable of parsing a different domain. Their approach is simple: Train the parser on WSJ and then parse another domain. The parser generates n-best parses which are ranked using a re-ranker. The top ranked parse is used for self-training. Re-ranking and adaptive learning are open issues.

What is "co-training"?

As per this paper : Co-training like self-training learns on its own predictions. However, co-training learns two separate models (which are assumed to be independent typically by training on disjoint feature sets). These models are applied to unlabeled data. Examples on which these two models agree are treated as labeled data for a new round of training. One could incorporate model confidence to include only examples both models are confident of.
The definitive paper is Blum and Mitchel
Also this paper by Collins and Singer.

What is "self-training"?

As per this paper : One learns a model by training on a small amount of labeled data. The model is then evaluated on a large amount of unlabeled data. Its predictions are assumed to be correct and it is retrained on the unlabeled data according to its own predictions.

What is "constraint-based" learning?

I first heard of this in the issues for the NLP workshop. I found this paper.

Incorporate domain knowledge into semi-supervised learning - incorporate task specific constraints. For example: if you are performing an IE task of extracting fields from a citation record, then one can build constraints such as fields that start with 19xx or 20xx are dates. The generated solutions can be penalized for not meeting these constraints.