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 centers 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. 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.
The Challenge of Domain Shift
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 (UDA), where labeled data exists in the source domain but the target domain is entirely unlabeled, by focusing on local, point-to-point alignment.
Methodology: Graph-Based Matching
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:
- Graph Representation: Both source and target domains are treated as graphs where nodes are data samples and edges represent similarities between neighbors.
- The Objective Function: They optimize a correspondence matrix $C$ based on three criteria:
- First-order similarity: Minimizing the distance between matched points (point-to-point).
- 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).
- Class-based regularization: Using a group-lasso penalty to ensure that target samples are matched primarily to source samples of the same class.
Optimization and Efficiency
To make the problem solvable, the authors relax the discrete matching requirement (a permutation matrix) into a continuous one (a doubly stochastic matrix). 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. This achieved significant speedups, such as reducing computation from 1577 seconds to 41 seconds for a 200-sample set.
Key Insights and Results
- 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.
- Robustness to Large Shifts: On a synthetic "moons" task with a 90-degree rotation, the proposed method achieved 72.2% accuracy, while traditional SVMs dropped to 17.2%.
- Broad Applicability: The method was highly competitive on the Office-Caltech image dataset and outperformed the popular CORAL algorithm across Amazon review domains for sentiment analysis.
Conclusion
By prioritizing local sample-to-sample correspondences over global statistical alignment, this method offers a robust solution for unsupervised domain adaptation. Future work will explore scaling to larger datasets via exemplar selection and integrating the correspondence loss into deep learning architectures for end-to-end representation learning.
Summary updated