Unsupervised Sequence Classification using Sequential Output Statistics
We consider learning a sequence classifier without labeled data by using sequential output statistics. The problem is highly valuable since obtaining labels in training data is often costly, while the sequential output statistics (e.g., language models) could be obtained independently of input data and thus with low or no cost. To address the problem, we propose an unsupervised learning cost function and study its properties. We show that, compared to earlier works, it is less inclined to be stuck in trivial solutions and avoids the need for a strong generative model. Although it is harder to optimize in its functional form, a stochastic primal-dual gradient method is developed to effectively solve the problem. Experiment results on real-world datasets demonstrate that the new unsupervised learning method gives drastically lower errors than other baseline methods. Specifically, it reaches test errors about twice of those obtained by fully supervised learning.
This paper presents a method for predicting a sequence of labels without a labeled training set. This is done by incorporating a prior probability on the possible output sequnces of labels, that is a linear classifier is sought such that the distribution of sequnces it predicts is close (in the KL sense) to a given prior. The authors present a cost function, an algorithm to optimize it, and experimental results on real data of predicting characters in two tasks: OCR and spell correction.
	  The paper is technically sound and generally clear. The idea is novel (some prior work is cited by the authors) and interesting. The main reason for my score is a concern regarding the difficulty of obtaining a useful prior model p_LM. Such models usually suffer from sparseness of data, that is unless the vocabulary is quite small, it is common for some test samples to have zero probability under the prior/LM learned from a training set. It is true that this isuue is well known and solutions exist in the literature, however I would like the authors to adress the influence of it on their method. Another aspect of the same issue is the scaling of the algorithm to large vocabularies and/or long sub-sequences (parameter N in the paper). Indeed, the experiments use quite a small vocabulary (29 characters) and short sub-sequences (Ngrams with N=2,3). In NLP data at word level, the vocabulary is orderes of magnitude larger.
	  Some more comments:
	  - I would also like the authors to adress the application of their method to non-NLP domains.
	  - The inclusion of the supervised solution in the figures of the 2D cost raises a question - it seems the red dot (the supervised solution) is always in a local minimum of the unsupervised cost - I don't understand why this should be the case.
	  - If it is assumed that there is a structure in the output space of sequences, why not incorporate this structure into the classifier, that is why use a point prediction p(y_t|x_t) of a single label independently of its neighbors?
	  Specific comments: 
	  (*) lines 117-118, 'negative cross entropy', isn't the following formula the cross entropy (and not the negative of it)?
	  (*) line 119, this sentence is somewhat confusing, if I understand correctly \bar p is the expected frequency of a *given* sequence {i_1,...i_n}, and not of *all* sequences.
	  (*) lines 163-166, here too the sign of the cross entropy seems to be reversed, also when referred to in the text, e.g in line 163, if p_LM goes to 0, then -log(0) is +inf and not -inf as written in the paper, and it indeed suits the sentence in line 167, since you expect that to penalize a minimization problem, some term goes to +inf and not to -inf. 
	  Typos:
	  (*) lines 173 and 174, "that p_LM" seems wrong, did the authors mean "for which p_LM" ?
	  (*) line 283, word 'rate' appears twice.