Migration learning notes - adaptive component analysis

《Adapting Component Analysis》 Article learning
2012 IEEE 12th International Conference on Data Mining

---

Abstract

Only when the training data is the appropriate representative of the test data , The prediction model can be implemented satisfactorily . That is, the training data and test data come from the same basic probability distribution . However , For various reasons , This assumption may not be correct in many applications . We propose a method based on Nuclear distribution embedding and Hilbert - Schmidt independence criterion （HSIC） To solve this problem . The proposed method explores a new representation of data in the new feature space , It has two properties ：

1. In the new feature space , The distribution of training and test data sets should be as close as possible
2. Important structural information of data is saved .

Our method has a closed form solution , Experimental results show that , It works well in practice .
Keywords：domain adaptation; kernel embedding; Hilbert-Schmidt independence criterion;

---

One 、 Introduce

In the field of machine learning , The training model is used to predict the response variables of the test data set . The training process is based on minimizing the loss function , Only when the training data set is a suitable representative of the test data , Learning can achieve the goal .
In the traditional prediction model , Suppose that the training data set and the test data set are the same distribution , However , In fact, the distribution of the two data sets is different for various reasons .
Domain adaptation in machine learning has always been the focus of attention , The research people have done is ：

1. Covariate shift
2. Class imbalance
3. Semi-supervised learning
4. Multi task learning
5. Sample selection bias

But all these methods mainly solve the problem through two methods ：

1. Reweight source instances
2. Change the representation space

The methods proposed in the literature have some common shortcomings ：

1. In high-dimensional datasets , The approximation of the underlying distribution makes the problem difficult to solve
2. Explore new representations of data that are not necessarily linear , Usually, the computational cost of solving problems is very high
3. Some domain adaptation techniques are only applicable to limited prediction models .

Our proposed method can solve the above problems , The algorithm finds a new representation of data in the new feature space , Make the potential probability distribution of the embedded training data set and the test data set as close as possible , And retain important structural information of data , For further prediction and analysis . These two constraints lead to a single optimization problem with closed solutions

Symbol

set up $X$ and $\varphi$ Represents a random variable ( That is, the input variables in the original feature space and the new feature space ),$Y$ Represents the corresponding response variable ( That is, output variables such as class labels ).$P(X,Y)$ yes $X$ and $Y$ The joint probability distribution of ,$P_{tr}(X)$ and $P_{ts}(X)$ Represents the training and test data set $X$ and $Y$ The true marginal probability distribution of . Again , We use it $P_{tr}(Y|X)$ and $P_{ts}(Y|X)$ To represent the true conditional probability distribution of these two domains .
Bold small letters ,$\mathbf{x}$ yes d V's sample .$X_{tr}$ and $X_{ts}$ The sizes are respectively $d\times n_{tr}$ and $d\times n_{ts}$ Matrix of training data set and test data set samples .$n_{tr}$ and $n_{ts}$ It is the number of samples in the training data set and the test data set respectively .$X_{d\times n}$ = $[X_{tr}{X}_{ts}$] It's a $n,d$ Matrix of dimensional samples , among $n=n_{tr}+n_{ts}$.$\Phi$ It is a new representation of data in the new feature space , among $\Psi :X\to \Phi$ Is defined as $\Phi$, such $\Phi :=[{\Phi }_{tr}{\Phi }_{ts}]$.${\Phi }_{tr}$ and ${\Phi }_{ts}$ Represent training and test data sets embedded in the new representation space .

Two 、 Method

The main challenge of the regional adaptation problem is the dissimilarity of the joint probability distribution of the training data set and the test data set . Decompose into
$$\begin{gathered} p_{tr}(X,Y)=p_{tr}(X)p_{tr}(Y|X) \\ {p}_{ts}(X,Y)=p_{ts}(X)p_{ts}(Y|X) \end{gathered}$$
Assuming that ： All differences between the joint probability distribution of the training data set and the test data set , It is caused by the difference between their marginal probability distributions . There is a new data representation $\Phi$, Make the edge probability distribution of the embedded training data set and the test data set similar , It means $p_{tr}(\Phi )\approx p_{ts}(\Phi )$

1. Minimize the distance between two probability distributions

Maximum average deviation (MMD) Is a nonparametric measure of the distance between data set distributions .
$$\begin{array}{c}\mathrm{MMD}\left({\hat{P}}_{tr},{\hat{P}}_{ts}\right)={\Vert {\mu }_{X_{tr}}\left[{\hat{P}}_{tr}\right]-{\mu }_{X_{ts}}\left[{\hat{P}}_{ts}\right]\Vert }_{\mathcal{H}}=\\ \underset{g\in \mathcal{F},\Vert g{\Vert }_{\mathcal{H}}\le 1}{\sup }\left({\mathbf{E}}_{X_{tr}\sim {\hat{P}}_{tr}}g\left({\mathbf{x}}_{tr}\right)-{\mathbf{E}}_{X_{ts}\sim {\hat{P}}_{ts}}g\left({\mathbf{x}}_{tr}\right)\right)\end{array}$$
In style ${\mathbf{E}}_{\mathbf{X}\sim P}[g(\mathbf{x})]$ Is the function $g(x)$ The expectation of ( The sample comes from the probability distribution $P$),MMD It can be estimated by experience as
$$\begin{array}{c}{\Vert {\mu }_{X_{tr}}\left[{\hat{P}}_{tr}\right]-{\mu }_{X_{ts}}\left[{\hat{P}}_{ts}\right]\Vert }_{\mathcal{H}}^2\approx tr\left(H{L}_{M}H{L}_{\varphi }\right)\end{array}$$
among $L_{\Phi }$ yes $\Phi$ A kernel on , The assumption is ${\Phi }^T\Phi$, $L_M$ Is a predefined kernel . So the objective function is ：
$$\begin{array}{c}\mathrm{minimize}tr\left(H{L}_{M}H{L}_{\varphi }\right)=tr\left(H{L}_{M}H{\Phi }^T\Phi \right)\end{array}$$
A simple solution is , Fold all samples of each probability distribution to a point , Then let these two points close to each other . But in the future, when making prediction and analysis , This new representation will lose key information in the data , therefore , The new representation should also retain any important data features required for later analysis .

2. Important characteristics of saving data

The dependence of raw data and its new representation can be used as a measure , Shows how the structure and important characteristics of the predicted response variables are preserved .HSIC It is used as a quantitative measure of the correlation between two random variables . The correlation between two random variables can be measured by the distance between probability distributions , This measure is estimated empirically as ：
$$\begin{array}{c}HSIC\left(X,\Phi \right)={\left(n-1\right)}^{-2}tr\left(H{K}_{X}H{L}_{\Phi }\right)\end{array}$$
among $L_{\Phi }$ yes $\Phi$ A kernel on , The assumption is ${\Phi }^T\Phi$, and $K_X$ Is a valid kernel on raw data . Choosing the kernel means retaining the structure and important information . The supplementary objective function is ：
$$\begin{array}{c}\mathrm{maximize}tr\left(H{K}_{X}H{L}_{\varphi }\right)=tr\left(H{L}_{M}H{\Phi }^T\Phi \right)\end{array}$$

3. Adjust the component analysis

take $P\left({\Phi }_{tr}\right)$ and $P\left({\Phi }_{ts}\right)$ Minimize the distance between , And keep $X$ An important feature of , Establish a single optimization problem to solve the domain adaptation problem , The solution is to embed the data into a new feature space . The objective function is defined as ：
$$\begin{array}{c}\mathrm{maximize}\frac{tr\left(H{K}_{X}H{L}_{\varphi }\right)}{tr\left(H{L}_{M}H{L}_{\varphi }\right)}\end{array}$$
Where the denominator is a measure of the distance between the probability distribution of the training data set and the probability distribution of the test data set , Molecules are measures that estimate the correlation between samples and their corresponding representations in the original space . to ：
$$\begin{array}{c}\mathrm{maximize}\frac{tr\left(H{K}_{X}H{\Phi }^T\Phi \right)}{tr\left(H{L}_{M}H{\Phi }^T\Phi \right)}=\frac{tr\left(\Phi H{K}_{X}H{\Phi }^T\right)}{tr\left(\Phi H{L}_{M}H{\Phi }^T\right)}\end{array}$$
The objective function is for $\Phi$ Any proportion of is constant , You can choose $\Phi$, Make the denominator equal to 1.
$$\begin{array}{c}\mathrm{maximize}tr\left(\Phi H{K}_{X}H{\Phi }^T\right)\\ subjecttotr\left(\Phi H{L}_{M}H{\Phi }^T\right)=1\end{array}$$
Because this optimization problem has a closed form solution , So it can directly find the best $\Phi$. This corresponds to an eigenvector estimation problem ,${\Phi }^T$ yes $K_X^{-1}{L}_M$ The eigenvector matrix of . Selected eigenvector $d^{\prime }\le d$ Is the dimension of data in the new feature space .
The proposed domain adaptation algorithm is called Adaptive component analysis (adaptive Component Analysis, ACA), On the basis of training set and test set , utilize Response variables of the training set To enhance the performance of the algorithm . They are encapsulated in the kernel $K_X$ in . Once you find the right expression , We can apply further prediction algorithms to the samples in the new feature space

Classification task kernel $K_X$ The choice of :

Using training data sets Response variables It's valuable information , It can improve the efficiency of the algorithm .
Use Response variables The information of is conducive to finding a new representation of data that is more suitable for the next prediction and analysis .
Rewrite according to linear kernel function $K_X$, We have :
$$\begin{array}{c}{K}_X=\left[\begin{array}{c}{X}_{tr}^T\\ X_{ts}^T\end{array}\right]\left[\begin{array}{cc}{X}_{tr}& X_{ts}\end{array}\right]=\left[\begin{array}{cc}{K}_{X_{tr}{X}_{tr}}& K_{X_{tr}{X}_{ts}}\\ K_{X_{ts}{X}_{tr}}& K_{X_{ts}{X}_{ts}}\end{array}\right]\end{array}$$
$K_{X_{tr}{X}_{tr}}$ and $K_{X_{ts}{X}_{ts}}$ Collect the structure information of training and test data sets respectively , These two sub matrices are very important for the learning or training of prediction models , They should be preserved .
matrix $K_X$ It can be changed to ${\hat{K}}_X$, among ${\hat{K}}_X$ It is built based on data and known response variables .
$K_{X_{ts}{X}_{tr}}$ Initially, it indicates the similarity between the training data set and the test data set .
therefore , take $K_{X_{ts}{X}_{tr}}$ and $K_{X_{tr}{X}_{ts}}$ The two sub matrices are respectively used ${\hat{K}}_{X_{ts}{X}_{tr}}=K_{X_{ts}{X}_{tr}}{K}_{Y_{tr}}$ and ${\hat{K}}_{X_{tr}{X}_{ts}}=K_{Y_{tr}}{K}_{X_{tr}{X}_{ts}}$ Replace , among $K_{Y_{tr}}$ It's the training data set $X_{tr}$ The kernel of the response variable , Indicates the similarity between the sample labels of the training data set , Its main function is to Differences between homogeneous and similar samples .
According to the formula , The samples of the training data set $x_i$ Change to the weighted mean of its similar samples . Weights and samples $x_i$ and $x_j$ Is directly proportional to the similarity . This makes the variation of similar samples smaller .
$$\begin{array}{c}{\hat{K}}_X=\left[\begin{array}{cc}{K}_{X_{tr}{X}_{tr}}& {\hat{K}}_{X_{tr}{X}_{ts}}\\ {\hat{K}}_{X_{ts}{X}_{tr}}& K_{X_{ts}{X}_{ts}}\end{array}\right]\end{array}$$

3、 ... and 、 experimental result

This paper compares this method with MMDE and CODA Made a comparison .

3.1 The kernel of the response variable

So in ACA Middle core $K_X$ It has been revised to ${\hat{K}}_X$
Will nucleus $K_{Y_{t}r}And{K}_{X_{ts}{X}_{tr}}and{K}_{X_{tr}{X}_{ts}}$ Multiply , Basically, each sample of the training data set is replaced by the weighted mean of its corresponding similar samples , Make the data change less along similar samples .

3.2 Examples of toy classification

Training data set and test data set are composed of 100 and 200 Sample composition , They come from multivariate normal distribution , The mean values are ${\mu }_{tr}=(-1,3)$ and ${\mu }_{ts}=(2,1)$, Their covariance matrix is similar ,$\sigma =\left[\begin{array}{cc}2& 0.5\\ 0.5& 2\end{array}\right]$
Training data sets and test data sets are divided into two categories . If the first eigenvalue of each set is less than its corresponding mean , Then the samples of this set belong to the first class , If its first eigenvalue is greater than its corresponding mean , Then the samples of this set belong to the second class .

chart 1-a It shows the data in the original feature space
chart 1-b To adopt ACA Embedded data of Algorithm
◦ and × There are two kinds of training data sets
$◊$ and * There are two types of test data sets
It can be seen that , The distance between the embedded training data set distribution and the test data set distribution is reduced .
therefore , The new training data sample can better represent the test data set for classification .
utilize 1-NN Classify the original data unchanged , And take the error rate as the baseline .
ACA The algorithm provides a significant improvement in the error rate of the classification process .

3.3 Real world data sets

3.3.1MNIST Handwritten numerals

The first data set is a collection of images , yes MNIST Handwritten numerals .
The definition of domain adaptation problem is : The classifier trains on two digits of the training set , And test on two different numbers in the test set .
surface 2 The training samples of all data sets in are 300 individual , The test sample is 500 individual
Through all the experiments in this paper , take ACA The dimension of the output data in is set to 2.
The error rates of different algorithms are shown in table 2 Shown ：

Dig-1 New representation in two-dimensional space , Its classification effect is obviously better ：

3.3.2 Newsgroup datasets

The second database is 20 Newsgroup datasets , By about 20,000 Newsgroup text documents , These documents are divided into four groups according to similar topics .
Generate 3 Data sets , among “Newsgroup-1” Data sets consist of groups 1 And groups 2 Randomly selected from 1000 Post as training data set , Group 3 And groups 4 Randomly selected from 2000 Posts as a test data set .
The error rate is 10 Average error rate of tests , The samples of each trial were randomly selected from the original data set .
ACA Better than other methods , Except in the second database Newsgroup-2.
Wine, German Credit, India diabetes and Ionosphere yes UCI Archived datasets , Their “ Offset ratio ” It is defined as 80%.

3.3.3 Breast cancer datasets

The data includes 699 Benign ( Positive label ) And malign ( Negative label ) sample .
This is a base 9 Binary classification of initial features .
The bias ratio is 70%、80%、90% Repeat the experiment .

Another parameter that shows the efficiency of the method is Normalization improvement (NI), It quantifies the algorithm a Relative to the algorithm B How good is the performance of . This parameter is estimated as ：
$$NI=\frac{|Erro{r}_A-Erro{r}_B|}{Erro{r}_A}$$
ACA It can also be considered as a dimension reduction technology

---

summary

We propose a domain adaptation algorithm , The algorithm transfers data samples to a new feature space . Explore new data representation , Make the training data set and the test data set as close as possible in the new feature space , At the same time, important structural information of data is preserved . In order to solve this problem and meet the above properties , We define a fast optimization problem , Its solution is known as the eigenvector of the given matrix . Experimental results show that , The algorithm has good performance in practical application , It has good efficiency in the case of low dimension , It can be used as a dimension reduction technology .

References

1. Adapting Component Analysis