Learning Adaptive Embedding Considering Incremental Class

Without any loss of generality, at initial time, we have a supervised training set $D^{0}=\{({\bf x}_{i}^{0},{\bf y}_{i}^{0})\}_{i=1}^{N}$, where ${\bf x}_{i}^{0}\in\mathbb{R}^{d}$ denotes the $i-$th instance, and ${\bf y}_{i}^{0}\in Y^{0}=\{1,2,\cdots,C\}$ denotes corresponding label, $0$ represents initial time. Then, we receive a non-stationary unlabeled testing data $D^{1}=\{({\bf x}_{j})\}_{j=1}^{N_{1}}$, where ${\bf x}_{j}\in\mathbb{R}^{d}$ denotes the $j-$th instance, and label ${\bf y}_{j}\in\hat{Y}=\{1,2,\cdots,C,C+1,\cdots,C+K^{1}\}$ is unknown, $K^{1}$ is the number of unknown classes. Thus, novel class detection can be defined as:

On the other hand, it is notable that streaming data with novel classes has two characteristics: (1) Data window. At time window $t$, we only get the data of current time window, not the full amount of streaming data for detection; and (2) Novel class continuity. At time window $t$, only partial novel classes will appear, or even no novel classes. Therefore, we need to incrementally detect novel classes, i.e., with the streaming data, every time after receiving the data of time window $t$, NCD is performed [30]. Specifically, the streaming test data $D$ can be denoted as $D=\{D^{t}\}_{t=1}^{T}$, where $D^{t}=\{{\bf x}_{j}^{t}\}_{j=1}^{N_{t}}$ is with $N_{t}$ unlabeled instances, and the underlying label ${\bf y}_{j}^{t}\in\hat{Y}^{t}$ is unknown, $\hat{Y}^{t}=\hat{Y}^{t-1}\cup Y^{t}$, where $\hat{Y}^{t-1}$ is the cumulative known classes until $(t-1)-$th time window and $Y^{t}$ is the new classes in $t-$th window. $\hat{Y}^{T}=\hat{Y}=\{1,2,\cdots,C,C+1,\cdots,C+K\}$. Therefore, we can give the definition of class-incremental learning:

Note that there exist two labeling cases after novel class detection, i.e., manually labeling or self-taught labeling [20]. We consider manually labeling following most approaches [30, 20, 17] to avoid label noise accumulation, and is more in line with real-world applications.

The main idea of CILF is to learn the feature embeddings such that instances exhibit distinguishing characteristics for label prediction, novel class detection, and subsequent model update over the non-stationary streaming data. Therefore, the most critical parts of CILF are: (1) feature embedding network; (2) novel class detection operator; and (3) model update mechanism.

• •

  Feature Embedding Network: With the initial training data, i.e., the blue and orange dots as shown in figure 3, the decoupled neural network model is trained using the labeled initial data with the prototype based loss, which concerns the intr-class/inter-class structure and can be easily transformed for NCD;

• •

  Novel Class Detection Operator: At time $t$, we receive a set of unlabeled data from the streaming data, i.e., gray dots as shown in figure 3, which includes known (blue and orange dots) and unknown (green dots) classes. The observed instances set $D^{t}$ are transformed through learned network, and achieve feature representations. Then we employ the pre-trained $f^{t-1}$ for curriculum clustering operating, which can detect multiple unknown classes from easy to difficult in self-taught form;

• •

  Model Update Mechanism: After NCD, true labels of instances from novel classes are queried (partially or fully), then IMU is performed on $f^{t-1}$ with the newly labeled data, while regularizing the performance of stored data from known classes to mitigate forgetting. The updated model is then used to further classify incoming instances along the stream.

This process is repeated until the end of streaming data. Figure 3 illustrates the overall streaming data classification performed by CILF framework. And Table I provides the definition of symbols used in this paper.

Given the initial training data $D^{0}$, our primary objective is to build an effective model $f^{0}$ for subsequent classification. Recent researches have demonstrated the effectiveness of deep model on feature embedding and subsequent tasks, thereby we employ the deep models for building $f^{0}$, for example, convolution neural networks for images. Importantly, the built deep model needs to consider two aspects: (1) Distance measure. The model needs to emphasize the exploitation of feature embeddings considering intra-class compactness and inter-class separability, thus leave larger space for novel class detection; (2) Model scalability. The model needs to effectively learn novel class knowledge and incrementally update model with the emergence of novel class data. However, traditional deep models using cross entropy cannot consider the distance measure effectively, and are difficult to conduct the model update (the prediction layer is coupled to the fully connected layer, and is difficult to expand). Consequently, we develop a decoupled deep embedding network with prototype based loss to improve the inter-class and intra-class structure.

Particularly, for a given input ${\bf x}_{i}^{0}$, the output feature representations are denoted as $f^{0}({\bf x}_{i}^{0},\theta)$, $\theta$ is the correspond network parameters, and we utilize notation $f^{0}({\bf x}_{i}^{0})$ for clarity. Inspired from the topic of metric learning [31], the loss can be defined as:

where $L_{intra}$ aims to pull data towards their neighbor from same class, and $L_{inter}$ is to push data away from different classes. $\lambda$ is the balance parameter.

Traditional closed-set methods predict the known classes of training phase, in which the number of possible labels at testing is known and fixed. However, in class-incremental setting, instances belonging to unknown classes may appear with the streaming test data. Therefore, we need to distinguish the known and unknown classes. Specifically, we receive a set of unlabeled data $D^{t}$ at $t-$th time, and there may occur $K^{t}$ novel classes, where $K^{t}\geq 0$. However, most current detection methods either assume that only one novel class appears per time, i.e., $K^{t}=1$, or classify multiple novel classes as a super-class, which is impractical and difficult to operate considering efficiency. To solve this problem, we aim to fine-tune the deep clustering network $f^{t-1}$ of last time for multiple novel class detection. As shown in Figure 2, a key challenge is that adversarial instances of novel classes are mixing with known classes in complex scenario, leading the embedding confusion and greatly affecting the clustering effect, i.e., biased prototypes for known and unknown classes. To solve this problem, we employ a learnable curriculum clustering operator, which aims to conduct clustering from easy (distinguishable) to difficult (confused) instance via curriculum learning [36]. Consequently, we can acquire more reliable prototype and novel class detection result.

In detail, considering the model training in Algorithm 1 is entirely supervised, whereas $D^{t}$ is unsupervised, we aim to discover novel classes in $D^{t}$ by unsupervised clustering, which fine-tunes the $f^{t-1}$ trained on $t-1$ phase with easy instances first, and then cluster the mixed ones. We address this challenge by decomposing the learnable curriculum clustering into two closely related sub-tasks as curriculum learning. The first is weighting function to calculate the weight of each instances, and initialize the prototype with weighted k-means. The second is pacing function to determine the pace for which data are presented to fine-tune the model, thus conduct curriculum clustering.

Ideally, the initial model training and novel class detection processes can identify the known and unknown classes. However, considering streaming data with unceasing novel class, we need reliable training data of novel classes to create new prototypes and update the model parameters in incremental fashion. Thus, we need to collect novel class data for labeling, which can be used to re-train $f^{t-1}$. Similar to previous studies [40, 20], after curriculum clustering operator for detection, we can achieve potential novel class instances $D_{new}^{t}$ for querying their true labels. Note that we can query full or only partial data of novel class. However, there exist catastrophic forgetting of known classes if we only use the new data to update the model.

To solve this problem, we develop a mechanism to incorporate the stored memory and novel class information incrementally, which can mitigate the forgetting of discriminatory characteristics about known classes. In detail, we utilize the exemplary data $M^{t-1}$ for regularization in re-training:

The first term encourages the network to output the correct class indicator (classification loss) for all labeled examples, i.e., $D_{new}^{t}$ and $M^{t-1}$, and reproduces the scores calculated in the previous step (distillation loss) for stored in-class examples, i.e., $M^{t-1}$. $\mathbb{T}^{t}$ is constituted from $D_{new}^{t}$ and $M^{t-1}$. After re-training, we need to update the $M^{t-1}$ to store key points of novel classes, we randomly remove $\frac{|Y^{t}||M|}{|\hat{Y}^{t-1}||\hat{Y}^{t}|}$ instances for each known class, and sample $\frac{|M|}{|\hat{Y}^{t}|}$ instances for each novel class. The details are shown in Algorithm 3.

We utilize three commonly used visual datasets for class-incremental scenario following [17, 30, 13], including MNIST [41], CIFAR-10 [42], CIFAR-100 ¹¹1http://www.cs.toronto.edu/kriz/cifar.html. In detail, MNIST dataset contains labeled handwritten digits images from 10 categories, where each class contains between 6313 and 7877 monochrome images; CIFAR-10 dataset has a total of 60000 color images of 32x32 pixels from 10 natural image classes; CIFAR-100 dataset is enlarged CIFAR-10, and we structure CIFAR-100 into 2 datasets: CIFAR-50 and CIFAR-100 according to [13].

Inspired from [43, 17, 30, 13, 44], we utilize the given testing data from the raw datasets as a holdout set to evaluate forgetting, and use the given training data to generate the streaming data. Specifically, we rearrange instances in each dataset to emulate a streaming form with novel classes considering two forms: (1) single novel class each time window; (2) multiple novel classes each time window. For single novel class case, we randomly choose $C$ initial classes, and only 1 novel class may start for each time window. In order to be more in line with real-world applications, each known class may disappear randomly at the end of current time window. Specifically, we set $C=5$ for MNIST and CIFAR-10, $C=30$ for CIFAR-50, $C=50$ for CIFAR-100. Figure 4 (a) presents a simulated example of the CIFAR-10, i.e., we randomly choose 5 initial classes, and there are 5 time windows with 1 novel class starting for each time window. For multiple novel class case, we randomly choose $C$ initial classes, and $K^{t}$ novel classes (i.e., $K^{t}\in[2,K]$ novel classes) may randomly start for each time window. Similar to single class setting, each class may disappear randomly. Specifically, we set $C=3$ for MNIST and CIFAR-10, $C=30$ for CIFAR-50, $C=50$ for CIFAR-100. Figure 4 (b) presents a simulated example of the CIFAR-10, i.e., we choose 3 initial classes and there are 3 time windows, 2 novel classes start for the first time window, 3 novel classes for the second time window, 2 novel classes for the last window.

To validate the effectiveness of proposed CILF, we compared with existing state-of-the-art novel class detection approaches and incremental learning methods.

First, we compared CILF with existing NCD and incremental NCD methods. Including traditional anomaly detection and linear methods: Iforest [45], One-Class SVM (One-SVM) [ScholkopfPSSW01], LACU-SVM (LACU) [19], SENC-MAS (SENC) [20]; deep methods: ODIN-CNN (ODIN) [22], CFO [13], CPE [17] and DTC [24]. Abbreviations in parentheses. DTC is clustering based methods for multiple unknown classes detection. Note that Iforest, One-SVM, LACU, ODIN, CFO, and DTC are NCD methods, SENC and CPE are incremental NCD methods. All NCD baselines except Iforest can be updated incrementally using newly labeled unknown class data and memory data.

• •

  Iforest: an ensemble tree method to detect outliers;

• •

  One-Class SVM (One-SVM): a baseline for out-of-class detection and classification;

• •

  LACU-SVM (LACU): a SVM-based method that incorporates the unlabeled data from open set for unknown class detection;

• •

  SENC-MAS (SENC): a matrix sketching method that approximates original information with a dynamic low-dimensional structure;

• •

  ODIN-CNN (ODIN): a CNN-based method that distinguishes in-distribution and out-of-distribution over softmax score;

• •

  CFO: a generative method that adopts an encoder-decoder GAN to generate synthetic unknown instances;

• •

  CPE: a CNN-based ensemble method, which adaptively updates the prototype for detection;

• •

  DTC: an extended deep transfer clustering method for novel class detection.

Specifically, 1) Iforest, ODIN and CFO can only perform binary classifications, i.e., whether the instance is an unknown class. Thus we further conduct unsupervised clustering on both know and unknown class data for subdividing; 2) all baselines are one-class methods except DTC, i.e., they perform NCD in two steps: first detect the super-class of unknown classes, then perform unsupervised clustering; 3) all of baselines are NCD methods except LACU, SENC and CPE, but they can be applied in incremental NCD by combing memory data to update following [17].

To validate the incremental model update, we also compare with state-of-the-art forgetting methods: DNN-Base, DNN-L2, DNN-EWC [28], IMM [29], DEN [46], each time window is regarded as a task in these methods. In detail, the compared methods are:

• •

  DNN-Base: Base DNN with $L_{2}$-regularizations;

• •

  DNN-L2: Base DNN, where at each stage t, $\Theta_{t}$ is initialized as $\Theta_{t-1}$ and continuously trained with $L_{2}$-regularization between $\Theta_{t}$ and $\Theta_{t-1}$;

• •

  DNN-EWC: Deep network trained with elastic weight consolidation for regularization, which remembers old stages by selectively slowing down learning on the weights important for those stages;

• •

  IMM: An incremental moment matching method with two extensions: Mean-IMM and Mode-IMM, which incrementally matches the posterior distribution of the neural network trained on the previous stages;

• •

  DEN: A deep network architecture for incremental learning, which can dynamically decide its network structure with a sequence of stages and learn the overlapping knowledge sharing structure among stages.

Considering that CILF can distinguish the known and unknown classes, while mitigating the forgetting. Thus we measure the proposed method from two aspects: (1) NCD performance; (2) Forgetting performance.

Following [30], we adopt the commonly used evaluation metrics for novel class detection: 1) Normalized Accuracy (NA), which weights the accuracy for known and novel classes [47]; 2) Macro-F-measure and Micro-F-measure; and 3) AUROC, which considers the NCD task as a combination of novelty detection and multi-class recognition [13]. Moreover, to validate the catastrophic forgetting, we calculate the performance about forgetting profile of different learning algorithms as [44], i.e., let $acc_{m,n}$ be the accuracy evaluated on the hold-out sets, i.e. the novel classes emerge on $n-$th time window ($n\leq m$), after training the network incrementally from stage 1 to $m$, the average accuracy at time $m$ is defined as: $A_{m}=\frac{1}{m}\sum_{n=1}^{m}acc_{m,n}$  [44]. higher $A_{m}$ represents for better classifier. $Forgetting=\frac{A^{*}-mean(A)}{A^{*}}$, $A^{*}$ is the optimal accuracy with the entire data. We repeat all experiments with 5 times, and record the mean and std.

We develop CILF based on convolutional network structure as ResNet18 [48]. Note that we use an identical set of hyperparameters ($\lambda_{1}=1$, $\lambda_{2}=1$, $\alpha=0.3$, $\beta=0.8$, $\upsilon=0.2$, $\delta=3$, $\phi=10$). In all of our models and experiments, we adopt standard SGD with Nesterov momentum [49], where the momentum is 0.9. We train the initial model $f$ as following: the number of epochs is 20, the batch size is 128, the learning rate is 0.01, and weight decay is 0.001. We implement all baselines and perform all experiments based on code released by corresponding authors. For CNN based methods, we use the same network architecture and parameters during training, such as optimizer, learning rate schedule, and data pre-processing. Our method is implemented on a RTX 2080TI GPU with Pytorch 0.4.06 ²²2https://pytorch.org/.

Table II compares the detection performance of CILF with all baseline methods on each streaming data with single novel class. We observe that: (1) CNN-based methods are better than traditional detection approaches, i.e., One-SVM, LACU-SVM, SENC-MAS. This indicates that neural network provides superior feature embeddings for prediction and detection over high dimensional streaming data; (2) CILF consistently outperforms all compared CNN-based methods in all the criteria. For example, in CIFAR-10, CILF provides at least 2$\%$ improvements than other methods. This indicates the effectiveness of prototype based loss for feature embedding and curriculum clustering operator for detection; and (3) The detection performance for large-scale data sets still needs to be improved, and the results of all methods are low.

Figure 5 shows feature embedding results within each time window using T-SNE [50], in which each class randomly samples 800 instances. Note that we turn to utilize the more complex dataset CIFAR-10 as an example, rather than simpler MNIST dataset in previous methods. Clearly, the optimal discriminative method (CPE) and generative method (DEC) are greatly interfered by the embedding confusion. While the output of CILF has more distinct groups from different classes compared to other methods, which is attributed to the prototype based loss for model training. Moreover, instances from novel classes are well separated from other known clusters, which is benefit for novel class detection. The compactness of new class indicates the effectiveness of curriculum clustering operator, in which reliable prototypes are developed and the the model is fine-tuned from easy to difficult.

Table III compared the forgetting performance of CILF with all baseline methods, which defines the forgetting of emerge class on a particular window, i.e., the difference between maximum knowledge gained about that window throughout learning process and we currently have about it, the lower difference the better. The results show that CILF has the least forgetting, which validates that the memory distillation and prototype regularization can mitigate the forgetting of known class data. Moreover, Figure 6 gives more direct results. Due to page limitation, we only report the result of CIFAR-10. The results indicate that at different window, the performance of known classes falls slower, which shows that CILF can mitigate forgetting efficiently.

Table IV compares the detection performance of CILF with all baseline methods considering multiple novel classes. We observe that: (1) multiple novel class detection method, i.e., DEC, has not achieved an advantage than single novel class detection methods with subsequent clustering operator. This indicates that direct clustering method may be influenced by the embedding confusion; and (2) CILF consistently outperforms all compared CNN-based methods in all the criteria except AUROC on CIFAR-50. This further indicates the effectiveness of curriculum clustering operator for detection.

Figure 7 shows feature embedding results within each time window using T-SNE, in which each class randomly samples 800 instances. Similarly, the output of CILF has more distinct groups from different classes compared to other methods, which indicates that CILF can solve the embedding confusion effectively. Table V and Figure 8 compared the forgetting performance of CILF with baseline methods. Identically, the results show that CILF has the least forgetting, and performance of known classes fall slower, which shows that CILF can mitigate forgetting under multiple novel classes scenario.

Figure 9 shows the influence of querying number about potential novel class instances, we only give the results of CIFAR-10 considering page limitation. Here, we randomly query a subset, i.e., a percent of potential instances from the current window. From the figure, it can be observed that the prediction performance improves with the increase of labeled data, which verifies the importance of ground-truths for model update.

The main parameters in novel class detection and model update are the $\lambda_{1}$ and $\lambda_{2}$ in Eq. 10. We vary these parameters in $\{0.01,0.1,1,10,100\}$ to study its sensitivity to classification performance and record the AUROC results in figure 10. Both the single and multiple cases indicate that the performances are higher when setting $\lambda_{1}$ with a larger value, i.e., larger than 1.

Consider our method focuses on multiple novel class detection, thus we analyze execution time for detecting and updating model with multiple novel class case. In detail, we select the five deep methods, i.e. ODIN-CNN, CFO, CPR, DTC and CILF, and record the results of multiple novel class case in Figure 11. CILF achieves the fastest results, this is because other methods require additional clustering operations, and embedding confusion will slow down the clustering convergence, which indicates the curriculum clustering can accelerate detection.