Learning Latest Classifiers without Additional Labeled Data

1 Introduction

The performance of classifiers deteriorates over time in various applications. For example, classifiers for identifying malicious web sites would become inaccurate since malicious web sites are uninterruptedly created to scam users [Ma et al., 2009]. In activity recognition using sensor data, the classification error would increase over time since user activity patterns dynamically change [Abdallah et al., 2012]. For tasks where the performance of classifiers deteriorates, retraining classifiers is required to maintain the performance.

Tomoharu Iwata

NTT Communication Science Laboratories iwata.tomoharu@lab.ntt.co.jp

There have been many methods proposed that retrain classifiers, such as online learning [Crammer et al., 2009], forgetting algorithms [Klinkenberg, 2004], and ensemble learning [Wang et al., 2003]. These methods require labeled data to retrain classifiers. However, it is quite expensive to continuously prepare labeled data since labels need to be manually assigned by domain experts. In contrasts, unlabeled data can be easily collected. In this paper, we propose a method for learning classifiers by using newly obtained unlabeled data as well as labeled data collected beforehand.

There are two major reasons for the performance deterioration. The first is the emergence of new features that do not appear in the training phase. For example, in spammail classification, spammers endlessly create new spammails that include words (features) related to new products or services to cheat users. Therefore, new features to discriminate spam mails emerge over time. If we do not retrain the classifier, it would become impossible to classify these mails precisely [Fdez-Riverola et al., 2007]. Figure 1 shows the time variation of the cumulative number of features in the real-world spam data sets (ECUE spam in [Gama et al., 2014]). The number of features increases rapidly over time.

The other reason is the change of probability distribution by which data are governed. For example, in a brain computer-interface, the probability distribution of EEG data changes over time since EEG patterns are affected by user attention or fatigue [Li et al., 2010]. If training and test data follow different distributions, the classification performance would become poor since the classifier is learned in order to accurately classify samples generated from the training data distribution rather than samples from the test data distribution [Gama et al., 2014; Pan and Yang, 2010]. In our situation, the training data correspond to the labeled data that are collected until a certain time point, and the test data correspond to the unlabeled data that are collected after the time point, which we would like to accurately classify. Figure 2 shows distributions of a real-world spam data set for February of 2003 and October of 2003, where samples are visualized in a two-dimensional space by t-distributed stochastic neighbor embedding (t-SNE) [Van der Maaten and Hinton, 2008]. The distribution for October of 2003, where there are many samples around the upper left, is varied from that on February of 2003, which is concentrated around the lower left.

The proposed method learns latest classifiers without additional labeled data that overcomes both problems, i.e., the emergence of new features and the change of distributions, simultaneously. Newly obtained unlabeled data contain information on the correlation between new features, which do not appear in the labeled data but appear in the unlabeled data, and existing features, which appear in the labeled data as well as in the unlabeled data. The proposed method models the conditional distribution of new features given existing features by a multivariate normal distribution, which is learned using the unlabeled data. The newly obtained unlabeled data also contain information on the distribution change. We consider a situation called "covariate shift", where training and test data follow different distributions but the class label distribution given the features is constant since it has been reported that this assumption matches various real-world problems, such as spam filtering [Bickel and Scheffer, 2007], HIV therapy screening [Bickel et al., 2008], and human activity recognition [Hachiya et al., 2012]. Using the labeled and unlabeled data, the proposed method estimates the density ratio between training and test distributions, which models the distribution change.

We approximate the classification error of a classifier, which exploits new features as well as existing features, at the test phase by incorporating both the conditional distribution of new features and the density ratio between training and test distribution. The approximation is calculated by integrating out new feature values by using newly obtained unlabeled data and labeled data collected beforehand without additional labeled data. By minimizing the upper bound of the approximated error, we obtain a classifier that exploits new features and fits on the test phase.

2 RelatedWork

The proposed method utilizes imputation techniques for handling the emergence of new features since it can be integrated with the framework for covariate shift in a principled way. The imputation techniques are typically used for obtaining estimates of missing values. For example, a single imputation method estimates a conditional distribution of missing features given the existing features and replaces missing values by the conditional mean [Donders et al., 2006]. Since single imputation methods treat missing values as fixed data, the uncertainty of the estimated missing values is not considered. Multiple imputation methods take the uncertainty into account and have flourished in the statistics community [Rubin, 2004]. They generate multiple samples from the estimated conditional distribution, and the multiple imputed data are used for learning classifiers. Since many samples would be necessary to represent the uncertainty, the computational cost of multiple imputation methods would be high. In comparison, the proposed method takes the uncertainty into account but is efficient since it does not require multiple samples by analytically integrating out missing values using the conditional distribution. Semi-supervised learning methods that use both labeled and unlabeled data for learning classifiers have been developed [Nigam et al., 2000; Grandvalet and Bengio, 2004; Kingma et al., 2014]. Since semi-supervised methods learn classifiers by assigning pseudo labels to unlabeled data, new features that appear only in the unlabeled data can be exploited to the classifiers. However, the existing imputation and semi-supervised methods does not explicitly consider the emergence of new features over time and does not handle the change of the distribution.

Many methods have been developed for covariate shift. [Zhang et al., 2013] proposed to match data distributions in the Hilbert space by aligning kernel matrices across domains. [Liu and Ziebart, 2014] proposed a minmax approach for learning classifiers. Recently, many works have converged to the direction of using importance weights for covariate shift [Shimodaira, 2000; Kanamori et al., 2009; Sugiyama et al., 2013]. This method learns classifiers by weighting a training sample with its importance, which is defined by a ratio between the data distribution at the training phase and the data distribution at the test phase. Many methods for estimating importance have been proposed, such as moment matching [Huang et al., 2006], density matching under the Kullback-Leibler divergence [Sugiyama et al., 2008], and least-squares importance fitting to the ratio [Kanamori et al., 2009]. All of these methods learn classifiers by using the importance weighted training data. This means that features that appear only in the test data but not in the training data cannot be incorporated into the classifiers. The proposed method is the first attempt to incorporate new features for importance weighting methods in covariate shift adaptation.

Our task is related to transfer learning and concept drift.

Transfer learning utilizes data in a source domain to solve a related problem in a target domain [Pan and Yang, 2010]. In our task, we regard data generated until a certain time point as source domain, and data generated after the time point as the target domain since these data follow different distributions. Although various assumptions for the distribution change have been studied in transfer learning, in this paper, we focus on a situation of covariate shift since it has been reported that it matches various real-world applications [Bickel and Scheffer, 2007; Bickel et al., 2008; Hachiya et al., 2012]. Concept drift is an online supervised scenario, where a data distribution changes over time, and many methods for concept drift have been proposed [Gama et al., 2014; Klinkenberg, 2004; Wang et al., 2003; Haque et al., 2016]. Although these methods for concept drift generally assume that labeled data are sequentially given to update classifiers, the proposed method utilizes unlabeled data to fit on the test distribution, and does not require labeled data to update. Methods for predicting future classifiers given only labeled data collected until the current time have been proposed [Kumagai and Iwata, 2016; 2017]. Although these methods are designed to maintain the classification performance, they do not cope with the problems of the emergence of new features and the distribution change since they do not use any additional training data, which contain rich information for the problems.

3 ProposedMethod

We introduce notations and define the task studied in this paper. Let D:={(xon , yn)}Nn=1 be a set of labeled samples collected until a certain time point, where xon ∈ RDo is the Do-dimensional feature vector of the n-th labeled sample, yn ∈ {0, 1} is its class label, and N is the number of the labeled data. We suppose that the training feature vectors {xon }Nn=1 are drawn from a training distribution p(xo ). D′ :={(xom, xhm)}Mm=1 is a set of unlabeled samples collected after the time point, where (xom, xhm) is the (Do + Dh)- dimensional feature vector of the m-th unlabeled sample, and M is the number of the unlabeled data. The unlabeled data contains new features xhm ∈ RDh , which do not appear in the labeled data D since the unlabeled data are collected after the labeled data are collected. The test feature vectors {(xom, xhm)}Mm=1 are drawn from a test distribution p′ (xo , xh ). Figure 3 summarizes observed and missing values in a given data in our task. We consider a situation of covariate shift where training and test data follow different distributions but the conditional distribution of the class label given the feature vector is constant between training and test phases: p(xo , xh ) ̸= p′ (xo , xh ), p(y|xo , xh ) = p′ (y|xo , xh ). Our goal is to find classifier h : RDo+Dh → {0, 1}, which can accurately classify samples drawn from p′ (xo , xh ), given the labeled and unlabeled data D ∪ D′ .

3.1 Our Framework

We obtain a classifier by minimizing the following generalization error G at the test phase,

where loss(y, y′ ) denotes any loss function that outputs a point-wise error when y is predicted by y′ . The generalization error G is the expectation of the loss function with the test distribution. This generalization error G can be rearranged as

where the assumption, p(y|xo , xh ) = p′ (y|xo , xh ), is used. Since the new features do not appear in the labeled training data, it is impossible to obtain the distribution of the new features from the labeled training data. Thus, we assume that the distribution of the new features given the existing features in the training phase is the same with the distribution in the test phase, p(xh |xo ) = p′ (xh |xo ) which enables us to learn classifiers that exploits new features. Then, the generalization error G is approximated by the following empirical risk,

which is estimated using the labeled training data and the unlabeled test data. Here, τ(xo ) := p′ (xo ) p(xo ) is the importance weight at xo . This weight depends only on the existing features but not on the newly emerged features. The empirical risk at the test phase (3) can be regarded as a importanceweighted average of the empirical risk at the training phase. To minimize the empirical risk (3), we must estimate the conditional distribution p(xhn |xon ) and the importance weight τ(xo ) at first.

3.2 Conditional Distributions of New Features

We estimate the distribution of the new features given the existing features p(xhn |xon ) by assuming it is modeled as the following multivariate normal distribution,

where N(µ,Σ) is a multivariate normal distribution with mean µ and covariance matrix Σ, A is a Dh × Do matrix for defining transformation from existing features xo to new features xh , a ∈ RDh is a bias term, and Λ is a Dh × Dh precision matrix. We assume that the matrix A is lowrank and can be decomposed into a product of two matrixes, A = BC, B ∈ RDh×K , C ∈ RK×Do . We can decrease the number of parameters by setting K < DhDo Dh+Do , which enables us to handle high-dimensional feature vectors. In addition, for simplicity, we restrict the precision matrix Λ to a diagonal matrix as Λ = diag(λ)2+ϵIDh , where λ = (λ1, . . . , λDh ) ∈ RDh is a precision vector, diag(x) returns a diagonal matrix whose diagonal elements are x, ϵ is a positive constant, and Ik is the k×k identity matrix. The term ϵIDh is added in order to ensure the positive definiteness of Λ. We estimate the unknown parameters B, C, a, and λ on the basis of the maximum a posteriori (MAP) estimation by using unlabeled data D′ = {(xom, xhm)}Mm=1 . The conditional density p(xhn |xon ) are estimated by using samples D′ drawn from test distribution p′ (x) but not using samples drawn from training distribution p(x) since p(xh |xo ) = p′ (xh |xo ) and the training data do not contain new features. For the priors of B and C, we assume the normal distributions N(0DhK, r-1 IDhK) and N(0DoK, r-1 IDoK), where 0k denotes the k-dimensional zero vector and r ∈ R+ is a precision parameter. For the prior of the elements of the precision vector λ2k , we assume a Gamma distribution Gam(λ2k |a, b). Then, the log posterior F := log p(B, C, a, λ|D′ ) is given by

where Tr is a trace, ⊤ denotes a transposition, and det is a determinant. The log posterior F is maximized using gradientbased methods over the parameters B, C, a, λ. Although we use a multivariate normal distribution to model p(xhn |xon ) for simplicity, it is possible to use other distributions such as Gaussian mixtures and Bernoulli distributions. In addition, although we modeled the mean of the multivariate normal distribution of xh given xo by linear regression, it is possible to use more powerful non-linear functions such as neural nets.

3.3 ImportanceWeight

We utilize the unconstrained least-square importance fitting approach (uLSIF) [Kanamori et al., 2009] for estimating the importance weight τ(xo ). Since the uLSIF was shown to have excellent numerical stability and efficient run-time solution [Sugiyama et al., 2013], we chose the uLSIF as the importance estimating method. The uLSIF models the importance τ(xo ) by using the following linear model, ˆ τ(xo ) = α⊤ψ(xo ), where α = (α1, . . . , αL) ∈ RL is a parameter vector, L is the number of parameters, and ψ(xo ) ∈ RL are basis functions. Although the original uLSIF implicitly assumes that the importance weight depends on both existing and new features, the uLSIF utilized in the proposed method depends only on the existing features. We use the Gaussian kernel model centered at the existing features of unlabeled data xom as basis functions: ˆ τ(xo ) = ∑Mm=1 αm exp (- ‖xo-xom‖2 2γ 2 ), where ‖ · ‖ is ℓ2-norm and γ 2 denotes the Gaussian width. The parameter vector α is learned so that the following objective function J(α) is minimized,

which is the expected squared error with ℓ2 regularization. With the empirical approximation, this objective function can be rearranged as

where H = 1N ∑n ψ(xon )ψ(xon )⊤ and h = 1M ∑m ψ(xom). This optimization problem is a convex and its minimizer ˆα can be analytically calculated by ˆα =

( 1N ∑n ψ(xon )ψ(xon )⊤ + ρI )-1 ( 1M ∑m ψ(xom)). Since elements of the estimated parameter ˆα can be negative, we modify them with ˜α = max(0L, ˆα), where max is applied in the element-wise manner [Kanamori et al., 2009].

3.4 Learning Classifiers with ImportanceWeights While Integrating out New Features

We employ the negative log likelihood -log p(yn|xon , xhn ) as a loss function in (3) though it is possible to use other loss functions such as the 0/1-loss or hinge-loss. We assume that the conditional probability of class label y given feature vector (xo , xh ) is modeled by logistic regression, p(y = 1|xo , xh ,w) = σ (w⊤(xo , xh )), where w ∈ RDo+Dh is a parameter vector of the classifier h, and σ(·) is the sigmoid function. We would like to minimize the empirical risk (3) with respect to the model parameter w. However, the aforementioned integral is intractable because of the nonconjugacy of p(y|xo , xh ,w). To deal with this problem, we use the following inequality [Bishop, 2006],

where sn := w⊤(xon , xhn ), ξn ∈ R is a parameter that is associated with each labeled training sample and controls the accuracy of the approximation, and g(ξn) = 1 2ξn (σ(ξn) - 12 ). By substituting the term on the right side of (8) with the negative log likelihood in the empirical risk (3), we obtain the new objective function ˜G. Since ˜G is the upper bound of the original objective function G, decreasing the value of ˜G leads to an decreased value of G. Using the first and second moments of the normal distributions, ∫ xhnp(xhn |xon )dxhn = BCxon + a (=: µ(xon )), ∫ xhnxh⊤ n p(xhn |xon )dxhn = µ(xon )µ(xon )⊤ + Λ-1 , we write the objective function ˜G with ℓ2- regularizer to be minimized as follows,

where w = (wo, wh) ∈ RDo+Dh and c is a positive constant. The objective function ˜G is minimized using gradient-based methods over the parameters w = (wo,wh), {ξn}Nn=1 .

4 Experiments

We conducted experiments using one synthetic and three realworld data sets to confirm the effectiveness of the proposed method.

4.1 Synthetic Data

Each training sample xon ∈ R is drawn from π1N(-3, 1) + π2N(6, 1) if yn = 1 and N(0, 1) if yn = 0, where πi ∈ R+ are mixture ratios satisfying π1 + π2 = 1. Each test sample xm = (xom, xhm) ∈ R2 is drawn from N ((-3, 6), I2) if ym = 1 and N ((0, 2), I2) if ym = 0, where new feature xhm is added in the test distribution. We illustrate this data in Figure 4. In the experiments, we generate 100 labeled training samples for each label y and 100 test samples for each label y.

4.2 Real-world Data

We used three real-world data sets: SPAM, URL, and LOG. SPAM is a collection of spam and legitimate email received by one from February 1st of 2003 to January 31th of 2004 [Gama et al., 2014]. This data set is the same as that stated in Figure 1 and 2. The total number of emails is 11, 905, and the number of features is 166, 047. URL is a public data set of malicious and normal urls collected over 120 days [Ma et al., 2009]. The total number of examples is 2, 396, 130, and the number of features 3,231,961. These two data sets are well-used in concept drift literatures. LOG is our in-house data collection of malicious and normal WebProxy logs. Malicious WebProxy logs were created on the basis of malware communications. Since malware evolve over time, the malware communications also change over time. Each log includes information such as source IP address, destination IP address and url.

4.3 Setting

In our experiments using the synthetic data set, we evaluated AUC, which is a well-used evaluation measure for classification tasks, varying the values of the mixture ratio (π1, π2). We created ten different sets and evaluated the average AUC for each mixture ratio (π1, π2). In our experiments using the real-world data sets, we calculated AUC by using samples collected until a certain time point for labeled training data and samples after the certain time point for unlabeled training and test data for evaluating the classification performance on latest data. For SPAM, roughly, samples collected in the n-th month were used for labeled data, samples in the n+1-th month for unlabeled data, and samples in the n + 2-th month for test data, where n is 2, 3, · · · , 11. Therefore, we obtained ten different sets in total, and we evaluated the average AUC over the these sets. For URL, we first split 120 days, making a split every 10 days, and samples collected in the n-th unit were used for labeled data, samples in the n + 1-th unit for unlabeled data, and samples in the n + 2-th unit for test data, where n is 1, 2, · · · , 10. For LOG, samples collected in a day were used for labeled data, and samples collected over two days after the day, which labeled data were collected in, were used for unlabeled or test data.

We compared the proposed method with four existing methods: logistic regression (LR), imputation logistic regression (ILR), importance weighted logistic regression (IWLR) and semi-supervised logistic regression by minimum entropy regularization (MER). LR learns classifiers by using only labeled data D:={(xon , yn)}Nn=1 . ILR learns classifiers by logistic regression after completing labeled data xon with the conditional mean in (4). IWLR learns classifiers by logistic regression with the importance weighted method (specifically, by uLSIF [Kanamori et al., 2009]). MER is a semisupervised extension of logistic regression [Grandvalet and Bengio, 2004]. MER learns classifiers so as to separate unlabeled data as much as possible on the basis of minimum entropy regularization. To evaluate the effectiveness of considering new features and importance weights, we used logistic regression for classifiers with all methods including the proposed method.

In our experiments, we chose the optimal hyper parameters for these methods from the following variations by using validation data: regularization parameter for classifiers c ∈ {10-1 , 1, 101 } in all methods, regularization parameter for importance ρ ∈ {10-1 , 1, 101 } in the proposed method and IWLR, regularization parameter for imputation r, b ∈ {10-1 , 1, 101 }, a ∈ {1}, and imputation parameter K ∈ {1, 3, 6, 9} in the proposed method and ILR. For the proposed method and IWLR, the Gaussian width of the Gaussian Kernel γ is determined by median trick, that is, γ is set by the median of squared distance between training points (labeled and unlabeled data). The weighting parameter of unlabeled data for MER is chosen in {{0.1 · 10-n , 0.5 · 10-n }3n=0 , 1}, The correction term ϵ is set by 10-4 for the proposed method and ILR.

4.4 Results

We first show the classification performance in the synthetic data sets. Figure 5 shows the average and standard error of AUC, varying the values of the mixture ratio (π1, π2). When π2 was 0.25, there was not much difference between each method. This is because the number of training samples with y = 1 located on the left side was much larger than training samples with y = 1 located on the right side, and therefore, the optimal decision boundary, whose normal vector points to the left direction, can be easily learned in every method. When π2 was 0.4 and 0.55, the AUCs of the methods except the proposed method and IWLR became poor since they were affected by a lot of training samples with y = 1 located on the right side. However, the proposed method and IWLR could learn a good decision boundary since the importance weights of training samples located on the left side are bigger than those located on the right side. When π2 was 0.7 and 0.85, only the proposed method achieved a high AUC, although IWLR became inaccurate. This is because the importance weights estimated by the proposed method only depend on existing features xo , although the importance weights with IWLR depend on existing and new features (xo , xh ) , and therefore, IWLR tends to give large importance weights to training samples with y = 1 on the right side. Overall, the proposed method achieved a good classification performance compared with the others in the situation, where there were new features and training and test distributions differ.

Next, we investigate the classification performance when varying the number of labeled samples for the real-world data sets. Here we set the number of unlabeled and test samples uniformly so that it did not exceed the smallest number of samples in each time unit (here, the time unit is a month in the case of SPAM, ten days in the case of URL, and a day in the case of LOG). As a result, the number of unlabeled samples for SPAM, URL and LOG were 500, 1000 and 600, respectively. The number of test samples was also the same number of unlabeled samples. Table 2 shows the number of existing features Do and new features Dh in the case of N/M = 1.0, where N is the number of labeled samples and M is the number of fixed unlabeled samples, for each realworld data set. Table 1 shows the average and standard error of AUC over N/M = {0.25, 0.5, 1.0}. For all data sets, the proposed method achieved the highest average of AUC over all N/M. In addition, the proposed method outperformed the other methods in many N/M (the proposed method showed the best results 6 out of 9 times). Although ILR and IWLR somewhat improved the average of AUC over all N/M compared with LR, the proposed method improved AUC further. This result suggests that it is better to learn classifiers taking into account two problems, that is, the emergence of new features and the distribution change, at the same time more than when they are considered separately.

Last, we investigated how the classification performance of the proposed method changed against imputation parameter K, which determines the number of parameters to be estimated for the conditional probability with new features given existing features. The number of labeled and unlabeled samples was same as in the earlier experiments. Figure 6 represents the averages of AUC over N/M = {0.25, 0.5, 1.0} when changing the value of imputation parameter K within {1, 3, 6, 9}. Here, the AUCs of LR, IWLR, and MER were constant when varying the value of K since they do not depend on the value of K. Overall, the proposed method achieved a good classification performance for all the values of imputation parameter K. For SPAM and URL, the AUC of the proposed method was better than the other methods for all imputation parameters K. For LOG, the proposed method outperformed the others except in the case of K = 1. Nevertheless, even with K = 1, the proposed method achieved a relatively good classification performance. One of the reasons the proposed method with K = 1 achieved a good classification performance is that only a small part of the new features affected the classification performance. That is, there is a possibility that only a small K is enough to improve the classification performance even though it is not sufficient to represent a correlation of new and existing features perfectly. As a result, we assume that the proposed method requires only a small K to classify data correctly.

5 Conclusion

We proposed a novel method for learning the latest classifiers by using labeled data collected beforehand and newly obtained unlabeled data. In experiments, we confirmed that the proposed method outperformed the various existing methods in the situation , where there were new features and training and test distributions differ. As future work, we will extend the proposed method to on-line learning in order to be able to apply it to large-scale data. In addition, applying deep learning methods for modeling conditional distribution of new features is also interesting.