Domain Adaptation: What and Why?

• When do we need Domain Adaptation (DA)?
  • The training distribution is different from the testing distribution
• Example Domain Adaptation task?
  • Given: labeled images (e.g., fruits images)
  • Task: what fruit appears on this unlabeled images of trees
  • 
    
  • • 
      Blueberry
    • 
      Almond
    • ⇒
      
      
    • 
      Blueberry
    • 
      Almond
• How can we learn, from one distribution,
  a low-error classifier on another distribution?

Domain Adaptation: task and notations

• Typical binary classification task
  • $\displaystyle X$ : input space, $\displaystyle Y = \{-1,+1\}$ : output space
• Typical supervised classification
  • $\displaystyle \green{P_S}$ source domain: distribution over $\displaystyle X \times Y$ - $\displaystyle \green{D_S}$: marginal distribution over $\displaystyle X$
  • $\displaystyle \green{S}{} = \{(x^s_i,y^s_i)\}_{i=1}^{m_s} \sim (\green{P_S})^{m_s}$: a sample of labeled points
  • Goal: Find a classifier $\displaystyle h \in \mathcal{H}$ with a low source error $\displaystyle R_{\green{P_S}}(h) = \mathbf{E}_{(x^s,y^s)\sim \green{P_S}}\;\; \mathbf{I}\big[h(x^s)\ne y^s\big]$
• Domain Adaptation
  • $\displaystyle \orange{P_T}$ target domain: distribution over $\displaystyle X \times Y$, ($\displaystyle \orange{D_T}$: marginal over $\displaystyle X$)
  • $\displaystyle \orange{T}{} = \{(x^t_i)\}_{j=1}^{m_t} \sim (\orange{D_T})^{m_t}$: a sample of unlabeled target points
  • Goal: Find a classifier $\displaystyle h \in \mathcal{H}$ with a low target error $\displaystyle R_{\orange{P_T}}(h) = \mathbf{E}_{(x^t,y^t)\sim \orange{P_T}}\;\; \mathbf{I}\big[h(x^t)\ne y^t\big]$

Domain Adaptation − Domain Divergence

• • • Labeled source samples $\displaystyle S$
      drawn i.i.d. from $\displaystyle \green{P_S}$
    • Unlabeled target samples $\displaystyle T$
      drawn i.i.d. from $\displaystyle \orange{P_T}$
  •  $\displaystyle h$ is learned on the source, how does it perform on the target?
  • ⇒ it depends on the closeness of the domains
  • • 
    • 
• Adaptation Bound [Ben-David et al., MLJ’10, NIPS’06]
  • $\displaystyle \forall h\in\mathcal{H},\quad R_{\orange{P_T}}(h)\ \leq\ \; R_{\green{P_S}}(h)\ +\ \frac{1}{2} d_{\mathcal{H}\;\Delta\;\mathcal{H}}(\green{D_S},\orange{D_T})\ +\ \nu$
  • Domain divergence:   $\displaystyle d_{\mathcal{H}\;\Delta\;\mathcal{H}}(\green{D_S},\orange{D_T}) \;=\; 2 \sup_{(h,h')\in\mathcal{H}^2} \Big| R_{\orange{D_T}}(h,h') - R_{\green{D_S}}(h,h')\Big|$
  • Error of the joint optimal classifier:   $\displaystyle \nu = \inf_{h'\in\mathcal{H}}\big(R_{\green{P_S}}(h')+R_{\orange{P_T}}(h')\big)$
• • with some probability (1 - delta)
  • H a symmetric hypothesis space
  • More (by M. Sebban), epat slides
  • about what is d_HH nips 07

Principle of Landmarks

• JMLR 2013 − Connecting the Dots with Landmarks:
  Discriminatively Learning Domain-Invariant Features for Unsupervised Domain Adaptation
  • Boqing Gong, Kristen Grauman, Fei Sha
• Principle: find source points (the landmarks) such that
  the domains are similarly distributed “around”
• Optimization problem:  $\displaystyle \min_\alpha \left\| \frac{1}{\sum_m \alpha_m } \sum_m \alpha_m \phi (x_m) - \frac{1}{N} \sum_n \phi(x_n) \right\|^2$
• • $\displaystyle \alpha$: binary landmark indicator variables
  • $\displaystyle \phi(.)$: nonlinear mapping, maps every $\displaystyle x$ to a RKHS
  • minimize the difference in sample-means
  • + a constraint: labels should be balanced among the landmarks

Multiscale Landmark Selection

• Select landmarks among all points, $\displaystyle \green{S} \cup \orange{T}$
• Greedy selection
  • consider each candidate point $\displaystyle c$ and a set of possible scales $\displaystyle s$
  • criteria to promote the candidate
    • after projection on the candidate
    • the overlap between source and target distributions is above a threshold
• Projection: a point is projected with $\displaystyle K(c, p)= \exp \left( \frac{-\left\|c - p\right\|^2}{2 s^2} \right)$
• Overlap
  • project source and target points
  • fit two Gaussians (one for each)
  • $\displaystyle overlap(\green{\mu_S, \sigma_S} ; \orange{\mu_T, \sigma_T}) = \frac{\mathcal{N}(\green{\mu_S} - \orange{\mu_T} \mid 0, \sigma_{sum}^2)}{\mathcal{N}(0 \mid 0, \sigma_{sum}^2)}$
    • normalized integral of product
    • with $\displaystyle \sigma_{sum}^2 = \green{\sigma_S}^2 + \orange{\sigma_T}^2$, and $\displaystyle \mathcal{N}(. \mid 0, \sigma_{sum}^2)$ centered 1d-Gaussian

Landmark-Based Alignment − Overall

• Select landmarks among all points, $\displaystyle \green{S} \cup \orange{T}$
  • greedy selection
  • multi-scale selection
  • maximize domain overlap
• Project all points on the landmarks
  • use a Gaussian kernel
  • $\displaystyle \sigma \gets median\_distance(S \cup T)$
• Subspace-align the projected points
  • PCA on source domain
  • PCA on target domain
  • compute the alignment $\displaystyle M$

Landmark-Based Alignment − Results

• Is landmark-based kernelization useful?
• Is our landmark-selection any good?

MVL-SVM Results svm-2k co-regularization of view to maximize agreement

• MVML Multi-view Metric Learning (MVML) which combines vvRKHS with Metric Learning
  • 
  • 
• • 

Missing Views?

• Landmark-based missing view reconstruction method
• Allow to maintain accuracy and scalability
• • 
  • 

Domain Adaptation − Covariate Shift? This difference between the two domains is called covariate shift (Shimodaira, 2000).

• • $\displaystyle R_{\orange{P_T}}(h)\; =\;\; \mathbf{E}_{(x^t,y^t)\sim \green{P_S}}\frac{\orange{P_T}(x^t,y^t)}{\green{P_S}(x^t,y^t)}\mathbf{I}\big[h(x^t)\ne y^t\big]$
  • The target risk can be rewritten as an expectation on the source
• Covariate Shift
  • When $\displaystyle \green{P_S}(y^t|x^t)=\orange{P_T}(y^t|x^t)$ (covariate shift assumption)
  • Very strong assumption
  • We can estimate a ratio between unlabeled data
  • 
    
  • $\displaystyle \begin{matrix} {R_{\orange{P_T}}(h)}&=&\mathbf{E}_{(x^t,y^t)\sim \green{P_S}}\frac{\orange{D_T}(x^t)\orange{P_T}(y^t|x^t)}{\green{D_S}(x^t)\green{P_S}(y^t|x^t)}\mathbf{I}\big[h(x^t)\ne y^t\big]\\ \\ &=&\mathbf{E}_{(x^t,y^t)\sim \green{P_S}}\frac{\orange{D_T}(x^t)}{\green{D_S}(x^t)}\mathbf{I}\big[h(x^t)\ne y^t\big]\\ \end{matrix}$
  • ⇒ Approach: density estimation and instance re-weighting actually, it is simpler to estimate the density of the ratio
• • nice pres http://www.slideserve.com/Anita/sample-selection-bias

Subspace Alignment − Experiments

• Comparison on visual domain adaptation tasks SURF, 800 words?
  • adaptation from Office/Caltech-10 datasets (four domains to adapt)
  • adaptation on ImageNet, LabelMe and Caltech-256 datasets: one is used as source and one as target
• Other methods
  • Baseline 1: projection on the source subspace
  • Baseline 2: projection on the target subspace
  • 2 related methods:
    • GFS [Gopalan et al.,ICCV'11] Geodesic flow subspaces
    • GFK [Gong et al., CVPR'12] Geodesic flow kernel