  Model deficiency that results from incomplete training data is a form of
structural blindness that leads to costly errors, oftentimes with high
confidence. During the training of classification tasks, underrepresented
class-conditional distributions that a given hypothesis space can recognize
results in a mismatch between the model and the target space. To mitigate the
consequences of this discrepancy, we propose Random Test Sampling and
Cross-Validation (RTSCV) as a general algorithmic framework that aims to
perform a post-training model rectification at deployment time in a supervised
way. RTSCV extracts unknown unknowns (u.u.s), i.e., examples from the
class-conditional distributions that a classifier is oblivious to, and works in
combination with a diverse family of modern prediction models. RTSCV augments
the training set with a sample of the test set (or deployment data) and uses
this redefined class layout to discover u.u.s via cross-validation, without
relying on active learning or budgeted queries to an oracle. We contribute a
theoretical analysis that establishes performance guarantees based on the
design bases of modern classifiers. Our experimental evaluation demonstrates
RTSCV's effectiveness, using 7 benchmark tabular and computer vision datasets,
by reducing a performance gap as large as 41% from the respective
pre-rectification models. Last we show that RTSCV consistently outperforms
state-of-the-art approaches.
