Authors: Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai, Omar Montasser
<aside> 💡
MAIN IDEA
This paper proposes two algorithms that bounds both error and rejection rate for selective classifiers in both a PQ and transductive setting.
</aside>
We consider the setup in which our test examples are drawn from a different distribution than our training examples. These test examples could be chosen from an adversary or drawn from some distribution not equal to ours. Clearly, learning entirely arbitrary test examples well is not possible, however, by combining both selective classifiers and transductive learning we create a redaction.
Redaction can be done when unlabeled test examples are available in advance, but also can be done in retrospect. Note that this model assumes that the target function $f$ is the same at train and test time.
Selective classification extends the standard output space to include a “reject” or decline to answer option, towards a general goal of low test error with minimal rejections. Most existing work considers the case of $P = Q$, i.e. the training distribution is the same as the test distribution with the exception of online **selective classification.
Transductive learning is an approach to learning problems that weakens the goal of generalizing to all unseen data, to good performance on a specific unlabeled test set. While this can harm generalization, it can lead to higher accuracy and more efficient use of data when applied in the correct settings. A useful assumption is that the unlabeled examples greatly outnumber the training examples.
We seek to learn a target function $f \in C$ with VC Dimension $d$ and training distribution $P$ over $X$.
Performance is measured by rejection($R_D$) and error rates ($\text{err}_D(h|_S))$.
$$ R_D(S) = Pr_{x-D}[x \notin S] $$
$$ \text{err}_D(h|S) = Pr{x-D}[h(x) \neq f(x) \land x \in S] $$