extfieldsofstudy:
Computer Science
Medicine

text:
Convolutional Neural Network-Based Discriminator for Outlier Detection

Noise in training data increases the tendency of many machine learning methods to overfit the training data, which undermines the performance. Outliers occur in big data as a result of various factors, including human errors. In this work, we present a novel discriminator model for the identification of outliers in the training data. We propose a systematic approach for creating training datasets to train the discriminator based on a small number of genuine instances (trusted data). The noise discriminator is a convolutional neural network (CNN). We evaluate the discriminator's performance using several benchmark datasets and with different noise ratios. We inserted random noise in each dataset and trained discriminators to clean them. Different discriminators were trained using different numbers of genuine instances with and without data augmentation. We compare the performance of the proposed noise-discriminator method with seven other methods proposed in the literature using several benchmark datasets. Our empirical results indicate that the proposed method is very competitive to the other methods. It actually outperforms them for pair noise.

Introduction
While the effectiveness of supervised machine learning algorithms relies on the existence of large and high-quality labeled datasets, it is a time-consuming and challenging matter to create clean datasets that are free from noise (i.e., incorrectly labeled instances) [1,2]. Outliers (noise and outlier are used interchangeably in this paper to refer to the mislabeled instances) occur in real-world datasets for many reasons that are related to data collection, human errors, and the widespread use of suboptimal automated processes to compile large datasets. e aim of this research is to propose a machine learning method for identifying and eliminating noise from datasets. We propose a method to train a noise discriminator (ND). e ND is trained using automatically generated datasets based on a small number of genuine instances. e NDs that we propose are CNN classifiers.
Deep learning (DL) models, including CNN, have been applied with great success in diverse areas with a performance that often exceeds the capabilities of human beings [3,4]. DL models are particularly valuable in domains where large amounts of training data are available. However, when a training dataset's size increases, so does the likelihood that it contains outliers, leading ML models to overfit the training data, thereby undermining the performance [5]. Given the negative effects of outliers on DL methods, a range of solutions has been identified to mitigate these effects [6].
is research focuses on developing a generalized CNNbased discriminator for outlier identification. e proposed method trains the discriminator on a specially built dataset, generated from a small number of genuine instances. e discriminator can be used as a preprocessing step to identify and eliminate outliers prior to their use to train classifiers.
Our proposed method was inspired by the generative adversarial network (GAN) model [7] that contains a discriminator model that is trained to separate genuine images from fake images produced by a generator. Similarly, we build a noise discriminator that can identify outliers based on preprepared genuine data (noise free). However, unlike GAN, we do not have a generator model; rather, we systematically generate the training data. e proposed discriminator is trained using a dataset derived from the trusted data. e training dataset contains all the possible mislabeled cases. In other words, the discriminator will be trained using every genuine instance and all of its potential mislabeling. e remainder of this paper is organized as follows. Section 2 presents an overview of the related works that deal with outliers. In Section 3, the proposed discriminator is presented. Section 4 discusses the empirical results used for evaluating the performance of the proposed discriminator. Finally, Section 5 is the conclusion.

Related Work
Various studies have been conducted to develop methods for mitigating the effect of mislabeled instances. Some of those methods are based on using an improved loss function that is robust against mislabeling, such as [8,9]. Other methods, such as [10,11], use instance reduction techniques to reduce the size of the training set and eliminate noise.
Another approach for handling noise is based on using the trusted data. Zeng and Martinez [12] proposed a neural network-based noise filter for a pretraining process to reduce the effect of noise in the nearest neighbor classifiers. eir mechanism was based on using a class probability vector that is updated consistently during training for each instance. e class probability vector is updated using a learning algorithm that is based on the disparity between its value and the neural network prediction. A potential limitation of this approach is that it requires training the neural network using a sufficient number of correct instances that may not always be available.
Sukhbaatar and Fergus [13] developed a framework in the context of neural networks that includes an extra noise layer on top of the network to handle the noisy labels. ey proposed bottom-up and top-down noise models. In the bottom-up model, the label probability output is varied according to the noisy labels. In contrast, the top-down model is used for modifying the noisy labels before using them for training. ey introduced a technique for estimating the noise distribution using clean and noisy data.
is technique involves building two confusion matrices for both clean and noisy data; the difference between these two confusion matrices represents the noise distribution. ey also found that reducing the weight of the noisy data is very effective. e concept of distillation, Hinton et al. [14], involves training one model using the knowledge transferred from another model. is concept inspired Li et al. [15] to develop a framework that can learn from noisy labels. A model is trained using a small clean dataset, and the learned knowledge is transferred for training another model on large, noisy datasets. However, obtaining a sufficient number of clean data remains a challenge for this method. Hendrycks et al. [16] proposed Gold Loss Correction, a loss function for handling noise. e proposed method is based on the availability of trusted data that is used for estimating a matrix C of corruption probabilities the matrix is K × K, where K represents the number of classes in a dataset. e matrix C is then used to train a classifier that is expected to be able to predict correct labels. However, the minimum genuine data required were 5%, which may be too large in datasets such as MNIST [17], CIFAR-10 [18], and SVHN [19].
Various methods for handling noise have also been proposed in the context of CNN training [6,20]. A probabilistic graphical model was integrated by Xiao et al. [21] into a deep learning framework to schematize the relationships between the input, class labels, and noisy labels in a clothing dataset. ey utilized the expectationmaximization algorithm in the training process. JoCoR [22] is a method that utilizes two networks that are trained simultaneously. During every batch of training, each network feeds the other by supposedly clean instances during training, where clean instances are identified by having small-loss values. e two networks are implemented with one regularization term to reduce the diversity between the two networks. Another method called EBF [23,24] is used as a filtration technique during the training of neural network-based models. It detects and removes noisy instances based on the exponential moving average (EMA) of the loss values for instances. e assumption is that any EMA of an instance that exceeds a certain threshold represents noise. In turn, elimination occurs during the training procedure. e GAN model [7] contains two submodels, a generator, and a discriminator. e generator model is trained to produce fake images that are assumed to be similar to the original ones, while the discriminator is trained to be able to determine if an image is original or fake. During training, the generator and the discriminator are locked in a contest, each attempting to beat the other one until the generator can produce fake images that the discriminator cannot identify.
In this paper, we propose a discriminator trained on a dataset produced using a few genuine (trusted) data for identifying mislabeling instances.

Discriminator for Outlier Detection
Machine learning (ML) methods seek to find a good approximation of a target function that maps an input, x, into an output, y [5]. us, ML algorithms learn a function, f(x), that can predict an output y for any given input x.
is section presents a method for constructing classifiers that can identify outlier instances in a noisy dataset. Specifically, the proposed method involves building a discriminator model for outlier detection that can be used for data cleansing. e discriminator receives an input instance and a possible label, after which it seeks to determine whether the label is correct or not, as shown in Figure 1.

Generating the Training Data.
e noise discriminator is trained using a training dataset that is generated based on a small number of trusted (genuine) instances; we call them the seeds. We use the trusted instances to create a dataset that contains instances labeled with either 1 or 0. An instance has label 1 if it is a genuine instance (not noisy) and label 0 if it is a noisy instance. To create noisy instances, we populate the dataset with instances labeled with all classes other than their correct class. Genuine instances are inserted and replicated to ensure that the dataset is balanced. e discriminator is trained using the generated dataset D, where D is derived from a small set of data, D Trusted . For every genuine instance of the form 〈x, y〉, in the trusted dataset, D Trusted , we derive K instances and insert them in D, where K is the number of classes. For every class c and a genuine instance, 〈x, y〉, D is augmented with one instance of the form ≪x, y > , 1 > and K − 1 instances of the form ≪x, c > , 0 > , where c ≠ y. In D, if an instance has label 1, this indicates that it is a genuine instance with the correct class; however, if an instance has label 0, this indicates that it is a mislabeled instance (an instance with an incorrect class).
Considering the example of the digit recognition problem [25], for every seed (genuine) instance, D will contain ten instances: one instance of the form ≪x, y > , 1 > representing that y is the correct digit of x and nine instances of the form ≪x, c > , 0 > representing the fact that c is not the correct digit of x. ese nine instances cover all possible mislabeling of x. Table 1 illustrates the instances that will be added to D for a genuine instance (image) of digit two. is means that, for every seed instance, D will be augmented by one instance of class 1 and nine instances of class 0.
To ensure that the resulting dataset is balanced, each instance of class 1 in D is duplicated K − 2 times. is is a form of oversampling to balance the training set. Algorithm 1 provides a detailed account of the procedure for creating D. e size of D (i.e., number of instances) can be calculated as follows: where G represents the number of seed instances per class. In addition, data augmentation methods can be used to generate more training data and avoid overfitting. For instance, operations such as zooming, rotation, shearing, and shifting are commonly used methods in image recognition systems [26]. erefore, we apply the following data augmentation procedures: firstly, shifting the width and height by 0.2; secondly, rotating by 50 degrees; thirdly, zooming by 0.9 for width and 0.8 for height; and finally, shearing with the transformation intensity of 0.2. e size of D (i.e., number of instances) in case of using data augmentation methods can be obtained as follows: where AugFact is the number of times we perform data augmentation and DA denotes the number of augmented images produced from each original image (including the original ones).

A Convolutional Neural Network-Based Discriminator.
In this section, we discuss the architecture of the noise discriminator. It is a CNN-based architecture that contains some convolutional and pooling layers. e convolutional layers are an effective model for feature extraction [27]. In particular, CNN comprises multiple convolution layers where the output of each layer is fed as input for the next layer. Early layers map the basic features, while the deeper layers detect higher-level features such as edges, faces, and objects. Features are represented by a number of parameters, and pooling layers are used to reduce the number of parameters without affecting the feature representation. Figure 2 shows a general architecture of the proposed noise discriminator. e model architecture consists of a set of convolutional and pooling layers, which is changeable according to the nature of the training dataset, followed by four hidden layers (512, 128, 64, and 10) of the fully connected neural network. e set of convolutional and pooling layers are left unspecified because they are problemdependent.

Evaluating the Discriminator
To evaluate the proposed model's performance in identifying outliers, the MNIST, CIFAR-10 [18], and CIFAR-100 [18] datasets were used. A brief description of each dataset is provided in Table 2.
e experiments undertaken in this section were divided into four main parts: the first part examined the Table 1: A sample of the generated dataset for digit 2.

Input
Output(0 or 1) Computational Intelligence and Neuroscience discriminator's behavior in identifying outliers; the second part verified the effectiveness of the proposed method in terms of the achieved classification accuracy of classifiers trained using the cleaned datasets compared to other methods reported in the literature; the third part investigates the effect of the discriminator on training time; and the last part compares different methods in terms of their accuracy in identifying outliers. e discriminator outputs a value of 1 for genuine instances and a value of 0 for outliers, and to decrease the number of genuine instances that might be incorrectly classified as outliers, we used a threshold of 0.75, instead of 0.5. is reduces the number of false negatives; however, it may also increase the number of false positives as a side effect.

Evaluating the Ability of the Discriminator in Identifying
Outliers.
is section investigates the ability of the proposed discriminator to identify outliers in a noisy dataset. For each noisy dataset, three discriminators were trained on different datasets, D, generated using a various number of seeds (trusted instances). Each discriminator's performance was evaluated by verifying the extent to which it could distinguish between outliers and genuine instances in a noisy dataset. e outliers were created by flipping the classes of randomly selected instances. e discriminators for MNIST, CIFAR-10, and CIFAR-100 datasets were trained for 50 epochs; after that, they were used to clean datasets with different noise ratios: 10%, 50%, and 90%.

Evaluation on MNIST.
To implement the discriminator so as to identify the outliers added to the MNIST dataset, two convolution layers (32 and 64), in addition to a max-pooling layer, were used as shown in Figure 3.
ree discriminators were trained for MNIST, each of which was trained on a different dataset. e dataset of the first was generated using five seed instances per class with no data augmentation, whereas the datasets for the second and third were generated using two and five seed instances per class and with data augmentation. e augmentation methods we used are rotation, shifting, shearing, and zooming. e first dataset contained 900 instances. Table 3 summarizes the results. It reveals that the discriminator identified most outlier instances with a low false-negative rate. In addition, the false-positive rate decreases as the noise ratio increases which is expected because as the number of outliers increases, the likelihood that the discriminator is correct when it classifies an instance as an outlier also increases. is observation also justifies the inverse correlation identified between the overall recall values and the noise ratio. However, the false-negative rate was found to increase as we increase the noise ratio. Table 4 summarizes the results we obtained using the second discriminator, which is based on two seed instances and with data augmentation. e generated training set contained 36,000 instances. e results show that this discriminator outperformed the first one, which shows the usefulness of using the augmentation operations.
For the third discriminator (i.e., based on 5 seed instances and data augmentation), D contained 90,000 instances. is noise discriminator outperformed both the first if c ≠ y do: else: end for//every class (9) : end for//every instance (10) : Replicate every instance of the form ≪x, y > , 1 > (K − 2) times (11) : Output D ALGORITHM 1: Creating dataset (D) for training the proposed discriminator.   and second discriminators, as can be seen in Table 5. With a noise ratio of 90%, this discriminator identified 97.56% of the outliers with a 1.8% false-positive rate. A comparison of Tables 3-5 indicates that the applied data augmentation methods positively influenced discriminator performance. Although 90% is a high noise ratio, the first, second, and third discriminators identified almost all outliers with false-negative rates of 12.9%, 8.9%, and 8.77%, respectively. Furthermore, with 10% and 50% noise, the discriminators identified a reasonable number of outliers with a false-negative rate of less than 2%.
A noteworthy point for high noise ratios in MNST (i.e., 50% and 90%) is that the discriminator performance was more effective compared to low noise ratios (10%).
is result stands to reason because when the amount of noise in a training dataset is substantial, the likelihood of the false positive decreases.

Evaluation on CIFAR-10.
e noise discriminator we trained for this dataset contained a 20-layer ResNet where each convolutional layer is of 16 × 16 × 3. It was shown that ResNet models are very effective for feature extraction for this dataset [28].
We trained three noise discriminators for the CIFAR-10 dataset using a different number of seed instances with data augmentation.
e first discriminator was based on 100 seed instances per class with an augmentation factor of 5. us, according to equation (2), the total number of instances used to train the discriminator amounted to 450,000. For the second discriminator, 200 seed instances were used per class with an augmentation factor of 2. erefore, the total number of instances used to train the discriminator was 360,000. As for the third discriminator, 400 seed instances were used per class with an augmentation factor of 1. Hence, 360,000 instances were used to train the discriminator. e results of the first, second, and third discriminators are given in Tables 6-8, respectively. e results clearly indicate that there is a proportional relationship between the number of seed instances used and the performance as the performance in terms of the F1 measure improves as we increase the number of seed instances regardless of the noise ratio.

Evaluation on CIFAR-100.
Similarly, for this dataset, we also used a 20-layer ResNet model for feature extraction, where each convolutional layer is of 16 × 16 × 3.
We also trained three discriminators for CIFAR-100 using a different number of seeds for generating the dataset to train each discriminator; data augmentation was used in    all cases. e first discriminator was trained using a dataset generated based on 10 seed instances per class and with an augmentation factor of 1. erefore, the total number of instances used to train the discriminator was 792,000. e second discriminator was trained based on 30 seed instances per class with an augmentation factor of 1. Hence, the total number of instances used to train the discriminator was 1,188,000. As for the third discriminator, 50 seed instances were used per class to generate the dataset with an augmentation factor of 1. e only augmentation method used in this case was image rotation. e total number of instances used to train the discriminator amounted to 1,980,000. Of course, the large number of instances used to train these discriminators is due to the large number of classes in CIFAR-100. e results of the three discriminators are summarized in Tables 9-11, respectively. It is clear that the discriminator that was based on 50 seed instances outperformed its counterparts in outlier identification. With 50% noise, the 50-seed discriminator identified outlier instances with a false-negative rate of 4.87%. In general, the F1 measure improves as the number of seed instances and noise ratio increase.
Finally, it is worth noting that, for all the experimental evaluations undertaken in this section, the false-negative rate was reasonable, while the false-positive rate was comparatively high.
is is probably because we used a relatively high threshold value of 0.75, which made the discriminators very conservative in classifying instances as genuine and less so when it comes to classifying the instances as outliers. is accounts for the high rate of false positives observed in these experiments.

Classification Using the Cleaned Datasets.
In this section, we compare different methods for noise handling indirectly by training classifiers using the cleaned datasets obtained by each method for the original classification problem. We compare the performance of the proposed noise discriminator against the results of the methods reported in [29]. To conduct a valid performance comparison in terms of mitigating the effect of noise, the model's architecture used in [29] was adopted, along with the data corruption procedures.
For dataset corruption, two types of noise transition matrices were used: pair flipping [29] and symmetry flipping [30]. Pair flipping involves changing the classes of some randomly selected instances to another specified class, according to a transition matrix (Figure 4(a)). Each column in the matrix represents a class, and the likelihood that an instance keeps its current class is 1 − ε, and with ε probability, it may change its class to the next class in the transition matrix. By contrast, symmetry flipping changes the class of a selected instance to any other class, where all classes are equally likely to be selected as a replacement of the original class, according to the transition matrix shown in Figure 4(b). As in [29], the noise ratios were 20% and 50% for symmetry noise, i.e., ε � 0.2, 0.5 { }, and 45% for pair noise type, ε � 0.45. All experiments were implemented using a 9-layer CNN trained for 200 epochs.
We compared our noise discriminator method with seven other methods for noise handling. ese methods are as follows: (i) Bootstrapping [9]: fixes noisy labels using the labels predicted by a neural network, where the consistency of prediction is a weighted measure for correct labels. (ii) S-model [31]: detects noisy instances on the basis of the constitution of a noisy transition matrix, which is used by an additional softmax layer.   Computational Intelligence and Neuroscience (iii) F-correction [32]: corrects a network's prediction using a noise transition matrix, where the estimation of the matrix occurs with a standard network that undergoes initial training.
(iv) Decoupling [33]: leverages two classifiers and updates the parameters based on the samples that have predictions that contrast with the classifiers.
(v) MentorNet [34]: trains two networks, one a teacher and another a student. e purpose of the teacher network is for pretraining and filtering noisy instances. In turn, the output of the teacher network is used as an input for the student network for training, which is employed later for classification.
(vi) Coteaching [29]: relies on a pair of simultaneously trained networks, each of which feeds its counterpart with supposedly clean instances during training. In this case, clean instances are defined based on their small-loss values.
(vii) EBF [23,24]: it is based on monitoring and analyzing the distribution of exponential moving average (EMA) values of the loss values of the training instances. An instance that continues to have a large EMA is identified as an outlier and eliminated.
All of the discriminators trained in Section 4.1 were used as a preprocess to clean the datasets. en, a 9-layer CNN    was trained using the cleaned data for the corresponding classification problem. Table 12 summarizes the results of all methods in terms of the classification accuracy for digit recognition using the cleaned version of the noisy MNIST. We used three noise discriminators based on two seed instances with data augmentation (2S + DA), five seed instances without data augmentation (5S), and five seed instances with data augmentation (5S + DA). e results clearly indicate that noise negatively impacted all methods, and the accuracy decreases as the noise ratio increases. However, training a classifier using the cleaned data by the proposed discriminator enabled the model to achieve reasonable performance regardless of the noise type and noise ratio.

Evaluation Using MNIST.
Under a 20% symmetry noise, every method achieved a reasonable classification accuracy. However, this accuracy decreased with a 50% noise ratio. Notably, the best-performing discriminators, which yielded overall accuracies of 96.33% and 93.07%, were the discriminator based on 5 seed instances with data augmentation and the discriminator based on 2 seed instances with data augmentation, respectively. However, they came after EBF, which achieved 98.27%.
Pair flipping represents the hardest type of noise compared to symmetry flipping, as can be seen from the results of all methods. However, all of the proposed noise discriminators outperformed all other methods. In particular, the discriminator based on five seed instances was the best, where it achieved an overall accuracy of 97.13% (approximately 9% higher than EBF, which is the second top-performing method).
It is noteworthy that the data augmentation procedure displayed a considerable improvement in terms of discriminator performance. is can be seen in Table 12, where the discriminator based on 2 seed instances for each class with data augmentation outperformed the discriminator based on 5 seed instances and without data augmentation.

Evaluation Using CIFAR-10.
e three discriminators built for CIFAR-10 in Section 4.1.2 were used to clean the noisy datasets of CIFAR-10. Table 13 summarizes the accuracy of all methods. e table reveals that the proposed discriminators are competitive with the other methods. Moreover, the three discriminators outperformed their counterparts for pair noise. Table 13 shows that the discriminator based on 400 seeds (400S) outperformed all other methods by a large margin with 50% symmetry noise and 45% pair noise. Specifically, the discriminator outperformed the second-best method by approximately 5% under 50% symmetry noise; and it outperformed the second-best method by approximately 8% under 45% pair noise. For 20% symmetry noise, EBF and the discriminator outperformed the other methods by achieving 85.58% and 84.72%, respectively.

Evaluation Using CIFAR-100.
e number of classes that a dataset contains is a major factor that influences the performance of all noise mitigation methods. e higher this number is, the more challenging the dataset is. erefore, the CIFAR-100 dataset, which contains 100 classes, represented a significant challenge for all methods.
In this experiment, the three discriminators built for CIFAR-100 in Section 4.1.3 which were based on 10, 30, and 50 seeds per class were used to clean the noisy CIFAR-100 dataset. Table 14 summarizes the results of all methods.
As shown in Table 14, for 45% pair noise, the discriminator based on 50 seeds (50S) outperformed all other methods by at least 12% higher accuracy. It also came in second place (after EBF) for 50% symmetry noise. However, EBF accuracy was drastically decreased for 45% pair noise.

4.3.
e Effect of the Discriminators on Training Time. is section investigates the impact of the discriminator on the training time of the classifiers that were trained using the cleaned datasets. We will also study its impact on the number of epochs and the achieved classification accuracy under specific conditions. Several experiments were undertaken on noisy versions of the MNIST, CIFAR-10, CIFAR-100, Fashion [35], and Traffic Signs [36] datasets, which were used to train a 9-layer CNN before and after Table 12: Average test accuracy on MNIST over the last ten epochs. e top part of the table presents the results that were adapted as published in [29]. e bottom part shows the results achieved by our implementation.

Method
Flipping cleaning the datasets with the proposed discriminator. It is intuitive that if the discriminator effectively eliminates outliers, the training time and the number of epochs needed to train the classifiers will decrease while increasing the classification accuracy.
Rather than training the classifiers for a specific number of training epochs, as we did so far, in the following experiments, the training process will continue until one of the following two conditions is met: either the training loss (error) value falls below 0.03 or when a maximum of 300 epochs is reached. In each experiment, we recorded the training time.
Given that three discriminators were trained for each dataset in Section 4.1, we used the discriminator that gave the best classification accuracy for every dataset, namely, for MNIST, we used the discriminator based on five seeds, while for CIFAR-10 and CIFAR-100, we used the discriminators based on 400 and 50 seeds, respectively.
In this section, we also use two more datasets: Fashion and Traffic Signs. Fashion dataset includes 60,000 instances in the training set and 10,000 instances in the test set. Each instance is a 28 × 28 gray image and labeled with one of ten classes. e Traffic Signs dataset contains 34,799 instances for training purposes and 12,630 instances for testing purposes. Each instance is represented as an RGB image of 32 × 32 and is labeled by one of 43 classes. For the Fashion dataset, we trained a discriminator based on ten seeds with data augmentation. We used an augmentation factor of ten, which means that the discriminator was trained using 90,000 instances (see equation (2)). e architecture of the discriminator model for Fashion is the same as the model used for MNIST. Finally, for the Traffic Signs dataset, we trained a discriminator using ten seeds with data augmentation. Due to the large number of classes in this dataset (43 classes), we used a small augmentation factor of one, which implies that the discriminator was trained on 180,600 instances (see equation (2)). e discriminator model's architecture was the same as the model used for CIFAR-10. Table 15 shows that, after using the proposed discriminator to clean the noisy datasets and using the cleaned data to train classifiers, a substantial improvement was observed in classification accuracy and training time compared to training the classifiers using the noisy (uncleaned) dataset. e only exception was in the Fashion dataset with 20% symmetric noise. e use of the discriminator led to a reduction in accuracy by 1.42%, but the training time was also reduced in this experiment too.
A remarkable improvement in classification accuracy was observed for the MNIST dataset after using the discriminator to clean the data, along with improvements in the required number of training epochs and the required training time. Notably, a considerable improvement was achieved for the MNIST results as a result of using the discriminator, as can be seen in Table 15.
As for CIFAR-10, Table 15 shows that a considerable improvement in classification accuracy was achieved for all types of noise. However, with 20% symmetric noise, a slight increase of two training epochs was noted, but still, the training time was reduced from 8.2 K seconds down to 5.1 K. e reduction in training time is due to the reduction in the size of the training data (as a result of eliminating the noisy instances). Also, in the case of 45% pair noise, the number of training epochs grew from 89 to 129, but still, the training time was reduced from 8.6 K down to 5.3 K seconds.

Computational Intelligence and Neuroscience
Regarding the CIFAR-100 dataset, the maximum number of training epochs (300) was reached in all experiments. However, a substantial improvement occurred in classification accuracy and training time in all experiments. e reduction in training time is due to the reduction in the size of the training data, which was reduced from 50,000 instances to 16,701, 10,920, and 11,917 instances in case of 20% symmetric noise, 50% symmetric noise, and 45% pair noise, respectively.
As for the Fashion dataset, training the classifiers using the cleaned data considerably improved the classification accuracy and reduced the number of training epochs and training time.
e only exception is with 20% symmetry noise, where the classification accuracy was reduced from 85.76% down to 84.34%.
Regarding the Traffic Signs dataset, which contains 43 classes, using the discriminator to clean the training data resulted in considerable improvements in training time, training epochs, and classification accuracy.
e results indicate that the proposed noise discriminator method led to a substantial reduction in training time  across every dataset. is comes as a result of reducing the number of training epochs, reducing training data size, or both. Furthermore, the use of the discriminator increased the classification accuracy, particularly when we have a high ratio of outliers. Hence, it is reasonable to conclude that the use of a noise discriminator to clean the training data has a positive effect on the training time, training epochs, and classification accuracy in most cases. It is worth noting that, in this evaluation, the training time of the discriminator was not taken into consideration. Nevertheless, Figure 5 indicates that the reduction in training time was remarkable, which compensates for the procedures undertaken as a preprocess before training. In any case, the improvement in the classification accuracy justifies the training time of the discriminator.

Comparing the Classification Accuracy of Different
Methods. Noise type and noise ratio are critical factors that pose major challenges for the performance of noise mitigation methods. Pair flipping represents the hardest case of noise. For instance, F-correction performed reasonably under symmetry noise, while it failed completely to learn under pair noise in all datasets (see Tables 12-14). e accuracy of every method was lower for pair noise compared to symmetry noise, but by contrast, the proposed discriminator performed well under pair noise as was discussed in Section 4.2. Figures 6-8 present each method's classification accuracy results for different types and ratios of noise for all datasets. It is clear from these figures that the type and ratio of noise represent a challenge for all methods. However, the proposed noise discriminator's performance is stable irrespective of the type and ratio of noise. erefore, it is reasonable to conclude that the proposed discriminator offers a vital improvement in terms of accelerating the training process after cleansing the training data.
Although the proposed discriminator demonstrates superior results compared to the other methods, its limitations cannot be overlooked for datasets with many classes. Training the proposed discriminator to clean a dataset with a substantial number of classes requires a large training dataset. is is because the size of the dataset generated to train a discriminator is proportional to the number of seeds and the number of classes. erefore, if the number of classes is large, then the size of the dataset needed to train the discriminator will also be large. For a dataset of 100 classes, for instance, the discriminator may need to be trained on a dataset of 1,980,000 instances, which requires relatively processing resources. Investigating other methods to reduce this number may be an interesting future work.

Conclusion
Many machine learning methods, including deep learning models, require vast amounts of high-quality training data to perform well. However, large datasets usually contain noise, which may undermine the performance. is paper proposes a novel discriminator for outlier detection, and it presents a systematic approach for generating the dataset required for training the noise discriminators based on a small number of genuine instances. e empirical results show that the proposed method is effective, especially for training data that contain excessive noise. e results also indicate that the proposed method performs well regardless of the type of noise (e.g., pair or symmetry noise). e method was compared with seven other methods with respect to the achieved accuracy after noise mitigation.
In the future, we intend to investigate utilizing other algorithms of learning such as semisupervised learning or weakly supervised learning to take advantage of those instances which were identified as outliers by the proposed discriminator. Furthermore, we intend to investigate the use of similar discriminators to relabel the identified outliers.
Data Availability e data that were used in the manuscript are the benchmark data that are already cited.

Conflicts of Interest
e authors declare that they have no conflicts of interest.


Cost-aware Feature Selection for IoT Device Classification

Classification of IoT devices into different types is of paramount importance, from multiple perspectives, including security and privacy aspects. Recent works have explored machine learning techniques for fingerprinting (or classifying) IoT devices, with promising results. However, existing works have assumed that the features used for building the machine learning models are readily available or can be easily extracted from the network traffic; in other words, they do not consider the costs associated with feature extraction. In this work, we take a more realistic approach, and argue that feature extraction has a cost, and the costs are different for different features. We also take a step forward from the current practice of considering the misclassification loss as a binary value, and make a case for different losses based on the misclassification performance. Thereby, and more importantly, we introduce the notion of risk for IoT device classification. We define and formulate the problem of cost-aware IoT device classification. This being a combinatorial optimization problem, we develop a novel algorithm to solve it in a fast and effective way using the Cross-Entropy (CE) based stochastic optimization technique. Using traffic of real devices, we demonstrate the capability of the CE based algorithm in selecting features with minimal risk of misclassification while keeping the cost for feature extraction within a specified limit.

IoT devices, subsequently using them as bots for launching different kinds of large-scale attacks (e.g., DDoS attacks) that result in significant losses [2], [3]. Attackers often explore and exploit vulnerabilities to gain access to machines. In this IoT era, it is now possible to exploit a few vulnerabilities of just one device type, and compromise hundreds of thousands of devices of the same type using the same exploits.
To detect and prevent attacks on and from IoT devices, one of the important tasks is to identify the type of devices connected to a network. Device identification is useful in keeping track of various device types in a network, which consequently helps in analyzing and defending against potential vulnerabilities of various IoT devices. In addition, a mitigation solutionsuch as blocking devices with newly known vulnerabilities-can be implemented quickly, if the network administrator knows the identities (brand, model number, functionality, etc.) of the devices connected to the network. Recent years have seen research proposals on identifying IoT devices, particularly by analyzing their network traffic (e.g., see [4], [5], [6] and [7]). Existing solutions often use machine-learning based approaches to fingerprint IoT devices, by extracting a number of features from IoT traffic. For instance, in the case of supervised or semi-supervised approaches (e.g., [8] and [9]), the features extracted are used to train a classification model to differentiate IoT devices while in operation.
A common underlying assumption of the device classification works in the literature is that all features can be easily extracted from the traffic and that there is no difference-technical or otherwise-in extracting any two different features. However, we argue that, such an assumption misses out some important points. Extraction of features from traffic incurs a cost, and different that (i) features have associated costs, (ii) a solution developer has a budget constraint, and (iii) there could be different kinds of losses due misclassifications. Different from existing works, the challenge here is to develop a cost-optimal IoT device classification solution with high accuracy.
Our contributions are the following: 1) We introduce the notion of feature cost and budget constraint in the problem of IoT device classification. Furthermore, going beyond the current way of treating misclassification as a binary value, we consider multiple losses due to misclassification (Sec. III-D), and introduce the notion of risk (Sec. III-E) to evaluate a classifier's performance. Subsequently, we formulate the feature-selection problem under constrained budget as an optimization problem (Section IV).
2) We present and develop a cross-entropy (CE) based algorithm (Section V), that solves the optimization problem efficiently. In comparison to a brute force approach which has to run a classifier exponential number of times, the number of executions (of classifier) that the CE algorithm has to run is linear in its two parameters.
3) We conduct extensive experiments using traffic of real IoT devices, analyzing a brute force approach, multiple greedy algorithms and our proposed CE-based algorithm, comprehensively.
We believe our framework for cost-optimal feature selection is also applicable for other problems, where features have associated costs and solution deployment has a budget constraint.
Examples of such problems in the domain of network traffic analysis include the traditional network application classification [15], botnet detection [16], anomaly detection in traditional [17], [18] as well as IoT [19] networks, etc.
After defining the system model in Section III, we formulate the optimisation problem in Section IV. In Section V, we develop the CE-based algorithm. Subsequently, in Section VI, we present three greedy algorithms for selecting features while respecting the provided budget. We carry out experiments and present results in Section VII.

II. RELATED WORKS
Fingerprinting or identification of hosts, operating systems, etc. has been a problem of interest for many years now (e.g., see [20]). Similarly, there have been works on fingerprinting devices; for instance Gao et al. [21] proposed to identify wireless access points by applying a waveletbased approach on frame arrival time differences. With the emergence of IoT devices, research works have looked into inferring different aspects of IoT devices from their network traffic [22], [23]. For example, the work in [23] reveals private and sensitive information of users at a smart home are leaked by analyzing only the encrypted network traffic.
Identification of IoT devices is of use to different entities, such as enterprises and ISPs. For an enterprise, identification helps in asset tracking as well as for securing the devices from potential vulnerability exploitation; whereas, for ISPs, knowing the type of different devices connected to its network might help in mitigation of large-scale attacks. For instance, Yang et al. [24] generated fingerprints of devices using neural algorithms, which were used to discover millions of devices connected to a network.
Recent works have been exploring machine learning models for IoT device fingerprinting. A common approach is to employ supervised machine learning, to train a single classifier for each device [4], [5]; and these set of classifiers are subsequently used for predicting a traffic session (or sequence of first n packets) of a device. If a device traffic is predicted to be of multiple types (or classes), then another metric (such as edit distance [25]) is used to break the tie. In our previous work [9], we combined both supervised and unsupervised approaches for identifying known devices as well as grouping unknown devices of the same type across different networks.
We explored large number of features extracted from network traffic, and the empirical study based on 16 IoT devices confirmed with other works that, devices can be classified based on network traffic features with high accuracy.
There are also works that consider the cost of including different features, although not in the IoT settings (e.g., [26], [27]). We briefly discuss a few here. In [28] the authors used a particle swarm optimization approach for cost-based feature selection in order to get a Pareto front of nondominated solutions which gives both high accuracy and low cost. Among other works, Min et.
al formulated cost-constrained feature selection as a CSP (constraint satisfaction problem) [29]; while they proposed a heuristic solution, they assumed decisions as given, and the notion of risk was not considered within the scope of the work. There are also works that included a cost evaluation function as part of existing feature selection approaches; for example, two filter-based feature selection methods were experimented in [30]. Another interesting approach was proposed in [31], wherein the cost of feature selection was made part of the SVM classification model for a credit scoring application. However, to the best of our knowledge, previous works did not consider the cost of different features that are extracted for training and classifying devices. Neither did they consider the risk of misclassification, in particular when the loss due to wrong classification can be different depending on the classification result. We consider these important aspects in our work here.

III. SYSTEM MODEL
We describe the system model in this section. Below, we first state the assumptions of the system, and then go on to define misclassification loss as well as our concept of risk. The commonly referred notations are listed in Table I.

A. Traffic and features
Let D denote the set of devices considered for classification in a network; furthermore, let n = |D|. Corresponding to a device d ∈ D, assume q d units of traffic have been stored and made available for the purpose of device classification. For simplicity, and without loss of generality, we assume q units of traffic are available for every device. Let T d denote the traffic of device d.
Each unit of traffic (a connection or a session) of T d is processed to extract the feature vector.
We use f to represent the m features of interest in our problem: Denote by E(.) the function for feature extraction. For an input traffic data T d of device d, E(T d ) produces a matrix S d of extracted features corresponding to all units of traffic: where s d j,k denotes the k th feature extracted from the j th traffic unit of device d. To generalize, we use s to denote an extracted feature vector of a device. Obviously, s is of length m. Note that, S d , ∀d ∈ D form the dataset X used for training and testing the classification model. We use X train and X test to denote the partition of the dataset for, training and testing, respectively.

B. Cost of feature extraction
Features characterise different aspects of the network traffic, and are obtained by processing network traffic. Therefore, feature extraction involves cost in terms of resources required for processing and storing the feature, and sometimes for even purchasing the feature. With a slight abuse of notation, we use E f k (.) the function to extract feature f k , 1 ≤ k ≤ m. Therefore the cost of extracting a feature f k will be denoted by: represented using an n×n confusion matrix X M that is processed to obtain relevant performance metrics, such as precision and recall. The element in the i th row and j th column of the confusion matrix, x i,j , represents the number of data points (or instances) of class j that were predicted to be of class i by the classifier. Given the confusion matrix, we now define p i,j , the probability of misclassification, as the probability that an instance of class j is predicted as an instance of class i. That is if d is the predicted device and d is the actual device, then we define the probability of classifying d = j as d = i is given as: For a classification model M, we define an n × n misclassification matrixP M with elements p i,j 's. For simplicity, henceforth, we drop the subscript and denote the misclassification matrix as P.

D. Misclassification loss
Assume that the classifier is tasked to predict the class of a device d i . We represent a device d i as as an ordered pair < type, brand >, where type indicates the type of the device, e.g., a camera or a speaker, while brand represents the brand of the item, e.g., Sony or Samsung.
This loss matrix is a user-defined parameter and depends on the types of devices considered for classification. While this allows for a generic definition of the misclassification losses as deemed right by the user, we later provide (in Section VII-C) the specific definition used in this work for the purpose of illustration as well as for experimentation.

E. Cyber Risk
Using these definitions, we define the cyber risk of the model. While f is the vector of features of interest, not all features might be available for modeling, given features have cost, and a solution is constrained by the available budget. We use a binary vector v to indicate whether a feature is selected or not.
Next, we define cyber risk. Given a classifier M, loss matrix L, feature budget λ, the extracted data (for the selected features indicated by v) X v , and a feature selection vector v, the cyber is the expected sum of the losses due to misclassifications. Since we are considering the risk score for a fixed classifier model, for a fixed number of devices and traffic data, we may simplify the risk score by denoting it as R(v). Formally, the cyber risk score or the risk score, based on the set of selected features (captured by v), is defined as the sum of the product of the probability of misclassification and the losses associated with misclassification of each device (l i,j ), which is given by:

IV. PROBLEM DEFINITION -OPTIMAL FEATURE SELECTION UNDER BUDGET CONSTRAINT
This work looks into the problem of minimizing the cyber risk associated with classification of IoT devices, by selecting the optimal set of features from a universal feature set, whilst keeping the feature cost less than the budget available.
Problem Definition: Given the misclassification matrix P for a given feature vector f , and the loss matrix L, we aim to find the optimal feature vector (via v) which minimizes the cyber risk score R(v), under a budget constraint λ.
Thus, the optimization problem may be defined as: where R(v) is as defined in Eq. 4.
The optimization problem presented in Eq. 5 has some unique properties making it a nontrivial problem to solve. Firstly, the cyber risk function R(v) used as the principle objective function, is not an analytic function. Hence, using methods to solve continuous optimization problems, like the gradient descent is not feasible in this scenario. This is mainly because the gradient descent uses the Newton's Method to find the optimal solution which in turn uses a well-defined continuous objective function; and R(v) is not a continuous function. Moreover, another important constraint to use such methods requires the objective function, the constraint equations and the domain space to be convex in nature. In our scenario, we do not know whether we have a closed-form analytical expression for the risk score which is the objective function.
This is because it is dependent on the classification model and the features selected. Though a probabilistic model for a simple classifier like the Naive-Bayes classifier can be obtained, we cannot say the same for any general classifier, for example the Decision tree or the Random Forest classifiers. Thus, in a general sense, it is not possible to get an analytical expression for the risk score defined in Eq. 4. The best we can do is to obtain a point-wise evaluation of the objective function which is the minimum requirement to attempt a solution to this optimization problem.
We observe that the constraint functions are affine in nature, and since all affine functions are convex, the constraint functions are also convex in nature. This leaves us with the domain space (m-dimensional binary subspace) for the optimization problem.
Since the domain space is not convex in nature, we can safely conclude that the problem is not a convex optimization problem, and cannot be solved by using convex optimization tools.
Therefore, the optimal way to solve such problems is via a combinatorial search over all possible combinations of features by the brute force method which is not a very efficient way. In classes of problem such as the one posed in this paper,a subsequent brute force enumeration of all possibilities is computationally prohibitive and as such a stochastic search based approach needs to be developed in practice. In the next section, we explore the cross entropy technique for searching the entire subspace in an efficient way to potentially converge to the global optima.

V. FEATURE SELECTION VIA CROSS ENTROPY METHOD
In this section we develop a novel algorithm to solve the feature selection under budget constraints, presented in Eq. 5. As mentioned before, this is a non-convex combinatorial optimization problem. To overcome this computational difficulty, we develop a novel algorithm via a Monte Carlo sampling approach, which has a low computational complexity. Specifically, we use the cross entropy (CE) technique, which is based on the Importance Sampling Technique which is known to be an effective solution in computational approaches to otherwise solving NP-hard problems. The CE converts the deterministic optimisation problem into a stochastic couterpart, see details in [32]. It then approximates the optimal sampling distribution by minimizing the Kullback-Leibler (KL) divergence [33]. Without loss of generality, we may change the optimization problem in Eq. 5 to a maximization problem, that is: . Instead of searching for the optimal solution directly, like in the case of a brute force search based approach, the CE places a probability distribution on the set of m-dimensional binary features (v ∈ {0, 1} m ), thus transforming the problem into estimation.
In our model, since the selection of a feature is indicated by a binary variable ("select" or "don't select"), we use an independent Bernoulli random variable to indicate this choice for each of the m features. The Bernoulli distribution has a single variable parameter p , i.e., for the k-th feature this is given by {p k } m k=1 , and is a member of the Natural Exponential Families (NEF) of distributions [34]. This is a big advantage, since under the NEF, the parameter of the distribution can be estimated analytically in closed form via the Maximum Likelihood Estimator (MLE), making the CE easy to implement. At each iteration of the CE method there are three steps: S1 Generate samples: generate η independent samples of binary sets given by S2 Selection of elite samples: from those η samples, we select only those samples which satisfy the budget constraint (ie. c T w [i] ≤ λ) to obtain a subset of η ≤ η samples. Next, from this subset we select only the "elite" samples-those for which the objective function value exceeds a pre-defined threshold, defined via a quantile value ρ. This choice is indicated S3 Estimation of parameters: using only this subset of elite samples, we re-estimate the parameters of the Bernoulli random variable {p k } m k=1 via the MLE, given by The three steps of the algorithm are then iterated until a stopping rule is met, for example, if the algorithm has converged to a local maxima or has exhausted a pre-defined number of iterations.
The parameter ρ is the quantile value, and is commonly set to 0.9. The resulting algorithm is presented in Algorithm 1, where in Step 10 we have introduced the parameter α ∈ [0, 1] which controls the learning rate of the algorithm, thus avoiding getting trapped in local maxima, see details in [33].
It is important to note that v k , where 1 ≤ k ≤ m, denotes whether the k th feature is selected by the algorithm. We iterate the cross entropy algorithm until the convergence criterion is met, which in this work, translates to reaching the maximum number of iterations (T max ).  Step 1:

4
Generate η independent samples of binary sets given by Step 2: ComputeP, from X as given in Eq. 2.

VI. FEATURE SELECTION VIA BRUTE-FORCE AND GREEDY APPROACHES
In this section we develop algorithmic alternatives to the CE technique that will act as comparisons to our proposed approach. We first present the brute-force approach for solving the optimization problem (Eq. 5). Subsequently, we also develop three greedy heuristics that use different strategies for selecting features for device classification.

A. Brute Force Method
The brute force approach is presented in Algorithm 2. The algorithm selects each combination of the features (via the vector v), and evaluates the risk score if the cost of the features is within the budget constraint (λ). Of all such feature combinations, one that minimizes the risk score is the optimal set of features for device classification. Though this method gives the optimal solution over the feature space, the computational complexity of searching over the entire parameter space exhaustively is prohibitively high. Thus, this approach gives us an upper bound on the run-time complexity of the algorithm, and also a lower bound on the risk.

B. Greedy Algorithms
As the name suggests, greedy algorithms are efficient ways to solve an optimization problem, with the down side being that, they might end up with a local optimum. We define three intuitive greedy approaches in this section; they differ on the parameter (referred to as key) they used to select the next feature for classification. The general steps for these three greedy approaches are given in Algorithm 3. First, the feature indices are sorted based on an input parameter key.
Subsequently, in each iteration within the while loop, the algorithm selects one feature at a time, constrained by the budget, thereby eventually forming the feature vector (indicated by v) for classification. 2) Risk-based greedy algorithm (RGA): Next, we define a risk based approach. We train a classifier using only one feature at a time, and we do this for all features constituting f . For

Algorithm 2: Brute Force Feature Selection
Input: X train , X test , c, λ, f , M,L ComputeP, from X as given in Eq.  12 ComputeP, from X as given in Eq. 2 13 Compute R(v) according to Eq. 4 14 return v the value of a feature f i as: The vector of values is then passed as the parameter key to Algorithm 3.
Complexity: Like the previous greedy algorithm, in this algorithm too, the classifier is run m times to train the model for the m features independently. Therefore, the complexity is O(m log m + m × C(m; Ψ)).

VII. PERFORMANCE EVALUATION
In this section, we describe the experiments performed to evaluate the different algorithms presented in the previous sections. After a briefing on the dataset used, we describe how we estimated costs of features (in Section VII-B). We also define the loss matrix used for experiments in this work (Section VII-C). The first set of experiments we carry out (in Section VII-D) are to evaluate a selected set of classification models. Subsequently, we evaluate brute force, CE and greedy algorithms, first under no budget constraints (Section VII-E), and then later we evaluate CE and greedy algorithms when budget is fixed (Section VII-F). In Section VII-F, we also perform further analysis to compare CE algorithm with the best greedy algorithm.

A. Real datasets for experiments
For the experiments, we used network traffic from 15 different IoT devices as listed in Table   I. The devices were connected to the Internet via a gateway, where the network traffic was captured. The traffic was split into intervals of 15 minutes each, and the number of sessions captured for each device is shown in Table II. From the network data of the IoT devices, 111 features were extracted (see [9] for the list of features).

B. Feature costs
As described earlier, the extraction of each feature has a cost. We argue that the cost of feature extraction is a function of three factors: the computational power (or computational complexity) of the extraction process, the memory used, and the confidentiality of the information related to that feature. Therefore, we break the cost into three components, each corresponding to compute power, memory and privacy. Finding the exact cost due to each component and how to integrate those component costs into a single cost value is outside the scope of this work. Instead, we simplify the cost of each component to be in one of three levels {low, medium, high}.
We illustrate the concept of assigning costs to feature using examples in the Appendix.
The total cost of a feature f i can be defined as:   extracted, and no private information (e.g., visited websites) is extracted. Therefore, the cost of extracting connection length is medium.

C. Loss matrix, L
We introduced the concept of misclassificaiton loss in Section III-D. Ideally, the loss matrix is an input provided by the users, based on how they perceive the loss due to misclassification errors. For the purpose of this work, we define the loss matrix as follows.
When the classifier classifies a device Taking every device pair, we follow this definition to derive the values for the loss matrix L in the experiments here. It is to be noted that we are giving a higher value of loss if the classifier cannot classify the type of the device even if it gets the right brand. For example, if the classifier classifies a Samsung camera as a Sony camera, the loss value l i,j = 2 × 0 + 1 = 1. But if it classifies the device as Samsung (Smart things) Hub, then the loss l i,j = 2 * 1 + 0 = 2.

D. Comparison of classifiers
The cyber risk score R(v) of a feature vector v depends on the misclassification matrix which is in turn derived from the confusion matrix of the classifier. As such, the choice of classifier plays an important role in evaluating the performance of the system. We selected four different classification models-Gaussian Naive-Bayes classifier, SVM (support vector machine) with RBF kernel, Decision tree and Random Forest, and compared their performances based on accuracy and the execution time. We use F 1 -score (the harmonic mean of precision and recall) to represent the accuracy of the classifier.
All the experiments in this work are carried out on an 8-core Intel Core i7-2600 running We also plot the accuracy of the different classifiers in Fig. 2; all of them achieve high F 1scores. Since Decision tree classifier has much less time of execution, while also having high F 1 -score, henceforth we use Decision tree for the rest of the experiments to evaluate cost-aware feature selection algorithms.  Since this is not computationally feasible, unless stated otherwise, we generate sequence of ranked features. To this end, we use the feature ranking mechanism described in our previous work [36] where the features are ranked according to their ability to discriminate between every pair of devices by combining the results from multiple statistical tests. In order to compare and evaluate the algorithms, we take the full set of ordered feature vector f (obtained via ranking), and select the first nine features from it asf = [f 1 , f 2 , . . . , f 9 ]. For each subsequent iteration, we add the next feature in the ranked order to our selected feature vector and calculate the time of execution and the risk score of all the five algorithms using the new set of selected features.
Thus for the t th iteration, the selected feature vector is represented asf = [f 1 , f 2 , . . . , f t+9 ] ; t = 0, 1, 2, . . . , 61, where |f | = t + 9. Therefore, the algorithm must be iterated 61 times, such that, when t = 61, all the 69 features will be explored. We proceed to the analyses next.   Fig. 3, we observe that the time of execution for the brute force algorithm increases exponentially as the number of features in the feature set increases. Thus, though the brute force algorithm has a low time of execution for small feature sets, it is extremely high for larger ones. This is why we limit the experiment on the brute force to 25 features. The greedy algorithms perform the best with respect to the execution time, which gradually increases with increasing m. Though the proposed CE algorithm takes more time than the greedy algorithm, its execution time is much lower than the brute force approach. Also, the growth in run-time with increasing number of features is marginal for the CE algorithm, thereby indicating the ability of the algorithm to scale.
2) Risk analysis: The risk score R(v) is another important parameter to evaluate the performance of the feature selection algorithms as we aim to minimize the risk score by the optimal selection of features. The graphs for the risk scores of the five different algorithms under consideration without any budget constraint is plotted in Fig. 4. Since this scenario does not constrain the budget, i.e., λ → ∞, note that, the three greedy algorithms will always choose all the features provided and thus, no difference is expected in the performance (in terms of accuracy and risk score) of the three different greedy approaches. We observe that the brute force algorithm gives the best risk score since it performs an exhaustive search over all possible combinations of the provided features. However, it can also be observed that the cross entropy algorithm is close in performance to that of the brute force method, and ultimately converges to the minimal risk score of 1. Due to this convergence, it may be concluded that any feature more than the first 63 (in the ranked order) is redundant in the classification of the devices when using the cross-entropy algorithm. In addition to this, it can also be observed that though the greedy algorithms select all the features, they do not give the best results. This highlights the necessity for the selection of an optimal set of features, and that the selection of a higher number of features does not necessarily imply a better risk score.

F. Evaluation of algorithms under budget constraint
Comparison of greedy algorithms: We first compare the performance of the three different greedy algorithms under budget constraint to determine the best-performing greedy algorithm.
We consider two cases: one with low budget for features, λ = 50, and another with high feature budget, λ = 200. We plot the risk scores of the three greedy algorithms For easier comparison, we also provide the mean and standard deviation of risk scores for each of the algorithms in Table III. From these results, it can be seen than VGA performs better than the other two under low budget (while all three have comparable performance under high budget).
An interesting aspect to note in the low-budget case is that, the risk scores do not decrease monotonically with increasing features provided at the input, instead we see spikes in the risk score (Fig. 5) Comparison of CE algorithm and VGA, for ranked and random ordering of features: The risk score calculated is dependent on the ordering of the features f and hence to test the performance of the algorithms, we carry out the experiments for not only the ranked feature vector, but also for randomly ordered features. The risk score R(v) is a function of the feature budget λ. Therefore, similar to the previous scenario, we compare the risk score as a function of the number of features m for a low budget (λ = 50) and high budget (λ = 200). For CE, we set the number of samples, η = 1000 and T max = 500; and compare CE with and VGA algorithms. Fig. 6 plots the results when the input provided was the ranked feature vector. CE is seen to outperform VGA under both low and high budgets. The CE algorithm consistently achieves lower risk score with increasing features, in comparison to VGA.
Under low budget constraint, we can clearly see that the CE algorithm outperforms the greedy method for all feature lengths m < 70. We observe a similar trend in Fig. 7, when randomly ordered features are provided as input. In this scenario, we evaluate the results for five different randomly ordered feature sequences, and show the standard deviation of the risk scores obtained.
We observe that the risk score's standard deviation is high for small feature length, which is quite intuitive as the small number of features (given as input) can be significantly different with every random sample. Thus the risk score also varies with different input features provided. We also note that the standard deviation of the risk scores of the CE algorithm is always low (and extremely low for the the high-budget scenario), showing the utility of the proposed algorithm.
Comparison of CE algorithm and VGA under varying budget: Finally, we compare the risk scores for the CE algorithm for varying feature budgets. The features are provided in ranked order. Since we now have two parameters to vary (m and λ), for this set of experiments, we keep the numner of samples η = 250 and the number of iterations T max = 50 for the CE algorithm.
We also conducted a similar experiment for VGA. In order to have a visual comparative analysis of the performance of the CE algorithm with the greedy algorithm, we take the difference between their risk scores for each m and λ. The resultant 3D graph for R CE (v) − R VGA (v) is plotted in Fig. 8. The part of the graph which is greater than 0 (above the z = 0 plane) denotes the conditions where the cross-entropy method has greater risk than the greedy algorithm. The risk score achieved by CE is lower than that of VGA for most cases, except when both, the budget is very low, and the number of features is high. For large m and a small λ, the CE algorithm rejects most of the initial samples, prohibiting the algorithm to select the optimal set of features possible, thus resulting in a high risk score. However, on increasing the budget, the risk score is seen to decrease. Besides, as seen in the previous set of experiments, the performance of CE can be improved by increasing the number of samples and the number of iterations.

VIII. CONCLUSIONS
In this work, we motivated, defined and focused on the problem of feature selection for IoT device classification considering the fact that there is a budget constraint for features in practice.
For this purpose, we also defined the notion of risk of misclassification. To obtain the optimal solution to this problem, one has to perform a combinatorial search over the solution space.
Therefore, we developed a cross entropy based algorithm for solving the optimization problem.
We carried out experiments using traffic of real IoT devices; our experiments showed that not only is CE algorithm practical and much faster than the brute force approach, it also obtains low risk score for classification and performs better than than value-based greedy algorithm in most cases.

APPENDIX: FEATURE COST
In this section we demonstrate how feature costs are estimated for a given IoT device. We defined the cost vector c to indicate the cost associated with each of the extracted features. The feature cost is divided into three different components. First, we analyze the memory required for the extraction of the features from the network traffic. Next, we focus on the computational complexity of the algorithm required for extracting the feature. And lastly, we analyze the intrusiveness of a feature into the privacy aspects of a device or user. For example, let us consider the feature dns_num_ans, which denotes the the number of answers returned for DNS queries.
While only a register is required to store the (running) value of this feature, a small buffer has to be maintained to temporarily store (unprocessed) DNS answers extracted from packet payloads (to absorb traffic bursts); therefore, we define the memory cost as medium. Similarly, this feature is computed by simple additions to the counter in the register. Therefore we can assume a low computational complexity. Finally, since the feature is extracted from the DNS responses (i.e., packet payload), which can leak considerable information (e.g., see [13]), we assign a high privacy cost to the feature. Table IV provides the logic we have used to define the three cost components for extracting any given feature from network traffic. To define the total cost of extracting a feature, we take the median of all three costs (memory, compute and privacy).


Complexity Estimation for Distributed Software Development Using SRS

In recent years distributed software development has gathered pace. Many development programmes now require asynchronous coordination several time zones apart between geographically dispersed teams. Owing to considerations such as effort spent on team development and technology sharing, software complexity calculation for such projects is difficult to establish a software system infrastructure that can be efficiently spread and minimizes cross-site connectivity, enabling communication between remote teams working on interrelated sections of the architecture and their day-to-day interactions. A globally distributed software project faces, in addition to the technological complexity, an additional complexity contributed by the different supporting parameters. This paper defines these parameters and attempts to estimate all the complexities described above and incorporate these two measures to obtain the corresponding overall measure of complexity during the requirement analysis phase.

Introduction
Geographic distribution of software development projects has been a requirement in recent years, and the software companies are now responsible for shifting their development teams to localized areas where qualified workers are more easily accessible, hence taking benefits of political and economic factors. The situation where a software company's numerous teams are spread outside a nation's limits is called Distributed Software Development. To produce a better quality of software products at low costs, as compared to co-located software projects, the main aim of this type of production criterion is to maximize capital. Sahay (UiO) defines DSD as "Software work undertaken at geographically distributed locations across national boundaries in a coordinated fashion involving synchronous (real time) and asynchronous interaction".
During the software lifecycle, Distributed Software Production enables team members to be located in multiple remote locations, creating a network of sub-teams that are geographically distributed in nature. Such teams may belong to the same organisation or there may be collaboration/outsourcing between various organisations. Face-to-face interaction between team members is a requirement when working on a distributed project and it involves the use of various technologies to promote communication and coordination [9].
For companies today, the distributed production of software systems and their implementations is increasingly growing in importance. There are various explanations why the trend of operating in a distributed environment should be embraced by an entity. It includes availability of a greater labour IOP Publishing doi:10.1088/1757-899X/1116/1/012193 2 pool and a good combination of skills and experiences, advantages in cost, and longer working hours [4].
A good development team for software has rich formal and informal interactions between its team members. It has a familiar organisational culture, required coordination and effective control; providing a good combination of technical skills and appropriate experience and known projectrelevant tools and technologies. DSD introduces new challenges and requirements to the product development process as it potentially threats all of the above mentioned ideal properties.
The aim of this paper is to define and then formulate different parameters that affect the software product cost in a globally distributed setting.

Related Work
Jorge Cardoso [1] discussed the requirements to develop a measure to analyze the complexity of processes in distributed software development. He stated that high complexity in a process is a key to bad understandability resulting in more errors, defects, and exceptions and hence lead processes to require more time to develop, test, and maintain. Therefore, avoiding excessive complexity becomes an essential part in software development.
Threats to communication, control and coordination in distributed development were considered by the authors in [2] due to Temporal Distance, Geographical Distance, and Socio-Cultural Distance.
Dr. Ashish Sharma and Dr. D.S Kushwaha proposed a complexity measure [16] based on the factors derived from SRS Document. Even before the analysis and design phases of SDLC, the measure can estimate the software complexity efficiently. But the approach is limited to centralized software development.
R Britto et.al in [15] developed a process that helps in developing systematically onboarding strategies.
Based on four key explanations for estimating the cost and effort of software development, the Function Points (FP) system approach was used in [35] by RS Dewi et.al. Considering Ricardo Britto et.al in [36], the findings of a systematic literature review for Global Software Development (GSD) effort estimation were presented so that the researchers and practitioners could have a clear understanding of the current state of the art about GSD effort estimation. Their outcomes indicated that an improvement on effort estimation in GSD can be made to the current state of the art. M Shameem et.al researched [37] in order to explore and prioritize the challenges of scaling agile practices in the DSD setting. Lack of efficient communication, management responsibilities, sharing of information, etc., are described as the most critical challenges for scaling agile methods by organisations.
Through [40] the authors contributed to the specification of the system and the analysis that has the ability to assist in mapping communication patterns for global software development. In addition, this platform includes communication evaluation interfaces and intercommunications from automated engineering instruments as bots.

Objective
The main aim here is to define and then formulate various factors that affect the software product's cost in DSD. The complexity of these factors is stated as Supportive Complexity (SC), which is then added to the technical complexity determined in the requirement analysis phase using RDPDC [12]. The given measure of complexity gives an approximate value of the total complexity of a software product (using SRS) to assist the project managers and analysts and the concerned development teams, who are greatly influenced by the dynamic behavior of DSD. [2], [8], [19], [21], [22] discuss the various parameters that affect the complexity of a globally distributed software project. These parameters are shown below (

Proposed Measure
The proposed framework for estimating complexity of software projects in distributed environment is shown in the figure below:

Technical Complexity
This complexity is estimated by adjusting the IRBC measure, as suggested in [16], in order to respond to the differences faced in DSD. The key benefit of using IRBC is to achieve the complexity of the software product using SRS in the requirement analysis phase itself.

Supportive Complexity
Different additional requirement parameters given in Figure 1 add supportive complications to the overall estimate of the complexity of the software product being produced in DSD, relative to the complexity of software in centralized production.
As shown in Figure 2, the fusion of the complexities determined by Predictor Variables (PVC) and Control Variables (CV) gives the Supportive Complexity (SC). The estimation of these complexities is described in section 5.2.1 and 5.2.2.

Predictor Variables Complexity (PVC):
The model suggested in [27] by H K Edwards & V Sridhar, uses separate predictor variables shown in Figure 2. The variables are identified after analyzing the factors that influence the efficiency and output of globally distributed virtual teams participating in the software development life cycle requirements specification process. Using heterogeneous teams scattered all over the world, the paper simulated the realities of the multinational software development environment. Now, in order to estimate PVC, the proposed measure is using the Predictor Variables defined by the authors in [27] and the corresponding 38 measurement items used in order to prove the construct validity as they are very well covering the parameters identified in section 4 and their impact over the complexity of a DSD project.
Requirements analysis phase is a critical phase in software engineering. The effectiveness or failure of the software project is decided by the compliance of the specifications especially in case of distributed development that presents several new difficulties as well as the rise of fundamental difficulties [32] [33]. So, right from the creation of the first version of SRS by the specification team, review and adaptation by the creation team, to the creation of the last version of SRS by the specification team itself, and the allocation of tasks and their approval by the team members at remote sites requires team members to communicate effectively and work collaboratively in order to obtain a good SRS apart from several differences, be it time, language, cultural, team size or technical. Finally, "virtuality requires trust to make it work: Technology on its own is not enough" [34].
The proposed measure suggests the calculation of the prediction variables by taking the evaluation of the measurement items by the remote site team analysts during the final stages of the SDLC's requirement elicitation and analysis phase. For the analysis to be conducted by the controlling location, the evaluations of the team analysts can be made by online GUIs accessible at the organisational sites. On a seven point Likert-type scale, all the items should be calculated as in [27] and then the mean rating of each variable for each site k is calculated as: Where MRp refers to the mean rating of the p th variable, RMIap is the p th variable's a th measurement item rating and i is the no. of measurement items for p th variable concerned. Obviously, the max value of these measures will be 7. Thus, the total value of MR for s no. of sites can be summed up as:

Control Variables Complexity (CCV):
Control is the method to fulfill the objectives, strategies, norms, or standards of quality defined by an organisation. As seen in Fig 1, this is one of the parameters determined in section 4. In essence, the proposed measure deals with the two major forces influencing an organization's control; they are Project Management and Instability/ Uncertainty. Using the project management variable PMGMT and an Uncertainty variable UC, both variables are calculated separately.
In order to accomplish particular objectives and goals, project management is the practice of preparing, coordinating, obtaining, and handling resources, and for this, an organisation needs welldefined procedures to help fulfill client and quality expectations.
As Dr. Edwards Deming, Quality Management theorist, consultant and author once said, "If you can't describe what you are doing as a process, you don't know what you are doing".
The SEI's Capability Maturity Model has five stages of organisational 'maturity' in terms of processes of software development that assess efficiency in the delivery of quality software. The proposed measure, as per the SEI-CMM Level, assigns a count value for the organisation and considers this value as the measure of PMGMT as shown in the figure below: Now, [26] claims that in the essence of globally distributed software projects, lack of knowledge of certain basic factors inherited makes developers fail and innovate new ways to survive. The paper summarizes various risks and their various negative effects and formulates the specifics of certain projects and their effects on the project success for managing uncertainty. Taking into account the length of the list of global threats and the difficulty of risk analysis, a method is built to computerize project outcome forecasts, appropriately labeled as a "risk barometer", for project managers to assess global project threats, taking into account the likelihood of occurrence and potential negative effects that can be correlated with past data of other projects. The instrument forecasts the amount of risk exposure for a hazard of scale [0; 1500].
Here the measure proposed divides the scale into 5 ranges and gives each such range a count value and considers this value as the measure of UC, as shown in the Table 3.
Thus it is appropriate to sum up the total complexity by control variables as: Hence, the overall Supportive Complexity can be measured as: And thus, for a project developed in a distributed setting, the final complexity can be given as:

Robustness Analysis of the Proposed Measure:
In order to analyze the robustness of CDSD, it has been evaluated against the 9 Weyuker's [5] properties. The results are shown in the Table 4: The application of the proposed CDSD measure has been explained in the next section.

Results
The proposed measure CDSD has been applied over ten well known algorithms and their results are compared and analyzed against the several existing ones like LOC, McCabe [14], IRBC [16], Halstead [6], CFS [41] and KLCID. Also, the complexity for "Email Classifier" project is calculated using CDSD measure. CDSD depends on the problem criteria and the additional parameters that were held constant for all 10 problems, such as connectivity, collaboration and control between team members. Thus, the IRBC plot, which also relies on the problem specifications, is very much compatible to CDSD (Figure 3).

Conclusion
This paper has investigated some factors that are affecting the performance and complexity in DSD. Through this paper, an attempt has been made to suggest a qualitative approach for estimating the difficulty of a project being developed in a distributive environment.

Motivation
There are several software complexity measures for estimating the difficulty while working in a centralized development environment. But, the same is not true in case of Distributed Software Development. Any framework or methodology for estimating the complexity in a distributed environment has not yet been proposed. So working on such significant area seems to be both challenging and interesting.