An Unbiased Risk Estimator for Learning with
Augmented Classes

Yu-Jie Zhang, Peng Zhao, Lanjihong Ma, Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology,
Nanjing University, Nanjing 210023, China{zhangyj, zhaop, maljh, zhouzh}@lamda.nju.edu.cn

Abstract
This paper studies the problem of learning with augmented classes (LAC), whereaugmented classes unobserved in the training data might emerge in the testing
phase. Previous studies generally attempt to discover augmented classes by exploiting geometric properties, achieving inspiring empirical performance yet lacking
theoretical understandings particularly on the generalization ability. In this paper
we show that, by using unlabeled training data to approximate the potential distribution of augmented classes, an unbiased risk estimator of the testing distribution canbe established for the LAC problem under mild assumptions, which paves a way
to develop a sound approach with theoretical guarantees. Moreover, the proposed
approach can adapt to complex changing environments where augmented classes
may appear and the prior of known classes may change simultaneously. Extensive
experiments confirm the effectiveness of our proposed approach.

1

Introduction

Recent advances in machine learning encourage its application in high-stake scenarios, where therobustness is the central requirement [1, 2]. A robust learning system should be able to handle
the distribution change in the non-stationary environments [3, 4, 5]. In this paper, we focus on the
problem of learning with augmented classes (LAC) [6], where the class distribution changes during
the learning process—some augmented classes unobserved in training data might emerge in testing.
To make reliable predictions, desired learning systems are required to identify augmented classes andretain good generalization performance over the testing distribution.
The main challenge of the LAC problem lies in how to depict relationships between known andaugmented classes. A typical solution is to learn a compact geometric description of the knownclasses and take those beyond the description as augmented classes, where the anomaly detection
or novelty detection approaches can be employed (such as one-class SVM [7, 8], kernel density
estimation [9, 10] and iForest [11]). Da et al. [6] give the name of LAC and employ the low-density
separation assumption to adjust the decision boundaries in a multi-class situation. In addition to theeffort of machine learning community, the computer vision and pattern recognition communities
also contribute to the study of the problem (or its cousin). Scheirer et al. [12] propose the notion ofopen space risk to penalize predictions outside the support of training data, based on which several
approaches are developed [12, 13]. Later, approaches based on the nearest neighbor [14] and extreme
value theory [15] are also developed. More discussions on related topics are deferred to Section 5.
Although various approaches are proposed with nice performance and some of them conduct theoretical analysis, generalization properties of the LAC problem is less explored. Scheirer et al.
[12, 13], Rudd et al. [15] formally use the open space risk or extreme value theory to identify augmented classes, but the generalization error of learned models is not further analyzed. There are also
works [16, 17, 18] focusing on the Neyman-Pearson (NP) classification, which controls the novelty
34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada.

Class 1: 1

Class 2: 2

Augmented Class: a

Unlabeled data:-=
1

distribution of unlabeled dataa2

distribution of labeled data

distribution of the class absent in labeled data

Figure 1: Distribution of augmented classes can be estimated by those of labeled and unlabeled training data.
detection ratio of augmented classes or false positive ratio of known classes with the constraint onanother. By using unlabeled data, authors develop approaches with one-side PAC-style guarantees forthe binary NP classification whereas the generalization ability for the LAC problem is not studied.
To design approaches with generalization error guarantees for the LAC problem, it is necessary toassess the distribution of augmented classes in the training stage. Note that in many applications,
during the training stage, in addition to labeled data, there are abundant unlabeled training data
available. In this paper, we show that by exploiting unlabeled training data, an unbiased risk estimator
over the testing distribution can be established under mild assumptions. The intuition is that, thoughinstances from augmented classes are unobserved from labeled data, their distribution information
may be contained in unlabeled data and estimated by separating the distribution of known classes fromunlabeled data (Figure 1). More concretely, we propose the class shift condition to model the testing
distribution as a mixture of known and augmented classes’ distributions. Under such a condition,
classifiers’ risk over testing distribution can be estimated in the training stage, where minimizing
its empirical estimator finally gives our E ULAC approach, short for Exploiting Unlabeled data for
Learning with Augmented Classes. Moreover, the E ULAC approach can further take the prior change
on known classes into account, which enables its adaptivity to complex changing environments.
E ULAC enjoys several favorable properties. Theoretically, our approach has both asymptotic (consistency) and non-asymptotic (generalization error bound) guarantees. Notably, the non-asymptotic
analysis further justifies the capability of our approach in exploiting unlabeled data, since the generalization error becomes smaller with an increasing number of unlabeled data. Moreover, extensive
experiments validate the effectiveness of our approach. It is noteworthy to mention that our approach
can now perform the standard cross validation procedure to select parameters, while most geometricbased approaches cannot due to the unavailability of the testing distribution, and their parameters
setting heavily relies on the experience. We summarize main contributions of this paper as follows.
(1) We propose the class shift condition to characterize the connection between known andaugmented classes for the learning with augmented class problem.
(2) Based on the class shift condition, we establish an unbiased risk estimator over the testing
distribution for the LAC problem by exploiting the unlabeled data. Similar results are also
attainable for a general setting of class distribution change.
(3) We develop our E ULAC approach with the unbiased risk estimator, whose theoreticaleffectiveness is proved by both consistency and generalization error analyses. We also
conduct extensive experiments to validate its empirical superiority.

2

An Unbiased Risk Estimator for LAC problem

In this section, we formally describe the LAC problem, followed by the introduction of the class
shift condition, based on which we develop the unbiased risk estimator over the testing distribution.
Moreover, we show the potential of our approach for adapting to complex changing environments.
2.1

Problem Setup and Class Shift Conditionl
LAC problem. In the training stage, the learner collects a labeled dataset DL = {(xi , yi )}ni=10sampled from distribution of known classes Pkc defined over X × Y , where X denotes the feature
space and Y 0 = {1, . . . , K} is the label space of K known classes. In the testing stage, the learnerrequires to predict instances from the testing distribution Pte , where augmented classes not observed
before might emerge. Since the specific partition of augmented classes is unknown, the learner
will predict all of them as a single augmented class ac. So the testing distribution is defined over2

X × Y, where Y = {1, . . . , K, ac} is the augmented label space. The goal of the learner is totrain a classifier f : X 7→ Y achieving good generalization ability by minimizing the expected riskR(f ) = E(x,y)∼Pte [1(f (x) 6= y)] over the testing distribution, where 1(·) is the indicator function.
u
Unlabeled data. In our setup, the learner additionally receives a set of unlabeled data DU = {xi }ni=1sampled from the testing distribution and hopes to use it to enhance performance of the trainedclassifier. This learning scenario happens when labeled training data fail to capture certain classes of
the testing distribution due to the class distribution change, while we can easily collect a vast amountof unlabeled data from current environments. Essentially, the missed class information has alreadybeen contained in the training data (unlabeled data) though is not revealed in the supervision (labeledtraining data). We thus prefer to call such classes as the “augmented class” instead of “new class”.

Class shift condition. Although not explicitly stated, previous works [12, 6, 14] essentially rely on
the assumption that the distribution of known classes remains unchanged when augmented classes
emerge. Following the same spirit, we introduce the following class shift condition for the LAC
problem to rigorously depict the connection between known and augmented class distributions.
Definition 1 (Class Shift Condition). The testing distribution Pte , the distribution of known classes
Pkc and the distribution of augmented classes Pac are under the class shift condition, if
Pte = θ · Pkc + (1 − θ) · Pac ,(1)

where θ ∈ [0, 1] is a certain mixture proportion.1
Class shift condition states that the testing distribution can be regarded as a mixture of those of known
and augmented classes with a certain proportion θ, based on which we can evaluate classifiers’ riskover the testing distribution with labeled and unlabeled training data.
2.2

Convex Unbiased Risk Estimator

This part, we develop an unbiased risk estimator for the LAC problem under the class shift condition.
We first introduce the notation conventions. The density function is denoted by the lowercase p, andthe joint, conditional and marginal density functions are indicated by the subscripts XY , X|Y (Y |X)
and X (Y ). For instance, pte
X (x) refers to the marginal density of the testing distribution over X .
OVR scheme. Suppose the joint testing distribution were available, the LAC problem would degenerate to standard multi-class classification, which can be then addressed by existing approaches. Among
those approaches, we adopt the one-versus-rest (OVR) strategy, which enjoys sound theoreticalguarantees [19] and nice practical performance [20]. The risk minimization is formulated as,hi
XK+1
min Rψ (f1 , . . . , fK+1 ) = E(x,y)∼Pte ψ(fy (x)) +ψ(−fk (x)) ,(2)
k=1,k6=y

f1 ,...,fK+1

where fk is the classifier for the k-th class, k = 1, . . . , K; and fac is the classifier for the augmentedclass. For simplicity, we substitute fac with fK+1 in the formulation. ψ : R 7→ [0, +∞) is a binary
surrogate loss such as hinge loss. The OVR scheme predicts by f (x) = arg maxk∈{1,...,K,ac} fk (x).
Approximating the testing distribution. However, the joint testing distribution is unavailable in
the training stage due to the absence of labeled instances from augmented classes. Fortunately, weshow that given the mixture proportion θ, it can be approximated with the labeled and unlabeled data.
Under the class shift condition, the joint density of the testing distribution can be decomposed as
(1)

kc
ac
pte
XY (x, y) = θ · pXY (x, y) + (1 − θ) · pXY (x, y)ac= θ · pkc
XY (x, y) + 1(y = ac) · (1 − θ) · pX (x),(3)

where the last equality follows from the fact that pac
XY (x, y) = 0 holds for all x ∈ X and y 6= ac.
kc
The first part pXY (x, y) is accessible via the labeled data. The only unknown term is the second
part, the marginal density of the augmented class pac
X (x). Under the class shift condition, it can beevaluated by separating the distribution of labeled data from unlabeled data astekc(1 − θ) · pac
X (x) = pX (x) − θ · pX (x).

(4)

Thus, by plugging (4) into (3), the testing distribution becomes attainable, and consequently, we canevaluate the OVR risk Rψ in the training stage through an equivalent risk RLAC .
1

We redefine all the distributions over the space X × Y, where pkc
XY (x, ac) = 0 for all x ∈ X

3

Proposition 1. Under the class shift condition, for measurable functions f1 , . . . , fK , fac , we haveRψ (f1 , . . . , fK , fac ) = RLAC (f1 , . . . , fK , fac ), where RLAC is defined as,
RLAC = θ · E(x,y)∼Pkc [ψ(fy (x)) − ψ(−fy (x)) + ψ(−fac (x)) − ψ(fac (x))]
h
i
XK
(5)
+ Ex∼pte
ψ(fac (x)) +ψ(−fk (x)) .
X (x)
k=1

Remark 1. We can assess RLAC during training as the distribution of known classes Pkc and marginal
testing distribution pte
X (x) can be estimated by labeled and unlabeled training data, respectively.
The remaining issue for the LAC risk RLAC is the non-convexity caused by terms −ψ(−fy (x)) and−ψ(fac (x)), which are non-convex w.r.t the classifiers even with the convex binary surrogate loss ψ.
Inspired by studies [21, 22], we can eliminate the non-convexity by carefully choosing the surrogate
loss satisfying ψ(z) − ψ(−z) = −z for all z ∈ R, and thereby RLAC enjoys a convex formulationhi
XK
RLAC = θ · E(x,y)∼Pkc [fac (x) − fy (x)] + Ex∼pte
ψ(f
(x))
+
ψ(−f
(x))
. (6)
ac
k
(x)
X
k=1

Many loss functions satisfy the above condition [22], such as logistic loss ψ(z) = log(1 + exp(−z)),square loss ψ(z) = (1 − z)2 /4 and double hinge loss ψ(z) = max(−z, max(0, (1 − z)/2)). Since
bLAC is unbiased over the
LAC risk RLAC equals to the ideal OVR risk Rψ , its empirical estimator R
testing distribution. We can thus perform the standard empirical risk minimization. Finally, we notethat Proposition 1 can be generalized for arbitrary multiclass losses, if the convexity is not required,
where more multiclass and binary losses can be used. We will take this as a future work.
2.3

Convex Unbiased Risk Estimator under Generalized Class Shift Condition

The class shift condition in Definition 1 models the appearance of augmented classes with theassumption that the distribution of known classes is identical to that in the testing stage. In real-world
applications, however, the environments might be more complex, where the distribution of knownclasses could also shift. We consider a specific kind of class distribution change: in addition to theemerging augmented classes, the prior of each class pte
Y (y) varies from labeled data to testing data,kcwhile their conditional density remains the same, namely pte
X|Y (x|y) = pX|Y (x|y) for all y ∈ [K].
To this end, we propose following generalized class shift condition to model such a case by further
decomposing the distribution of known classes in the testing stage as a mixture of several components,


XK
XK
k
k
Pte =
θte · Pk + 1 −θte · Pac ,
(7)
k=1

k=1

where Pk is the distribution of the k-th known class whose marginal density equals to pkc
X|Y (x|k), andkteθte = pY (k) is the prior of k-th known class in testing, for all k ∈ [K]. When there is no distributionchange on known classes, the generalized class shift condition recovers the vanilla version in (1).
With the generalized class shift condition (7), following the similar argument in Section 2.2, we canevaluate the OVR risk for the testing distribution even if the prior of known classes has changed.
Proposition 2. Under the generalized class shift condition (7), by choosing the surrogate loss
function satisfying ψ(z) − ψ(z) = −z for all z ∈ R, for measurable functions f1 , . . . , fK , fac , weshif tshif thave Rψ (f1 , . . . , fK , fac ) = RLAC
(f1 , . . . , fK , fac ), where RLAC
is defined as,
h
i
X
XK
K
shif tk
RLAC=
θte· E(x,y)∼Pk [fac (x) − fy (x)] + Ex∼pte
ψ(f
(x))
+
ψ(−f
(x))
.
ac
k
X (x)
k=1

k=1

Proposition 2 implies that we can handle the augmented classes together with the distribution change
shif tshif ton prior of known classes by empirically minimizing the risk RLAC
. Note that since RLAC
further
decomposes the distribution of known classes into several components, it enjoys more flexibility thank
RLAC in evaluating the testing risk, yet requires more efforts in estimation of class prior θtefor eachknown class rather than mixture proportion θ only, which will be discussed next.

3

Approach

In this section, we develop two practical algorithms for the proposed E ULAC approach to minimize
the empirical version of the LAC risk RLAC (similar results can be extended for its generalization
shif tk
RLAC). Meanwhile, we discuss how to estimate the mixture proportion θ and class prior θte.
4

bLAC in the
Kernel-based hypothesis space. We first consider minimizing the empirical LAC risk R
reproducing kernel Hilbert space (RKHS) F associated to a PDS kernel κ : X × X 7→ R: XK
bLAC + λminR
kfk k2F + kfac k2F ,(8)
k=1

f1 ,...,fK ,fac ∈F

bLAC is the empirical approximation of the LAC risk (6)where RXKXn l
1 Xnu bLAC = θRψ(fac (xi )) +ψ(−fk (xi )) . (9)(fac (xi ) − fyi (xi )) +
k=1
i=1
i=1
nl
nu
According to the representer theorem [23], the optimal solution of (8) is provably in the form ofXX
αik κ(·, xi ) +αjk κ(·, xj ),fk (·) =(10)xi ∈DL

xj ∈DU

where αik is the i-th coefficient of the k-th classifier.

Plugging (10) into (8), we get a convex
optimization problem with respect to α, which can be solved efficiently. Since the risk estimatorbLAC is assessed on the testing distribution directly, we can perform unbiased cross validation toRselect parameters. Then, after obtaining the binary classifiers f1 , . . . , fK , fac , we follow the OVR
rule to construct the final predictor as f : X 7→ Y with f (x) = arg maxk∈{1,...,K,ac} fk (x).
Deep model. Our approach can be also implemented by deep neural networks. Since the deep models
themselves are non-convex, we directly minimize the non-convex formulation of RLAC (5) by taking
outputs of the deep model as OVR classifiers. However, as shown by Kiryo et al. [24], the direct
minimization easily suffers from over-fitting as the risk is not bounded from below by 0. To avoid theundesired phenomenon, we apply their proposed non-negative risk [24] to rectify the OVR scheme
for training the deep model, whose effectiveness will be validated by experiments. More detailed
elaborations for the rectified RLAC risk is presented in the full paper [25].

bLAC requires estimating θ, which is known
On the estimation of θ. Notice that minimizing R
as the problem of Mixture Proportion Estimation (MPE) [26], where one aims to estimate themaximum proportion of distribution H in distribution F given their empirical observations. Many
works have been devoted to developing theoretical foundations and efficient algorithms [27, 17, 28,29]. We employ the kernel mean embedding (KME) based algorithm proposed by Ramaswamy
et al. p[26], which guarantees that the estimator θb converges to true proportion θ in the rate ofO(1/ min{nl , nu }) under the separability condition. Moreover, since the KME-based algorithm
easily suffers from the curse of dimensionality in practice, inspired by the recent work [28], we further
use a pre-trained model to reduce the dimensionality of original input to its probability outputs. We
refer to the above estimator as KME-base, and the corresponding approach for LAC as E ULAC-base.
Additionally, under the generalized class shift condition, we need more refined estimations for eachshif tkknown class. Therefore, we use the above MPE estimator to estimate each class prior θtein RLAC(2)
via the labeled instances from the k-th known class and the unlabeled data, k ∈ [K]. We refer tosuch an estimator as KME-shift and the corresponding approach as E ULAC-shift. Finally, we notethat since the vanilla LAC can also be modeled with the generalized class shift condition, we can
PK k
use KME-shift to estimate the mixture proportion θb by θb = k=1 θbte
. It turns out that KME-shiftachieves comparable (even better) empirical performance with KME-base.

4

Theoretical Analysis

In this section, we first show the infinite-sample consistency of the LAC risk RLAC . Then, we derive
the generalization error bounds. All the proofs can be found in the full paper [25].
Infinite-sample consistency. At first, we show that the LAC risk RLAC is infinite-sample consistent
with the risk over the testing distribution with respect to 0-1 loss. Namely, by minimizing the expectedrisk of RLAC , we can get classifiers achieving the Bayes rule over the testing distribution.
Theorem 1. Under the class shift condition, suppose the surrogate loss ψ is convex, bounded below,
differential, satisfying ψ(z) − ψ(−z) = −z and ψ(z) < ψ(−z) when z > 0, then for any 1 > 0,
there exists 2 > 0 such that∗
RLAC (f1 , . . . , fK , fac ) ≤ RLAC
+ 2

5

=⇒

R(f ) ≤ R∗ + 1

holds for all measurable functions f1 , . . . , fK , fac and f (x) = arg maxk∈{1,...,K,ac} fk (x). Here,∗
RLAC= minf1 ,...,fK ,fac RLAC (f1 , . . . , fK , fac ) and R∗ = minf R(f ) = E(x,y)∼Pte [1(f (x) 6=y)] is the Bayes error over the testing distribution.
Theorem 1 follows from Proposition 1 and analysis in the seminal work of Zhang [19], who investigates the consistency property of OVR risk in depth. Since the LAC risk RLAC is equivalent to
the OVR risk Rψ , it is naturally infinite-sample consistent. There are many loss functions satisfy
assumptions in Theorem 1 such as the logistic loss ψ(z) = log(1 + exp(−z)) and the square loss
ψ(z) = (1 − z)2 /4. In particular, we can obtain a more quantitative results for the square loss.
Theorem 2. Under the same conditionqof Theorem 1, when using ψ(z) = (1−z)2 /4 as the surrogate
∗loss function, we have R(f ) − R∗ ≤ 2 RLAC (f1 , . . . , fK , fac ) − RLAC.
Theorem 2 shows that the excess risk of RLAC upper bounds that of 0-1 loss. Thus, by minimizing
the LAC risk RLAC , we can obtain well-behaved classifiers on the testing distribution w.r.t. 0-1 loss.
Remark 2. Theorems 1 and 2 show the consistency for RLAC under class shift condition. Similar
shif tresults can be easily obtained for RLAC
with the generalized class shift condition, due to theshif tequivalence of RLAC
and the OVR risk, even when prior of known classes have changed.
Finite-sample generalization error bound. We establish the generalization error bound for the probLAC
posed approach in this part. Since the approach actually minimizes the empirical risk estimator Rwith a regularization term of the RKHS F, it is equivalent to investigate the generalization ability ofclassifiers f1 , . . . , fK , fac in the kernel-based hypothesis set F = {x 7→ hw, Φ(x)i | kwkF ≤ Λ},
where Φ : x 7→ F is a feature mapping associated with the positive definite symmetric kernel κ, andw is an element in the RKHS F. We have the following generalization error bound.
Theorem 3. Assume that κ(x, x) ≤ r2 holds for all x ∈ X and the surrogate loss function ψ isbounded by Bψ ≥ 0 and is L-Lipschitz continuous.2 Then, for any δ > 0, with probability at least
1 − δ over the draw of labeled samples DL of size nl from the distribution of known classes Pkc andunlabeled samples DU of size nu from pte
X (x), the following holds for all f1 , . . . , fK , fac ∈ F,
bLAC (f1 , . . . , fK , fac )RLAC (f1 , . . . , fK , fac ) − Rss2(K + 1)Λr
2 log(4/δ) 2(K + 1)LΛrlog(4/δ)≤+ 6Λr++ 3(K + 1)Bψ
.
√
√
nl
nl
nu
nu
Based on Theorem 3, by the standard argument [30, 31], we can obtain the estimation error bound.
Theorem 4. Under the same assumptions of Theorem 3 and let fb1 , . . . , fbK , fbac be the optimal
solution of the optimization problem (8) with certain λ > 0, with high probability, we have
K +1 K +1bbb
RLAC (f1 , . . . , fK , fac ) − inf RLAC (f1 , . . . , fK , fac ) ≤ O
+ √
,
√
f ∈F
nl
nu
PK
where f denotes (f1 , . . . , fK , fac ) and F = {f | f1 , . . . , fK , fac ∈ F, k=1 kfk k2F +kfac k2F ≤ c2λ }.
The parameter cλ > 0 is a constant related to λ in (8). We use the O-notation to keep the dependence
on nu , nl and K only, where the full expression can be found in the full paper.
Remark 3. Theorem 3 and Theorem 4 show that, the estimation error of the trained classifiers
decreases with a growing number of labeled and unlabeled data, which theoretically justifies theeffecacy of our approach in exploiting unlabeled data. Experiments also validate the same tendency.
Overview of theoretical results. Recall that the goal of the LAC problem is to obtain classifiers
that approach Bayes rule over
the testing distribution, so we need to minimize the excess risk
R argmaxk∈{1,...,K,ac} fk − R∗ . According to the consistency guarantee presented in Theorem 1,∗
it suffices to minimize the excess risk RLAC (f ) − RLAC
, which can be further decomposed into theestimation error and the approximation error as follows,∗∗
RLAC (f ) − RLAC
= RLAC (f ) − inf f ∈F RLAC (f ) + inf f ∈F RLAC (f ) − RLAC
.
|
{z
} |
{z
}
estimation error

2

approximation error

Common surrogate loss functions satisfy these conditions, such as logistic loss, exp loss and square loss.

6

Theorem 4 shows that with an increasing number of labeled and unlabeled data, the excess risk
converges to the irreducible approximation error, which measures how well the hypothesis set
approximates the Bayes rule and is generally not accessible for learning algorithms [31]. Thus, theconsistency and excess risk bounds theoretically justify the effectiveness of our approach.

5

Related Work and Discussion

This section discusses several research topics and techniques that are related to our approach.
Class-incremental learning [32] aims to handle new classes appearing in the learning process,and learning with augmented classes is one of its core tasks. Some early studies [6, 33] try to
exploit unlabeled data for handling the LAC problem. Our approach differs from theirs as we depict
the connection between known and augmented classes by the class shift condition rather than thegeometric assumption, which leads to more clear theoretical understandings and better performance.
Apart from the batch setting, researchers also manage to handle even more challenging scenario
where augmented classes emerge in the streaming data [34, 35, 36, 37]. It is interesting to study thatwhether our approach can be tailored for the streaming setting.
Open set recognition [12, 38] is a cousin of the LAC problem studies in the computer vision andpattern recognition communities. As we have mentioned, several techniques or concepts are employed
to depict the relationship between known and augmented classes, including open space risk [12, 13],nearest neighbor approach [14], extreme value theory [15] and the adversarial sample generation
framework [39], etc. We note that many works in OSR implicitly use the feature semantic information
to help identifying augmented classes. By contrast, our paper works on a general setting without suchdomain knowledge on the semantic information.
Although the approaches achieve nice empirical behavior and are underpinned by formal definitionsor theories, their generalization error over testing distribution are less explored. Exceptions areworks [16, 17, 18]. Authors focus on the Neyman-Pearson (NP) classification problem, where false
positive ratio on known classes are minimized with the constraint on desired novelty detection ratio,or vice. Scott and Blanchard [16] and Blanchard et al. [17] provide one-side generalization bounds
for both the novelty detection ratio and false positive ratio. However, the results mainly focus on
the binary NP classification problem. The generalization error and excess risk analysis for the
LAC problem, where multiple classes appear, is not investigated. Liu et al. [18] design a generalmeta-algorithm that can take any existing novelty detection approach as a subroutine to recognize
augmented classes. They contribute to the PAC-style guarantee for the meta-algorithm on the novelty
detection ratio, while performance on the false positive rate is less explored.
Learning with positive and unlabeled examples (LPUE), also known as PU learning, is a special
semi-supervised learning task aiming to train a classifier for the binary classification with the positive
and unlabeled data only [40, 27, 41, 42, 22]. One research line of LPUE is to exploit the risk rewriting
technique to establish unbiased estimators for classifier training, which have also been adopted in
our paper. The LAC problem with unlabeled data can be seen as a generalized LPUE problem bytaking the known classes as positive. However, most studies on LPUE mainly focus on the binary
scenario and established approaches are no longer unbiased in the multiclass case. For the multiclassscenario, Xu et al. [43] exploit the risk rewriting technique to train linear classifiers, which has also
been adopted by Tsuchiya et al. [44] for ordinal regression. Although sharing similarity with [43, 44],
our LAC risk is established in a quite different context and brings novel understandings for the LAC,
through which more complex changing environments could be handled. Besides, the LAC risk allows
more flexible implementations where the kernel method and deep model are applicable.

6

Experiments

We examine three aspects of the proposed E ULAC approach: (Q1) performance of classifying knownclasses and identifying augmented classes; (Q2) accuracy of estimating mixture prior θ and its
influence on E ULAC; (Q3) capability of handling the complex changing environments (augmentedclass appears and prior of known classes shifts simultaneously). We answer the questions in following
three subsections. In all experiments, classifiers are trained with labeled and unlabeled data, and are
evaluated with an additional testing dataset which is never observed in training.
7

Table 1: Macro-F1 scores on benchmark datasets. The best method is emphasized in bold. Besides, •indicates that E ULAC is significantly better than others (paired t-tests at 5% significance level).
W-SVM

OSNN

EVM

LACU-SVM

PAC-iForest

E ULAC

75.42 ± 4.87 •71.78 ± 5.12 •54.67 ± 9.80 •80.11 ± 3.80 •72.78 ± 5.19 •48.07 ± 3.80 •60.43 ± 7.65 •66.74 ± 2.76 •37.39 ± 14.1 •79.77 ± 4.97 •80.82 ± 9.38 •76.29 ± 13.2 •87.82 ± 4.64 •87.79 ± 3.95
45.96 ± 2.32 •68.91 ± 17.0 •75.38 ± 4.62 •58.48 ± 34.5 •63.14 ± 8.91 •85.10 ± 5.98
62.48 ± 11.2 •86.97 ± 3.79 •86.69 ± 3.39 •49.91 ± 6.88 •73.25 ± 9.23 •57.75 ± 10.9 •48.21 ± 16.4 •61.14 ± 6.27 •82.13 ± 5.88 •72.10 ± 8.16 •72.00 ± 8.33 •89.94 ± 1.30
51.24 ± 3.91 •76.00 ± 7.79 •58.39 ± 5.94 •–69.20 ± 8.34 •40.69 ± 12.5 •51.56 ± 17.3 •80.92 ± 3.68 •70.66 ± 6.18 •51.61 ± 3.31 •53.59 ± 9.88 •63.53 ± 7.58 •34.18 ± 13.4 •55.69 ± 13.3 •63.64 ± 13.1 •60.76 ± 7.79 •71.65 ± 5.46 •73.21 ± 4.52 •54.12 ± 7.19 •70.50 ± 7.16 •48.31 ± 9.62 •29.36 ± 8.70 •86.52 ± 2.72
86.17 ± 5.80
81.25 ± 6.18
91.54 ± 2.95
88.41 ± 4.81
77.33 ± 2.17
85.70 ± 4.46
80.66 ± 5.38
66.49 ± 17.9

9/ 0/ 08/ 1/ 08/ 1/ 08/ 1/ 09/ 0/ 09/ 0/ 0rank first 8/ 9

Macro-F1

E ULAC w/ t/ l

1.0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0

LACU-SVM
PAC-iForest
Eulac
250 500 750 1000 1250 1500
Number of unlabeled instances(a) mnist

1.0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0

LACU-SVM
PAC-iForest
Eulac
250 500 750 1000 1250 1500
Number of unlabeled instances(b) landset

Macro-F1OVR-SVM

usps
segment
satimage
optdigits
pendigits
SenseVehlandsetmnist
shuttleMacro-F1

Dataset

1.0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0

LACU-SVM
PAC-iForest
Eulac
250 500 750 1000 1250 1500
Number of unlabeled instances(c) usps

Figure 2: Macro-F1 score comparisons when the number of unlabeled data increases.
6.1

Performance Comparison

To answer Q1, we compare two implementations of E ULAC (RKHS-based and DNN-based versions)with contenders on several benchmark datasets for various tasks. The overall performance over testing
distribution is measured by the Macro-F1 score and accuracy. Meanwhile, we report AUC of augmented class score to evaluate the ability of identifying augmented classes. Due to space constraints,
we provide detailed descriptions of datasets, contenders and measures in the full paper [25].
Comparison on RKHS-based Eulac. We adopt 9 datasets, where half of the total classes are
randomly selected as augmented classes for 10 times. In each dataset, the labeled, unlabeled andtesting data contain 500, 1000 and 1000 instance respectively. The instance sampling procedure
repeats 10 times. Meanwhile, there are six contenders, including four without exploiting unlabeleddata (OVR-SVM, W-SVM [13], OSNN [14], EVM [15]) and two using them (LACU-SVM [6],PAC-iForest [11]). Table 1 reports performance in terms of Macro-F1 score. Similar results for
accuracy and AUC are shown in the full paper. We can see that E ULAC outperforms others in mostdatasets. Note that it is surprising that W-SVM and EVM achieve better results than LACU-SVM
and PAC-iForest, which are fed with unlabeled data. The reason might be that these methods require
to set parameters empirically and the default one may not be proper for all datasets. By contrast, ourproposed E ULAC can perform unbiased cross validation to select proper parameters.
Influence on the size of unlabeled data. We vary the size of unlabeled data from 250 to 1500 withan interval of 250 on 3 datasets: mnist, landset, and usps. LACU-SVM and PAC-iForest are included
for comparison. Figure 2 presents the Macro-F1 score and shows that the score of LACU-SVM
remains unchanged or even drops in the three datasets, while performance of our approach is enhanced
when provided with more unlabeled data, which is consistent with theoretical analysis in Section 4.
This again validates that our approach can exploit unlabeled data effectively. Notice that PAC-iForest
also enjoys sound theoretical guarantees, yet the guarantees only hold for the novelty detection ratio
and thus the overall performance on the testing distribution is not promised to be improved.
Comparison on deep models. We also evaluate DNNTable 2: AUC for DNN-based E ULAC
based E ULAC, where the sigmoid loss ψ(z) = 1/(1 +Methods
mnist
Cifar-10
SVHN
exp(z)) is used for the non-negative risk. The experSoftMax
97.8 ± 0.6 67.7 ± 3.8 88.6 ± 1.4
iments are conducted on mnist, SVHN and Cifar-10
OpenMax
98.1 ± 0.5 69.5 ± 4.4 89.4 ± 1.3
G-OpenMax 98.4 ± 0.5 67.5 ± 4.4 89.6 ± 1.7
datasets, where six of all ten classes are randomly seOSRCI
98.8 ± 0.4 69.9 ± 3.8 91.0 ± 1.0
lected as known while the rest four are treated as augE ULAC
98.6 ± 0.4 85.2 ± 2.0 91.2 ± 2.8
mented. The contenders are SoftMax, OpenMax [45],G-OpenMax [46], OSRCI [47]. All methods are trained based on the standard training split. The
unlabeled data are sampled from part of the standard testing split and the rest instances are used forevaluation. Following the previous study [47], we report AUC of the augmented class in Table 2,8and results of contenders are also from [47]. DNN-based E ULAC can learn nice detection score for
identifying augmented classes, which validates its efficacy.
6.2

Issue of Mixture Proportion

Influence and accuracy on the estimation of θ. Figure 3
plots the sensitivity curve, where the estimated prior θb varies
from 0.1 to 0.9 under different ground-truth mixture proportions θ. We observe that a misspecified mixture proportion
will clearly lead to performance degeneration. Interestingly,
the degeneration is not isotropy—a larger misspecified value
would be much more benign than a smaller one. We markaveraged estimated values of KME-base () and KME-shift(F). Evidently, the estimator gives high-quality estimatedb close to the ground-truth value, which prevents ourprior θ,approach from performance degeneration.
6.3

Macro-F1

To answer Q2, we conduct experiments on mnist dataset, where the true mixture proportion varies
from 0.1 to 0.9. Other configurations are the same as those in Section 6.1.
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0

= 0.1
= 0.3

0.1

0.3

= 0.5
= 0.7

0.5 0.7 0.9
estimated prior

= 0.9

1

Figure 3: Influence and estimation accuracy of mixture proportion θ.

Handling Complex Changing Environments

To answer Q3, we compare our approach with several baselines when augmented classes appear andprior of known classes shifts simultaneously. The experiments are simulated on mnist dataset, whereclasses {1, 3, 5, 7, 9} are known and share the equal prior in labeled data. {2, 4, 6, 8, 10} are taken as
the augmented classes and account for 50% in unlabeled data. As for the prior shift in the testing
distribution, we scale the the prior of five known classes to [1 − α, 1 − α/2, 1, 1 + α/2, 1 + α] × 0.2
respectively, where parameter α controls shift intensity ranging from 0 to 0.7.
Contenders. Contenders include LACU-SVM, OVR-shift and three variants of E ULAC (E ULACbase, E ULAC-base++ and E ULAC-shift), where LACU-SVM and E ULAC-base do not consider theshift on known classes’ prior, while OVR-shift and E ULAC-base++ take it into account but are biased.
k
E ULAC-shift is the unbiased estimator. For all approaches, class prior θteis estimated by KME-shift.
Detailed descriptions of contenders can be found in the full paper [25].

Accuracy

0.90
Results. Since Macro-F1 is an insensitive measure for the
0.85
prior shift scenario, we report the accuracy for contenders
0.80
in Figure 4. First, with the increase of shift intensity, meth0.75
ods without considering prior shift (LACU-SVM, E ULAC0.70
base) suffer from marked performance degeneration, which
0.65
shows the importance for handling distribution change of
0.60
LACU-SVM
Eulac-base
Eulac-shift
known classes with augmented classes. Besides, E ULAC0.55
OVR-shift
Eulac-base++shift achieves the best accuracy with high shift intensity and
0.50
0
0.3
0.5
0.7
retains comparable performance with its baselines whenshift intensity
there is no prior shift. The results validate the efficacy and Figure 4: Comparison in complex environments (augmented classes & prior shift).
safety of our proposal in complex environments.

7

Conclusion

In this paper, we investigate the problem of learning with unobserved augmented classes by exploiting
unlabeled training data. We introduce the class shift condition to connect known and augmentedclasses, based on which an unbiased risk estimator can be established. By empirically minimizing
the risk estimator with various hypothesis sets, we design the E ULAC approach, supported by bothconsistency and generalization error analysis. Moreover, with the generalized class shift condition,
we show the potential of our approach for handling a more general setting of class distribution change,
where augmented classes appear and the prior of known classes shifts simultaneously. Extensive
empirical studies confirm the effectiveness of the proposed approach. In the future, we will investigate
whether our approach can be tailored for the streaming setting. Besides, it is also interesting toconsider even more general scenarios of class distribution change than the problem settings studied
in this paper, in order to handle more realistic changing environments.
9

Acknowledgements
This research was supported by the NSFC (61751306, 61921006) and the Collaborative Innovation
Center of Novel Software Technology and Industrialization. Meanwhile, the authors want to thankYu-Hu Yan for reading the draft and the anonymous reviewers for the helpful and insightful comments.

Broader Impact
In this paper, we develop the E ULAC, an approach exploiting unlabeled data for learning withaugmented classes. The augmented classes appear in many applications, such as unobserved animals
appear in species recognition task [1] and unexpected background images exist in object detection [12].
Our approach offers a way to improve the robustness of the learning system for these applications byidentifying the unseen augmented classes more accurately. Nevertheless, we also admit it would raise
concerns when applying these techniques to some malicious applications. For example, one could
employ ML systems to detect rare animals, resulting in an increased probability of rare animals being
hunted and thus making the animals even more dangerous. Therefore, we should call for laws andregulations to limits the use of ML techniques in such applications.
On the other hand, it is also crucial to facilitate learning systems with the capability of tackling theaugmented classes. Many applications require such robustness and will benefit from our techniques,
and the potential risk is believed to be manageable with more sound human regulations.

References[1] Thomas G. Dietterich. Steps toward robust artificial intelligence. AI Magazine, 38(3):3–24,
2017.
[2] Zhi-Hua Zhou. Learnware: on the future of machine learning. Frontiers of Computer Science,10(4):589–590, 2016.
[3] Masashi Sugiyama and Motoaki Kawanabe. Machine Learning in Non-Stationary Environments:
Introduction to Covariate Shift Adaptation. The MIT Press, 2012.
[4] João Gama, Indre Zliobaite, Albert Bifet, Mykola Pechenizkiy, and Abdelhamid Bouchachia. A
survey on concept drift adaptation. ACM Computing Surveys, 46(4):44:1–44:37, 2014.
[5] Peng Zhao, Xinqiang Wang, Siyu Xie, Lei Guo, and Zhi-Hua Zhou. Distribution-free one-passlearning. IEEE Transaction on Knowledge and Data Engineering, 2019. doi: 10.1109/TKDE.
2019.2937078.
[6] Qing Da, Yang Yu, and Zhi-Hua Zhou. Learning with augmented class by exploiting unlabeled
data. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), pages
1760–1766, 2014.
[7] Bernhard Schölkopf, John C. Platt, John Shawe-Taylor, Alexander J. Smola, and Robert C.
Williamson. Estimating the support of a high-dimensional distribution. Neural Computation,
13(7):1443–1471, 2001.
[8] David M. J. Tax and Robert P. W. Duin. Support vector data description. Machine Learning, 54(1):45–66, 2004.
[9] Emanuel Parzen. On estimation of a probability density function and mode. The Annals of
Mathematical Statistics, 33(3):1065–1076, 1962.
[10] JooSeuk Kim and Clayton D. Scott. Robust kernel density estimation. Journal of Machine
Learning Research, 13(1):2529–2565, 2012.
[11] Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation forest. In Proceedings of the 8thIEEE International Conference on Data Mining (ICDM), pages 413–422, 2008.
[12] Walter J. Scheirer, Anderson Rocha, Archana Sapkota, and Terrance E. Boult. Towards open
set recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(7):1757–1772, 2013.
10

[13] Walter J. Scheirer, Lalit P. Jain, and Terrance E. Boult. Probability models for open set
recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(11):2317–
2324, 2014.
[14] Pedro Ribeiro Mendes-Junior, Roberto Medeiros de Souza, Rafael de Oliveira Werneck,
Bernardo V. Stein, Daniel V. Pazinato, Waldir R. de Almeida, Otávio A. B. Penatti, Ricardoda Silva Torres, and Anderson Rocha. Nearest neighbors distance ratio open-set classifier.
Machine Learning, 106(3):359–386, 2017.
[15] Ethan M. Rudd, Lalit P. Jain, Walter J. Scheirer, and Terrance E. Boult. The extreme value
machine. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(3):762–768,
2018.
[16] Clayton Scott and Gilles Blanchard. Novelty detection: Unlabeled data definitely help. In
Proceedings of the 12th International Conference on Artificial Intelligence and Statistics(AISTATS), pages 464–471, 2009.
[17] Gilles Blanchard, Gyemin Lee, and Clayton Scott. Semi-supervised novelty detection. Journalof Machine Learning Research, 13:2973–3009, 2010.
[18] Si Liu, Risheek Garrepalli, Thomas G. Dietterich, Alan Fern, and Dan Hendrycks. Open
category detection with PAC guarantees. In Proceedings of the 35th International Conference
on Machine Learning (ICML), pages 3175–3184, 2018.
[19] Tong Zhang. Statistical analysis of some multi-category large margin classification methods.
Journal of Machine Learning Research, 5:1225–1251, 2004.
[20] Ryan M. Rifkin and Aldebaro Klautau. In defense of one-vs-all classification. Journal of
Machine Learning Research, 5:101–141, 2004.
[21] Nagarajan Natarajan, Inderjit S. Dhillon, Pradeep Ravikumar, and Ambuj Tewari. Learningwith noisy labels. In Advances in Neural Information Processing Systems 26 (NeurIPS), pages
1196–1204, 2013.
[22] Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama. Convex formulation forlearning from positive and unlabeled data. In Proceedings of the 32nd International Conference
on Machine Learning (ICML), pages 1386–1394, 2015.
[23] Bernhard Scholkopf and Alexander J. Smola. Learning with Kernels: Support Vector Machines,
Regularization, Optimization, and Beyond. The MIT Press, 2001.
[24] Ryuichi Kiryo, Gang Niu, Marthinus Christoffel du Plessis, and Masashi Sugiyama. Positiveunlabeled learning with non-negative risk estimator. In Advances in Neural Information
Processing Systems 30 (NeurIPS), pages 1675–1685, 2017.
[25] Yu-Jie Zhang, Peng Zhao, Lanjihong Ma, and Zhi-Hua Zhou. An unbiased risk estimator forlearning with augmented classes. arXiv:1910.09388, 2019.
[26] Harish G. Ramaswamy, Clayton Scott, and Ambuj Tewari. Mixture proportion estimation via
kernel embeddings of distributions. In Proceedings of the 33rd International Conference on
Machine Learning (ICML), pages 2052–2060, 2016.
[27] Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled data. In
Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery andData Mining (KDD), pages 213–220, 2008.
[28] Shantanu Jain, Martha White, Michael W. Trosset, and Predrag Radivojac. Nonparametricsemi-supervised learning of class proportions. arXiv:1601.01944, 2016.
[29] Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama. Class-prior estimation forlearning from positive and unlabeled data. Machine Learning, 106(4):463–492, 2017.
[30] Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Introduction to statistical learningtheory. In Advanced Lectures on Machine Learning, Machine Learning Summer Schools 2003,
pages 169–207, 2003.
11

[31] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning,
2nd Edition. The MIT Press, 2012.
[32] Zhi-Hua Zhou and Zhaoqian Chen. Hybrid decision tree. Knowledge-Based Systems, 15(8):515–528, 2002.
[33] Si-Yu Ding, Xu-Ying Liu, and Min-Ling Zhang. Imbalanced augmented class learning with
unlabeled data by label confidence propagation. In Proceedings of the 18th IEEE International
Conference on Data Mining (ICDM), pages 79–88, 2018.
[34] Michael Fink, Shai Shalev-Shwartz, Yoram Singer, and Shimon Ullman. Online multiclasslearning by interclass hypothesis sharing. In Proceedings of the 23rd International Conference
on Machine Learning (ICML), pages 313–320, 2006.
[35] Michael D. Muhlbaier, Apostolos Topalis, and Robi Polikar. Learn++ .nc: Combining ensembleof classifiers with dynamically weighted consult-and-vote for efficient incremental learning of
new classes. IEEE Transactions on Neural Networks and Learning Systems, 20(1):152–168,
2009.
[36] Xin Mu, Kai Ming Ting, and Zhi-Hua Zhou. Classification under streaming emerging newclasses: A solution using completely-random trees. IEEE Transactions on Knowledge and Data
Engineering, 29(8):1605–1618, 2017.
[37] Xin-Qiang Cai, Peng Zhao, Kai Ming Ting, Xin Mu, and Yuan Jiang. Nearest neighborensembles: An effective method for difficult problems in streaming classification with emerging
new classes. In Proceedings of the 19th International Conference on Data Mining (ICDM),
pages 970–975, 2019.
[38] Chuanxing Geng, Sheng-Jun Huang, and Songcan Chen. Recent advances in open set recognition: A survey. arXiv: 1811.08581, 2018.
[39] Yang Yu, Wei-Yang Qu, Nan Li, and Zimin Guo. Open category classification by adversarial
sample generation. In Proceedings of the Twenty-Sixth International Joint Conference on
Artificial Intelligence (IJCAI), pages 3357–3363, 2017.
[40] Bing Liu, Wee Sun Lee, Philip S. Yu, and Xiaoli Li. Partially supervised classification of text
documents. In Proceedings of the Nineteenth International Conference on Machine Learning(ICML), pages 387–394, 2002.
[41] Gill Ward, Trevor Hastie, Simon Barry, Jane Elith, and John R Leathwick. Presence-only data
and the EM algorithm. Biometrics, 65(2):554–563, 2009.
[42] Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learningfrom positive and unlabeled data. In Advances in Neural Information Processing Systems 27(NeurIPS), pages 703–711, 2014.
[43] Yixing Xu, Chang Xu, Chao Xu, and Dacheng Tao. Multi-positive and unlabeled learning. In
Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), pages
3182–3188, 2017.
[44] Taira Tsuchiya, Nontawat Charoenphakdee, Issei Sato, and Masashi Sugiyama. Semi-supervised
ordinal regression based on empirical risk minimization. arXiv:1901.11351, 2019.
[45] Abhijit Bendale and Terrance E. Boult. Towards open set deep networks. In Proceedings ofthe IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1563–1572,
2016.
[46] Zongyuan Ge, Sergey Demyanov, and Rahil Garnavi. Generative openmax for multi-class open
set classification. In Proceedings of the British Machine Vision Conference 2017 (BMCV), 2017.
[47] Lawrence Neal, Matthew Olson, Xiaoli Fern, Weng-Keen Wong, and Fuxin Li. Open set
learning with counterfactual images. In Proceedings of the European Conference on Computer
Vision (ECCV), pages 613–628, 2018.

12