Exploratory Machine Learning with Unknown Unknowns*
Peng Zhao, Yu-Jie Zhang, Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology,
Nanjing University, Nanjing 210023, China{zhaop, zhangyj, zhouzh}@lamda.nju.edu.cn

low-confidence region

Abstract
In conventional supervised learning, a training dataset is given
with ground-truth labels from a known label set, and thelearned model will classify unseen instances to known labels.
In real situations, when the learned models do not work well,learners generally attribute the model failure to the inadequate
selection of learning algorithms or the lack of enough labeledtraining samples. In this paper, we point out that there is an
important category of failure, which owes to the fact that there
are unknown classes in the training data misperceived as otherlabels, and thus their existence is unknown from the given
supervision. Such problems of unknown unknown classes canhardly be addressed by common re-selection of algorithms oraccumulation of training samples. For this purpose, we propose the exploratory machine learning, where in this paradigm
once learner encounters unsatisfactory learning performance,
she can examine the possibility and, if unknown unknowns
really exist, deploy the optimal strategy of feature space augmentation to make unknown classes observable and be enabled
for learning. Theoretical analysis and empirical study on bothsynthetic and real datasets validate the efficacy of our proposal.

1

Introduction

Machine learning has achieved great success in many realworld applications. The success heavily relies on the suitablelearning algorithm and sufficient supervised training data.
Therefore, facing model failure, the learner would always
doubt the inadequate selection of algorithms and the lackof data. A common practice is to try other algorithms oraccumulate more data, and such an approach could work
effectively when there are no other factors leading to thefailure. In this paper, however, we point out that there is
an important cause of model failure always ignored before:
unknown unknowns hidden in the training dataset.
Specifically, we attribute the unknown unknowns to thefact that some training instances of certain unknown classes
are wrongly perceived as others, and thus appear unknown to
the learned model with the given supervision. This is always
the case when the label space is misspecified due to the insufficient feature information. Consider the task of medical
diagnosis, where we need to train a model for community* This research was supported by NSFC (61921006).

Copyright © 2021, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

asthmapneumonia

lungcancerground-truthlabel space

asthmacommunity
healthcare centerspneumonia

knownlabel space

asthmapneumonia
lung cancer

Figure 1: Unknown unknowns in medical diagnosis tasks. Patientswith lung cancer are misdiagnosed as asthma or pneumonia due tothe lack of CT scan devices, and thus appear as unknown to learned
model. So “lung cancer” class becomes invisible in training data.
healthcare centers based on their patient records, to help diagnose the cause of a patient with cough and dyspnea. As
shown in Figure 1, there are actually three causes: two common ones (asthma and pneumonia), as well as an unusual
one (lung cancer) whose diagnosis crucially relies on thecomputerized tomography (CT) scan device, yet too expensive to purchase. Thus, the community healthcare centers
are not likely to diagnose patients with dyspnea as cancer,
resulting in that the class of “lung cancer” becomes invisible
and hidden in the collected training dataset. As a result, thelearned model will be unaware of this unobserved class.
Similar phenomena occur in many other applications. For
instance, the trace of a new-type aircraft was mislabeled as
old-type ones until performance of aircraft detectors is foundpoor (i.e., capability of collected signals is inadequate), andthe officer suspects that there are new-type aircrafts unknown
previously. When feature information is insufficient, there
is a high risk to misperceive some classes of training data
as others, leading to existence of hidden classes. Especially,
hidden classes are sometimes of more interest, like in above
two cases. Thus, it is crucial to discover hidden unknownclasses and classify known classes well simultaneously.
Conventional supervised learning (SL) cannot obtain asatisfied model when such unknown unknowns emerge in the
training dataset, even if we could accumulate more data andre-select algorithms exhaustively. The reason lies in that theunknown factors are beyond the expressivity of training data.
We thus require new ideas to tackle such unknown unknowns.

2

ExML: A New Learning Framework

The problem we are concerned with is essentially a classof unknown unknowns. In fact, how to deal with unknown

known classes:

class 1

misperceived
hidden class:hiddenlow-confidence region

Conventional Supervised Learning
environments

observabledatasettest sample

exploitmodel

predictclass 2

Exploratory Machine Learning

augment
featureexplore more features
environments

operational
datasettest sample

exploitoriginal feature spacemodel
discoverFigure 2: An example illustrates that an informative feature
can substantially improve separability of low-confidence samples and make the hidden class distinguishable.

Figure 3: Comparison of two frameworks. SL exploits observable dataset for prediction. ExML explores more features
based on operational dataset for discovery of hidden classes.

unknowns is the fundamental question of robust artificial
intelligence (Dietterich 2017), and many studies have been
devoted to addressing various aspects including changing distributions (Pan and Yang 2010; Gama et al. 2014), evolvablefeatures (Hou, Zhang, and Zhou 2017; Hou and Zhou 2018),
open categories (Scheirer et al. 2013; Geng, Huang, and Chen
2018), etc. Different from them, we study a new problem setting ignored previously, that is, the training dataset is badly
advised by the incompletely perceived label space due to theinsufficient feature information. This problem turns out tobe quite challenging, since feature space and label space areentangled and both of them are unreliable.
The first challenge is that when the learning performanceis undesired we do not know whether the issue is caused by
the hidden unknown classes or not. To tackle that, we may
accumulate more training data and re-select the learning algorithms. If the model failure persists, we would suspect theexistence of unknowns. The second challenge is how to recognize the hidden unknown classes. Notably, it is infeasible tomerely pick out instances with low predictive confidence as
hidden classes, since we can hardly distinguish (i) instancesfrom hidden classes that suffer from low-confidence predictions owing to the incomplete label space; (ii) instances fromknown classes that suffer from low-confidence predictions
because of insufficient feature information. This characteristic reflects intrinsic hardness of learning with unknown
unknowns due to feature deficiency, and thus it is necessary
to ask for external feature information.

learner will then realize that there exists an additional classhidden in training data previously due to feature deficiency.
Enlightened by the above example, we introduce a newlearning framework called exploratory machine learning(ExML), which explores more feature information to deal
with unknown unknowns caused by feature deficiency. The
terminology of exploratory learning is originally raised in
the area of education, defined as an approach to teaching andlearning that encourages learners to examine and investigate
new material with the purpose of discovering relationships between existing background knowledge and unfamiliar content
and concepts (Njoo and De Jong 1993; Spector et al. 2014).
In the context of machine learning, our proposed framework
encourages learners to examine and investigate the training dataset via exploring new feature information, with the
purpose of classifying known classes and discovering potentially hidden classes. Figure 3 compares the proposed ExML
to conventional supervised learning (SL). Conventional SL
views the training dataset as an observable representation ofenvironments and exploits it to train a model to predict thelabel. By contrast, ExML considers the training dataset is
operational, where learners can examine and investigate thedataset by exploring more feature information, and thereby
discover unknown unknowns due to feature deficiency.
We develop an approach to implement ExML, consistingof three ingredients: rejection model, feature exploration,and model cascade. The rejection model identifies suspicious
instances that potentially belong to hidden classes. Feature exploration guides which feature should be explored, and thenretrains the model on the augmented feature space. Modelcascade allows a layer-by-layer processing to refine the selection of suspicious instances. Theoretical analysis is provided
to justify the superiority of the proposed framework. We
present empirical evaluations on synthetic data to illustrate
the idea and further validate the effectiveness on real datasets.

2.1

Exploratory Machine Learning

To handle unknown unknowns caused by feature deficiency,
we resort to the human in the learning loop to interact withenvironments for enhancing the data collection, more specifically, actively augmenting the feature space. The idea isthat when a learned model remains performing poorly evenfed with much more data, learner will suspect existence ofhidden classes and subsequently seek several candidate features to augment. Figure 2 shows a straightforward example
that learner receives a dataset and observes that there are
two classes with poor separability, resulting in a noticeable
low-confidence region. After a proper feature augmentation,

2.2

Problem Formulation

Training Dataset. The learner receives a training dataset
b tr = {(bbi )}mbi ∈ Xb ⊆ Rd is from theDxi , yi=1 , where xbi ∈ Yb is from the incomplete
observed feature space, and ylabel space with N known classes. We consider the binary

case for simplicity. Note that there exist training samples
that are actually from hidden classes yet wrongly labeled asknown classes due to feature deficiency.

initial model learning
original
datasetTesting Stage. Suppose the learner identifies the best feature as ci , he/she will then augment the testing sample
with this feature, leading to the augmented feature space
Xi = (Xb ∪ X i ) ⊆ Rd+1 where X i is the feature space of
ci . The learned model requires to predict the label of theaugmented testing sample, either classified to one of knownclasses or discovered as the hidden classes (abbrev. hc).
We finally note that several assumptions are introduced forsimplicity, with the aim of avoiding distractions of an overcomplicated setting and better understanding the essence ofthe new problem. Actually, our proposal still works whenrelaxing these assumptions by borrowing well-known techniques such as multi-class rejection (Zhang, Wang, and Qiao2018), learning with non-uniform cost (Seldin et al. 2014).
We emphasize that above aspects are not the current focus.
These extensions will be considered as future works.

3

A Practical Approach

Due to the feature deficiency, the learner might be even unaware of the existence of hidden classes based on the observed training data. It is thus necessary to introduce theassumption that instances with high predictive confidence aresafe, i.e., they will be correctly predicted as one of knownclasses. Learner will suspect the existence of hidden classes
when the learned model performs badly.
We justify the necessity of above assumption. Actually,
there are some previous works studying the problem of highconfidence false predictions without considering the issue offeature deficiency (Attenberg, Ipeirotis, and Provost 2015;
Lakkaraju et al. 2017), in which there exist some instances
wrongly predicted with high confidence. Since the model’s
performance is highly unreliable, to rectify that, they assume
the existence of an oracle providing ground-truth labels forthe given query. However, in present of feature deficiency as
in our scenario, the problem would not be tractable unlessthere is an oracle able to provide ground-truth labels basedon the insufficient feature information, which turns out tobe an even stronger assumption that does not hold in reality
generally. We leave high-confidence unknown unknowns dueto the insufficient feature as future work to explore.
On the other hand, we emphasize that the introduced
assumption does not trivialize the problem because lowpredictive instances are not necessarily from hidden classesfeatureexploration

augmented
datasetaugmented model
learning

known
class

initialmodel

rejectedsamplesmodel cascade

Candidate Features and Cost Budget. Besides the training
dataset, the learner can access a set of candidate features
C = {c1 , . . . , cK }, whose values are unknown before acquisition. For the example of medical diagnosis (Figure 1), a
feature refers to signals returned from CT scan devices, only
available after patients have taken the examination. Moreover, a certain cost will be incurred to acquire any candidatefeature for any sample. The learner aims to identify top k informative features from the pool under a given budget B. For
convenience, the cost of each acquisition is set as 1 uniformly
and the learner desires to find the best feature, i.e., k = 1.

testing samples

augmented
model

known
class

unknown class

Figure 4: Overall procedure of ExML. Our approach begins withan initial model (blue part), followed by exploring the best candidatefeature (green part). Afterwards, a model is retrained based on theaugmented dataset, and finally cascaded with the initial model todiscover the hidden class (red part).

(as explained at the beginning of Section 2), which necessities more efforts. Following the methodology of ExML
(examining the training dataset via exploring new feature
information), we design a novel approach, which consists ofthree components: rejection model, feature exploration, andmodel cascade. Figure 4 illustrates main procedures, and wewill describe details of each component subsequently.

3.1

Rejection ModelAs shown in Figure 4, the learner starts from training an initialmodel on the original dataset, with capability of identifying
low-confidence instances. As emphasized previously (cf. thebeginning of Section 2), these low-confidence instances could
come from either known or hidden classes, so they are only
detected as suspicious and will be further refined.
We realize this goal by the learning with rejection technique (Cortes, DeSalvo, and Mohri 2016b), where the learned
model will abstain from predicting instances whose maximum conditional probability lower than a given value 1 − θ.
More precisely, we learn a function pair f = (h, g), whereh : Xb 7→ R is the predictive function for known classes andg : Xb 7→ R is the gate function to reject the hidden class. The
b is identified to the hidden class if g(bsample xx) < 0, andotherwise to the class of sign(h(bx)). Such rejection models
can be trained via optimizing the following objective:b, yb ; θ)],
minf E(bx,by)∼Db [`0/1 (f, x

(1)

b, y
b ; θ) = 1yb·h(bx)<0 · 1g(bx)>0 + θ · 1g(bx)≤0
where `0/1 (f, xis the 0-1 loss of the rejection model f parameterized byb is the data distribution
the threshold θ ∈ (0, 0.5) and Db A smaller θ will lead to more rejections but
over Xb × Y.
a higher predictive accuracy on known classes. To tackle

g samples

known
class

nitialmodel

gmentedmodel

original feature
𝑥𝑥1

model cascadedsselected
𝑓𝑓1

𝑓𝑓2

𝑓𝑓3

𝑦𝑦

…
…
…

𝑥𝑥𝑚𝑚

known
class

original features

queried candidate features

Figure 5: Feature Exploration

own classthe difficulty of non-convex optimization arising from theindicator function, Cortes, DeSalvo, and Mohri (2016b)
introduce the following calibrated surrogate loss functionb, yb; θ) defined as`surr := `surr (f, x
n

1
g(b
x)  ox) − yb · h(bx) , θ 1 −,0`surr = max 1 + g(b2
1 − 2θ
to approximate the original `0/1 loss. Since the distribution
is unknown we cannot directly measure the risk, we choose
the model that minimizes the empirical risk:m

1 X
bi , ybi ; θ)+Ch khk2H +Cg kgk2H , (2)`surr (f, xf ∈H×H mi=1minwhere Ch and Cg are regularization parameters, and H is the
RKHS induced by kernel K : Xb×Xb 7→ R. By the representer
theorem (Schölkopf and Smola
Pm2002), the optimizer of (2)bi ) and g(b
is
in
the
form
of
h(b
x
)
=
x, x
x) =
i=1 ui K(b
Pm
b
w
K(b
x
,
x
),
where
u
and
w
are
coefficientstolearn.
iii
i=1 i
So (2) can be reformulated as quadratic programming andsolved efficiently. For more details we refer the reader to theseminal work of Cortes, DeSalvo, and Mohri (2016b).

3.2

Feature Exploration

If the initial model is unqualified (for instance, it rejects too
many samples for achieving desired accuracy), the learner
will suspect the existence of hidden classes and explore newfeatures to augment. In our setting, the learner requires toselect the best feature from K candidates and retrain a model
based on the augmented data, as shown in Figure 5.
We emphasize that the conventional feature selection is not
feasible here, because it requires to know values of candidatefeatures, while these values are unknown before acquisitions.
To address the challenge, we propose a novel procedure—feature exploration—to adaptively identify the most informative feature under the cost budget, without requiring feature
values in advance. To address the issue, there are two fundamental questions to answer:(1) how to measure the quality of candidate features?
(2) how to allocate the budget to identify the best feature?
We answer the above two questions in the following.
Feature quality measure. Denote by Di the data distributionb where Xi is the augmented feature space of theover Xi × Y,

i-th candidate feature. We use the Bayes risk on Di as feature
quality measure:b ; θ) , (3)Ri∗ = Ri (fi∗ ) = minf E(x,by)∼Di `0/1 (f, x, y
where Ri (f ) is the expected 0/1 risk of function f over
Di , and fi∗ minimizes Ri (f ) over all measurable functions.
The Bayes risk essentially reflects the minimal error that any
rejection model can attain on the augmented data distribution,
whose value will be smaller when the selected augmented
feature improves the separability more significantly (and isbelieved more informative).
Due to the inaccessibility of the underlying distribution
Di , we approximate the Bayes risk by its empirical versionibj )}nj=1
over the augmented data Di = {(xj , y∼ Di ,Xni
bD = Rbi (fbi ) =R`0/1 (fbi , xj , ybj ; θ),
(4)
i
j=1

b and fbi is the rejection model learned
bj ∈ Y,
where xj ∈ Xi , yby empirical risk minimization over surrogate loss (2) on augmented dataset Di . Based on the feature quality measure (3)and its empirical version (4), we now introduce the budget
allocation strategy to identify the best candidate feature.
Budget allocation strategy. Without loss of generality, suppose features are sorted according to their quality, i.e., R1∗ ≤∗. Our goal is to identify the best feature within· · · ≤ RK
the limited budget, and meanwhile the model retrained on
augmented data should have good generalization ability.
We first propose the uniform allocation strategy as follows,
under the guidance of criterion (3).
Uniform Allocation For each candidate feature ci , i ∈[K], learner allocates bB/Kc budget and obtains an augmented dataset Di . So we can compute the empirical feature
measure by (4), and select the feature with the smallest risk.
The above strategy is simple yet effective, which can provably
identify the best feature with high probability (Theorem 1).
Median Elimination We further propose another variant
inspired by the bandit theory to improve the budget allocation
efficiency. Specifically, we adopt the technique of medianelimination (ME) (Even-Dar, Mannor, and Mansour 2006),
which removes one half of poor candidate features after every
iteration and only the best one remains in the end. As aresult, the algorithm can avoid allocating too many budgets
on poor features. More specifically, the elimination proceeds
in T = dlog2 Ke episodes, in each episode, bB/T c budget
is allocated uniformly to all remaining candidate features,and the learner could query their values for updating thebD iscorresponding augmented datasets Di . Then, the score Ricalculated on the current augmented datasets Di and the halfbD are eliminated. In the last, only one
features with high R
icandidate feature is will be left and its augmented dataset Dis
contains around bB/ log Kc samples, which is the largest
one among all the candidate features. Algorithm details arepresented in Appendix B.
As shown in Figure 5, poor features are eliminated earlier,budget left for the selected feature is thus improved frombB/Kc to bB/ log Kc by ME, which ensures better generalization ability of the learned model. Meanwhile, median elimination can explore the best candidate feature more efficiently

than uniform allocation, as shown in the bandit theory (EvenDar, Mannor, and Mansour 2006). We finally remark that ourpaper currently focuses on the best feature, and the framework is ready for identifying the top k features (k > 1) byintroducing more sophisticated techniques (Kalyanakrishnan
et al. 2012; Chen, Li, and Qiao 2017).

3.3

Model Cascade

After feature exploration, learner will retrain a model on augmented data. Considering that the augmented model might
not always be better than the initial model, particularly when
the budget is not enough or candidate features are not quite
informative, we propose the model cascade mechanism tocascade the augmented model with the initial one. Concretely,
high-confidence predictions are accepted in the initial model,
the rest suspicious are passed to the next layer for feature
exploration, those augmented samples with high confidence
will be accepted by the augmented model, and the remaining
suspicious continue to the next layer for further refinements.
Essentially, our approach can be regarded as a layer-bylayer processing for identifying instances of hidden classes,
and the procedures can be stopped until human discovers remaining suspicious are indeed with certain hidden structures.
For simplicity, we only implement a two-layer architecture.

4

Theoretical Analysis

This section presents theoretical results. We first investigate
the attainable excess risk of supervised learning, supposingthat the best feature were known in advance. Then, we provide
the result of ExML to demonstrate the effectiveness of our
proposed criterion and budget allocation strategies.
For each candidate feature ci , we denote the corresponding
hypothesis space as Hi , Gi = {x 7→ hw, Φi (x)i | kwkHi ≤Λi }, where Φi and Hi are induced feature mapping and
RKHS of kernel Ki in the augmented feature space.
Supervised learning with known best feature. Suppose thebest feature were known in advance, we could obtain B
samples augmented with this particular feature. Let fSL be
the model learned by supervised learning via minimizing (2).
From learning theory literatures (Bousquet, Boucheron, andLugosi 2003; Cortes, DeSalvo, and Mohri 2016b), for any
δ > 0, with probability at least 1 − δ, we haver
r(κ1 Λ1 )2log(1/δ)∗R1 (fSL ) − R1 ≤ O++ Rap ,
B
2B
(5)
where Rap = Cθ (inf f ∈H1 ×G1 R1surr (f ) − inf f R1surr (f ))is the approximation error measuring how well hypothesis
spaces H1 , G1 approach the target, in terms of the expectedb ; θ)]. The
surrogate risk R1surr (f ) = E(x,by)∼D1 [`surr (f, x, y
constant factor is Cθ = 1/((1 − θ) · (1 − 2θ)).
The above result theoretically reveals that if the best feature
were known in advance, the excess risk of supervised learning
would converge
to the inevitable approximate error in the rate√of O(1/ B), with a given feature budget B.
Exploratory learning with unknown best feature. In our
setting, the best feature is unfortunately unknown ahead oftime. More importantly, since values of K candidate features

are unavailable, it is infeasible to perform the feature selection. We show that by means of ExML (featurep
exploration),
the excess risk also converges, in the rate of O( K/B), yet
without requiring to know the best feature.
Theorem 1. Let cis be the identified feature and fbis be theaugmented model returned by E X ML with uniform allocation. Then, with probability at least 1 − δ, we have
s
s

2
(κΛ)
log(3/δ)∗b
Ris (fis ) − R1 ≤ O++ Rap ,bB/Kc
2bB/Kc(6)where Λ = maxi∈[K] Λi , κ = maxi∈[K] supx∈Xi Ki (x, x).
Remark. Comparing the excess risk bounds of (5) and (6),
we can observe that ExML exhibits a similar convergencetendency to SL with known best feature,√yet without requiring to know the best feature. An extra K times factor ispaid for exploration of the best feature. We note that undercertain mild technical√ assumptions, the dependence can befurther reduced to log K by median elimination (Even-Dar,
Mannor, and Mansour 2006), as poor candidate features havebeen removed in the earlier episodes.

5

Experiments

In this section, we conduct experiments to examine empiricalperformance of the proposed exploratory machine learning(ExML). Specifically, we provide evaluations on synthetic
data for visualizing the superiority of ExML to conventional
supervised learning in handling unknown unknowns. Then,
we report results on real-world datasets to demonstrate theeffectiveness of the overall method, as well as the usefulnessof feature exploration and model cascade modules. In all
experiments, we denote by B = b·mk the feature explorationbudget, where m is number of training samples, K is numberof candidate features, b ∈ [0, 1] is the budget ratio.

5.1

Synthetic Data for Illustration

We first illustrate the advantage of exploratory machine learning over conventional supervised learning in discovering thehidden classes on the synthetic data.
Setting. Following the illustrative example in Figure 1, we
generate a 3-dim dataset containing 3 classes, whose groundtruth distribution is shown as Figure 6(a). However, as shownin Figures 6(b), only the first two dimensions are observablein the training stage, resulting in a hidden class (hc) locatedin the intersection area of known classes (kc1 and kc2).
Specifically, we generate instances of each class fromGaussian distributions. Means and variances are [−a, 0, −z]and σ · I3×3 for the first known class, [a, 0, z] and σ · I3×3 forthe second known class as well as [0, 0, 0] and σ/2 · I3×3 forthe hidden class, where I3×3 is a 3 × 3 identity matrix. We
set σ = 3a and z = 5a. In the training stage, the third-dim isunobservable and the hidden class (hc) is randomly labeled
as another two. Each class contains 100 instances in the training data. Besides, we generate 9 candidate features in various
qualities, whose angle to the horizon varies from 10◦ to 90◦ ,the larger the better. Figure 6(c) plots the augmented feature
space via t-SNE. The budget ratio is b = 20%. In the testingclass 1class 2class 3(a) ground-truth

kc 1
kc 2

10°

30°

60°

90°

hc
hc

(b) training data(c) candidates

Figure 6: Visualization of synthetic data: (a) ground-truth distribution; (b) training data (only first two dimensions are observable); (c)t-SNE of candidate features with various qualities (a larger angle
implies a better feature quality).
120
100
80
60

class 1class 2class 3class 1class 2class 34020
010° 20° 30° 40° 50° 60° 70° 80° 90°(a) SL(b) E X ML(c) allocation

Figure 7: Visualization of results: (a) SL; b) ExML; (c) budget
allocation of ExML with median elimination.

stage, the learner requires to predict on the 3-dim data, where
the third dimension is the selected candidate features.
Contenders. We compare ExML to SL (with rejection
model). For all rejection models, we employ the Gaussian
kernel K(xi , xj ) = exp(−kxi − xj k22 /γ) with bandwidthγ = medianxi ,xj ∈D (kxi − xj k22 ) and set Ch , Cg to 1.
• SL trains the rejection model (Cortes, DeSalvo, and Mohri
2016b) with the given dataset on the original feature space,following the paradigm of conventional supervised learning. The threshold θ is choose as one achieving best accuracy on the testing data from the pool [0.1, 0.2, 0.3, 0.4].
• ExML is our proposal with cascade models and using
median elimination for feature exploration. The thresholdfor the initial rejection model is selected by cross validation
to ensure 95% accuracy on high-confidence samples. The
threshold θ for the augmented rejection model is choose
as one achieving best accuracy on the testing data from thepool [0.1, 0.2, 0.3, 0.4]. The budget ratio is 20%.
Results. We first conduct SL to train a rejection model basedon the 2-dim training data, and then perform E X ML to actively augment the feature within the budget to discoverunknown unknowns. Figures 7(a) and 7(b) plot the results,
demonstrating a substantial advantage of E X ML over SL indiscovering the hidden class and predicting known classes.
Furthermore, Figure 7(c) reports budget allocation of eachcandidate feature over 50 times repetition. We can see thatthe allocation clearly concentrates to more informative features (with larger angles), which validates the effectivenessof median elimination for the best feature exploration.

5.2

Benchmark Data for Evaluation

Dataset and Setting. We further evaluate on a UCI benchmark dataset Mfeat (van Breukelen et al. 1998), which is amulti-view dataset1 containing 2000 samples and 6 viewsof features extracted by various methods. Their semantic
information and statistics are:• Fac: profile correlations, 216-dim;• Pix: pixel averages in 2 × 3 windows, 240-dim;• Kar: Karhunen-Love coefficients, 64-dim;• Zer: Zernike moments, 47-dim;• Fou: Fourier coefficients of the character shapes, 76-dim;• Zer: morphological features, 6-dim.
The domain knowledge sorts the features by their quality as:
Fac > Pix > Kar > Zer > Fou > Mor, in a descending order.
In the training stage, we randomly sample 600 instances
to form the labeled training data. This procedure repeats 10
times to generate different configurations. Since Mfeat is amulti-class dataset, we randomly sample 5 configurations
to convert it into the binary classification task, where each
known class and hidden class contain three original classes,
and the instances from the hidden class are randomly mislabeled as one of known classes. There are in total 50 random
configurations for training. As for the candidate features,
each one of six views (features) is taken as original featureand the rest are prepared in the candidate set. Before training,
we normalize all the features to the range [0, 1]. We evaluate
all contenders on the testing data containing 1400 instances.
Contenders. Apart from SL, we include two ExML variants:ME
E X MLUA
csd and E X ML aug for ablation studies. Here aug/csd
denotes the final model is only the augmented or cascadedwith the initial model; UA/ME refers to feature exploration
by uniform allocation or median elimination.
• E X MLUA
csd is our proposal with cascade model and using
uniform allocation for feature exploration.
• E X MLME
aug is our proposal without cascade model and using median elimination for feature exploration.
All ExML-type methods use the same parameters. SL and
ExML are configured by the same setting as those in synthetic
experiments. The budget ratio b varies from 10% to 30%.
Measure. We measure the performance of all the methods
by the classification. Additionally, we introduce the recall tomeasure the effectiveness of feature exploration, defined as
the ratio of the number of cases when identified feature is
one of its top 2 features to the total number.
• Accuracy: the mean and standard deviation of the predictive accuracy on testing dataset over 50 configurations,where the true label of hidden classes are observable.
• Recall: the ratio of the number of cases when identified
feature is one of top 2 features to the total number, wherefeatures quality is measured by the accuracy of augmented
model trained on whole data with this particular feature.
Results. Table 1 reports mean and std of the predictive accuracy, and all features are sorted in descending order by their
quality. We first compare SL to (variants of) ExML. Whenthe original features are in high quality (Kar, Pix, Fac), SL
could achieve favorable performance and there is no need to
explore new features. However, in the case where uninformative original features are provided, which is of more interest
for ExML, SL degenerates severely and E X MLME
aug (the single
1

http://archive.ics.uci.edu/ml/datasets/Multiple+Features0.90

scending qualities. Bold font indicates algorithms significantly outperforms than others (paired t-test at 95% significance level).

0.85

BudgetSLE X MLME
aug

E X MLUA
csd

E X ML

Recall

0.75

10%
20%
30%

93.39 ± 1.66
93.39 ± 1.66
93.39 ± 1.66

71.80 ± 9.55
82.26 ± 7.52
89.29 ± 4.72

92.39 ± 2.79
91.95 ± 3.32
92.20 ± 3.33

92.40 ± 2.78
92.00 ± 3.27
92.50 ± 2.86

48%
46%
44%

0.70

Pix

10%
20%
30%

92.19 ± 2.47
92.19 ± 2.47
92.19 ± 2.47

70.53 ± 8.27
81.70 ± 7.16
88.67 ± 4.14

90.54 ± 6.27
90.84 ± 6.17
90.45 ± 5.74

90.55 ± 6.31
90.87 ± 6.09
91.82 ± 4.26

58%
54%
68%

0.60
0.05

Kar

10%
20%
30%

86.87 ± 3.43
86.87 ± 3.43
86.87 ± 3.43

70.25 ± 10.2
81.46 ± 6.88
86.01 ± 5.41

85.55 ± 4.94
85.21 ± 5.46
86.52 ± 4.71

85.90 ± 4.85
86.49 ± 4.81
88.18 ± 3.57

56%
54%
56%

Zer

10%
20%
30%

73.82 ± 8.82
73.82 ± 8.82
73.82 ± 8.82

69.61 ± 10.7
80.86 ± 8.02
86.07 ± 5.51

72.96 ± 10.4
77.31 ± 7.89
81.11 ± 6.79

76.17 ± 8.52
81.72 ± 7.33
86.33 ± 5.04

82%
82%
86%

Fou

10%
20%
30%

68.73 ± 9.07
68.73 ± 9.07
68.73 ± 9.07

69.42 ± 9.68
82.11 ± 6.48
89.90 ± 3.69

68.88 ± 11.8
77.93 ± 8.27
82.45 ± 5.20

75.92 ± 8.81
85.03 ± 4.39
89.35 ± 3.89

82%
88%
92%

Mor

10%
20%
30%

57.47 ± 15.3
57.47 ± 15.3
57.47 ± 15.2

69.09 ± 11.3
79.60 ± 10.1
87.44 ± 7.34

66.58 ± 13.5
73.61 ± 8.86
78.31 ± 9.00

71.07 ± 11.1
79.74 ± 9.92
86.98 ± 7.07

80%
84%
90%

ExML model without model cascade) achieves better performance even with the limited budget. Besides, from thelast column, we can see that informative candidates (top 2)
are selected to strengthen the poor original features, which
validates the effectiveness of the proposed budget allocation
strategy (namely, the median elimination mechanism).
Since the E X MLME
aug is not guaranteed to outperform SL,
particularly with the limited budget on poor candidate features, we propose the cascade structure. Actually, ExML approach (aka, E X MLME
csd ) achieves roughly best-of-two-worlds
performance, in the sense that it is basically no worse or evenbetter than the best of SL and E X MLME
aug . It turns out that evenE X MLUA
could
behavebetterthan
E
X ML ME
aug . These results
csd
validate the effectiveness of the model cascade component.

5.3

Real Data of Activities Recognition

We additionally examine the effectiveness on a real-world
dataset called RealDisp2 , which is an activities recognition
task (Baños et al. 2012). There are 9 on-body sensors used tocapture various actions of participants. Each sensor is placedon different parts of the body and provides 13-dimensionalfeatures including 3-dim from acceleration, 3-dim from gyro,
3-dim from magnetic field orientation and another 4-dimfrom quaternions. Hence, we have 117 features in total.
Dataset. Three types of actions (walking, running, and jogging) are included to form the dataset containing 2000 instances, where 30% of them are used for training and theremaining 70% for testing. In the training data, one sensor is
deployed and the class of jogging is randomly misperceived
as walking or running. The learner would explore the rest
eight candidate features to discover the unknown unknowns.
Thus, there are 9 partitions, and each is repeated for 10 times
by sampling the training instances randomly.
Results. Figure 8 shows the mean and std of accuracy, ourapproach E X ML (aka, E X MLME
csd ) outperforms others, vali2
http://archive.ics.uci.edu/ml/datasets/REALDISP+Activity+
Recognition+Dataset

2 85.20.80

Fac85.2 88.5 86.8 85.7 85.4 90.9 89.6 90.8

1

original feature

FeatureAccuracy

Table 1: Evaluation on Mfeat dataset. Features are sorted by de-

88.5 86.3 87.9 86.0 89.9 87.2 87.4

3 88.5 88.5

85.4 93.8 81.8 84.1 90.0 93.1

4 86.8 86.3 85.4

SL
aug-ME

0.1

0.2
0.15
shift intensity

csd-ME
csd-UA

0.25

Figure 8: Performance comparisons of all contenders.

0.3

5 85.7 87.9 93.8 93.0

92.1 94.0 92.5 91.7

6 85.4 86.0 81.8 84.8 92.1

0.1
91.4 93.6
88.4

9 90.8 87.4 93.1 91.8 91.7 91.8 93.6 88.4
2

3

0.15

86.3 90.3 91.8

8 89.6 87.2 90.0 87.9 92.5 90.3 91.4

1

0.2

93.0 84.8 86.6 87.9 91.8

7 90.9 89.9 84.1 86.6 94.0 86.3

0.65

0.25

4 5 6 7 8
candidate features

9

0.05
0

Figure 9: Budget allocation (median elimination).

dating the efficacy of our proposal. In addition, Figure 9 illustrates the budget allocation when the budget ratio b = 30%.
The i-th row denotes the scenario when the i-th sensor is theoriginal feature, and patches with colors indicate the fractionof budget allocated to each candidate feature. The number
above a patch means the attainable accuracy of the modeltrained on the whole training dataset with the particular feature. We highlight the top two candidate features of each row
in white, and use blue color to indicate selected feature is not
in top two. The results show that E X ML with median elimination can select the top two informative features to augment
for all the original sensors. The only exception is the 9-th
sensor, but quality of the selected feature (91.8%) does notdeviate too much from the best one (93.6%). These results
reflect the effectiveness of our feature exploration strategy.

6

Conclusion

In this paper, we identify that aside from the inadequate selection of learning algorithms or the lack of enough labeledtraining samples, unknown unknowns could also lead to themodel failure. In particular, we are concerned with the scenario where some instances in the training dataset belong
to an unknown hidden class but are wrongly perceived asknown classes, due to the insufficient feature information.
To address this issue, we propose the exploratory machinelearning (ExML) to encourage the learner to examine andinvestigate the training dataset by exploring more features todiscover potentially hidden classes. Following this idea, we
design an approach consisting of three procedures: rejection
model, feature exploration, and model cascade. By leveraging techniques from bandit theory, we prove the rationale andefficacy of the feature exploration procedure. Experiments
validate the effectiveness of our approach.
There remain many directions for future investigations.
For instance, as mentioned in Section 2.2, we can borrow
more advanced techniques to further relax some model assumptions introduced in the current work (such as binary
known classes, uniform cost, best feature exploration, etc).
In particular, it is interesting to consider a personalized costfor each candidate feature, since we usually need to pay ahigher price to obtain more informative features in real-world
applications. Moreover, in addition to the feature exploration
proposed in this paper, we argue that there are many otherpossibilities for ExML to deal with unknown unknowns, bymeans of adaptive interactions with environments.

References
Attenberg, J.; Ipeirotis, P.; and Provost, F. 2015. Beat theMachine: Challenging Humans to Find a Predictive Model’s
Unknown Unknowns. ACM Journal of Data and Information
Quality 1–17.
Baños, O.; Damas, M.; Pomares, H.; Rojas, I.; Tóth, M. A.;
and Amft, O. 2012. A benchmark dataset to evaluate sensor
displacement in activity recognition. In Proceedings of 12th
ACM Conference on Ubiquitous Computing, 1026–1035.
Bansal, G.; and Weld, D. S. 2018. A Coverage-Based Utility
Model for Identifying Unknown Unknowns. In Proceedingsof the 32nd AAAI Conference on Artificial Intelligence, 1463–
1470.
Bartlett, P. L.; and Wegkamp, M. H. 2008. Classification
with a Reject Option using a Hinge Loss. Journal of Machine
Learning Research 1823–1840.
Bousquet, O.; Boucheron, S.; and Lugosi, G. 2003. Introduction to Statistical Learning Theory. In Advanced Lectures
on Machine Learning (Machine Learning Summer Schools
2003), 169–207.
Bousquet, O.; and Zhivotovskiy, N. 2019. Fast classification
rates without standard margin assumptions. arXiv preprint
arXiv:1910.12756.
Cai, X.-Q.; Zhao, P.; Ting, K. M.; Mu, X.; and Jiang, Y.
2019. Nearest Neighbor Ensembles: An Effective Method for
Difficult Problems in Streaming Classification with Emerging New Classes. In Proceedings of the 19th International
Conference on Data Mining (ICDM), 970–975.
Chen, L.; Li, J.; and Qiao, M. 2017. Nearly Instance Optimal
Sample Complexity Bounds for Top-k Arm Selection. In Proceedings of the 20th International Conference on Artificial
Intelligence and Statistics, 101–110.
Chow, C. K. 1970. On optimum recognition error and reject
tradeoff. IEEE Transactions on Information Theory 41–46.
Cortes, C.; DeSalvo, G.; and Mohri, M. 2016a. Boosting with
Abstention. In Advances in Neural Information Processing
Systems 29, 1660–1668.
Cortes, C.; DeSalvo, G.; and Mohri, M. 2016b. Learningwith Rejection. In Proceedings of International Conferenceon Algorithmic Learning Theory, 67–82.
Da, Q.; Yu, Y.; and Zhou, Z.-H. 2014. Learning with Augmented Class by Exploiting Unlabeled Data. In Proceedingsof the 28th AAAI Conference on Artificial Intelligence, 1760–
1766.
Dhurandhar, A.; and Sankaranarayanan, K. 2015. Improving Classification Performance Through Selective InstanceCompletion. Machine Learning 425–447.
Dietterich, T. G. 2017. Steps Toward Robust Artificial Intelligence. AI Magazine 3–24.
Even-Dar, E.; Mannor, S.; and Mansour, Y. 2006. Action
Elimination and Stopping Conditions for the Multi-Armed
Bandit and Reinforcement Learning Problems. Journal of
Machine Learning Research 7: 1079–1105.

Gama, J.; Zliobaite, I.; Bifet, A.; Pechenizkiy, M.; andBouchachia, A. 2014. A survey on concept drift adaptation.
ACM Computing Surveys 46(4): 44:1–44:37.
Geng, C.; Huang, S.-J.; and Chen, S. 2018. Recent Advances in Open Set Recognition: A Survey. arXiv preprint
arXiv:1811.08581.
Herbei, R.; and Wegkamp, M. H. 2006. Classification withreject option. Canadian Journal of Statistics 709–721.
Hou, B.-J.; Zhang, L.; and Zhou, Z.-H. 2017. Learningwith Feature Evolvable Streams. In Advances in Neural
Information Processing Systems 30, 1417–1427.
Hou, C.; and Zhou, Z.-H. 2018. One-Pass Learning with
Incremental and Decremental Features. IEEE Transactions
on Pattern Analysis and Machine Intelligence 40(11): 2776–
2792.
Huang, S.; Xu, M.; Xie, M.; Sugiyama, M.; Niu, G.; andChen, S. 2018. Active Feature Acquisition with Supervised Matrix Completion. In Proceedings of the 24th ACM
SIGKDD International Conference on Knowledge Discovery& Data Mining, 1571–1579.
Kalyanakrishnan, S.; Tewari, A.; Auer, P.; and Stone, P. 2012.
PAC Subset Selection in Stochastic Multi-armed Bandits. In
Proceedings of the 29th International Conference on Machine
Learning, 227—-234.
Lakkaraju, H.; Kamar, E.; Caruana, R.; and Horvitz, E. 2017.
Identifying Unknown Unknowns in the Open World: Representations and Policies for Guided Exploration. In Proceedings of the 31st AAAI Conference on Artificial Intelligence,
2124–2132.
Liu, S.; Garrepalli, R.; Dietterich, T. G.; Fern, A.; andHendrycks, D. 2018. Open Category Detection with PAC
Guarantees. In Proceedings of the 35th International Conference on Machine Learning, 3175–3184.
Melville, P.; Provost, F. J.; and Mooney, R. J. 2005. An Expected Utility Approach to Active Feature-Value Acquisition.
In Proceedings of the 5th IEEE International Conference on
Data Mining, 745–748.
Mohri, M.; Rostamizadeh, A.; and Talwalkar, A. 2018. Foundations of Machine Learning. The MIT Press, second edition.
Mu, X.; Ting, K. M.; and Zhou, Z.-H. 2017. Classification
Under Streaming Emerging New Classes: A Solution Using
Completely-Random Trees. IEEE Transactions on Knowledge and Data Engineering 29(8): 1605–1618.
Mu, X.; Zhu, F.; Du, J.; Lim, E.-P.; and Zhou, Z.-H. 2017.
Streaming Classification with Emerging New Class by Class
Matrix Sketching. In Singh, S. P.; and Markovitch, S., eds.,
Proceedings of the 31st AAAI Conference on Artificial Intelligence, 2373–2379.
Njoo, M.; and De Jong, T. 1993. Exploratory learning with acomputer simulation for control theory: Learning processes
and instructional support. Journal of research in scienceteaching 821–844.
Pan, S. J.; and Yang, Q. 2010. A Survey on Transfer Learning.
IEEE Transactions on Knowledge and Data Engineering
1345–1359.

Scheirer, W. J.; de Rezende Rocha, A.; Sapkota, A.; andBoult, T. E. 2013. Toward Open Set Recognition. IEEE
Transactions on Pattern Analysis and Machine Intelligence
1757–1772.
Scheirer, W. J.; Jain, L. P.; and Boult, T. E. 2014. Probability
Models for Open Set Recognition. IEEE Transactions on
Pattern Analysis and Machine Intelligence 2317–2324.
Schölkopf, B.; and Smola, A. J. 2002. Learning with Kernels:
support vector machines, regularization, optimization, andbeyond. The MIT Press.
Seldin, Y.; Bartlett, P. L.; Crammer, K.; and Abbasi-Yadkori,Y. 2014. Prediction with Limited Advice and Multiarmed
Bandits with Paid Observations. In Proceedings of the 31th
International Conference on Machine Learning, 280–287.
Settles, B. 2012. Active Learning. Morgan & Claypool
Publishers.
Shim, H.; Hwang, S. J.; and Yang, E. 2018. Joint Active
Feature Acquisition and Classification with Variable-Size Set
Encoding. In Advances in Neural Information Processing
Systems 31, 1375–1385.
Spector, J. M.; Merrill, M. D.; Elen, J.; and Bishop, M. 2014.
Handbook of Research on Educational Communications andTechnology. Springer, fourth edition.
van Breukelen, M.; Duin, R. P. W.; Tax, D. M. J.; and den Hartog, J. E. 1998. Handwritten digit recognition by combinedclassifiers. Kybernetika 381–386.
Wang, W.; and Qiao, X. 2018. Learning Confidence Sets
using Support Vector Machines. In Advances in Neural Information Processing Systems 31, 4934–4943.
Yuan, M.; and Wegkamp, M. H. 2010. Classification Methods
with Reject Option Based on Convex Risk Minimization.
Journal of Machine Learning Research 111–130.
Zhang, C.; Wang, W.; and Qiao, X. 2018. On reject andrefine options in multicategory classification. Journal of theAmerican Statistical Association 730–745.
Zhang, Y.-J.; Zhao, P.; Ma, L.; and Zhou, Z.-H. 2020. An Unbiased Risk Estimator for Learning with Augmented Classes.
In Advances in Neural Information Processing Systems 33,
10247–10258.

Appendix A

Related WorkIn this section, we discuss some related topics of the exploratory machine learning.
Open Category Learning. Open category learning is also
named as learning with new classes, which focuses on
handling unknown classes appearing only in the testing
phase (Scheirer et al. 2013; Scheirer, Jain, and Boult 2014;
Da, Yu, and Zhou 2014; Mu, Ting, and Zhou 2017; Mu et al.
2017; Liu et al. 2018; Cai et al. 2019; Zhang et al. 2020).
Although these studies also care about the unknown classes
detection, they differ from us significantly and are not able toapply to our situations. Specifically, first, they do not consider
deficiency of the feature quality; second, there exist unknownclasses in training data in our setting, while in theirs unknownclasses only appear in the testing stage.
High-Confidence False Predictions. High-confidence
false predictions appear due to model’s unawareness of suchkind of mistakes. Such instances and predictions are also
referred to as a kind of “unknown unknowns” (Attenberg,
Ipeirotis, and Provost 2015; Lakkaraju et al. 2017; Bansal andWeld 2018). As the model gives high-confidence for the false
predictions, it is almost not possible to rectify the model‘s
performance. As a result, existing studies typically ask forexternal human expert to help identifying high-confidence
false predictions and then retrain the model with the guidance.
Although these works also consider unknown unknowns andresort to external human knowledge, their setting and methodology differ from ours: our unknown unknowns are caused
due to feature deficiency, so the learner requires to augment
features rather than querying labels.
Active Learning. Active learning aims to achieve greater
accuracy with fewer labels by asking queries of unlabeleddata to be labeled by the human expert (Settles 2012). Besides, there are some works querying features (Melville,
Provost, and Mooney 2005; Dhurandhar and Sankaranarayanan 2015; Huang et al. 2018), which tries to improvelearning with missing features via as fewer as possible queriesof entry values (the feature of an instance). Unlike their settings, in our work we augment new features to help the identification of the unknown classes rather than querying missing
values of the given feature to improve the performance ofknown classes classification.
Learning with Rejection. Learning with rejection gives
the classifier an option to reject an instance instead of providing a low-confidence prediction (Chow 1970). Plenty ofworks are proposed to design effective algorithms (Yuan andWegkamp 2010; Cortes, DeSalvo, and Mohri 2016a; Wang
and Qiao 2018; Shim, Hwang, and Yang 2018) and establish
theoretical foundations (Herbei and Wegkamp 2006; Bartlett
and Wegkamp 2008; Cortes, DeSalvo, and Mohri 2016b;
Bousquet and Zhivotovskiy 2019). As aforementioned, methods of rejection cannot be directly applied in exploratory machine learning, because it will result in inaccurate rejectionsof instances from known classes, and meanwhile, it cannot
exploit new features like exploratory machine learning.

Appendix B

More Algorithm Details

This section presents more details for the feature exploration
algorithm shown in Section 3.2, which attempts to identify
the best feature from the K candidates with B budget. For better exploiting the budget, our algorithm essentially employing the idea of median elimination (Even-Dar, Mannor, andMansour 2006). The algorithm proceeds in T = dlog2 Ke
episodes, where half of the poor features are removed every
episode and only the best one remains in the last.
In each episode, in total bB/T c budget is allocated uniformly to all remaining candidate features, and the learner
could query their values for updating the corresponding augbD is calculated onmented datasets Di . Then, the score Rithe current augmented datasets Di and the half features withbD are eliminated. In the last, only one candidate feahigh R
iture is will be left and its augmented dataset Dis contains
around bB/ log Kc samples, which is the largest among all
candidate features.
Algorithm 1 Median Elimination for Feature Exploration
Input: Feature exploration budget B, original datasetb trbi )}mD= {(bxi , yi=1 , candidate feature poolC{c1 , . . . , cK }, threshold θ ∈ (0, 1).
Output: Selected feature cis ∈ C and corresponding augmented model fbis .
1: Initialize: dataset Di = ∅ for each feature ci ∈ C, set of
active features C1 = C, T = dlog2 Ke.
2: for t = 1, . . . , T do
3:
Randomly select nt = bB/(T |Ct |)c samples fromb tr and query active features ci ∈ Ct ;D
4:Update Di with selected samples and train a model fbi
on Di by ERM (2), for all ci ∈ Ct ;bD according to (4), for all ci ∈ Ct ;5:
Compute RibD ;6:Update Ct+1 as half of features in Ct with lower Ri7: end forAppendix C

Proof of Theorem 1

Proof of Theorem 1. The excess risk of the learned model
fbis can be decomposed into three parts,
Ris (fbis ) − R1∗bi (fbi ) + R
bi (fbi ) − R
b1 (fb1 ) + R
b1 (fb1 ) − R1∗ ,= Ris (fbis ) − R|{z s s } | s s {z} |{z}term (a)term (b)term (c)where term (a) is the generalization error of the learned
model fbis and term (b) is the difference between empiricalcriterion of the selected feature and that of the best feature,
where fb1 refers to the model trained on the best feature witha bB/Kc budget. Besides, term (c) captures the excess riskof fb1 relative to the Bayes risk. Notice that term (b) < 0
since the empirical criterion of the selected feature is thelowest among all candidates. Thus, to prove the theorem, it
is sufficient to bound term (a) and term (c).
We bound term (a) based on the following lemma on thegeneralization error of the rejection model, which can be
regarded as a two-side counterpart of (Cortes, DeSalvo, andMohri 2016b, Theorem 1).
Lemma 1. Let H and G be the kernel-based hypotheses
H, G = {x 7→ hw, Φ(x)i | kwkH ≤ Λ}. Then for any
δ > 0, with probability of 1 − δ over the draw of a sample Dof size n from D, the following holds for all f ∈ H × G:
r
r
(κΛ)2
log(2/δ)b|R(f ) − R(f )| ≤ (2 + θ)
+
, (7)
n
2n
where κ2 = supx∈X K(x, x) and K : X × X 7→ R is thekernel function associated with H.
Therefore, the generalization error of the fbis can be directly
bounded by,ss(κs Λs )2log(2/δ 0 )+, (8)term (a) ≤ (2 + θ)
bB/Kc
2bB/Kcwith probability at least 1 − δ 0 .
Then we process to analyze the excess risk of fb1 trainedon the best feature with surrogate loss `surr , where term (c)can be decomposed into two parts asterm (c-2)
≤ Cθ R1surr (fb1 ) − inf f R1surr (f )= Cθ R1surr (fb1 ) − inf R1surr (f )f ∈H1 ×G1


R1surr (f ) − inf R1surr (f )f ∈H1 ×G1f= Cθ R1surr (fb1 ) − inf R1surr (f ) + Rap .
+inf

f ∈H1 ×G1

can be further bounded by the generalization error bound of
the the surrogate loss function and the optimality of fb1 forthe ERM problem (2) in hypotheses H1 × G1 as,term (c-2)

Based on Lemma 1, term (c-1) is bounded byss(κ1 Λ1 )2log(2/δ 0 )+,term (c-1) ≤ (2 + θ)
bB/Kc
2bB/KcLemma 3 can be obtained by the standard analysis ofgeneralization error based on the Rademacher complexity.
One may refer to Chapter 3 of the seminal textbook (Mohri,
Rostamizadeh, and Talwalkar 2018). Then, based on the consistency property of the surrogate loss function demonstrated
in Lemma 2, we have

Denote f1∗ = inf f ∈H1 ×G1 R1surr (f ). The first term of (10)b1 (fb1 ) − R∗term (c) = R1bb= R1 (f1 ) − R1 (fb1 ) + R1 (fb1 ) − R1∗ .
|
{z
} |
{z
}
term (c-1)

Lemma 3. Let H and G be the kernel-based hypotheses,
defined as H, G = {x 7→ hw, Φ(x)i | kwkH ≤ Λ}. Thenfor any δ > 0, with probability of 1 − δ over the draw ofa sample D of size n from D, the following holds for allf ∈ H × G:rr
2 − 2θ (κΛ)2log(2/δ)
surr
surr
b
|R
(f )− R(f )| ≤
+B,
1 − 2θ
n2nwhere K : X × X 7→ R is the kernel function associated with H and κ2 = supx∈X K(x, x). Moreover,B = supf ∈H×G sup(x,y)∈X ×Y `surr (f, x, y; θ) ≤ 1 +max {1, θ/(1 − 2θ)} · κΛ.

R1surr (fb1 ) − R1surr (f1∗ )b1surr (fb1 ) + R
b1surr (fb1 ) − R1surr (f1∗ )= R1surr (fb1 ) − R(9)which holds with probability at least 1 − δ 0 .
Before presenting the analysis on term (c-2), we introduce the results on consistency and the generalization errorof the surrogate loss function. First, we show that the excess
risk with respect to 0/1 loss for any function f is bound by
the excess risk with respect to the surrogate loss `surr .
Lemma 2 (Theorem 3 of Cortes, DeSalvo, and Mohri(2016b)). Let Rsurr (f ) = E(x,y)∼D [`surr (f, x, y; θ)] denote the expected risk in terms of the surrogate loss of a pairf = (h, g). Then, the excess error of f is upper bounded byits surrogate excess error as follows,


∗
surr
surr
R(f ) − R ≤ Cθ R
(f ) − inf R(f ) ,

b1surr (fb1 ) + R
b1surr (f1∗ ) − R1surr (f1∗ )≤ R1surr (fb1 ) − R
b1surr (f )|≤ 2 sup |R1surr (f ) − R
f ∈H1 ×G1

4 − 4θ
≤1 − 2θs(κ1 Λ1 )2
+ 2B
bB/Kc

term (c-2)≤ Cθ

4 − 4θ
1 − 2θs(κ1 Λ1 )2
+ 2B
bB/Kc

s

log(2/δ 0 )2bB/Kc

!
+ Rap
(10)

0

Besides, the generalization error over the surrogate loss isbounded in the following lemma.

log(2/δ 0 ).
2bB/KcHere, for simplicity, we analyze the version of ERM problem
in terms of the constraint on the RKHS norm instead of interms of its Lagrange multiplier as (2), as they have identicalregularization paths. Thus, term (c-2) is bounded byf1
where Cθ = (1−θ)(1−2θ)and R∗ = inf f R(f ).

swith probability at least 1 − δ .
Combining (8), (9) and (10), and setting κ = supi∈[K] κi ,
Λ = supi∈[K] Λi and δ 0 = δ/3, we have
Ris (bhis , gbis ) − R1∗

s

s
(κΛ)2
log(6/δ)≤ (4 + 2θ)+2bB/Kc
2bB/Kcss!
(κΛ)2log(6/δ)4 − 4θ
+ 2B
+ Rap
+ Cθ
1 − 2θ bB/Kc
2bB/Kcs4(κΛ)2= 4 + 2θ +2
(1 − 2θ)bB/Kcslog(6/δ)+ 2(1 + Cθ B)+ Rap ,
2bB/Kcwhich holds with probability at least 1 − δ. This ends theproof of Theorem 1.