Daume ICML 2009

In progress by Francis Keith

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.

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$.

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 sampled from the possible vocabulary for $y$, and represent the latent structure, and the last $T$ components are the true input $x$. We can then use SEARN on this input.

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