Year: 2019

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.

heading: 1 INTRODUCTION
text: 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 = {z1, . . . , zm} ∈ Rd be source data sampled from the source domain distribution p(z) and let X = {x1, . . . ,xn} ∈ Rd 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) 6= 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 Nyströ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 Nyström Singular Value Decomposition (SVD) with class-wise sampling. Further, we show that Nyströ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.

heading: 2 RELATED WORK
text: 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 Nyströ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(n2) 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).

heading: 3 PRELIMINARIES
text: We introduce the basics of the Nyström kernel approximation in section 3.1, which is the foundation of the Nyström based Singular Value Decomposition in section 3.2. The Nyström-SVD is used for creating the subspace transformation of Nyström Basis Transfer in section 4.1.

heading: 3.1 NYSTRÖM APPROXIMATION
text: The computational complexity of calculating kernels or eigensystems scales with O(n3) 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 Nyströ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 Nyström approximation technique assumes a symmetric matrix K ∈ Rn×n with a decomposition of the form
K = [ A B C D ] , (1)
with A ∈ Rs×s, B ∈ Rs×(n−s), C ∈ R(n−s)×s and D ∈ R(n−s)×(n−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 ∈ Rs×s and eigenvalues are on the diagonal of Λ ∈ Rs×s. The remaining approximated eigenvectors Û of K as the part C or BT , are obtained by the Nyström method with ÛΛ = CU. Combining U and Û the full approximated eigenvectors of K are
Ũ =
[ U
Û
] = [ U
CUΛ−1
] ∈ Rn×s. (2)
The right part of the EVD (Ũ−1) of K can be obtained via Nyström similar to equation 2 by Ṽ = [ U−1 Λ−1U−1B ] . (3)
Combining equation 2, equation 3 and Λ, the matrix K is approximated by
K̃ = ŨΛṼ =
[ U
CUΛ−1
] Λ [ U−1 Λ−1U−1B ] . (4)
The Nyström approximation error is given by the Frobenius Norm between ground truth and reconstructed matrices, i. e. Eny = ||K̃−K||F , with bounds proven by Gittens & Mahoney (2013).

heading: 3.2 GENERAL MATRIX APPROXIMATION
text: Another application of the Nyströ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 ∈ Rn×d be a rectangular matrix with the decomposition as in equation 1. The SVD of the landmark matrix is given by A = LSRT 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 Nyström techniques and are defined as L̂ = CRS−1 and R̂ = BTLS−1 respectively (Nemtsov et al., 2016). Applying the same principal as for Nyström-EVD, K is approximated by
K̃ = L̃SR̃T =
[ L
L̂
] S [ R R̂ ] = [ L
CRS−1
] S [ R S−1LTB ] . (5)

heading: 3.3 POLAR DECOMPOSITION
text: 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 = LRT and P = RSRT 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 ∈ Rn×d and K = XXT with EVD of K = UΛU−1 and Singular Value Decomposition (SVD) of K = LSRT . Taking the square root of K and using the Polar Decomposition with
K 1 2 = (UΛU−1) 1 2 = (QP) 1 2 = (LRTRSRT ) 1 2 = (LSRT ) 1 2 = LS 1 2 RT , (6)
then the eigenvectors and square root eigenvalues of K are singular vectors and values of X respectively.

heading: 3.4 GERSCHGORIN THEOREM
text: 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 ∈ Rn×d with n, d ≥ 1, the singular values {si}ni=1 of X are in the range of
si = {pi ± |ri|}, i = 1, . . . , n. (7) Where pi = |xii| and the range ri is defined as
ri = max
{ d∑
j=1,j 6=i
|xij |, n∑
j=1,j 6=i
|xji| } , i = 1, . . . , n. (8)
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.

heading: 4 BASIS TRANSFER
text: 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 Schö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 ∈ Rn×d and Z ∈ Rm×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:
min M,T ‖MZT−X‖F . (9)
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 = LZSZRTZ with LZ ∈ Rm×m and
RZ ∈ Rd×d. And X = LXSXRTX with LX ∈ Rn×n and RX ∈ Rd×d. Note that we denote Z / X as source/target related matrix respectively. Next, the approach assumes SZ ∼ SX 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 = LXL−1Z and T = R −1 Z R T X . Note that LZL −1 Z = RZR −1 Z = I. Finally, a transfer operation is applied such that the source matrix is approximated by using the available target information by
Z̃ = MZT = LXL −1 Z LZSZRZR −1 Z R T X = LXSZR T X . (10)
With Z̃ ∈ Rm×d as approximated source data, used for training. In the following, the work (Raab & Schleif, 2018) is hereby substantially improved and we propose a Nyström based version with following improvements: Reduction of computational complexity, neglecting sample size requirements and achieve a low-rank projection via Nyström approximation with class-wise sampling and implicit dimensionality reduction. Recap equation 9 and consider the slightly changed optimization problem
min M ||MZ−X||F . (11)
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 (Schö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:
XTX = (RXSXL T X)(LXSXR T X) = RXS 2 XR T X . (12)
Where RX ∈ Rd×s as eigenvectors and S2X ∈ Rs×s as eigenvalues of XTX. By choosing only the biggest s eigenvalues and corresponding eigenvectors the dimensionality of X is reduced by
Xs = XRs = LsSsR T s Rs = LsSs. (13)
With Ls ∈ Rn×s, Ss ∈ Rs×s. Xs ∈ Rn×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(n3) (Williams & Seeger, 2001). In the following, we apply Nyströ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.

heading: 4.1 NYSTRÖM BASIS TRANSFER
text: Let Z and X have a valid decomposition given as in equation 1. Note for clarity the Nyström notation is used as in section 3.2. For a Nyström-SVD we sample from both matrices s values obtaining landmarks matrices AZ = LZSZRTZ ∈ Rs×s and AX = LXSXRTX ∈ Rs×s. Based on Nyström-SVD in equation 5, the dimensions are reduced as in equation 13 keeping only most relevant data structures
Xs = L̃XSX = [ LX L̂X ] SX = [ LX CXRXS −1 X ] SX ∈ Rn×s. (14)
Hence, it is sufficient to only compute a SVD of AX instead of X with s m, d and therefore is considerably lower in computational complexity. Analogy, we approximate source data by Zs = L̃ZSZ ∈ Rn×s. Since we again assume SZ ∼ Sx due to data normalization and domain similarities, solving the linear equation as a possible solution for equation 11, leads to M = L̃X L̃−1Z . Plugging it back we obtain
Zs = L̃X L̃ −1 Z L̃ZSZ = L̃XSZ ∈ R n×s. (15) Where again a basis of a target subspace transfers structural information into the source domain. The matrix Zs is used for training and Xs is used for testing. We showed in equation 13, that equation 14 and equation 15 are valid PCA transformations. By definition of SVD follows L̃ZL̃TZ = L̃X L̃ −1 X = I and L̃X 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 Nyströ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 Nyström Basis Transfer (NBT). But uniform sampling may not be optimal for Nyström, given labeled data in a classification task (Schleif et al., 2018). Therefore, we integrate class-wise sampling in the following.

heading: 4.2 SAMPLING STRATEGY FOR NYSTRÖM
text: The standard technique to create Nyströ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 Nyström-SVD is intractable with class-wise sampling, because respective matrices are non-square: Let Z ∈ Rm×d with m 6= d and landmark indices I = {i1, . . . , is} with at least one ij > d, then it is by definition undefined and is especially true for n > d. Therefore, we sample rows class-wise forming AdZ ∈ Rs×d instead of AZ ∈ Rs×s. Using the insights of theorem 1, we implicitly obtain an SVD of a square landmark matrix, i. e. AdZA dT Z = K d Z ∈ Rs×s by computing AdZ = LZS d ZR T Z . Hence, we can proceed without a non-square landmark matrix and using the SVD of AdZ 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 Nyström approximations. The sampling from test data X is done uniformly row-wise, because of missing class information and SVD is obtained analogy via AdX = LXS d XR T X and used in equation 14. However, the possible range of singular values of AdZ is naturally not equal to AZ . Utilizing theorem 2 it is easy to show that SdZ 6= SZ . It scales approximated matrices Zs (equation 15) different through SdZ 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.

heading: 4.3 PROPERTIES OF NYSTRÖM BASIS TRANSFER
text: The computational complexity of Nyström Basis Transfer (NBT) is composed of economy-size SVD of landmark matrices AdZ and A d X with complexity O(2s2). The matrix inversion of diagonal matrix SdX −1 in equation 14 can be neglected. Remaining k matrix multiplications are O(ks2) contributing to the overall complexity of NBT which is O(s2) 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
ENBT = ‖Xs − Zs‖F ≤ | √ n||DsX −DsZ || < ‖X− Z‖F . (16)
Where ||L̃X || ≤ √ 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 Xs and Zs 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
1Experimental data are standardized to mean zero and variance one in the preprocessing.
respective proof is given in appendix A.1. The out-of-sample extension for unseen target/source samples, e. g. x ∈ Rd, 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 xs = xR̃TX =
x [ RX S d X −1 LTBX ] and be evaluated by an arbitrary classifier learned in the subspace. The pseudo code of NBT is shown in Algorithm 1.
Algorithm 1 Nyströ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 Zs; new Target Xs;
1: AdX ,A d Z ,CX = matrix decomposition(X,Z,s) . According to section 4.2 2: SdZ = SV D(A d Z); . SVD of landmark matrix of Z 3: LX ,SdX ,RX = SV D(A d X); . SVD of landmark matrix of X
4: L̃X = [ LX CXRXS d X −1 ]T
. According to equation 14
5: Xs = L̃XSdX . According to equation 14 6: Zs = L̃XSdZ . According to equation 15 7: Zs,Xs=z normalization(Zs,Xs) . Per Matrix; Effect shown in figure 2

heading: 5 EXPERIMENTS
text: 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.

heading: 5.1 PERFORMANCE COMPARISON
text: The experiments are cumulated as three dataset group, which are Reuters, Newsgroup and OfficeCaltech. 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 KolmogorovSmirnoff-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 Nyströ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 Schö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.
2Source code and datasets are hosted at https://github.com/iclr-nbt/nbt.git
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 Nyströ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.

heading: 6 CONCLUSION
text: We proposed a low-rank domain approximation algorithm called Nyströ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 Nyströ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 Nyström approximation error with the proposed decomposition should be theoretically evaluated and compared to current Nyström techniques.
3We encountered numerical issues at our experiments, therefore the shown results are taken from (Mahadevan et al., 2019) with a similar sampling scheme.

heading: A APPENDIX
text: A.1 NORM BOUND OF NYSTRÖM BASIS TRANSFER
This section discusses the approximation error of Nyströ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 ∈ Rn×d as
‖X‖F =
√ n∑
i=1 d∑ j=1 |xij |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
D = ‖S‖F ≤ √√√√ n∑ i=1 (pi + |ri|)2. (17)
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 ∈ Rn×d with n, d > 1 and rank(X), rank(Z) > 1. The norm ‖Zs −Xs‖F in the subspace Rs induced by normalized singular vectors L ∈ Rn×s is bounded by
ENBT = ‖Zs −Xs‖F ≤ √ n||DsX −DsZ || < ‖Z−X‖F . (18)
Proof. We start by proofing the first part given by ‖Zs −Xs‖F ≤ √ n||DsX − DsZ ||. 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 = LXL−1Z leads to
‖Zs −Xs‖F = ‖MZ−Xs‖F = ∥∥LXL−1Z LZSZ − LXSX∥∥F = ‖LXSZ − LXSX‖F . (19)
Where we assume 1 ≤ s < n. This can be simplified applying the Cauchy-Schwarz inequality twice with ‖LXSZ − LXSX‖F ≤ ‖LX‖F ‖SZ − SX‖F ≤ ‖LX‖F (‖SZ‖F − ‖SX‖F ). (20) The norm of the singular values SZ ,SX ∈ Rs×s can be bounded by equation 17 resulting in
‖SZ‖F ≤ D s Z = √√√√ s∑ i=1 (pzi + |rzi |)2, ‖SX‖F ≤ D s X = √√√√ s∑ i=1 (pxi + |rxi |)2. (21)
Where pzi and r z i are the bound of a singular value of Zs and p x i and r x i are the bound of a singular value of Xs. Further, the singular vectors LX are normalized and thus can be bounded by ‖LX‖F ≤ √ n. Applying both to equation 20 leads to
‖LXSZ − LXSX‖F ≤ ‖LX‖F (‖SZ‖F − ‖SX‖F ) ≤ √ n||DsX −DsZ ||. (22)
The second term √ n||DsX −DsZ || < ‖Z−X‖F is obtained analogy. Given the SVD of the original matrices we obtain ‖Z−X‖F = ‖LZSZRZ − LXSXRX‖F . (23) By again using the Cauchy-Schwarz inequality we obtain
‖Z−X‖F ≤ ‖LZ‖F ‖SZ‖F ‖RZ‖F − ‖LX‖F ‖SX‖F ‖RX‖F . (24)
Because LZ and LX have the same size they are bounded by √ n and because RZ ,RX ∈ Rd×d and are also normalized, the norm can be bounded by ∥∥R(·)∥∥ ≤ √d respectively. Because we are not in the subspace Rs but Rd with s < d and the singular values are SZ ,SX ∈ Rn×d the numerical bound becomes
DnZ = √√√√ n∑ i=1 (pzi + |rzi |)2, D n X = √√√√ n∑ i=1 (pxi + |rxi |)2. (25)
Applying the bounds to equation 24 we obtain
‖LZ‖F ‖SZ‖F ‖RZ‖F − ‖LX‖F ‖SX‖F ‖RX‖F ≤ || √ nDnZ √ d− √ nDnX √ d||. (26)
Simplifying this term further leads to
‖Z−X‖F ≤ √ n √ d||DnZ −DnX ||. (27)
Because we assume d > 1 and a minimum of one non-zero singular vector in R(·) this at least √ n||DsX −DsZ || < ‖Z−X‖F ≤ √ n √ d||DnZ −DnX ||. (28)
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 Rd, this allows the conclusion that ENBT < EBT . 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 NYSTRÖM BASIS TRANSFER
In this section, an illustration of Nyström Basis Transfer (NBT) is given. Figure 2 shows the process of Nyström Basis Transfer. The first row shows the samples of Nyströ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, TermFrequency 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. They are two-class problems with the top categories as the positive and negative class and with subcategories as training and testing examples.
20-Newsgroup5 (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 by Long 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 (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
4http://www.daviddlewis.com/resources/testcollections/reuters21578 5http://qwone.com/˜jason/20Newsgroups/ 6https://people.eecs.berkeley.edu/˜jhoffman/domainadapt/#datasets_code
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 Nyströ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.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.

Review summaries:
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.