Summary: If we train a classifier on a training set that comes from one distribution, and test it on a dataset coming from a different distribution, uniform convergence guarantees generally no longer hold. This post presents a strategy for creating classifiers that will reject test points when they are sufficiently different from training data. It works by rejecting points that are much more probable under the predicted test distribution than under the training distribution.

Introduction

In machine learning, we often train a system (e.g. a classifier or regression system) on a training set, and then test it on a test set. If the test set comes from the same distribution as the training set, uniform convergence guarantees allow us to bound the system's expected error on the test set based on its performance on the training set. As an example, if we are creating an automated system for making moral judgments, we could get training data by asking humans for their moral judgments. Then we could use the system to make additional moral judgments.

If the test dataset comes from the same distribution as the training dataset, then uniform convergence guarantees can give us nice bounds on the performance on the test set. In reality, the test set will often be different. For a moral judgment system, this could be disastrous: perhaps we only train the classifier on ordinary moral problems, but then the classifier decides whether it is a good idea to tile the universe with tiny smiley faces. At this point, we have no guarantees about whether the classifier will correctly judge this question.

Therefore, I aim to create a system that, when presented with a question, will choose to either answer the question or abort. It should abort when the question is sufficiently different from the training data that the system cannot make reliable judgments.

Mathematical setup

We have some input set $X$. Let $p_{train}:\Delta X$ be the (known) distribution of training data. We train a classifier (or some other system) on the training data, and (using uniform convergence guarantees) estimate that it has good expected performance on random points from $p_{train}$. Afterwards, we will receive test points in $X$. The system can either use the classifier on the test point and make decisions on the basis of this classification, or abort (e.g. by asking a human for their judgment instead of the classifier).

Specifically, suppose there is some unknown cost function $c:X\to R^{+}$. $c\left(x\right)$ represents the cost of using the classifier's judgment on point $x$. Due to uniform convergence guarantees, we have $E_{p_{train}}\left[c\right(X\left)\right]\le 1$ (i.e. it is not very costly to use the classifier on random training points). Also suppose that aborting always has a cost of $k$.

Let $p_{test}:\Delta X$ represent the system's prediction for the next test point. After predicting the next test point, the system chooses a policy $\pi :X\to [0,1]$, which maps each possible input point to the probability that the system will use the classifier for that point.

The total expected cost will then be $E_{p_{test}}\left[\pi \right(X\left)c\right(X)+(1-\pi \left(X\right)\left)k\right]=k-k{E}_{p_{test}}\left[\pi \right(X\left)\right]+E_{p_{test}}\left[\pi \right(X\left)c\right(X\left)\right]$.

The minimax policy

Suppose the system chooses a minimax policy. Then

$$\pi =\arg \underset{\pi }{min}\underset{c,E_{p_{train}}\left[c\right(X\left)\right]\le 1}{max}(k-k{E}_{p_{test}}[\pi \left(X\right)]+E_{p_{test}}[\pi \left(X\right)c\left(X\right)\left]\right)$$ $$=\arg \underset{\pi }{min}(-k{E}_{p_{test}}[\pi \left(X\right)]+\underset{c,E_{p_{train}}\left[c\right(X\left)\right]\le 1}{max}{E}_{p_{test}}[\pi \left(X\right)c\left(X\right)\left]\right)$$

To solve this optimization problem, first consider how to maximize $E_{p_{test}}\left[\pi \right(X\left)\right]$ (i.e. the probability of using the classifier for the next point) subject to the hard constraint on $\pi$ that $\forall c.E_{p_{train}}\left[c\right(X\left)\right]\le 1\to E_{p_{test}}\left[\pi \right(X\left)c\right(X\left)\right]\le d$.

The constraint can be rewritten:

$$\forall c.\frac{E_{p_{test}}\left[\pi \right(X\left)c\right(X\left)\right]}{E_{p_{train}}\left[c\right(X\left)\right]}\le d$$

As explained previously in the post about quantilizers, this constraint is equivalent to $$\forall x\in X.\frac{p_{test}\left(X\right)\pi \left(X\right)}{p_{train}\left(X\right)}\le d$$ or equivalently $$\forall x\in X.\pi \left(X\right)\le d\frac{p_{train}\left(X\right)}{p_{test}\left(X\right)}$$

This constraint states that we may only rarely use the classifier for points that are much more probable under the predicted test distribution than the training distribution.

How can the system maximize $E_{p_{test}}\left[\pi \right(X\left)\right]$ subject to this constraint on $\pi$? Since the constraint is a conjunction of independent constraints for each $x$, and the quantity to be maximized is monotonic in each $pi\left(x\right)$, it is sufficient to maximize each $\pi \left(x\right)$ subject to the constraint that $\pi \left(x\right)\le d\frac{p_{train}\left(X\right)}{p_{test}\left(X\right)}$. But this is achieved by setting $\pi \left(x\right)=min\{1,d\frac{p_{train}\left(X\right)}{p_{test}\left(X\right)}\}$. Therefore, this policy maximizes $E_{p_{test}}\left[\pi \right(X\left)\right]$ subject to the constraint.

Now let's step back and use this fact to solve the original optimization problem. This policy $\pi$ achieves maximum cost $$\underset{c,E_{p_{train}}\left[c\right(X\left)\right]\le 1}{max}{E}_{p_{test}}\left[\pi \right(X\left)c\right(X)+(1-\pi \left(X\right)\left)k\right]$$ $$=k-k{E}_{p_{test}}\left[\pi \right(X\left)\right]+\underset{c,E_{p_{train}}\left[c\right(X\left)\right]\le 1}{max}{E}_{p_{test}}\left[\pi \right(X\left)c\right(X\left)\right]$$ $$=k-k{E}_{p_{test}}[min\{1,d\frac{p_{train}\left(X\right)}{p_{test}\left(X\right)}\left\}\right]+d$$ $$=k{E}_{p_{test}}[max\{0,1-d\frac{p_{train}\left(X\right)}{p_{test}\left(X\right)}\left\}\right]+d$$

To minimize worst-case expected cost, choose $d$ to minimize this quantity, and then set $\pi \left(x\right)=min\{1,d\frac{p_{train}\left(x\right)}{p_{test}\left(x\right)}\}$.

Classifying multiple points

The previous section analyzed the case when we classify a single point $X$. We can apply this strategy repeatedly to classify multiple data points, but this strategy is not necessarily optimal. Instead, the optimal policy is to reject points that will appear more expected times in the data, compared to the probability under the training set. The derivation of this rule follows.

Suppose we will classify multiple data points $X_1,...,X_n$, with joint distribution $p_{test}(X_1,...,X_n)$. We will choose the policy ${\pi }_i:X^i\to [0,1]$, where ${\pi }_i(X_1,...,X_{i-1},X_i)$ is the probability of using the classification of point $X_i$ given the previous points $X_1,...,X_{i-1}$. All ${\pi }_i$ will be chosen to jointly minimize the maximum possible total expected cost

$$\underset{c:E_{p_{train}}\left[c\right(X\left)\right]\le 1}{max}{E}_{p_{test}}\left[\sum _{i=1}^n\right(\pi \left(X_i\right)c\left(X_i\right)+(1-\pi (X_i\left)\right)k\left)\right]$$

Due to linearity of expectation, this can be decomposed $$\underset{c:E_{p_{train}}\left[c\right(X\left)\right]\le 1}{max}\sum _{i=1}^n{E}_{p_{test}}\left[\pi \right(X_i\left)c\right(X_i)+(1-\pi \left(X_i\right)\left)k\right]$$ $$

\max_{c : \mathbb{E}{p{train}}[c(X)] \leq 1} \sum_{i=1}^n (k - k \mathbb{E}{p{test}}[\pi(X_i)] + \mathbb{E}{p{test}}[\pi(X_i) c(X_i)])

nk - k \sum_{i=1}^n \mathbb{E}{p{test}}[\pi_i(X_1, ..., X_i)] + \max_{c : \mathbb{E}{p{train}}[c(X)] \leq 1} \sum_{i=1}^n \mathbb{E}{p{test}}[\pi_i(X_1, ..., X_i) c(X_i)]

nk - k \sum_{i=1}^n \sum_{x \in \mathcal{X}} p_{test}(X_i = x)\mathbb{E}{p{test}}[\pi_i(X_1, ..., X_{i-1}, x)] + \max_{c : \mathbb{E}{p{train}}[c(X)] \leq 1} \sum_{i=1}^n \sum_{x \in \mathcal{X}} p_{test}(X_i = x) \mathbb{E}{p{test}}[\pi_i(X_1, ..., X_{i-1}, x)] c(x)

nk - k \sum_{x \in \mathcal{X}} \sum_{i=1}^n p_{test}(X_i = x) \mathbb{E}{p{test}}[\pi_i(X_1, ..., X_{i - 1}, x)] + \max_{c : \mathbb{E}{p{train}}[c(X)] \leq 1} \sum_{x \in \mathcal{X}} c(x) \sum_{i=1}^n p_{test}(X_i = x) \mathbb{E}{p{test}}[\pi_i(X_1, ..., X_{i-1}, x)] $$

In this term, each use of $\pi$ appears in an expression of the form ${\sum }_{i=1}^n{E}_{p_{test}}\left[{\pi }_i\right(X_1,...,X_{i-1},x\left)\right]$. This means that the only features of $\pi$ relevant to expected cost are ${\sum }_{i=1}^n{p}_{test}(X_i=x)E_{p_{test}}\left[{\pi }_i\right(X_1,...,X_{i-1},x\left)\right]$ for each $x\in X$. Define $\alpha \left(x\right)={\sum }_{i=1}^n{p}_{test}(X_i=x)$. The sum must be between 0 and $\alpha \left(x\right)$, and any value in this interval can be achieved using a ${\pi }_i$ which ignores both $i$ and its first $i-1$ inputs (i.e. ${\pi }_i(x_1,...,x_i)=\beta \left(x_i\right)$ for some $\beta :X\to [0,1]$. $\beta \left(x\right)$ is the probability of using the classification of a point $x$, regardless of which iteration it is encountered on). Therefore, an optimal policy of this form exists, and we can rewrite the expected total cost as

$$nk-k\sum _{x\in X}\alpha \left(x\right)\beta \left(x\right)+\underset{c:E_{p_{train}}\left[c\right(X\left)\right]\le 1}{max}\sum _{x\in X}c\left(x\right)\alpha \left(x\right)\beta \left(x\right)$$

As before, suppose we have a hard constraint that $$\forall c.E_{p_{train}}\left[c\right(X\left)\right]\le 1\to \sum _{x\in X}c\left(x\right)\alpha \left(x\right)\beta \left(x\right)\le d$$ and we want to maximize ${\sum }_{x\in X}\alpha \left(x\right)\beta \left(x\right)$. Just as the original constraint $$\forall c.E_{p_{train}}\left[c\right(X\left)\right]\le 1\to E_{p_{test}}\left[\pi \right(X\left)c\right(X\left)\right]\le d$$ could be rewritten as $$\forall x\in X.p_{test}\left(x\right)\pi \left(x\right)\le d{p}_{train}\left(x\right)$$ this constraint can be rewritten as $$\forall x\in X.\alpha \left(x\right)\beta \left(x\right)\le d{p}_{train}\left(x\right)$$ To maximize ${\sum }_{x\in X}\alpha \left(x\right)\beta \left(x\right)$ subject to this constraint, just maximize each term $\alpha \left(x\right)\beta \left(x\right)$ subject to $\alpha \left(x\right)\beta \left(x\right)\le d{p}_{train\left(x\right)}$ for each $x$. This is achieved by setting $\beta \left(x\right)=min\{1,d\frac{p_{train}\left(x\right)}{\alpha \left(x\right)}\}$.

Now this policy achieves maximum expected cost $$nk-k\sum _{x\in X}\alpha \left(x\right)\beta \left(x\right)+d$$ $$

nk - k \sum_{x \in \mathcal{X}} \alpha(x) \min{1, d \frac{p_{train}(x)}{\alpha(x)}} + d

nk - k \sum_{x \in \mathcal{X}} \min{\alpha(x), d p_{train}(x)} + d $$

So to minimize the original expected cost, it is sufficient to choose $d$ to minimize this quantity, and then choose ${\pi }_i(x_1,...,x_i)=min\{1,d\frac{p_{train}\left(x\right)}{\alpha \left(x\right)}\}$.

Extensions and questions for future research

• These bounds rely on the cost decomposing as a sum of costs for each iteration. How problematic is this assumption, and how might we drop it? This problem is also discussed in the post about quantilizers.
• Here, the uniform convergence guarantee is only about a single distribution, $p_{train}$. In practice, the same classifier may have good performance on many different distributions. It should be possible to use these additional bounds to use the classifier on a wider range of test points.
• The analysis does not handle the case when the policy ${\pi }_i$ affects the distribution of $X_j$ for any $j>i$.
• It is somewhat worrying that the system uses the classification of every point with some probability. This is justified under certain adversarial assumptions, but it indicates some flaw in this approach, and fixing it in a principled manner might yield a better system.
• This system requires an accurate Bayesian prediction module. It should be possible to adapt this system to work under pessimistic assumptions about predictions (e.g. choosing a minimax policy if we have many predictors and only one is guaranteed to be accurate).
• If the data points contain timestamps, then the test data will always be identifiably different from the training data (since they have higher timestamps). This is a problem, because then the system will almost always reject new points. There might be some additional constraints we could place on the classifier to prevent this from being a problem.
• If we predict that we will see some class of points in the test data, and we do not have enough training data to know how to classify these points, perhaps it would be good to ask the user about some points in this class (i.e. active learning). It might be interesting to look at active learning in this framework.