# Training Classifiers under Covariate Shift by Constructing the Maximum Consistent Distribution Subset

Authors: Xu Yu; Miao Yu; Li-xun Xu; Jing Yang; Zhi-qiang Xie
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

The assumption that the training and testing samples are drawn from the same distribution is violated under covariate shift setting, and most algorithms for the covariate shift setting try to first estimate distributions and then reweight samples based on the distributions estimated. Due to the difficulty of estimating a correct distribution, previous methods can not get good classification performance. In this paper, we firstly present two types of covariate shift problems. Rather than estimating the distributions, we then desire an effective method to select a maximum subset following the target testing distribution based on feature space split from the auxiliary set or the target training set. Finally, we prove that our subset selection method can consistently deal with both scenarios of covariate shift. Experimental results demonstrate that training a classifier with the selected maximum subset exhibits good generalization ability and running efficiency over those of traditional methods under covariate shift setting.


---

## Body

## 1. Introduction

Traditional classification methods, such as Support Vector Machines (SVMs) [1, 2], decision tree [3, 4], and neural networks [5, 6], are always based on the assumption that the training and testing samples are drawn from the same distribution. In many classification scenarios, such as the class imbalance problem [7, 8], concept drift [9, 10], and covariate shift [11], however, this assumption is violated. An informal description on covariate shift is as follows. Covariate shift refers to the learning settings in which source data sets and target data sets have the same feature attributes, label attribute, and the conditional probabilities of y∣x but have different feature distributions. In this paper, we mainly study classifying under covariate shift. Below, we give two types of classification scenarios belonging to covariate shift. They are what we focus on in this paper.Scenario 1.
Classification problems contain training samples, testing samples, and auxiliary samples, where training samples and testing samples are drawn from the same distribution, while the auxiliary samples are drawn from another distribution. In addition, the training set size is very small.
In real world, lots of classification problems belong to Scenario1. For example, suppose we want to construct a Web page classification model. The Web data used in training a Web page classification model can be easily outdated when applied to the Web sometime later, because the topics on the web change frequently. Often, new data are expensive to label and thus their quantities are limited due to cost issues. How to accurately classify the new test data by making the maximum use of the old data becomes a critical problem.Scenario 2.
Classification problems contain training samples and testing samples, where training samples and testing samples are drawn from different distributions. There are no auxiliary samples.
For example, suppose we are using a learning method to induce a model that predicts the side effects of a treatment for a given patient. Because the treatment is not given randomly to individuals in the general population, the available training samples are not a random sample from the population. Therefore, the training samples and testing samples are drawn from different distributions. How to accurately classify the testing data by employing the training data becomes a critical problem.In this paper, we address the two types of covariate shift problems by training on a newly constructed set following approximately the target distribution. The rest of this paper is organized as follows. In Section2, we formally define covariate shift in machine learning terms and describe the related works on this problem. In Section 3, we propose the MIDS construction method by matching sample numbers between target set and auxiliary set in each feature subspace. In Section 4, we present the corresponding data correction methods with respect to the two scenarios, propose the corresponding classification algorithms, and analyze the time complexity of the algorithms. Our experimental results and discussion are shown in Section 5. Section 6 summaries the main contribution of this paper and gives some future works.


## 2. Related Concepts and Works

### 2.1. Related Concepts

In this section, we introduce some notations and definitions that are used in this paper. First of all, we give the definitions of a “domain” and a “task,” respectively.Definition 1 (domain).
In this paper, a domainD consists of two components: a feature space X and a marginal probability distribution P(X), where X=x1,…,xn∈X.Definition 2 (task).
Given a specific domain—D={X,P(X)}—a task consists of two components: a label space Y and an objective predictive function f(·) (denoted by T={Y,f(·)}), which is not observed but can be learned from the training data, which consist of pairs {xi,yi}, where xi∈X and yi∈Y. The function f(·) can be used to predict the corresponding label, f(x), of a new instance x. From a probabilistic viewpoint, f(x) can be written as P(y∣x).In this section, we denote the source domain data byDS=xS1,yS1,…,xSnS,ySnS, where xSi∈XS is the data instance and ySi∈YS is the corresponding class label. Similarly, we denote the target domain data by DT={(xT1,yT1),…,(xTnT,yTnT)}, where the input xTi is in XT and yTi∈YT is the corresponding output. In most cases, 0≤nT≪nS.We now give a formal definition of covariate shift.Definition 3 (covariate shift).
Covariate shift refers to the learning settings that have the following features: (1) source domain and target domain have the same feature and label spaces; that is,XS=XT and YS=YT. (2) Source domain and target domain have different feature distribution; that is, PS(X)≠PT(X). (3) Source domain and target domain have the same concept; that is, fS(·)=fT(·) or PSY∣X=PTY∣X.It is worthwhile to note that there can be multiple auxiliary data sets in classification problems under covariate shift and their feature distributions can be different. In addition, from the definition of covariate shift, we can see that the two scenarios described in Section1 do belong to covariate shift, because, for Scenario 2, testing samples can be considered as target samples and training samples can be considered as auxiliary samples.


### 2.2. Related Works

As described before, covariate shift includes the two scenarios described above. With respect to Scenario1, auxiliary samples are utilized to improve the performance of classifiers. In previous works, Wu and Dietterich [12] proposed an image classification algorithm using both inadequate training data and plenty of low quality auxiliary data. They demonstrated some improvement by using the auxiliary data. However, they did not give a quantitative study using different auxiliary examples. Liao et al. [13] improved learning with auxiliary data using active learning. Rosenstein et al. [14] proposed a hierarchical naive Bayes approach for transfer learning using auxiliary data and discussed when transfer learning would improve or decrease the performance. Dai et al. [15] proposed a covariate shift-related algorithm, TrAdaBoost, which is an extension of the AdaBoost algorithm, to address the inductive transfer learning problems. TrAdaBoost assumes that the source and target domain data use exactly the same set of features and labels, but the distributions of the data in the two domains are different. In addition, TrAdaBoost assumes that, due to the difference in distributions between the source and the target domains, some of the source domain data may be useful in learning for the target domain but some of them may not and could even be harmful. It attempts to iteratively reweight the source domain data to reduce the effect of the “bad” source data while encouraging the “good” source data to contribute more to the target domain. For each round of iteration, TrAdaBoost trains the base classifier on the weighted source and target data. The error is only calculated on the target data. Furthermore, TrAdaBoost uses the same strategy as AdaBoost [16] to update the incorrectly classified examples in the target domain while using a different strategy from AdaBoost to update the incorrectly classified source examples in the source domain. However, TrAdaBoost can not deal with the case where there are multiple auxiliary data sets coming from different distributions.With respect to Scenario2, unlabeled testing samples are utilized to improve the performance of classifiers. Unlike semisupervising learning problem [17], for Scenario 2, the unlabeled testing samples are under a different distribution from the training samples and are used to correct the sample selection bias. In previous works, most approaches intend to estimate the importance P(xSi)/P(xTi). If we can estimate the importance for each instance, we can solve the learning problems under covariate shift. There exist various ways to estimate P(xSi)/P(xTi).Zadrozny [18] proposed to estimate the terms P(xSi) and P(xTi) independently by constructing simple classification problems and then estimate the importance by taking the ratio of the estimated densities. However, estimating densities is known to be a hard problem particularly in high-dimensional cases. Therefore, this approach may not be effective.Huang et al. [19] proposed a kernel-mean matching (KMM) algorithm to learn P(xSi)/P(xTi) directly by matching the means between the source domain data and the target domain data in a reproducing kernel Hilbert space (RKHS). KMM is shown to work well if tuning parameters such as the kernel width are chosen appropriately. Thus, the importance estimation problem is now relocated to the model selection problem. Standard model selection methods such as cross-validation, however, are heavily biased under covariate shift. Therefore, KMM can not be directly applied in the cross-validation [20] framework.Unlike KMM, Sugiyama et al. [21] proposed an algorithm known as Kullback-Leibler importance estimation procedure (KLIEP), which is equipped with a natural model selection procedure. KLIEP can be integrated with cross-validation to perform model selection automatically in two steps: (1) estimating the weights of the source domain data; (2) training models on the reweighted data.In this paper, we propose a novel method by constructing a MIDS to deal with classification problems under covariate shift. The formal definition of MIDS and its construction method will be given in the next section. Unlike previous transfer learning methods, our method can consistently deal with both scenarios and the cases where there are multiple auxiliary data sets coming from different distributions. Furthermore, unlike the above sample reweighting techniques, we do not estimate distributions but match sample numbers between target set and auxiliary set in each feature subspace; we do not reweight samples but construct a new training set following approximately the target distribution.


## 2.1. Related Concepts

In this section, we introduce some notations and definitions that are used in this paper. First of all, we give the definitions of a “domain” and a “task,” respectively.Definition 1 (domain).
In this paper, a domainD consists of two components: a feature space X and a marginal probability distribution P(X), where X=x1,…,xn∈X.Definition 2 (task).
Given a specific domain—D={X,P(X)}—a task consists of two components: a label space Y and an objective predictive function f(·) (denoted by T={Y,f(·)}), which is not observed but can be learned from the training data, which consist of pairs {xi,yi}, where xi∈X and yi∈Y. The function f(·) can be used to predict the corresponding label, f(x), of a new instance x. From a probabilistic viewpoint, f(x) can be written as P(y∣x).In this section, we denote the source domain data byDS=xS1,yS1,…,xSnS,ySnS, where xSi∈XS is the data instance and ySi∈YS is the corresponding class label. Similarly, we denote the target domain data by DT={(xT1,yT1),…,(xTnT,yTnT)}, where the input xTi is in XT and yTi∈YT is the corresponding output. In most cases, 0≤nT≪nS.We now give a formal definition of covariate shift.Definition 3 (covariate shift).
Covariate shift refers to the learning settings that have the following features: (1) source domain and target domain have the same feature and label spaces; that is,XS=XT and YS=YT. (2) Source domain and target domain have different feature distribution; that is, PS(X)≠PT(X). (3) Source domain and target domain have the same concept; that is, fS(·)=fT(·) or PSY∣X=PTY∣X.It is worthwhile to note that there can be multiple auxiliary data sets in classification problems under covariate shift and their feature distributions can be different. In addition, from the definition of covariate shift, we can see that the two scenarios described in Section1 do belong to covariate shift, because, for Scenario 2, testing samples can be considered as target samples and training samples can be considered as auxiliary samples.


## 2.2. Related Works

As described before, covariate shift includes the two scenarios described above. With respect to Scenario1, auxiliary samples are utilized to improve the performance of classifiers. In previous works, Wu and Dietterich [12] proposed an image classification algorithm using both inadequate training data and plenty of low quality auxiliary data. They demonstrated some improvement by using the auxiliary data. However, they did not give a quantitative study using different auxiliary examples. Liao et al. [13] improved learning with auxiliary data using active learning. Rosenstein et al. [14] proposed a hierarchical naive Bayes approach for transfer learning using auxiliary data and discussed when transfer learning would improve or decrease the performance. Dai et al. [15] proposed a covariate shift-related algorithm, TrAdaBoost, which is an extension of the AdaBoost algorithm, to address the inductive transfer learning problems. TrAdaBoost assumes that the source and target domain data use exactly the same set of features and labels, but the distributions of the data in the two domains are different. In addition, TrAdaBoost assumes that, due to the difference in distributions between the source and the target domains, some of the source domain data may be useful in learning for the target domain but some of them may not and could even be harmful. It attempts to iteratively reweight the source domain data to reduce the effect of the “bad” source data while encouraging the “good” source data to contribute more to the target domain. For each round of iteration, TrAdaBoost trains the base classifier on the weighted source and target data. The error is only calculated on the target data. Furthermore, TrAdaBoost uses the same strategy as AdaBoost [16] to update the incorrectly classified examples in the target domain while using a different strategy from AdaBoost to update the incorrectly classified source examples in the source domain. However, TrAdaBoost can not deal with the case where there are multiple auxiliary data sets coming from different distributions.With respect to Scenario2, unlabeled testing samples are utilized to improve the performance of classifiers. Unlike semisupervising learning problem [17], for Scenario 2, the unlabeled testing samples are under a different distribution from the training samples and are used to correct the sample selection bias. In previous works, most approaches intend to estimate the importance P(xSi)/P(xTi). If we can estimate the importance for each instance, we can solve the learning problems under covariate shift. There exist various ways to estimate P(xSi)/P(xTi).Zadrozny [18] proposed to estimate the terms P(xSi) and P(xTi) independently by constructing simple classification problems and then estimate the importance by taking the ratio of the estimated densities. However, estimating densities is known to be a hard problem particularly in high-dimensional cases. Therefore, this approach may not be effective.Huang et al. [19] proposed a kernel-mean matching (KMM) algorithm to learn P(xSi)/P(xTi) directly by matching the means between the source domain data and the target domain data in a reproducing kernel Hilbert space (RKHS). KMM is shown to work well if tuning parameters such as the kernel width are chosen appropriately. Thus, the importance estimation problem is now relocated to the model selection problem. Standard model selection methods such as cross-validation, however, are heavily biased under covariate shift. Therefore, KMM can not be directly applied in the cross-validation [20] framework.Unlike KMM, Sugiyama et al. [21] proposed an algorithm known as Kullback-Leibler importance estimation procedure (KLIEP), which is equipped with a natural model selection procedure. KLIEP can be integrated with cross-validation to perform model selection automatically in two steps: (1) estimating the weights of the source domain data; (2) training models on the reweighted data.In this paper, we propose a novel method by constructing a MIDS to deal with classification problems under covariate shift. The formal definition of MIDS and its construction method will be given in the next section. Unlike previous transfer learning methods, our method can consistently deal with both scenarios and the cases where there are multiple auxiliary data sets coming from different distributions. Furthermore, unlike the above sample reweighting techniques, we do not estimate distributions but match sample numbers between target set and auxiliary set in each feature subspace; we do not reweight samples but construct a new training set following approximately the target distribution.


## 3. The MIDS Construction Method

In this section, we use two data sets, target set and auxiliary set. Our objective is to design a method that can construct MIDS from auxiliary samples according to target distribution. First of all, we give the formal definitions of identical distribution subset (IDS) and MIDS.Definition 4 (identical distribution subset, IDS).
LetT={t1,t2,…,tn} be a target sample set and S=s1,s2,…,sm a source sample set. Assuming that they follow different distributions and have the same feature and label space—that is, PSX,Y≠PTX,Y—XS=XT and YS=YT. Identical distribution subset is a subset of S and follows the same distribution with T.Definition 5 (maximum identical distribution subset, MIDS).
A proper identical distribution subsetI is called a maximal identical distribution subset if there exists no other proper identical distribution subset J with a bigger size than that of I.


### 3.1. Basic Idea of MIDS Construction Method

Our basic idea of MIDS construction is first to partition the feature space into several subspaces and then construct MIDS by matching sample numbers between target set and auxiliary set in each feature subspace; that is, select a maximum amount of auxiliary samples from each subspace to compose the MIDS according to the proportion of target samples in each subspace. The detailed process of the MIDS construction method will be presented in Section3.2.


### 3.2. The Detailed MIDS Construction Process

LetXT=x1,x2,…,xk be the n-dimensional target set drawn from the distribution PT(x) and XS=x1′,x2′,…,xm′ the n-dimensional source set drawn from the distribution PS(x).(1) Partitioning the Feature Space into Several Subspaces. Firstly, compute the mean of the target set by the following formula:(1)x0=∑1kxik.Then, partition then-dimensional space into 2n subspaces. In detail, let x=(x1,…,xi,…,xn) be any vector in the feature space, where xi denotes the ith-dimensional value of the vector x. Compare the ith-dimensional value of the vector x with the ith-dimensional value of x0, and we can obtain n inequalities. We use an n-dimensional binary vector to represent these inequalities; that is to say, if xi≤x0i, we label the ith-dimensional value of the binary vector with 0, otherwise 1. Thus we can divide the feature space into 2n subspaces, corresponding to 2n binary vectors from (0,0,…,0) to (1,1,…,1), respectively. We number the subspace with the decimal numbers corresponding to the binary vectors.(2) Computing the Proportion of the Target Samples in Each Subspace. Compute the number of the target samples in each subspace, and so we can obtain the proportion of samples in each subspace.(3) Extracting Samples from the Auxiliary Set. We first compute the numbers of auxiliary samples in each subspace. Then, according to the proportion and the numbers, we select a maximum amount of samples from each subspace to compose the MIDS, noting that the proportion of the auxiliary samples selected from each subspace should be consistent with the proportion of the target samples in each subspace.Thus we obtain the MIDS, and this subset can be considered to follow approximately the target distribution.


### 3.3. The Description of the MIDS Construction Algorithm and Its Time Complexity Analysis

The pseudocode of the MIDS construction algorithm is described in Algorithm1. Firstly, we define two 2-dimensional arrays, A and B. The first dimension of Array A records the subspace number of samples in the target sample set. It is worth noting that Array A only has one record for samples with the same subspace number. The second dimension of Array A records the number of samples in the corresponding subspace. Array B is the same as Array A, but for the source sample set.Algorithm 1:The MIDS construction algorithm.
Require: the source sample set RS, the target sample set RT, dimension n,
size of the source sample setkS, size of the target sample set kT
Ensure: the MIDS R
x0=∑1kTxikT;
Clarifying two 2-dimensional Arrays,A and B;
/∗The first dimension of Array A records the subspace
number of samples in the target sample set. Note that
ArrayA only has one record for samples with the same
subspace number. The second dimension of ArrayA
records the number of samples in the corresponding subspace.
ArrayB is the same as A, but for the source sample set∗/
A=Array_generation(RT,x0)  /∗obtain Array A from RT and x0∗/
B=Array_generation(RS,x0)  /∗obtain Array B from RS and x0∗/
R=construct(a,b)   /∗select a maximum amount of samples from
each subspace to compose the MIDSR according
to ArrayA and Array B∗/Then we obtain ArrayA from RT and x0. We compute the subspace number of samples by real number comparison operation. To obtain the number of samples in the corresponding subspace, we need to scan the whole data set RT. It is the same with array B.Finally, we select a maximum amount of samples from each subspace to compose the MIDSR according to Array A and Array B.We split the whole space into2n subspaces, and for large n the number of subspaces is enormous, which would cause the curse of dimensionality if we compute the number of samples in each subspace. Luckily it is not necessary to do that, as the samples are always sparse in a high-dimensional space. Thus we only need to compute the number of samples in subspaces which consist of samples.Therefore the time complexity is mainly composed of two parts, corresponding to calculating the proportion of the target samples in certain subspaces and calculating the numbers of the source samples in certain subspaces, respectively. It is worth noting that we only need to compute the number of samples in subspaces which consist of samples.Thus if we define one-time real number comparison operation as one-time basic operation, we need to don(kT+kS) times operations, where kS denotes the size of the source sample set and kT denotes the size of the target sample set.


## 3.1. Basic Idea of MIDS Construction Method

Our basic idea of MIDS construction is first to partition the feature space into several subspaces and then construct MIDS by matching sample numbers between target set and auxiliary set in each feature subspace; that is, select a maximum amount of auxiliary samples from each subspace to compose the MIDS according to the proportion of target samples in each subspace. The detailed process of the MIDS construction method will be presented in Section3.2.


## 3.2. The Detailed MIDS Construction Process

LetXT=x1,x2,…,xk be the n-dimensional target set drawn from the distribution PT(x) and XS=x1′,x2′,…,xm′ the n-dimensional source set drawn from the distribution PS(x).(1) Partitioning the Feature Space into Several Subspaces. Firstly, compute the mean of the target set by the following formula:(1)x0=∑1kxik.Then, partition then-dimensional space into 2n subspaces. In detail, let x=(x1,…,xi,…,xn) be any vector in the feature space, where xi denotes the ith-dimensional value of the vector x. Compare the ith-dimensional value of the vector x with the ith-dimensional value of x0, and we can obtain n inequalities. We use an n-dimensional binary vector to represent these inequalities; that is to say, if xi≤x0i, we label the ith-dimensional value of the binary vector with 0, otherwise 1. Thus we can divide the feature space into 2n subspaces, corresponding to 2n binary vectors from (0,0,…,0) to (1,1,…,1), respectively. We number the subspace with the decimal numbers corresponding to the binary vectors.(2) Computing the Proportion of the Target Samples in Each Subspace. Compute the number of the target samples in each subspace, and so we can obtain the proportion of samples in each subspace.(3) Extracting Samples from the Auxiliary Set. We first compute the numbers of auxiliary samples in each subspace. Then, according to the proportion and the numbers, we select a maximum amount of samples from each subspace to compose the MIDS, noting that the proportion of the auxiliary samples selected from each subspace should be consistent with the proportion of the target samples in each subspace.Thus we obtain the MIDS, and this subset can be considered to follow approximately the target distribution.


## 3.3. The Description of the MIDS Construction Algorithm and Its Time Complexity Analysis

The pseudocode of the MIDS construction algorithm is described in Algorithm1. Firstly, we define two 2-dimensional arrays, A and B. The first dimension of Array A records the subspace number of samples in the target sample set. It is worth noting that Array A only has one record for samples with the same subspace number. The second dimension of Array A records the number of samples in the corresponding subspace. Array B is the same as Array A, but for the source sample set.Algorithm 1:The MIDS construction algorithm.
Require: the source sample set RS, the target sample set RT, dimension n,
size of the source sample setkS, size of the target sample set kT
Ensure: the MIDS R
x0=∑1kTxikT;
Clarifying two 2-dimensional Arrays,A and B;
/∗The first dimension of Array A records the subspace
number of samples in the target sample set. Note that
ArrayA only has one record for samples with the same
subspace number. The second dimension of ArrayA
records the number of samples in the corresponding subspace.
ArrayB is the same as A, but for the source sample set∗/
A=Array_generation(RT,x0)  /∗obtain Array A from RT and x0∗/
B=Array_generation(RS,x0)  /∗obtain Array B from RS and x0∗/
R=construct(a,b)   /∗select a maximum amount of samples from
each subspace to compose the MIDSR according
to ArrayA and Array B∗/Then we obtain ArrayA from RT and x0. We compute the subspace number of samples by real number comparison operation. To obtain the number of samples in the corresponding subspace, we need to scan the whole data set RT. It is the same with array B.Finally, we select a maximum amount of samples from each subspace to compose the MIDSR according to Array A and Array B.We split the whole space into2n subspaces, and for large n the number of subspaces is enormous, which would cause the curse of dimensionality if we compute the number of samples in each subspace. Luckily it is not necessary to do that, as the samples are always sparse in a high-dimensional space. Thus we only need to compute the number of samples in subspaces which consist of samples.Therefore the time complexity is mainly composed of two parts, corresponding to calculating the proportion of the target samples in certain subspaces and calculating the numbers of the source samples in certain subspaces, respectively. It is worth noting that we only need to compute the number of samples in subspaces which consist of samples.Thus if we define one-time real number comparison operation as one-time basic operation, we need to don(kT+kS) times operations, where kS denotes the size of the source sample set and kT denotes the size of the target sample set.


## 4. Classification Methods under Covariate Shift by Constructing the MIDS

In Section3, we present a general MIDS construction method by matching sample numbers between target set and auxiliary set in each feature subspace. In this section, we will propose the special MIDS construction methods corresponding to Scenarios 1 and 2, respectively. Furthermore, we will propose the classification methods for the two scenarios.


### 4.1. The MIDS Construction of Scenario1

LetTtr=xitr,yitr∣i=1,2,…,m be the target training set, Tte=xjte,yjte∣j=1,2,…,n the target testing set, and Tau={xkau,ykau∣k=1,2,…,p} the auxiliary training set. Assume that Ttr and Tte follow the same distribution Pt(x,y) and Tau follow another distribution Ps(x,y). In this section, we will present two kinds of MIDS construction methods, where one is direct and the other is indirect. Moreover, we will prove that the effect of the indirect method is equivalent to that of the direct method.


#### 4.1.1. The Direct MIDS Construction Method of Scenario1

With respect to the direct MIDS construction, we consider feature vectorx and label y as a joint vector. We consider Tt=Ttr∪Tte and Tau as the target sample set and the source sample set, respectively. Thus we can use the above algorithm directly to obtain the MIDS. The MIDS construction method by considering feature vector x and label y as a joint vector is called the direct MIDS construction method.Since feature vectorx and label y are considered to be one joint vector, the dimension of samples will be increased. As described in Section 3.3, with the increase of the dimension, the running time of the MIDS algorithm will increase correspondingly. In the next section, we will present the indirect MIDS construction method, for which it is not necessary to consider x and y collectively and the MIDS is constructed according to feature vector x alone. Thus the indirect method can reduce effectively the running time and moreover it can be applied to the case where the target testing set contains only feature vectors.


#### 4.1.2. The Indirect MIDS Construction Method of Scenario1

With respect to the case where there are no class labels in the target testing set, we can construct the MIDS according to feature vectorx alone. The MIDS construction method by considering only feature vector x is called the indirect MIDS construction method. Now let Tte=xjte∣j=1,2,…,n be target testing set. First of all, we present the detailed process of the indirect MIDS construction method.Process  1. Remove all the labels of samples in Tt, and label the set composed by the remaining feature vectors as Ttx. Similarly, remove all the labels of samples in Tau, and label the set composed by the remaining feature vectors as Taux.Process  2. Use the MIDS construction algorithm to obtain a subset taux of Taux.Process  3. Add the class labels removed in Process 1 to each sample of taux correspondingly, and thus we obtain a subset tau of Tau.Below we will prove that the effect of the indirect method is equivalent to that of the direct method.Theorem 6.
The subsettau obtained from the auxiliary set Tau by the indirect MIDS method follows the same distribution with the target set Tt; that is, PS′(x,y)=PT(x,y), where PS′(X,Y) and PT(x,y) denote the distributions of tau and Tt, respectively.Proof.
LetPS′(x) and PT(x) denote the distributions of taux and Ttx, respectively. From the definition of conditional distribution, we have(2)PTx,y=PTy∣xPTx,PS′x,y=PS′y∣xPS′x.As described in Process  3, tau is obtained by adding the original class labels to taux correspondingly. Thus the conditional probability is unchanged; that is, PS′y∣x=PSy∣x. From Definition 3, we know that PT(y∣x)=PS(y∣x). Thus we can obtain that PS′y∣x=PTy∣x. Moreover since taux is a MIDS of Ttx, we can obtain that PS′x=PT(x). Therefore we have PS′x,y=PTx,y.


### 4.2. The MIDS Construction of Scenario2

LetTtr=(xitr,yitr)∣i=1,2,…,m be target training set and Tte=(xjte,yjte)∣j=1,2,…,n target testing set. Assume that Ttr and Tte follow distributions Ptr(x,y) and Pte(x,y), respectively. We consider Tte and Ttr as the target sample set and the source sample set, respectively. Thus we also can use the above algorithm directly to obtain the MIDS.With respect to the case where there are no class labels in the target testing set, we can also use indirect method to construct the MIDS. Now letTte={xjte∣j=1,2,…,n} be target testing set. The detailed process is as follows.Process 1. Remove all the labels of samples in Ttr, and label the set composed by the remaining feature vectors as Ttrx.Process 2. Use the MIDS construction algorithm to obtain a subset ttrx of Ttrx.Process 3. Add the class labels removed in Process 1 to each sample of ttrx correspondingly, and thus we obtain a subset ttr of Ttr.


### 4.3. Classification Algorithms

With the help of the MIDS construction method, we can make effective classification by traditional classification method. With respect to Scenario1, we first construct the MIDS from the auxiliary set and then train a model on the set composed by the target training set and the MIDS. The pseudocodes of the two classification algorithms corresponding to the direct and indirect MIDS construction methods are shown in Algorithms 2 and 3, respectively. With respect to Scenario 2, we first construct the MIDS from the target training set and then train a model on this MIDS. The pseudocodes of the two classification algorithms corresponding to the direct and indirect MIDS construction methods are shown in Algorithms 4 and 5, respectively.Algorithm 2:The direct classification algorithm of Scenario 1.
Require: the target training set Ttr={(xitr,yitr)∣i=1,2,…,m}, the target testing set Tte={(xjte,yjte)∣j=1,2,…,n},
the auxiliary sample setTau={(xkau,ykau)∣k=1,2,…,p}, a base learning algorithm Learner
Ensure: classification function f(⋅)
Tt=Ttr∪Tte;        /∗Tt denotes the target sample set∗/
tau=MIDS_Construction(Tt,Tau);     /∗constructing the MIDS∗/
T1=tau∪Ttr;     /∗T1 denotes the new training set∗/
f(⋅)=Learner(T1);    /∗f denotes the function implemented by a base
learning algorithm trained on the new training setT1∗/Algorithm 3:The indirect classification algorithm of Scenario 1.
Require: the target training set Ttr={(xitr,yitr)∣i=1,2,…,m}, the target testing set Tte={xjte∣j=1,2,…,n},
the auxiliary sample setTau={(xkau,ykau)∣k=1,2,…,p}, a base learning algorithm Learner
Ensure: classification function f(⋅)
Ttrx=select_x(Ttr);     /∗Ttrx denote the feature vectors set of Ttr∗/
Tt=Ttrx∪Tte;    /∗Tt  denote the target sample set∗/
Taux=select_x(Tau);   /∗Taux denote the feature vectors set of Tau∗/
taux=MIDS_Construction(Tt,Taux);    /∗constructing the MIDS∗/
tau=expand(taux,Tau);  /∗add the corresponding labels to the feature
vectors oftaux∗/
T1=tau∪Ttr   /∗T1 denotes the new training set∗/
f(⋅)=Learner(T1);  /∗f denotes the function implemented by a base
learning algorithm trained on the new training setT1∗/Algorithm 4:The direct classification algorithm of Scenario 2.
Require: the target training set Ttr={(xitr,yitr)∣i=1,2,…,m}, the target testing set
Tte={(xjte,yjte)∣j=1,2,…,n}, a base learning algorithm Learner
Ensure: classification function f(⋅)
ttr=MIDS_Construction(Ttr,Tte);       /∗constructing the MIDS∗/
f(⋅)=Learner(ttr);  /∗f denotes the function implemented by a base
learning algorithm trained on the new training setttr∗/Algorithm 5:The indirect classification algorithm of Scenario 2.
Require: the target training set Ttr={(xitr,yitr)∣i=1,2,…,m}, the target testing set
Tte={xjte∣j=1,2,…,n}, a base learning algorithm Learner
Ensure: classification function f(⋅)
Ttrx=select_x(Ttr);     /∗Ttrx denote the feature vectors set of Ttr∗/
ttrx=MIDS_Construction(Ttrx,Tte);  /∗constructing the MIDS∗/
ttr=expand(ttrx,Ttr);  /∗add the corresponding labels to the feature
vectors ofttrx∗/
f(⋅)=Learner(ttr);  /∗f denotes the function implemented by a base
learning algorithm trained on the new training setttr∗/


## 4.1. The MIDS Construction of Scenario1

LetTtr=xitr,yitr∣i=1,2,…,m be the target training set, Tte=xjte,yjte∣j=1,2,…,n the target testing set, and Tau={xkau,ykau∣k=1,2,…,p} the auxiliary training set. Assume that Ttr and Tte follow the same distribution Pt(x,y) and Tau follow another distribution Ps(x,y). In this section, we will present two kinds of MIDS construction methods, where one is direct and the other is indirect. Moreover, we will prove that the effect of the indirect method is equivalent to that of the direct method.


### 4.1.1. The Direct MIDS Construction Method of Scenario1

With respect to the direct MIDS construction, we consider feature vectorx and label y as a joint vector. We consider Tt=Ttr∪Tte and Tau as the target sample set and the source sample set, respectively. Thus we can use the above algorithm directly to obtain the MIDS. The MIDS construction method by considering feature vector x and label y as a joint vector is called the direct MIDS construction method.Since feature vectorx and label y are considered to be one joint vector, the dimension of samples will be increased. As described in Section 3.3, with the increase of the dimension, the running time of the MIDS algorithm will increase correspondingly. In the next section, we will present the indirect MIDS construction method, for which it is not necessary to consider x and y collectively and the MIDS is constructed according to feature vector x alone. Thus the indirect method can reduce effectively the running time and moreover it can be applied to the case where the target testing set contains only feature vectors.


### 4.1.2. The Indirect MIDS Construction Method of Scenario1

With respect to the case where there are no class labels in the target testing set, we can construct the MIDS according to feature vectorx alone. The MIDS construction method by considering only feature vector x is called the indirect MIDS construction method. Now let Tte=xjte∣j=1,2,…,n be target testing set. First of all, we present the detailed process of the indirect MIDS construction method.Process  1. Remove all the labels of samples in Tt, and label the set composed by the remaining feature vectors as Ttx. Similarly, remove all the labels of samples in Tau, and label the set composed by the remaining feature vectors as Taux.Process  2. Use the MIDS construction algorithm to obtain a subset taux of Taux.Process  3. Add the class labels removed in Process 1 to each sample of taux correspondingly, and thus we obtain a subset tau of Tau.Below we will prove that the effect of the indirect method is equivalent to that of the direct method.Theorem 6.
The subsettau obtained from the auxiliary set Tau by the indirect MIDS method follows the same distribution with the target set Tt; that is, PS′(x,y)=PT(x,y), where PS′(X,Y) and PT(x,y) denote the distributions of tau and Tt, respectively.Proof.
LetPS′(x) and PT(x) denote the distributions of taux and Ttx, respectively. From the definition of conditional distribution, we have(2)PTx,y=PTy∣xPTx,PS′x,y=PS′y∣xPS′x.As described in Process  3, tau is obtained by adding the original class labels to taux correspondingly. Thus the conditional probability is unchanged; that is, PS′y∣x=PSy∣x. From Definition 3, we know that PT(y∣x)=PS(y∣x). Thus we can obtain that PS′y∣x=PTy∣x. Moreover since taux is a MIDS of Ttx, we can obtain that PS′x=PT(x). Therefore we have PS′x,y=PTx,y.


## 4.1.1. The Direct MIDS Construction Method of Scenario1

With respect to the direct MIDS construction, we consider feature vectorx and label y as a joint vector. We consider Tt=Ttr∪Tte and Tau as the target sample set and the source sample set, respectively. Thus we can use the above algorithm directly to obtain the MIDS. The MIDS construction method by considering feature vector x and label y as a joint vector is called the direct MIDS construction method.Since feature vectorx and label y are considered to be one joint vector, the dimension of samples will be increased. As described in Section 3.3, with the increase of the dimension, the running time of the MIDS algorithm will increase correspondingly. In the next section, we will present the indirect MIDS construction method, for which it is not necessary to consider x and y collectively and the MIDS is constructed according to feature vector x alone. Thus the indirect method can reduce effectively the running time and moreover it can be applied to the case where the target testing set contains only feature vectors.


## 4.1.2. The Indirect MIDS Construction Method of Scenario1

With respect to the case where there are no class labels in the target testing set, we can construct the MIDS according to feature vectorx alone. The MIDS construction method by considering only feature vector x is called the indirect MIDS construction method. Now let Tte=xjte∣j=1,2,…,n be target testing set. First of all, we present the detailed process of the indirect MIDS construction method.Process  1. Remove all the labels of samples in Tt, and label the set composed by the remaining feature vectors as Ttx. Similarly, remove all the labels of samples in Tau, and label the set composed by the remaining feature vectors as Taux.Process  2. Use the MIDS construction algorithm to obtain a subset taux of Taux.Process  3. Add the class labels removed in Process 1 to each sample of taux correspondingly, and thus we obtain a subset tau of Tau.Below we will prove that the effect of the indirect method is equivalent to that of the direct method.Theorem 6.
The subsettau obtained from the auxiliary set Tau by the indirect MIDS method follows the same distribution with the target set Tt; that is, PS′(x,y)=PT(x,y), where PS′(X,Y) and PT(x,y) denote the distributions of tau and Tt, respectively.Proof.
LetPS′(x) and PT(x) denote the distributions of taux and Ttx, respectively. From the definition of conditional distribution, we have(2)PTx,y=PTy∣xPTx,PS′x,y=PS′y∣xPS′x.As described in Process  3, tau is obtained by adding the original class labels to taux correspondingly. Thus the conditional probability is unchanged; that is, PS′y∣x=PSy∣x. From Definition 3, we know that PT(y∣x)=PS(y∣x). Thus we can obtain that PS′y∣x=PTy∣x. Moreover since taux is a MIDS of Ttx, we can obtain that PS′x=PT(x). Therefore we have PS′x,y=PTx,y.


## 4.2. The MIDS Construction of Scenario2

LetTtr=(xitr,yitr)∣i=1,2,…,m be target training set and Tte=(xjte,yjte)∣j=1,2,…,n target testing set. Assume that Ttr and Tte follow distributions Ptr(x,y) and Pte(x,y), respectively. We consider Tte and Ttr as the target sample set and the source sample set, respectively. Thus we also can use the above algorithm directly to obtain the MIDS.With respect to the case where there are no class labels in the target testing set, we can also use indirect method to construct the MIDS. Now letTte={xjte∣j=1,2,…,n} be target testing set. The detailed process is as follows.Process 1. Remove all the labels of samples in Ttr, and label the set composed by the remaining feature vectors as Ttrx.Process 2. Use the MIDS construction algorithm to obtain a subset ttrx of Ttrx.Process 3. Add the class labels removed in Process 1 to each sample of ttrx correspondingly, and thus we obtain a subset ttr of Ttr.


## 4.3. Classification Algorithms

With the help of the MIDS construction method, we can make effective classification by traditional classification method. With respect to Scenario1, we first construct the MIDS from the auxiliary set and then train a model on the set composed by the target training set and the MIDS. The pseudocodes of the two classification algorithms corresponding to the direct and indirect MIDS construction methods are shown in Algorithms 2 and 3, respectively. With respect to Scenario 2, we first construct the MIDS from the target training set and then train a model on this MIDS. The pseudocodes of the two classification algorithms corresponding to the direct and indirect MIDS construction methods are shown in Algorithms 4 and 5, respectively.Algorithm 2:The direct classification algorithm of Scenario 1.
Require: the target training set Ttr={(xitr,yitr)∣i=1,2,…,m}, the target testing set Tte={(xjte,yjte)∣j=1,2,…,n},
the auxiliary sample setTau={(xkau,ykau)∣k=1,2,…,p}, a base learning algorithm Learner
Ensure: classification function f(⋅)
Tt=Ttr∪Tte;        /∗Tt denotes the target sample set∗/
tau=MIDS_Construction(Tt,Tau);     /∗constructing the MIDS∗/
T1=tau∪Ttr;     /∗T1 denotes the new training set∗/
f(⋅)=Learner(T1);    /∗f denotes the function implemented by a base
learning algorithm trained on the new training setT1∗/Algorithm 3:The indirect classification algorithm of Scenario 1.
Require: the target training set Ttr={(xitr,yitr)∣i=1,2,…,m}, the target testing set Tte={xjte∣j=1,2,…,n},
the auxiliary sample setTau={(xkau,ykau)∣k=1,2,…,p}, a base learning algorithm Learner
Ensure: classification function f(⋅)
Ttrx=select_x(Ttr);     /∗Ttrx denote the feature vectors set of Ttr∗/
Tt=Ttrx∪Tte;    /∗Tt  denote the target sample set∗/
Taux=select_x(Tau);   /∗Taux denote the feature vectors set of Tau∗/
taux=MIDS_Construction(Tt,Taux);    /∗constructing the MIDS∗/
tau=expand(taux,Tau);  /∗add the corresponding labels to the feature
vectors oftaux∗/
T1=tau∪Ttr   /∗T1 denotes the new training set∗/
f(⋅)=Learner(T1);  /∗f denotes the function implemented by a base
learning algorithm trained on the new training setT1∗/Algorithm 4:The direct classification algorithm of Scenario 2.
Require: the target training set Ttr={(xitr,yitr)∣i=1,2,…,m}, the target testing set
Tte={(xjte,yjte)∣j=1,2,…,n}, a base learning algorithm Learner
Ensure: classification function f(⋅)
ttr=MIDS_Construction(Ttr,Tte);       /∗constructing the MIDS∗/
f(⋅)=Learner(ttr);  /∗f denotes the function implemented by a base
learning algorithm trained on the new training setttr∗/Algorithm 5:The indirect classification algorithm of Scenario 2.
Require: the target training set Ttr={(xitr,yitr)∣i=1,2,…,m}, the target testing set
Tte={xjte∣j=1,2,…,n}, a base learning algorithm Learner
Ensure: classification function f(⋅)
Ttrx=select_x(Ttr);     /∗Ttrx denote the feature vectors set of Ttr∗/
ttrx=MIDS_Construction(Ttrx,Tte);  /∗constructing the MIDS∗/
ttr=expand(ttrx,Ttr);  /∗add the corresponding labels to the feature
vectors ofttrx∗/
f(⋅)=Learner(ttr);  /∗f denotes the function implemented by a base
learning algorithm trained on the new training setttr∗/


## 5. Experiments

In this section, we perform experiments to test the performance of the proposed classification algorithms. As proven in Section4, the effect of the indirect method is equivalent to that of the direct method. Thus, we just test the performance of the two indirect classification algorithms. The experiment data in this section come from the UCI Machine Learning Repository [22]. All experiments are run on 2.00 GHz, Intel (R) Core (TM) i5-4200U CPU with 4 GB main memory under window 8.


### 5.1. The Experiment on Scenario1

(1) Experimental Data Construction. This experiment is performed on 20 data sets, from which the target training set, the target testing set, and the auxiliary training set are constructed by the following principles.Principle 1.
The target training set and the target testing set should follow the same distribution.Principle 2.
The auxiliary training set and the target set should follow different distributions.Principle 3.
The size of the target training set is far less than that of the auxiliary training set.We select auxiliary samples using a deliberately biased procedure (as in [19]). To describe our biased selection scheme, we need to define an additional random variable si for each point in the pool of possible training samples, where si=1 means the ith sample is included and si=0 indicates an excluded sample. In this paper, we discuss the classification problems under covariate shift, so we only consider the situation Psi∣xi,yi=Psi∣xi. Below, we present the detailed method of experimental data construction. First of all, we select some samples randomly from the original data set to compose the target set, 1/4 of the data used for training and 3/4 for testing. Then, in the remaining samples, we consider a biased sampling scheme based on the input features to construct the auxiliary set. For convenience, in this paper, we only consider a biased sampling scheme based on one input feature. For example, with respect to breast cancer data set, there are nine features, with integer values from 1 to 10. We consider a biased sampling scheme based on the first feature. Since smaller feature values predominate in the unbiased data, we consider a biased sampling scheme according to Ps=1∣x≤6=0.2 and Ps=1∣x>6=0.8, where x is the value of the first feature.(2) Experimental Methods. In the following, we compare our method (the indirect classification of Scenario 1, which is denoted by IDC1) against two other methods: the traditional classification algorithm (training on the set composed by target training samples and auxiliary samples) and the TrAdaBoost algorithm proposed in [15].We selectC-SVC [23] and Radial Basis Function (RBF) [1],(3)Kx,y=exp⁡-x-y2β,as the basic classification algorithm and kernel function, respectively, for the above three methods, where C is a penalty factor, β is a width parameter, and x and y are n-dimensional vectors in the original feature space. With respect to the multiclass data sets of the 20 selected data sets, we select one-against-all (1-v-r) approach [24], which is to transform a c-class problem into c-two-class problems, where one class is separated from the remaining ones. In this experiment, the best C and β are obtained by 10-fold cross-validation.(3) Result Analysis. The three methods are compared on the selected 20 data sets. Five runs of 10-fold cross-validation are performed for each algorithm, and the average result is reported in Table 1, where the numbers following “±” are the standard deviations. The running time and parameter values of different algorithms are shown in Table 2, where N denote the number of iterations, C is a penalty factor, β is a width parameter, and t (ms) denotes the running time. N is set to 100 according to the parameter setting in [15], and the best C and β are obtained by 10-fold cross-validation.Table 1
Comparing ICD1 with SVM and TrAdaBoost.
Data set
SVM
IDC1
TrAdaBoost
Australian
0.756 ± 0.082
0.889 ± 0.052
0.836 ± 0.055
Balance
0.721 ± 0.072
0.846 ± 0.060
0.803 ± 0.062
Breast
0.698 ± 0.088
0.779 ± 0.086
0.722 ± 0.082
Cleveland
0.623 ± 0.072
0.697 ± 0.067
0.660 ± 0.061
Credit
0.792 ± 0.020
0.902 ± 0.025
0.826 ± 0.031
Diabetes
0.702 ± 0.056
0.816 ± 0.046
0.733 ± 0.039
Heart
0.729 ± 0.092
0.832 ± 0.070
0.830 ± 0.072
Ionosphere
0.837 ± 0.053
0.926 ± 0.052
0.903 ± 0.059
Iris
0.805 ± 0.061
0.976 ± 0.044
0.915 ± 0.049
Liver
0.672 ± 0.062
0.729 ± 0.038
0.732 ± 0.042
Page
0.892 ± 0.015
0.982 ± 0.021
0.901 ± 0.022
Sonar
0.705 ± 0.105
0.820 ± 0.102
0.767 ± 0.099
Thyroid
0.825 ± 0.081
0.961 ± 0.076
0.882 ± 0.075
Vehicle
0.708 ± 0.021
0.798 ± 0.025
0.790 ± 0.026
Voting
0.825 ± 0.046
0.963 ± 0.022
0.896 ± 0.028
Waveform21
0.721 ± 0.026
0.823 ± 0.017
0.821 ± 0.010
Waveform40
0.772 ± 0.025
0.838 ± 0.019
0.786 ± 0.029
Wine
0.793 ± 0.098
0.915 ± 0.092
0.898 ± 0.109
wdbc
0.803 ± 0.036
0.966 ± 0.023
0.909 ± 0.018
wpbc
0.682 ± 0.113
0.775 ± 0.099
0.726 ± 0.094Table 2
The running time and parameter values in Experiment  1.
Data set
SVM
IDC1
TrAdaBoost
t
,
c
,
β
t
,
c
,
β
t
,
c
,
β
,
N
Australian
250.6, 10, 16
210.1, 100, 16
280.9, 50, 128, 100
Balance
322.1, 20, 8
295.2, 50, 32
353.2, 30, 256, 100
Breast
412.1, 100, 64
368.8, 10, 128
515.5, 100, 32, 100
Cleveland
243.2, 50, 32
205.1, 20, 64
301.5, 100, 64, 100
Credit
1129.2, 1000, 128
989.3, 500, 16
1250.6, 500, 64, 100
Diabetes
517.6, 1000, 32
410.1, 100, 128
620.3, 500, 32, 100
Heart
32.5, 100, 256
24.6, 30, 512
33.7, 10, 128, 100
Ionosphere
50.6, 20, 128
42.1, 1000, 32
52.3, 10, 256, 100
Iris
12.2, 10, 64
9.3, 50, 64
13.1, 100, 32, 100
Liver
19.6, 30, 32
18.2, 50, 32
22.3, 100, 128, 100
Page
22.1, 100, 128
18.8, 200, 64
22.8, 500, 16, 100
Sonar
9.6, 50, 1024
6.6, 100, 128
10.2, 80, 512, 100
Thyroid
32.3, 1000, 256
26.6, 500, 128
40.2, 60, 64, 100
Vehicle
1080.9, 100, 8
916.1, 50, 16
1120.3, 100, 128, 100
Voting
62.8, 60, 64
56.6, 100, 256
70.5, 80, 512, 100
Waveform21
632.1, 30, 32
527.1, 60, 64
636.9, 10, 16, 100
Waveform40
535.3, 50, 64
468.2, 100, 128
586.2, 200, 16, 100
Wine
50.2, 1000, 256
44.1, 500, 128
59.2, 200, 1024, 100
wdbc
289.2, 200, 128
266.1, 100, 256
299.5, 500, 32, 100
wpbc
267.1, 500, 512
256.9, 1000, 1024
268.2, 100, 512, 100As is shown in Table1, the precision given by SVM is strictly lower than IDC1 and TrAdaBoost. Intuitively, this is true because, unlike SVM, IDC1 and TrAdaBoost are learning techniques designed for classification of Scenario 1. Furthermore Table 1 shows that IDC1 outperforms TrAdaBoost. In detail, pairwise two-tailed t-tests indicate that there are 16 data sets (Australian,balance,breast,Cleveland,credit,diabetes,ionosphere,iris,page,sonar,thyroid,voting,waveform40,wine,wdbc, andwpbc) where IDC1 is significantly more accurate than TrAdaBoost, while there is no significant difference on the remaining 4 data sets. We believe that the auxiliary set contain not only good samples, but also noisy data that caused the distribution of the auxiliary set different from that of the target set. The reason why IDC1 outperforms TrAdaBoost might be that ICD1 always employs the most important samples, which is included in the MIDS, to help the learners, while TrAdaBoost sometimes can not avoid using bad samples to help the learners.Moreover, as shown in Table2, the running time of IDC1 is the least, while the running time of TrAdaBoost is the most. Thus IDC1 is the most effective model. The reason is below. In this experiment, traditional SVM algorithm uses the target sample set and the whole auxiliary sample set for training, while IDC1 employs the target sample set and only a subset of the auxiliary samples set for training. With respect to TrAdaBoost, the reason why its running time is the most is that it needs to do repeated iteration for a better performance.


### 5.2. The Experiment on Scenario2

(1) Experimental Data Construction. Unlike the first experiment, in this experiment, we only construct the target training set and the target testing set. We should guarantee that the target training set and the target testing set follow different distributions. Like Scenario 1, we also use a deliberately biased procedure to construct the experimental data.(2) Experimental Method. In the following, we compare our method (the indirect classification of Scenario 2, which is denoted by IDC2) against two other methods: the traditional classification algorithm and the KLIEP algorithm proposed in [21]. We also select C-SVC and RBF as the basic classification algorithm and kernel function, respectively, and select 1-v-r approach for the multiclass data sets.(3) Result Analysis. Five runs of 10-fold cross-validation are performed for each algorithm, and the average result is reported in Table 3, where the numbers following “±” are the standard deviations. Also the running time and parameter values of different algorithms are shown in Table 4.Table 3
Comparing ICD2 with SVM and KLIEP.
Data set
SVM
IDC2
KLIEP
Australian
0.787 ± 0.046
0.869 ± 0.035
0.827 ± 0.063
Balance
0.754 ± 0.049
0.823 ± 0.028
0.819 ± 0.055
Breast
0.669 ± 0.059
0.789 ± 0.062
0.783 ± 0.049
Cleveland
0.601 ± 0.068
0.677 ± 0.034
0.671 ± 0.062
Credit
0.790 ± 0.056
0.892 ± 0.068
0.832 ± 0.051
Diabetes
0.802 ± 0.044
0.826 ± 0.039
0.822 ± 0.039
Heart
0.697 ± 0.083
0.818 ± 0.088
0.831 ± 0.062
Ionosphere
0.852 ± 0.046
0.902 ± 0.044
0.899 ± 0.056
Iris
0.901 ± 0.062
0.919 ± 0.056
0.912 ± 0.072
Liver
0.653 ± 0.065
0.745 ± 0.041
0.751 ± 0.053
Page
0.836 ± 0.016
0.932 ± 0.009
0.889 ± 0.022
Sonar
0.727 ± 0.223
0.856 ± 0.102
0.846 ± 0.235
Thyroid
0.859 ± 0.088
0.933 ± 0.128
0.929 ± 0.077
Vehicle
0.665 ± 0.056
0.728 ± 0.032
0.739 ± 0.046
Voting
0.795 ± 0.052
0.929 ± 0.031
0.915 ± 0.038
Waveform21
0.771 ± 0.019
0.832 ± 0.012
0.801 ± 0.026
Waveform40
0.756 ± 0.021
0.815 ± 0.018
0.818 ± 0.025
Wine
0.876 ± 0.096
0.922 ± 0.076
0.916 ± 0.091
wdbc
0.853 ± 0.021
0.935 ± 0.032
0.939 ± 0.012
wpbc
0.681 ± 0.101
0.765 ± 0.086
0.779 ± 0.121Table 4
The running time and parameter values in Experiment  2.
Data set
SVM
IDC2
KLIEP
t
,
c
,
β
t
,
c
,
β
t
,
c
,
β
Australian
225.6, 100, 64
209.1, 60, 64
218.9, 200, 128
Balance
262.1, 20, 128
225.2, 500, 64
278.2, 80, 16
Breast
312.1, 10, 128
288.2, 60, 128
315.5, 200, 16
Cleveland
196.2, 500, 256
160.1, 200, 1024
171.5, 80, 32
Credit
1029.2, 100, 64
899.3, 30, 256
1050.6, 20, 64
Diabetes
469.2, 200, 64
420.5, 300, 1024
425.5, 50, 16
Heart
28.8, 50, 512
22.1, 10, 16
30.3, 20, 64
Ionosphere
46.5, 10, 16
40.9, 200, 64
42.5, 80, 256
Iris
9.2, 100, 128
6.3, 60, 16
9.9, 200, 32
Liver
18.2, 60, 64
13.2, 100, 32
16.2, 60, 256
Page
32.1, 80, 1024
29.6, 1000, 16
32.6, 20, 16
Sonar
12.6, 20, 64
10.1, 200, 64
29.6, 60, 256
Thyroid
29.8, 100, 64
25.5, 400, 16
30.6, 100, 64
Vehicle
1286.2, 200, 16
1120.3, 100, 128
1225.6, 200, 16
Voting
44.6, 20, 16
38.2, 80, 512
50.5, 200, 1024
Waveform21
556.3, 600, 64
513.2, 300, 16
532.8, 100, 256
Waveform40
443.3, 800, 128
399.6, 200, 64
422.1, 600, 256
Wine
49.6, 20, 256
40.3, 100, 64
44.5, 50, 512
wdbc
266.6, 600, 64
236.2, 200, 256
299.5, 10, 128
wpbc
198.7, 10, 64
155.3, 500, 128
167.8, 200, 64As is shown in Table3, the precision given by SVM is strictly lower than IDC2 and KLIEP. Like the analysis of Scenario 1, this is true because, unlike SVM, IDC2 and KLIEP are learning techniques designed for classification of Scenario 2. Furthermore Table 3 shows that IDC2 is comparable to KLIEP that is a state-of-the-art algorithm. In detail, pairwise two-tailed t-tests indicate that there are 4 data sets (Australian,credit,page, andwaveform21) where IDC2 outperforms KLIEP, and there are 3 data sets (heart,vehicle, andwpbc) where IDC2 performs a little worse than KLIEP, while there is no significant difference on the remaining 13 data sets. Therefore, ICD2 exhibits a new way of classification learning of Scenario 2.As shown in Table4, IDC2 costs less time than SVM and KLIEP. Like the case in Experiment  1, the reason is that in the training process it uses only a subset of the training samples, while SVM and KLIEP have to employ the whole training samples for training.


## 5.1. The Experiment on Scenario1

(1) Experimental Data Construction. This experiment is performed on 20 data sets, from which the target training set, the target testing set, and the auxiliary training set are constructed by the following principles.Principle 1.
The target training set and the target testing set should follow the same distribution.Principle 2.
The auxiliary training set and the target set should follow different distributions.Principle 3.
The size of the target training set is far less than that of the auxiliary training set.We select auxiliary samples using a deliberately biased procedure (as in [19]). To describe our biased selection scheme, we need to define an additional random variable si for each point in the pool of possible training samples, where si=1 means the ith sample is included and si=0 indicates an excluded sample. In this paper, we discuss the classification problems under covariate shift, so we only consider the situation Psi∣xi,yi=Psi∣xi. Below, we present the detailed method of experimental data construction. First of all, we select some samples randomly from the original data set to compose the target set, 1/4 of the data used for training and 3/4 for testing. Then, in the remaining samples, we consider a biased sampling scheme based on the input features to construct the auxiliary set. For convenience, in this paper, we only consider a biased sampling scheme based on one input feature. For example, with respect to breast cancer data set, there are nine features, with integer values from 1 to 10. We consider a biased sampling scheme based on the first feature. Since smaller feature values predominate in the unbiased data, we consider a biased sampling scheme according to Ps=1∣x≤6=0.2 and Ps=1∣x>6=0.8, where x is the value of the first feature.(2) Experimental Methods. In the following, we compare our method (the indirect classification of Scenario 1, which is denoted by IDC1) against two other methods: the traditional classification algorithm (training on the set composed by target training samples and auxiliary samples) and the TrAdaBoost algorithm proposed in [15].We selectC-SVC [23] and Radial Basis Function (RBF) [1],(3)Kx,y=exp⁡-x-y2β,as the basic classification algorithm and kernel function, respectively, for the above three methods, where C is a penalty factor, β is a width parameter, and x and y are n-dimensional vectors in the original feature space. With respect to the multiclass data sets of the 20 selected data sets, we select one-against-all (1-v-r) approach [24], which is to transform a c-class problem into c-two-class problems, where one class is separated from the remaining ones. In this experiment, the best C and β are obtained by 10-fold cross-validation.(3) Result Analysis. The three methods are compared on the selected 20 data sets. Five runs of 10-fold cross-validation are performed for each algorithm, and the average result is reported in Table 1, where the numbers following “±” are the standard deviations. The running time and parameter values of different algorithms are shown in Table 2, where N denote the number of iterations, C is a penalty factor, β is a width parameter, and t (ms) denotes the running time. N is set to 100 according to the parameter setting in [15], and the best C and β are obtained by 10-fold cross-validation.Table 1
Comparing ICD1 with SVM and TrAdaBoost.
Data set
SVM
IDC1
TrAdaBoost
Australian
0.756 ± 0.082
0.889 ± 0.052
0.836 ± 0.055
Balance
0.721 ± 0.072
0.846 ± 0.060
0.803 ± 0.062
Breast
0.698 ± 0.088
0.779 ± 0.086
0.722 ± 0.082
Cleveland
0.623 ± 0.072
0.697 ± 0.067
0.660 ± 0.061
Credit
0.792 ± 0.020
0.902 ± 0.025
0.826 ± 0.031
Diabetes
0.702 ± 0.056
0.816 ± 0.046
0.733 ± 0.039
Heart
0.729 ± 0.092
0.832 ± 0.070
0.830 ± 0.072
Ionosphere
0.837 ± 0.053
0.926 ± 0.052
0.903 ± 0.059
Iris
0.805 ± 0.061
0.976 ± 0.044
0.915 ± 0.049
Liver
0.672 ± 0.062
0.729 ± 0.038
0.732 ± 0.042
Page
0.892 ± 0.015
0.982 ± 0.021
0.901 ± 0.022
Sonar
0.705 ± 0.105
0.820 ± 0.102
0.767 ± 0.099
Thyroid
0.825 ± 0.081
0.961 ± 0.076
0.882 ± 0.075
Vehicle
0.708 ± 0.021
0.798 ± 0.025
0.790 ± 0.026
Voting
0.825 ± 0.046
0.963 ± 0.022
0.896 ± 0.028
Waveform21
0.721 ± 0.026
0.823 ± 0.017
0.821 ± 0.010
Waveform40
0.772 ± 0.025
0.838 ± 0.019
0.786 ± 0.029
Wine
0.793 ± 0.098
0.915 ± 0.092
0.898 ± 0.109
wdbc
0.803 ± 0.036
0.966 ± 0.023
0.909 ± 0.018
wpbc
0.682 ± 0.113
0.775 ± 0.099
0.726 ± 0.094Table 2
The running time and parameter values in Experiment  1.
Data set
SVM
IDC1
TrAdaBoost
t
,
c
,
β
t
,
c
,
β
t
,
c
,
β
,
N
Australian
250.6, 10, 16
210.1, 100, 16
280.9, 50, 128, 100
Balance
322.1, 20, 8
295.2, 50, 32
353.2, 30, 256, 100
Breast
412.1, 100, 64
368.8, 10, 128
515.5, 100, 32, 100
Cleveland
243.2, 50, 32
205.1, 20, 64
301.5, 100, 64, 100
Credit
1129.2, 1000, 128
989.3, 500, 16
1250.6, 500, 64, 100
Diabetes
517.6, 1000, 32
410.1, 100, 128
620.3, 500, 32, 100
Heart
32.5, 100, 256
24.6, 30, 512
33.7, 10, 128, 100
Ionosphere
50.6, 20, 128
42.1, 1000, 32
52.3, 10, 256, 100
Iris
12.2, 10, 64
9.3, 50, 64
13.1, 100, 32, 100
Liver
19.6, 30, 32
18.2, 50, 32
22.3, 100, 128, 100
Page
22.1, 100, 128
18.8, 200, 64
22.8, 500, 16, 100
Sonar
9.6, 50, 1024
6.6, 100, 128
10.2, 80, 512, 100
Thyroid
32.3, 1000, 256
26.6, 500, 128
40.2, 60, 64, 100
Vehicle
1080.9, 100, 8
916.1, 50, 16
1120.3, 100, 128, 100
Voting
62.8, 60, 64
56.6, 100, 256
70.5, 80, 512, 100
Waveform21
632.1, 30, 32
527.1, 60, 64
636.9, 10, 16, 100
Waveform40
535.3, 50, 64
468.2, 100, 128
586.2, 200, 16, 100
Wine
50.2, 1000, 256
44.1, 500, 128
59.2, 200, 1024, 100
wdbc
289.2, 200, 128
266.1, 100, 256
299.5, 500, 32, 100
wpbc
267.1, 500, 512
256.9, 1000, 1024
268.2, 100, 512, 100As is shown in Table1, the precision given by SVM is strictly lower than IDC1 and TrAdaBoost. Intuitively, this is true because, unlike SVM, IDC1 and TrAdaBoost are learning techniques designed for classification of Scenario 1. Furthermore Table 1 shows that IDC1 outperforms TrAdaBoost. In detail, pairwise two-tailed t-tests indicate that there are 16 data sets (Australian,balance,breast,Cleveland,credit,diabetes,ionosphere,iris,page,sonar,thyroid,voting,waveform40,wine,wdbc, andwpbc) where IDC1 is significantly more accurate than TrAdaBoost, while there is no significant difference on the remaining 4 data sets. We believe that the auxiliary set contain not only good samples, but also noisy data that caused the distribution of the auxiliary set different from that of the target set. The reason why IDC1 outperforms TrAdaBoost might be that ICD1 always employs the most important samples, which is included in the MIDS, to help the learners, while TrAdaBoost sometimes can not avoid using bad samples to help the learners.Moreover, as shown in Table2, the running time of IDC1 is the least, while the running time of TrAdaBoost is the most. Thus IDC1 is the most effective model. The reason is below. In this experiment, traditional SVM algorithm uses the target sample set and the whole auxiliary sample set for training, while IDC1 employs the target sample set and only a subset of the auxiliary samples set for training. With respect to TrAdaBoost, the reason why its running time is the most is that it needs to do repeated iteration for a better performance.


## 5.2. The Experiment on Scenario2

(1) Experimental Data Construction. Unlike the first experiment, in this experiment, we only construct the target training set and the target testing set. We should guarantee that the target training set and the target testing set follow different distributions. Like Scenario 1, we also use a deliberately biased procedure to construct the experimental data.(2) Experimental Method. In the following, we compare our method (the indirect classification of Scenario 2, which is denoted by IDC2) against two other methods: the traditional classification algorithm and the KLIEP algorithm proposed in [21]. We also select C-SVC and RBF as the basic classification algorithm and kernel function, respectively, and select 1-v-r approach for the multiclass data sets.(3) Result Analysis. Five runs of 10-fold cross-validation are performed for each algorithm, and the average result is reported in Table 3, where the numbers following “±” are the standard deviations. Also the running time and parameter values of different algorithms are shown in Table 4.Table 3
Comparing ICD2 with SVM and KLIEP.
Data set
SVM
IDC2
KLIEP
Australian
0.787 ± 0.046
0.869 ± 0.035
0.827 ± 0.063
Balance
0.754 ± 0.049
0.823 ± 0.028
0.819 ± 0.055
Breast
0.669 ± 0.059
0.789 ± 0.062
0.783 ± 0.049
Cleveland
0.601 ± 0.068
0.677 ± 0.034
0.671 ± 0.062
Credit
0.790 ± 0.056
0.892 ± 0.068
0.832 ± 0.051
Diabetes
0.802 ± 0.044
0.826 ± 0.039
0.822 ± 0.039
Heart
0.697 ± 0.083
0.818 ± 0.088
0.831 ± 0.062
Ionosphere
0.852 ± 0.046
0.902 ± 0.044
0.899 ± 0.056
Iris
0.901 ± 0.062
0.919 ± 0.056
0.912 ± 0.072
Liver
0.653 ± 0.065
0.745 ± 0.041
0.751 ± 0.053
Page
0.836 ± 0.016
0.932 ± 0.009
0.889 ± 0.022
Sonar
0.727 ± 0.223
0.856 ± 0.102
0.846 ± 0.235
Thyroid
0.859 ± 0.088
0.933 ± 0.128
0.929 ± 0.077
Vehicle
0.665 ± 0.056
0.728 ± 0.032
0.739 ± 0.046
Voting
0.795 ± 0.052
0.929 ± 0.031
0.915 ± 0.038
Waveform21
0.771 ± 0.019
0.832 ± 0.012
0.801 ± 0.026
Waveform40
0.756 ± 0.021
0.815 ± 0.018
0.818 ± 0.025
Wine
0.876 ± 0.096
0.922 ± 0.076
0.916 ± 0.091
wdbc
0.853 ± 0.021
0.935 ± 0.032
0.939 ± 0.012
wpbc
0.681 ± 0.101
0.765 ± 0.086
0.779 ± 0.121Table 4
The running time and parameter values in Experiment  2.
Data set
SVM
IDC2
KLIEP
t
,
c
,
β
t
,
c
,
β
t
,
c
,
β
Australian
225.6, 100, 64
209.1, 60, 64
218.9, 200, 128
Balance
262.1, 20, 128
225.2, 500, 64
278.2, 80, 16
Breast
312.1, 10, 128
288.2, 60, 128
315.5, 200, 16
Cleveland
196.2, 500, 256
160.1, 200, 1024
171.5, 80, 32
Credit
1029.2, 100, 64
899.3, 30, 256
1050.6, 20, 64
Diabetes
469.2, 200, 64
420.5, 300, 1024
425.5, 50, 16
Heart
28.8, 50, 512
22.1, 10, 16
30.3, 20, 64
Ionosphere
46.5, 10, 16
40.9, 200, 64
42.5, 80, 256
Iris
9.2, 100, 128
6.3, 60, 16
9.9, 200, 32
Liver
18.2, 60, 64
13.2, 100, 32
16.2, 60, 256
Page
32.1, 80, 1024
29.6, 1000, 16
32.6, 20, 16
Sonar
12.6, 20, 64
10.1, 200, 64
29.6, 60, 256
Thyroid
29.8, 100, 64
25.5, 400, 16
30.6, 100, 64
Vehicle
1286.2, 200, 16
1120.3, 100, 128
1225.6, 200, 16
Voting
44.6, 20, 16
38.2, 80, 512
50.5, 200, 1024
Waveform21
556.3, 600, 64
513.2, 300, 16
532.8, 100, 256
Waveform40
443.3, 800, 128
399.6, 200, 64
422.1, 600, 256
Wine
49.6, 20, 256
40.3, 100, 64
44.5, 50, 512
wdbc
266.6, 600, 64
236.2, 200, 256
299.5, 10, 128
wpbc
198.7, 10, 64
155.3, 500, 128
167.8, 200, 64As is shown in Table3, the precision given by SVM is strictly lower than IDC2 and KLIEP. Like the analysis of Scenario 1, this is true because, unlike SVM, IDC2 and KLIEP are learning techniques designed for classification of Scenario 2. Furthermore Table 3 shows that IDC2 is comparable to KLIEP that is a state-of-the-art algorithm. In detail, pairwise two-tailed t-tests indicate that there are 4 data sets (Australian,credit,page, andwaveform21) where IDC2 outperforms KLIEP, and there are 3 data sets (heart,vehicle, andwpbc) where IDC2 performs a little worse than KLIEP, while there is no significant difference on the remaining 13 data sets. Therefore, ICD2 exhibits a new way of classification learning of Scenario 2.As shown in Table4, IDC2 costs less time than SVM and KLIEP. Like the case in Experiment  1, the reason is that in the training process it uses only a subset of the training samples, while SVM and KLIEP have to employ the whole training samples for training.


## 6. Conclusion

In this paper, we first propose a MIDS construction method by matching sample numbers between the target set and auxiliary set in each feature subspace, and then we propose a novel approach for classification under covariate shift by training on a new data set. Our basic idea is to train a model on a newly constructed data set following approximately the target distribution. Our approach consists of two methods, including a direct method and an indirect one. The theoretical analysis shows that the indirect method is equivalent to the direct method for the MIDS construction, but with less running time. In our experiments, the two indirect algorithms, ICD1 and ICD2, demonstrate better classification abilities than traditional learning techniques. In addition, our method can consistently deal with both scenarios of covariate shift and the cases where there are multiple auxiliary data sets coming from different distributions.We note that our method assumes that the source domain and the target domain have the same concept and can not deal with the case where they have different concepts, that is, the problem of concept drifts. In the future, we will try to extend the proposed method to address this issue.



---

*Source: 302815-2015-12-09.xml*