Learning from Multiple Sources

Koby Crammer, Michael J. Kearns, Jennifer WortmanNeurIPS 2006 · OpenReview

Introduction

In many real-world machine learning scenarios, we have a small amount of labeled data for many different "sources"—such as individual web users, different hospital branches, or various sensors. If we only use a specific user's data to train their model, we suffer from high variance due to the small sample size. However, if we simply lump everyone's data together, we risk "polluting" the model with data from users who have very different preferences or behaviors.

This paper provides a formal theoretical framework for "multi-source learning," where a model for a specific target source is improved by strategically incorporating data from "nearby" similar sources. The authors tackle a fundamental question: Which subset of available data sources should be used to learn the best possible model for a specific target source? They derive a general bound that optimizes the trade-off between increasing sample size (to reduce variance) and including increasingly dissimilar data (which introduces bias).

Theoretical Framework

The authors introduce a decision-theoretic framework that generalizes across classification, regression, and density estimation. The key components of their method include:

  1. Disparity Matrix ($D$): The approach assumes access to a matrix that bounds the "distance" (or disparity) between any two sources $i$ and $j$.
  2. $\alpha$-Triangle Inequality: This is the paper's core theoretical innovation. While standard classification obeys the triangle inequality ($\alpha=1$), other problems like regression with squared loss do not. The authors prove that an "approximate" triangle inequality holds for these cases (e.g., $\alpha=2$ for regression), allowing them to bound the error of a model trained on source $B$ when applied to source $A$.
  3. Uniform Convergence Bounds: They utilize standard complexity measures (like VC dimension for classification and pseudo-dimension for regression) to account for how well empirical loss on a sample represents the true expected loss.
  4. Prefix Optimization: A significant insight is that under typical conditions, the best subset of data to use is always a "prefix" of the sources sorted by similarity. You don't need to search through all $2^K$ possible combinations of sources; you only need to check $K$ possible prefixes to find the optimal $k^*$ nearest sources that minimize the derived error bound.

Synthetic Demonstration

While primarily a theoretical contribution, the paper uses a simulated environment to demonstrate the algorithm's behavior. The setup features $K=100$ classifiers represented as points in a unit square, where "disparity" is defined as the $L_1$ distance between parameters.

Synthetic environment and sample size distribution

This visualization illustrates how the algorithm adaptively chooses to aggregate more data from distant neighbors when local data is sparse, and stays "local" when direct data is plentiful.

Key Insights and Results

The paper quantifies the three-way trade-off in multi-source learning: the total sample size (more is better), the weighted average of disparities (lower is better), and the model complexity (simpler is often safer).

The General Bound (Theorem 1): The authors provide a master equation for expected loss. It shows that the error is bounded by a term involving $\alpha$, the average disparity of the chosen sources, and a complexity term that shrinks as the total number of observations $n_{1:k}$ increases.

From this general bound, they derive task-specific bounds:

  • Classification: Error scales with $\sqrt{d/n}$, where $d$ is the VC dimension.
  • Regression: Error scales with the pseudo-dimension and includes a factor of $B^2$ (the range of the function).
  • Density Estimation: They show how to apply this to the exponential family (e.g., Gaussian, Multinomial) using the Hessian of the log-partition function to determine $\alpha$.

Furthermore, they extend the theory to use Rademacher complexity, allowing the model to adapt based on the actual data observed rather than just worst-case theoretical limits. By proving that squared loss and Bregman divergences satisfy an $\alpha$-triangle inequality, they successfully extend transfer learning theory to a much wider array of statistical problems.

Limitations and Future Work

  • The Disparity Matrix Requirement: The theory assumes the disparity matrix $D$ is known or can be accurately estimated. In practice, estimating these disparities from small samples is itself a challenging problem.
  • Computational Cost: While Rademacher complexity provides tighter data-dependent bounds, optimizing $k^*$ using this method requires re-running the learning algorithm for every possible prefix, which can be computationally expensive.
  • Static Disparities: The model assumes disparities are fixed. Future work could explore settings where source similarities evolve over time or are dependent on the specific hypothesis being tested.

Summary updated

Abstract

We consider the problem of learning accurate models from multiple sources of "nearby" data. Given distinct samples from multiple data sources and estimates of the dissimilarities between these sources, we provide a general theory of which samples should be used to learn models for each source. This theory is applicable in a broad decision-theoretic learning framework, and yields results for classification and regression generally, and for density estimation within the exponential family. A key component of our approach is the development of approximate triangle inequalities for expected loss, which may be of independent interest.
BibTeX
@inproceedings{crammer2006learning,
  author = {Koby Crammer and Michael J. Kearns and Jennifer Wortman},
  title = {{Learning from Multiple Sources}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2006},
  url = {https://openreview.net/forum?id=HJVyGwbdZH},
}
Figure