Title: DOMAIN ADAPTATION VIA LOW-RANK BASIS AP-PROXIMATION

Abstract: Domain adaptation focuses on the reuse of supervised learning models in a new context. Prominent applications can be found in robotics, image processing or web mining. In these areas, learning scenarios change by nature, but often remain related and motivate the reuse of existing supervised models. While the majority of symmetric and asymmetric domain adaptation algorithms utilize all available source and target domain data, we show that efficient domain adaptation requires only a substantially smaller subset from both domains. This makes it more suitable for real-world scenarios where target domain data is rare. The presented approach finds a target subspace representation for source and target data to address domain differences by orthogonal basis transfer. By employing a low-rank approximation, the approach remains low in computational time. The presented idea is evaluated in typical domain adaptation tasks with standard benchmark data.

1. INTRODUCTION:

Supervised learning and in particular classification is an essential task in machine learning with a broad range of applications. The obtained models are used to predict the label of unseen test samples. A basic assumption in supervised learning is that the underlying domain or distribution is not changing between training and test samples. If the domain is changing from one task to a related but different task, one would like to reuse the available learning model. Domain differences are quite common in real-world scenarios and eventually, lead to substantial performance drops (Weiss et al., 2016) . A domain adaptation example is the classification of web pages. A classifier is trained in the domain of university web pages with a word distribution according to universities. In the test scenario, the domain has changed to non-university web pages, where the word distribution is related, but may not be similar to the training distribution. More formally, let Z = {z 1 , . . . , z m } ∈ R d be source data sampled from the source domain distribution p(z) and let X = {x 1 , . . . , x n } ∈ R d be target data from the target domain distribution p(x). Traditional machine learning assumes similar distributions, i.e. p(z) ∼ p(x), but domain adaptation assumes different distributions, i.e. p(z) = p(x) and appears in the web page example where Z could be data of university websites and X are data of non-university websites. Multiple domain adaptation techniques have been already proposed, following different strategies and improving the prediction performance of underlying classification algorithms in test scenarios (Weiss et al., 2016; Pan & Yang, 2010) . The common domain adaptation approach requires a large number of source or target samples, which is indeed a disadvantage of many domain adaptation approaches and is not guaranteed in restricted environments where labeling is expensive (Weiss et al., 2016) . Further, learning a matrix for the alignment of domain distributions does not necessarily lead to effective adaptation shown by (Raab & Schleif, 2018) , where domain differences are explicitly solved by overriding the basis of one domain with another and is competitive to current state of the art domain adaptation algorithms (Gong et al., 2012; Long et al., 2015; 2013; Pan et al., 2011; Fernando et al., 2013; Sun et al., 2016) .

The main contribution of this work is to improve the Basis-Transfer (Raab & Schleif, 2018) approach by deriving a more simplified closed-form solution of the least-squares problem and enhance this by a Nyström based dimensionality reduction. The resulting method has a better prediction performance and makes it easer to apply. Further, it is the fastest domain adaptation algorithm in terms of computational complexity, while maintaining its excellent performance by using only a subset of source and target data. It determines a target subspace representation for both domains and transfers target basis information to source data via Nyström Singular Value Decomposition (SVD) with class-wise sampling. Further, we show that Nyström approximation is well suited for nonsquare landmark matrices, in contrast to common decomposition (Nemtsov et al., 2016) by applying post-processing.

The rest of the paper is organized as follows: We give an overview of related work in section 2. The underlying mathematical concepts are given in section 3. The proposed approach is discussed in section 4, followed by an experimental part in section 5, addressing the classification performance and computational time. A summary with a discussion of open issues is provided in the conclusion at the end of the paper. More detailed derivations, description of experiments, implementation details and additional results can be found in the appendix.

2. RELATED WORK:

In general, homogeneous transfer learning (Weiss et al., 2016) approaches, or domain adaptation (DA), distinguish roughly between the following strategies: Methods implementing the symmetric feature adaptation (Weiss et al., 2016) are trying to find a common latent subspace for source and target domain to reduce marginal distribution differences, such that the underlying structure of the data is preserved in the subspace. A baseline approach for symmetric feature adaptation is the Transfer Component Analysis (TCA) (Pan et al., 2011) . TCA finds a suitable subspace transformation called transfer components via minimizing the Maximum Mean Discrepancy (MMD) in the Reproducing Kernel Hilbert Space (RKHS). The Geodesic Flow Kernel (GFK) finds a particular subspace by embedding original data onto a Grassmannian manifold, matches source and target on the geodesic flow and determines a suitable domain adaptation kernel by applying the kernel trick (Gong et al., 2012) . The relational-knowledge adaptation aims to find some relationship between source and target data (Weiss et al., 2016) . Transfer Kernel Learning (TKL) (Long et al., 2015) is a recent approach, which approximates a kernel of training data K(Z) by test kernel K(X) via the Nyström kernel approximation.

However, recent studies conclude that the asymmetric transformation of source data is a promising approach in domain adaptation due to the better classification performance (Sun et al., 2016; Fernando et al., 2016; Raab & Schleif, 2018; Long et al., 2013) . Possibly, because a classifier is trained on the source label information in the target domain (Sun et al., 2016) . The good performance has led to a variety of unsupervised asymmetric domain adaptation algorithms (Elhadji-Ille-Gado et al., 2017; Shao et al., 2014; Blitzer et al., 2011; Thopalli et al., 2019) , to name a few. The asymmetric feature adaptation approaches try to transform source domain data in the target (subspace) domain to match the source to target subspace and is most related to our work. In comparison to the symmetric feature adaptation approaches, there is no shared subspace, but only the target space (Weiss et al., 2016) . The Joint Distribution Adaptation (JDA) (Long et al., 2013) solves divergences in marginal distributions similar to TCA, but aligning conditional distributions with pseudo-labeling techniques. The Subspace Alignment (SA) (Fernando et al., 2013) computes a target subspace representation based on the correlation between target and source subspace projectors and hence aligning source and target data. The Correlation Alignment (CORAL) (Sun et al., 2016) technique transfers secondorder statistics of the target domain into whitened source data. Given these methods, there is an overall trend in domain adaptation in the direction of non-linear problem formulations, indirect alignment of matrix differences and learning a suitable subspace for the source domain in the target domain and have similar problem statements to ours. However, in this work, we do not learn a suitable source subspace transformation, but explicitly override the structural information of source domain with the target one. With this, we model the source subspace domain as part of the target subspace. The considered domain adaptation methods have approximately a complexity of O(n 2 ) where n is the most significant number of samples concerning target or source. These algorithms pursue transductive adaptation (Pan & Yang, 2010) , because some unlabeled test data must be available at training time. These transfer-solutions cannot be directly used as predictors, but instead, are wrappers for classification algorithms. The respectively used baseline classifier is the Support Vector Machine (SVM).

3. PRELIMINARIES:

We introduce the basics of the Nyström kernel approximation in section 3.1, which is the foundation of the Nyström based Singular Value Decomposition in section 3.2. The Nyström-SVD is used for creating the subspace transformation of Nyström Basis Transfer in section 4.1.

3.1. NYSTR ÖM APPROXIMATION:

The computational complexity of calculating kernels or eigensystems scales with O(n 3 ) where n is the sample size (Williams & Seeger, 2001) . Therefore, low-rank approximations and dimensionality reduction of data matrices are popular methods to get a better computational performance. In this scope, however not limited to it, the Nyström approximation (Williams & Seeger, 2001 ) is a reliable technique to accelerate eigendecomposition or approximation of general symmetric matrices (Gisbrecht & Schleif, 2015) . It computes an approximated set of eigenvectors and values based on a usually much smaller sample matrix. The landmarks are typically picked at random, but advanced sampling concepts could be used as well (Talwalkar et al., 2012) . The approximation is exact if the sample size is equal to the rank of the original matrix and the rows of the sample matrix are linear independent (Gisbrecht & Schleif, 2015) . In general, the Nyström approximation technique assumes a symmetric matrix K ∈ R n×n with a decomposition of the form

EQUATION

with -s) . The submatrix A is called the landmark matrix containing s randomly chosen rows and columns from K and has the Eigenvalue Decomposition (EVD) A = UΛU -1 . Where eigenvectors are U ∈ R s×s and eigenvalues are on the diagonal of Λ ∈ R s×s . The remaining approximated eigenvectors Û of K as the part C or B T , are obtained by the Nyström method with ÛΛ = CU. Combining U and Û the full approximated eigenvectors of K are

A ∈ R s×s , B ∈ R s×(n-s) , C ∈ R (n-s)×s and D ∈ R (n-s)×(n

Ũ = U Û = U CUΛ -1 ∈ R n×s .

(2)

The right part of the EVD ( Ũ-1 ) of K can be obtained via Nyström similar to equation 2 by

EQUATION

Combining equation 2, equation 3 and Λ, the matrix K is approximated by

EQUATION

The Nyström approximation error is given by the Frobenius Norm between ground truth and reconstructed matrices, i. e. E ny = || K -K|| F , with bounds proven by Gittens & Mahoney (2013) .

3.2. GENERAL MATRIX APPROXIMATION:

Another application of the Nyström method is the approximation of the Singular Value Decomposition, which generalizes the concept of matrix decomposition with the consequence that respective matrices must not be squared. Let K ∈ R n×d be a rectangular matrix with the decomposition as in equation 1. The SVD of the landmark matrix is given by A = LSR T where L are left and R are right singular vectors. S are positive singular values. The left and right singular vectors for the non-symmetric part C and B are obtained via Nyström techniques and are defined as L = CRS -1 and R = B T LS -1 respectively (Nemtsov et al., 2016) .

Applying the same principal as for Nyström-EVD, K is approximated by

K = LS RT = L L S R R = L CRS -1 S R S -1 L T B .

(5)

3.3. POLAR DECOMPOSITION:

The Polar decomposition (Higham, 2005) theorem is used to validate the proposed subspace transformations as PCA transformations in section 4 and the class-wise sampling strategy in section 4.2.

It is a universal decomposition applicable to an arbitrary matrix and is defined as X = QP. Where Q = LR T and P = RSR T with S as singular values, L and R are left and right singular vectors respectively. If X is a square matrix, the decomposition is unique and U is orthogonal and a rotation matrix. P is positive semi-definite and contains the scaling factors of X.

Theorem 1 (Reusing of Eigensystem). Let X ∈ R n×d and K = XX T with EVD of K = UΛU -1 and Singular Value Decomposition (SVD) of K = LSR T . Taking the square root of K and using the Polar Decomposition with

EQUATION

then the eigenvectors and square root eigenvalues of K are singular vectors and values of X respectively.

3.4. GERSCHGORIN THEOREM:

The Gerschgorin theorem (Varga, 2004) provides a geometric structure to bound eigenvalues to socalled discs for complex square matrices, but also generalize to none complex square matrices. The work of Qi (1984) expands the Gerschgorin circles to so-called Gerschgorin type circles for singular values:

Theorem 2 (Gerschgorin Type Bound for Singular Values (Qi, 1984) ). Given the matrix X ∈ R n×d with n, d ≥ 1, the singular values {s i } n i=1 of X are in the range of

EQUATION

Where p i = |x ii | and the range r i is defined as

EQUATION

By this, it is possible to estimate the numerical range of singular values of X and is used in the error bound given in section 4.3.

4. BASIS TRANSFER:

The task of domain adaptation is to align distribution differences. That means that underlying statistics will be similar afterwards. The key idea of the approach presented in the following is that explicit alignment of data matrices without any knowledge of statistics and distribution of data is possible and successful. It is based on the work of Schölkopf et al. (1998) , which proposed that if two kernel matrices are similar, they follow similar distributions. Hence, we make the domain data as similar as possible by overriding the syntactic structure, which will result in similar kernels. This also applies to arbitrary rectangular data matrices of a linear kernel, because it can be reconstructed by using theorem 1. Hence, the method is also applicable in the original feature space without requiring a positive semi definite kernel.

The recent Basis-Transfer (BT) (Raab & Schleif, 2018) approach already showed great transfer capabilities and performance by aligning X ∈ R n×d and Z ∈ R m×d with a small error in terms of the Frobenius norm. However, this required equal samples sizes n = m. In BT, the following optimization problem was considered:

EQUATION

Where M and T are transformation matrices, drawing the source (Z) closer to target (X) data. A solution of equation 9 is found in closed-form, summarized in three steps (Raab & Schleif, 2018) : First, normalize data to standard mean and variance. It is assumed that this will align marginal distributions in Euclidean space without considering label information (Raab & Schleif, 2018) . Second, compute an SVD of source and target data, i. e.

Z = L Z S Z R T Z with L Z ∈ R m×m and R Z ∈ R d×d . And X = L X S X R T X with L X ∈ R n×n and R X ∈ R d×d .

Note that we denote Z / X as source/target related matrix respectively. Next, the approach assumes S Z ∼ S X in terms of the Frobenius norm due to similar domains providing similar scaling factors by singular values and normalization. Finally, compute a solution for equation 9 by solving the linear equations. One obtains

M = L X L -1 Z and T = R -1 Z R T X . Note that L Z L -1 Z = R Z R -1 Z = I.

Finally, a transfer operation is applied such that the source matrix is approximated by using the available target information by

EQUATION

With Z ∈ R m×d as approximated source data, used for training.

In the following, the work (Raab & Schleif, 2018) is hereby substantially improved and we propose a Nyström based version with following improvements: Reduction of computational complexity, neglecting sample size requirements and achieve a low-rank projection via Nyström approximation with class-wise sampling and implicit dimensionality reduction.

Recap equation 9 and consider the slightly changed optimization problem

EQUATION

)

Where a transformation matrix M must be found, which is again obtained in closed-form. Note this is a transfer learning interpretation of the orthogonal procrustes problem (Schönemann, 1966) .

Because we apply a dimensionality reduction technique, just the left-sided transformation matrix must be determined, derived as follows: Based on the relationship between SVD and EVD, the Principal Component Analysis (PCA) can be rewritten in terms of SVD. Consider the target matrix with SVD:

X T X = (R X S X L T X )(L X S X R T X ) = R X S 2 X R T X .

(12) Where R X ∈ R d×s as eigenvectors and S 2 X ∈ R s×s as eigenvalues of X T X. By choosing only the biggest s eigenvalues and corresponding eigenvectors the dimensionality of X is reduced by

EQUATION

With L s ∈ R n×s , S s ∈ R s×s . X s ∈ R n×s is the reduced target matrix. Hence, only a left sided transformation in equation 11 is required, because the right sided transformation is omitted in equation 13. Note, that for equation 12 a linear covariance or kernel is used. However, this procedure requires a complete data matrix or corresponding singular values and scales the in worst case with O(n 3 ) (Williams & Seeger, 2001 ). In the following, we apply Nyström-SVD and show that only a subset of the data is required, which simultaneously reduces computational complexity and eliminates the need to examine all singular values.

4.1. NYSTR ÖM BASIS TRANSFER:

Let Z and X have a valid decomposition given as in equation 1. Note for clarity the Nyström notation is used as in section 3.2. For a Nyström-SVD we sample from both matrices s values obtaining landmarks matrices

A Z = L Z S Z R T Z ∈ R s×s and A X = L X S X R T X ∈ R s×s .

Based on Nyström-SVD in equation 5, the dimensions are reduced as in equation 13 keeping only most relevant data structures

EQUATION

)

Hence, it is sufficient to only compute a SVD of A X instead of X with s m, d and therefore is considerably lower in computational complexity. Analogy, we approximate source data by Z s = LZ S Z ∈ R n×s . Since we again assume S Z ∼ S x due to data normalization and domain similarities, solving the linear equation as a possible solution for equation 11, leads to M = LX L-1 Z . Plugging it back we obtain

Z s = LX L-1 Z LZ S Z = LX S Z ∈ R n×s .

(15) Where again a basis of a target subspace transfers structural information into the source domain. The matrix Z s is used for training and X s is used for testing. We showed in equation 13, that equation 14 and equation 15 are valid PCA transformations. By definition of SVD follows LZ LT Z = LX L-1 X = I and LX is an orthogonal basis. Therefore, equation 14 and equation 15 are orthogonal transformations. In particular, equation 15 transforms the source data into the target subspace and projects it onto the principal components of X. If data matrices X and Z are standardized1 , the geometric interpretation is a rotation of source data w.r.t to angles of the target basis. The relationship between BT and NBT is in the number of samples s used by Nyström. If the rank of the data matrices is equal to s the approximation is exact and it became a subspace version of BT.

According to (Weiss et al., 2016) , it is an asymmetric transfer approach. Further, it is transductive (Pan & Yang, 2010) , where unlabeled target data is needed at training time. Subsequently this approach is denoted as Nyström Basis Transfer (NBT). But uniform sampling may not be optimal for Nyström, given labeled data in a classification task (Schleif et al., 2018) . Therefore, we integrate class-wise sampling in the following.

4.2. SAMPLING STRATEGY FOR NYSTR ÖM:

The standard technique to create Nyström landmark matrices is to sample uniform or find clusters in the data matrix (Talwalkar et al., 2012) . In supervised learning, sampling should utilize classwise sampling to properly include class-depending attributes of a matrix into the approximation (Schleif et al., 2018) . This is especially necessary for ||Y|| > 2. However, a decomposition as in equation 1, required for Nyström-SVD is intractable with class-wise sampling, because respective matrices are non-square: Let Z ∈ R m×d with m = d and landmark indices I = {i 1 , . . . , i s } with at least one i j > d, then it is by definition undefined and is especially true for n > d. Therefore, we sample rows class-wise forming

A d Z ∈ R s×d instead of A Z ∈ R s×s .

Using the insights of theorem 1, we implicitly obtain an SVD of a square landmark matrix, i. e.

A d Z A dT Z = K d Z ∈ R s×s by computing A d Z = L Z S d Z R T Z .

Hence, we can proceed without a non-square landmark matrix and using the SVD of A d Z analogy as in equation 15. Therefore, it is possible to sample from the whole range of source data and by application of the Polar decomposition, the standard decomposition as in equation 1 is not required. The resulting singular values and vectors are utilized for successive Nyström approximations. The sampling from test data X is done uniformly row-wise, because of missing class information and SVD is obtained analogy via A d X = L X S d X R T X and used in equation 14. However, the possible range of singular values of A d Z is naturally not equal to A Z . Utilizing theorem 2 it is easy to show that S d Z = S Z . It scales approximated matrices Z s (equation 15) different through S d Z and accurate normalization of matrix cannot be guaranteed. Therefore, we apply a postprocessing correction and apply z-normalization against the standard convention after NBT. The singular vectors also have an approximation error. However, both subspace projections are based on the same transformation matrix, hence making an identical error and as a result, the error should not affect the classification. The process is given in the figure 2 (appendix A.2) and showing the alignment of source to the target domain. Further, it shows the mechanics of the approach: The structural similarities stay the same, while the scaling is changed leading to a high similarity after the post-processing correction.

4.3. PROPERTIES OF NYSTR ÖM BASIS TRANSFER:

The computational complexity of Nyström Basis Transfer (NBT) is composed of economy-size SVD of landmark matrices A d Z and A d X with complexity O(2s 2 ). The matrix inversion of diagonal matrix S d X -1 in equation 14 can be neglected. Remaining k matrix multiplications are O(ks 2 ) contributing to the overall complexity of NBT which is O(s 2 ) with s n, m, d. This makes NBT the fastest domain adaptation solution in terms of computational complexity in comparison to discussed methods in section 2. The difference between source and target domain after NBT, i.e. approximation error of source by target domain is bounded by

EQUATION

)

Where || LX || ≤ √ n is the bounding of the normalized singular vectors and D (•) is the maximum sum of the s singular values obtained by the numerical estimation, given in theorem 2, of X s and Z s respectively. The equation 16 shows that NBT has a lower norm compared to BT or original data and proofs that the matrices are aligned during NBT, reducing the distribution differences. The respective proof is given in appendix A.1. The out-of-sample extension for unseen target/source samples, e. g. x ∈ R d , is analog to equation 14. Based on equation 13 a subspace projection via (approximated) right singular vectors is also valid. Hence, a sample can be projected into the subspace via x s = x RT X = x R X S d X -1 L T B X and be evaluated by an arbitrary classifier learned in the subspace. The pseudo code of NBT is shown in Algorithm 1.

Algorithm 1 Nyström Basis Transfer (NBT) Require: Z as m sized training; X as n sized test set; Y as m sized training label vector; s as number of landmarks parameter. Ensure: New Source Z s ; new Target X s ;

1: A d X , A d Z , C X = matrix decomposition(X,Z,s) According to section 4.2 2: S d Z = SV D(A d Z ); SVD of landmark matrix of Z 3: L X , S d X , R X = SV D(A d X ); SVD of landmark matrix of X 4: LX = L X C X R X S d X -1 T

According to equation 14 

5. EXPERIMENTS:

We follow the experimental design typical for domain adaptation algorithms (Long et al., 2015; Gong et al., 2012; Long et al., 2013; Pan & Yang, 2010; Pan et al., 2011; Sun et al., 2016; Mahadevan et al., 2019; Fernando et al., 2013) . A crucial characteristic of datasets for domain adaptation is that domains for training and testing are different but related. This relation exists because the train and test classes have the same top category or source. The classes itself are subcategories or subsets.

The parameters for respective methods2 are determined for best performance in terms of accuracy via grid search. A detailed description of experiments can be found in appendix A.4. In the experiments, the SVM independent of being a baseline or underlying classifier for domain adaptation methods uses the RBF-Kernel. The tests are conducted on the datasets groups Reuters, Newsgroup and Office-Caltech. A detailed dataset description is given in appendix A.3.

5.1. PERFORMANCE COMPARISON:

The experiments are cumulated as three dataset group, which are Reuters, Newsgroup and Office-Caltech. The results are summarized in table 1 . It shows the mean errors of the experiments per dataset group. To determine statistically significant differences, the two-sided Kolmogorov-Smirnoff-Test with a p-value of 1% is applied. The * marks statistical significance compared to NBT. The NBT is compared to baseline SVM and standard domain adaptation methods. The NBT and BT methods have excellent performance and outperform every other algorithm by far and are overall similar. Looking at the datasets individually, the only competitive approach is SA, however, in the overall rating, all non-BT methods are statistically worse. Note that BT and NBT are very similar at Office-Caltech, this is caused because within NBT the rank r of a given image data matrices is equal to the number of samples drawn by the Nyström approximation. Hence, the approximation is exact and we use the most important r singular vectors and values. BT and NBT are overall much better than remaining approaches, caused by following possible reasons: Aligning differences of Frobenius norm between domains using a target (subspace)-transformation is sufficient as a problem statement and overriding of source basis is a successful approach. Further, by Schölkopf et al. (1998) it will also align differences in subsequent kernels. Explicit integration of non-linearity or kernel statistic alignments does not necessarily lead to more knowledge transfer. But, second-order statistics but also structural and geometric information should be transferred. * marks statistical differences with a p-value of 1% against NBT. The standard deviation was omitted, since it is the same for all and on average around 2-3%.

The sensitivity of the number of landmarks on prediction error as the only parameter of NBT is demonstrated in figure 1 . It shows a comparison of the number of landmarks and the mean classification error over Reuters and Office-Caltech datasets. At Reuters, it is a monotonically decreasing convex function with decreasing error by increasing the number of landmarks. This supports the Nyström error expectation of approximating the real rank of a matrix. However, the image function has many local minima. We assume this indicates that only a subset of features is relevant and correlate for classification and remaining features are noise. A time comparison is given in the appendix A.5 showing that our NBT approach is the overall fastest domain adaptation approach.

6. CONCLUSION:

We proposed a low-rank domain approximation algorithm called Nyström Basis Transfer. It transfers source and target data into the target subspace, requiring only a subset of domain data from both domains. The dimensionality reduction, paired with smart class-wise sampling showed its reliability and robustness in this study. Validated on common domain adaptation tasks and data, it showed an outstanding performance both in absolute and statistical values. Additionally, it is lowest in computational complexity compared to discussed solutions. NBT is an extension of earlier versions of Basis Transfer via Nyström Methods and is a low-rank and fast domain adaption solution.

In future work, deep transfer learning, real-world and other domain adaptation datasets should be considered. A more comprehensive discussion of the Nyström approximation error with the proposed decomposition should be theoretically evaluated and compared to current Nyström techniques.

A APPENDIX:

A.1 NORM BOUND OF NYSTR ÖM BASIS TRANSFER This section discusses the approximation error of Nyström Basis Transfer in terms of the Frobenius norm of the matrix difference shown in equation 16. First, we clarify some definitions used in the subsequent theorem. In this work, we define the Frobenius norm of a matrix X ∈ R n×d as

X F = n i=1 d j=1 |x ij | 2

. By using theorem 2 we can bound the norm of the singular values S F of X by the square root of the squared sum of the numerical range given by

EQUATION

)

Finally, we assume that the non-zero singular vectors are normalized and have by definition unit length. Therefore, the norm of a singular vector matrix with n singular vectors can be bounded by √ n.

Theorem 3. Given two rectangular matrices X, Z ∈ R n×d with n, d > 1 and rank(X), rank(Z) > 1. The norm Z s -X s F in the subspace R s induced by normalized singular vectors L ∈ R n×s is bounded by

EQUATION

Proof. We start by proofing the first part given by Z s -X s F ≤ √ n||D s X -D s Z ||. Using equation 14, equation 15 and equation 16 the respective term can be rewritten in terms of a SVD-PCA using only the biggest s singular values. Further, substituting

M = L X L -1 Z leads to Z s -X s F = MZ -X s F = L X L -1 Z L Z S Z -L X S X F = L X S Z -L X S X F . (19)

Where we assume 1 ≤ s < n. This can be simplified applying the Cauchy-Schwarz inequality twice with

L X S Z -L X S X F ≤ L X F S Z -S X F ≤ L X F ( S Z F -S X F ).

(20) The norm of the singular values S Z , S X ∈ R s×s can be bounded by equation 17 resulting in

EQUATION

)

Where p z i and r z i are the bound of a singular value of Z s and p x i and r x i are the bound of a singular value of X s . Further, the singular vectors L X are normalized and thus can be bounded by L X F ≤ √ n. Applying both to equation 20 leads to

EQUATION

The second term

√ n||D s X -D s Z || < Z -X F is obtained analogy. Given the SVD of the original matrices we obtain Z -X F = L Z S Z R Z -L X S X R X F .

(23) By again using the Cauchy-Schwarz inequality we obtain

EQUATION

)

Because L Z and L X have the same size they are bounded by √ n and because R Z , R X ∈ R d×d and are also normalized, the norm can be bounded by R (•) ≤ √ d respectively. Because we are not in the subspace R s but R d with s < d and the singular values are S Z , S X ∈ R n×d the numerical bound becomes

EQUATION

)

Applying the bounds to equation 24 we obtain

EQUATION

Simplifying this term further leads to

EQUATION

)

Because we assume d > 1 and a minimum of one non-zero singular vector in R (•) this at least

EQUATION

)

The result from the above allows the conclusion that the norm of the subspace matrices is smaller than the norm of the original matrices. Note that because BT (Raab & Schleif, 2018) is applied in R d , this allows the conclusion that E N BT < E BT . If the norm of the difference of two matrices is small, they are similar and if they are numerically similar, we can conclude that the distributions are also similar (Song & Park, 2018) . Finally, this is the reason why NBT aligns the distribution of two given matrices. However, note that similar distributions not necessarily means a good classification performance in terms of accuracy by an arbitrary classifier in a transfer learning setting.

A.2 PROCESS OF NYSTR ÖM BASIS TRANSFER:

In this section, an illustration of Nyström Basis Transfer (NBT) is given. Figure 2 shows the process of Nyström Basis Transfer. The first row shows the samples of Nyström to create the approximated set of subspace projectors. The second row shows the data after the subspace projection. The similarity in structure but dissimilarity in scaling, as discussed in section 4.3 is visible. The last row shows the data after applying post projection and the difference is not visible anymore.

A.3 DATASET DESCRIPTION:

The study consists of 24 benchmark datasets, already preprocessed and taken from (Gong et al., 2012) , (Long et al., 2015) and (Long et al., 2014) .

Reuters-215784 (Long et al., 2015) : A collection of Reuters news-wire articles collected in 1987.

The text is converted to lower case, words are stemmed and stopwords are removed. With the Document Frequency (DF)-Threshold of 3, the numbers of features are cut down. Finally, Term-Frequency Inverse-Document-Frequency (TFIDF) is applied for feature generation (Dai et al., 2007) .

The three top categories organization (orgs), places and people are used in our experiment.

To create a transfer problem, a classifier is not tested with the same categories as it is trained on, i. g. it is trained on some subcategories of organization and people and tested on others. Therefore, six datasets are generated: orgs vs. places, orgs vs. people, people vs. places, places vs. orgs, people vs. places and places vs. people. (Long et al., 2015) .

Caltech-256-Office6 (Gong et al., 2012) : The first, Caltech (C) is an extensive dataset of images and contains 30.607 images within 257 categories. The Office dataset is a collection of images drawn from three sources which are from amazon (A), digital SLR camera (DSLR) and webcam (W). They vary regarding camera, light situation and size, but ten similar object classes, e. g. computer or printer, are extracted for a classification task. Duplicates are removed, as well as images which have more than 15 similar Scale Invariant Feature Transform (SIFT) in common (Gong et al., 2012) .

The final feature extraction is done with Speeded Up Robust Features Extraction (SURF) and encoded with 800-bin histograms. Finally, the twelve sets are designed to be trained and tested against each other by the ten labels (Gong et al., 2012) .

Note to reproduce the results of this paper, one should use the linked version of datasets with the same choice of subcategories. A summary of all datasets is shown in table 2. Regardless of the dataset, data have been standardized to standard mean and variance. The experiments are summarized as the mean over 20 runs with a 2-fold sampling, with separated samplings for source and target data.

A.4 IMPLEMENTATION DETAILS:

The parameters for the respective domain adaptation algorithms are obtained via grid-search for best performance on a dataset type, meaning text with Reuters and Newsgroup and image with Office vs Caltech. All algorithms using the SVM with an RBF-Kernel, except GFK which suggest a k nearest neighbor classifier. The C parameter of the SVM is set to 10 for all experiments. For SVM the LibSVM is used. The TCA also has one parameter which gives the subspace dimensions and is set to µ = 50 for both datasets. The JDA has two model parameters. First, the number of subspace bases k, which is set to 100. Second, the regularization parameter λ is set to 1 for both sets.

The TKL approach has the eigenvalue dumping factor ξ as a parameter, which was set to 2 for the text datasets and 1.1 for the image datasets. For the GFK solution, the parameter, number of subspace dimensions is set to 20 for image and 40 for text data. The SA subspace dimension parameter d is set to 5 for every dataset. The CORAL has no free parameters and CGCA is not evaluated, because of numerical issues. The BT approach has no free parameter and for NBT, the subspace dimension is set to 500 for text and 210 for images.

A.5 TIME COMPARISON:

The mean time results in seconds of the cross-validation study per data set group are shown in the table 3 . Note that SVM is the underlying classifier for the compared approaches and is presented for the baseline and not listed for stand-alone comparison but included into the time measurement of domain adaptation approaches. In the overall comparison, NBT is the fastest compared to the discussed solutions and in contrast to BT, the required time is a magnitude smaller, especially at Newsgroup, which is a high dimensional dataset. This is an expected effect due to Nyström approximation. Individually, the NBT is the fastest algorithm at the Newsgroup and Office-Caltech data set. At Reuters, JDA is the fastest. In summary, the differences between the winning algorithm and other algorithms are very small. However, GFK and CORAL are the slowest methods with a factor of at least 90 compared to the fastest approach for Newsgroup and are clear outliers in this time comparison.

A 

:

Experimental data are standardized to mean zero and variance one in the preprocessing.

Source code and datasets are hosted at https://github.com/iclr-nbt/nbt.git

We encountered numerical issues at our experiments, therefore the shown results are taken from(Mahadevan et al., 2019) with a similar sampling scheme.

http://www.daviddlewis.com/resources/testcollections/reuters21578

http://qwone.com/ ˜jason/20Newsgroups/

https://people.eecs.berkeley.edu/ ˜jhoffman/domainadapt/#datasets_code

Figures and Tables:

Figure 1: Relationship between number of landmarks and mean classification error over all Reuters datasets, shown in left figure and mean over all Office-Caltech datasets, shown in right figure.

Figure 2: Process of Nyström Basis Transfer with ten landmark samples applied to Caltech vs Amazon image dataset as a surface plot. The left column shows the target and the right column shows source data. The first row shows samples used for creating NBT transformations. The differences are clearly visible. The second row shows the data after transformation. Note the similarities in structure but differences in scale, based on the approximation error of singular values. The last row contains the normalization correction and differences are hardly visible with the bare eye. This is finally used for training and testing. Note that this is a toy example approximation unsuitable for proper classification due to small landmark size, shown in figure 1. Best viewed in color.

Result of experiments as mean error in percent over each dataset group. Bold marks winner.

Table content: <table><tr><td>Dataset</td><td>SVM</td><td>TCA 2011</td><td>JDA 2013</td><td>TKL 2015</td><td>GFK 2012</td><td>SA 2013</td><td>CORAL 2016</td><td>BT 2018</td><td>NBT</td></tr><tr><td>Reuters</td><td colspan="5">32.1 *  31.8 *  33.1 *  23.2 *  35.0 *</td><td>7.6</td><td>35.7 *</td><td>3.5</td><td>1.9</td></tr><tr><td>Newsgroup</td><td colspan="3">17.8 *  14.7  *  17.4 *</td><td>6.7</td><td>22.5 *</td><td>2.3</td><td>28.1  *</td><td>2.6</td><td>2.3</td></tr><tr><td colspan="7">Office-Caltech 55.5  *  51.5  *  51.4  *  49.2  *  55.3  *  68.7  *</td><td>52.6  *</td><td colspan="2">20.7 20.8</td></tr><tr><td colspan="7">Overall Mean 35.1  *  32.7  *  34.0  *  26.4  *  37.6  *  26.2  *</td><td>38.8  *</td><td>8.90</td><td>8.3</td></tr></table>

They are two-class problems with the top categories as the positive and negative class and with subcategories as training and testing examples.20-Newsgroup 5(Long et al., 2014): The original collection has approximately 20.000 text documents from 20 Newsgroups and is nearly equally distributed in 20 subcategories. The top four categories are comp, rec, talk and sci and containing four subcategories each. We follow a data sampling scheme introduced byLong et al. (2015) and generate 216 cross domain datasets based on subcategories: Let C be a top category and {C1, C2, C3, C4} ∈ C are subcategories and analogy K with {K1, K2, K3, K4} ∈ K. Select two subcategories each, e. g. C1, C2, K1 and K2, train a classifier, select another four and test the model on it. The top categories are respective classes. Following this, 36 samplings per top category-combinations are possible, which are in total 216 dataset samplings. This is summarized as mean over all test runs as comp vs rec, comp vs talk, comp vs sci, rec vs sci, rec vs talk and sci vs talk. This version of 20-Newsgroup has 25.804 TF-IDF features within 16.021 documents

Table content: <table/>

Overview of dataset characteristics containing numbers of samples, features and labels. Datasets are categorized into two data types, i. e. text and image. The horizontal line separates the datasets into groups namely Caltech-Office, Newsgroup and Reuters.

Table content: <table><tr><td colspan="2">Office-Caltech Dataset Names</td><td colspan="3">#Samples #Features #Labels</td><td colspan="2">Text Datasets Names</td><td colspan="2">#Samples #Features #Labels</td></tr><tr><td>Caltech (C)</td><td/><td>1123</td><td/><td/><td>Comp</td><td/><td/><td>4857</td></tr><tr><td>Amazon(A) DSLR (D)</td><td/><td>958 295</td><td>800</td><td>10</td><td>Rec Sci</td><td/><td/><td>3968 3946</td><td>25804</td><td>2</td></tr><tr><td>Webcam (W)</td><td/><td>157</td><td/><td/><td>Talk</td><td/><td/><td>3250</td></tr><tr><td/><td/><td/><td/><td/><td>Orgs</td><td/><td/><td>1237</td></tr><tr><td/><td/><td/><td/><td/><td>People</td><td/><td/><td>1208</td><td>4771</td><td>2</td></tr><tr><td/><td/><td/><td/><td/><td>Places</td><td/><td/><td>1016</td></tr><tr><td>Dataset</td><td colspan="2">SVM Baseline</td><td colspan="2">TCA JDA TKL</td><td>GFK</td><td>SA</td><td/><td>CORAL</td><td>BT</td><td>NBT</td></tr><tr><td>Reuters</td><td colspan="2">0.06</td><td colspan="2">0.86 0.36 0.40</td><td>3.11</td><td>0.87</td><td/><td>8.38</td><td>0.94</td><td>0.50</td></tr><tr><td>Newsgroup</td><td colspan="2">1.35</td><td colspan="5">21.39 4.79 2.80 214.40 59.70</td><td>705.77</td><td>34.49 2.64</td></tr><tr><td>Office-Caltech</td><td colspan="2">0.05</td><td colspan="2">0.64 0.45 1.09</td><td>0.38</td><td>0.28</td><td/><td>0.37</td><td>0.20</td><td>0.09</td></tr><tr><td>Overall</td><td colspan="2">0.48</td><td colspan="2">7.51 1.77 1.21</td><td colspan="3">72.54 20.22</td><td>238.38</td><td>11.87 1.08</td></tr></table>

Result of experiments shown in mean time in seconds per dataset group. All considered methods using a baseline classifier, hence the SVM is not compared as standalone solution.

Table content: <table/>

.6 DETAILS OF PREDICTION PERFORMANCE The detailed version of the results of the experiments are shown in table 4. It is an extended version of table 1 of the main paper.

Table content: <table/>

Peer review (iclr2020):
In this work, the authors improve the work (Raab & Schleif, 2018) by (1) reducing the computational complexity, (2) neglecting the sample size requirement, and (3) achieving a low-rank projection through Nystrom approximation. More specifically, the feature dimensionality is reduced by using only s biggest eigenvalues and eigenvectors, and the sample size is coordinated through Nystrom approximation. Class-wise sampling is used for the source, and uniform sampling is used for the target. Experimental studies on three datasets have been done. This paper should be rejected because (1) the paper lacks important latest references on domain adaptation, (2) the paper misuses the notations that makes the paper is not easy to follow, (3) the algorithm is not well justified either by theory or experiments, and (4) the presentation should be further polished. Here are some detailed comments: (1) A lot of recent deep domain adaptation methods are missing. These deep works achieve the state-of-the-art results on many transfer benchmark tasks. Without comparison with them (the paper does not mention any deep works), it is very unconvincing to conclude the paper makes new contributions to the transfer community. (2) In line 2 of page 5, the authors claim that BT assumes S_Z ~ S_X, which is not true. The key idea of BT is to construct new source data using target basis and source eigenvalues. Similarly, the authors make the same claim in section 4.1 for NBT, which is also not valid. (3) The notations in eq. (12) and (13) are very misleading. Eq. (12) follows the notations of the first line in page 5, but in the first line below eq. (12), why R_X in R^{d 	imes s}, S_X^2 in R^{s 	imes s}? I understand that X_s is the low dimensional X, then X_s = XR_s with R_s is the dimensionality reduction matrix whose size is d 	imes s (using biggest s eigenvectors is fine). With this, eq. (13) is incorrect as X should be L_X*S_X*R_X^T, but not L_s*S_s*R_s^T. Moreover, it is also unclear why X is decomposed into product of two matrices in this work, is there any benefit of doing so for transfer purpose? (4) In section 4.1, A_Z and A_X have exactly same form with X and Z, i.e., L_Z*S_Z*R_Z^T and L_X*S_X*R_X^T, please clarify. How eq. (14) X_s = 	ide{L_X}*S_X come from? Is it the same as eq. (13)? (5) The title highlights low-rank, but it is not very clear how low-rank matters in the proposed method. I do not find contents stating the low-rank property of the proposed algorithm in the main technical sections. (6) Regarding section 4.2, what is the benefit of using class-wise sampling for the source? Have you tried to use uniform sampling for both the source and target domains? (7) The bound in eq.(16) is not very meaningful as s << n, m, d. Moreover, I am also not convinced by the claim this reduces the distribution differences, please give more theoretical justifications. (8) Regarding the experimental studies, why not use accuracy as many existing works do? The baselines are all subspace-based papers, and are out-of-the-date. The latest subspace papers, e.g., JGSA and MEDA, should be included. Moreover, deep methods are completely missing, which makes the empirical evaluation much less convincing. The improvements of NBT to BT are very marginal, 0.6. (9) Some typos and unclear points (please further polish the paper): (a) The last sentence of para 2, X and Z should be data, not features/ (b) Para 3, it is unclear what are the implicit alignment and explicit alignment of domain distributions. (c) The first sentence in section 2, it should be homogeneous. (d) Page 5 above eq. (15), it should be S_Z ~ S_X. (e) Section 4.2 the second line, it should be “in the data matrix” (f) The second last line of page 6, it should be inequality (16). (g) Some references miss page information.