Unsupervised Sequence Classification using Sequential Output Statistics
Yu Liu Jianshu Chen Li Deng



Constraining stellar mass black hole mergers in AGN disks detectable with LIGO
    D.J.Rosen
    December 30, 2023
==============================================================================




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.




§ INTRODUCTION


Unsupervised learning is one of the most challenging problems in machine learning. It is often formulated as the modeling of how the world works without requiring a huge amount of human labeling effort, e.g. <cit.>. To reach this grand goal, it is necessary to first solve a sub-goal of unsupervised learning with high practical value; that is, learning to predict output labels from input data without requiring costly labeled data. Toward this end, we study in this paper the learning of a sequence classifier without labels by using sequential output statistics. The problem is highly valuable since the sequential output statistics, such as language models, could be obtained independently of the input data and thus with no labeling cost.

The problem we consider here is different from most studies on unsupervised learning, which concern automatic discovery of inherent regularities of the input data to learn their representations <cit.>. When these methods are applied in prediction tasks, either the learned representations are used as feature vectors <cit.> or the learned unsupervised models are used to initialize a supervised learning algorithm <cit.>. In both ways, the above unsupervised methods played an auxiliary role in helping supervised learning when it is applied to prediction tasks.

Recently, various solutions have been proposed to address the input-to-output prediction problem without using labeled training data, all without demonstrated successes <cit.>. Similar to this work, the authors in <cit.> proposed an unsupervised cost that also exploits the sequence prior of the output samples to train classifiers. The power of such a strong prior in the form of language models in unsupervised learning was also demonstrated in earlier studies in <cit.>. 
However, these earlier methods did not perform well in practical prediction tasks with real-world data without using additional strong generative models. Possible reasons are inappropriately formulated cost functions and inappropriate choices of optimization methods. For example, it was shown in <cit.> that optimizing the highly non-convex unsupervised cost function could easily get stuck in trivial solutions, although adding a special regularization mitigated the problem somewhat.


The solution provided in this paper fundamentally improves these prior works in <cit.> in following aspects. First, we propose a novel cost function for unsupervised learning, and find that it has a desired coverage-seeking property that makes the learning algorithm less inclined to be stuck in trivial solutions than the cost function in <cit.>. Second, we develop a special empirical formulation of this cost function that avoids the need for a strong generative model as in <cit.>. Third, although the proposed cost function is more difficult to optimize in its functional form, we develop a stochastic primal-dual gradient (SPDG) algorithm to effectively solve problem. Our analysis of SPDG demonstrates how it is able to reduce the high barriers in the cost function by transforming it into a primal-dual domain. Finally and most importantly, we demonstrate the new cost function and the associated SPDG optimization algorithm work well in two real-world classification tasks. In the rest of the paper, we proceed to demonstrate these points and discuss related works along the way.












§ EMPIRICAL-ODM: AN UNSUPERVISED LEARNING COST FOR SEQUENCE CLASSIFIERS



In this section, we extend the earlier work of <cit.>  and propose an unsupervised learning cost named Empirical Output Distribution Match (Empirical-ODM) for training classifiers without labeled data. We first formulate the unsupervised learning problem with sequential output structures. Then, we introduce the Empirical-ODM cost and discuss its important properties that are closely related to unsupervised learning.



 §.§ Problem formulation



We consider the problem of learning a sequence classifier that predicts an output sequence (y_1,…,y_T_0) from an input sequence (x_1,…,x_T_0) without using labeled data, where T_0 denotes the length of the sequence. Specifically, the learning algorithm does not have access to a labeled training set D_XY{(x_1^n,…,x_T_n^n), (y_1^n,…,y_T_n^n): n=1,…,M}, where T_n denotes the length of the n-th sequence. Instead, what is available is a collection of input sequences, denoted as D_X {(x_1^n,…,x_T_n^n): n=1,…,M}. In addition, we assume that the sequential output statistics (or sequence prior), in the form of an N-gram probability, are available:
	
    p_(i_1,…,i_N) 
    				    
    						p_(y^n_t-N+1=i_1,…,y^n_t=i_N)

where i_1,…,i_N ∈{1,…,C} and the subscript “LM” stands for language model. Our objective is to train the sequence classifier by just using D_X and p_(·). Note that the sequence prior p_(·), in the form of language models, is a type of structure commonly found in natural language data, which can be learned from a large amount of text data freely available without labeling cost. For example, in optical character recognition (OCR) tasks, y_t^n could be an English character and x_t^n is the input image containing this character. We can estimate an N-gram character-level language model p_(·) from a separate text corpus. Therefore, our learning algorithm will work in a fully unsupervised manner, without any human labeling cost. In our experiment section, we will demonstrate the effectiveness of our method on such a real OCR task. Other potential applications include speech recognition, machine translation, and image/video captioning. 

In this paper, we focus on the sequence classifier in the form of p_θ(y_t^n|x_t^n) that is, it computes the posterior probability p_θ(y_t^n|x_t^n) only based on the current input sample x_t^n in the sequence. Furthermore, we restrict our choice of p_θ(y_t^n|x_t^n) to be linear classifiers[p_θ(y_t^n = i | x_t^n) = e^γ w_i^T x_t^n /∑_j=1^C e^γ w_j^T x_t^n, where the model parameter is θ{ w_i ∈R^d, i=1,…, C}.] and focus our attention on designing and understanding unsupervised learning costs and methods for label-free prediction. In fact, as we will show in later sections, even with linear models, the unsupervised learning problem is still highly nontrivial and the cost function is also highly non-convex. And we emphasize that developing a successful unsupervised learning approach for linear classifiers, as we do in this paper, provides important insights and is an important first step towards more advanced nonlinear models (e.g., deep neural networks). We expect that, in future work, the insights obtained here could help us generalize our techniques to nonlinear models.

A recent work that shares the same motivations as our work is <cit.>, which also recognizes the high cost of obtaining labeled data and seeks label-free prediction. Different from our setting, they exploit domain knowledge from laws of physics in computer vision applications, whereas our approach exploits sequential statistics in the natural language outputs. Finally, our problem is fundamentally different from the sequence transduction method in <cit.>, although it also exploits language models for sequence prediction. Specifically, the method in <cit.> is a fully supervised learning in that it requires supervision at the sequence level; that is, for each input sequence, a corresponding output sequence (of possibly different length) is provided as a label. The use of language model in <cit.> only serves the purpose of regularization in the sequence-level supervised learning. In stark contrast, the unsupervised learning we propose does not require supervision at any level including specifically the sequence level; we do not need the sequence labels but only the prior distribution p_(·) of the output sequences.
































 §.§ The Empirical-ODM



We now introduce an unsupervised learning cost that exploits the sequence structure in p_(·). It is mainly inspired by the approach to breaking the Caesar cipher, one of the simplest forms of encryption <cit.>. Caesar cipher is a substitution cipher where each letter in the original message is replaced with a letter corresponding to a certain number of letters up or down in the alphabet. For example, the letter “D” is replaced by the letter “A”, the letter “E” is replaced by the letter “B”, and so on. In this way, the original message that was readable ends up being less understandable. The amount of this shifting is also known to the intended receiver of the message, who can decode the message by shifting back each letter in the encrypted message. However, Caesar cipher could also be broken by an unintended receiver (not knowing the shift) when it analyzes the frequencies of the letters in the encrypted messages and matches them up with the letter distribution of the original text <cit.>. More formally, let y_t=f(x_t) denote a function that maps each encrypted letter x_t into an original letter y_t. And let p_(i)  p_(y_t=i) denote the prior letter distribution of the original message, estimated from a regular text corpus. When f(·) is constructed in a way that all mapped letters {y_t: y_t = f(x_t), t=1,…,T} have the same distribution as the prior p_(i), it is able to break the Caesar cipher and recover the original letters at the mapping outputs.

Inspired by the above approach,  the posterior probability p_θ(y_t^n|x_t^n) in our classification problem can be interpreted as a stochastic mapping, which maps each input vector x_t^n (the “encrypted letter”) into an output vector y_t^n (the “original letter”) with probability p_θ(y_t^n|x_t^n). Then in a samplewise manner, each input sequence (x_1^n, …, x_T_n^n) is stochastically mapped into an output sequence (y_1^n, …, y_T_n^n). We move a step further than the above approach by requiring that the distribution of the N-grams among all the mapped output sequences are close to the prior N-gram distribution p_(i_1,…,i_N). With this motivation, we propose to learn the classifier p_θ(y_t|x_t) by minimizing the negative cross entropy between the prior distribution and the expected N-gram frequency of the output sequences:
	
    min_θ   {J(θ)
    		
    		-∑_i_1,…,i_N
    		p_ (i_1,…,i_N)
    		lnp_θ(i_1,…,i_N)
    		}

where p_θ(i_1,…,i_N) denotes the expected N-gram frequency of all the output sequences. In Appendix <ref> of the supplementary material, we derive its expression as
	
    p_θ(i_1,…,i_N)
    			   1/T∑_n=1^M ∑_t=1^T_n∏_k=0^N-1
    					p_θ(y_t-k^n = i_N-k  | x_t-k^n)

where T  T_1 + ⋯ + T_M is the total number of samples in all sequences. Note that minimizing the negative cross entropy in (<ref>) is also equivalent to minimizing the Kullback-Leibler (KL) divergence between the two distributions since they only differ by a constant term, ∑ p_ln p_. Therefore, the cost function (<ref>) seeks to estimate θ by matching the two output distributions, where the expected N-gram distribution in (<ref>) is an empirical average over all the samples in the training set.  For this reason, we name the cost (<ref>) as Empirical Output Distribution Match (Empirical-ODM) cost. 

In <cit.>, the authors proposed to minimize an output distribution match (ODM) cost, defined as the KL-divergence between the prior output distribution and the marginalized output distribution, D(p_(y) || p_θ(y)), where p_θ(y) ∫ p_θ(y|x) p(x) dx. However, evaluating p_θ(y) requires integrating over the input space using a generative model p(x). Due to the lack of such a generative model, they were not able to optimize this proposed ODM cost. Instead, alternative approaches such as Dual autoencoders and GANs were proposed as heuristics. Their results were not successful without using a few labeled data. Our proposed Empirical-ODM cost is different from the ODM cost in <cit.> in three key aspects. (i) We do not need any labeled data for training. (ii) We exploit sequence structure of output statistics, i.e., in our case y = (y_1,…,y_N) (N-gram) whereas in <cit.> y = y_t (unigram, i.e., no sequence structure). This is crucial in developing a working unsupervised learning algorithm. The change from unigram to N-gram allows us to explicitly exploit the sequence structures at the output, which makes the technique from non-working to working (see Table <ref> in Section <ref>). It might also explain why the method in <cit.> failed as it does not exploit the sequence structure. (iii) We replace the marginalized distribution p_θ(y) by the expected N-gram frequency in (<ref>). This is critical in that it allows us to directly minimize the divergence between two output distributions without the need for a generative model, which  <cit.> could not do. In fact, we can further show that p_θ(i_1,…,i_N) is an empirical approximation of p_θ(y) with y=(y_1,…,y_N) (see Appendix <ref> of the supplementary material). In this way, our cost (<ref>) can be understood as an N-gram and empirical version of the ODM cost except for an additive constant, i.e., y is replaced by y=(y_1,…,y_N) and p_θ(y) is replaced by its empirical approximation. 








 §.§ Coverage-seeking versus mode-seeking


We now discuss an important property of the proposed Empirical-ODM cost (<ref>) by comparing it with the cost proposed in <cit.>. We show that the Empirical-ODM cost has a coverage-seeking property, which makes it more suitable for unsupervised learning than the mode-seeking cost in <cit.>. 

In <cit.>, the authors proposed the expected negative log-likelihood as the unsupervised learning cost function that exploits the output sequential statistics. The intuition was to maximize the aggregated log-likelihood of all the output sequences assumed to be generated by the stochastic mapping p_θ(y_t^n|x_t^n). We show in Appendix <ref> of the supplementary material that their cost is equivalent to
	
    -∑_i_1,…, i_N-1∑_i_N p_θ(i_1,…,i_N) ln p_(i_N | i_N-1, …, i_1)

where p_(i_N | i_N-1, …, i_1)  p(y_t^n=i_N | y_t-1^n=i_N-1,…, y_t-N+1^n=i_1), and the summations are over all possible values of i_1,…,i_N ∈{1,…,C}. In contrast, we can rewrite our cost (<ref>) as
	
    -
    		   ∑_i_1,…, i_N-1		
    		p_(i_1, …, i_N-1) 
    		·∑_i_N p_(i_N|i_N-1,…,i_1)
    		lnp_θ(i_1,…,i_N)

where we used the chain rule of conditional probabilities. Note that both costs (<ref>) and (<ref>) are in a cross entropy form. However, a key difference is that the positions of the distributions p_θ(·) and p_(·) are swapped.  We show that the cost in the form of (<ref>) proposed in <cit.> is a mode-seeking divergence between two distributions, while by swapping p_θ(·) and p_(·), our cost in (<ref>) becomes a coverage-seeking divergence (see <cit.> for a detailed discussion on divergences with these two different behaviors). To understand this, we consider the following two situations:
	
		
  * If p_(i_N | i_N-1, …, i_1) → 0 and
		p_θ(i_1,…,i_N)>0 for a certain (i_1,…, i_N),
		the cross entropy in
		(<ref>) goes to +∞
		and the cross entropy in (<ref>) 
		approaches zero.
		
  * If p_(i_N | i_N-1, …, i_1) >  0 and
		p_θ(i_1,…,i_N) → 0 for a certain (i_1,…,i_N), 
		the cross entropy in (<ref>) approaches zero
		and the cross entropy in (<ref>) 
		goes to +∞.
	
Therefore, the cost function (<ref>) will heavily penalize the classifier if it predicts an output that is believed to be less probable by the prior distribution p_(·), and it will not penalize the classifier when it does not predict an output that p_(·) believes to be probable. That is, the classifier is encouraged to predict a single output mode with high probability in p_(·), a behavior called “mode-seeking” in <cit.>. This probably explains the phenomena observed in <cit.>: the training process easily converges to a trivial solution of predicting the same output that has the largest probability in p_(·). In contrast, the cost (<ref>) will heavily penalize the classifier if it does not predict the output that p_(·) is positive, and will penalize less if it predicts outputs that p_(·) is zero. That is, this cost will encourage p_θ(y|x) to cover as much of p_(·) as possible, a behavior called “coverage-seeking” in <cit.>. Therefore, training the classifier using (<ref>) will make it less inclined to learn trivial solutions than that in <cit.> since it will be heavily penalized. We will verify this fact in our experiment section <ref>. In summary, our proposed cost (<ref>) is more suitable for unsupervised learning than that in <cit.>.



 §.§ The difficulties of optimizing J(θ)



However, there are two main challenges of optimizing the Empirical-ODM cost J(θ) in (<ref>). The first one is that the sample average (over the entire training data set) in the expression of p_θ(·) (see (<ref>)) is inside the logarithmic loss, which is different from traditional machine learning problems where the average is outside loss functions (e.g., ∑_t f_t(θ)). This functional form prevents us from applying stochastic gradient descent (SGD) to minimize (<ref>) as the stochastic gradients would be intrinsically biased (see Appendix <ref> for a detailed discussion and see section <ref> for the experiment results). The second challenge is that the cost function J(θ) is highly non-convex even with linear classifiers. To see this, we visualize the profile of the cost function J(θ) (restricted to a two-dimensional sub-space) around the supervised solution in Figure <ref>.[The approach to visualizing the profile is explained with more detail in Appendix <ref>. More slices and a video of the profiles from many angles can be found in the supplementary material.] We observe that there are local optimal solutions and there are high barriers between the local and global optimal solutions. Therefore, besides the difficulty of having the sample average inside the logarithmic loss,  minimizing this cost function directly will be difficult since crossing the high barriers to reach the global optimal solution would be hard if not properly initialized.









§ THE STOCHASTIC PRIMAL-DUAL GRADIENT (SPDG) ALGORITHM



To address the first difficulty in Section <ref>, we transform the original cost (<ref>) into an equivalent min-max problem in order to bring the sample average out of the logarithmic loss. Then, we could obtain unbiased stochastic gradients to solve the problem. To this end, we first introduce the concept of convex conjugate functions. For a given convex function f(u), its convex conjugate function f^⋆(ν) is defined as f^⋆(ν) sup_u (ν^T u - f(u)) <cit.>, where u and ν are called primal and dual variables, respectively. For a scalar function f(u) = -ln u, its conjugate function can be calculated as f^⋆(ν) = -1 - ln(-ν) with ν<0. Furthermore, it holds that f(u) = sup_ν( u^T ν - f^⋆(ν) ), by which we have -ln u = max_ν ( u ν + 1 + ln(-ν) ).[The supremum is attainable and is thus replaced by maximum.] Substituting it into (<ref>), the original minimization problem becomes the following equivalent min-max problem:
	
    min_θ   max_{ν_i_1,…,i_N<0}{L(θ, V)
    			1/T∑_n=1^M∑_t=1^T_n L_t^n(θ, V)
    			+ ∑_i_1,…,i_N
    			p_(i_1,…,i_N) ln(-ν_i_1,…,i_N)
    		}

where V {ν_i_1,…,i_N} is a collection of all the dual variables ν_i_1,…,i_N, and  L_t^n(θ, V) is the t-th component function in the n-th sequence, defined as
	
    L_t^n(θ,V)
    			   ∑_i_1,…,i_N	
    					p_(i_1,…,i_N)
    					ν_i_1,…,i_N∏_k=0^N-1
    					p_θ(y_t-k^n = i_N-k | x_t-k^n)

In the equivalent min-max problem (<ref>), we find the optimal solution (θ^⋆, V^⋆) by minimizing L with respect to the primal variable θ and maximizing L with respect to the dual variable V. The obtained optimal solution to (<ref>), (θ^⋆, V^⋆),  is called the saddle point of L <cit.>. Once it is obtained, we only keep θ^⋆, which is also the optimal solution to (<ref>) and thus the model parameter. 










	
We further note that the equivalent min-max problem (<ref>) is now in a form that sums over T=T_1+⋯+T_M component functions L_t^n(θ, V). Therefore, the empirical average has been brought out of the logarithmic loss and we are ready to apply stochastic gradient methods. Specifically, we  minimize L with respect to the primal variable θ by stochastic gradient descent and maximize L with respect to the dual variable V by stochastic gradient ascent. Therefore, we name the algorithm stochastic primal-dual gradient (SPDG) method (see its details in Algorithm <ref>). We implement the SPDG algorithm in TensorFlow, which automatically computes the stochastic gradients.[The code will be released soon.] Finally, the constraint on dual variables ν_i_1,…,i_N are automatically enforced by the inherent log-barrier, ln(-ν_i_1,…,i_N), in (<ref>) <cit.>. Therefore, we do not need a separate method to enforce the constraint.





We now show that the above min-max (primal-dual) reformulation also alleviates the second difficulty discussed in Section <ref>. Similar to the case of J(θ), we examine the profile of L(θ,V) in (<ref>) (restricted to a two-dimensional sub-space) around the optimal (supervised) solution in Figure <ref> (see Appendix <ref> for the visualization details). Comparing Figure <ref> to Figure <ref>, we observe that the profile of L(θ,V) is smoother than that of J(θ) and the barrier is significantly lower. To further compare J(θ) and L(θ,V), we plot in Figure <ref> the values of J(θ) and L(θ, V) along the same line of θ^⋆ + λ_p (θ_1-θ^⋆) for different λ_p. It shows that the barrier of L(θ, V) along the primal direction is lower than that in J(θ). These observations imply that the reformulated min-max problem (<ref>) is better conditioned than the original problem (<ref>), which further justifies the use of SPDG method.




























§ EXPERIMENTS






 §.§ Experimental setup


We evaluate our unsupervised learning scheme described in earlier secitons using two classification tasks, unsupervised character-level OCR and unsupervised English Spelling Correction (Spell-Corr). In both tasks, there is no label provided during training. Hence, they are both unsupervised.



For the OCR task, we obtain our dataset from a public database UWIII English Document Image Database <cit.>, which contains images for each line of text with its corresponding groudtruth.  We first use Tesseract <cit.> to segment the image for each line of text into characters tiles and assign each tile with one character. We verify the segmentation result by training a simple neural network classifier on the segmented results and achieve 0.9% error rate on the test set. Then, we select sentence segments that are longer than 100 and contain only lowercase English characters and common punctuations (space, comma, and period). As a result, we have a vocabulary of size 29 and we obtain 1,175 sentence segments including 153,221 characters for our OCR task. To represent images, we extract VGG19 features with dim=4096, and project them into 200-dimension vectors using Principal Component Analysis. We train the language models (LM) p_(·) to provide the required output sequence statistics from both in-domain and out-of-domain data sources. The out-of-domain data sources are completely different databases, including three different language partitions (CNA, NYT, XIN) in the English Gigaword database <cit.>.

In Spell-Corr task, we learn to correct the spelling from a mis-spelled text. From the AFP partition of the Gigaword database, we select 500 sentence segments into our Spell-Corr dataset. We select sentences that are longer than 100 and contain only English characters and common punctuations, resulting in a total of 83,567 characters. The mis-spelled texts are generated by substitution simulations and are treated as our inputs. The objective of this task is to recover the original text.

[We gratefully acknowledge the discussions with Prof. Hermann Ney for private discussions on this task and his work on using likelihood as the objective function for unsupervised training.]




 §.§ Results: Comparing optimization algorithms


In the first set of experiments, we aim to evaluate the effectiveness of the SPDG method as described in Section <ref>, which is designed for optimizing the Empirical-ODM cost in Section <ref>. The analysis provided in Sections <ref> and <ref> sheds insight to why SPDG is superior to the method in <cit.> and to the standard stochastic gradient descent (SGD) method. The coverage-seeking behavior of the proposed Empirical-ODM cost helps avoid trivial solutions, and the simultaneous optimization of primal-dual variables reduces the barriers in the highly non-convex profile of the cost function. Furthermore, we do not include the methods from <cit.> because their approaches could not achieve satisfactory results without a few labeled data, while we only consider fully unsupervised learning setting. In addition, the methods in <cit.> are not optimizing the ODM cost and do not exploit the output sequential statistics.

Table 1 provides strong experimental evidence demonstrating the substantially greater effectiveness of the primal-dual method over the SGD and the method in <cit.> on both tasks. All these results are obtained by training the models until converge. Let us examine the results on the OCR in detail. First, the SPGD on the unsupervised cost function achieves 9.21% error rate, much lower than the error rates of any of mini-batch SGD runs, where the size of the mini-batches ranges from 10 to 10,000.  Note that, larger mini-batch sizes produce lower errors here because it becomes closer to full-batch gradient and thus lower bias in SGD. On the other hand, when the mini-batch size is as small as 10, the high error rate of 83.09% is close to a guess by majority rule — predicting the character (space) that has a largest proportion in the train set, i.e., 25,499/153,221 = 83.37%. Furthermore,  the method from <cit.> does not perform well no matter how we tune the hyperparameters for the generative regularization. Finally and perhaps most interestingly, with no labels provided in the training, the classification errors produced by our method are only about twice compared with supervised learning (4.63% shown in Table 1). This clearly demonstrates that the unsupervised learning scheme proposed in this paper is an effective one. For the Spelling Correction data set (see the third column in Table <ref>), we observe rather consistent results with the OCR data set.





 §.§ Results: Comparing orders of language modeling


In the second set of experiments, we examine to what extent the use of sequential statistics (e.g. 2- and 3-gram LMs) can do better than the uni-gram LM (no sequential information) in unsupervised learning. The unsupervised prediction results are shown in Table <ref>, using different data sources to estimate N-gram LM parameters. Consistent across all four ways of estimating reliable N-gram LMs, we observe significantly lower error rates when the unsupervised learning exploits 2-gram and 3-gram LM as sequential statistics compared with exploiting the prior with no sequential statistics (i.e. 1-gram). In three of four cases, exploiting a 3-gram LM gives better results than a 2-gram LM. Furthermore, the comparable error rate associated with 3-gram using out-of-domain output character data (10.17% in Table <ref>) to that using in-domain output character data (9.59% in Table <ref>) indicates that the effectiveness of the unsupervised learning paradigm presented in this paper is robust to the quality of the LM acting as the sequential prior.







§ CONCLUSIONS AND FUTURE WORK



In this paper, we study the problem of learning a sequence classifier without the need for labeled training data. The practical benefit of such unsupervised learning is tremendous. For example, in large scale speech recognition systems, the currently dominant supervised learning methods typically require a few thousand hours of training data, where each utterance in the acoustic form needs to be labeled by humans. Although there are millions of hours of natural speech data available for training, labeling all of them for supervised learning is less feasible. To make effective use of such huge amounts of acoustic data, the practical unsupervised learning approach discussed in this paper would be called for. Other potential applications such as machine translation, image and video captioning could also benefit from our paradigm. This is mainly because of their common natural language output structure, from which we could exploit the sequential structures for learning the classifier without labels. Furthermore, our proposed Empirical-ODM cost function significantly improves over the one in <cit.> by emphasizing the coverage-seeking behavior. Although the new cost function has a functional form that is more difficult to optimize, a novel SPDG algorithm is developed to effectively address the problem. An analysis of profiles of the cost functions sheds insight to why SPDG works well and why previous methods failed. Finally, we demonstrate in two datasets that our unsupervised learning method is highly effective, producing only about twice errors as fully supervised learning, which no previous unsupervised learning could produce without additional steps of supervised learning. While the current work is restricted to linear classifiers, we intend to generalize the approach to nonlinear models (e.g., deep neural nets <cit.>) in our future work. We also plan to extend our current method from exploiting N-gram LM to exploiting the currently state-of-the-art neural-LM.




plain






















§ SUPPLEMENTARY MATERIAL FOR “UNSUPERVISED SEQUENCE CLASSIFICATION USING SEQUENTIAL OUTPUT STATISTICS”




§ DERIVATION OF THE EQUIVALENT FORM OF THE COST IN <CIT.>



The cost function in <cit.> can be expressed as:
	
    [- ∑_n=1^M ln p_(y_1^n,…,y_T_n^n) | x_1^n, …, x_T_n^n ]

We now show how to derive (<ref>) from the above expression. In N-gram case, the language model can be written as
	
    p_(y_1^n,…,y_T_n^n)
    			   =
    					∏_t=1^T_n p_(y_t^n | y_t-1^n,…, y_t-N+1^n)

Substituting the above expression into the cost (<ref>), we obtain
	
    [    - ∑_n=1^M ln p_(y_1^n,…,y_T_n^n) | x_1^n, …, x_T_n^n ]
    					
       =				
    					-∑_n=1^M ∑_(y_1^n,…,y_T_n^n)∏_t=1^T_n p_θ(y_t^n | x_t^n)
    					ln p_(y_1^n,…,y_T_n^n)
    					
       =										
    					-∑_n=1^M ∑_(y_1^n,…,y_T_n^n)
    					p_θ(y_1^n | x_1^n) ⋯ p_θ(y_T_n^n | x_T_n^n)
    					 ×∑_t=1^T_nln p_ (y_t^n | y_t-1^n, …, y_t-N+1^n)
    					
       =
    					- ∑_n=1^M ∑_t=1^T_n∑_(y_1^n,…,y_T_n^n)
    					p_θ(y_1^n | x_1^n) ⋯ p_θ(y_T_n^n | x_T_n^n)
    
    
    					×ln p_ (y_t^n | y_t-1^n, …, y_t-N+1^n)
    					
       =
    					- ∑_n=1^M ∑_t=1^T_n∑_(y_t^n,…,y_t-N+1^n)
    					p_θ(y_t^n | x_t^n) ⋯ p_θ(y_t-N+1^n|x_t-N+1^n)
    
    
    					×ln p_ (y_t^n | y_t-1^n,…,y_t-N+1^n)
    					
                                 ×∑_y_1^n,…,y_t-N^n
    					p_θ(y_1^n|x_1^n)
    					⋯
    					p_θ(y_t-N^n | x_t-N^n)
    
    
                        ×∑_y_t+1^n,…,y_T_n^n
    					p_θ(y_t+1^n | x_t+1^n)
    					⋯
    					p_θ(y_T_n^n | x_T_n^n)
    					
       =
    					- ∑_n=1^M ∑_t=1^T_n∑_(y_t^n,…,y_t-N+1^n)
    					p_θ(y_t^n | x_t^n) ⋯ p_θ(y_t-N+1^n|x_t-N+1^n)
    
    
    					×ln p_ (y_t^n | y_t-1^n,…,y_t-N+1^n)
    					
       =
    					- ∑_n=1^M ∑_t=1^T_n∑_i_1,…, i_N
    					p_θ(y_t^n = i_N | x_t) ⋯ p_θ(y_t-N+1^n=i_1|x_t-N+1^n)
    
    
    					×ln p_ (y_t^n = i_N | y_t-1^n = i_N-1,…,y_t-N+1^n=i_1)
    					
       =
    					- ∑_n=1^M ∑_t=1^T_n∑_i_1,…, i_N
    					p_θ(y_t^n = i_N | x_t^n) ⋯ p_θ(y_t-N+1^n=i_1|x_t-N+1^n)
    
    
    					×ln p_ (i_N | i_N-1,…,i_1)
    					
       =
    					-  ∑_i_1,…, i_Nln p_ (i_N | i_N-1,…,i_1)
    
    
                        ×∑_n=1^M ∑_t=1^T_n
    					p_θ(y_t^n = i_N | x_t) ⋯ p_θ(y_t-N+1^n=i_1|x_t-N+1^n)
    					
       =
    					-  T ∑_i_1,…, i_Nln p_ (i_N | i_N-1,…,i_1)
    
    
                        ×1/T∑_n=1^M ∑_t=1^T_n
    					p_θ(y_t^n = i_N | x_t^n) ⋯ p_θ(y_t-N+1^n=i_1|x_t-N+1^n)







§ PROPERTIES OF P_Θ(I_1,…,I_N)





 §.§ p_θ(i_1,…,i_N) is the expected N-gram frequency of all the output sequences

In this section, we formally derive the following relation, which interprets p_θ(i_1,…,i_N) as the expected frequency of (i_1,…,i_N) in the output sequence:
	
    _∏_n=1^M ∏_t=1^T_n p_θ(y_t^n|x_t^n)[
    						n(i_1,…,i_N)/T]
    			   =
    					p_θ(i_N,…,i_1)

where T  T_1 + ⋯ T_M. Let (x_1^n,…,x_T_n^n) be a given n-th input training sequence, and let (y_1^n,…,y_T_n^n) be a sequence generated according to the posterior ∏_t=1^T_n p_θ(y_t^n|x_t^n) (which is the classifier). Furthermore, let I_t^n(i_1,…,i_N) denote the indicator function of the event {y_t-N+1^n=i_1,…,y_t^n=i_N}, and let n(i_1,…,i_N) denote the number of the N-gram (i_1,…,i_N) appearing in all the output sequences {(y_1^n,…,y_T_n^n): n=1,…,M}. Then, we have the following relation:
	
    n(i_1,…,i_N)
    			   =
    					∑_n=1^M ∑_t=1^T_nI_t^n(i_1,…,i_N)

Obviously, n(i_1,…,i_N) is a function of {(y_1^n,…,y_T_n^n): n=1,…,M} and is thus a random variable. Taking the conditional expectation of the above expression with respect to ∏_n=1^M∏_t=1^T_n p_θ(y_t^n|x_t^n), we obtain
	
    _∏_n=1^M∏_t=1^T_n p_θ(y_t^n|x_t^n) [n(i_1,…,i_N)]
    					
         =
    					∑_n=1^M ∑_t=1^T_n_∏_n=1^M∏_t=1^T_n p_θ(y_t^n|x_t^n)[ I_t^n(i_1,…,i_N) ]
    					
         =
    					∑_n=1^M ∑_t=1^T_n_∏_t=1^T_n p_θ(y_t^n|x_t^n)[ I_t^n(i_1,…,i_N) ]
    					
         (a)=∑_n=1^M∑_t=1^T_n∏_k=0^N-1
    					p_θ(y_t-k^n = i_N-k  | x_t-k^n)

where step (a) uses the fact that the expectation of an indicator function of an event equals the probability of the event.
Divide both sides by T, the right hand side of the above expression becomes p_θ(i_1,…,i_N), and we conclude our proof.	
	


 §.§ p_θ(i_N,…,i_1) is an empirical approximation of the marginal output N-gram probability



First, define the marginal N-gram probability p_θ(i_1,…, i_N) as
	
    p_θ(i_1,…, i_N)
    			   
    					p_θ(y_1=i_1,…,y_N=i_N)

For simplicity, we consider the case where the input random variables are discrete, taking finite value from a set X, then p_θ(i_1,…,i_N) can be written as
	
    p_θ(i_1,…,i_N)
    			   =
    					∑_(x_1,…,x_N) ∈X^N∏_k=1^N
    					p_θ(y_k = i_k  | x_k)
    					p(x_1,…,x_N)

To show that p_θ(i_N,…,i_1) is an empirical approximation of p_θ(i_1,…,i_N), it suffices to show that
	
    p_θ(i_1,…,i_N)
    			   =
    					∑_(x_1,…,x_N) ∈X^N∏_k=1^N
    					p_θ(y_k = i_k  | x_k)
    					p̂(x_1,…,x_N)

where p̂(x_1,…,x_N) is the empirical frequency of the N-tuple (x_1,…,x_N) in the dataset {(x_1^n,…,x_T_n^n): n=1,…,M}. The result follows in a straightforward manner from the definition of  p_θ(i_1,…,i_N):
	
    p_θ(i_1,…,i_N)
    			   =
    					1/T∑_n=1^M∑_t=1^T_n∏_k=0^N-1
    					p_θ(y_t-k^n = i_N-k  | x_t-k^n)
    					
       =
    					1/T∑_(x_1,…,x_N) ∈X^N∏_k=0^N-1
    					p_θ(y_t-k^n = i_N-k  | x_t-k^n=x_N-k)
    					×
    					n(x_1,…,x_N)
    					
       =					
    					∑_(x_1,…,x_N) ∈X^N∏_k=0^N-1
    					p_θ(y_t-k^n = i_N-k  | x_t-k^n=x_N-k)
    					×n(x_1,…,x_N)/T

where n(x_1,…,x_N) denotes the number of N-tuple (x_1,…,x_N) in the dataset {(x_1^n,…,x_T_n^n): n=1,…,M}. The second equality is simply re-organizing the summation in the first expression according to the value of (x_1,…,x_N), i.e., accumulating all the terms inside the double-summation with the same value of (x_1,…,x_N) together. Further note that p_θ(y_t-k^n = i_N-k  | x_t-k^n=x_N-k) is independent of t and n for any given values of i_N-k and x_N-k, so that
	
    ∏_k=0^N-1
    		p_θ(y_t-k^n = i_N-k  | x_t-k^n=x_N-k)
    			   =
    					∏_k=1^N
    					p_θ(y_k = i_k  | x_k)

Then, we can conclude the proof by recognizing that p̂(x_1,…,x_N) = n(x_1,…,x_N)/T.




§ OPTIMIZING EMPIRICAL-ODM BY SGD IS INTRINSICALLY BIASED



In this section, we show that the stochastic gradient of Empirical-ODM is intrinsically biased. To see this, we can express the (full batch) gradient of J(θ) as
	
    ∇_θ   J(θ)
    			=
    				-∑_i_1,…,i_N
    				p_(i_1,…,i_N)
    				1/T∑_n=1^M ∑_t^T_n∇_θ(
    					∏_k=0^N-1
    					p_θ(y_t-k^n = i_N-k | x_t-k^n)
    					)
    					/1/T∑_n=1^M ∑_t^T_n∏_k=0^N-1
    					p_θ(y_t-k^n = i_N-k | x_t-k^n)

Note that the gradient expression has sample averages in both the numerator and denominator. Therefore, full batch gradient method is less scalable as it needs to go over the entire training set to compute ∇_θJ(θ) at each update. To apply SGD, we may obtain an unbiased estimate of it by sampling the numerator with a single component while keeping the denominator the same:
	
    - ∑_i_1,…,i_N
    				p_(i_1,…,i_N)
    				∇_θ(∏_k=0^N-1
    					p_θ(y_t-k^n = i_N-k | x_t-k^n)
    					)
    					/1/T∑_n=1^M ∑_t^T_n∏_k=0^N-1
    					p_θ(y_t-k^n = i_N-k | x_t-k^n)

However, this implementation is still not scalable as it needs to average over the entire training set at each update to compute the denominator. On the other hand, if we sample both the numerator and the denominator, i.e.,
	
    - ∑_i_1,…,i_N
    				p_(i_1,…,i_N)
    				∇_θ(∏_k=0^N-1
    					p_θ(y_t-k^n = i_N-k | x_t-k^n)
    					)
    					/∏_k=0^N-1
    					p_θ(y_t-k^n = i_N-k | x_t-k^n)

then it will be a biased estimate of the gradient (<ref>). Our experiments in Section <ref> showed that this biased SGD does not perform well on the unsupervised learning problem. 



§ EXPERIMENT DETAILS


In the experiment, we implement the model with Python 2.7 and Tensorflow 0.12. 

In training of models both on OCR and Spell-Corr task, we initialize the linear model's parameters (primal variable) with w_init=1/dim(x) and γ=10, where dim(x) is the dimension of input. And we initialize the dual parameters V_init with uniformly distributed random variables v ∼ U(-1,0). We set the learning rate for primal parameter μ_θ=10^-6 and learning rate for dual parameter μ_v=10^-4. We use Adam optimization to train our model.

The test set of OCR is generated also from UWIII database,but avoiding overlap with training set. The size of test set of OCR is 15000. Furthermore, the size of the test set of Spell-Corr is also 15000 without overlapping with the training set.




§ THE DETAILS OF VISUALIZING THE HIGH-DIMENSIONAL COST FUNCTIONS



Since J(θ) is a high-dimensional function, it is hard to visualize its full profile. Instead, we use the following procedure to partially visualize J(θ). First, since the supervised learning of linear classifiers is a convex optimization problem, from which we could obtain its global optimal solution θ^⋆.[Note that, we solve the supervised learning only for the purpose of understanding our proposed unsupervised learning cost J(θ). In our implementation of the unsupervised learning algorithm, we do not use any of the training label information nor supervised learning algorithms.] Then, we randomly generate two parameter vectors θ_1 and θ_2 and plot the two-dimensional function J(θ^⋆ + λ_1(θ_1-θ^⋆) + λ_2 (θ_2-θ^⋆)) with respect to λ_1,λ_2 ∈R, which is a slice of the cost function on a two-dimensional plane.

For the profile of L(θ,V) in (<ref>), similar to the case of J(θ), in order to visualize L(θ,V), we first solve the supervised learning problem to get θ^⋆. Then we substitute θ^⋆ into (<ref>) and maximize L(θ^⋆, V) over V to obtain V^⋆={ν_i_1,…,i_N^⋆}, where
	ν_i_1,…,i_N^⋆
			=
					-1/1/T∑_n=1^M ∑_t=1^T_n∏_k=0^N-1
					p_θ^⋆(y_t-k^n = i_N-k | x_t-k^n).
We also randomly generate a (θ_1,V_1) (with the elements of V_1 being negative) and plot in Figure <ref> the values of L(θ^⋆ + λ_p (θ_1 - θ^⋆), V^⋆ + λ_d (V_1 - V^⋆)) for different λ_p, λ_d ∈R. Clearly, the optimal solution (red dot) is at the saddle point of the profile. 





§ ADDITIONAL VISUALIZATION OF J(Θ)



In Figures <ref>, <ref> and <ref>, we show three visualization examples of J(θ) for the OCR dataset on three different affine spaces, part of the first example was included in Figure <ref>. The six sub-figures in each example show the same profile from six different angles, spinning clock-wise from (a)-(f). The red dots indicate the global minimum.

In Figure <ref>, we show the same type of profiles as above except using synthetic data for of a binary classification problem. First, we sequentially generated a sequence of states from 0,1 by an hidden Markov model. Then we sample the corresponding data points from two separate 2-dimensional Gaussian models.  accordingly.






§ ADDITIONAL VISUALIZATION OF L(Θ,V)



Figure <ref> shows the profile of L(θ,V) for the OCR data set on a two-dimensional affine space viewed from nine different angles. The red dots show the saddle points of the profile, one for each angle.




















