  Unsupervised learning is the most challenging problem in machine learning and
especially in deep learning. Among many scenarios, we study an unsupervised
learning problem of high economic value --- learning to predict without costly
pairing of input data and corresponding labels. Part of the difficulty in this
problem is a lack of solid evaluation measures. In this paper, we take a
practical approach to grounding unsupervised learning by using the same success
criterion as for supervised learning in prediction tasks but we do not require
the presence of paired input-output training data. In particular, we propose an
objective function that aims to make the predicted outputs fit well the
structure of the output while preserving the correlation between the input and
the predicted output. We experiment with a synthetic structural prediction
problem and show that even with simple linear classifiers, the objective
function is already highly non-convex. We further demonstrate the nature of
this non-convex optimization problem as well as potential solutions. In
particular, we show that with regularization via a generative model, learning
with the proposed unsupervised objective function converges to an optimal
solution.
