Dimitrios Milios

Ioannis Stamelos

Christos Chatzibagias

Global Optimization of Analogy-Based Software Cost Estimation with Genetic Algorithms

Estimation by Analogy is a popular method in the field of software cost estimation. A number of research approaches focus on optimizing the parameters of the method. This paper proposes an optimal global setup for determining empirically the best method parameter configuration based on genetic algorithms. We describe how such search can be performed, and in particular how spaces whose dimensions are of different type can be explored. We report results on two datasets and compare with approaches that explore partially the search space. Results provide evidence that our method produces similar or better accuracy figures with respect to other approaches.

Introduction

One of the most challenging, yet essential, tasks in software industry is cost estimation. The term cost refers to the human effort spent in every phase of the development life cycle, including analysis, design, coding and testing. The most widely researched estimation methods are expert judgement, algorithmic/parametric estimation and analogy based estimation [START_REF] Boehm | Software engineering economics[END_REF]. The first one involves consulting one or more experts who provide estimates using their own methods and experience. Although this practice produces estimates easily, the dependency on human factor has certain drawbacks, like subjectivity or availability of the expert. Algorithmic estimation models, such as COCOMO [START_REF] Boehm | Software engineering economics[END_REF] and Function Points Analysis [START_REF] Albrecht | Software function, source lines of code, and development effort prediction: a software science validation[END_REF], have been proposed in order to generate estimates in a more repeatable and controllable manner. They are based on mathematical models that produce a cost estimate as a function of a number of variables. Several researchers have investigated the accuracy of such models. For example, Kemerer has suggested in [START_REF] Kemerer | An empirical validation of software cost estimation models[END_REF] that the efficiency of such models is strongly dependent on the calibration of these models to local conditions. Finnie et al [START_REF] Finnie | A comparison of software effort estimation techniques: using function points with neural networks, case-based reasoning and regression models[END_REF] conducted a comparison between algorithmic cost models, Artificial Neural Networks and Case-Based Reasoning for software cost estimation. It was verified that algorithmic models do not effectively model the complexities involved in software development projects. Both CBR and ANN produced more accurate estimations for the effort, however, ANN do not adequately explain their predictions. More recent research has reinforced such findings, providing further evidence in support of calibration. For example, in [START_REF] Kitchenham | Cross versus within-company cost estimation studies: a systematic review[END_REF] it was found that estimates based on within-company projects are more accurate w.r.t. estimates based on cross-company historical data. In addition, research efforts have been dedicated to approaches that aim to explain better cost estimates to users and managers [START_REF] Bibi | Combining probabilistic models for explanatory productivity estimation[END_REF].

Estimation by Analogy (or EbA) is a case-based reasoning technique, in which cost estimation is produced by comparing the characteristics of the target project with the ones of old cases. These old cases are projects with known costs, also called analogies. It is assumed that the cost of the project to be estimated will be similar to that of the most similar projects. The similarity between two projects can be specified using the distance between them in the N -dimensional space defined by their characteristics. In most of EbA recent implementations [START_REF] Huang | Optimization of analogy weights by genetic algorithm for software effort estimation[END_REF][15] [START_REF] Li | Analysis of attribute weighting heuristics for analogy-based software effort estimation method AQUA+[END_REF], Euclidean distance is adopted for measuring project dissimilarity. In this work, the following distance metrics are also considered: Euclidean, Manhattan, Minkowski, Canberra, Czekanowski, Chebychev and Kaufman-Rousseeuw.

Projects are classified differently for each one of the metrics above, thus method's performance is affected. The choice of attributes that describe the projects also affect this classification, since the attributes are not of the same importance [START_REF] Shepperd | Estimating software project effort using analogies[END_REF]. Attribute importance can be expressed either as the subset of attributes that best describes the given dataset, or as a vector of weights that are applied to the attributes. Furthermore, it has been already stated that the prediction accuracy is sensitive to the number N of analogies [START_REF] Shepperd | Estimating software project effort using analogies[END_REF]. One more issue is how to combine their values in order to produce an estimate. In this paper the following statistics are used for the adjustment of the efforts of the most similar projects: Mean, Median, Size Adjusted Mean and Size Adjusted Median.

The objective of the current paper is to propose an automated strategy to select a combination of the parameters described above that result in the best performance for EbA. What we have is an optimization problem featuring a huge search space. The width of the possible solutions as well as the lack of an underlying mathematical model imposes the use of approximate search algorithms. In this domain, a popular optimization method is Genetic Algorithms (or GA).

A brief overview of related work is presented in Sect. 2. Section 3 describes how global optimization can be implemented with GA. Section 4 provides some experimental results. Finally, Section 5 concludes and provides future research ideas.

Related Work

Estimation by Analogy, was considered as valid alternative to conventional methods long ago [START_REF] Boehm | Software engineering economics[END_REF], although it was not presented as estimation methodology until 1997 by Shepperd and Schofield [START_REF] Shepperd | Estimating software project effort using analogies[END_REF]. The efficiency of EbA is dependent on numerous parameters that affect the way of retrieval of similar projects and producing estimations. In [START_REF] Shepperd | Estimating software project effort using analogies[END_REF], it was found that the exclusion of the least important attributes results in improvement of prediction accuracy. In the same paper, the number of analogies was marked as another parameter that has to be carefully determined, since it has a strong effect on final estimates. In [START_REF] Angelis | A simulation tool for efficient analogy based cost estimation[END_REF], different distance metrics were also investigated and it was proposed that interval estimates be produced for EbA.

The optimization of certain parameters in applying analogy was among the goals of AQUA method [START_REF] Li | A flexible method for software effort estimation by analogy[END_REF]. More specifically, a learning phase was applied in order to find the number of analogies and the threshold for the degree of similarity that granted the maximum prediction accuracy. Exhaustive search was used, by applying jackknife [START_REF] Efron | A leisurely look at the bootstrap, the jackknife, and crossvalidation[END_REF] for each number of analogies and similarity threshold. It was observed that although, in general, high numbers of analogies tend to produce increased values of MMRE, best performance is achieved for a different number of analogies for each database. Furthermore, the optimum number of analogies varied for different values of the threshold.

The importance of the project attributes was also discussed in various papers. For example in [START_REF] Keung | Analogy-X: Providing statistical inference to analogy-based software cost estimation[END_REF], a stepwise procedure based on statistical analysis was used, in order to select the most important attributes. However, it is more common that weighting factors are used to adjust the influence of each attribute in correspondence with its own significance. In [START_REF] Huang | Optimization of analogy weights by genetic algorithm for software effort estimation[END_REF], a GA approach was proposed as a search method for identifying a combination of weights that maximizes the accuracy of the EbA. Further improvement was possible after applying both linear and nonlinear equations as weighting factors. The identification of the optimum weights was the objective of a second version of AQUA that was published in 2008 [START_REF] Li | Analysis of attribute weighting heuristics for analogy-based software effort estimation method AQUA+[END_REF], establishing a way of attribute weighting based on rough set analysis.

In 2007, Chiu and Hung [START_REF] Chiu | The adjusted analogy-based software effort estimation based on similarity distances[END_REF] proposed an adjustment of the efforts of the closest analogies, based on similarity distances. According to experimental results, this way of adjustment outperformed the typical adjustment methods. It is also important that more than one distance metrics were used in these experiments, including Euclidean, Manhattan and Minkowski. It is interesting, however, that there was no distance metric found that was globally superior to others. In fact, performance of each distance metric varied both for different ways of adjustment and different datasets.

From what has been discussed so far, there is no optimization proposal that considers all parameters involved in EbA. Consequently, although genetic algorithms have already been adopted in the field of cost estimation [START_REF] Huang | Optimization of analogy weights by genetic algorithm for software effort estimation[END_REF][19], the current paper focuses on a fitness function and a problem representation that enable the search to be expanded to any application parameter available. The challenge is to combine the variables that represent the alternatives in applying EbA with the N -dimensional space derived from the weighting factors of project attributes.

Global Optimization by Genetic algorithms

GA [START_REF] Holland | Adaptation in natural and artificial systems[END_REF] is a search technique inspired from the genetic evolution in nature. Given an optimization problem, populations of possible solutions are considered, from which the fittest ones are going to survive and get combined so as to form a probably better population. The new set of solutions, or else the next generation, goes through the same process. It has been observed that the average fitness of each generation is increased. So, it is quite possible that the population will converge to one of the local optima.

In the case of EbA optimization, the individuals of the population are different combinations of the alternatives for applying the EbA method. In general, most GAs consist of the following components [START_REF] Goldberg | Genetic algorithms in search, optimization, and machine learning[END_REF]:

-Encoding refers to the assignment of a unique string to each solution. The characteristics of a solution are translated into genes. Genes are parts of a larger string, the chromosome, in which the entire solution is encoded. -Genetic operators are applied to the chromosomes. Their purpose is to produce the genes of the chromosomes of the next generation. -Fitness evaluation function assigns to each solution-individual a value that corresponds to its relative fitness. -Selection algorithm is applied to the evaluated solutions. The selection favors the fittest among the individuals, which is basic principal of evolution theory.

However, only two of these components are problem dependent: the encoding and the evaluation function.

Selection and Reproduction

Starting from the selection algorithm, the roulette-wheel selection is a typical choice in GA textbooks [START_REF] Goldberg | Genetic algorithms in search, optimization, and machine learning[END_REF]. The probability of selecting an individual to participate in the process of reproduction is proportional to its fitness. This feature captures the main principle of evolution, the survival of the fittest. As we will see in Sect. 3.3, the chromosomes are encoded in a binary form, so we can use some of the simplest, yet effective reproduction operators that can be found in the literature [START_REF] Goldberg | Genetic algorithms in search, optimization, and machine learning[END_REF]. One-point binary crossover randomly combines parents' chromosomes, producing children that inherit most of the genes of their parents, while there is still a probability to create random genes with unknown effect. In order to prevent premature convergence, a mutation operator is used with much less probability e.g. about 5%. Binary mutation involves the random inversion of any bit of a chromosome, destroying its properties.

Evaluation

As already mentioned, individuals are combinations of EbA parameters. The fitness of any combination can be expressed as an accuracy measure of its application on the known projects of an available dataset. Accuracy measures, as defined in [START_REF] Conte | Software Engineering Metrics and Models[END_REF], make use of the Magnitude Relative Error:

MRE = |act -est | act ( 1
)
where act is the project's actual effort, and est is the estimated value produced by applying EbA.

A widely accepted accuracy measure is the Mean MRE (or MMRE). The purpose of the algorithm when using this criterion is to minimize the error. Another accuracy measure that is also considered is Pred(0.25), which computes the number of projects that have been estimated with an MRE of less than 25%. The fitness of an individual is directly proportional to the second criterion. Moreover, the median of MRE values, MdMRE, is also used as it is less likely to be affected by extreme values. Eventually, in our approach these criteria are combined using the following ad-hoc fixed formula:

fitness = -0.4MMRE -0.3MdMRE + 0.3Pred (0 .25 ) (2)
The purpose of the GA is to maximize Equation ( 2) for the projects of some training dataset. A jackknife method is used consisting of the following steps:

1. For each project with known effort that belongs to the database 2. Remove the current project from the database 3. Apply EbA with the selected configuration, in order to produce an estimate 4. Push the project back to its original dataset

The procedure above will be repeated for each one of the individuals of a population, which correspond to different configurations of EbA.

Encoding

We have chosen to encode EbA configuration parameters into binary strings. This is a convenient choice, since we can then apply the simple genetic operators described in Sect. 3.1. Moreover, this choice allows to easily explore a massive search space whose dimensions are essentially of different type.

Application Parameters. The use of one or another parameter for applying EbA should be translated into binary words (i.e. genes). Provided that genes have fixed size, each one should be long enough to store all the possible options for a parameter. The number of bits needed to encode a parameter will be:

bits = ⌈log 2 S⌉ ( 3
)
where S is the number of the possible values of the parameter encoded to the specified gene. In this paper, we have considered three parameters for EbA: the distance metric, the number of analogies, and the analogies' adjustment method. It is straightforward to allocate an appropriate number of bits to represent the possible values for these parameters in a binary string. This policy of encoding is quite flexible in the case we want to examine the effect of more parameters.

Project Attributes. Project attributes can be either numerical or categorical.

In the first case, they are normalized between 0 and 1, in order to neutralize the side-effects of different units. This normalization is described by the type below:

normalized xy = attr xy -min x max x -min x (4)
Where attr xy is the value of the x-th numerical attribute for the y-th project of the dataset, min x is the minimum value observed for the x-th attribute in the current dataset, while max x is respectively the maximum value observed. In the case of categorical attributes, only values selected from a limited set can be assigned. As there is no order imposed among possible values, a '0' indicates that two compared values are the same, while '1' is used when they are different. In this way, the definition of similarity is compatible with that of numerical values.

Encoding of the Attribute Subsets. In the simplest case, an attribute will either participate in distance calculation or not. Just one bit is enough for each attribute indicating its presence in calculations. Finally, we have as many one-bit genes as the maximum of attributes available in the dataset, with each gene corresponding to a certain attribute.

Non-Normalized Weights Encoding (NNWE). Any real number could be applied as weighting factor to an attribute. However, we do not have to consider negative weights, since there is no use in counting the degree of unsuitability. It is also reasonable to allow values only in the range [0, 1). The next step is to choose an appropriate level of accuracy for the weighting factors. Two decimal digits are considered enough to represent all significant variations in attributes' importance. So, the length of each attribute gene will be determined by Equation ( 3). This Non-Normalized Weights Encoding (or NNWE) is used in the majority of the experiments run in Sect. 4. Although it performs well, it is not considered as optimum, due to the existence of weight vectors that have same effect.

An alternative encoding is also proposed, that allows weighting vectors that are linearly independent only. However, NNWE is still preferred. In the next paragraph, there is a detailed description about the need for excluding linearly dependent vectors and new problems that arise.

Normalized Weighting Vector Encoding (NWVE). In general, when applying a weighting vector to a set of attributes, the N -dimensional space defined by these attributes is modified. Weighting vectors that are linearly dependent produce the same space, in a different scale however. This means that distance between any two points will be different in each one of the modified spaces, but the relative position of these points will be the same. Thus, we should use only normalized vectors as candidate solutions, which means that a new representation has to be specified. It is difficult to generate binary words from normalized vectors, as any bit inversion or interchange would probably destroy the unary length property.

Instead, we could take advantage of the fact that all these vectors define an (N -1)-sphere in an N -dimensional space. Attribute weights are normally expressed in Cartesian coordinates. Equations ( 5), which are adapted from [START_REF] Schweizer | Numerical quantum dynamics[END_REF], show the relationship between hyperspherical and Cartesian coordinates in an N dimensional space, such as the one defined by the weights of N attributes.

x 1 = r cos φ 1 x 2 = r sin φ 1 cos φ 2 . . . x n-1 = r sin φ 1 . . . sin φ n-2 cos φ n-1 x n = r sin φ 1 . . . sin φ n-2 sin φ n-1 (5)
Vectors in the hyperspherical system include a radius r and N -1 angles φ i of the vector with each one of the N -1 axes. Since we are interested in the portion of space where all weights are non-negative, we can restrict the range of all N -1 angles to [0, π/2]. Moreover, as far as only normalized vectors are used, radius will always be equal to 1, so it can be considered as a constant. In this way, any combination of N -1 φ i angles represents a vector of unary norm. Each one of them has unique influence in EbA, since linear independence among different individuals is guaranteed. The vector of angles can easily be encoded into binary strings that can be recombined without destroying the vector's unary norm. Each angle corresponds to a gene that consists of a numbers of bits. Therefore, the hyperspherical system is used to encode the attribute weights into genes, while Equation ( 5) is used to transform to Cartesian coordinates to calculate distances.

In this way, there is a unique bit string representation for any weighting vector. However, there is a critical drawback that is derived from the way of computation of Cartesian coordinates. In Equations ( 5), we can see that a weighting factor x k , where 1 ≤ k ≤ n -1, is dependent on k sines or cosines, while x n-1 is dependent on n -1 sines. It is evident that for large values of k, x k tends to be zero, as it is a product of a large set of numbers whose absolute values are smaller than 1.

On the other hand, the existence of few attributes could probably diminish that bias. So, given a dataset described by a small number of attributes, it is worth exploring the possibility of further improvement in estimation accuracy, when using Normalized Weighting Vector Encoding (or NWVE). Hence, we are going to perform experiments for this encoding too. In any case however, NWVE needs to be revised so as to be generally applicable.

Experiments

The experiments are conducted in two phases. In the first phase, the optimization method is applied in Desharnais dataset [START_REF] Desharnais | Analyse statistique de la productivitie des projets informatique a partie de la technique des point des fonction[END_REF]. This is sort of a sanity check of the method, trying to measure the improvement, if any, of EbA after applying a global optimization with GA. In the second phase, the goal is to produce comparative results with other EbA approaches [START_REF] Huang | Optimization of analogy weights by genetic algorithm for software effort estimation[END_REF] [START_REF] Li | Analysis of attribute weighting heuristics for analogy-based software effort estimation method AQUA+[END_REF]. ISBSG is a popular database for project estimation and benchmarking [13], and there is already evidence of the performance of various methods using this dataset. In both cases, the datasets were randomly split into training and validation sets. The 2/3 of each dataset are used for the training phase, which involves applying the GA.

The results presented correspond to the remaining 1/3 of the projects. It is noted that the datasets have been split several times and the results presented are the averages of the different dataset instances. Is it also noted that any project with one or more missing values is excluded from EbA optimization.

Results on Desharnais Dataset

The global optimization method is applied using three different encodings for project attributes, as described in Sect. 3.3. Table 1 summarizes the results of the simple EbA and the three different encodings. The MMRE, MdMRE and Pred(0.25) values presented are the average values out of ten different trials.

The first thing we observe is a significant improvement in all of the evaluation criteria, when comparing the simple EbA with the GA optimized ones. Moreover, the MMRE for NNWE has been further reduced to 44.33%, compared to the 46.18% of Subset Encoding. This is due to the fact that weighting factors provide a more refined way of regulating the influence of each attribute in distance calculations. Finally, NWVE produced the best results in terms of MMRE and MdMRE, 40.67% and 36.8% respectively. This seems to confirm that attribute weights should be handled as normalized vectors. However, as reported in Sect. 3.3, a large number of project attributes would introduce serious bias towards certain attributes. That is the reason why we use NNWE to measure methods efficiency at the sections that follow, as ISBSG dataset makes use of a large number of attributes.

ISBSG Results and Comparison

In this test case, we have adopted the assumption made in AQUA+, including projects with effort between 10000 and 20000, as representatives of medium size projects [START_REF] Li | Analysis of attribute weighting heuristics for analogy-based software effort estimation method AQUA+[END_REF]. Such an assumption is realistic, since it is possible for an experienced manager to define a priori the size of a project in general terms. After eliminating projects with missing values, a total of 65 projects remain in effort range . Table 2 presents the results of AQUA+ for the same estimation range and the best case obtained by attribute weighting by genetic algorithms [START_REF] Huang | Optimization of analogy weights by genetic algorithm for software effort estimation[END_REF]. It is clear that our method outperformed Attribute Weighting GA. Actually, this was expected to happen, since the search has been expanded to parameters that had not been taken into account in the past. It also outperforms by a limited amount AQUA+ MMRE. However, it is important to note that AQUA+ had a higher value for Pred(0.25). It should be noted that AQUA+ used a larger collection of projects as a result of tolerating missing values. In any case, method's efficiency is promising, however the elimination of a number of projects due to missing values seems to be an issue.

Conclusions and Future Work

The purpose of the current work was to explore the unified search space that emerges from the combination of many parameters which are incompatible at first sight. Genetic Algorithms were selected to conduct this search, due to their ability to approach global optima, no matter what the properties of the search space are. However, the key element was the encapsulation of variables that are different in nature, such as the distance metric to be used and the attribute weights, into a single encoding.

Summarizing the results for Desharnais dataset, optimization based on attribute weights outperformed attribute selection. Two different kinds of encoding were used for attribute weights. Both of them resulted in considerable improvement in prediction accuracy, while NWVE seems to be superior to NNWE. This fact supports the hypothesis that there should be a single representation for each weighting vector. However, because of some computational issues, as reported in Sect. 3.3, NWVE is not used in the rest of the experiments in the current paper. Further adjustment for dealing with this problem is subject of future research. Finally, the results in ISBSG dataset seem to support the concept of broadening the search space. By comparing with optimization attempts in earlier researches [START_REF] Huang | Optimization of analogy weights by genetic algorithm for software effort estimation[END_REF][17], evidence was found that the optimum configuration is obtained with combinations of multiple parameters.

The generation of the current experimental data involved distance metrics, analogy numbers, attribute weights and a small set of adjustment methods only. Of course, there are more options than the ones reported. Nevertheless, the encoding adopted can be easily expanded to contain more alternatives for any parameter. Such an expansion demands no change in the rationale of the encoding. An even more extensive search is an interesting subject of future work. Another issue to be looked into is to deal with missing values. Moreover, Equa-tion (2), which was adopted for fitness evaluation, is ad-hoc and needs further investigation.

Table 1 .

 1 Results of Global Optimization approaches in Desharnais dataset

		EbA	Global Optimization with GA
			Subset Encoding	NNWE	NWVE
	MMRE %	73.02	46.18	44.43	40.67
	MdMRE %	48.5	37.14	38.11	36.8
	Pred(0.25) % 24.8	39.2	38.4	38.8

Table 2 .

 2 Results of EbA approaches in ISBSG dataset

		AQUA+ Attribute Weighting GA Global Optimization GA
	MMRE%	26	54	23
	MdMRE%	-	34	23.4
	Pred(0.25)%	72	45	59.4


Dmitry Adamskiy
email: adamskiy@cs.rhul.ac.uk

Ilia Nouretdinov

Andy Mitchell
email: a.p.mitchell@vla.defra.gsi.gov.uk

Nick Coldham
email: n.g.coldham@vla.defra.gsi.gov.uk

Alex Gammerman

Applying Conformal Prediction to the Bovine TB Diagnosing

Keywords: conformal predition, bovine TB, online learning

Conformal prediction is a recently developed flexible method which allows making valid predictions based on almost any underlying classification or regression algorithm. In this paper, conformal prediction technique is applied to the problem of diagnosing Bovine Tuberculosis. Specifically, we apply Nearest-Neighbours Conformal Predictor to the VETNET database in an attempt to allow the increase of the positive prediction rate of the existing Skin Test. Conformal prediction framework allows us to do so while controlling the risk of misclassifying true positives.

Introduction

Bovine Tuberculosis (bTB) is an infectious disease of cattle, caused by the bacterium Mycobacterium bovis (M.bovis). The disease is widespread in certain areas of the UK (particularily South West England) and of major economic importance, costing the UK Government millions of pounds each year, since positive animals are slaughtered and compensation paid to the cattle owners. The main testing tool for diagnosing TB in cows is the Single Intradermal Cervical Tuberculin (SICCT) skin test. The procedure involves administering intradermally both Bovine and Avian Tuberculin PPDs and measuring the thickening of the skin.

Avian tuberculin is used to exclude unspecific reactions so the actual value of the skin test is a difference of thickenings: (B 2 -B 1 ) -(A 2 -A 1 ), where A 1 and B 1 are the initial values of skin thickness measured in millimetres, A 2 and B 2 are skin thickness after the injection of avian and bovine tuberculin respectively.

If the cow is a reactor, in the sense that the test is positive,

(B 2 -B 1 ) -(A 2 -A 1 ) > T
where T is a threshold (usually 3mm), it is slaughtered and the post-mortem examination is performed, which may result in the detection of visible lesions typical of M.bovis. Furthermore, samples for some of the slaughtered cattle are sent for the bacteriological culture analysis.

The data on all the reactors is stored in the VETNET database. The data stored there includes (per reactor) the numeric test results A 1 , A 2 , B 1 , B 2 , and such features as age, herd identifier, date of the test, post-mortem and culture results (if any) and others( [START_REF] Mitchell | [END_REF]).

As there are two tests that can confirm the diagnosis after the cow is slaughtered, the of truly positive cow could be different and here we use logical OR as such (the cow is positive if there are visible lesions or if the culture test was positive). The data in VETNET alone is not enough to judge about the efficiency of the skin test, as the post-mortem tests are not performed for the negative animals. However, it is believed that the positive prediction rate could be improved by taking into account some other factor apart from just the binary result of the skin test.

In this paper we state it as an online learning problem: given the history of the animals tested prior to the current reactor, we try to dislodge, at a given significance level, the hypothesis of this reactor being a real one. In what follows we introduce conformal predictors and describe how conformal predictors could be used for this task.

Conformal prediction

Conformal prediction [START_REF] Vovk | Algorithmic Learning in a Random World[END_REF] is a way of making valid hedged predictions which does not require any assumption other than i.i.d.; the only assumption made is the i.i.d. assumption: the examples are generated from the same probability distribution independently of each other.

Also, it is possible to estimate confidence in the prediction of the given individual example. Detailed explanation of conformal prediction could be found in [START_REF] Vovk | Algorithmic Learning in a Random World[END_REF], here we outline the intuition behind it and the way it is applied to the problem stated.

Online setting implies that the sequence of examples z i = (x i , y i ), z i ∈ Z = (X, Y ) is revealed one by one and at each step after the object x i is revealed the prediction is made. Original conformal prediction algorithm takes as a parameter the function called nonconformity measure and outputs the prediction set Γ . Thus the performance of the conformal predictor is measured in terms of validity and efficiency: how many errors the predictor makes (y i / ∈ Γ i ) and how big is the set Γ i . In case of the classification task it is also possible to output forced point prediction along with the measure of confidence in it.

A nonconformity measure formally is any measurable function taking bag of examples and a new example and returning a number specifying "nonconformity" (strangeness) of a given example to the set. The resulting conformal predictor will be valid no matter what function we choose, however in order to obtain an efficient predictor one should carefully select the reasonable one. Specifically there is a general scheme of defining nonconformity from any given point predictor.

Mondrian conformal predictors

The algorithm 1 is valid in a sense that under the i.i.d. assuption it makes errors independently on each trial with probability less then 1 -γ. However, sometimes we want to define the categories of the examples to have the categorywise validity. For instance, suppose that the examples fall into "easy to predict" and "hard to predict categories", then the overall validity will be reached by conformal predictor, but the individual error rate for "hard to predict" objects could be worse.

In order to overcome this, Mondrian conformal predictor (first presented in [START_REF] Vovk | Modrian Confidence Machine[END_REF]) is used. Here we are interested in label-wise validity, thus we predict it in a most simple form, see Algorithm 2.

Applying conformal prediction to the VETNET database

We used the positively test cows from VEBUS subset of the original VETNET database. It includes 12873 false positives and 18673 true positives. In what follows the words "true positives" and "false positives" will refer to the skin test results.

After the preliminary study, it was discovered that the most relevant atrtibutes for classification are numeric value of skin test result, age and either the ID of the given test which is a herd identifier combined with a test date, or just indentifier of a herd (that may cover several tests performed at different time).

The extract from the VETNET database showing those features is shown in Table 1. The first of these examples is a True Positive (Lesions or Culture test is positive) and the second is a False Positive (both Lesions and Culture tests are negative).

The task is to distinguish between these two classes.

Remind that the goal is to decrease number of cows being slaughtered. This means that we wish to discover as many cows as possible to be False Positives. On the other hand, the number of True Positives misclassified as False Positives should be strictly limited. So unlike standard conformal prediction, the role of two classes is different.

Thus we present a one-sided version of conformal predictor. Each new example is assigned only one p-value, that corresponds to True Positive hypothesis. Then for a selected significance level γ we mark a cow as a False Positive if p < γ. This allows us to set the level at which we tolerate the marking of true positive and we aim to mark as many false positives as possible.

The property of validity is interpreted in the following way: if a cow is True Positive, it is mismarked as a False Positive with probability at most γ. A trivial way to achieve this is to mark any cow with probability γ. So the result of conformal prediction can be considered as efficient only if the percentage of marked False Positives is essentially larger.

In our experiments we used the nonconformity measure presented in algorithm 3 based on k-Nearest-Neighbour algorithm. A possible version of efficient predictor can be done setting k = 50 and using the following distance, which assings the highest importance to comparison of herd IDs, second priority is given to the numerical value (B 2 -B 1 ) -(A 2 -A 1 ) of skin test, and age is used as an additional source of information.

dist(x 1 , x 2 ) = 100S(x 1 , x 2 ) + T (x 1 , x 2 ) + |log 10 (age(x 1 )) -log 10 (age(x 2 ))| where S(x 1 , x 2 ) = 1 if x 1 and x 2 belong to the same herd and 0 otherwise, T (x 1 , x 2 ) is the difference between numerical values of test results on x 1 and x 2 . Thus, first all the animals within given test are considered as neighbours and then all the others. Experiments showed that this distance resulted in the efficient predictor though the validity property holds for other parameters as well. The results on the subset of VETNET database are summarized in the Table 2. The experiment was performed in an online mode with the data sorted by test date (as in real life). The i.i.d. assumption is clearly a simplification here, but as in some other conformal predictor applications(see [START_REF] Nouretdinov | Application of Inductive Confidence Machine to ICMLA Competition Data[END_REF]) we can see that it is not essentially broken and we can see that the validity property holds: the number of marked reactors within true positives is indeed the level that was set. The efficiency could be judged by the number of marked reactors within false positives: at a cost of misclassifying 10% of true positives it is possible to identify almost two thirds of test mistakes.

We can see from the table above that the resulting predictions are valid and efficient. The disadvantage is not taking into account the delay (normally several weeks), needed to perform post mortem analysis. This actually might lead to overestimation of the importance of herd ID as a factor: when a skin test is performed on many cows from same farm same day, it is likely to be either correct or wrong on the most of them.

To perform the experiment more fairly, the online protocol can be replaced with "slow learning" one (described in [START_REF] Ryabko | Online Region Prediction with Real Teachers[END_REF]) where the labels are revealed not immediately, but with the delay. Preliminaty investigation show that herd ID in such case should be replaced with more specific attributes related to the illness history of a herd.

  Input: data examples (x1, y1), (x2, y2), . . . , (x l , y l ) ∈ X × Y Input: a new object x l+1 ∈ X Input: a non-conformity measure A : (zi, {z1, . . . , z l+1 }) → αi on pairs zi ∈ X × Y Input(optional): a significance level γ z1 = (x1, y1), . . . , z l = (x l , y l ) for y ∈ Y do z l+1 = (x l+1 , y) for j in 1, 2, . . . , l + 1 do αj = A(zj, {z1, . . . , z l , z l+1 }) end for p(y) = #{j=1,...,l+1:α j ≥α l+1 } l+1 end for Output(optional): prediction set R γ l+1 = {y : p(y) ≥ 1 -γ} Output: forced prediction ŷl+1 = arg maxy{p(y)} Output: confidence conf (ŷ l+1 ) = 1 -max y =ŷ l+1 {p(y)}

  Input: data examples (x1, y1), (x2, y2), . . . , (x l , y l ) ∈ X × Y Input: a new object x l+1 ∈ X Input: a non-conformity measure A : (zi, {z1, . . . , z l+1 }) → αi on pairs zi ∈ X × Y Input(optional): a significance level γ z1 = (x1, y1), . . . , z l = (x l , y l ) for y ∈ Y do z l+1 = (x l+1 , y) for j in 1, 2, . . . , l + 1 do αj = A(zj, {z1, . . . , z l , z l+1 }) end for p(y) = #{j=1,...,l+1:y j =y,α j ≥α l+1 } |y=y j | end for Output(optional): prediction set R γ l+1 = {y : p(y) ≥ 1 -γ} Output: forced prediction ŷl+1 = arg maxy{p(y)} Output: confidence conf (ŷ l+1 ) = 1 -max y =ŷ l+1 {p(y)}

Algorithm 3 kNN

 3 Nonconromity Measure for VETNET database Input: a bag of data examples z1 = (x1, y1), z2 = (x2, y2), . . . , z l+1 = (x l+1 , y l+1 ) ∈ X × Y Input: an example zi = (xi, yi) from this bag; Input: a distance function d(x1, x2) : X × X → R + A(zi, z1, z2, . . . , z l+1 ) = |{j : xj is amongst k nearest neighbours of xi in x1, . . . , xi-1, xi+1, . . . , x l+1 according to the distance d, and yj = y l+1 }|

Table 1 .

 1 Two entries in VETNET database

	Test time (seconds) CPHH (herd ID) Lesions Culture Age AvRes BovRes
	1188860400	35021001701	1	1	61	4	22
	1218495600	37079003702	0	0	68	1	9

Table 2 .

 2 VETNET results

	Significance Marked reactors Marked reactors
	level	within FP	within TP
	1%	1267/12873	138/18673
	5%	4880/12873	919/18673
	10%	7971/12873	1904/18673

5 Acknowledgements This work was supported in part by funding from the ERASySBio+ Salmonella Host Interactions PRoject European Consortium (SHIPREC) grant; VLA of DEFRA grant on Development and Application of Machine Learning Algorithms for the Analysis of Complex Veterinary Data Sets; EU FP7 grant O-PTM-Biomarkers (2008-2011); and by grant PLHRO/0506/22 (Development of New Conformal Prediction Methods with Applications in Medical Diagnosis) from the Cyprus Research Promotion Foundation.


Xuan Zhang

B John Oommen

Ole-Christoffer Granmo

Generalized Bayesian Pursuit: A Novel Scheme for Multi-Armed Bernoulli Bandit Problems

Keywords: Bandit Problems, Estimator Algorithms, Generalized Bayesian Pursuit Algorithm, Beta Distribution, Conjugate Priors

In the last decades, a myriad of approaches to the multi-armed bandit problem have appeared in several different fields. The current top performing algorithms from the field of Learning Automata reside in the Pursuit family, while UCB-Tuned and the ε-greedy class of algorithms can be seen as state-ofthe-art regret minimizing algorithms. Recently, however, the Bayesian Learning Automaton (BLA) outperformed all of these, and other schemes, in a wide range of experiments. Although seemingly incompatible, in this paper we integrate the foundational learning principles motivating the design of the BLA, with the principles of the so-called Generalized Pursuit algorithm (GPST), leading to the Generalized Bayesian Pursuit algorithm (GBPST). As in the BLA, the estimates are truly Bayesian in nature, however, instead of basing exploration upon direct sampling from the estimates, GBPST explores by means of the arm selection probability vector of GPST. Further, as in the GPST, in the interest of higher rates of learning, a set of arms that are currently perceived as being optimal is pursued to minimize the probability of pursuing a wrong arm. It turns out that GBPST is superior to GPST and that it even performs better than the BLA by controlling the learning speed of GBPST. We thus believe that GBPST constitutes a new avenue of research, in which the performance benefits of the GPST and the BLA are mutually augmented, opening up for improved performance in a number of applications, currently being tested.

Introduction

The multi-armed Bernoulli bandit problem (MABB) is a classical optimization problem that captures the exploration-exploitation dilemma. The MABB setup consists of a gambling machine with multiple arms and an agent that sequentially pulls one of the arms, with each pull resulting in either a reward or a penalty 3 . The sequence of rewards/penalties obtained from each arm i forms a Bernoulli process with an unknown reward probability d i , and a penalty probability 1d i . The dilemma is this: Should the arm that so far seems to provide the highest chance of reward be pulled once more, or should an inferior arm be pulled to learn more about its reward probability? Sticking prematurely with the arm that is presently considered to be the best one, may lead to not discovering which arm is truly optimal. On the other hand, lingering with an inferior arm unnecessarily, postpones the harvest that can be obtained from the optimal arm.

Existing Solutions to Multi-Armed Bernoulli Bandit Problem

Bandit like problems involve two highly related yet distinct fields: the field of Learning Automata and the field of Bandit Playing Algorithms. A myriad of approaches have been proposed within these two fields. Classical exact solutions for discounted rewards take advantage of Gittins Indices [START_REF] Gittins | Bandit processes and dynamic allocation indices[END_REF][START_REF] Gittins | A dynamic allocation index for the discounted multiarmed bandit problem[END_REF][START_REF] Whittle | Multi-armed bandits and the gittins index[END_REF] -by always pulling the arm with the largest Gittins index (measuring the value associated with the state of a stochastic process), the expected amount of discounted rewards obtained is maximized. Calculating Gittins Indices in a computationally efficient manner is far from trivial [START_REF] Varaiya | Extensions of the multiarmed bandit problem[END_REF][START_REF] Katehakis | The multi-armed bandit problem: decomposition and computation[END_REF], and this problem is currently being pursued [START_REF] Sonin | A generalized gittins index for a markov chain and its recursive calculation[END_REF][START_REF] Nino-Mora | A (2/3)n3 fast-pivoting algorithm for the gittins index and optimal stopping of a markov chain[END_REF]. Because of the computational difficulties associated with exact solutions based on Gittins Indices, a number of approximate solution techniques has also been proposed. The ε-greedy strategy, first described by Watkins [START_REF] Watkins | Learning from delayed rewards[END_REF], represents an early approximate solution to the bandit problem, in which the arm so far being perceived as the best is pulled with probability 1 -ε, and a randomly chosen action is pulled with probability ε. Thus, the expected frequency of exploring a random action is determined by the parameter of ε. A variant of ε-greedy strategy is the ε-decreasing strategy [START_REF] Cesa-Bianchi | Finite-time regret bounds for the multiarmed bandit problem[END_REF][START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF], which gradually shifts focus from exploration to exploitation by slowly decreasing ε. Recently, Tokic proposed an adaptive ε-greedy strategy based on reward value differences (VDBE) [START_REF] Tokic | Adaptive ε-greedy exploration in reinforcement learning based on value differences[END_REF]. In this strategy, ε decreases on the basis of changes in the reward value estimates.

Another direction for solving the bandit problem is confidence interval based algorithms. They estimate confidence intervals for the reward probabilities, and identify an "optimistic" reward probability estimate for each arm. The arm with the most optimistic reward probability estimate is then greedily selected [START_REF] Vermorel | Multi-armed bandit algorithms and empirical evaluation[END_REF][START_REF] Kaelbling | Learning in embedded systems[END_REF]. Furthermore, Auer et al. has shown that variants of confidence interval based algorithms, the so-called UCB and UCB-Tuned schemes, provide a logarithmic regret bound [START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF].

There are also algorithms for solving MABB problems that are based on so-called Boltzmann exploration. These introduce the parameter τ as the "temperature" of the exploration. Related schemes include EXP3 [START_REF] Auer | Gambling in a rigged casino: the adversial multi-armed bandit problem[END_REF]. The "Price of Knowledge and Estimated Reward" (POKER) algorithm proposed in [START_REF] Vermorel | Multi-armed bandit algorithms and empirical evaluation[END_REF] takes into consideration pricing of uncertainty, exploiting the arm reward distributions, and the horizon of the problem. The Linear Reward-Inaction (L RI ) learning automaton [START_REF] Narendra | Learning Automat: An Introduction[END_REF] and the Pursuit Scheme based on Linear Reward-Inaction philosophy (PST RI ) [16] [17] are known for their ε-optimality. Besides, PST RI , which uses Maximum Likelihood (ML) reward probability estimates to pursue the currently optimal action, is known for its pioneering role in the estimator Learning Automata family. A thorough comparison of several of the above mentioned schemes can be found in [START_REF] Vermorel | Multi-armed bandit algorithms and empirical evaluation[END_REF][START_REF] Norheim | A generic solution to multi-armed bernoulli bandit problems based on random sampling from sibling conjugate priors[END_REF].

There also exists several algorithms based on Bayesian reasoning [START_REF] Sutton | Reinforcement learning: An introduction[END_REF], with [START_REF] Wyatt | Exploration and inference in learning from reinforcement[END_REF][START_REF] Dearden | Bayesian q-learning[END_REF] being a few examples. In general, Bayesian reasoning is in many cases computational intractable for bandit like problems [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]. However, based on the Thompson sampling principle [START_REF] Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF], the Bayesian Learning Automata (BLA) reported in [START_REF] Norheim | A generic solution to multi-armed bernoulli bandit problems based on random sampling from sibling conjugate priors[END_REF][START_REF] Granmo | Solving two-armed bernoulli bandit problems using a bayesian learning automaton[END_REF] and extended in [START_REF] Granmo | Solving Non-Stationary Bandit Problems by Random Sampling from Sibling Kalman Filters[END_REF] to deal with non-stationary environments, are inherently Bayesian in nature, yet avoids computational intractability by relying simply on updating the hyper-parameters of sibling conjugate distributions, and on simultaneously sampling randomly from the respective posteriors. As seen in [START_REF] Norheim | A generic solution to multi-armed bernoulli bandit problems based on random sampling from sibling conjugate priors[END_REF] and [START_REF] Granmo | Solving Non-Stationary Bandit Problems by Random Sampling from Sibling Kalman Filters[END_REF], BLA demonstrate significant performance advantage compared to a number of competing MABB solution schemes.

Contributions and Paper Organization

In this paper, we propose a new Bayesian algorithm for MABB problems, which we refer to as the Generalized Bayesian Pursuit algorithm (GBPST). GBPST augments the philosophy of BLA with the principles behind the GPST [START_REF] Agache | Generalized pursuit learning schemes: new families of continuous and discretized learning automata[END_REF] and is able to outperform both the GPST as well as the BLA schemes in extensive experiments 4 . This augmentation is achieved as follows: Firstly, as in the BLA, the estimates are truly Bayesian (as opposed to ML in GPST) in nature. However, the arm selection probability vector of GPST is used for exploration purposes. Secondly, as opposed to the ML estimate, which is usually a single value -the one which maximizes the likelihood function -the use of a posterior distribution permits us to choose any one of a spectrum of values in the posterior, as the appropriate estimate. In the interest of being concrete, we have chosen a 95% percentile value of the posterior (instead of the mean) to pursue promising arms. Thirdly, as in the GPST, after each arm pull, all arms currently being associated with a higher reward estimate than the currently pulled arm, are pursued. Finally, the pursuit is done using the Linear Reward-Inaction philosophy, leading to the corresponding GBPST RI scheme 5 . To the best of our knowledge, all these contributions are novel to the field of MABB problem, and we thus believe that the GBPST constitutes a new avenue of research, in which the performance benefits of the GPST and the BLA are mutually augmented. We also believe that the theoretical contributions of this paper could lend itself to practical solutions improving performance in a number of applications, some of which are currently being tested.

The paper is organized as follows. In Section 2 we give an overview of GPST and BLA. Then, in Section 3, we present the new Bayesian estimator algorithm -the Generalized Bayesian Pursuit algorithm -by incorporating GPST and BLA. In Section 4, we provide extensive experimental results demonstrating that the GBPST is truly superior to GPST. The BLA scheme is also outperformed by appropriately choosing a learning speed parameter for the GBPST RI . Finally, in Section 5, we report opportunities for further research, in addition to providing concluding remarks.

Linear Updating Schemes:

The more notable and well-used traditional LA approaches include the family of linear updating schemes, with the Linear Reward-Inaction (L RI ) automaton being designed for stationary environments [START_REF] Narendra | Learning Automat: An Introduction[END_REF]. In short, the L RI maintains an arm selection probability vector p = [p 1 , p 2 , ..., p r ], with r ∑ i=1 p i = 1 and r being the number of arms. The question of which arm is to be pulled is decided randomly by sampling from p. Initially, p is uniform. The following linear updating rules summarize how rewards and penalties affect p with p ′ i and p ′ j being the resulting updated arm selection probabilities:

p ′ j = (1 -λ) × p j , 1 ≤ j ≤ r, j = i p ′ i = 1 -∑ j =i p ′ j if pulling Arm i results in a reward. p ′ j = p j , 1 ≤ j ≤ r if pulling Arm j results in a penalty.
In the above, the parameter λ (0 < λ < 1) governs the learning speed. As seen, after arm i has been pulled, the associated probability p i is increased using the linear updating rule upon receiving a reward, with p j ( j = i) being decreased correspondingly. Note that p is left unchanged upon a penalty.

Pursuit Schemes: A Pursuit scheme (PST) makes the updating of p more goal-directed in the sense that it maintains ML estimates ( d i ) of the reward probabilities (d i ) associated with each arm. In brief, a Pursuit scheme increases the arm selection probability p i associated with the currently largest ML estimate d i , instead of the arm actually producing the reward. Thus, unlike L RI , in which the reward from an inferior arm can cause unsuitable probability updates, in the Pursuit scheme, these rewards will not influence the learning progress in the short term, except by modifying the estimate of the reward vector. This, of course, assumes that the ranking of the ML estimates are correct, which is what it will be if each arm is chosen a "sufficiently large number of times". Accordingly, a Pursuit scheme consistently outperforms the L RI in terms of its rate of convergence.

Generalized Pursuit Schemes:

The Generalized Pursuit schemes (GPST) generalizes PST by allowing several arms to be pursued at the same time. Instead of only pursuing the arm with the highest reward estimate, the whole set of arms that possess higher reward estimates than the arm actually pulled is pursued. In PST, when the arm with the maximum reward estimate is not the one with the highest reward probability, the incorrect arm is pursued, thus potentially derailing the pursuit of the optimal action. The probability of this happening is reduced in GPST.

Bayesian Learning Automata: A unique feature of the Bayesian Learning Automaton (BLA) is its computational simplicity, achieved by relying implicitly on Bayesian reasoning principles. In essence, at the heart of the BLA we find the Beta distribution, which is the conjugate prior for the Bernoulli distribution. Its shape is determined by two positive parameters, denoted by a and b, producing the following probability density function:

f (x; a, b) = x a-1 (1 -x) b-1 1 0 u a-1 (1 -u) b-1 du , x ∈ [0, 1]. (1)
Essentially, the BLA uses the Beta distribution for two purposes. First of all, it is used to provide a Bayesian estimate of the reward probabilities associated with each of the available arms -the latter being valid by virtue of the conjugate prior nature of the Binomial parameter. Secondly, a novel feature of the BLA is that it uses the Beta distribution as the basis for an Order-of-Statistics-based randomized selection mechanism.

The Generalized Bayesian Pursuit Algorithm (GBPST)

Bayesian reasoning is a probabilistic approach to inference which is of significant importance in machine learning because it allows for the quantitative weighting of evidence supporting alternative hypotheses, with the purpose of allowing optimal decisions to be made. Furthermore, it provides a framework for analyzing learning algorithms [START_REF] Mitchell | Machine Learning[END_REF]. We present here a completely new estimator algorithm that builds upon the GPST framework. However, rather than utilizing ML reward probability estimates, optimistic Bayesian estimates are used to pursue the arms currently perceived to be potentially optimal. We thus coin the algorithm Generalized Bayesian Pursuit (GBPST).

As in the case of the BLA, the GBPST estimates the reward probability of each arm based on the Beta distribution. These Bayesian estimates allow us to accurately calculate an optimistic reward probability x i that provides a 95% upper bound for the reward probability of arm i, by means of the respective cumulative distribution F(x i ; a, b).

F(x i ; a, b) = x i 0 v a-1 (1 -v) b-1 dv 1 0 u a-1 (1 -u) b-1 du , x i ∈ [0, 1]. ( 2
)
The following algorithm contains the essence of the GBPST approach.

Algorithm: GBPST RI Parameters: α: The arm chosen by LA.

p i : The i th element of the arm selection probability vector P. λ: The learning speed, where 0 < λ < 1.

a i , b i : The two positive parameters of the Beta distribution.

x i : The i th element of the Bayesian estimate vector X, given by the 95% upper bound of the cumulative distribution function of the corresponding Beta distribution. R: The response from the environment, where R = 0 (reward) or R = 1 (penalty). Initialization:

1. p i (t) = 1/r,
If R(t) = 0 Then a i (t) = a i (t -1) + 1; b i (t) = b i (t -1); Else a i (t) = a i (t -1); b i (t) = b i (t -1) + 1; 3.
Identify the upper 95% reward probability bound of x i (t) for each arm i as:

x i (t) 0 v (a i -1) (1-v) (b i -1) dv 1 0 u (a i -1) (1-u) (b i -1) du = 0.95 4. If M(t)
is the number of arms with higher upper 95% reward probability bound than the pulled arm at time t, update the arm selection probability vector P(t + 1) according to the following rule:

If R(t) = 0 Then p j (t + 1) = (1 -λ)p j (t) + λ M(t) , for ∀ j = i such that x j (t) > x i (t); p j (t + 1) = (1 -λ)p j (t), for ∀ j = i such that x j (t) ≤ x i (t); p i (t + 1) = 1 -∑ j =i
p j (t + 1).

Else P(t + 1) = P(t).

End Algorithm: GBPST RI

Observe that the GBPST is quite similar to the GPST in the sense that both of them pursue the currently perceived potentially optimal arms, and update the arm selection probability vector based on a linear updating rule. The difference is that instead of using ML estimates for the reward probabilities, in the GBPST the estimation is Bayesian, allowing the calculation of 95% upper bounds, {x i }.

It is crucial that the salient features of the GBPST and the BLA are highlighted. The reader should observe that they both rely on the Beta distribution for reward probability estimation. However, the BLA does not perform any Bayesian computations explicitly. Instead, when it comes to arm selection and exploration, the BLA chooses an arm based on sampling directly from the Beta distributions, while the GBPST samples the arm selection space based on the arm selection probability vector. Also, by calculating the 95% upper bound, x i , the GBPST is able to decide which arms are most promising to pursue.

Empirical Results

In this section, we evaluate the computational efficiencies of GBPST RI by comparing it with the GPST RI and the BLA. Although we have conducted numerous experiments using various reward distributions, we report here, for the sake of brevity, results based on the experimental configurations listed in Table 1.

In the experiments considered, Configurations 1 and 4 form the simplest environments, possessing a low reward variance and a large difference between the reward probabilities of the arms. This is because by reducing the difference between the arms, we increase the learning difficulty of the environment. Configurations 2 and 5 achieve this task. The challenge of Configurations 3 and 6 is their high variance combined with the small difference between the arms.

For these configurations, an ensemble of 1,000 independent replications with different random number streams was performed to minimize the variance of the reported results. In each replication, 100, 000 arm pulls were conducted in order to examine both the short term and the limiting performance of the evaluated algorithms.

Since both the two schemes, the GBPST RI and the GPST RI depend on an external parameter λ, we measure performance using a wide range of learning speeds: λ = 0.05, λ = 0.01 and λ = 0.005. We report the best performing learning speeds.

Table 2 reports the average probability of pulling the optimal arm after 10, 100, 1, 000, 10, 000 and 100, 000 rounds of arm pulls, for each configuration. As seen, in Configurations 1, 2 and 4, all three schemes converge to the optimal arm with high ac- In Configuration 3, the GBPST RI outperforms the GPST RI . The BLA learns faster than GBPST RI scheme at the beginning but was caught up with and surpassed by the GBPST RI in the final 10, 000 to 100, 000 rounds.

Configurations 5 and 6 are the two most challenging experimental set-ups, in which the superiority of the GBPST RI over the GPST RI is more obvious than in previous configurations. As compared with the BLA, the GBPST RI are not as fast as the BLA at the beginning, but again outperforms the BLA from around the time index 10,000.

We now consider the so-called Regret of the algorithms. The Regret is the difference between the sum of rewards expected after N successive arm pulls, and what would have been obtained by only pulling the optimal arm. Assuming that a reward amounts to the value (utility) of unity (i.e., 1), and that a penalty possesses the value 0, the Regret can be defined as:

d opt • N - N ∑ i=1 d i , (3)
where d opt is the reward probability of the optimal action and d i is the reward probability of the selected action i.

The Regret offers the advantage that it does not overly emphasize the importance of pulling the best arm. In fact, pulling one of the inferior arms will not necessarily affect the overall amount of rewards obtained in a significant manner if, for instance, the reward probability of the inferior arm is relatively close to the optimal reward probability. For Regret it turns out that the performance characteristics of the algorithms are mainly decided by the reward distributions, and not by the number of arms. Thus, we now consider configuration 4, 5, and 6 only. The plots in Fig. 1 illustrate the accumulation of the Regret of each algorithm with the number of rounds of pulling arms. As seen in Fig. 1(a), early in the learning phase, the BLA is clearly better than the other two schemes, but the GBPST RI and the GPST RI catch up later with the GBPST RI increasing slowly and the GPST RI converging to yield a constant Regret. In the more challenging configurations as shown in Fig. 1(b) and Fig. 1(c), none of the schemes converge to yield a constant Regret because of their low learning accuracy. However, the Regret of the GBPST RI is much lower and increases more slowly than the others, showing its superiority to the other schemes.

From the above results we draw the following conclusions:

1. The GBPST RI is superior to the GPST RI , although the GBPST RI performs slightly worse than GPST RI in the simplest configuration. Furthermore, in the other configurations, the GBPST RI provides much better performance than the GPST RI , suggesting the former's superiority. 2. By tuning the learning parameter λ, the GBPST RI provides better performance compared to the BLA. On the other hand, in several cases, the BLA initially improves performance faster. This difference in behavior can be explained by their respective distinct strategies for pulling arms. The BLA pulls arms based on the magnitude of a random sample drawn from the posterior distribution of the reward estimate, while the GBPST RI chooses arms based on the maintained arm selection probability vector. In fact, with some deeper insight one can see that the initial performance gap can be traced back to the initialization phase of the algorithms, where each arm pulled to provide initial reward estimates.

Conclusion and Further Work

In this paper we have presented the Generalized Bayesian Pursuit Algorithm (GBPST) based on the Reward-Inaction philosophy (GBPST RI ). The GBPST RI maintains an arm selection probability vector that is used for the selection of the arms. However, it Bayesian estimates for the reward probabilities associated with each available arm, and adopts a reward-inaction linear updating rule for arm selection probability updating. Also, because we have used the posterior distributions, we are able to utilize a 95% upper bound of the estimates (instead of the mean) to pursue a set of potentially optimal arms. Thus, to the best of our knowledge, the GBPST is the first MABB solution scheme built according to the GPST strategy that also takes advantage of a Bayesian estimation scheme. Our reported extensive experimental results demonstrate the advantages of the GBPST over the GPST scheme. The GBPST also provides better performance than the BLA by choosing λ suitably.

Based on these results, we thus believe that the GBPST forms a new avenue of research, in which the performance benefits of the GPST and the BLA can be combined. In our further work, we intend to investigate how our Generalized Bayesian Pursuit strategy can be extended to the Discretized Pursuit family of schemes. Besides this, we are currently working on convergence proofs, including the results for games of GBPSTs, involving multiple interacting GBPSTs.

Fig. 1 :

 1 Fig. 1: The Regret for experiment conf. 4, conf. 5 and conf. 6

  where r is the number of arms. 2. Set a i = b i = 1. Then repeat Step 1 and Step 2 in "Method" below a small number of times (i.e., in this paper 10 * r times) to get initial estimates for a i and b i .

	1. Pick α(t) randomly according to arm selection probability vector P(t). Suppose α(t) = α i .
	2. Based on the Bayesian nature of the conjugate distributions, update a i (t) and b i (t)
	according to the response from the environment:
	Method: For t:=1 to N Do

Table 1 :

 1 Bernoulli distributed rewards used in 4-armed and 10-armed bandit problems

	Config./Arm 1	2	3	4	5	6	7	8	9	10
	1	0.90 0.60 0.60 0.60 -	-	-	-	-	-
	2	0.90 0.80 0.80 0.80 -	-	-	-	-	-
	3	0.55 0.45 0.45 0.45 -	-	-	-	-	-
	4	0.90 0.60 0.60 0.60 0.60 0.60 0.60 0.60 0.60 0.60
	5	0.90 0.80 0.80 0.80 0.80 0.80 0.80 0.80 0.80 0.80
	6	0.55 0.45 0.45 0.45 0.45 0.45 0.45 0.45 0.45 0.45

Table 2 :

 2 Probability of pulling the optimal arm after 10, 100, 1000, 10 000, and 100 000 rounds

	Configuration Algorithm	10	100	1000 10000 100000
	Con f .1	GBPST RI 0.05	0.2655 0.5949 0.9438 0.9941 0.9993
		GPST RI 0.05	0.2649 0.5966 0.9437 0.9941 0.9994
		BLA	0.3512 0.7130 0.9540 0.9942 0.9993
	Con f .2	GBPST

RI 0.005 0.2514 0.2869 0.6812 0.9645 0.9963

  the BLA being the fastest scheme. The GBPST RI and the GPST RI perform comparably.

	curacy, with
		GPST RI 0.005	0.2507 0.2844 0.6852 0.9652 0.9956
		BLA	0.2852 0.4583 0.8190 0.9712 0.9960
	Con f .3	GBPST RI 0.01	0.2507 0.2800 0.6312 0.9552 0.9953
		GPST RI 0.005	0.2505 0.2647 0.5387 0.9419 0.9933
		BLA	0.2761 0.3856 0.6942 0.9419 0.9915
	Con f .4	GBPST RI 0.05	0.1027 0.3136 0.8677 0.9854 0.9985
		GPST RI 0.05	0.1035 0.3244 0.8735 0.9862 0.9986
		BLA	0.1407 0.4187 0.8707 0.9826 0.9978
	Con f .5	GBPST RI 0.01	0.0998 0.1204 0.5065 0.9368 0.9924
		GPST RI 0.005	0.0996 0.1106 0.4194 0.9187 0.9819
		BLA	0.1103 0.1870 0.5492 0.9163 0.9878
	Con f .6	GBPST RI 0.005 0.0992 0.1035 0.2357 0.8494 0.9817
		GPST RI 0.005	0.0995 0.1041 0.2596 0.8523 0.9581
		BLA	0.1075 0.1493 0.3572 0.8347 0.9752

Professorship with the Dept. of ICT, University of Agder, Norway.[START_REF] Whittle | Multi-armed bandits and the gittins index[END_REF] A penalty may also be perceived as the absence of a reward. However, we choose to use the term penalty as is customary in the LA and RL literature.

The Generalized Pursuit Algorithm and Bayesian Learning AutomataWe here briefly review the selected schemes upon which the Generalized Bayesian Pursuit scheme builds.[START_REF] Varaiya | Extensions of the multiarmed bandit problem[END_REF] The theoretical results concerning the formal properties of the family of GBPST are currently being compiled.[START_REF] Katehakis | The multi-armed bandit problem: decomposition and computation[END_REF] The pursuit can also be conducted using the Linear Reward-Penalty philosophy (GBPST RP ), as advocated in[START_REF] Oommen | Continuous and discretized pursuit learning schemes: various algorithms and their comparison[END_REF]. In the interest of brevity, we here report the best performing scheme, which is GBPST RI .


Zacharias Voulgaris
email: research@voulgaris.tk

A New Discernibility Metric and Its Application on Pattern Classification and Feature Evaluation

Keywords: Discernibility, Feature Evaluation, Classification Performance, Dataset Evaluation, Information Content, Classification, Pattern Recognition

A novel evaluation metric is introduced, based on the Discernibility concept. This metric, the Distance-based Index of Discernibility (DID) aims to provide an accurate and fast mapping of the classification performance of a feature or a dataset. DID has been successfully implemented in a program which has been applied to a number of datasets, a few artificial features and a typical benchmark dataset. The results appear to be quite promising, verifying the initial hypothesis.

Introduction

The potential of accurate classification of a feature or a set of features has been a topic of interest in the field of pattern classification. Especially in cases where the classification process is a time-consuming or generally impractical process, knowing beforehand how well a classifier will perform on that data can be a very useful insight. The concept of Discernibility aims at exactly that [START_REF] Voulgaris | Discernibility Concept for Classification Problems[END_REF], through its metrics. Yet it was only with the creation of the latest index that this insight can be yielded in a very efficient way, making it a viable alternative for feature evaluation among other applications. For this purpose, a number of artificial features, of different class overlap levels were created. These features, along with a typical machine learning benchmark dataset [2] were applied to four different classifiers as well as the proposed metric.

The rest of the paper is structured as follows. In Section 2, a review of the relevant literature is conducted. This is followed by description of the methodology of the introduced metric (Section 3). In Section 4, the experiments related to the aforementioned datasets are described and a discussion of the results is presented. This is followed by the conclusions along with future avenues of research based on this work (Section 5).

The concept of Discernibility was formally introduced in previous work of the author [START_REF] Voulgaris | Discernibility Concept for Classification Problems[END_REF]. However, this notion has been used even before that, since the idea of class distinguishability has been present in the field of clustering and pattern classification for a while.

In particular, a metric called Silhouette Width [START_REF] Kaufman | Finding groups in data[END_REF] has been a popular choice for measuring this, in the context of clustering. This measure makes use of inter-and intra-class distances, though it only considers the inter-class distance of the closest class. It has been shown in [START_REF] Voulgaris | Discernibility Concept for Classification Problems[END_REF][START_REF] Voulgaris | Choosing a Discernibility Measure for Reject-Option of Individual and Multiple Classifiers[END_REF] that it is outperformed by the Spherical and the Harmonic Indexes of Discernibility, which were developed for this particular task. The latter have been tested in a variety of pattern recognition problems with success.

Another metric that performs this task is the Fisher Discriminant Ratio [START_REF] Fisher | The use of Multiple Measurements in Taxonometric Problems and[END_REF] which makes use of statistical analysis to evaluate the class overlap. The downside of this measure is that, because of its nature, it only works for one-dimensional data (a single feature). Also, while the other metrics yield a value in a bound interval ([-1, 1] for SW and [0, 1] for SID and HID), FDR may yield any positive value, making its output sometimes difficult to incorporate in larger frameworks, or to compare with other metrics. This shortcoming is addressed in the metric introduced in this paper.

Alternative metrics for this task have been proposed in [START_REF] Voulgaris | A Novel Feature Evaluation Methodology for Fault Diagnosis[END_REF], although they share the same drawback as FDR, as they were designed to evaluate a single feature at a time. Although most of them concentrate on measuring the trend of the features in relation to the class vector (something quite significant for Fault Diagnosis applications), one of them focuses on class distinguishability. This metric, the Assumption Free Discriminant Ratio, is basically another version of FDR with the difference that it does not assume any distribution for the data at hand, an approach that is shared by SW, SID and HID as well.

Another metric is that of the Kernel Class Separability method [START_REF] Wang | Learning Kernel Parameters by using Class Separability Measure[END_REF], which has application in feature selection [START_REF] Wang | Feature Selection with Kernel Class Separability[END_REF]. However, this metric this metric is very heavy in terms of parameters, which although they can be fine-tuned, they make this technique quite cumbersome and impractical for real-world problems. In addition, this metric's use in feature selection was tested only using SVMs, a powerful classifier type but a single classifier type nevertheless. Therefore, this metric cannot be considered as a viable alternative for the class separability measurement task, at least not until it is further refined and optimized.

An interesting alternative is presented in [START_REF] Cantú-Paz | Feature Subset Selection, Class Separability, and Genetic Algorithms[END_REF] where a statistical analysis is performed to evaluate the class separability potential of various features. This is very similar to the FDR technique, though more analytical and therefore computationally expensive. This method has the inherent weakness of the statistical approach, namely its limitation to a single-dimensional dataset, rendering it ideal for feature evaluation but inept for anything more complex.

All of the aforementioned metrics, with the exception of FDR, are to some extent computationally expensive when it comes to larger datasets, a drawback that is addressed by the proposed metric, as it will become evident later on.

The idea of the metric introduced in this work is to provide a measure of a dataset's Discernibility using inter-class and intra-class distances for each class, for each class pair combination. This is why the metric is called Distance-based Index of Discernibility (DID). Contrary to the Spherical Index of Discernibility, it does not use hyper-spheres, therefore cutting down the computational cost significantly. In addition, it provides only an overall estimate of the Discernibility of the dataset, avoiding the individual Discernibility scores of the comprising data points. This gives it an edge in the computational cost towards both SID and HID, which base their Discernibility estimate on the individual discernibilities of the patters of the dataset.

DID also has the option of using only a sample of the data points, instead of taking the whole dataset. This allows it to tackle datasets with forbiddingly large sizes, without much loss of accuracy in the Discernibility estimation (as it will be seen in Section 4). If the sample size is omitted in the inputs, the whole dataset is used.

Moreover, the DID metric provides the inter-class Discernibility for each class pair, something that, to the best of the author's knowledge, no other similar measure yields as an output. This is particularly useful as it provides insight to the dataset structure, something essential in datasets which due to their dimensional complexity cannot be viewed graphically.

DID's Discernibility estimate is computed by averaging the various inter-class Discernibility scores. The latter are calculated as follows. First the centers of the various classes are found, by averaging all the data points of each class. For example, in a 2-D feature space, if in class A there are 3 points (x 1 , y 1 ), (x 2 , y 2 ) and (x 3 , y 3 ), the center of class A would be (x A , y A ) = ( (x 1 +x 2 +x 3 )/3, (y 1 +y 2 +y 3 )/3).

Then the radius of each class is then calculated, by taking the largest distance from the center of the class to the various class points. In the previous example, if point 2 is the farthest from the center (x A , y A ), then the radius of class A would be R A = sqrt( (x 2 -x A ) 2 + (y 2 -y A ) 2 ).

Afterwards, a small number is added to all the radii to ensure that there are all nonzero. Then, the sample is divided according to the class proportions and the corresponding amount of data points from each class are selected randomly, for each class. Following that, the distances of these points to each class center are calculated (using the Euclidean distance formula). The ratio of each distance of a pattern of a class i over the radius of the class j is then computed and adjusted so that it does not surpass the value of 1.

Following that, these ratios are added up for each class pair and then divided by the number of patterns used in the calculations. So if due to the class distributions of the dataset the sample used comprise of n patterns in class i and m patterns in class j, the inter-class discernibility of classes i and j (ICD ij ) would be:

m n R dist R dist ICD m j j ij n i i ij ij + + = ∑ ∑ = = 1 1 ) / , 1 min( ) / , 1 min( . ( 1
)
where ICD ij : inter-class disc. of classes i and j dist ij : distance between patterns i and j R i : radius of hypersphere of class i R j : radius of hypersphere of class j n: number of patterns in sample of class i and m: number of patterns in sample of class j Note that the above measure is calculated only for different classes (i ≠ j), for all possible combinations. Moreover, as one would expect, ICD ij = ICD ji . So, in a dataset having 4 classes, 6 class combinations will be taken, yielding 6 inter-class distances.

As mentioned previously, once the inter-class discernibility scores for each class pair have been calculated, their average yields the overall discernibility score for the whole dataset. So, for a 3-class dataset, DID would be equal to (ICD 12 + ICD 13 + ICD 23 ) / 3.

Experiments and Results

Data Description

The data used for this research are a combination of 5 artificial datasets, generated by simple Gaussian distributions, and a benchmark dataset from the UCI machinelearning repository, titled balance.

The artificial datasets were designed to manifest five distinct class overlap levels and are single-dimensional (in essence they are features of various quality levels). These datasets comprised of 3000 data points, divided evenly among three classes, which followed a Gaussian distributions with σ = 1 and various µ's. A typical such dataset is feature3, which exhibits a moderate class overlap, as seen in Fig. 1. The balance dataset was created as part of a cognitive research [START_REF] Siegler | Three Aspects of Cognitive Development[END_REF]

Experiment Setup

A number of experiment rounds over four quite diverse classifiers were carried out. Each round comprised of a 10-fold cross-validation scheme, to ensure an unbiased partitioning of the training and testing sets. The classifiers used were the classic k Nearest Neighbor (using k = 5, which is a popular value for the number of neighbors parameter), the ANFIS neuro-fuzzy system (30 epochs for training), the Linear Discriminant Analysis statistical classifier (LDA) and the C4.5 decision tree. These classifiers were selected because they cover a wide spectrum of classification techniques. Also, in order to ensure more robust results, the number of experiment rounds was set to 30. Most of these classifiers, along with a few others, are thoroughly described in [START_REF] Duda | Pattern Classification[END_REF].

These experiments were conducted for each dataset and afterwards, the Accuracy Rates of the four classifiers were averaged. The end result was an Accuracy Rate for each dataset, reflecting in a way the classification potential of that data. In addition, each dataset was evaluated using the proposed metric, as well as a few other representative measures: SID, HID, FDR and AFDR. Note that the last two metrics were not applied on the balance dataset as they are limited to one-dimensional data. Also, all of the aforementioned measures were applied on the whole datasets, although their outputs are not significantly different when applied on the training sets alone (which constituted 90% of the whole datasets, for each classification experiment).

Another set of experiments was conducted in order to perform a sensitivity analysis of the proposed metric and the sample size used. These experiments constituted of 100 rounds and two of the aforementioned datasets were used.

An additional set of experiments was carried out, this time using only the Discernibility metrics, in order to establish a comparison in terms of computational complexity. These experiments comprised of 100 rounds and all of the aforementioned datasets were used.

Evaluation Criteria

The various outputs of the experiments were evaluated using three evaluation criteria, one for each set of experiments. The relationship between a Discernibility metric with the (average) Accuracy Rate is assessed using the Pearson Correlation (over the six datasets used). For the sensitivity analysis experiments the relative error (in relation to the Discernibility score of the whole dataset) was employed. As for the computational complexity series of experiments, the CPU time measure was used.

Results

The experiments described previously yielded some interesting results that appear to validate the initial aim of acquiring a reliable insight of a dataset's classification potential, in a way that is computationally inexpensive.

As it can observed from the results of the Accuracy Rates experiments (Table 1), the DID metric appears to follow closely the average Accuracy Rate, for the six datasets used. This close relationship can be more clearly viewed in Figure 2. The correlation coefficient was calculated to be an impressive 99.8%, verifying statistically the above observation. In order to ensure that the proposed metric is a viable alternative to the existing measures that opt to accomplish the same task, a comparison was made among them. Since a couple of these metrics cannot be applied in multi-dimensional data, two sets of comparisons were made, one using all datasets and one using only the singledimensional ones (the artificial features created for this research). The results can be viewed in Table 2. As the proposed metric has the option of using a sample of the data points in the dataset it is applied on, it is worthwhile investigating how the size of the sample influences the metric's output. This was done in the second set of experiments, which involved two datasets, the balance one and one of the features (feature3). The output of the metric when it is applied using the whole dataset is taken to be the correct Discernibility score, with which all the other outputs are compared (Table 3). In the third set of experiments the computational cost of the proposed metric, in comparison with the other metrics, is examined. The results of these experiments can be best viewed graphically, as seen in Figure 3 below.

Discussion

It is clear from the aforementioned results that the proposed metric maps quite accurately the (average) Accuracy Rate. This in essence makes it a reliable predictor of a classifier's performance, something can translates into a significant advantage in applications where the classification cost is relatively high. Also, it enables the user to have a better understanding of the dataset before the actual classification, something that may help him/her make a better decision regarding the classifier used. The results of the second series of experiments dictate that the proposed metric is at least as good the other ones, in mapping the Accuracy Rate of the classifiers. Also, in appears to be somewhat better in that aspect, when compared to FDR which has been extensively used in the past for the same purpose.

The results of the sensitivity analysis are quite interesting as they show that the metric's output is not greatly affected by the sample size. As one would expect, the output varies more as the sample becomes smaller, yet the relative error remains quite low (<1%). even at samples of only 1/20th of the original dataset. It is noteworthy that in the case of feature3, where the number of data points is relatively high, the metric's output is quite stable and close to the correct value, even though it varies a bit, as the sample gets smaller.

The computational cost experiments verified the original hypothesis that the proposed metric is an efficient alternative to the other Discernibility measures. When tested on a multi-dimensional dataset against SID and HID, it is clear that it is generally faster. Also, on a single-dimensional data with more data points, the advantage over these two measures is even more evident. It is still not as fast as FDR, but it is significantly faster than AFDR, which is in general a more robust metric than FDR.

Further analysis, using the ROC evalutation criterion for example, could have been performed. However, it is evident from the analysis so far that the proposed metric is adequate regarding the task it undertakes. Besides, a more extensive analysis is beyond the scope of this paper and can be part of a future publication based on further research on the subject.

Conclusions and Future Work

From the research conducted it can be concluded that the proposed method is a robust Discernibility metric, yielding a very high correlation with the average Accuracy Rate over the datasets used in the experiments of this research. Apparently it is not as fast as FDR, yet DID provides a better performance that this metric plus it is applicable on multi-dimensional data as well. Also, it has the option of using a sample of the dataset, without deviating much in its output, even for quite small sample sizes.

Future work on this topic will include more extensive testing of the method, in a larger variety of datasets, as well as use of it in other classification-related applications. Also, ways of making it applicable on the data point level will be investigated, so that it can yield Discernibility scores for the individual patterns of the dataset it is applied on. Finally, ways of making use of the inter-class Discernibility assessments of the various class pairs of a dataset will be also explored.

Fig. 1 .

 1 Fig. 1. Mapping of a typical artificial dataset (feature3).

  and comprises of 3 classes as well. It has 625 points of 4 numeric attributes each. The class distribution is unbalanced (288 points in class 1, 49 points in class 2, and 288 points in class 3). The attributes (which are all integers from 1 to 5) describe the following measures: Left-Weight, Left-Distance, Right-Weight and Right-Distance, of a balance scale tip. This dataset has been used mainly for classification research and has no missing values.

Fig. 3 .

 3 Fig. 3. Computational cost analysis. The calculation time of the Discernibility scores for the various metrics are shown (in sec). Two datasets were used for 100 runs (left = balance, right = feature3). The error bars depict the 95% confidence intervals of the calculation time.

Table 1 .

 1 Experimental results for examining the relationship between classification accuracy and DID scores. The accuracy rate is averaged over all four classifiers used and over all thirty rounds. Relationship between mean Accuracy Rate and DID scores, for all of the datasets tested. It is clear that a vivid (linear) correlation exists.

	Dataset	Mean Accuracy Rate	DID score
	Feature1	0.9998	1.0000
	Feature2	0.9887	0.9921
	Feature3	0.8970	0.8909
	Feature4	0.5354	0.4265
	Feature5	0.3361	0.2468
	Balance	0.8116	0.7599

Table 2 .

 2 Comparison of DID with other Discernibility metrics, based on the (Pearson) correlation with the classification Accuracy Rate, using all 6 datasets and the 5 singledimensional datasets respectively.

	Discernibility	Correlation w. Mean Accuracy Rate
	Metric	All datasets	Only 1-dim datasets
	SID	0.997	0.998
	HID	0.976	0.999
	DID	0.998	0.998
	FDR	-	0.946
	AFDR	-	0.971

Table 3 .

 3 Sensitivity analysis of DID scores, over different sample sizes, for two of the datasets used in the classification experiments. The DID scores were calculated over 100 runs. The original DID scores for the two datasets were 0.7599 and 0.8909 respectively.

	Dataset	Sample size	Mean	St. Dev.	Rel. Error (%)
	Balance	50% 25% 12.5%	0.7593 0.7605 0.7611	0.0060 0.0104 0.0153	0.0734 0.0790 0.1535
		5%	0.7558	0.0211	0.5457
	Feature3	50% 25% 12.5%	0.8911 0.8911 0.8911	0.0018 0.0029 0.0051	0.0197 0.0197 0.0197
		5%	0.8911	0.0076	0.0197