Source-linked AI summary
Algorithms and Theory for Multiple-Source Adaptation
Judy Hoffman, Mehryar Mohri, Ningshan Zhang
TL;DR
Multiple-source adaptation seeks a good predictor for an unknown target mixture when learners have source predictors but may lack pooled source data. The paper develops normalized theoretical guarantees and algorithms for distribution-weighted combinations, including cross-entropy with distinct source conditional probabilities. Experiments report that the resulting model outperforms competing approaches and performs well on any target mixture distribution.
Problem
Multiple-source adaptation must combine source-domain predictors for an unknown target mixture when the learner cannot directly access the target and may not pool source data.
Method
The paper develops normalized distribution-weighted combinations, extends guarantees to stochastic settings, and uses DC-programming algorithms for squared and cross-entropy losses.
Results
The algorithm outperforms competing approaches and performs well on any target mixture distribution.
Takeaways & Limitations
The theory, algorithms, and empirical results provide a practically applicable solution for multiple-source adaptation.
Takeaways & Limitations
The setup assumes each source predictor has expected loss at most ϵ and uniformly bounded pointwise loss M.
Abstract
from arXiv · showhide
This work includes a number of novel contributions for the multiple-source adaptation problem. We present new normalized solutions with strong theoretical guarantees for the cross-entropy loss and other similar losses. We also provide new guarantees that hold in the case where the conditional probabilities for the source domains are distinct. Moreover, we give new algorithms for determining the distribution-weighted combination solution for the cross-entropy loss and other losses. We report the results of a series of experiments with real-world datasets. We find that our algorithm outperforms competing approaches by producing a single robust model that performs well on any target mixture distribution. Altogether, our theory, algorithms, and empirical results provide a full solution for the multiple-source adaptation problem with very practical benefits.
1 Introduction
The paper addresses multiple-source adaptation when target domains are unknown mixtures of sources and source data cannot be pooled. It develops normalized theory, algorithms, and experiments aimed at robust prediction across target mixtures.
- Motivation: Multiple-source adaptation combines available source-domain predictors to perform well on an unknown target mixture.The target may be a mixture, or close to a mixture, of source joint distributions.
- Motivation: Privacy and storage constraints can prevent learners from pooling all source data to train a single predictor.
- Research gap: Prior distribution-weighted theory lacked an algorithmic solution and did not apply to normalized predictors required by cross-entropy loss.Earlier analysis also assumed deterministic domains with a shared labeling function.
- Contributions: The paper provides normalized solutions with strong guarantees, including cases where source conditional probabilities differ, and extends theory to stochastic domains.
- Contributions: New algorithms determine distribution-weighted combinations for cross-entropy and other losses, while experiments report robustness across target mixture distributions.The reported algorithm outperforms competing approaches and performs well on any target mixture distribution.
- Contributions: Together, the theory, algorithms, and empirical results are presented as a practical solution to multiple-source adaptation.
2 Problem setup
The problem setup models domains as joint distributions and assumes access to relatively accurate, bounded source predictors but no target-domain information. The learner must combine these predictors for arbitrary or mixture target distributions, and convex combinations may fail.
- Setup: The stochastic MSA setup represents each domain by a joint distribution over X × Y and provides one predictor hk for each source domain.The framework assumes discrete X and Y, while predictors may take real values.
- Setup: The paper studies regression predictors hk: X → R and probability predictors hk: X × Y → [0,1] with corresponding loss functions.
- Losses: Expected predictor loss is defined with respect to a domain distribution, with particular attention to squared loss and cross-entropy loss.
- Assumptions: Each source predictor has expected loss at most ϵ, and its pointwise loss is bounded by M.
- Objective: The learner must combine source predictors without knowing the target, which may be an arbitrary unknown mixture of source domains or another distribution.
- Combination rule: No convex combination rule performs well even in simple MSA problems, motivating the distribution-weighted combination rule.
- Combination rule: The distribution-weighted combination is defined for mixture weights z and smoothing parameter η using source distributions and their input marginals.The construction extends prior definitions to the stochastic setting.
3 Theoretical analysis
The theoretical analysis extends multiple-source adaptation to stochastic domains with potentially distinct conditional label distributions. It establishes robust guarantees for mixture targets, including normalized cross-entropy predictors under stated assumptions.
- Stochastic scenario: The theory uses exponential Rényi divergence to measure distributional differences between target and source domains.
- Stochastic scenario: The stochastic analysis allows target and source conditional output distributions to differ for the same input, unlike the earlier deterministic shared-labeling setup.
- General guarantees: For source-mixture targets, Theorem 1 establishes a distribution-weighted predictor with favorable guarantees under conditional-distribution proximity conditions.
- General guarantees: In the probability model, the constructed predictor has loss at most ϵ on any target distribution in the source-mixture family.
- Shared conditional probabilities: When source conditional probabilities are shared, a single predictor can achieve loss at most ϵ + δ for every source-mixture target, for any δ > 0.
- Extensions: The guarantees extend to estimated source densities and targets outside the source-mixture family, with dependence on Rényi divergences.
- Cross-entropy loss: For normalized cross-entropy predictors, Theorem 3 gives the same ϵ + δ guarantee under a lower-bound assumption on source distributions.
- Cross-entropy loss: When source conditional probabilities differ, a marginal distribution-weighted rule is already normalized and can inherit favorable guarantees.
4 Algorithms
The paper develops practical algorithms for finding distribution-weighting parameters with strong guarantees, including normalized combinations for probability models. It formulates the task as DC programming and iteratively solves convex subproblems that converge to a local minimum.
- Algorithmic objective: The distribution-weighted combination has favorable guarantees, and the paper introduces an algorithm to determine its weighting vector z.This addresses an algorithmic gap left by earlier theoretical work.
- Optimization formulation: The method formulates finding z as a min-max problem that seeks nearly equal loss across source domains.The resulting objective minimizes the maximum source-domain loss.
- DC formulation: For squared loss and cross-entropy loss, the paper provides explicit DC decompositions of the optimization objective.These decompositions express each source-domain loss as a difference of convex functions.
- Model construction: The combination hypothesis is represented as a ratio of affine functions for both the regression and probability models.The paper writes the predictor as h_z = J_z/K_z.
- DC algorithm: The DC algorithm repeatedly solves a convex optimization problem from an arbitrary z_0 and is guaranteed to converge to a local minimum.The optimization subproblem is relatively simple because its objective and constraints have tractable forms.
- Optimality criterion: A solution is globally optimal when its objective value is close to zero, providing a criterion for assessing the obtained weighting vector.The global optimum cannot be negative and is theoretically close to zero.
5 Experiments
Experiments evaluate the distribution-weighted method on sentiment, digit-recognition, and Office datasets under varied target mixtures. Across these settings, the method generally outperforms or matches competing baselines while using a single predictor without target data or network retraining.
- Experimental setup: On an artificial dataset with known densities, the global objective approached the known optimum of zero.The experiment first checks the DC-programming solution against a setting with a known global solution.
- Sentiment analysis: The sentiment dataset contains 2,000 samples from each of four product-review domains: books, dvd, electronics, and kitchen.Features use a 2,500-word vocabulary, and source predictors are trained with support vector regression.
- Sentiment analysis: In two-source sentiment mixtures, DW outperforms all baseline predictors, including privileged λ-comb and KMM scenarios.KMM uses unlabeled target data, whereas DW uses no target data.
- Sentiment analysis: Across sentiment test domains, DW outperforms all baseline predictors, including the uniform combination and source-only models.The comparison reports mean and standard deviations of MSE over 10 repetitions.
- Recognition tasks: The recognition experiments use digit and Office datasets, evaluating individual domains, pairwise mixtures, and fully combined test distributions.The digit task uses SVHN, MNIST, and USPS; the Office task uses amazon, webcam, and dslr.
- Recognition tasks: On digit and Office datasets, DW outperforms or matches same-domain classifiers and is comparable or marginally superior to jointly trained networks on mixed targets.DW does not retrain network parameters and learns distribution weights from only a small number of per-domain examples.
6 Conclusion
The paper presents practically applicable multiple-source domain adaptation algorithms for cross-entropy and similar losses, supported by favorable theoretical guarantees and empirical evidence of effectiveness.
- The algorithms target cross-entropy and other similar losses in multiple-source domain adaptation.
A Lower bounds for convex combination rules
This section shows that convex combinations of source predictors can have poor performance on mixture targets, even when each predictor is perfect on its own domain.
- Convex combination rules can incur a squared-loss lower bound on a mixture-adaptation problem.
- Even zero source-domain error does not ensure that a convex combination performs well on the target mixture.
- For cross-entropy, any convex combination rule incurs loss at least log(p) on some target mixture.
- The lower bound demonstrates that no convex combination rule is robust against every target mixture, despite zero error for the base hypotheses on their own domains.
- The theoretical results distinguish regression and probability models because their distribution-weighted combinations use different definitions.
B.1 Regression model
The regression-model analysis develops guarantees for distribution-weighted combinations, including extensions to stochastic settings and cases with distinct conditional probabilities.
- The analysis first treats shared conditional probabilities, then relaxes that assumption to prove a stronger result for regression.
- Brouwer’s Fixed-Point Theorem supplies a point used in the regression-model proof.
- For positive η and η′, a distribution-weighted combining rule admits z in the simplex with every coordinate nonzero.
- Under shared conditional probabilities, the distribution-weighted rule obtains a bound for any source mixture, with η and z chosen for any δ > 0.
- The guarantees extend to arbitrary target distributions through Rényi-divergence conditions and estimated source distributions.
- Theorem 12 provides the regression guarantee without requiring identical conditional probabilities across domains.
- When the target belongs to the relevant mixture family, Theorem 12 coincides with Theorem 1.
B.2 Probability model
The probability-model analysis parallels the regression results while making no assumption that conditional probabilities are shared across domains.
- The probability-model proofs follow the regression-model results but do not assume identical conditional probabilities across domains.
- For positive η and η′, the probability-model distribution-weighted combining rule has a simplex point z with all coordinates nonzero.
- For any δ > 0, the distribution-weighted rule satisfies a guarantee for arbitrary source mixtures.
- Theorem 12 and Corollary 11 provide probability-model guarantees for arbitrary target distributions without shared conditional probabilities.
C Specific theoretical analysis for the cross-entropy loss
The paper develops normalized cross-entropy solutions with guarantees under both shared and distinct source conditional probabilities, plus DC-programming formulations for computing distribution-weighted predictors.
- Cross-entropy guarantees: Normalized predictors are required for cross-entropy guarantees, motivating a separate analysis of the normalized distribution-weighted combination.The section specifically targets cross-entropy and other probability-model losses.
- Shared conditional probabilities: Under a shared conditional-probability assumption and a density lower bound, the theory guarantees loss at most ϵ + δ for any source-mixture parameter λ.The assumption is Dk(y|x) independent of k, and each source joint density is bounded below by µU.
- Distinct conditional probabilities: When source conditional probabilities differ, the analysis provides a modified normalized combination with favorable guarantees, while identifying a log(p) lower bound for the earlier analysis.The marginal distribution-weighted rule is already normalized and can be analyzed directly.
- Estimated distributions: The theoretical extensions also cover estimated source distributions, with favorable guarantees retained under the corresponding estimates.The results and proofs are described as analogous to earlier regression-model corollaries.
- Optimization: For squared and cross-entropy losses, the optimization objective is expressed as a difference of convex functions, yielding a DC-programming algorithm converging to a stationary point.The cross-entropy decomposition uses convexity of negative logarithms and unnormalized relative entropy.
- Optimization: Synthetic experiments show the global objective approaches the known optimum of zero for squared and cross-entropy losses.The supplied experiments use artificial datasets to test convergence toward the known optimum.
E.1 Artificial dataset
Artificial-data experiments test the DC-programming solution for squared and cross-entropy losses against known global optima. In both settings, the objective approaches zero from varied initializations.
- Squared loss: The synthetic squared-loss experiment uses known Gaussian-mixture densities to optimize the mixing weights directly.Two source domains are constructed from overlapping Gaussian components, and linear regressors provide the base hypotheses.
- Squared loss: The squared-loss objective approaches 0.0, the known global minimum, and reaches the global solution under various initial conditions.The experiment initializes with uniform weights z0 = [1/2, 1/2].
- Cross-entropy loss: The cross-entropy dataset contains three colored domains and three categories generated from Gaussian mixtures with domain-specific covariance magnitudes.The domains are red, green, and blue; the categories are squares, circles, and triangles.
- Cross-entropy loss: The cross-entropy global objective approaches 0.0, the known global minimum, from uniform and other initial mixing weights.Only each convex subproblem is guaranteed to converge, while the reported experiments reach the global solution from tested initializations.
E.2 Sentiment analysis task for squared loss
The sentiment-analysis experiment estimates source marginals with domain-specific bigram language models and uses unlabeled generated samples to find the mixing solution. The resulting distribution-weighted predictor outperforms competing baselines across tested target mixtures.
- Density estimation: Each source marginal is estimated by drawing 10,000 sentences from a domain-specific bigram language model.The empirical sample distribution is used as a close estimate of each source marginal.
- Density estimation: The mixing vector z is found using generated samples whose labels are approximated by averaging the available source predictors.The generated samples are used to determine the fixed-point solution.
- Evaluation setup: The method uses only estimated marginal language-model distributions to find z, without using labels during this step.Original review text and rating labels are reserved for testing.
- Results: The distribution-weighted predictor DW outperforms source-only predictors, K, D, B, E, a uniform predictor, and KMM across tested target mixtures.The experiments include combinations of two domains and mixtures of four domains.