Open Category Classification by Adversarial Sample Generation

1 Introduction

As machine learning techniques are adopted in increasing applications, it is appealing that they can be applied in environments that are open and non-stationary, where unseen situations can emerge unexpectedly. For classification, a typical learning task, classical methods implicitly assume that the data is i.i.d. even for the future test ones. This assumption no longer holds in open environments, which drastically weaken the robustness of classical classification methods.

In this work, we consider the open-category classification (OCC) problem, where there are novel classes that none of their instances were observed during the training phase, but in the test phase their instances could be encountered. Classical approaches can only predict instances from unseen classes as one of the seen classes. An open-environment aware classifier, on the contrary, should be able to tell at first if an instance belongs to a seen class.

Different directions have been explored related to the OCC problem. In class incremental-learning [Fink et al., 2006; Muhlbaier et al., 2009; Kuzborskij et al., 2013], new classes are assumed to appear incremental. However, these studies mainly focused on how to enable the system to incorporate later coming training instances from new classes, but did not address the problem of recognizing unseen classes. In learning with a rejection option [Chow, 1970], the classifier rejects to recognize an instance if its confidence is low, which, however, does not take open-environment into consideration. Note that an instance close to the seen class boundary can have a low confidence but belongs to a seen class, while an unseen class instance can have a high confidence if it is far from the seen class boundary. Outlier detection techniques [Hodge and Austin, 2004] could be employed if we treat unseen class instances as outliers. However, samples from seen class could also contains outliers, meanwhile, a cluster of unseen class instances may not be treated as outliers. Zero-shot learning [Palatucci et al., 2009] is close to the OCC problem, but they commonly assume that a high-level attribute set is available for all classes including the unseen one, which provides useful information for recognizing unseen class instances. In our problem, however, we consider learning in an unfamiliar open environment and thus do not assume the availability of such high-level attributes.

∗This research was supported by the NSFC (61375061, 61333014), Jiangsu SF (BK20160066), and Foundation for the Author of National Excellent Doctoral Dissertation of China (201451).

†Part of the work was done when Z. Guo was visiting Nanjing University as an undergraduate student.

Only a few previous studies addressed the OCC problem. For examples, in [Scheirer et al., 2013] the open-set cost is considered, but it is hard to measure that cost without seeing open-set data; in [Da et al., 2014], a set of unlabeled data of all classes is employed, but sufficient unlabeled data from all potential classes may not always available. We are thus more interested in solving the problem without extra information.

In this paper, we propose the adversarial sample generation (ASG) framework for the OCC problem. Inspired by the adversarial learning [Goodfellow et al., 2014], ASG generates negative instances of seen classes by finding data points that are close to the training instances, given that they can be separated from the seen data by a discriminator. When the training data is small, ASG also generates positive instances that cannot be discriminated from the seen class instances, in order to enlarge the dataset. Using the supervision of the generated negative and positive samples of seen classes, it is then straightforward to train an open-category classifier to tell seen from unseen. We conduct experiments on several domains with open categories but no extra training information. The results show that the ASG achieves significant better performance than the compared methods.

The rest of this paper is organized in four sections that presents the background, the proposed method, the experiment results, and the conclusion, respectively.

2 Background

2.1 Related Problems

This paper studies the open-category classification problem, where no information about the unseen classes, neither instances nor attributes, is available. Some studies are related to this problem.

The incremental learning requires a proper adaptation of traditional machine learning approaches to deal with the dynamic and open environment, in addition, class-incremental learning(C-IL) [Zhou and Chen, 2002] is an important branch of it, which mainly concerned with the addition of new classes. In [Fink et al., 2006; Kuzborskij et al., 2013], each new class has a binary classifier which distinguishes between existing categories and new categories, and the new category in the classifier shares the hypothesis with the existing category to train. However, the method still need a few instances of new categories, when no instances of new categories are available in the training phase, these methods can not be applied. To address this limitation, a new method is introduced in [Da et al., 2014], which processes new categories by exploring unlabeled instances, this requires reliable unlabeled data, but the data availability and quality is difficult to guarantee in practice.

The open set recognition problem is mainly concerned by the community of pattern recognition, and has been applied to face recognition and speech recognition, etc. In [Phillips et al., 2011], the main concern is the operation of the threshold, only instances where the confidence is above the threshold are classified as seen classes. In [Scheirer et al., 2013; Bendale and Boult, 2015], both the new decision boundary and the risk over open space are considered to limit the regions for seen categories.

The outlier detection problem [Hodge and Austin, 2004] requires the identification of anomaly instances from a given data set. The outlier detection methods can be applied in open-category problems as long as the abnormal instances is predicted as novel classes. However, the difference is that outlier detection is only concerned with the discovery of abnormal instances, which is limited to specific applications. Besides, it does not take into account the classification error of existing categories

The class discovery problem tries to identify the instances of rare categories which are not known in advance, but are known to exist in the training data [Pelleg and Moore, 2005; Hospedales et al., 2013]. The open-category problem is different from class discovery problem, because the unseen class is not necessarily a rare class. On the other hand, it is possible to find examples of a rare class in the training data, while the instance of novel classes only appear in the test data.

The zero-shot problem tries to identify the unseen classes with the assumption that some high-level attributes of all classes are known as a prior. For example, in [Xian et al., 2016], a latent embedding model was presented which learns a compatibility function in the high-level attributes space considered between image and class embeddings. In this work, we do not assume the availability of such information.

2.2 Adversarial Learning

The adversarial learning employs a generative model and a discriminative model, where the generative model learns to generate instances that can fool the discriminative model as a non-generated instance, which is also called Turing Learning in [Li et al., 2016]. Besides, the Generative adversarial nets (GAN) combines the two models as a whole neural network for end-to-end training, resulting in a model that is consistent with the original data distribution. Further improvements include studies on the stability of GAN. For example, in [Nowozin et al., 2016], the F-divergence is introduced from the perspective of distance measurement, and GAN has been shown to be a special case of F-divergence when it comes to a particular metric.

In our work, we will employ the adversarial learning principle that a generative model fights to generate instances judged by a discriminator. Different with the studies on GAN, our framework can apply to various learning models besides neural networks. Moreover, to solve the open-category classification problem, we do not only need to generate seen class data, but more importantly need to generate unseen class data.

2.3 Derivative-free Optimization

Previously learning approaches commonly employed gradient-based optimization methods. However, the optimization problems may not always simple enough to fit the gradient-based methods. Often, a complex optimization has to be relaxed to a convex problem, sacrificing the faithfulness to the original problem.

Ancient derivative-free optimization methods include representatives such as genetic algorithms [Goldberg, 1989], which are mostly heuristic methods. Recently, the derivativefree optimization methods have made significant progress in both theoretical foundation and practical usage, including Bayesian optimization methods [Brochu et al., 2010], optimistic optimization methods [Munos, 2014], and modelbased optimization [Yu et al., 2016]. A derivative-free optimization method considers an optimization formalized as argmaxx∈X f(x), where X is domain. The method, instead of calculating gradients of f, samples solutions x and learns from their feedbacks f(x) for finding better solutions. Therefore, derivative-free optimization methods can be more suitable for problem with bad mathematical properties, including non-convexity, non-differentiability, and having many local optima. We thus employ the state-of-the-art derivative-free methods in our approach.

3 ProposedMethod

The open-category classification (OCC) problem can be described as follows. Given a training dataset D = {(xi, yi)}Li=1 , where xi ∈ Rd is a training instance and yi ∈ Y = {1, 2, ...,K} is the corresponding category label. In the test phase, we need to predict the categories of an open dataset Do = {(xi, yi)}∞i=1 , where yi ∈ Yo = {1, 2, ...,K,K +

1, ..., M} with M > K. Since there are classes which are not observed in the training phase, the goal of OCC is to learn a model f(x) : X → Y ′ = {1, 2, ...,K, novel}, where the option novel indicates that the category was unseen in the training phase, so as to minimize the expected risk as follows

where H is the hypnosis space and err is defined as follows

The I(expression) is an indicator function, it equals 1 when the expression holds and 0 otherwise.

The OCC problem is difficult to solve because no information about the novel class is available. Our overall idea is that, if we can generate the instances of the class novel and put them into the training set (denoted the augmented training set as ˜D), then the problem will be easily solved by standard supervised learning

The label of instance x can be predicted as argmaxk=1,...,K,novel fk(x). The problem is then how to generate data of the novel class.

The idea of adversarial learning [Goodfellow et al., 2014] is employed for data generation. In the adversarial learning, a generative model is trained to generate samples that are thought to be appropriate according to a discriminator. For example, to generate data consisting with the training data, the objective is that the discriminator cannot distinguish the generated data from the training data. Using this idea, we directly generate the data of unseen class for the OCC problem.

Generate Unseen Class Instances

To generate an instance of the unseen classes, ASG searches in the instance space, such that the instance should not be recognized as the seen class by the discriminator, which is a classifier trained to separate generated samples and seen class instances. However, there are too many such instances. For the purpose of distinguishing seen from unseen, we only need the samples that are around the boundary between seen and unseen classes. Therefore, ASG tries to find an instance that is close to the seen class instances, but is recognized as unseen class by the discriminator.

ASG considers each class separately, and for each class, it generates samples one by one. Let PD(x;D,D-) denote the probability of x to be positive by the discriminator, trained with positive data D and negative data D-. For class k, denote the current generated samples as Dk , which is empty initially. The objective that a generated sample does not belong to the seen class is

Intuitively, we evaluate a generated sample by adding it to the negative data set and train the model to see if the generated sample is not classified as positive (seen class).

Eq.(4) alone cannot generate all the boundary samples of the seen class, but only data samples that do not belong to the

Algorithm 1 Generation of negative instances of seen classes

Input:

• D: Training instances{(xi, yi)}Li=1
• T : Number of generated instances per class
• L: Learning algorithm for the discriminant model

Opt: A derivative-free optimization method

Output:

D-: Negative samples of all class 1, 2, ..K

• 1: for each k ∈ {1, ...,K} do
• 2: Dk = ∅
• 3: for t = 1, 2, ..., T do
• 4: x- = solve Eq.(7) by Opt with discriminator L
• 5: Update Dk =Dk ∪ {x-}
• 6: end for
• 7: end for
• 8: return D- = {D1 ,D2 , . . . ,D-K }

seen class. To generate boundary samples, we further require that the generated samples are close to the seen class data. Therefore, it is natural to consider that the distance between the generated sample and the original data set Dk should be small in a measure, which is enforced by the penalty term as

where the radius parameter C1 is a positive constant, and dist(x, x′ ) is a distance measure that can be Euclidean distance or other distance measures.

Furthermore, since ASG generates samples one by one, Eq.(4) and Eq.(5) cannot prevent it from generating many identical samples. However, we want the generated samples to be scattered around the boundary. Therefore, we force the generated samples to be different, i.e., a newly generated sample should be far away from the previously generated samples, which is expressed as

Here the radius parameter C2 is a positive constant.

Combining the loss and the penalty terms, the overall objective function is

where λ1 and λ2 are hyper-parameters of the penalty terms. Note that our penalty terms aims only at are pushing samples out of the radius distance, the hyper-parameters will not have a great impact on the learning result.

Note that Eq.(7) is non-convex, particularly when models other than neural networks are considered. It is hard to rely on the gradient-based method. Thus, we employ the derivativefree method to solve the optimization. Since most derivativefree methods are generally applicable, we denote such an algorithm as Opt in Algorithm 1. The concrete algorithm will be disclosed in the experiment section.

Algorithm 1 shows the overall procedure of generating negative instances. The algorithm takes input of labeled training dataset D and parameter T to indicate the number of instances to be generated per class. For each class k ∈ 1, 2, ...,K, it generates a set of instances, Dk , in turn, and the instances are obtained by optimizing Eq.(7).

Generate Seen Class Instances

On the other hand, if the class k is a rare class that has only a small number of samples, the trained classification model may be inaccurate. Our sample generation method can also be used to generate positive/seen class data, in order to improve the prediction accuracy. We only need to change the optimization function in step 6 of Algorithm 1 to complete this goal.

For the goal of generating a seen class instance, the loss is

where D+ k is the previously generated positive data set. Again, we want to generate scattered samples, thus we force the generated instance to be distant to the previously generated ones, by the penalty:

where the dist is a distance measure function, and C3 is a positive constant. Then the overall objective is:

arg maxx PD(x; Dk , D+ k ∪ {x}) - ηP3(x,D+ k ) (10) where η is the coefficient of regular entry P3. Let the Eq.(10) replace the Eq.(7) in the step 6 of Algorithm 1, the D+ k set can be obtained for each class k.

Overall Procedure

After the data of unseen and seen classes are generated, it is straightforward to train a classifier for distinguishing between them. In ASG, we prefer to train such classifier for each class, i.e., train f ooc k fromDk ∪D+ k and Dk .

Another issue needs to be considered is the learning capacity of the discriminator L. Note that when the capacity is too high, every generated sample can be discriminated from the original data; while when the capacity is too low, the boundary of the seen classes cannot be well captured. Unlike unsupervised learning, in the OCC problem we have some data of the seen classes. Using this data, we can fine tune the hyper-parameter (e.g. the structure of a neural network) of the learning algorithm for a proper capacity.

Overall, given any learning algorithm L, the procedure of the ASG framework is as follows:

1. On the seen data D, fine tune the hyper-parameters of L;
2. Generate negative instances D- of the seen classes by Algorithm 1, as well as positive instances D+ if necessary;

(3) For each class k, train a classifier f ooc k from positive data Dk ∪ D+ k and negative data Dk by L;

In the prediction stage, for a test instance x, it is tested by each of f ooc k . If all f ooc k classify x as negative, then x is predicted as a novel class. Otherwise, x is predicted as the class k with f ooc k has the highest confident.

4 Experiments

4.1 ComparisonMethods

As discussed above, the hyper-parameters of the learning algorithm should be determined at the first step. In the experiment, we employ SVM with RBF kernel as the learning algorithm and for the discriminant model too. And the binary classifier trained after the generation is also set as RBF-SVM. In order to verify the validity of the ASG framework, we conducted experiments on several benchmark datasets, comparing with:

OC-SVM: One-Class SVM [Sch¨olkopf et al., 2001] is a state-of-the-art outlier detector [Ma and Perkins, 2003], which computes a binary function supposed to capture regions in the input space where the probability density lives.

MOC-SVM: The OC-SVM can hardly find local outliers since it seeks for a hyperplane to separate the data and the origin in essence. Therefore, for this comparison method, we train multiple one-class SVMs, one OC-SVM for each seen class in the training set, for outlier detection.

1-vs-Set: 1-vs-Set Machine [Scheirer et al., 2013] introduces extra decision boundaries for the seen classes in order to minimize the risk over open space.

OVR-SVM: One-vs-rest SVM is a powerful multi-class classification scheme [Rifkin and Klautau, 2004]. In the original OVR-SVM, an instance x is predicted as category y, where y = arg maxk=1,...,K fk(x) where fk is a binary SVM trained for class k. In order to adapt OVR-SVM for the prediction of open-category problem, we let the x be predicted as class y only when maxkf(x) > 0, otherwise x is considered to be the instance of novel class.

NNO: Nearest Non-Outlier(NNO) [Bendale and Boult, 2015] is a theoretical guaranteed method which deal with the open world recognition by introduce a measurable function in Nearest Class Mean method.

In experiments, we use the implementations of OC-SVM, MOC-SVM and OVR-SVM in the LIBSVM software [Chang and Lin, 2011], and the implementation of 1-vs-Set Machine from the code released by the authors. And we implement the NNO by ourselves due to the miss of the code. The coefficient C in SVM is determined by cross validation on the training dataset using the original OVR-SVM. The width of Gaussian kernel γ is fixed to 1/d, where d is the size of the feature. For the ASG algorithm, the distance measure dist is set to be the Euclidean distance. When generating negative samples of class k, the parameter C1,C2 is set as minx1,x2∈Dk;x1̸=x2 dist(x1, x2), λ1 and λ2 are both set to 0.1, and T = 200. When generating positive samples for class k, the parameter C3 is also set to minx1,x2∈Dk;x1̸=x2 dist(x1, x2), η is set to 0.3, and also T = 200. For the derivative-free optimization method, we employ the recently developed RACOS algorithm 1 [Yu et al., 2016] with default parameters.

4.2 Results

Three Moons: We first illustrate the behaviors of ASG using a 2-dimensional synthetic data as in Figure 1. The dataset consists of three classes, but only two of them are seen in the training stage, as in Figure 1 (a). With the generated data, the boundary of the seen classes can be well characterized, as in Figure 1 (b). The decision boundaries in Figure 1 (c) show that ASG can correctly exclude the unseen moon as seen data, while the classical SVM will classify the unseen moon as blue.

1 using the implementation in https://github.com/eyounx/ZOOpt

Handwritten Digit Image Classification: We conducted the second experiment on the MNIST handwritten digit dataset. First, seen categories were randomly selected from 10 total categories and the test data contains all 10 categories. The number of training data, generated data and test data are 100, 300 and 100 for each class. We have 10 random selections for the seen categories and repeat 10 times for each selection, both mean and standard deviation are recorded. Figure 2 shows the results on 3 and 5 seen classes in training. It can be observed that ASG-SVM achieves the best performance on both configurations, while the OVR-SVM is the runner up. Besides, the 1-vs-set machine shows to outperform the OC-SVM and MOC-SVM, and the outlier detection methods, OC-SVM and MOC-SVM, produce the worst performance. Besides, the NNO seems not perform well in this dataset.

To break down the performance to seen and unseen data separately, we set the class 2, 3, 5 as seen categories, and training data size for each category is set to 100 and 1000, respectively. The experiments are repeated for 10 times, and both mean and standard variance of the measure are reported. The results of F1, precision and recall for both seen classes and unseen classes are shown in Table 1. For seen classes, the ASG-SVM gets the best performance on F1 and precision when the instance number for each category is set to 100 and 1000, while the recall of OVR-SVM and 1-vs-set is the highest when the number of instance is set to 100 and 1000. For unseen classes, the ASG-SVM obtains the highest performance on F1 and recall, while the precision of OVR-SVM and 1-vs-set is the best when the instance number of each class is 100 and 1000.

Table 2 shows the improvement ratio of ASG-SVM over the comparing methods in 4 configurations of the number of seen classes and training set size. The cases in the first column represent different situations, for example, 3-100 represent there are 3 seen classes in the training data and 100 instances for each class. It can be observed that, when the training data has a smaller size, ASG-SVM has larger improvements. This mainly due to that ASG also generates samples of seen classes to improve the prediction accuracy.

Document Classification: In the third experiment, we conduct experiments on the 20 Newsgroups dataset, which is a popular text dataset consists of documents from 20 different topics. Note that this data set has some topics that are highly similar, such as comp.sys.ibm.pc.hardware and comp.sys.mac.hardware. When one belongs to the seen classes and the other is unseen, the classification will be quite difficult. We set the number of seen classes as 5. The number of training data, generated positive data, generated negative data and test data are set to 3000, 2000, 2000 and 3000, respectively. We randomly sample seen classes and the training data to form 20 data sets, and for each data sets, the experiment is repeat for 10 times.

Figure 3 shows the Macro-F1 performance with the increase of test classes. It can be observed that the curves in general decreases as expected. Among these methods, ASG-SVM consistently achieves the best performance, and the OVR-SVM is the runner-up. The outlier detection methods, OC-SVM and MOC-SVM, fail in this data, which further confirms that the instance of unseen classes should not be simply treated as outliers in the OCC problem. The win/tie/loss table on all algorithm pairs is in the appendix due to the space limit, which will show that ASG framework is significantly better than the other methods.

Small Datasets: We also conducted experiments on five small datasets, where the size for each seen class is no more than 100 in the training datasets, which makes the classification tasks become more challenging.

As the result shown in Table 3, ASG-SVM obtains the best performance in four datasets compared to the other five methods; NNO has the best performance in the flag dataset, but can be worse than some of the comparing methods. In addition to ASG-SVM, NNO and OVR-SVM are runner-ups that have better performance in several cases, but have lower Macro-F1 in the glass dataset than MOC-SVM, where the number of each class is just 15 in the training set. Sort the algorithms with their average ranks on all data sets, the best is ASG-SVM (average rank 1.2), and the remaining are NNO (2.6), OVR-SVM (3.0), MOC-SVM (3.6), 1-vs-Set (4.6), and OC-SVM (6).

5 Conclusion

Open-category classification problem often occurs in practical problems, where a system needs to predict the data in an open environment. In this paper, we propose the ASG framework to address the problem by adversarial data generation. In experiments, we demonstrate that ASG can successfully generate boundary data around the seen classes, which makes the recognition of unseen classes can be easily done by supervised learning. On several datasets, ASG shows to be more effective than several state-of-the-art methods. In the future, besides the current SVM model, we would like to apply ASG with state-of-the-art multi-class learning method, and develop a theoretical grounded method for the OCC problem.