Sample-to-sample correspondence for unsupervised domain adaptation

Debasmit Das, C. S. George Lee

TL;DR

This paper introduces a novel approach to Unsupervised Domain Adaptation (UDA) by establishing explicit sample-to-sample correspondences between source and target datasets. By treating data as graphs and using convex optimization to match their structures, the authors outperform traditional global statistical matching methods, especially in scenarios with significant distribution shifts.

What Problem Does This Paper Address?

In machine learning, we often assume that training (source) and testing (target) data come from the same distribution. In reality, "domain shift" is common—for example, a model trained on frontal photos of cats may fail on side-view photos.

Domain Adaptation (DA) aims to bridge this gap. Most existing methods are "global," meaning they try to align the overall statistics (like mean and covariance) of the two domains. However, these methods often ignore the local, structural relationships between individual data points. The authors tackle the challenge of Unsupervised Domain Adaptation, where we have labeled data in the source domain but zero labels in the target domain, by focusing on local, point-to-point alignment.

Methods

The core idea is to find a mapping that makes source samples look like target samples. The authors formulate this as a graph matching problem:

  1. Graph Representation: Both source and target domains are treated as hyper-graphs where nodes are data samples and edges represent similarities between neighbors.
  2. The Objective Function: They optimize a correspondence matrix $C$ based on three criteria:
  3. First-order similarity: Minimizing the distance between matched points (point-to-point).
  4. Second-order similarity: Ensuring that the "neighborhood structure" is preserved (e.g., if two points are close in the source, their matches should be close in the target).
  5. Class-based regularization: Using a group-lasso penalty to ensure that target samples are matched primarily to source samples of the same class.
  6. Convex Optimization: To make the problem solvable, they relax the discrete matching requirement (a permutation matrix) into a continuous one (a doubly stochastic matrix).
  7. Efficiency: To handle large datasets, they use the Conditional Gradient (Frank-Wolfe) method. Crucially, they convert the linear sub-problems into min-cost flow problems, which are solved extremely fast using a Network Simplex approach rather than generic linear programming solvers.

Datasets

The authors evaluated their method on a diverse set of benchmarks:

  • Toy Dataset: Two interleaving moons (rotated at various angles to simulate increasing domain shift).
  • Digit Recognition: MNIST and USPS datasets.
  • Object Recognition: The Caltech-Office dataset (Amazon, Caltech-256, DSLR, and Webcam domains) using both traditional SURF features and deep features (decaf6, decaf7).
  • Sentiment Classification: Amazon reviews across four product categories (Kitchen, DVD, Books, Electronics).

Key Insights and Ideas

  • Structure Trumps Statistics: While global methods (like CORAL) align distributions, they can "smear" class boundaries. By matching samples explicitly, this method preserves the discriminative geometry of the data.
  • The Power of Second-Order Matching: The authors found that second-order (structural) similarity is vital when the domain shift is large. For example, in the "moons" dataset, when the rotation exceeds 50 degrees, point-to-point distance becomes misleading, but the relative structure of the "moon" shape remains a reliable anchor for matching.
  • Optimization as a Bottleneck: A major contribution is the computational routine. Standard convex solvers struggle with the $O(n_s \times n_t)$ variables required for correspondence. By reframing the iteration as a network flow problem, they achieved significant speedups (e.g., 41 seconds vs. 1577 seconds for a 200-sample set).

Key Results

  • Robustness to Large Shifts: On the synthetic moons task with a 90-degree rotation, the proposed method achieved 72.2% accuracy, while traditional SVMs dropped to 17.2% and other optimal transport methods hovered around 49%.
  • Image Classification: On the Office-Caltech dataset using SURF features, the method was highly competitive, often outperforming the state-of-the-art "Optimal Transport with Group Lasso" (OT-GL) and significantly beating moment-matching methods like JDA.
  • Sentiment Analysis: The method outperformed the popular CORAL algorithm across all Amazon review domain pairs, proving its utility beyond computer vision.

Limitations and Future Work

  • Dimensionality Constraints: The current formulation assumes the source and target features have the same dimensionality. If they differ, a preprocessing step (like mapping to a latent space) is required.
  • Categorical Data: The method is designed for continuous feature spaces. Adapting it to structured/tabular data with categorical variables would require embedding techniques.
  • Scalability: While the Network Simplex approach is fast, the number of variables still grows quadratically with the number of samples. The authors suggest that future work could involve using "exemplars" (a subset of important samples) to further reduce the computational load.
  • Deep Integration: The authors express interest in integrating this correspondence-based loss directly into deep learning architectures for end-to-end representation learning.

Summary updated

Abstract

The assumption that training and testing samples are generated from the same distribution does not always hold for real-world machine-learning applications. The procedure of tackling this discrepancy between the training (source) and testing (target) domains is known as domain adaptation. We propose an unsupervised version of domain adaptation that considers the presence of only unlabelled data in the target domain. Our approach centres on finding correspondences between samples of each domain. The correspondences are obtained by treating the source and target samples as graphs and using a convex criterion to match them. The criteria used are first-order and second-order similarities between the graphs as well as a class-based regularization. We have also developed a computationally efficient routine for the convex optimization, thus allowing the proposed method to be used widely. To verify the effectiveness of the proposed method, computer simulations were conducted on synthetic, image classification and sentiment classification datasets. Results validated that the proposed local sample-to-sample matching method out-performs traditional moment-matching methods and is competitive with respect to current local domain-adaptation methods.
BibTeX
@article{das2018sample,
  author = {Debasmit Das and C. S. George Lee},
  title = {{Sample-to-sample correspondence for unsupervised domain adaptation}},
  journal = {Engineering Applications of AI},
  year = {2018},
  url = {https://openreview.net/forum?id=rrlDZ62XzQq},
}

Loading related content...

Figure