Impossibility Theorems for Domain Adaptation
Shai Ben David, Tyler Lu, Teresa Luu, David Pal ; JMLR W&CP 9:129-136, 2010.
Abstract
The domain adaptation problem in machine learning occurs when the test
data generating distribution differs from the one that generates the
training data. It is clear that the success of learning under such
circumstances depends on similarities between the two data
distributions. We study assumptions about the relationship between the
two distributions that one needed for domain adaptation learning to
succeed. We analyze the assumptions in an agnostic PAC-style learning
model for a the setting in which the learner can access a labeled
training data sample and an unlabeled sample generated by the test
data distribution. We focus on three assumptions: (i) Similarity
between the unlabeled distributions, (ii) Existence of a classifier in
the hypothesis class with low error on both training and testing
distributions, and (iii) The covariate shift assumption. I.e., the
assumption that the conditioned label distribution (for each data
point) is the same for both the training and test distributions. We
show that without either assumption (i) or (ii), the combination of the remaining assumptions is not sufficient toguarantee successful learning. Our negative results hold with respect to any domain adaptation learning algorithm, as long as it does not have access to target labeled examples. In particular, we provide formal proofs that the popular covariate shift assumption is rather weak and does not relieve the necessity of the other assumptions. We also discuss the intuitively appealing paradigm of reweighing the labeled training sample according to the target unlabeled distribution. We show that, somewhat counter intuitively, that paradigm cannot be trusted in the following sense. There are DA tasks that are indistinguishable, as far as the input training data goes, but in which reweighing leads to significant improvement in one task, while causing dramatic deterioration of the learning success in the other.
