Analysis of Representations for Domain Adaptation

Shai Ben-DavidJohn BlitzerKoby CrammerFernando Pereira

article2006NeurIPS2,598 citations

Establishes a theoretical generalization bound for domain adaptation based on the A-distance between distributions, formalizing the fundamental trade-off between minimizing source classification error and learning aligned feature representations across domains.

Listen

Domain adaptation arises when a classifier trained on labeled data from a source domain must perform well on a target domain whose data distribution differs, as occurs frequently in natural language processing tasks such as part-of-speech tagging across financial news and biomedical abstracts. The core challenge is that standard learning theory assumes identical training and test distributions, yet real applications routinely violate this assumption while still sharing the same underlying task.

The article develops a theoretical bound on target-domain error for a classifier trained only on source labels and evaluates how different feature representations affect that bound. It combines finite-sample generalization results with a divergence measure (the A-distance) between the source and target distributions induced by a representation, under the assumption that a single hypothesis performs well on both domains.

The analysis shows that effective representations must simultaneously keep source training error low and reduce the A-distance between domains. Experiments on adapting a part-of-speech tagger from Wall Street Journal text to MEDLINE abstracts confirm that structural correspondence learning achieves both goals and yields the lowest target error, whereas identity features produce low source error but large domain divergence and random projections produce small divergence but high source error.

These results indicate that representation design for domain adaptation involves an explicit, quantifiable tradeoff rather than purely heuristic choices. They also justify existing successful heuristics and suggest that directly optimizing the bound terms could yield improved algorithms.

Further work should therefore focus on learning parametric representations that minimize a combination of source error and A-distance, together with empirical checks on the accuracy of the approximate divergence measure. The main limitations are that the divergence approximation does not supply a rigorous upper bound and that the experiments cover only one task and data pair, so the quantitative magnitudes observed may not generalize without additional validation.

University of Pennsylvania University of Waterloo training sample transfer learning parameter adaptation domain adaptation structural correspondence learning target domain generalization

Ben-David et al (2006).pdf

Paper: Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network, Kristina Toutanova et al. (2003). It provides the foundational sequence-tagging architecture and Wall Street Journal benchmarking setup that the source paper directly uses for its experimental evaluation on domain adaptation.
Paper: Transductive Inference for Text Classification using Support Vector Machines, T. Joachims (1999). It establishes the foundational transductive learning framework for exploiting unlabeled test distributions in text classification, which motivates the formal domain adaptation setting examined in the source.

Paper: A theory of learning from different domains, Shai Ben-David et al. (2010). It formalizes and expands the A-distance theoretical generalization bounds introduced in the source into the rigorous HΔH-divergence learning-theory framework for domain adaptation.
Paper: Biographies, Bollywood, Boom-boxes and Blenders: Domain Adaptation for Sentiment Classification, John Blitzer et al. (2007). It directly extends the structural correspondence learning and representation analysis explored in the source to multi-domain sentiment classification using mutual information pivot selection.
Paper: A Survey on Transfer Learning, Sinno Jialin Pan et al. (2010). It organizes feature-representation learning and domain adaptation methodologies into a comprehensive taxonomy of transfer learning paradigms built upon foundational representation-tradeoff bounds.
Paper: Unsupervised Domain Adaptation by Backpropagation, Yaroslav Ganin et al. (2015). It realizes the source's objective of learning domain-invariant, discriminative representations end-to-end via adversarial backpropagation and gradient reversal.
Paper: Learning Transferable Features with Deep Adaptation Networks, Mingsheng Long et al. (2015). It generalizes the feature-space divergence minimization principle established in the source to deep neural network representations using multi-kernel maximum mean discrepancy.
Paper: Deep Domain Confusion: Maximizing for Domain Invariance, Eric Tzeng et al. (2014). It implements deep domain confusion objectives that directly optimize the source error and representation divergence tradeoff proposed in the source.
Paper: Adversarial Discriminative Domain Adaptation, Eric Tzeng et al. (2017). It advances representation adaptation by framing domain alignment as an adversarial discriminative mapping into a shared feature space.
Paper: Conditional Adversarial Domain Adaptation, Mingsheng Long et al. (2017). It builds directly upon the domain adaptation bounds of the source to condition adversarial distribution alignment on classifier prediction uncertainty.
Paper: Deep CORAL: Correlation Alignment for Deep Domain Adaptation, Baochen Sun et al. (2016). It incorporates the principle of matching feature representations across domains by minimizing second-order activation covariance distances in deep networks.
Paper: Adapting Visual Category Models to New Domains, Kate Saenko et al. (2010). It applies representation transformation methods to computer vision benchmarks to align shifted feature distributions between domains.

Cover for Analysis of Representations for Domain Adaptation

Abstract

Discriminative learning methods for classification perform well when training and test data are drawn from the same distribution. In many situations, though, we have labeled training data for a source domain, and we wish to learn a classifier which performs well on a target domain with a different distribution. Under what conditions can we adapt a classifier trained on the source domain for use in the target domain? Intuitively, a good feature representation is a crucial factor in the success of domain adaptation. We formalize this intuition theoretically with a generalization bound for domain adaption. Our theory illustrates the tradeoffs inherent in designing a representation for domain adaptation and gives a new justification for a recently proposed model. It also points toward a promising new model for domain adaptation: one which explicitly minimizes the difference between the source and target domains, while at the same time maximizing the margin of the training set.

Topics

training sample transfer learning parameter adaptation svm training programs

Keywords

domain adaptation structural correspondence learning target domain generalization feature representation variational distance optimal hyperplane classifier random projections hypothesis space

1 Introduction
2 Background and Problem Setup
2.1 Domain Adaptation
3 Generalization Bounds for Domain Adaptation
3.1 The A -distance and labeling function complexity
3.2 Bound on the target domain error
4 Computing the A -distance for Signed Linear Classifiers
5 Natural Language Experiments
5.1 Random Projections
5.2 Structural Correspondence Learning
5.3 Results
6 Discussion and Future Work
7 Conclusions
References

Knowls

Knowl 1 — Finite-Sample Target Generalization Bound for Domain Adaptation
theoretical result
Let $\mathcal{X}$ be the instance space, $\mathcal{Z}$ be the feature space, and $\mathcal{R}: \mathcal{X} \to \mathcal{Z}$ be a fixed feature representation mapping. Let $\mathcal{H} \subseteq \{g: \mathcal{Z} \to \{0,1\}\}$ be a hypothesis class of VC-dimension $d$ . Let $\mathcal{D}_S$ and $\mathcal{D}_T$ be the source and target instance distributions, and let $\tilde{\mathcal{D}}_S$ and $\tilde{\mathcal{D}}_T$ be the induced marginal distributions over $\mathcal{Z}$ under $\mathcal{R}$ . Let $f: \mathcal{X} \to [0, 1]$ be the labeling rule common to both domains with induced target function $\tilde{f}(z) = \mathbb{E}_{\mathcal{D}}[f(x) \mid \mathcal{R}(x) = z]$ , and suppose $\tilde{f}$ is $\lambda$ -close to $\mathcal{H}$ , meaning $\inf_{h \in \mathcal{H}} [\epsilon_S(h) + \epsilon_T(h)] \le \lambda$ , where $\epsilon_S(h) = \mathbb{E}_{z \sim \tilde{\mathcal{D}}_S} [|\tilde{f}(z) - h(z)|]$ and $\epsilon_T(h) = \mathbb{E}_{z \sim \tilde{\mathcal{D}}_T} [|\tilde{f}(z) - h(z)|]$ .

If a labeled source sample of size $m$ is generated by applying $\mathcal{R}$ to a $\mathcal{D}_S$ -i.i.d. sample labeled by $f$ , yielding empirical source error $\hat{\epsilon}_S(h)$ , and $\tilde{U}_S, \tilde{U}_T$ are unlabeled samples of size $m'$ drawn i.i.d. from $\tilde{\mathcal{D}}_S$ and $\tilde{\mathcal{D}}_T$ respectively, then with probability at least $1 - \delta$ over the choice of samples, for every hypothesis $h \in \mathcal{H}$ :

$\epsilon_T(h) \le \hat{\epsilon}_S(h) + \sqrt{\frac{4}{m} \left(d \log \frac{2em}{d} + \log \frac{4}{\delta}\right)} + \lambda + d_{\mathcal{H}}(\tilde{U}_S, \tilde{U}_T) + 4\sqrt{\frac{d \log(2m') + \log(4/\delta)}{m'}}$

where $e$ is the base of the natural logarithm and $d_{\mathcal{H}}(\tilde{U}_S, \tilde{U}_T)$ is the empirical $\mathcal{A}$ -distance over subsets induced by $\mathcal{H}$ on the unlabeled samples.
Knowl 2 — Population Generalization Bound on Target Error
theoretical result
Let $\mathcal{R}: \mathcal{X} \to \mathcal{Z}$ be a fixed representation function from instance space $\mathcal{X}$ to feature space $\mathcal{Z}$ , and let $\mathcal{H} \subseteq \{g: \mathcal{Z} \to \{0,1\}\}$ be a hypothesis class of VC-dimension $d$ . Let $\mathcal{D}_S$ and $\mathcal{D}_T$ denote the source and target instance distributions, inducing feature distributions $\tilde{\mathcal{D}}_S$ and $\tilde{\mathcal{D}}_T$ under $\mathcal{R}$ . Let the labeling function $f: \mathcal{X} \to [0, 1]$ induce $\tilde{f}(z) = \mathbb{E}_{\mathcal{D}}[f(x) \mid \mathcal{R}(x)=z]$ , with $\lambda = \inf_{h \in \mathcal{H}} [\epsilon_S(h) + \epsilon_T(h)]$ . If a labeled sample of size $m$ is drawn i.i.d. from $\mathcal{D}_S$ , then with probability at least $1 - \delta$ , every $h \in \mathcal{H}$ satisfies:

$\epsilon_T(h) \le \hat{\epsilon}_S(h) + \sqrt{\frac{4}{m} \left(d \log \frac{2em}{d} + \log \frac{4}{\delta}\right)} + d_{\mathcal{H}}(\tilde{\mathcal{D}}_S, \tilde{\mathcal{D}}_T) + \lambda$

where $\hat{\epsilon}_S(h)$ is the empirical training error on the source sample, $e$ is the base of the natural logarithm, and $d_{\mathcal{H}}(\tilde{\mathcal{D}}_S, \tilde{\mathcal{D}}_T)$ is the $\mathcal{H}$ -divergence between the induced source and target marginal distributions.
Knowl 3 — A-Distance and H-Distance Between Probability Distributions
definition
Given a domain $\mathcal{X}$ and a collection $\mathcal{A}$ of measurable subsets of $\mathcal{X}$ , the $\mathcal{A}$ -distance between two probability distributions $\mathcal{D}$ and $\mathcal{D}'$ over $\mathcal{X}$ is defined as:

$d_{\mathcal{A}}(\mathcal{D}, \mathcal{D}') = 2 \sup_{A \in \mathcal{A}} |\Pr_{\mathcal{D}}[A] - \Pr_{\mathcal{D}'}[A]|$

When $\mathcal{A}$ is the family of characteristic subsets corresponding to a binary hypothesis class $\mathcal{H}$ , defined by $\{Z_g = \{z \in \mathcal{Z} : g(z) = 1\} : g \in \mathcal{H}\}$ , the distance is denoted $d_{\mathcal{H}}(\mathcal{D}, \mathcal{D}')$ .
Knowl 4 — Equivalence of Empirical A-Distance to Domain Discrimination Error
theoretical result
Given two unlabeled finite samples $\tilde{U}_S$ and $\tilde{U}_T$ , each of size $m'$ drawn from induced distributions $\tilde{\mathcal{D}}_S$ and $\tilde{\mathcal{D}}_T$ over $\mathcal{Z}$ , the task of discriminating whether a point originates from $\tilde{U}_S$ or $\tilde{U}_T$ using a classifier $h \in \mathcal{H}$ has error:

$\text{err}(h) = \frac{1}{2m'} \sum_{i=1}^{2m'} |h(z_i) - I_{z_i \in \tilde{U}_S}|$

where $I_{z_i \in \tilde{U}_S}$ is the indicator function for membership in the source sample $\tilde{U}_S$ . The empirical $\mathcal{A}$ -distance between the two samples over the hypothesis class $\mathcal{H}$ is directly related to the minimal discrimination error by:

$d_{\mathcal{A}}(\tilde{U}_S, \tilde{U}_T) = 2 \left(1 - 2 \min_{h' \in \mathcal{H}} \text{err}(h')\right)$

Consequently, finding the subset in $\mathcal{H}$ that maximizes the distribution discrepancy is mathematically identical to finding a classifier in $\mathcal{H}$ that minimizes the binary classification error distinguishing the two domains.
Knowl 5 — Lambda-Closeness of Target Labeling Function to Hypothesis Class
assumption
An induced labeling function $\tilde{f}: \mathcal{Z} \to [0, 1]$ is defined to be $\lambda$ -close to a hypothesis class $\mathcal{H}$ with respect to induced distributions $\tilde{\mathcal{D}}_S$ and $\tilde{\mathcal{D}}_T$ if:

$\inf_{h \in \mathcal{H}} [\epsilon_S(h) + \epsilon_T(h)] \le \lambda$

where $\epsilon_S(h) = \mathbb{E}_{z \sim \tilde{\mathcal{D}}_S} [|\tilde{f}(z) - h(z)|]$ and $\epsilon_T(h) = \mathbb{E}_{z \sim \tilde{\mathcal{D}}_T} [|\tilde{f}(z) - h(z)|]$ . This assumption formalizes domain adaptability: there must exist a single hypothesis $h^* \in \mathcal{H}$ that achieves low error on both the source and target domains under the chosen feature representation.
Knowl 6 — Approximation of A-Distance via Convex Surrogate Loss
model/method
Because finding the optimal hyperplane classifier minimizing 0-1 classification error between two distributions is NP-hard, the empirical $\mathcal{A}$ -distance $d_{\mathcal{A}}(\tilde{U}_S, \tilde{U}_T) = 2 (1 - 2 \min_{h' \in \mathcal{H}} \text{err}(h'))$ is approximated in practice by training a linear classifier to discriminate source from target instances using a convex upper bound on the error. Specifically, a linear discriminator is trained by minimizing modified Huber loss via stochastic gradient descent on the source vs. target discrimination task.
Knowl 7 — Tradeoff Principle in Domain Adaptation Representation Design
model/method
The domain adaptation generalization bounds establish that an effective representation mapping $\mathcal{R}: \mathcal{X} \to \mathcal{Z}$ must simultaneously optimize two competing quantities:
1. Low source empirical risk $\hat{\epsilon}_S(h)$ (or small classification loss) so the task remains learnable.
2. Low domain discrepancy $d_{\mathcal{H}}(\tilde{\mathcal{D}}_S, \tilde{\mathcal{D}}_T)$ so the source-trained classifier generalizes to the target domain.
Representations that optimize only one side of the tradeoff fail: preserving original distinct features yields low source error but maximal domain divergence, while unguided projections (e.g. random projections) reduce domain divergence but destroy task-discriminative information, leading to high source error.

Knowl 8 — Experimental Comparison of Feature Representations for Domain Adaptation on POS Tagging

data/table

A part-of-speech (PoS) tagger was adapted from the Wall Street Journal (WSJ, financial news source domain) to MEDLINE (biomedical abstracts target domain) using linear projections into $\mathbb{R}^d$ ( $d=200$ ). Labeled training used 100 WSJ sentences (~2,500 words), and domain $\mathcal{A}$ -distance was estimated using 500,000 unlabeled words from each domain (1,000,000 words total) via modified Huber loss.

Identity representation achieves minimal training Huber loss (0.003) but near-maximal domain divergence (1.796) due to domain-specific vocabulary. Random projections yield low $\mathcal{A}$ -distance (0.223) but destroy discriminative task structure (Huber loss 0.254, target error 0.561). Structural Correspondence Learning (SCL) achieves both low Huber loss (0.070) and low $\mathcal{A}$ -distance (0.211), yielding the lowest target domain tagging error (0.216).

Knowl 9 — Cross-Domain Part-of-Speech Tagging Adaptation Setup
experimental setup
The domain adaptation evaluation uses a part-of-speech (PoS) tagging task adapting from Wall Street Journal (WSJ) financial news (source domain with labeled data) to MEDLINE biomedical abstracts (target domain with no labeled training data). The original input representation consists of 3 million high-dimensional, sparse binary feature vectors. Representations are constructed by projecting these instances into $\mathbb{R}^d$ ( $d=200$ ) before training linear classifiers. The source training set consists of 100 sentences (~2,500 words) from WSJ. The unlabeled dataset for estimating domain $\mathcal{A}$ -distance consists of 500,000 words from WSJ and 500,000 words from MEDLINE (1,000,000 words total).

Coverage note — None was omitted; all key theoretical definitions, generalization bounds, algorithmic reductions, and empirical results are included.

References

1.R. Arriaga and S. Vempala. An algorithmic theory of learning robust concepts and random projection. In FOCS, volume 40, 1999.
2.T. Batu, L. Fortnow, R. Rubinfeld, W. Smith, and P. White. Testing that distributions are close. In FOCS, volume 41, pages 259–269, 2000.
3.J. Baxter. Learning internal representations. In COLT ’95: Proceedings of the eighth annual conference on Computational learning theory, pages 311–320, New York, NY, USA, 1995.
4.S. Ben-David, N. Eiron, and P. Long. On the difficulty of approximately maximizing agreements. Journal of Computer and System Sciences, 66:496–514, 2003.
5.S. Ben-David and R. Schuller. Exploiting task relatedness for multiple task learning. In COLT 2003: Proceedings of the sixteenth annual conference on Computational learning theory, 2003.
6.J. Blitzer, R. McDonald, and F. Pereira. Domain adaption with structural correspondence learning. In EMNLP, 2006.
7.K. Crammer, M. Kearns, and J. Wortman. Learning from data of variable quality. In Neural Information Processing Systems (NIPS), Vancouver, Canada, 2005.
8.W. Johnson and J. Lindenstrauss. Extension of lipschitz mappings to hilbert space. Contemporary Mathematics, 26:189–206, 1984.
9.D. Kifer, S. Ben-David, and J. Gehrke. Detecting change in data streams. In Very Large Databases (VLDB), 2004.
10.C. Manning. Foundations of Statistical Natural Language Processing. MIT Press, Boston, 1999.
11.D. McClosky, E. Charniak, and M. Johnson. Reranking and self-training for parser adaptation. In ACL, 2006.
12.M. Sugiyama and K. Mueller. Generalization error estimation under covariate shift. In Workshop on Information-Based Induction Sciences, 2005.
13.Y. W. Teh, M. I. Jordan, M. J. Beal, and D. M. Blei. Sharing clusters among related groups: Hierarchical Dirichlet processes. In Advances in Neural Information Processing Systems, volume 17, 2005.
14.V. Vapnik. Statistical Learning Theory. John Wiley, New York, 1998.
15.T. Zhang. Solving large-scale linear prediction problems with stochastic gradient descent. In ICML, 2004.

Citation

MLA

Ben-David, S., et al. “Analysis of Representations for Domain Adaptation”. Advances in Neural Information Processing Systems, vol. 19, 2006, https://proceedings.neurips.cc/paper_files/paper/2006/file/b1b0432ceafb0ce714426e9114852ac7-Paper.pdf.

APA

Ben-David, S., Blitzer, J., Crammer, K., & Pereira, F. (2006). Analysis of Representations for Domain Adaptation. Advances in Neural Information Processing Systems, 19. https://proceedings.neurips.cc/paper_files/paper/2006/file/b1b0432ceafb0ce714426e9114852ac7-Paper.pdf

Chicago

Ben-David, S., J. Blitzer, K. Crammer, and F. Pereira. 2006. “Analysis of Representations for Domain Adaptation”. Advances in Neural Information Processing Systems 19. https://proceedings.neurips.cc/paper_files/paper/2006/file/b1b0432ceafb0ce714426e9114852ac7-Paper.pdf.

Harvard

Ben-David, S. et al. (2006) “Analysis of Representations for Domain Adaptation”, Advances in Neural Information Processing Systems. Curran Associates, Inc. Available at: https://proceedings.neurips.cc/paper_files/paper/2006/file/b1b0432ceafb0ce714426e9114852ac7-Paper.pdf.

Vancouver

1. Ben-David S, Blitzer J, Crammer K, Pereira F (2006) Analysis of Representations for Domain Adaptation. Advances in Neural Information Processing Systems 19:

BibTeX

@inproceedings{bendavid2006analysis,
  title = {Analysis of Representations for Domain Adaptation},
  author = {Ben-David, Shai and Blitzer, John and Crammer, Koby and Pereira, Fernando},
  year = {2006},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {19},
  url = {https://proceedings.neurips.cc/paper_files/paper/2006/file/b1b0432ceafb0ce714426e9114852ac7-Paper.pdf}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Representation	Huber loss	$\mathcal{A}$ -distance	Error
Identity	0.003	1.796	0.253
Random Proj	0.254	0.223	0.561
SCL	0.070	0.211	0.216

Analysis of Representations for Domain Adaptation

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Finite-Sample Target Generalization Bound for Domain Adaptation

Knowl 2 — Population Generalization Bound on Target Error

Knowl 3 — A-Distance and H-Distance Between Probability Distributions

Knowl 4 — Equivalence of Empirical A-Distance to Domain Discrimination Error

Knowl 5 — Lambda-Closeness of Target Labeling Function to Hypothesis Class

Knowl 6 — Approximation of A-Distance via Convex Surrogate Loss

Knowl 7 — Tradeoff Principle in Domain Adaptation Representation Design

Knowl 8 — Experimental Comparison of Feature Representations for Domain Adaptation on POS Tagging

Knowl 9 — Cross-Domain Part-of-Speech Tagging Adaptation Setup

References

Citation

BibTeX

Access the Paper