We consider the problem of \emph{ pruning} a classification tree, that is, selecting a suitable subtree that balances bias and variance, in common situations with inhomogeneous training data. Namely, assuming access to mostly data from a distribution $P_{ X, Y}$, but little data from a desired distribution $Q_{ X, Y}$ with different $X$-marginals, we present the first efficient procedure for optimal pruning in such situations, when cross-validation and other penalized variants are grossly inadequate. Optimality is derived with respect to a notion of \emph{ average discrepancy} $P_{ X} \to Q_{ X}$ (averaged over $X$ space) which significantly relaxes a recent notion -- termed \emph{ transfer-exponent} -- shown to tightly capture the limits of classification under such a distribution shift. Our relaxed notion can be viewed as a measure of \emph{ relative dimension} between distributions, as it relates to existing notions of information such as the Minkowski and Renyi dimensions.
Categories: stat.ML cs.LG