Daume ICML 2009

Citation

"Unsupervised Search-based Structured Prediction", Hal Daume III, ICML 2009

Online Version

An online version of the paper can be found here [1]

Summary

This paper details a methodology for unsupervised SEARN. It compares the results to other methods, first on synthetic data, and then on other methods for unsupervised dependency parsing, as well as briefly touching on semi-supervised learning with SEARN.

Algorithm

The basic SEARN algorithm is described (see the SEARN wiki article for more background).

In the supervised form, the algorithm uses a sample space of $(x,y)$ pairs, where $x$ is the input and $y$ is the true output. In the unsupervised case, we must account for the fact that the algorithm must be run on an input of simply $x$, with the classifier still producing $y$.

The proposed solution is to essentially predict $y$, and then perform the normal prediction. The loss function will only be dependent on $x$, as, while we will be predicting $y$, we do not have any observed "true" outputs.

Given an input $x$, which is a sequence of length $T$, we consider the true output to be of length $2T$, where the first $T$ components will be drawn from the possible vocabulary for $y$ (that is, the possible outputs), and represent the latent structure (which we will refer to as $y<math>,andthelast<math>T$ components are the drawn from the vocabulary for the input, $x$. We can then use SEARN on this input. It is important to note that constructing features for these two parts is different:

• For $y$, the $T$ latent components, they can be based on $x$ and the partial latent structure (i.e., at $y_{t}$, we can look at $y_{1},...,y_{t-1}$)
• For $x$, the $T$ input components, they can be based on $x$ and $y$. However, the paper notes that in designing features here, the ideal feature set will be dependent on correctly predicting the latent structure correctly. This makes intuitive sense - if we correctly predict $y$, then we have an "optimal" label set.

In dealing with $\pi *$, the optimal (and thus initial) policy, it already predicts fully the true input, and it can arbitrarily/randomly predict the latent input. This gives us the ability to run the first iteration of SEARN.

The paper describes the unsupervised algorithm as follows:

• First iteration: Use $\pi =\pi *$ to classify the sequence of latent and input components. Note that $\pi *$ randomly or arbitrarily produces classifications for the latent components, and all of the costs are 0, so this won't even induce any update to the classifier for these components. The important piece is that $\pi *$ does predict classifications for the input components, and recall that these predictions will produce input symbols, taken from the true input.
• Second iteration: Given that $\pi \neq \pi *$ due to the update, we no longer are guaranteed to produce zero-cost classifications for the latent component. Given that features for the latent structure are based partially on $x$, they get either high costs if the classifier performs poorly, or low costs if it performs well. As a result, the classifier will begin to predict classifications for the latent component.
• More iterations will cause the output to be closer to the learned classifier and further from the "optimal" policy (which arbitrarily produced the classifications).

The paper also shows that, given a certain set of definitions, this approach is pretty much equivalent to the EM algorithm. It is also noteworthy that the unsupervised algorithm no longer has all of the theoretical guarantees of the supervised algorithm.

Experiments

They use two experiments in the paper. The first is a synthetic experiment using data sampled from HMMs and comparing it to other methods, while the second is applying the method to dependency parsing and comparing it to other, similar methods.

Synthetic Experiments

The first experiments involve generating synthetic data from a first order HMM and a second order HMM. The "truth" is produced by using the generating HMM to predict the sequence. The methods compared are: EM, SEARN with HMM features and using naive Bayes, and SEARN with a logistic regression classifier.

Model	States	Truth (Error Rate)	EM (Error Rate)	SEARN-NB (Error Rate)	SEARN-LR (Error Rate)
1st Order HMM	K = 2	$0.227\pm 0.107$	$0.275\pm 0.128$	$0.287\pm 0.138$	$0.276\pm 0.095$
1st Order HMM	K = 5	$0.687\pm 0.043$	$0.678\pm 0.026$	$0.688\pm 0.025$	$0.672\pm 0.022$
1st Order HMM	K = 10	$0.806\pm 0.035$	$0.762\pm 0.021$	$0.771\pm 0.019$	$0.755\pm 0.019$
2nd Order HMM	K = 2	$0.294\pm 0.072$	$0.396\pm 0.057$	$0.408\pm 0.056$	$0.271\pm 0.057$
2nd Order HMM	K = 5	$0.651\pm 0.068$	$0.695\pm 0.027$	$0.710\pm 0.016$	$0.633\pm 0.018$
2nd Order HMM	K = 10	$0.815\pm 0.032$	$0.764\pm 0.021$	$0.771\pm 0.015$	$0.705\pm 0.019$

The results from the first order HMM are uninteresting, as they are all comparable (i.e. within the standard deviation of the optimal algorithm).

Of the second order HMM results, the best performer is always the SEARN with Logistic Regression. This is due to the richer set of features that it contains.

Dependency Parsing Experiments

The more interesting experiment is about dependency parsing. It uses the WSJ10 corpus, with:

• 5301 sentences of training data
• 531 sentences of development data
• 530 sentences of blind test data

The systems compared are as follows (full paper citations at the end):

• Rand-Gen is a random generative baseline
• Rand-SEARN is the baseline given by the SEARN initial policy
• 2 versions of the model from Klein and Manning, which provides an EM-based model
  • K+M:Rand-Init is initialized with a random value
  • K+M:Smart-Init is initialized intelligently
• 3 variants on Smith and Eisner (S+E:Length, S+E:DelOrTrans1, S+E:Trans1)
• SEARN: Unsup is unsupervised SEARN
• S+E: Sup is Smith and Eisner's supervised model (for an upper bound)
• SEARN: Sup is supervised SEARN, also for an upper bound

The following table reports the accuracy of each method.

Algorithm	Training Accuracy	Test Accuracy	# of iterations
Rand-Gen	$23.5\pm 0.9$	$23.5\pm 1.3$
Rand-SEARN	$21.3\pm 0.2$	$21.0\pm 0.6$
K+M:Rand-Init	$23.6\pm 3.8$	$23.6\pm 4.3$	63.3
K+M:Smart-Init	$35.2\pm 6.6$	$35.2\pm 6.0$	64.1
S+E:Length	$33.8\pm 3.6$	$33.7\pm 5.9$	173.1
S+E:DelOrTrans1	$47.3\pm 6.0$	$47.1\pm 5.9$	132.2
S+E:Trans1	$48.8\pm 0.9$	$49.0\pm 1.5$	173.4
SEARN: Unsup	$45.8\pm 1.6$	$45.4\pm 2.2$	27.6
S+E: Sup	$79.9\pm 0.2$	$78.6\pm 0.8$	350.5
SEARN: Sup	$81.0\pm 0.3$	$81.6\pm 0.4$	24.4

Though Unsupervised SEARN doesn't perform the best (it performs worse than the the best Smith and Eisner models), it converges significantly more quickly than any of the other algorithms. The results for the supervised methods cannot be fairly compared, as SEARN contains additional features that the Smith and Eisner model does not, but it still shows a reasonable upper bound (and continues to hold the concept that SEARN converges more quickly

Semi-supervised

The unsupervised SEARN can be expanded to semi-supervised simply by using the latent component within the loss function. The results show that the semi-supervised technique, when compared to the supervised and unsupervised technique, begins with the highest accuracy (70%), and slowly grows to the maximum (of about 80%), while the supervised begins very low (~40%), and grows up to about 80% when 5000+ labeled examples have been provided. The accuracy of the unsupervised method goes from about 25% to 40%.

Related Papers

The papers on the methods compared in the experiments are:

• Smith, N. A., & Eisner, J. (2005). Guiding unsupervised grammar induction using contrastive estimation. IJCAI Wk. on Grammatical Inference Apps (pp. 73-82).
• Klein, D., & Manning, C. (2004). Corpus-based induction of syntactic structure: Models of dependency and constituency. Proc. Conf. of the Assoc. for Computational Linguistics (pp. 478-485)

Extra papers on SEARN can be found:

• Daume, H., Langford, J., and Marcu, D. 2009. Search-based structured prediction. Machine Learning. 75. 3. p297-325
• Duame, H., Langford, J., and Marcu, D. 2006. SEARN in Practice. Unpublished Manuscript