Unsupervised Sequence Classification using Sequential Output Statistics

We address a class of unsupervised learning problems where the same goal of supervised learning is aimed except with no output labels provided for training classifiers. This type of unsupervised learning is highly valuable in machine learning practice since obtaining labels in training data is often costly. Instead of pairing input-output samples, we exploit sequential statistics of output labels, in the form of N-gram language models, which can be obtained independently of input data and thus with low or no cost. We introduce a novel cost function in this unsupervised learning setting, whose profiles are analyzed and shown to be highly non-convex with large barriers near the global optimum. A new stochastic primal-dual gradient method is developed to optimize this very difficult type of cost function via the use of dual variables to reduce the barriers. We demonstrate in experimental evaluation, with both synthetic and real-world data sets, that the new method for unsupervised learning gives drastically lower errors and higher learning efficiency than the standard stochastic gradient descent, reaching classification errors about twice of those obtained by fully supervised learning. We also show the crucial role of labels' sequential statistics exploited for label-free training with the new method, reflected by the significantly lower classification errors when higher-order language models are used in unsupervised learning than low-order ones.