Distribution shift and domain adaptation

Let $(\mathsf{X},{\mathrm{\Sigma }}_X)$, $(\mathsf{Y},{\mathrm{\Sigma }}_Y)$, and $(\mathsf{A},{\mathrm{\Sigma }}_A)$ be nonempty measurable spaces. A source/target pair of joint laws consists of probability measures $P_S$ and $P_T$ on $(\mathsf{X}\times \mathsf{Y},{\mathrm{\Sigma }}_X\otimes {\mathrm{\Sigma }}_Y)$. For $D\in \{S,T\}$, its input marginal is the probability measure ${\mu }_D$ on $(\mathsf{X},{\mathrm{\Sigma }}_X)$ defined by ${\mu }_D(A)=P_D(A\times \mathsf{Y})$. If $h:\mathsf{X}\to \mathsf{A}$ is measurable and $\mathrm{\ell }:\mathsf{A}\times \mathsf{Y}\to [0,+\mathrm{\infty }]$ is product-measurable, then $(x,y)\mapsto (h(x),y)$ is measurable: the preimage of a measurable rectangle $U\times V$ is $h^{-1}(U)\times V$, and such rectangles generate the product sigma-algebra. Taking preimages once more shows that $(x,y)\mapsto \mathrm{\ell }(h(x),y)$ is measurable. The domain risk is the extended nonnegative integral $R_D(h):={\int }_{\mathsf{X}\times \mathsf{Y}}\mathrm{\ell }(h(x),y)P_D(d(x,y))\mathrm{.}$

A conditional label kernel for $P_D$ is a specified probability kernel $K_D$ from $(\mathsf{X},{\mathrm{\Sigma }}_X)$ to $(\mathsf{Y},{\mathrm{\Sigma }}_Y)$ such that, for every nonnegative product-measurable $g:\mathsf{X}\times \mathsf{Y}\to [0,+\mathrm{\infty }]$, $\int g(x,y)P_D(d(x,y))={\int }_{\mathsf{X}}({\int }_{\mathsf{Y}}g(x,y)K_D(x,dy)){\mu }_D(dx)\mathrm{.}$ The pair is under covariate shift when conditional label kernels $K_S,K_T$ are supplied, there is a measurable set $N$ with ${\mu }_T(N)=0$ such that $K_S(x,\cdot )=K_T(x,\cdot )$ as probability measures for every $x\mathrm{\notin }N$, and ${\mu }_T\ll {\mu }_S$. No existence of conditional kernels is asserted by this definition.

Supervised prediction problems: gives the measurable spaces, joint probability law, predictor class, and measurable loss convention.

Population and empirical risk: defines domain risk as an extended nonnegative integral.

A measurable function between measurable spaces: a map is measurable when preimages of measurable sets are measurable.

The product sigma-algebra and its finite iterates: the product sigma-algebra is generated by measurable rectangles.

Measure kernel and probability kernel: a probability kernel assigns a probability measure to each input and has measurable event evaluations.

Absolute continuity of a signed or complex measure with respect to a positive measure: ${\mu }_T\ll {\mu }_S$ means every ${\mu }_S$-null measurable set is ${\mu }_T$-null.

Measurability of integration against a kernel: for a probability kernel and a nonnegative product-measurable function, the section integral is measurable.

Shalev-Shwartz and Ben-David, §3.2.1–3.2.2, PDF pp. 45–48: joint domain/label laws, marginal input law, classification risk, general loss, and expected risk.

Ben-David et al., §§3–4, printed pp. 154–158: source and target input distributions and labeling functions, their risks, and the joint-labeling error convention.

Mansour, Mohri, and Rostamizadeh, §§2–3, arXiv version 3, pp. 2–4: domain risks and distribution-dependent losses for arbitrary measurable function classes.

Sugiyama, §2, book pp. 928–930: training and test input laws, a shared conditional label law, and target generalization risk.

Let $(\mathsf{X},{\mathrm{\Sigma }}_X)$ be a measurable space, equip $\{0,1\}$ with its discrete sigma-algebra, let ${\mu }_S$ and ${\mu }_T$ be probability measures on $\mathsf{X}$, and let $\mathcal{H}$ be a nonempty class of measurable classifiers $h:\mathsf{X}\to \{0,1\}$. For $h,h^{\mathrm{\prime }}\in \mathcal{H}$, define their measurable disagreement set by $A_{h,h^{\mathrm{\prime }}}:=(h^{-1}(\{0\})\cap h^{\mathrm{\prime }-1}(\{1\}))\cup (h^{-1}(\{1\})\cap h^{\mathrm{\prime }-1}(\{0\}))\mathrm{.}$ The $\mathcal{H}\mathrm{\Delta }\mathcal{H}$ divergence of the two input laws is $d_{\mathcal{H}\mathrm{\Delta }\mathcal{H}}({\mu }_S,{\mu }_T):=2{\sup }_{h,h^{\mathrm{\prime }}\in \mathcal{H}}\mid {\mu }_S(A_{h,h^{\mathrm{\prime }}})-{\mu }_T(A_{h,h^{\mathrm{\prime }}})\mid \in [0,2]\mathrm{.}$

Source and target joint laws, risks, and covariate shift: supplies the source and target input marginals ${\mu }_S$ and ${\mu }_T$.

A measurable function between measurable spaces: measurability means measurable preimages, so the displayed finite union of intersections is measurable.

Ben-David et al., Definition 3, Lemma 3, printed pp. 156–157: the symmetric-difference hypothesis class and the disagreement-probability bound.

Mansour, Mohri, and Rostamizadeh, Definition 3 and §3, arXiv version 3, pp. 3–4: the $d_A$ distance with $A=\mathcal{H}\mathrm{\Delta }\mathcal{H}$ for binary classification.

Let $(\mathsf{X},{\mathrm{\Sigma }}_X)$ and $(\mathsf{Y},{\mathrm{\Sigma }}_Y)$ be measurable spaces, let $P$ and $Q$ be probability measures on $\mathsf{X}$ (in particular, source and target input marginals), and let $\mathcal{H}$ be a nonempty class of measurable functions $h:\mathsf{X}\to \mathsf{Y}$. Let $L:\mathsf{Y}\times \mathsf{Y}\to [0,+\mathrm{\infty }]$ be product-measurable. For $h,h^{\mathrm{\prime }}\in \mathcal{H}$, the map $x\mapsto (h^{\mathrm{\prime }}(x),h(x))$ is measurable because the preimage of each measurable rectangle $A\times B$ is $h^{\mathrm{\prime }-1}(A)\cap h^{-1}(B)$ and such rectangles generate the product sigma-algebra; composing with $L$ shows that $x\mapsto L(h^{\mathrm{\prime }}(x),h(x))$ is measurable. Assume that, for every $h,h^{\mathrm{\prime }}\in \mathcal{H}$, the two integrals below are finite, and define $L_P(h^{\mathrm{\prime }},h):={\int }_{\mathsf{X}}L(h^{\mathrm{\prime }}(x),h(x))P(dx),L_Q(h^{\mathrm{\prime }},h):={\int }_{\mathsf{X}}L(h^{\mathrm{\prime }}(x),h(x))Q(dx)\mathrm{.}$ The $L$-discrepancy between $P$ and $Q$ over $\mathcal{H}$ is the extended nonnegative number ${\mathrm{disc}}_L(P,Q):={\sup }_{h,h^{\mathrm{\prime }}\in \mathcal{H}}\mid L_P(h^{\mathrm{\prime }},h)-L_Q(h^{\mathrm{\prime }},h)\mid \in [0,+\mathrm{\infty }]\mathrm{.}$ The supremum need not be attained.

Source and target joint laws, risks, and covariate shift: supplies the source and target input marginals and their common measurable input space.

A measurable function between measurable spaces: a map is measurable when preimages of measurable sets are measurable.

The product sigma-algebra and its finite iterates: the product sigma-algebra is generated by measurable rectangles.

Mansour, Mohri, and Rostamizadeh, Definition 4 and Theorem 8, arXiv version 3, pp. 4–6: the discrepancy distance for a general loss and its domain-adaptation bound.

Sugiyama, §2 and §3.1, book pp. 928–931: generalization risk under distinct input laws and loss reweighting under a shared conditional label law.

Assume AC. Let $P_S,P_T$ be source and target joint laws with input marginals ${\mu }_S,{\mu }_T$ and specified conditional label kernels $K_S,K_T$ as in the definition of source/target distributions. Suppose ${\mu }_T\ll {\mu }_S$ and there is a ${\mu }_T$-null set outside of which $K_S(x,\cdot )=K_T(x,\cdot )$. Let $w$ be any nonnegative measurable representative of $d{\mu }_T\mathrm{/}d{\mu }_S$. Then for every product-measurable set $E\subseteq \mathsf{X}\times \mathsf{Y}$, $P_T(E)={\int }_{E}w(x)P_S(d(x,y))\mathrm{.}$ Consequently $P_T\ll P_S$ and $w\circ {\pi }_X$ is a representative of the likelihood-ratio density of $P_T$ with respect to $P_S$.

Sugiyama, §3.1, book pp. 930–931: the density-based covariate-shift identity that this lemma establishes for general measurable spaces using supplied conditional kernels.

Assume AC. Let $P_S,P_T$ be source and target joint laws under covariate shift, with input marginals ${\mu }_S,{\mu }_T$ and common conditional label kernel $K$. Let $w$ be a nonnegative measurable representative of $d{\mu }_T\mathrm{/}d{\mu }_S$. For any measurable predictor $h$ and nonnegative product-measurable loss $\mathrm{\ell }$, if the weighted source loss is integrable, then $R_T(h)={\int }_{\mathsf{X}\times \mathsf{Y}}\mathrm{\ell }(h(x),y)P_T(d(x,y))={\int }_{\mathsf{X}\times \mathsf{Y}}w(x)\mathrm{\ell }(h(x),y)P_S(d(x,y))<+\mathrm{\infty }\mathrm{.}$

Sugiyama, §3.1, book pp. 930–931: the importance-weighting identity for a shared conditional label law.

Mansour, Mohri, and Rostamizadeh, §2, arXiv version 3, pp. 2–3: domain risks and arbitrary measurable loss notation.

Let $(\mathsf{X},{\mathrm{\Sigma }}_X)$ be a measurable space, equip $\{0,1\}$ with its discrete sigma-algebra, and let $P_S,P_T$ be joint probability laws on $\mathsf{X}\times \{0,1\}$ with input marginals ${\mu }_S,{\mu }_T$. Let $\mathcal{H}$ be a nonempty class of measurable classifiers $h:\mathsf{X}\to \{0,1\}$. Define the source and target risks by ${ϵ}_D(h):=P_D\{(x,y):h(x)\mathrm{\ne }y\}$ for $D\in \{S,T\}$ and define the joint-labeling error $\lambda :={\inf }_{g\in \mathcal{H}}({ϵ}_S(g)+{ϵ}_T(g))$. Then every $h\in \mathcal{H}$ satisfies ${ϵ}_T(h)\le {ϵ}_S(h)+\frac{1}{2}{d}_{\mathcal{H}\mathrm{\Delta }\mathcal{H}}({\mu }_S,{\mu }_T)+\lambda \mathrm{.}$

Ben-David et al., Definitions 2–3, Lemma 3, and complete Theorem 2 proof, printed pp. 156–158: the ideal joint error, symmetric-difference divergence, and the source/target triangle argument.

Mansour, Mohri, and Rostamizadeh, §3 and §4.1, arXiv version 3, pp. 3–5: the disagreement distance and the separate finite-sample complexity bounds.

This is a population inequality. It does not bound empirical source risk or an empirical estimate of the divergence; finite-sample substitution requires a separate bounded-loss and complexity theorem. Even when the input divergence is small, a large joint-labeling error $\lambda$ can leave the target-risk bound large.

Ben-David et al., Theorem 2 and its complete proof, printed pp. 157–158: the finite-sample target bound adds VC-complexity terms to the population inequality.

Mansour, Mohri, and Rostamizadeh, §3 and Theorem 9, arXiv version 3, pp. 4–7: empirical discrepancy bounds require Rademacher-complexity controls and bounded-loss assumptions.

Let $P,Q$ be the source and target input marginals on a common measurable space $\mathsf{X}$. Let $\mathsf{Y}$ be a measurable output space, $\mathcal{H}$ a nonempty class of measurable functions $h:\mathsf{X}\to \mathsf{Y}$, and $f_P,f_Q:\mathsf{X}\to \mathsf{Y}$ measurable labeling functions. Let $L:\mathsf{Y}\times \mathsf{Y}\to [0,+\mathrm{\infty }]$ be product-measurable, symmetric, and satisfy the triangle inequality. Define $L_D(g_1,g_2):={\int }_{\mathsf{X}}L(g_1(x),g_2(x))D(dx)(D\in \{P,Q\}),{\mathrm{disc}}_L(P,Q):={\sup }_{g_1,g_2\in \mathcal{H}}\mathrm{\mid }{L}_P(g_1,g_2)-L_Q(g_1,g_2)\mathrm{\mid }\mathrm{.}$ Assume that every pairwise integral in this discrepancy definition is finite and that source and target minimizers $h_P^{\ast }\in \arg {\min }_{g\in \mathcal{H}}{L}_P(g,f_P)$ and $h_Q^{\ast }\in \arg {\min }_{g\in \mathcal{H}}{L}_Q(g,f_Q)$ exist. Then every $h\in \mathcal{H}$ satisfies $L_P(h,f_P)\le L_P(h_P^{\ast },f_P)+L_Q(h,h_Q^{\ast })+{\mathrm{disc}}_L(P,Q)+\min \{L_Q(h_Q^{\ast },h_P^{\ast }),L_P(h_Q^{\ast },h_P^{\ast })\}\mathrm{.}$ The supremum defining ${\mathrm{disc}}_L$ may be infinite, in which case the inequality is interpreted in the extended nonnegative reals.

Mansour, Mohri, and Rostamizadeh, Definition 4 and Theorem 8, arXiv version 3, §§3–4.1, pp. 3–6: the discrepancy definition and the bound with the minimum of both cross-domain terms (Theorem 8, Eq. (11)); its proof gives both triangle-inequality routes.

The discrepancy in this theorem is a population quantity. Estimating it from finite samples, or replacing the input laws by empirical laws, requires additional bounded-loss and complexity assumptions and is a separate result.

Mansour, Mohri, and Rostamizadeh, §§3–4.1, arXiv version 3, pp. 3–7: finite-sample discrepancy estimation and the empirical target-risk bound are stated separately with Rademacher and bounded-loss hypotheses.