{'fraction_non_alphanumeric': 0.036661541418412456, 'fraction_numerical': 0.016000384393619067, 'mean_word_length': 4.626655852933225, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Towards well-specified semi-supervised model-based classifiers via structural adaptation

Semi-supervised learning plays an important role in large-scale machine learning. Properly using additional unlabeled data (largely available nowadays) often can improve the machine learning accuracy. However, if the machine learning model is misspecified for the underlying true data distribution, the model performance could be seriously jeopardized. This issue is known as model misspecification. To address this issue, we focus on generative models and propose a criterion to detect the onset of model misspecification by measuring the performance difference between models obtained using supervised and semi-supervised learning. Then, we propose to automatically modify the generative models during model training to achieve an unbiased generative model. Rigorous experiments were carried out to evaluate the proposed method using two image classification data sets PASCAL VOC'07 and MIR Flickr. Our proposed method has been demonstrated to outperform a number of state-of-the-art semi-supervised learning approaches for the classification task.


Introduction
Semi-supervised learning (SSL) plays an important role in many real world machine learning applications, such as image classification [Papandreou et al., 2015], speech recognition [Cui et al., 2012], and text categorization [Liu et al., 2016;Sun et al., 2012], where the cost of annotating unlabeled data is generally considered too high to afford. SSL tries to make use of additional unlabeled data together with a limited amount of labeled data to enhance model learning accuracy [Zhu et al., 2003], and thus has gained a lot of researchers' attention [Yang and Priebe, 2011;Fox-Roberts and Rosten, 2014].
However, it is generally believed that using additional unlabeled data for SSL does not always guarantee increase in model learning accuracy. Sometimes, it may end up with performance degradation. This phenomenon is known as model misspecification [Yang and Priebe, 2011;Fox-Roberts and Rosten, 2014;Bach, 2006] or safe semisupervised learning [Zhou and Li, 2010]. Yet in essence, model misspecification and safe semi-supervised learning are two concepts proposed independently, despite their common goal of designing SSL approach so that its performance, even in the worst case, is still better than that of the simple supervised learning approach [Li et al., 2016;. For safe semi-supervised learning, most of the existing approaches were proposed for non-parametric models [Li et al., 2016;Li and Zhou, 2011]. For instance, in [Li et al., 2016], they first set a baseline classifier corresponding to the supervised learners in the worst cases, and then further optimize the performance of the classifier using the proposed SSL method. The performance difference between the classifiers learned in supervised and semi-supervised manners is crucial in designing such SSL algorithms.
Approaches proposed from the perspective of model misspecification are mostly for parametric models [Yang and Priebe, 2011;Loog and Jensen, 2015;Loog, 2016] where the mismatch between the unlabeled data and the employed generative model are often used to guide the model learning. For instance, the mixture model is adopted in [Yang and Priebe, 2011] to represent both labeled and unlabeled data, which then formulates the corresponding Bayes plug-in classifier based on the mixture density functions. The performance of this Bayes plug-in classifier seriously relies on how far the learnt parameters are from the true ones. The performance degradation mainly comes from the model bias and estimation error. While how the unlabeled data could affect the SSL model performance is theoretically analysed in [Yang and Priebe, 2011], how to detect the onset of the model misspecification and how to solve the challenge have not been addressed yet. Along this line, the lower bound and upper bound of the performance of semi-supervised generative models are analyzed in [Fox-Roberts and Rosten, 2014], and then the authors propose to use the ratio of unlabeled data to labeled data to control the model performance. Inspired by these two works, we propose a generative model based approach for addressing the model misspecification issue. Different from the two aforementioned methods, we not only explore how to detect whether the model misspecification occurs, but also propose a model modification method instead of controlling the unlabeled data to be utilized.
The remaining of this paper is organized as follows. We first present related work in Section 2 and formulate the model misspecification problem using generative models in Section 3. The proposed SSL learning approach is described in Section 4. Experimental results based on two image classification datasets are reported in Section 5. We conclude the paper in Section 6.

Related Work
The difficulty to achieve a reliable semi-supervised learning method has been reported in some earlier works (e.g., [Cozman et al., 2002]). The general believe is that a better SSL model is not always guaranteed even though additional unlabeled data are used for the model learning. There exist a number of factors that may affect the SSL performance such as the quality of the training data as well as the classifier itself [Yang and Priebe, 2011]. Some researchers considered that to be the consequence of a wrong model assumption [Wang et al., 2012]. Practically, it is hard to assume a perfect generative model without any prior knowledge about the unknown data set. In [Zhou and Li, 2010;, the underlying challenge is viewed as having some unlabeled data assigned with incorrect labels which are then used to augment the labeled training data set.
Some recent research works proposed safety-aware mechanisms to restrict the SSL from using risky unlabeled data Li et al., 2016]. Other than the earlier disagreement based SSL [Bennett et al., 1998], several safe SSL approaches have been proposed, such as S3VMs [Bennett et al., 1998], S4VM [Li and Zhou, 2011] and UMVP [Li et al., 2016] with promising experimental results. However, most of them fall into the non-parametric category. To leverage on their good generalization capabilities, generative models based on SSL are common for many applications such as image classification [Yang et al., 2017]. The two most representative works addressing the model misspecification issue include [Yang and Priebe, 2011] and [Fox-Roberts and Rosten, 2014]. In [Yang and Priebe, 2011], they started with the asymptotic optimal parameters of two generative models obtained using fully supervised learning and fully unsupervised learning, respectively. Then, they proved that if the KL divergence between the distributions generated by the two generative models is small, the SSL performance is less likely to be affected by the addition of unlabeled data. More theoretical analysis was provided in [Fox-Roberts and Rosten, 2014] where the local and global bounds on the divergence of SSL are formulated. Then, they proposed an unbiased generative SSL which is defined based on an unbiased likelihood estimator exponentially controlled by the ratio of the number of labeled data over the total number of data.
Our work is different from [Yang and Priebe, 2011] and [Fox-Roberts and Rosten, 2014] as follows. We focus more on adaptively modifying the structure of the generative models instead of controlling risky data to be used. Furthermore, we propose a criterion to determine whether a model misspecification occurs or not. To the best of our knowledge, neither approaches have been considered in the literature.

Model Misspecification Problem
Given a finite number of labeled data and an infinite number of unlabeled data, it is impossible to directly detect whether the model misspecification occurs or not as the true data distribution is generally unknown. Figure 1 gives an illustrating example of the proposed approach. Assume that the model estimation error is ignored. In Figure 1 (a), the assumed semisupervised generative model (SEM) is misspecified, and its performance, in the worst case, would converge to the classification loss bound L * unsup of SEM learnt in an unsupervised manner if infinite unlabeled data were used. And the unbiased SEM [Fox-Roberts and Rosten, 2014] would converge to the classification loss bound L * sup of SEM learnt in the supervised manner. However, these classification loss bounds are higher than the best classification loss L * opt obtained by a well-specified model. Therefore, the minimum model bias from the learnt SEMs to the true data model can be approximated by L * opt − L * sup which is indicated by the loss difference, i.e., L * sup − L * unsup . Such loss difference can be approximated by the KL distance between two SEMs. If the assumed SEM is well-specified as plotted in Figure 1 (b), the classification loss bound of the SEM, unbiased SEM and the well-specified SEM will be the same, i.e., L * opt = L * sup = L * unsup , in the ideal case. Consequently, the model difference (KL) of two SEMs should be also small. Inspired by this observation, we conjecture that there must exist the model misspecification if the KL between two SEMs is getting large and therefore we can use this value to determine whether a model misspecification occurs or not. The problem is formulated in the following paragraphs.
(a) When model is misspecified.
(b) When model is well-specified. Let X := (x 1 , x 2 , · · · , x N ) T and Y := (y 1 , y 2 , · · · , y N ) T denote the training data and the corresponding label, respectively. The set of labeled data and unlabeled data are denoted as S l := (X, Y ) and S u := (x U 1 , x U 2 , · · · ) T , respectively. The mixed set of labeled and unlabeled data is denoted as D = S l S u . Suppose P (X, Y ) is the true data distribution for D and f (X, Y |Θ) denote the assumed generative model with its parameter set as Θ. A supervised generative model is obtained by learning the model parameters that best fit P (X, Y ), written as where KL(·) is the Kullback-Leibler divergence, defined as Given a generative model f (e.g. GMM) with its parameter set Θ, a popular semi-supervised learning objective function is given as, Proof. For brevity, let N l = |S l |,N u = |S u |, λ = N u /N l , following the Theorem proposed in [Cozman et al., 2003], the MLE problem in Eq.3 is stated as: Using Eq.2, Eq.5 is equivalent to Eq.4.
For this reason, [Fox-Roberts and Rosten, 2014] proposed a weighting strategy to avoid the model misspecification issue, given as The effectiveness of this strategy is quite tricky as it seriously relies on whether there are enough labeled data or not. It becomes risky when the labeled data are few. Therefore, we propose a safer strategy as follows. For a generative model f , let Θ sup denote the parameter set learnt in a supervised manner using Eq. 1. Similarly, Θ smsup , Θ usmsup , and Θ unsup are the solutions to Eqs. 4, 7, and 6, respectively, denoting original SSL models, unbiased SSL models, and unsupervised models. As the data set only contains a finite number of data points, the best estimations Θ * sup ,Θ * smsup ,Θ * usmsup , and Θ * unsup are only theoretical values. On the finite data set D,Θ S l ,Su smsup ,Θ S l ,Su usmsup are the solutions to Eqs. 4 and 7 respectively. Let L f (Θ) denote the loss of the Bayes plug-in classifier.
Corollary 2. When N l → ∞, N u → ∞ and N l /N u → 0, for the ideal solutions Θ * sup ,Θ * smsup ,Θ * usmsup , and Θ * unsup , there is, Thus, if f is incorrect, the difference betweenΘ usmsup and Θ smsup will become larger and larger when more unlabeled data are used for model learning.
This theorem shows that the semi-supervised learning yields degradation with a positive probability when more unlabeled data are introduced. The proof is straightforward and is not given due to the page limitation. By optimizing Eqs 3 and 7, two distributions f (X, Y |Θ smsup ) and f (X, Y |Θ usmsup ) can be acquired. Then, the difference between the original and the unbiased semi-supervised learning can be defined as Theorem 3. If the model f with Θ is not misspecified, So, With the proposed theorems and corollaries, we have theoretically proved that the correctness of the previous conjectures illustrated in Figure 1 and a well-specified semisupervised model-based classifier is proposed in the next Section.

The Proposed ASKKM Approach
To alleviate the model misspecification problem, we propose to adapt the model structure. In particular, we focus on kernel k-means model which can be considered as a special case of Gaussian mixture models (GMM), and explore mechanisms to learn the model structure and the model parameters to ensure the model to be well-specified. Although different model complexity measures (such as BIC [Watanabe, 2013]) have been proposed to determine the optimal generative models like GMM, these measures were designed primarily for density estimation, and thus cannot be directly applied in the semi-supervised setting to address the misspecification problem. As discussed in Section 3, we adopt the KL divergence between the original and unbiased semi-supervised learning to guide the adaptive model structure learning of a kernel kmeans model. This section presents the proposed adaptive model modification based semi-supervised kernel k-means model (ASKKM for short).

Model Misspecification Criterion
As illustrated in Figure 1, if the assumed model is misspecified, the original SEM and unbiased SEM converge to different classification loss bound. The difference between classification loss bounds is approximated by the KL divergence between two SEMs. Practically, the discrete KL divergence might be problematic when calculated on the limited number od data points. Therefore, the aggregated classification disagreement is adopted to approximate the bound difference. If the aggregated classification disagreement is large enough, then their KL divergence must be greater than 0 and thus exists model misspecification according to Theorem 3. Denote BΘ usmsup (x) and BΘ smsup (x) as the Bayes plug-in classifiers for original SEM and unbiased SEM, respectively. The criterion for model misspecification is defined as where I(·) is the indicator function. If Criterion is greater than a predefined threshold ǫ, the corresponding assumed model is determined as misspecified.
If model misspecification occurs, we gradually increase the model complexity of the employed semi-supervised generative model by modifying K, i.e., the number of components. Specially, for each labeled training data x i ∈ S l , a new label c i is assigned to it if Criterion > ǫ. The size of new label set C is then larger than that of the given class label set Y , i.e., |C| > |Y |. For the classification task, a mapping function from new label set to the given label set is defined as, (15) With this function, a new cluster is introduced for the new class label and thus the model structure is adaptively modified.

Adaptive Semi-supervised Kernel K-means Model
For the classification task, a kernel k-means is adopted in the paper, and accordingly Eqs. 4 (original SEM) and Eq.7 (un- if Z 1 l = Z 2 l then 7: modify the misspecified model and update K; 8: goto 2; 9: end if 10: end while biased SEM) can be rewritten respectively as where ϕ 1 , µ k 1 and ϕ 2 , µ k 2 are respectively the kernel maps and the centroids for the original and weighted semisupervised kernel k-means, and Z 1 and Z 2 are the cluster assignments with Z 1 = Z 1 l ∪ Z 1 u and Z 2 = Z 2 l ∪ Z 2 u . That is, if x i is assigned to the k-th cluster according to Eq. 16 or 17, z 1 i,k = 1 or z 2 i,k = 1. Intuitively speaking, the proposed approach tracks the difference between Z 1 l and Z 2 u . If Z 1 l = Z 2 u , Eq. 14 is used to check whether model misspecification occurs or not. Details of the proposed ASKKM is illustrated in Algorithm 1.

Experimental Results
For experimental evaluation, we evaluate the proposed ASKKM using two image classification data sets, i.e.,  , 2008]. PASCAL VOC'07 consists of 9,963 images from 20 classes and 804 annotated tags. Among them, 5,011 images are selected as the training set and the rest form the test set. MIR Flikr contains 25,000 images and 457 tags from 38 classes collected from the Flickr website. Among them, 12,500 images are randomly selected for training and the rest form the test set. For image feature representations, two local features (SIFT, Hue), three global histogram features (RGB, Hsv and Lab) as well as GIST are used to represent each image. We adopted different distance metrics for features of different types. In particular, the Manhattan distance, Euclidean distance and Chisquare distance are used respectively for the histogram features, the GIST features and the local features. The state-ofthe-art SSL algorithms as well as semi-supervised generative models are chosen for model comparison, including S4VM [Li and Zhou, 2011], co-training [Zhou and Li, 2005], semisupervised EM (SEM) [Fox-Roberts and Rosten, 2014] and MKL [Guillaumin et al., 2010]. In addition to utilizing the labels of images, the original MKL also utilizes the tags of images. Therefore, we extend the proposed ASKKM in the same way as what MKL does to utilize the tag information.
For performance evaluation metric, we adopt average precision (AP) which is the evaluation criterion used in PASCAL VOC competition, written as

Verification of Model Structure Modification
To evaluate how the adaptive modification on model structure could affect the model performance, experiments are performed on "car" data set of PASCAL VOC'07. For this binary classification task, K is fixed to 2 for the original SEM and ubiased SEM model [Fox-Roberts and Rosten, 2014]. However, the true data distributions for image data may contain more than two clusters (components). Therefore, the proposed ASKKM adaptively modifies K once the model misspecification is detected during the experiments. The comparison results are then plotted in Figure 2. From this figure, it is noticed that the model performance of the original SEM gradually degrades after N u > 100. The unbiased SEM is better than the original SEM as its AP value, although slightly fluctuates, almost keeps around 0.4 which does not degrade. For the performance of the ASKKM, it slowly increases at the beginning part of the curve. After N u > 100, its AP value dramatically increases where model misspecification is detected and the model structure is accordingly modified. Then, the ASKKM gradually converge with the addition of unlabeled data. The converged model performance of ASKKM is much better than that of the compared semi-supervised generative models. This verifies that a well-specified semi-supervised models could acquire a superior model performance.

Model Performance Comparison
The model performance evaluation is performed on aforementioned two image data sets. For each class in the data set, we only choose few labeled data, i.e., N l = 20 for PAS-CAL VOC'07 data set and N l = 50 for MIR Flikr data set. We not only compare our approach with two semisupervised generative models but also with the most representative semi-supervised learning algorithms such as S4VM and co-training. Experimental results are reported in Table 1 and Table 2.
From Table 1, the model performance of the ASKKM is the best on 17 classes out of 20 classes when tag information is not considered. The S4VM achieves the best AP value in class "aeroplane" and "bottle". The MAP value of the ASKKM is 17.2% higher than the second best model S4VM. It is also noticed that semi-supervised SVM based algorithms performs better than the generative model based ones. The superior performance of the proposed approach indicates the superiority of the ASKKM over the rest approaches. If tag information is considered, it is observed that MKL+tag is better than these approaches without the integration of tag informa-tion, and this is consistent with our intuition. However, the ASKKM+tag is better than MKL+tag in 16 classes and the overall MAP of the ASKKM is 10.6% higher than that of MKL+tag. This further verify the effectiveness of the proposed approach. Similar observations could be found in the evaluation results on MIR Flickr data set reported in Table 2. From these rigorous experimental results, we can conclude the proposed ASKKM is superior to the state-of-the-art semisupervised learning approaches in terms of average precision and mean average precision.

Conclusion
To learn a reliable semi-supervised models is of utmost importance. Most of existing works are non-parametric based ones and the generative model based approach is seldom studied. This paper first proposes a criterion to judge whether a