On the Learning with Augmented Class via Forests

1 Introduction

How to handle distribution changes has become an important problem in a non-stationary learning environment [Zhou, 2022], and recent years have witnessed increasing attentions with various applications [Gama et al., 2014; Geng et al., 2021; Wang et al., 2024]. This work focuses on learning with augmented class, that is, the class distribution changes and an augmented class unseen in the training data may emerge during the testing process [Da et al., 2014]. Here, we take object recognition in autonomous driving for example: new objects may appear on roads yet not in the historical labeled data, and a reliable learning system should make good predictions over both known classes and augmented class.

Various approaches have been developed for learning with augmented class. Da et al. [2014] studied decision boundaries for augmented class under the low-density assumption. Bendale and Boult [2016] and Rudd et al. [2017] estimated the probability of an instance belonging to augmented class on the basis of extreme value theory. Mendes J´unior et al. [2017] detected augmented class by a nearest neighbor method, and Liu et al. [2018] presented PAC guarantees for the detection of augmented class. Some generative networks have also been applied to learn augmented class [Ge et al., 2017; Neal et al., 2018; Chen et al., 2021]. Zhang et al. [2020] gave an unbiased risk estimation by exploiting unlabeled data, and Shu et al. [2023] generalized such approach to arbitrary loss functions.

Decision trees and forests have achieved great successes in various applications with strong generalization in handling discrete features and exploring local regions [Cutler et al., 2007; Qi, 2012; Grinsztajn et al., 2022; Costa and Pedreira, 2023]. Most previous studies worked on the same distribution between training and testing data. For augmented class, Mu et al. [2017] and Liu et al. [2018] only studied its detection from labeled data of known classes, whereas it remains open on how to construct trees for learning with augmented class by exploiting unlabeled data from testing data.

This work aims to incorporate some useful information of augmented class into the construction of forests, and our main contributions can be summarized as follows:

• We introduce a new splitting criterion, i.e., augmented Gini impurity, to incorporate information of augmented class from unlabeled data during the trees' splitting. We develop the LACForest approach for learning with augmented class, which constructs shallow forests by augmented Gini impurity and considers pseudo-labeled augmented instances for better performance.
• For complex data with intrinsic structures (e.g., images), we develop deep neural forests for learning with augmented class, because of their powerful representations with an end-to-end training manner. We propose a new optimization objective for deep neural forests to learn augmented class, and the basic idea is to extend our augmented Gini impurity into a differentiable form by considering the mechanism of deep neural trees.
• From a theoretical view, we present the convergence analysis of our augmented Gini impurity with respect to both decision trees and deep neural trees. We finally conduct extensive experiments to validate the effectiveness of our proposed approaches and perform some parameter influence analysis.

The rest of this work is organized as follows: Section 2 gives some preliminaries. Section 3 introduces augmented Gini impurity and LACForest approach. Section 4 presents our deep neural approach. Section 5 conducts some extensive experiments. Section 6 concludes with future works.

2 Preliminaries

Let X ⊆ Rd and Y = {1, . . . , κ, κ + 1} be the instance and class spaces, respectively. Suppose that D is an underlying (unknown) distribution over X × Y, and denote by DX its marginal distribution over X. We focus on learning with augmented class [Da et al., 2014], where the first κ classes can be observed in training data, while the (κ + 1)-th class will merely emerge in testing data, which is known as an augmented class in training phase.

For known classes and augmented class, let Dkc and Dac be the marginal distributions over space X × {1, . . . , κ} and X × {κ + 1} from distribution D, respectively. We introduce the class shift assumption as follows:

Assumption 1. We say that distribution D and its marginal distributions Dkc and Dac satisfy class shift assumption if

This assumption correlates data distributions for known classes and augmented class, which has been well-studied for learning with augmented class [Zhang et al., 2020; Shu et al., 2023] and open-set recognition [Scheirer et al., 2013].

We focus on the semi-supervised setting for learning with augmented class [Da et al., 2014; Liu et al., 2018; Zhang et al., 2020; Shu et al., 2023], and the goal is to learn a function f : X → Y from labeled data Sl and unlabeled data Su with

Here, each labeled example (xli , yi) is drawn i.i.d. fromDkc, and each unlabeled instance xuj is sampled i.i.d. fromDX .

Let I[·] be the indicator function, which returns 1 if the argument is true and 0 otherwise. For integer k > 0, we write [k] = {1, 2, · · · , k}, and denote by ∆k the k-dimensional simplex. For z ∈ R, we denote by ⌊z⌋ the largest integer no more than z, and define (z)+ = max(0, z). Let |A| be the cardinality of set A.

3 Our LACForest Approach

This section proposes the LACForest approach for learning with augmented class based on random forests, and the core idea is to introduce a new splitting criterion, augmented Gini impurity, to incorporate potential information of augmented instances during the construction of decision trees.

3.1 Augmented Gini Impurity

For instance space C ⊆ X, unlabeled data Su and labeled data Sl, we introduce

Denote by nC,l = |SC,l| and nC,u = |SC,u|. We could define the augmented Gini impurity as a splitting criterion.

Definition 1. For an instance space C ⊆ X, we define the augmented Gini impurity GC(Sl, Su) w.r.t. Sl and Su as

Here, ϑC,κ+1(Sl, Su) is defined as

where θ is given in Eqn. (1); and for k ∈ [κ], we define

This definition essentially follows the original Gini impurity [Breiman, 1984], except with an additional term ϑC,κ+1(Sl, Su), which aims to incorporate some information of augmented class into impurity measure.

Figure 1 presents an intuitive illustration on the difference between our augmented and original Gini impurity over a 2-dimensional synthetic dataset. It is observable that our augmented Gini impurity could properly take augmented data into consideration compared with Gini impurity.

Lemma 1. For δ ∈ (0, 1) and instance space C ⊆ X, the following holds with probability at least 1-δ over Sl and Su

if nC,u/nu ≥ γ for some constant γ ∈ (0, 1).

Let L∗C be the optimal squared loss over distribution D under the condition x ∈ C as follows:

where ˜ y ∈ Rκ+1 is the one-hot encoding of y ∈ [κ + 1]. Intuitively, L∗C shows the minimum expected squared loss under the same prediction for all instances in space C.

Based on Lemma 1 and Assumption 1, we have

Theorem 1. For δ ∈ (0, 1) and instance space C ⊆ X, the following holds with probability at least 1-δ over Sl and Su

if nC,u/nu ≥ γ and nC,l/nl ≥ γ for constant γ ∈ (0, 1).

This theorem shows that our augmented Gini impurity can be viewed as a good estimation of L∗C with the convergence rate O(1/√min{nl, nu}). The detailed proof is given in our full work [Xu et al., 2025], which involves the equivalence between splitting criterions and loss functions, as well as the convergence of ϑC,κ+1(Sl, Su) in Lemma 1.

3.2 Construction of LACForest

A tree model can be constructed by partitioning instance space into disjoint rectangular nodes recursively. Given node C ⊆ X , splitting feature j ∈ [d] and splitting point a ∈ R, we denote by the left and right children as

respectively. We then solve the optimal splitting feature j ∗ and splitting point a∗ from the following optimization

where the reduction of augmented Gini impurity is given by

From Theorem 1, we can distinguish augmented class from known classes in node C by solving Eqn. (4), as it converges to optimizing the squared loss as training data increases. From a theoretical view, we require sufficient training data in each node C, i.e., nC,l ≥ γnl and nC,u ≥ γnu for some γ ∈ (0, 1) in Theorem 1; therefore, we should construct relatively shallow tree models.

On the other hand, we should take deeper tree models for better performance, and it is well-known that better predictions could be obtained by deepening tree models sufficiently [Quinlan, 1986; Hastie et al., 2009]. Hence, our algorithm includes two main steps as follows:

Step-I: Exploration of Augmented Instances

We preliminarily construct m random trees T ′ 1 , · · · , T ′m for the exploration of augmented instances from Eqn. (4). For simplicity, we present the detailed construction of tree T ′ 1 , and consider other trees similarly. We initialize T ′ 1 with one root node of instance space X, and recursively repeat a procedure for each leaf node as follows:

• Select a τ-subset S from d available features randomly without replacement;
• Solve the optimal splitting feature j ∗ ∈ S and point a∗ according to Eqn. (4) under the constraints

This ensures sufficient instances in each splitting node from Theorem 1;

• Split current node into left and right children via the optimal splitting feature j ∗ and position a∗ .

Algorithm 1 Our LACForest approach

Input: Labeled data Sl, unlabeled data Su, proportion θ, hyper-parameters m, τ, γ

% Step-I: Exploration of Augmented Instances.

• 1: for i ∈ {1, · · · ,m} do
• 2: Grow random tree T ′ i based on Sl and Su according to the reduction of augmented Gini impurity .
• 3: end for
• % Step-II: Improvement of Prediction Performance
• 4: Calculate LF ′κ+1 (x) for x ∈ Su by Eqn. (7).
• 5: Label top np = ⌊θnu⌋ instances in Su of the highest LF ′κ+1 (x) and obtain ˜ S.
• 6: for i ∈ {1, · · · ,m} do
• 7: Split random tree T ′ i based on Sl ∪ ˜ S according to the reduction of Gini impurity and obtain Ti.
• 8: end for

The above procedure is stopped if there is no feasible solution for Eqn. (4) under constraints in Eqns. (5) and (6).

Given random tree T ′ 1 with t′ leaves C ′1 , C ′2 , · · · , C ′t′ , we present the probability of augmented class for x ∈ X as

where ϑC′j ,κ+1(Sl, Su) is an unbiased estimator for the proportion of augmented instances in C ′j , given by Definition 1.

Step-II: Improvement of Prediction Performance

Given m trees T ′ 1 , · · · , T ′m, we calculate the average augmented score of instance x ∈ X by

We then select ⌊θnu⌋ instances in Su of the highest average augmented scores, and label them with pseudo-labels of augmented class. Without loss of generality, we denote by

Intuitively, ˜ S retains the most likely augmented instances for further partition, and similar approaches have been studied by [Liu et al., 2002; Tanha et al., 2017].

We further partition T ′ 1 , · · · , T ′m for better predictions based on ˜ S ∪ Sl. We also repeat the following procedure recursively for each leaf C of T ′ 1 :

• Select a τ-subset S from d available features randomly without replacement;
• Solve the optimal splitting feature j ∗ ∈ S and position a∗ w.r.t. Gini impurity and instances in ˜ S ∪ Sl;
• Split the current node into left and right children via the optimal splitting feature j ∗ and position a∗ .

The above procedure is stopped if all instances have the same label in a leaf, and get the final random tree T1. Similarly, we repeat the above procedure for T ′ 2 , · · · , T ′m.

Given m random trees T1, · · · , Tm, we predict the final label of instance x ∈ X as

where Ti,k(x) is the probability of the k-th category of tree Ti with leaves Ci,1, Ci,2, · · · , Ci,ti , i.e.,

Algorithm 1 gives detailed descriptions of our LACForest approach. Notice that our method requires the proportion θ of augmented class, which is usually unknown in practice. One feasible solution is to consider the kernel mean embedding method from [Ramaswamy et al., 2016], and this is similar to previous studies on learning with augmented class [Zhang et al., 2020; Shu et al., 2023].

4 Deep Neural LACForest

This section explores deep neural forests via augmented Gini impurity for learning with augmented class, which presents powerful representations with an end-to-end training manner for complex data such as images and texts. For neural forests, another advantage is to take soft splits rather than hard splits of decision trees, which could yield smoother decision boundaries and avoid overfitting [Kontschieder et al., 2015]. In this work ,we take one step on learning with augmented class via deep neural forests, while previous works mostly focused on all known classes [Kontschieder et al., 2015; Tanno et al., 2019; Ji et al., 2020; Li et al., 2024].

4.1 Augmented Gini Impurity for Neural Trees

A deep neural forest is constructed with a DNN encoder h and m differentiable neural trees DT1,DT2, · · · ,DTm. The key point is how to learn differentiable neural trees by incorporating information of augmented class, and our idea is to consider augmented Gini impurity as an optimization objective for neural trees.

We take neural tree DT1 as an example, and it is essentially an l-layer complete binary tree with l ≥ 2. We denote by {B1, · · · , Bt} and {Bt+1, · · · , B2t+2} all internal and leaf nodes of DT1, respectively, where t = 2l-1 - 1.

For every internal node Bi (i ∈ [t]), we associate with a function fi : X → [0, 1] to represent the probability of being assigned to the left child, and hence the probability of the right child is 1 - fi(x). Given encoder h, we define

where sigmoid(z) = (1+exp(-z))-1 and wi, bi are learned parameters, as in [Kontschieder et al., 2015].

For every leaf node Bi (i ∈ [2t + 2] \ [t]), let I(x → Bi) be the event that x is assigned to leaf Bi, and denote by

.

Algorithm 2 Deep Neural LACForest

Input: Labeled data Sl, unlabeled data Su, proportion θ, hyper-parameters m, l, T, λce

• 1: Randomly initialize h and DT1, · · · ,DTm.
• 2: for j ∈ {1, · · · , T} do
• 3: Break Sl and Su into randommini-batches.
• 4: for mini-batches S′ l and S′u from Sl and Su do
• 5: Compute L by Eqn. (10) and compute gradients.
• 6: Update h and DT1, · · · ,DTm by SGD.
• 7: end for
• 8: end for

where Bi ↙ Bj and Bj ↘ Bi represent that Bi belongs to the left and right subtrees of Bj , respectively. We also denote by

for unlabeled data Su and labeled data Sl, respectively.

Definition 2. For i ∈ [2t + 2] \ [t], we define the augmented Gini impurity w.r.t. Sl and Su as

where ϑBi,κ+1(Sl, Su) is defined as

and for k ∈ [κ], ϑBi,k(Sl, Su) is given by

This definition follows the augmented Gini impurity of decision trees in Definition 1, whereas deep neural trees consider probabilistic assignment of instances to nodes while the latter focuses on deterministic assignment. Essentially, ϑBi,k(Sl, Su) estimates the probability of the k-th class under the condition I(x → Bi). Based on Assumption 1, we have

Lemma 2. For k ∈ [κ + 1], δ ∈ (0, 1) and i ∈ [2t + 2] \ [t], we have, with probability at least 1 - δ over Sl and Su,

if ED[µBi (x)] ≥ γ, EDkc [µBi (x)] ≥ γ, nBi,u ≥ γnu and nBi,l ≥ γnl for some constant γ ∈ (0, 1).

Denote by L∗Bi the optimal squared loss under I(x → Bi):

where ˜ y ∈ Rκ+1 is the one-hot encoding of y ∈ [κ + 1]. Based on Assumption 1 and Lemma 2, we have Theorem 2. For δ ∈ (0, 1) and i ∈ [2t+2]\[t], the following holds with probability at least 1 - δ over Sl and Su

if ED[µBi (x)] ≥ γ, EDkc [µBi (x)] ≥ γ, nBi,u ≥ γnu and nBi,l ≥ γnl for some constant γ ∈ (0, 1).

This theorem shows that GBi (Sl, Su) could be seen as an unbiased estimation of L∗Bi . The detailed proof is presented in [Xu et al., 2025], which is similar to that of Theorem 1, but takes different analysis on the convergence of ϑBi,k(Sl, Su) by considering the probabilistic assignment of neural trees.

4.2 Deep Neural LACForest

In the training phase, we randomly initialize encoder h and neural trees DT1, · · · ,DTm, and update the encoder and neural trees iteratively. In each iteration, we receive two minibatches of labeled data S′ l and unlabeled data S′u sampled randomly from Sl and Su, respectively. We introduce

where {Bi,j}j∈[2t+2]\[t] denote all leaf nodes of DTi, and ωi,j(S′u ) is the proportion of unlabeled data in Bi,j, i.e.,

The augmented Gini loss in Eqn. (9) is a weighted average augmented Gini impurity for all leaf nodes of DTi.

For better representation, we introduce an auxiliary linear predictor g : Rd′ → ∆κ as done in [Yan et al., 2021], and take the cross entropy loss on known classes w.r.t. S′ l as

We finally get the optimization objective as follows:

where λce > 0 is a trade-off parameter. Intuitively, the cross entropy loss is beneficial to learning a basic representation of target data, and the augmented gini loss could improve the ability of neural trees to distinguish augmented class from known classes, as shown by Theorem 2.

Notice that the optimization objective L in Eqn. (10) is differentiable w.r.t. the parameters of feature encoder h and neural trees DT1, · · · ,DTm, and we could update the entire model with stochastic gradient descent directly.

Given feature encoder h and neural trees DT1, · · ·DTm, we could present the prediction for instance x ∈ X as

where DTi,k(x) shows the probability of the k-th class w.r.t. neural tree DTi, i.e.,

with ϑBi,j ,k(Sl, Su) given by Definition 2.

Algorithm 2 presents the detailed description of our deep neural LACForest approach. In experiments, we should take relatively large batch sizes for mini-batches S′ l and S′u , since GBi,j (S′ l , S′u ) in Eqn. (9) converges to the optimal squared loss in the rate of O(1/√min{|S′ l |, |S′u |}) from Theorem 2.

4.3 RelatedWorks

Zhou and Chen [2002] introduced the problem of classincremental learning via a few labeled augmented instances. Fink et al. [2006] learned multiple binary classifiers for this problem and Topalis and Polikar [2008] considered voting classifiers. Recent years have witnessed increasing attention on the design of practical algorithms for this problem [Li and Hoiem, 2017; Rebuffi et al., 2017; Yan et al., 2021; Zou et al., 2022; Zhou et al., 2024]. These methods can not be applied to our learning scenario directly, since we have no access to any labeled augmented instances.

Another relevant problem is open-set recognition in computer vision. Scheirer et al. [2013] introduced open space risk to penalize predictions outside the support of training data. Along this line, various approaches have been developed based on open space risk [Scheirer et al., 2014], extreme value theory [Bendale and Boult, 2016; Rudd et al., 2017], nearest neighbors [Mendes J´unior et al., 2017] and generative neural networks [Ge et al., 2017; Neal et al., 2018; Chen et al., 2021]. Those studies are strongly based on some geometric assumptions.

5 Experiments

We conduct experiments on 15 benchmark datasets and 5 image datasets, and the details are summarized in Table 1. Most datasets have been well-studied in previous works on learning with augmented class.

datasets

Figure 2: Experimental comparisons of AUC on the detection of augmented class.

5.1 Evaluation of Our LACForest Approach

For our LACForest approach, we compare with seven stateof-the-art approaches: GLAC [Shu et al., 2023], EULAC [Zhang et al., 2020], PAC-iForest [Liu et al., 2018], EVM [Rudd et al., 2017], OSNN [Mendes J´unior et al., 2017], LACU-SVM [Da et al., 2014] and OVR-SVM [Rifkin and Klautau, 2004]. More details on these approaches could be found in our full work [Xu et al., 2025].

For each dataset, we randomly select half of classes as the augmented class with the rest as known classes, following [Zhang et al., 2020]. We then randomly sample 500 examples of known classes as labeled data Sl, and 1000 instances as unlabeled data Su and 100 instances as testing data. We take θ = 0.5 in Eqn. (1), and more experimental settings could be found in [Xu et al., 2025]. The performance is evaluated by 10 trials of random selections of augmented class, and with 10 times of random data sampling. The average test accuracies are obtained over these 100 runs, as shown in Table 2.

It is clear that our LACForest method achieves significantly better performance than previous EVM, OSNN, PAC-iForest and OVR-SVM, as our LACForest wins in most times and never loses. This is because those methods mainly focus on labeled data from known classes, but without exploring information from unlabeled data.

Our LACForest also outperforms LACU-SVM, which is heavily dependent on the low-separation assumption over data. In comparison to GLAC and EULAC, our LACForest achieves better and comparable performance in most times, except for datasets mfcc and drybean, partially because of class imbalance in these datasets, which makes it difficult to accurately estimate proportions of augmented class in nodes.

We also take the average AUC to show the performance on the detection of augmented class in Figure 2. It is obvious that our LACForest takes better and comparable performance on the detection of augmented class over most datasets, since our method could explore augmented class effectively in each leaf node, as shown by Lemma 1.

5.2 Evaluation of Our Deep Neural LACForest

For our deep neural LACForest, we compare with seven deep learning methods for augmented class: Deep-GLAC [Shu et al., 2023], ARPL [Chen et al., 2021], Deep-EULAC [Zhang et al., 2020], OSRCI [Neal et al., 2018], G-Openmax [Ge et al., 2017], Openmax [Bendale and Boult, 2016] and SoftmaxT [Hendrycks and Gimpel, 2016]. More details on these approaches are presented in our full work [Xu et al., 2025].

We take a three-layer convolutional neural network as the backbone neural network on mnist, fmnist and kuzushiji, and consider VGG16 [Simonyan and Zisserman, 2015] on svhn and cifar10, as done in [Shu et al., 2023]. We randomly select four classes as the augmented class and take the rest as known classes, and set θ = 0.4 similarly to [Shu et al., 2023].

We take average test accuracies over 5 random selections of augmented class as our performance measure, and the experimental comparisons are shown in Table 3. It is clear that our approach takes better performance than ARPL, GOpenmax, OSRCI, Openmax and Softmax-T, due to some additional geometric assumptions over those methods. For Deep-GLAC and Deep-EULAC, our method achieves better and comparable performance in most times, and an intuitive explanation is that our approach could effectively explore augmented class from each local region during tree partitions.

Parameter Influence. We analyze the influence of various parameters on several datasets, and the trends are similar for other datasets. Figure 3 shows that our LACForest gets better performance under different proportions θ ∈ [0.3, 0.8] for augmented data. Figure 4 shows the performance with different sizes of unlabeled data, where our LACForest achieves better and stable performance with the increase of unlabeled data, in consistency with Theorem 1. For deep neural LACForest, Figure 5 shows that our approach is insensitive to parameter λce and generally works well for λce ∈ [0.2, 2]. Figure 6 shows the influence of the depth of neural trees, and our method takes stable results when the tree depth l ≥ 5.

Figure 6: Influence of neural trees' depth.

6 Conclusion

This work studies learning with augmented class via forests, where an augmented class may appear in testing data yet not in training data. We introduce the augmented Gini impurity as a new splitting criterion by incorporating information of augmented class during tree construction. We develop the approach on Learning with Augmented Class via Forests, which constructs shallow forests based on augmented Gini impurity and further splits forests with pseudo-labeled augmented instances. We also explore deep neural forests with a new optimization objective via our augmented Gini impurity. We validate the effectiveness of our methods both empirically and theoretically. An interesting future direction is to exploit our methods under other learning settings such as streaming datasets and multiple augmented classes.

Acknowledgments

The authors want to thank the reviewers for their helpful comments and suggestions. This research was supported by National Key R&D Program of China (2021ZD0112802) and NSFC (62376119). Wei Gao is the corresponding author.