Low-Rank Subspace Override for Unsupervised Domain Adaptation

Abstract

Current supervised learning models cannot generalize well across domain boundaries, which is a known problem in many applications, such as robotics or visual classification. Domain adaptation methods are used to improve these generalization properties. However, these techniques suffer either from being restricted to a particular task, such as visual adaptation, require a lot of computational time and data, which is not always guaranteed, have complex parameterization, or expensive optimization procedures. In this work, we present an approach that requires only a well-chosen snapshot of data to find a single domain invariant subspace. The subspace is calculated in closed form and overrides domain structures, which makes it fast and stable in parameterization. By employing low-rank techniques, we emphasize on descriptive characteristics of data. The presented idea is evaluated on various domain adaptation tasks such as text and image classification against state of the art domain adaptation approaches and achieves remarkable performance across all tasks.

Appendices

A Appendix A Proof of Subspace Override Bound

Theorem 1

Given two rectangular matrices $\mathbf {X}_t,\mathbf {X}_s \in \mathbb {R}^{n \times d}$ with $n,d > 1$ and rank of $\mathbf {X}_t$ and $\mathbf {X}_s > 1$. The norm $\left\Vert \mathbf {X}_s^l-\mathbf {X}_t^l\right\Vert _F^2$ in the subspace $\mathbb {R}^l$ induced by normalized subspace projector $\mathbf {M}\in \mathbb {R}^{n \times l}$ with $\mathbf {M}^T\mathbf {M} = \mathbf {I}$ is bounded by

$$\begin{aligned} E_{SO} = \left\Vert \mathbf {X}_s^l-\mathbf {X}_t^l\right\Vert _F^2 < \sum _{i=1}^{l+1} (\sigma _i(\mathbf {X}_s) - \sigma _i(\mathbf {X}_t))^2 \le \left\Vert \mathbf {X}_s-\mathbf {X}_t\right\Vert _F^2. \end{aligned}$$

(13)

Following  [9] the squared Frobenius norm of a matrix difference between two matrices can be bounded by

$$\begin{aligned} \sum _{i=1}^q (\sigma _i(\mathbf {X}_s) - \sigma _i(\mathbf {X}_t))^2 \le \left\Vert \mathbf {X}_s-\mathbf {X}_t\right\Vert _F^2, \end{aligned}$$

(14)

where $q = min(n,d)$ and $\sigma _i(\cdot )$ is the i-th singular value of the respective matrix in descending order. However, the subspace matrices $\mathbf {X}_s^l$ and $\mathbf {X}_t^l$ are a special case due to the subspace override of the projector $\mathbf {M} =\mathbf {U}_t^l{\mathbf {U}_s^l}^{-1}$, because

$$\begin{aligned} \left\Vert \mathbf {X}_s^l-\mathbf {X}_t^l\right\Vert _F^2&= \left\Vert \mathbf {M}\mathbf {U}_s^l \varvec{\varSigma }_s^l - \mathbf {U}_t^l \varvec{\varSigma }_t^l\right\Vert _F^2 = \left\Vert \mathbf {U}_t^l\varvec{\varSigma }_s^l - \mathbf {U}_t^l\varvec{\varSigma }_t^l \right\Vert _F^2 \end{aligned}$$

(15)

$$\begin{aligned}&= \left\Vert \mathbf {U}_t^l\varvec{\varSigma }_s^l\right\Vert _F^2 + \left\Vert \mathbf {U}_t^l\varvec{\varSigma }_t^l\right\Vert _F^2 - 2Tr({\varvec{\varSigma }_s^l}^T {\mathbf {U}_t^l}^T \mathbf {U}_t^l \varvec{\varSigma }_t^l) \end{aligned}$$

(16)

$$\begin{aligned}&= \left\Vert \varvec{\varSigma }_s^l\right\Vert _F^2 + \left\Vert \varvec{\varSigma }_t^l\right\Vert _F^2 - 2Tr({\varvec{\varSigma }_s^l}^T \varvec{\varSigma }_t^l) \end{aligned}$$

(17)

$$\begin{aligned}&= \sum _{i=1}^l \sigma _i^2(\mathbf {X}_s^l) +\sum _{i=1}^l \sigma _i^2(X_t^l) - 2\sum _{i=1}^l (\sigma _i(X_s^l) \cdot \sigma _i(X_t^l))\end{aligned}$$

(18)

$$\begin{aligned}&= \sum _{i=1}^l (\sigma _i(\mathbf {X}_s^l) - \sigma _i(\mathbf {X}_t^l))^2. \end{aligned}$$

(19)

The important fact in the right part of Eq. (16) and (17) is that we do not rely on the bound of the Frobenius inner product as in the proof for Eq. (14) [9, p. 459], because ${\mathbf {U}_t^l}^T\mathbf {U}_t^l = \mathbf {I}$. Therefore, we can directly compute the Frobenius inner product of the the diagonal matrices $\varvec{\varSigma }_s^l$ and $\varvec{\varSigma }_t^l$, which is simply the sum of the product of the singular values. Consequently follows for $l+1$ and $(\sigma _{l+1}(\mathbf {X}_s) - \sigma _{l+1}(\mathbf {X}_t))^2\ne 0$,

$$\begin{aligned} \left\Vert \mathbf {X}_s^l-\mathbf {X}_t^l\right\Vert _F^2< \sum _{i=1}^{l+1} (\sigma _i(\mathbf {X}_s) - \sigma _i(\mathbf {X}_t))^2 < \sum _{i=1}^q (\sigma _i(\mathbf {X}_s) - \sigma _i(\mathbf {X}_t))^2 \le \left\Vert \mathbf {X}_s-\mathbf {X}_t\right\Vert _F^2, \end{aligned}$$

(20)

where again $q = min(n,d)$ and $1<l<q$.

B Appendix B Component Analysis

We inspect the performance contribution of the different parts of the NSO approach. First, the exact solution to the optimization problem is called Subspace Override (SO). The approximation with uniform sampling is evaluated to study the impact of class-wise sampling on the performance. To show the efficiency of the subspace projection in original space, we include a kernelized version where we approximate the RBF-kernels of $\mathbf {X}_s$ and $\mathbf {X}_t$, respectively. The results are given in Table 7 and show that the Nyström approximation independent of the sampling strategy yields the best performance. This comes from the approximation of the subspace projection, where small values are likely to be zero, hence reducing noise further. The kernelized version is not recommended due to bad performance. Overall, as proposed, the class-wise NSO is recommended, because it is slightly better.

Table 7. Component evaluation of NSO in mean accuracy.