Chenzhe Zhou

Ilia Nouretdinov

Zhiyuan Luo

Dmitry Adamskiy

Luke Randell

Nick Coldham

Alex Gammerman

A Comparison of Venn Machine with Platt's Method in Probabilistic Outputs

Keywords: Venn Machine, Support Vector Machine, Probabilistic Estimation

The main aim of this paper is to compare the results of several methods of prediction with confidence. In particular we compare the results of Venn Machine with Platt's Method of estimating confidence. The results are presented and discussed.

Introduction

There are many machine learning algorithms that allow to make classification and regression estimation. However, many of them suffer from the absence of a confidence measure to assess the risk of error made by an individual prediction.

Sometimes, however, the confidence measure is introduced but very often it is an ad hoc measure. An example of this is a Platt's algorithm developed to estimate confidence for SVM [START_REF] John | Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods[END_REF]. We recently developed a set of new machine learning algorithms [START_REF] Gammerman | Hedging Predictions in Machine Learning (with discussion)[END_REF][START_REF] Vovk | Algorithmic Learning in a Random World[END_REF] that allow not just to make prediction but also to supply this prediction with a measure of confidence. What's more important is that this measure is valid and based on a well-developed algorithmic randomness theory.

The algorithm introduced in this paper is Venn Machine [START_REF] Vovk | Algorithmic Learning in a Random World[END_REF], a method that outputs the prediction with an interval of probability that prediction is correct. What follows is an introduction to Venn Machine and Platt's Method, then description of used data and results of experiments.

Venn Machine

Let us consider a training set consisting of object, x i , and label, y i , as pairs: (x 1 , y 1 ), . . . , (x n-1 , y n-1 ). The possible labels are finite, that is, y ∈ Y. Our task is to predict the label y n for the new object x n and give the estimation of the likelihood that our prediction is correct.

In brief, Venn Machine operates as follows. First, we define a taxonomy that can divide all examples into categories. Then, we try all the possible labels of the new object. In each attempt, we can calculate the frequencies of the labels in the category which the new object falls into. The minimum frequency is called the quality of this column. At last, we output the assumed label with the highest quality among all the columns as our prediction and output the minimum and the maximum frequencies of this column as the interval of the probability that this prediction is correct.

T axonomy (or, more fully, V enn taxonomy) is a function A n , n ∈ N of the space Z (n-1) × Z that divide every example into one of the finite categories τ i , τ i ∈ T. Then we consider z i as the pair (x i , y i ),

τ i = A n ({z 1 , . . . , z i-1 , z i+1 , . . . , z n }, z i ) (1)
We assign z i and z j to the same category if and only if

A n ({z 1 , . . . , z i-1 , z i+1 , . . . , z n }, z i ) = A n ({z 1 , . . . , z j-1 , z j+1 , . . . , z n }, z j ) (2)
Here is an example of a simplest taxonomy based on 1-nearest neighbour (1NN). We assign the category of an example the same to the label of its nearest neighbour based on the distance between two objects (e.g. Euclidean distance).

A n ({z 1 , . . . , z i-1 , z i+1 , . . . , z n }, z i ) = τ i = y j (3)
where j = arg min j=1,...,i-1,i+1,...,n

||x i -x j || (4)
For every attempt (x n , y), of which the category is τ , let p y be the empirical probability distribution of the labels in category τ . After all attempts, we get a K × K matrix P . Let the best column with the highest quality, which is the minimum entry of a column, be j best . j best is our prediction and the interval of the probability that the prediction is correct is [ min i=1,...,K P i,j best , max i=1,...,K P i,j best ] (6)

Platt's Method

Standard Support Vector Machines (SVM) [START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF] only output the value of sign(f (x i )), where f is the decision function. So we can say that SVM is a non-probabilistic binary linear classifier. But in many cases we are more interested in the belief that the label should be +1, that is, the probability P (y = 1|x). Platt introduced a method to estimate posterior probabilities based on the decision function f by fitting a sigmoid for SVM.

P (y = 1|f ) = 1 1 + exp(Af + B) (7)
The best parameter A and B are determined by using maximum likelihood estimation from a training set (f i , y i ). Let us use regularized target probabilities t i as the new training set (f i , t i ) defined as:

t i = N++1 N++2 , if y i = +1 1 N-+2 , if y i = -1 (8)
where N + is the number of positive examples, while N -is the number of negative examples. Then, the parameters A and B are found by minimizing the negative log likelihood of the training data, which is a cross-entropy error function.

-

i (t i log (p i ) + (1 -t i ) log(1 -p i )) -→ min pi (9)
where the solution is

p i = 1 1 + exp(Af i + B) (10)
With parameters A and B we can calculate the posterior probability that the label should be +1 of every example using (10). But in many cases, probability that the prediction is correct is more useful and easy to compare with Venn Machine. In this binary classification problem, one example with the probability p i means its label should be +1 with the likelihood of p i , that is to say, its label should be -1 with the likelihood of 1 -p i . So we use the complementary probability when the probability is less than the optimal threshold (in this paper we set it to 0.5 as explained later).

Data Sets

The data sets we used in this paper is Salmonella mass spectrometry data provided by VLA 3 and Wisconsin Diagnostic Breast Cancer (WDBC) data from UCI.

The aim of the study of Salmonella data is to discriminate Salmonella vaccine strains from wild type field strains of the same serotype. We analysed the set of 50 vaccine strains (Gallivav vaccine strain) and 43 wild type strains. Both vaccine and wild type strains belong to the same serotype Salmonella enteritidis.

Each strain was represented by three spots; each spot produced 3 spot replicates. Therefore, there are 9 replicates per strain. Pre-processing was applied to each replicate and resulted in representation of each mass spectra as a vector of 25 features corresponding to the intensity of most common peaks. The median was later taken for each feature across replicates of the same strain. In the data set, label +1 corresponds to vaccine strains, label -1 to wild type strains. Table 1 shows some quantitive properties of the data set.

In Figure 1, there is a plot of the class-conditional densities p(f |y = ±1) of Salmonella data. The plot shows histograms of the densities of the data set with The second data set is Wisconsin Diagnostic Breast Cancer data. There are ten real-valued features computed for each cell nucleus, resulting in 30 features in the data set. These features are from a digitized image of a fine needle aspirate (FNA) of a breast mass. They describe characteristics of the cell nuclei present in the image. And the diagnosis includes two predicting fields, label +1 corresponding to Benign and label -1 corresponding to Malignant. Data set is linearly separable using all 30 input features. Table 2 shows some quantitive properties of the data set.

Empirical Result

There are two experiments in this paper to compare the performance of Venn Machine with the SVM+sigmoid combination in Platt's Method.

Taxonomy Design

The taxonomy used in both experiments is newly designed and it is based on the decision function the same as Platt's Method.

Let the number of categories K T = |T | and the taxonomy is further referred to as K T -SVM. Then we train an SVM for the whole data {(x 1 , y 1 ), . . . , (x n , y n )} and calculate the decision values for all examples. We put the examples into the same category if the decision values of them are in the same interval which is generated depending on K T .

For an instance, if K T = 8, the intervals can be (-∞, -1.5], (-1.5, -1.0], (-1.0, -0.5], (-0.5, 0], (0, 0.5], (0.5, 1.0], (1.0, 1.5], (1.5, ∞).

Experiments

The first experiment dealing with Salmonella data set is using a radial basis function (i.e. RBF) kernel in SVM and a Venn Machine with 8-SVM taxonomy since Salmonella data is a linearly non-separable data set . And the second experiment dealing with WDBC data set is using a linear kernel in SVM (i.e. Standard SVM) and a Venn Machine with 6-SVM taxonomy. The Venn Machine can be compared to Platt's Method and the raw SVM for accuracies and estimated probabilities. Assuming equal loss for Type I and Type II errors, the optimal threshold for the Platt's Method is P (y = 1|f ) = 0.5. And all of the results in this paper are presented using Leave-One-Out Cross-Validation (LOOCV).

Table 3 shows the parameters setting for experiments. The C value is the cost for the SVM. And the Underlying Algorithm is the algorithm used in the taxonomy for Venn Machine and the kernel used in SVM. The Kernal Parameter is σ, the parameter of RBF.

Table 4 is the results of experiments. The table lists the accuracies and the probabilistic outputs for raw SVM, Platt's Method, and Venn Machine using both data sets. For Platt's Method, the probabilistic output is the average estimated probability that the prediction is correct. And for Venn Machine, the probabilistic output is the average estimated interval of probability that the prediction is correct.

Results

Table 5 lists some comparisons between two methods. As shown in the table, Venn Machine got better results in both two data sets. For Salmonella data set, Venn Machine got a significant improvement (7.52%) comparing with Platt's Method in accuracy when it used a 8-SVM RBF taxonomy. In the aspect of probabilistic outputs, Venn Machine output an interval of probability with the accuracy included while the probabilistic output of Platt's Method is 1.93% higher than the accuracy. For WDBC data set, Venn Machine increased by 0.52% in accuracy while Platt's Method got 0.35%. In the aspect of probabilistic outputs, Venn Machine output an interval of probability with the accuracy included while the probabilistic output of Platt's Method is 1.87% lower than the accuracy.

Sensitivity and specificity are also calculated and shown in Table 5. For Salmonella Data Set, Venn Machine got a outstanding result in sensitivity, 16.00% better than Platt's Method. It is obvious that Venn Machine got a better ability of identity salmonella vaccine. And for WDBC Data Set, they got approximate results in both sensitivity and specificity. It is hard to tell which method is better, but we can still find Venn Machine has made a slight improvement in both aspects.

Another interest thing we observed is that Platt's Method performs better on linearly separable data set (that is WDBC in this paper) than linearly nonseparable data set (that is Salmonella data set), while Venn Machine can achieve good results on both data sets. But it needs conducting experiments on more data sets to prove this. Table 6 shows several examples in Salmonella data set predicted by Venn Machine and Platt's Method. For each example, the table contains the true label, prediction of Venn Machine and intervals of probability that the prediction is correct, the prediction of Platt's Method and the probabilistic outputs. The table indicates that both methods can be proper or erroneous. For instance, wild type strain 2, 4, 5 and vaccine strain 44 are both wrong for the two methods. From our experience on these data sets we see the following. The Platt's estimation for the accuracy of prediction can be too optimistic or too pessimistic, while Venn's bounds estimate it more correctly: two-sided estimation is safer than single one. As for the accuracy itself, we see that if Platt's and Venn Machines are based on the same kind of SVM, accuracy of Venn Machine is also a bit better. This may be because Venn Machine do not rely on a fixed transformation of the SVM output, but makes its own transformation for each taxonomy, based on the actual data set.

We applied different probabilistic approaches to the dataset of Salmonella strains. As it can be seen from Figure 1 and Table 6, this data set is hard to separate: there are few errors in the class +1, but large part of examples from the class -1 seems to be hardly distinguishable from the class +1. This is why in this case we need to have individual assessment of prediction quality: being unable to make a confident prediction on any example, we still can select some of them where our prediction has higher chance to be correct.

The results have been observed on two particular data sets. We plan to conduct experiments on bigger data sets. Another possible direction is to compare Venn Machine and Platt's Method theoretically.

p

  y {y } := |{(x * , y * ) ∈ τ : y * = y }| |τ | (5) this is a probability distribution on Y. The set P n := {p y : y ∈ Y} is the multiprobability predictor consists of K probabilities, where K = |Y |.

  1 wide, derived from Leave-One-Out Cross-Validation. The solid line is p(f |y = +1), while the dot line is p(f |y = -1). What we observed from the plot is that this a linearly non-separable data set.

Fig. 1 .

 1 Fig. 1. The histograms for p(f |y = ±1) for a linear SVM trained on the Salmonella Data Set.

Table 1 .

 1 Salmonella Data Set Features

	Number of	Number of	Number of Positive	Number of Negative
	Instances	Attributes	Examples	Examples

Table 2 .

 2 Wisconsin Diagnostic Breast Cancer Data Set Features

	Number of	Number of	Number of Positive	Number of Negative
	Instances	Attributes	Examples	Examples
	569	30	357	212

Table 3 .

 3 Experimental Parameters

	Data Set	Task	C Underlying Algorithm	Kernal
					Parameter
	Salmonella	SVM	1	RBF	0.05
		Platt's Method 1	RBF	0.05
		Venn Machine	1	8-SVM RBF	0.05
	WDBC	SVM	1	Linear
		Platt's Method 1	Linear
		Venn Machine	1	6-SVM Linear

Table 4 .

 4 Experimental Results

	Data Set	Task	Accuracy Probabilistic Outputs
	Salmonella	SVM	81.72%
		Platt's Method	82.80%	84.77%
		Venn Machine	90.32%	[83.49%, 91.03%]
	WDBC	SVM	97.72%
		Platt's Method	98.07%	96.20%
		Venn Machine	98.24%	[97.22%, 98.27%]

Table 5 .

 5 Comparisons Between Two Methods

	Data Set	Task	Accuracy	Probabilistic	Sensitivity Specificity
				Outputs
	Salmonella Platt's Method	82.80%	84.77%	76.00%	67.44%
		Venn Machine	90.32% [83.49%, 91.03%] 92.00%	67.44%
	WDBC	Platt's Method	98.07%	96.20%	97.52%	99.02%
		Venn Machine	98.24% [97.22%, 98.27%] 97.53%	99.50%

Table 6 .

 6 Prediction for Individual Examples in Salmonella Data Set

	No. True	Prediction	Probabilistic Outputs of	Prediction	Probabilistic
		Label	of VM	VM	of PM	Outputs of PM
	1	-1	-1	[88.89%, 100.00%]	-1	95.65%
	2	-1	+1	[60.00%, 63.33%]	+1	77.72%
	3	-1	-1	[88.89%, 100.00%]	-1	98.49%
	4	-1	+1	[60.00%, 63.33%]	+1	63.98%
	5	-1	+1	[60.00%, 63.33%]	+1	56.57%
	6	-1	-1	[76.19%, 80.95%]	-1	78.57%
	7	-1	-1	[76.19%, 80.95%]	-1	71.69%
	. . . . . .	. . .	. . .	. . .	. . .
	44	+1	-1	[80.95%, 85.71%]	-1	71.92%
	45	+1	+1	[90.00%, 93.33%]	+1	96.91%
	46	+1	+1	[90.00%, 93.33%]	+1	77.96%
	47	+1	+1	[56.67%, 60.00%]	-1	61.81%
	48	+1	+1	[56.67%, 60.00%]	-1	58.43%
	49	+1	+1	[90.00%, 93.33%]	+1	96.15%
	50	+1	+1	[90.00%, 93.33%]	+1	94.12%
	. . . . . .	. . .	. . .	. . .	. . .

Acknowledgements

This work was supported in part by funding from BBSRC for ERASySBio+ Programme: 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.


Alexandros Panteli

Manolis Maragoudakis

A Random Forests Text Transliteration System for Greek Digraphia

Keywords: Greek Language, Transliteration, Data Mining, Random Forests, Non-Deterministic

Greeklish to Greek transcription does undeniably seem to be a challenging task since it cannot be accomplished by directly mapping each Greek character to a corresponding symbol of the Latin alphabet. The ambiguity in the human way of Greeklish writing, since Greeklish users do not follow a standardized way of transliteration makes the process of transcribing Greeklish back to Greek alphabet challenging. Even though a plethora of deterministic approaches for the task at hand exists, this paper presents a nondeterministic, vocabulary-free approach, which produces comparable and even better results, supports argot and other linguistic peculiarities, based on an ensemble classification methodology of Data Mining, namely Random Forests. Using data from real users from a conglomeration of resources such as Blogs, forums, email lists, etc., as well as artificial data from a robust stochastic Greek to Greeklish transcriber, the proposed approach depicts satisfactory outcomes in the range of 91.5%-98.5%, which is comparable to an alternative commercial approach.

Introduction

Greeklish is a term which originates from the words Greek and English, signifying a writing style in which Greek words are written using the Latin alphabet. Other synonyms for Greeklish are Latinoellinika or ASCII Greek. This phenomenon is not only appearing within the Greek domain, it is linguistically identified as Digraphia [START_REF] Dale | Digraphia[END_REF]. Digraphia is either synchronic, in the sense that two writing systems coexist for the same language, or diachronic, meaning that the writing system has changed over time and has finally been replaced by a new one. Examples of digraphia are common in a variety of languages that do not adopt the Latin alphabet or Latin script (e.g. Greek, Serbian, Colloquial Arabic, Chinese, Japanese etc.). Serbian is probably the most noticeable modern instance of synchronic digraphia, in which Serbian texts is found to be written concurrently in the Cyrillic script and in an adapted Latin-based one. Singlish, a word similar to Greeklish refers to an English-based creole used in Singapore which employs transliteration practices, as well as vocabulary modifications and additions from the English language. As a final point, we should mention the case of the Romanian Language, where there has been a full adoption of Latin-based writing style instead of the original Cyrillic one. The same principle is also appearing in the Turkish and other Central Asian countries of the former Soviet Union.

There is a significant amount of research papers that deal with the application and the acceptability of Greeklish as a writing style. The most representative amongst them was introduced by [START_REF] Androutsopoulos | Latin-Greek spelling in e-mail messages: Usage and attitudes[END_REF], in which a sequence of issues is studies such as the degree of penetration of Greeklish in textual resources, the acceptance rate of them, etc. More specifically, some descriptive statistical results mention that 60% of users have been reported to use Greeklish in over 75% of the contexts they submit. In addition, 82% of the users accept Greeklish as an electronic communication tool while 53% consider this style as non-appealing, 24% concern it as a violation or even vandalism of the Greek Language and 46% have reported to face difficulties in the reading of such texts. As regards to the latter, other research works study the reading time for the comprehension of words and sentences written in the Greek and Greeklish texts. The results indicate that the response time is lower when the text is written in Greek (657ms mean value) than when it is written using characters of the Latin alphabet (886ms mean value) [START_REF] Tseliga | On-line processing of Roman-alphabeted Greek: the influence of morphology in the spelling preferences of Greeklish[END_REF].

Although an official prototype has been proposed (ELOT 743:1982 [START_REF] Elot | Greek Organisation of Standardization[END_REF]) and already approved and used by the British council, the majority of users follow empirical styles of Greeklish styles, mainly categorized into four distinct groups:  phonetic transcription. Each letter or combination of letters is mapped into an expression with similar acoustic form.  optical transliteration. Each letter or combination of letter is mapped into an expression that optically resembles the former. For example the Greek letter θ is usually mapped into 8, due to its optical similarity.  keyboard-mapping conversion. in this group, many letters are mapped to Latin ones according to the QWERTY layout of the Greek keyboard. For example, θ is mapped to its corresponding key in the Greek/English keyboard which is u.

Additionally, Greeklish writing suffers from the presence of "iotacism", a phenomenon which is characterized by the use of the Latin character "i" for the transliteration of the Greek symbol sets "ι", "η", "υ", "ει", and "οι" since they are all pronounced as "I" according to the SAMPA phonetic alphabet.

Based on the aforementioned issues, the present work is a Data Mining approach towards an efficient Greeklish-to-Greek transliteration tool, based on a state-of-the-art ensemble classification algorithm of Random Forests. This is, according to our knowledge, the first attempt to this domain in a non-deterministic manner. The use of Greeklish is now considered of an issue of high controversy and it is banned from numerous web sites and forums (e.g. Greek Translation Forum, Athens Wireless Metropolitan Network Forum, etc.). Therefore, a robust and affective transcriber is considered of high importance in order for users not to be excluded from web discussions and other social networking activities.

A lot of work has been done in the field of Greeklish-to-Greek conversion. The most representative approaches including E-Chaos [START_REF]Chaos: freeware Greeklish converter[END_REF], Greeklish Out [START_REF]Greek to Greeklish by Innoetics[END_REF], Greek to Greeklish by Innoetics [START_REF] Chalamandaris | All Greek to me! An automatic Greeklish to Greek transliteration system[END_REF], All Greek to me! [START_REF] Degreeklish | [END_REF] and deGreeklish [9]. The first two approaches are not using a vocabulary and they are mainly based on manual rules, refined by the user and adjustable to include more in the future. The second implementation does not mention its scientific parameters as it is a commercial application, however, the company mention 98% using language models as the core mechanism. The third and fourth approaches are based on a more sophisticated methodology, namely Finite State Automata (FSA), which make the mapping of each letter more straightforward. The latter system is implemented as a web service in PHP and C++ and addresses a novel search strategy in the directed acyclic graph. Note that all of the above approaches use deterministic implementation, either using handcoded rules or FSA, or other user-defined methods.

Random Forests

Nowadays, numerous attempts in constructing ensemble of classifiers towards increasing the performance of the task at hand have been introduced [START_REF] Breiman | Random forests[END_REF]. A plethora of them has portrayed promising results as regards to classification approaches. Examples of such techniques are Adaboost, Bagging and Random Forests. Random Forests are a combination of tree classifiers such that each tree depends on the values of a random vector sampled independently and with the same distribution for all trees in the forest. A Random Forest multi-way classifier Θ(x) consists of a number of trees, with each tree grown using some form of randomization, where x is an input instance [START_REF] Kononenko | Estimating attributes: analysis and extensions of Relief[END_REF]. The leaf nodes of each tree are labeled by estimates of the posterior distribution over the data class labels. Each internal node contains a test that best splits the space of data to be classified. A new, unseen instance is classified by sending it down every tree and aggregating the reached leaf distributions.

Each tree is grown as follows:  If the number of cases in the training set is N, sample N cases at random but with replacement, from the original data. This sample will be the training set for growing the tree.  If there are M input variables, a number m<<M is specified such that at each node, m variables are selected at random out of the M and the best split on these m is used to split the node. The value of m is held constant during the forest growing.  Each tree is grown to the largest extent possible. Therefore, no pruning is applied.

Experimental Design

The training data (a set of Greeklish characters with the corresponding Greek characters) were created using Stochastic Greek2Greeklish Transcriber. For each character a separate instance is created. For the small scale experiments a data set of ~12000 instances was used, these instances were created from some random articles from in.gr The large scale experiments use "OpenThesaurus -Green synonyms thesaurus OpenOffice.org edition" (under GNU general public license), which consists of ~84000 Greek words (with duplicates), this thesaurus combined with the 12000 instance dataset yields a dataset of over 0.7million instances. Using multiples of words produces a model with higher accuracy. This happens because each instance of a word would have a slightly different Greeklish conversion thus creating a better prediction model. The training data is converted to vectors suitable for data mining using the n-grams method. For each pair of Greek, Greeklish characters (e.g. (g,G) ) an k-dimensional vector is created using n preceding characters of the Greek character (g), the Greek character g and m proceeding characters (n+m = k-1). The corresponding supervisory signal is of course the character G.

Using a large k impacts not only the accuracy of the classifier (as explained later) but the training and classification time. For example if a tree based classification algorithm is used the dimensionality of the training data affects the size of the produced tree and the time it takes to build it. Fortunately there are some clues that guided us to choose an optimal vector length (discussed later).

As regards to the creation of instances, before the input data is converted to instances all characters are turned to lowercase, this does not affect in any way the process since the capitalization rules are known. Apart from the change in case, all diaeresis are removed since they are rare and could impact the accuracy more (of all other classes) than not using them. All punctuation marks and whitespace are ignored and will be preserved unaltered. All words are independent from each other in the sense that no instance has characters from more than one word, the value for characters beyond the current word are filled in with the character "*" which represents whitespace. The reasoning behind this is the same with the removal of diaeresis, since words with double word stresses are rare and context dependent and generally word stressing is independent for each word.

A training instance consists of a number of features which represent the next n characters in the word, the previous k characters and the current character. The corresponding class is the Greek character in the same position as the current Greeklish character. Special care has been taken for Greek character pairs (e.g. diphthongs) that are equivalent phonetically to one Latin character.

Experimental Evaluations

Using the dataset as mentioned above, a series of experiments was conducted using WEKA and RapidMiner benchmarks. For reasons of thorough evaluation, we have compared Random Forests (in practice, both implementations, either Random Input or Random Combination Forests proven to behave similarly, with little variation amongst them) against K-Nearest neighbor (IB1 and IB3 respectively), Decision Trees (J48), Naive Bayes (NB) and Bayesian Networks (BN) classification algorithms. The obtained the results are tabulated in the following table: The results shown in the above table are visualized in the following figure (Fig. 1).

Fig. 1.

Results on the set of benchmark algorithms, in terms of prediction accuracy.

The dataset used for the creation of the classifier, as mentioned, consists of about 84000 Greek words (including duplicates). This dataset was obtained by using a window size of [+4-4] to extract the n-grams. Character classes with 1/10 th the number of instances are only 1% more accurate. As shown by a study done by Hatzigeorgiu et al. [START_REF] Hatzigeorgiu | Word length, word frequencies and Zipf"s law in the Greek language[END_REF] the average length of a Greek word is between 6-7 characters, so using a much greater than this number of grams should yield worst results since the data would be sparse (remember that if the length of the word is smaller than the number of features whitespace is added). Our results confirm this by having an accuracy peak at 9 features (considering 3 previous characters and 5 next, plus the current character ([+5-3]). A second observation is that accuracy decreases if the number of characters considered is highly asymmetrical. This is to be expected since instances at the beginning or the end of the word (depending on if more next or previous characters are considered) will have a lot of whitespace, thus resulting in sparse data. The accuracy measurements obtained from the dataset persist when analyzing using the large dataset. Random Forest showed an overall accuracy of over 98%. This percentage of course refers to a single character being classified correctly.

Conclusions

This work dealt with the importance issue of implementing a Greeklish to Greek transliteration tool, which differs from existing approaches in two ways. The former lies to the fact that no vocabulary is used, therefore the proposed approach is robust to slang and other linguistic idioms, while the latter lies to the fact that it is a nondeterministic, Data Mining approach, which could encompass a variety of user"s writing styles and be independent of manually defined, empirical rules. Evaluations against numerous other Data Mining classification approaches have supported our claim that Random Forests (using both of their existing utilizations) are well suited for the task at hand and behave competitive or better that existing deterministic, commercial implementations

Table 1 .

 1 The cell values represent correct prediction percentage using 10 fold cross validation.

				Algorithm
	Window	J48	RF	IB1	IB3	BN	NB
	size
	[+2-2]	87.59 90.25 85.94 84.28 85.03 84.80
	[+2-4]	89.99 92.70 87.12 84.28 86.66 86.13
	[+3-3]	89.90 93.34 88.02 85.11 87.02 86.27
	[+4-2]	87.90 91.20 84.99 82.72 85.51 84.80
	[+2-6]	90.13 92.63 82.76 80.31 86.31 85.85
	[+3-5]	89.96 93.21 85.25 82.49 86.60 85.97
	[+4-4]	90.08	97.4	86.73 83.25 86.75 85.92
	[+5-3]	90.09 98.43 85.79 82.97 87.27 86.22
	[+6-2]	88.18 91.31 81.62 79.71 85.29 84.55
	[+3-6]	90.10 93.14 93.25 81.06 86.42 85.83
	[+5-4]	90.15 93.36 85.25 82.31 86.63 85.95
	[+4-5]	90.01 93.34 85.06 81.90 86.61 85.85
	[+6-3]	90.08 93.31 83.72 81.46 86.84 86.12
	[+5-5]	90.08 93.24 83.98 81.49 86.54 85.72


Meng Yang

Ilia Nouretdunov

Zhiyuan Luo

Alex Garmmerman

Feature Selection by Conformal Predictor

Keywords: feature selection, conformal predictor, confidence estimation

In this work we consider the problem of feature selection in the context of conformal prediction. Unlike many conventional machine learning methods, conformal prediction allows to supply individual predictions with valid measure of confidence. The main idea is to use confidence measures as an indicator of usefulness of different features: we check how many features are enough to reach desirable average level of confidence. The method has been applied to abdominal pain data set. The results are discussed.

Introduction

When we deal with classification or regression problems, the size of the training data and noise in the data may affect the speed and accuracy of the learning system. Are all the features really important or can we use less features to achieve the same or better results? The irrelevant features will induce greater computational cost and may lead to overfitting. For example, in the domain of medical diagnosis, our purpose is to infer the relationship between the symptoms and their corresponding diagnosis. If by mistake we include the patient ID number as one input feature, an over-tuned machine learning process may come to the conclusion that the illness is determined by the ID number.

Feature selection is the process of selecting a subset of features from a given space of features with the intention of meeting one or more of the following goals.

1. Choose the feature subset that maximises the performance of the learning algorithm. 2. Minimise the size of the feature subset without reducing the performance of a learning problem significantly. 3. Reduce the requirement for storage and computational time to classify data.

The feature selection problem has been studied by the statistics and machine learning communities for many years. Many methods have been developed for feature selection and these methods can basically be classified into three groups: filter, wrappers and embedded feature selection [START_REF] Bellotti | Strangeness Minimisation Feature Selection with Confidence Machines[END_REF]2]. The filter method employs a feature ranking function to choose the best features. The ranking function gives a relevance score based on a sequence of examples. Intuitively, the more relevant the feature, the higher its ranking. Either a fixed number of (at most) t features with the highest ranking are selected, or a variable number of features above a preset threshold are selected. Filter methods have been successful in a number of problem domains and are very efficient. Wrapper methods are general-purpose algorithms that searches the space of feature subsets, testing performance of each subset using a learning algorithm. The feature subset that gives the best performance is selected for final use. Some learning algorithms include an embedded feature selection method. Selecting features is then an implicit part of the learning process. This is the case, for example, with decision tree learners like ID3 [START_REF] Quinlan | Induction of decision trees[END_REF] that use an information measure to choose the best features to make a decision about the class label. Other learning algorithms have been developed with embedded feature selection in mind. For example, Littlestone's WINNOW algorithm is an adaptation of the Perceptron algorithm [START_REF] Rosenblatt | The perceptron: a probabilistic model for information storage and organization in the brain[END_REF] that uses multiplicative weight updates instead of additive.

The methods we mentioned above often use accuracy as criterion to select features; in our paper, we consider confidence for the feature selection. This is because in our approach we can regulate the accuracy by choosing a certain confidence level. We will use conformal predictors as a tool to perform feature selection. Conformal predictors are recently developed machine learning algorithms which supply individual predictions with valid measure of confidence [START_REF] Vovk | Algorithmic Learning in a Random World[END_REF]. Level of confidence in predictions produced by such algorithm can used as a performance measure instead of just accuracy [START_REF] Bellotti | Strangeness Minimisation Feature Selection with Confidence Machines[END_REF].

Conformal predictors could be proceed in on-line and batch mode. In batch mode, a fixed size of training set will be used, we may get good results by chance. In on-line mode, the size of training set grows after prediction, it could consider all different sizes of the training set. So we will extend on-line conformal predictors in order to get the average confidence, make feature selection and present results of application of this approach on a medical database.

Conformal Predictor

Conformal predictor is a method that not just makes predictions but also provides corresponding confidences [START_REF] Vovk | Algorithmic Learning in a Random World[END_REF]. When we use this method, we predict labels for new objects and use the degree of conformity to estimate the confidence in the predictions.

We start by defining the concept of a nonconformity measure which is a way of measuring how well an example fits to a set. A measure of fitness is introduced by a nonconformity measure A. For a sequence z 1 , z 2 , ...z n of examples, where the i th example z i is composed of objects and labels, z i = (x i , y i ), x i means objects and y i means label, x i ⊂ X and y i ⊂ Y . We can write ≀z 1 , z 2 , ..., z n ≀ for the bag consisting of the examples z 1 , z 2 , ..., z n , we can score a distance between z i and the bag ≀z 1 , z 2 , ..., z n ≀/z i , expressed by

α i = A(≀z 1 , z 2 , ..., z n ≀/z i , z i ), called the nonconformity score.
Non-conformity score can be based on a classical algorithm of prediction, in this paper we use the nearest neighbors algorithm [START_REF] Shafer | A Tutorial on Conformal Prediction[END_REF]. The idea of using the nearest neighbors algorithm to measure the nonconformity of example z, (x, y), from the other examples is comparing x's distance to other examples' objects with the same label to its distance to others with different label.

α =

distance to z ′ s nearest neighbor to other examples with the same label distance to z ′ s nearest neighbor to other examples with a dif f erent label

Prediction and Confidence

Assume that an i.i.d (independent and identically distributed) data are given: z 1 , z 2 , ...z n-1 . Now, we have an new example x n and want to predict its label y n . First of all, we give y n a value which belongs to Y , then calculate the nonconformity score for each example, finally, compare α n to the other α by using p-value: . If the p-value is small, then z n is nonconforming, if it is large, then z n is very conforming. After we tried every value in Y , each of the possible labels will get a p-value p(y), then the label with the largest p-value will be our prediction and its corresponding confidence will be equal to 1-the second largest p-value.

Validity

In conformal predictor, we also could set a level of significance ϵ to find the prediction region which contains all labels y ⊂ Y with the corresponding pvalue larger than ϵ, that means we will have confidence 1 -ϵ in our prediction about y, and the probability of the event that true label is not contained by prediction region should be ϵ. And we define the situation when the true label is not contained in prediction region as error. Thus, the prediction in on-line mode is under the guarantee and valid.

P rob{pvalue ≤ ϵ} ≤ ϵ

According to this, size of prediction region could be another criterion, for a specific significant level, smaller region sizes provide us more efficient predictions. In this paper, we will use number of uncertain prediction to express this property, and uncertain prediction means the situation when prediction region contains multi-classes.

The confidence corresponds to the minimal level, at which we can guarantee that the prediction is certain (consists of the only label) under i.i.d. assumption. For example, if Y = {1, 2, 3}, and p(1) = 0.23, p(2) = 0.07, p(3) = 0.01 is the results for one of the examples in on-line mode, the prediction is: 1 with confidence 0.93. We can say that true label is 1 or 2 if we wish to be right with probability 0.95, on this level we are not sure that it is 1. On the other hand, if it enough for us to be right with probability 0.90, then we can claim that it is 1. See [START_REF] Vovk | Algorithmic Learning in a Random World[END_REF] for details of conformal (confident) prediction.

We can find that if the prediction is very conforming, its confidence will be very high, the prediction is made depends on the objects of examples, which means the more useful features we use, the higher confidence we will get. So, we could use confidence to justify how useful the features are.

Data Description

We use abdominal pain dataset, it has 9 kinds of diagnosis as labels and 33 types of symptoms as object [START_REF] Gammerman | Bayesian Diagnostic Probabilisties without Assuming Independence of Symptoms[END_REF][START_REF] Papadopoulos | Reliable Diagnosis of Acute Abdominal Pain with Conformal Prediction[END_REF]

Methodology

Our goal is to find the most useful features' set for separating two kinds of diagnosis by using conformal predictors. Firstly, we try to separate the two classes just by one feature. We take all examples from the dataset that belong to one of these two classes and do not contain missing values. Then we process it in on-line mode: prediction for a next example is based using all preceding ones as the training set, and then get the corresponding confidence of the single prediction. To assess performance we calculate average confidence of the examples, and Due to on-line processing, it is averaged over different sizes of the training set.

This was done for each feature, so the feature with the largest average confidence will be the first important feature of useful features' set.

Then we solve in the same way the question: what the second feature can be added to this one in order to maximize average confidence? After deciding this we will have list of two features, then we look for the third feature and so on.

On each step a feature is added to the list of ones being used for prediction, and average confidence grows until adding more features appears not to be useful anymore, the confidence does not change much. The speed of the method is depending on the size of examples and how many m suitable features we want from the full feature set.

Results and Discussion

We choose a typical result for illustration, and you can find more results at appendix. Table 1 shows the order we get when we separate APP (D1) from DYS (D9).

The order of features listed in tables corresponds to stage of including features into the selected set of features. Figure 1 shows us the tendence of confidence average while separate APP(D1) from DYS(D9) when we extend features size till take every feature into account. As we can seen from figure, there are just 102 features, because when we calculate for useful features, some features show same values as equal useful features and we just choose one of them for further steps. The confidences in this picture grows fast at the beginning till meet the peak, 0.97503, and then keep steady for a while, near the end part, it get a slight fall to 0.958. This kind of fall also happens in other separation cases we mentioned above and may cause by the influence from features which are not relevant with this separation.

And, the programme finish its learning process when confidence reached 0.95 with the useful feature size is around 16 out of 135 features and then reach a plateau.

Figure 1 shows that the confidence level is greater than 0.95 when useful features'size is 20, so we will compare the results of using these 20 features with using whole features for separation D1 from D9 by on-line conformal prediction, and significance level ϵ is 0.05. Figure 2 presents the results of using all the features -we have 11 errors, 63 uncertain predictions and 2 empty predictions. Figure 3 shows the prediction results using only 20 selected features. It is clear that the number of prediction errors is reduced to 9 and we just get 42 uncertain predictions and 0 empty prediction. Thus, the selected 20 features give us better prediction results with less errors and more efficient size.

The following Table 2 shows us the comparison of results between full features and selected features in other binary classification subproblems by on-line conformal prediction. Compare with using all features, selected features could give us the same level of accuracy by small size. Because the predictions are under the guarantee, for a specific significant level, the best result is which has the most efficient prediction region. We will find how many features could provide us the best results which have the least uncertain predictions when significance level ϵ is 0.05.

Conclusion

As we can seen from above tables, at beginning, confidences are always low because few features are not enough for accurate predictions. As the number of features growing, the corresponding average confidence increases, and we could get desirable confidences by small number of features . One can then use a significance level in order to decide where to stop adding them. If a plateau is not reached, one can stop when confidence stops to grow, but this would probably mean that the underlying method of computing non-conformity measure was not very appropriate. So, conformal predictor could be an useful way of feature selection.

  |{j=1,...n:αj ≥αn}| n

Fig. 1 .Fig. 2 .Fig. 3 .

 123 Fig. 1. Separate APP(D1) from DYS(D9)

  , which are sex, age, pain-site onset, painsite present, aggravating factors, relieving factors, progress of pain, duration of pain, type of pain, severity, nausea, vomiting, anorexia, indigestion, jaundice, bowel habit, micturition, previous pain, previous surgery, drugs, mood, calor, abdominal movements, abdominal scar, abdominal distension, site of tenderness, rebound, guarding, rigidity, abdominal masses, murphy's test, bowel sounds and rectal examination. Each of symptoms contains different numbers of values, we can give two options for each value, 1 and 0, which means the patient has this value of one symptom or not, separately. After this step, we get 135 features in total. There are around 6000 examples in the original dataset where some of them have missing values, so we use 1153 of them which do not have missing values.

	List of diagnostic groups is below:
		Diagnostic Groups
	Group	Diagnosis	Number of Examples
	D=1	Appendicitis (APP)	126
	D=2	Diverticulitis (DIV)	28
	D=3	Perforates Peptic Ulcer (PPU)	9
	D=4 Non-Specific Abdominal Pain (NAP)	585
	D=5	Cholecystitis (CHO)	53
	D=6	Intestinal Obstruction (INO)	68
	D=7	Pancreatitis (PAN)	11
	D=8	Renal Colic (RCO)	60
	D=9	Dyspepsia (DYS)	173

Table 1 .

 1 Separate APP (D1)from DYS (D9)

	Order	Value	Symptom	Average Confidence
	1	4/2	Pain-site present: right lower quadrant	0.16
	2 24/0 or 24/1	Abdominal scar: present or absent	0.32
	3	5/3	Aggravating factors: food	0.44
	4	6/5	Relieving factors: nil	0.48
	5 14/0 or 14/1 Indigestion: history of indigestion or no history	0.64
	6 27/0 or 27/1	Rebound: present or absent	0.73
	7	9/0	Type of pain: steady	0.81
	8	26/2	Site of tenderness: right lower quadrant	0.86
	9	33/4	Rectal examination: normal	0.88
	10	2/1	Age: 10-19	0.91

Table 2 .

 2 Results Comparison

		full features	selected features		the best results
	subproblem size accuracy uncertain predictions size accuracy size uncertain predictions
	D1-D9 135 0.96	63	17	0.96	30	31
	D2-D9 135 0.98	76	22	0.98	26	30
	D3-D9 135 0.97	41	20	0.97	21	26
	D5-D9 135 0.96	173	17	0.96	40	92
	D6-D9 135 0.97	101	14	0.97	33	40
	D8-D9 135 0.96	69	18	0.96	30	44

Acknowledgements. This work was supported in part by funding from BB-SRC for ERASySBio+ Programme: 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.

Appendix

Table 3 is for separating of classes DIV(D2) and DYS(D9), Table 4 is for CHO(D5)and DYS(D9) and Table 5 is for PPU(D3) and NAP(D4).


S K Tasoulis

C N Doukas
email: doukas@aegean.gr

I Maglogiannis

V P Plagianakos

Independent Component Clustering for Skin Lesions Characterization

Keywords: Pigmented Skin Lesion, Image Analysis, Feature Extraction, Unsupervised clustering, Cluster analysis, Independent Component Analysis, Projection Pursuit, Kernel density estimation

In this paper, we propose a clustering technique for the recognition of pigmented skin lesions in dermatological images. It is known that computer vision-based diagnosis systems have been used aiming mostly at the early detection of skin cancer and more specifically the recognition of malignant melanoma tumor. The feature extraction is performed utilizing digital image processing methods, i.e. segmentation, border detection, color and texture processing. The proposed method combines an already successful clustering technique from the field of projection based clustering with a projection pursuit method. Experimental results show great performance on detecting the skin cancer.

Introduction

Several studies found in literature have proven that the analysis of dermatological images and the quantification of tissue lesion features may be of essential importance in dermatology [START_REF] Maglogiannis | Overview of advanced computer vision systems for skin lesions characterization[END_REF][START_REF] Pariser | Primary care physicians errors in handling cutaneous disorders[END_REF]. The main goal is the early detection of malignant melanoma tumor, which is among the most frequent types of skin cancer, versus other types of non-malignant cutaneous diseases. The interest in melanoma is due to the fact that its incidence has increased faster than that of almost all other cancers and the annual incidence rates have increased on the order of 3 -7% in fair-skinned populations in recent decades [START_REF] Marks | Epidemiology of melanoma[END_REF].

The advanced cutaneous melanoma is still incurable, but when diagnosed at early stages it can be cured without complications. However, the differentiation of early melanoma from other non-malignant pigmented skin lesions is not trivial even for experienced dermatologists. In several cases, primary care physicians underestimate melanoma in its early stage [START_REF] Pariser | Primary care physicians errors in handling cutaneous disorders[END_REF]. To deal with this problem in several cases we utilize data mining methods. In particular, using clustering could be the key step to understand the differences between the types and subtypes of skin lesions.

In this paper, based on an already saucerful clustering technique, we propose a new algorithmic framework for the skin lesion characterization. The paper is organized as follows: in Section 2 we present the image dataset, as well as the preprocessing and segmentation, and feature extraction techniques applied. Next, in Section 4 we present the ICA model. Section 5 is devoted to the proposed method and in Section 6 we investigate the efficiency of the proposed technique. The paper ends with concluding remarks.

Skin Lesions Image Analysis

The image data set used in this study is an extraction of the skin database that exists at the Vienna and the Athens General Hospital, kindly provided by Dr. Ganster. The whole data set consists of 3631 images, 972 of them are displaying nevus (dysplastic skin lesions), 2590 featuring non-dysplastic lesions and the rest 69 images contain malignant melanoma cases. The number of the melanoma images set is not small considering the fact that malignant melanoma cases in a primordial state are very rare. It is very common that many patients arrive at specialized hospitals with partially removed lesions.

The first step in an image analysis workflow is image segmentation, which in this case concerns the separation of the skin lesion from the healthy skin. For the special problem of skin lesion segmentation, mainly region-based segmentation methods are applied [START_REF] Zhang | Border detection on digitized skin tumor image[END_REF][START_REF] Chung | Segmenting skin lesions with partial-differentialequations-based image processing algorithms[END_REF]. A simple approach is thresholding, which is based on the fact that the values of pixels that belong to a skin lesion differ from the values of the background.

In this study, a more sophisticated approach of a local/adaptive thresholding technique was adopted, where the window size, the threshold value and degree of overlap between successive moving windows were the procedure parameters. The details of this method may be found in [START_REF] Maglogiannis | Intelligent Segmentation and Classification of Pigmented Skin Lesions in Dermatological Images[END_REF]. Image analysis and feature extraction is performed by measurements on the pixels that represent a segmented object allowing non-visible features to be computed. Several studies have also proven the efficiency of border shape descriptors for the detection of malignant melanoma on both clinical and computer based evaluation methods [START_REF] Maglogiannis | An integrated computer supported acquisition, handling and characterization system for pigmented skin lesions in dermatological images[END_REF][START_REF] Stoecker | Automatic detection of asymmetry in skin tumors[END_REF]. Three types of features are utilized in this study: Border Features which cover the A and B parts of the ABCD-rule of dermatology, Color Features which correspond to the C rules and Textural Features, which are based on D rules. More specifically the extracted features are as follows:

Border features -Thinness Ratio measures the circularity of the skin lesion defined as:

T R = 4πArea/(perimeter) 2 . -Border Asymmetry is computed as the percent of non-overlapping area after a hypothetical folding of the border around the greatest diameter or the maximum symmetry diameters.

-The variance of the distance of the border lesion points from the centroid location. -Minimum, maximum, average and variance responses of the gradient operator, applied on the intensity image along the lesion border.

Color Features

-Plain RGB color plane average and variance responses for pixels within the lesion. -Intensity, Hue, Saturation Color Space average and variance responses for pixels within the lesion:

I = R+G+B 3 , S = 1 - 3 R+G+B [min(R, G, B)],
and

H =    W , G > B, 2π -W , G < B, 0 , G = B,
and

W = arccos[ R(1 -1 2 (G + B)) (R -G) 2 + (R -B)(G -B) 1 2
].

-Spherical coordinates LAB average and variance responses for pixels within the lesion:

L = √ R 2 + G 2 + B 2 , AngleA = cos -1 [ B L ], and AngleB = cos -1 [ R L sin(AngleA) ].
Texture features -Dissimilarity, d, which is a measure related to contrast using linear increase of weights as one moves away from the GLCM (gray level co-occurrence matrix) diagonal: d = N -1 i,j=0 P i,j i -j , where i and j denote the rows and columns, respectively, N is the total number of rows and columns, and

P i,j = Vi,j N -1 i,j=0
Vi,j is the normalization equation in which V i,j is the DN value of the cell i, j in the image window.

-Angular Second Moment, ASM, which is a measure related to orderliness, where P i,j is used as a weight to itself: ASM = N -1 i,j=0 iP 2 i,j . -GLCM Mean, µ i , which differs from the familiar mean equation in the sense that it denotes the frequency of the occurrence of one pixel value in combination with a certain neighbor pixel value and is given by µ i = N -1 i,j=0 i(P i,j ). For the symmetrical GLCM, holds that µ i = µ j . -GLCM Standard Deviation, σ i , which gives a measure of the dispersion of the values around the mean:

σ i = N -1 i,j=0 P i,j (i -µ i ) 2 .

Clustering Background

The "divisive" hierarchical clustering techniques produce a nested sequence of partitions, with a single, all-inclusive cluster at the top. Starting from this allinclusive cluster the nested sequence of partitions is constructed by iteratively splitting clusters, until a termination criterion is satisfied. Any divisive clustering algorithm can be characterized by the way it chooses to provide answers to the following three questions: Q 1 : Which cluster to split further? Q 2 : How to split the selected cluster? Q 3 : When should the iteration terminate?

The projection based divisive clustering algorithms in particular, projects the high dimensional data onto a lower dimensional subspace to provide answers to the questions above, in a computationally efficient manner. Note also that certain answers to one of these questions may render obsolete one of the others. However, this is not always the case.

To formally describe the manner in which projection based divisive clustering algorithms operate, let us assume the data is represented by an n × a matrix D, whose each row represents a data sample d i , for i = 1, . . . , n. Finally, if A is the matrix with columns the vectors that denote the targeted subspace, then

D P n×k = D n×a A a×k ,
is the projection of the data onto the lower k-dimensional subspace defined by the matrix A. The most studied technique for such data analysis is the Principal Component Analysis (PCA) [START_REF] Jain | Algorithms for clustering data[END_REF]. PCA can be viewed as one of many possible procedures for projection pursuit [START_REF] Huber | Projection Pursuit[END_REF] and is able to compute meaningful projections of high dimensional data [START_REF] Nilsson | Hierarchical Clustering using non-greedy principal direction divisive partitioning[END_REF][START_REF] Boley | Principal direction divisive partitioning[END_REF][START_REF] Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF][START_REF] Tasoulis | Improving principal direction divisive clustering[END_REF].

Independent Component Analysis

Independent component analysis (ICA) [START_REF] Hyvärinen | Independent Component Analysis[END_REF][START_REF] Comon | Independent component analysis, a new concept?[END_REF] is a technique that finds underlying factors or independent components from multivariate (multidimensional) statistical data by maximizing the statistical independence of the estimated components. ICA defines a generative model for the observed multivariate data, which is typically given as a large database of samples. In the model, the data variables are assumed to be linear or nonlinear mixtures of some unknown latent variables, and the mixing system is also unknown. The latent variables are assumed non-gaussian and mutually independent, and they are called the independent components of the observed data. These independent components can be found by ICA. We can define ICA as follows. Let x = (x 1 , ..., x n ) be the random vector that represents the data and s = (s 1 , ..., s n ) be random vector that represents the components. The task is to transform the data x, using a linear static transformation W , as s = W x, into maximally independent components s measured by some function of independence. The definition of independence for ICA that we utilize in this work is the maximization non-gaussianity. The most used measure of non-gaussianity is kurtosis and the second measure is given by negentropy. Kurtosis is zero for a gaussian random variable and nonzero for most non-gaussian random variables. Negentropy is based on the informationtheoretic quantity of (differential) entropy. The entropy of a random variable can be interpreted as the degree of information that the observation of the variable gives. The more random and unstructured the variable is, the larger its entropy.

Relation to Projection Pursuit

The critical attribute of the ICA model is that we can use it to find directions for which the 1-dimensional projected data onto these directions show the least Gaussian distribution. It has been argued by Huber [START_REF] Huber | Projection pursuit[END_REF] and by Jones and Sibson [START_REF] Jones | What is projection pursuit?[END_REF] that the Gaussian distribution is the least interesting one, and that the most interesting directions are those that show the least Gaussian distribution.

Interesting distribution can be a consider a distribution that captures the structure of the data. As such ICA can be considered as an 1-dimensional projection pursuit technique for finding directions of maximum non-gaussianity.

The FastICA Algorithm

To find the direction for maximum non-gaussianity, we utilize a well known fixed point algorithm. The FastICA algorithm [START_REF] Hyvärinen | Fast and robust fixed-point algorithms for independent component analysis[END_REF] is a very efficient method for maximizing the objective function with respect to the selected measure of non-gaussianity. For this task it is assumed that the data is preprocessed by centering and whitening. Whitening can be achieved with principal component analysis or singular value decomposition. Whitening ensures that all dimensions are treated equally, before the algorithm is run. In this work, we only make use of the FastICA algorithm for one unit. The FastICA for one unit finds a direction w such that the projection D P n×k = D n×a w a×1 , maximizes nongaussianity. Nongaussianity is here measured by the approximation of negentropy [START_REF] Hyvärinen | Independent component analysis: algorithms and applications[END_REF].

The Proposed Framework

A new clustering algorithm that was proposed recently [START_REF] Tasoulis | Enhancing Principal Direction Divisive Clustering[END_REF], incorporates information about the true clusters in the data from the density of their projections on the principal components. Based on that principle, we introduce an new algorithmic scheme that utilize the ICA model to find optimal directions to project the data and then splits the data based on the density of their projections on these directions. In contrast to the previous approach, in this work, we choose as a splitting point the maximum of all the local minima of the projections density denoted by x * . Finally, to estimate the ICA model, the FastICA algorithm is utilized. The proposed algorithmic scheme mICDC (refer to Algorithm 1) utilizes the following criteria:

-(Stopping Criterion) ST : Let Π = {{C i , P i }, i = 1, . . . , k} a partition of the data set D into k sets C i , and the assorted projections P i of them onto the direction of maximum nongaussianity. Let X , be the set x * i of the density estimates f (x * i ; h) of the projection P i of the data of each C i ∈ Π, i = 1, . . . , k. Stop the procedure when the set X is empty.

-(Cluster Selection Criterion) CS: Let Π = {{C i , P i }, i = 1, . . . , k} a partition of the data set D into k sets C i , and the assorted projections P i of them onto the direction of maximum nongaussianity. Let F be the set of the density estimates f i = f (x * i ; h) of x * i for the projection P i of the data of each The computational complexity of this approach, using a brute force technique, would be quadratic in the number of samples. However, it has been shown [START_REF] Greengard | The fast gauss transform[END_REF][START_REF] Yang | Improved fast gauss transform and efficient kernel density estimation[END_REF] that using techniques like the Fast Gauss Transform linear running time can be achieved for the Kernel Density Estimation, especially for the one dimensional case. To find the maximum of the minima, we only need to evaluate the density at n positions, in between the projected data points, since those are the only valid splitting points.

C i ∈ Π, i = 1, . . . ,

Experimental Analysis

As defined in Section 2, the image dataset used in our experiments consists of 3631 images; 972 of them are displaying nevus (dysplastic skin lesions), 2590 featuring non-dysplastic lesions, and the rest 69 images contain malignant melanoma cases. The number of the melanoma images is not so small considering the fact that malignant melanoma cases in a primordial state are very rare.

In our first experiment, in an attempt to effectively retrieve the malignant melanoma class, we consider the problem as a two class situation. Since we know beforehand the actual cluster number, we can control the number of clusters that the algorithm retrieves by setting a proper value of the bandwidth parameter for the density function. In [START_REF] Tasoulis | Enhancing Principal Direction Divisive Clustering[END_REF] the bandwidth parameter was set by choosing a multiple of the h opt bandwidth ("normal reference rule"), which is the bandwidth that minimizes the Mean Integrated Squared Error (MISE). This is given by:

h opt = σ 4 3n 1/5 , (1)
where σ is the standard deviation of the data. The starting multiplier value is set to 2 and then we set greater values in an attempt to get good clustering results with fewer clusters. Table 1 reports the clustering results with respect to the multiplier values. 100 experiments have been made for each case and the mean values and the respective standard deviation are presented. To assess the quality of a data partition, additional external information not available to the algorithm, such as class labels, are used [START_REF] Jain | Algorithms for Clustering Data[END_REF][START_REF] Kogan | Introduction to Clustering Large and High-Dimensional Data[END_REF]. Consequently, the degree of correspondence between the resulting clusters and the classes assigned a priori to each object can be measured. For a dataset D, let L be a set of labels l i ∈ L, for each point d i ∈ D, i = 1, . . . , n, with l i taking values in {1, . . . , L}. Let a k-cluster partitioning Π = {C 1 , . . . , . . . , C k }. The purity of Π is defined as:

p(Π) = k j=1 max {|{p i ∈ C j : l i = 1, . . . , L}|} n , (2)
so that 0 ≤ p(Π) ≤ 1. High values indicate that the majority of vectors in each cluster come from the same class, so in essence the partitioning is "pure" with respect to class labels. However, cluster purity does not address the question of whether all members of a given class are included in a single cluster and therefore is expected to increase monotonically with the number of clusters in the result. For this reason, criteria like the V-measure [START_REF] Rosenberg | V-measure: A conditional entropy-based external cluster evaluation measure[END_REF] have been proposed. The V-measure tries to capture cluster homogeneity and completeness, which summarizes a clustering solution's success in including every point of a single class and no others. Again, high values corresponds to better performance. For details on how these are calculated, the interested reader should refer to [START_REF] Rosenberg | V-measure: A conditional entropy-based external cluster evaluation measure[END_REF].

As shown even for the case of a high multiplier value where the algorithm finds very few clusters, the performance remains at high levels. For comparison purposes, we also report the performance of well known k-means algorithm. For the results to be comparable, the number of clusters for the k-means algorithm is set to the values found by the mICDC algorithm. For the computation of k-means, we employ the Matlab function "kmeans".

To better understand the clustering results, firstly we employ the confusion matrices for the 4 cluster case (Table 2). Class 1 refers to the malignant melanoma class and class 2 to the rest of the dataset. As shown in this case, the mICDC algorithm does not split the much bigger class 2; so the rest of the clusters are considered to belong to class 1 (melanoma samples). This is a very important result, since one can easily conclude that the clusters with the much fewer samples constitute the malignant melanoma class. As shown in Table 3, the malignant melanoma class can also be found even when the algorithms retrieves more clusters. In our next experiment, we will perform clustering on the dataset containing only the displaying nevus and the malignant melanoma classes. The lack of samples of the non-dysplastic class makes the projection pursuit problem a bit more difficult, due loss of information. The results are presented in Table 4. In Table 5, we exhibit a high performance case of the mICDC algorithm. In this case the two classes have been perfectly separated and the majority of the displaying nevus samples are at the same cluster. However, there also exists a small cluster that does not belong to the malignant melanoma class.

Conclusions

In this paper, a clustering technique for the recognition of pigmented skin lesions in dermatological images is proposed. The images are preprocessed and feature extraction is performed utilizing digital image processing methods, i.e. segmentation, border detection, color and texture processing. The proposed clustering methodology combines an already successful clustering technique from the field of projection based clustering with a projection pursuit method. The new framework utilizes the ICA model to find optimal projections, and then it incorporates information from the density of the projected data to effectively retrieve the malignant melanoma class. Experimental results show great performance on detecting the skin cancer.

6

  k. The next set to split is C j , with j = arg max i {f i : f i ∈ F}.-(Splitting Criterion) SP C: Let f ′ (x; h ′ ) be the kernel density estimation of the density of the projections p i ∈ P, and x ⋆ the maximum of the minima.Then constructP 1 = {d i ∈ D : p i x ⋆ } and P 2 = {d i ∈ D : p i > x ⋆ }.Get u p the direction of maximum nongaussianity of D 3 Calculate P = Du p the projection of D to u p 4 Set Π = {{D, P }} 5 repeat Select an element {C, P C } ∈ Π using Cluster Selection Criterion CS C 1 }, {C2, P C 2 }}, where P C 1 , P C 2 are the projections of C1, C2 on the direction of maximum nongaussianity u p 1 , u p 2 of C1 and C2, respectively 9 until Stopping Criterion ST is not satisfied ; 10 return Π the partition of D into |Π| clusters

1 Function mICDC (D) 2 7 Split C into two sub-sets C1, C2, using Splitting Criterion SP C 8 Remove {C, P C } from Π and set Π → Π ∪ {{C1, P Algorithm 1: The mICDC algorithm

Table 1 .

 1 Results with respect to the mean clustering purity and V-measure (with the observed standard deviation in parenthesis) for several multiplier values for the full dataset.

			mICDC
	Multi.	Purity	V-measure Clusters
	2	0.9959(0.00) 0.2788(0.07) 9.40(3.06)
	4	0.9974(0.00) 0.6670(0.19) 5.28(2.81)
	8	0.9986(0.00) 0.9005(0.06) 3(0.92)
			K-means
		0.9979(0.00) 0.0673(0.00) 13(0)
		0.9978(0.00) 0.1013(0.00)	7(0)
		0.9878(0.00) 0.0913(0.06)	4(0)

Table 2 .

 2 Confusion Matrices of the mICDC and k-means algorithms for 4 clusters

		mICDC			k-means
		Class 1 Class 2		Class 1 Class 2
	cluster1	0	3558 cluster1	6	2436
	cluster2	62	0	cluster2	62	0
	cluster3	4	0	cluster3	1	884
	cluster4	3	0	cluster4	0	238

Table 3 .

 3 Confusion Matrices of the mICDC algorithm for 7 clusters

			mICDC
		Class 1 Class 2		Class 1 Class 2
	cluster1	5	0	cluster5	5	0
	cluster2	46	0	cluster6	0	3558
	cluster3	6	0	cluster7	3	0
	cluster4	4	0

Table 4 .

 4 Results with respect to the mean clustering purity and V-measure (with the observed standard deviation in parenthesis) for different multiplier values for the dataset containing only nevus and the malignant melanoma classes.

			mICDC
	Multi.	Purity	V-measure Clusters
	2	0.9809 (0.02) 0.3710 (0.23) 7.30 (2.98)
	4	0.9520 (0.02) 0.2490 (0.40) 2.20 (0.63)
			K-means
		0.9908 (0.00) 0.1718 (0.01) 10 (0)
		0.9452 (0.02) 0.1420 (0.02)	3 (0)

Table 5 .

 5 Confusion Matrices of the mICDC algorithm for 7 clusters

			mICDC
		Class 1 Class 2		Class 1 Class 2
	cluster1	55	0	cluster4	6	0
	cluster2	4	0	cluster5	0	52
	cluster3	0	920 cluster6	4	0

Acknowledgments:

The authors thank the European Social Fund (ESF), Operational Program for EPEDVM and particularly the Program Herakleitos II, for financially supporting this work.


Aristeidis Tsitiridis

Peter Wt Yuen

Izzati Ibrahim

Umar Soori

Tong Chen

Hong Kan

Zhengjie Wang

David James

Mark Richardson

Enhanced object recognition in cortex-like machine vision

Keywords: Computer vision, Human vision models, Generic Object recognition, Machine vision, Biological-like vision algorithms

This paper reports an extension of the previous MIT and Caltech's cortex-like machine vision models of Graph-Based Visual Saliency (GBVS) and Feature Hierarchy Library (FHLIB), to remedy some of the undesirable drawbacks in these early models which improve object recognition efficiency. Enhancements in three areas, a) extraction of features from the most salient region of interest (ROI) and their rearrangement in a ranked manner, rather than random extraction over the whole image as in the previous models, b) exploitation of larger patches in the C1 and S2 layers to improve spatial resolutions, c) a more versatile template matching mechanism without the need of ‗pre-storing' physical locations of features as in previous models, have been the main contributions of the present work. The improved model is validated using 3 different types of datasets which shows an average of ~7% better recognition accuracy over the original FHLIB model.

Introduction

After millions of years of evolution visual perception in primates is capable of recognising objects independent of their sizes, positions, orientations, illumination conditions and space projections. Cortex-like machine vision [START_REF] Treisman | A feature-integration theory of attention[END_REF] [2] [3] [4] [START_REF] Riesenhuber | Models of object recognition[END_REF] [START_REF] Serre | Object recognition with features inspired by visual cortex[END_REF], attempts to process image information in a similar manner to that of biological visual perception. This work is different from other studies on human vision models such as [START_REF] Serre | Object recognition with features inspired by visual cortex[END_REF] [7] [START_REF] Wysoski | Fast and adaptive network of spiking neurons for multi-view and pattern recognition[END_REF], in which the features are extracted with a statistical distance based descriptor methodology rather than a biologically inspired saliency approach [START_REF] Zhang | A Hierarchical Object Recognition System Based on Multi-scale Principal Curvature Regions[END_REF]. In Itti's recent biological visual research [START_REF] Elazary | A Bayesian model for efficient visual search and recognition[END_REF] [START_REF] Borji | Scene Classification with a Sparse Set of Salient Regions[END_REF], which utilised a 44-class data set for the scene classification work, the authors reported a slightly inferior performance of the biological inspired C2 feature than the statistical SIFT. However, it is difficult to draw conclusions based on a single dataset and more work is needed to confirm their results. Other models such as Graph-Based Visual Saliency (GBVS) [START_REF] Harel | Graph-Based Visual Saliency[END_REF] and Feature Hierarchy Library (FHLib) [START_REF] Mutch | Object class recognition and localisation using sparse features with limited receptive fields[END_REF], have implemented biological vision in hierarchical layers of processing channels similar to the ventral and dorsal streams of the visual cortex [START_REF] Ungerleider | Two cortical visual systems[END_REF]. In these models the dorsal stream process has been implemented by means of a saliency algorithm to locate the positions of the most -prominent‖ regions of interest for visual attention. To mimic the simple and complex cell operations in the primary visual cortex for object recognitions, the cortex ventral stream process has been commonly presented in alternating layers of simple (S-layers) and complex (Clayers) operations. In the centre of these cortex-like models is the centre-surround operation over different spatial scales (so called image pyramids) of the image in both the dorsal-like and ventral-like processing. Although previous models have achieved rather impressive results using the Caltech 101 data as the test set [START_REF] Mutch | Object class recognition and localisation using sparse features with limited receptive fields[END_REF], additional improvements are needed. Firstly, the previous work [START_REF] Mutch | Object class recognition and localisation using sparse features with limited receptive fields[END_REF] considered datasets where all objects in the images are in the centre of the scene, like that in the Caltech 101 dataset. Secondly, FHLIB has been testified using a single dataset and there is real need to extend the tests using different datasets. Thirdly, the existing model extracts features for the template library in a random manner, which may reduce performance due to the inclusion of non-prominent and/or repeated features. Fourthly, the template matching process itself in FHLIB utilises a pre-stored location of the templates from the training data and then -searches‖ around the vicinity of this location to perform matching. This -blind‖ searching mechanism is neither efficient nor adaptive.

This paper is largely based on MIT and Caltech's work and it addresses the above four points. All enhancements are implemented within the cortex-like FHLIB framework. All codes utilised in this work have been implemented in MATLAB and results are compared with that of the -original‖ FHLIB algorithm which has been recoded in this work, according to paper [START_REF] Mutch | Object class recognition and localisation using sparse features with limited receptive fields[END_REF] and it is referred as MATLAB-FHLIB [MFHLIB]. One main contribution in this work is the incorporation of saliency within the template feature extraction process and this is termed as saliency FHLIB [SFHLIB]. Other enhancements have been the substitution of the computationally expensive Gabor filters for multiple orientations with a single circular Gabor filter, the improvement of the feature representation using larger patches as well as the addition of an extra layer to refine the feature library thereby eliminating redundant patches while at the same time ranking features in the order of significance. The classification in the present paper is achieved through a Support Vector Machine (SVM) classifier using the features extracted in a cortex-like manner similar to the previous work.

Cortex-like vision algorithms 2.1 Graph-Based Visual Saliency (GBVS)

In GBVS the saliency of intrinsic features is obtained without any intentional influence while incorporating a very important characteristic of biological vision, the centre-surround operation. Initially for a digital RGB input image, the algorithm extracts the fundamental features i.e. average intensity over RGB bands, double opponency colour and Gabor filter orientations, and activation maps are formed by using image pyramids across different scales under centre surround operations. The final saliency map that highlights the most prominent regions of interest (ROI) in the image is then constructed from the normalised Markov chains of these activation maps. For more information on GBVS please refer to [START_REF] Harel | Graph-Based Visual Saliency[END_REF].

Feature Hierarchy Library (FHLIB)

FHLIB is an unsupervised generic object recognition model which consists of five layers. Their operations follow the early discoveries of simple and complex cells in the primary visual cortex [START_REF] Hubel | Receptive fields and functional architecture of monkey striate cortex[END_REF] and alternate in order to simulate the unsupervised behaviour of the ventral stream as it propagates visual data up to higher cortical layers. FHLIB's layers are the input image layer, Gabor filter (S1) layer, Local invariance (C1) layer, Intermediate feature (S2) layer, Global invariance (C2) layer. S2 patches are stored in a common featurebook during the training phase and used as templates to be matched against testing images. The stored C2 vectors from the training phase can be compared against the C2 vectors of a given test image, for example by means of a linear classifier such as a Support Vector Machine (SVM). In addition, FHLIB introduced further modifications with respect to previous biologically inspired vision models to improve performance such as the sparsification of S2 units, inhibition of S1/C1 units and limitation of position/scale invariance in S2 units. For more information on FHLIB please refer to [START_REF] Mutch | Object class recognition and localisation using sparse features with limited receptive fields[END_REF]. 3 The Cranfield University algorithm (SFHLIB)

Feature extractions from a salient Region Of Interest (ROI)

Unless there is a task in which even the most refined features are required to distinguish subtle differences or similarities between objects (often of the same category) then retaining all visual information is computationally expensive and unnecessary. Currently in FHLIB, there is no specific pattern by which features are extracted and the selection process of both feature size and locations occurs randomly across input images. Moreover, it becomes difficult to estimate the number of features or feature sizes ideally required. Solving this problem by introducing a geometric memory in the algorithm (section 2.2) i.e. storing the location coordinates from which an S2 template was found so that a respective area in a testing image is compared, led to the conclusion that such a system becomes specialised in recognising objects in similar locations [START_REF] Tsitiridis | An improved cortex-like neuromorphic system for target recognitions[END_REF]. This however is impractical for real-world situations since objects may appear at other locations or may become differently orientated and so the algorithm must generically overcome this problem.

By applying the GBVS model on a particular object points to salient areas and evaluates an activation map according to priority of attention. For objects of the same category the most prominent areas are nearly the same and thus condensation of structured objects can be achieved (figure 2). We use the orientation feature only and rank salient areas of a certain circumference around the highest values. These areas effectively represent the local features which can be used along with more global shape areas (i.e. larger types of features extracted freely from any point in the image) and can be combined for the recognition stage. Fig. 2. Two images of cars. Top row shows the original images and second row their saliency maps using GBVS (12 Gabor angles). Highest attention accumulates on the areas of the wheels which is a common saliency feature and it is evident that saliency can effectively ignore background information. Third row shows the effect of accurate feature extraction via salience in a C1 layer map. Rectangular boxes illustrate the feature templates of varying sizes. Extraction occurs in FHLIB (centre) -blindly‖ while in C1 map from SFHLIB (right) patches are extracted from the salient ROI.

Higher resolution, patch sizes and Circular Gabor filters

Salient areas can be very specific to small regions of an image. At low resolutions spatial information is also low and therefore extractions yield to incoherent representations of the object. To overcome this problem and to improve spatial representation, the resolution of images has to be increased. At the same time, in order to maintain the spectrum of patch sizes required to store suitable features the patch sizes have to be enlarged. To tackle these issues, we increase the size of the short edge of an image to 240 pixels (thus preserving the aspect ratio) and include S2 feature patches of size 20x20 and 24x24. The use of Gabor filter banks in object recognition simulates the tuning of V1 simple cell at different orientations (θ) well and highlights their role in bottom-up mechanisms of the brain. However, constructing S1 responses for different orientations requires the creation of an equal amount of Gabor pyramids for each orientation which is computationally expensive and time consuming as the number of orientations increases to improve an object's description. To eliminate this, we generalise the S1 responses by varying the sinusoid across all orientations which then becomes circular symmetric [START_REF] Zhang | Invariant Texture Segmentation Via Circular Gabor Filters[END_REF]. Using this single circular Gabor filter, one S1 pyramid is obtained and at the same time FHLib's sparsifying step over orientations (section 2.2) become redundant and are removed. The circular Gabor filter is given below:

                  2 2 2 exp 2 2σ ) 2 Y 2 (X exp y) G(x, Y X  (1)
Note that in equation 1, θ and γ are no longer parameters for this equation and this equation now only depends on σ and λ.

Adding S3 and C3 layers

At the object recognition part, when training template patches are extracted randomly from salient ROI, it is inevitable to have patches extracted more than once from the same location and scale, especially as the required total number of training patches is increased. Furthermore, there is no refinement mechanism currently in FHLIB that evaluates the extracted patches' performance and as such the algorithm may store patches that do not explicitly and accurately represent each class. In FHLIB, a refinement was made at the classification stage [START_REF] Mutch | Object class recognition and localisation using sparse features with limited receptive fields[END_REF], however it is a post-processing, non-biological and time consuming remedy.

We address both aforementioned issues by introducing two more layers, namely S3 and C3. In the S3 layer, all patches of a particular class are directly grouped together from the S2 featurebook (section 2.2) and are organised according to their extraction sequence. The algorithm continues by extracting the training C2 vectors (as in FHLIB) which are again grouped so that the responses of every patch from each class across all images now exist together. By examining the C2 responses of each patch for every class on objects of the same class, e.g. if the class was ‗bikes' and a patch was extracted from one of its images then C2 responses for this patch from all images portraying bikes are grouped together. Patches that have yielded identical C2 responses (in practice C2 vectors are float numbers and identical responses can only be obtained from identical patches) are dropped and only one unique patch is retained therefore eliminating co-occurrences. We remember the origin of the retained C2 vectors and refine the S3 featurebook accordingly.

Additionally, the performance of each patch can be measured for every class against objects of the same category to deduce to sampled patches that best describe that class. By summing the C2 responses for every patch we rank the S3 patches from high to low (high showing patches that are most commonly found for a particular object, low showing less generalisation and thus uncommon patches that do not exist across all images). At this point, a percentage number is introduced i.e. the amount of patches to be retained and for example, setting it to a certain value means that the featurebook is reduced by a percentage and the patches retained maximally express the trained classes. The final version of the significantly reduced S3 featurebook refined from co-occurences and uncommon patches, is used over the training images to create C3 vectors which in turn are used to train the SVM classifier. Similarly, at the testing phase, the stored S3 featurebook is used over the testing images and their C3 responses are compared against the trained C3 vectors.

Experiments

Image Datasets

Three image datasets were used, the Cranfield University Uncluttered Dataset (CUUD), the Cranfield University Cluttered Dataset (CUCD) and the Caltech 101. CUUD consists of four categories of vehicle images that were collected from the internet and are namely airplanes, bikes, cars and tanks. Each image contains only a particular vehicle without any clutter or obscurances (figure 3a). The images are of varying aspect ratios and their resolutions are always higher than a minimum of 240 pixels for their shortest edge. Objects are in varying directions and portray some variation in spatial position. Naturally, we have separated the dataset into different training and testing images.

CUCD has also been partly assembled from the internet and in part from our own image database. All images in the dataset contain background clutter and belong to four categories background, bikes, cars, and people. The background category shows a great variability of information, i.e. buildings, roads, trees etc. The people's category is the only category of non-rigid objects and therefore within this category pose and position vary significantly. Another difference with respect to CUUD is that in an image there may be more than one object (of the same category) present. Similarly to CUUD, the images are of varying aspect ratios and their resolutions are always higher than a minimum of 240 pixels for their shortest edge (figure 3b). The multiclass image dataset Caltech 101 [START_REF] Fei-Fei | Learning generative models from few training examples: an incremental bayesian approach tested on 101 object cagories[END_REF] consists of 101 different object categories including one for backgrounds. A total of 9197 images on various spatial poses include unobstructed objects mostly centred in the foreground with both cluttered and uncluttered background environments. All images have been taken at different aspect ratios and are always higher than a minimum of 200 pixels for their shortest edge.

Experiments Setup

In this work, we directly use GBVS MATLAB code with some modifications while all code regarding the recognition part of the algorithm has been inspired from [START_REF] Mutch | Object class recognition and localisation using sparse features with limited receptive fields[END_REF] but otherwise created from the authors .

The algorithm is first tested with FHLIB-like parameterisation, 140 pixels for the images' short edge and 4 different size patches (4x4, 8x8, 12x12, 16x16), 11x11 Gabor filter banks while a sliding window approach was used to extract the maximum C2 responses across the entire image. At this point, the Gabor filters consist of 12 banks i.e. one per orientation angle. Subsequently, we enhance this algorithm with our improvements gradually by introducing a higher resolution for each image (240 pixels, short edge) and adding two more patch sizes 20x20 and 24x24. We then attach our feature extraction method using saliency and also substitute the 12 Gabor filters with one circular Gabor filter. Finally, the S3 and C3 layers are in turn embedded.

Efficient and fast biological-like detection and object recognition requires parallel execution. For our experiments, we concentrate on the results and use a sequential approach in order to prepare the saliency maps of both training and testing images of our dataset beforehand.

Each saliency map from GBVS matches the size of the original image that is later used in object recognition exactly i.e. 240 pixels for the shortest edge, and the only feature used is orientation at 12 Gabor angles spanning from 0 to π. For all experiments during training, we choose an abundant number of features (10000) to avoid underrepresentation of objects and Gabor filter parameters γ, σ and λ are all fixed according to [START_REF] Mutch | Object class recognition and localisation using sparse features with limited receptive fields[END_REF]. For datasets CUUD and CUCD, 50 different images for each class were chosen for training and another 50 per class for training. For the Caltech dataset, we use 15 per class for training and 15 per class for testing. Classification accuracies are obtained as an average of 3 independent runs for all experiments. Finally, all classification experiments were conducted using an SVM classifier using one-against-one decomposition.

Results -Discussion

MFHLIB is the foundation upon which all improvements of this work are established. It extracts the maximum responses by using a sliding window approach which is overall inefficient, time-consuming and as table 1 shows the least accurate. Salience FHLIB (SFHLIB) on other hand illustrates higher performance and robust behaviour. 1. Average percentage classification accuracies over 3 independent runs for the three datasets. Note that descending order algorithms in the left column include the enhancements of the previous algorithms. All results typically vary at ±1.5% (see our discussion for more detail).

From table 1, the results portray for all enhancements a gradual improvement over both the accuracy itself and time. CUUD being uncluttered, presents minimal difficulty for an algorithm and classification accuracies were overall the highest. Under this dataset, a 6% percentage improvement was observed between MFHLIB and SFHLIB variants (excluding SFHLIB with 100% features).

A higher difference between the MFHLIB and our enhancements was noticed in CUCD. In this dataset even though the number of classes remains the same, the added background information and more complicated poses, affect the performance of all algorithms, particularly in MFHLIB. As a first step by increasing the resolution and tampering the number and size of patches has increased performance by 6% and a total of 10% better performance was achieved by using SFHLIB with circular Gabor filters. A drop of nearly 10% for MFHLIB between CUUD and CUCD signifies its inefficiency as a dataset becomes more realistic. A decrease in performance (4.5%) can be also observed for SFHLIB though it is almost half compared with MFHLIB.

Experiments with the benchmark Caltech 101 dataset have revealed a decrease in performance with respect to the other two datasets which was primarily caused by the large number of classes and different setup. However, within this set of experiments an incremental difference between FHLIB and SFHLIB is apparent.

Classification accuracies for S3/C3 layers show that although for the cluttered datasets an improvement can be claimed the trend is not followed in CUUD. A major difference between previous variants of the code is that the number of features required to achieve this performance was lower and thus computationally cheaper. Having selected a fixed number of features (10000) for the library, by running the S3/C3 on the CUUD, reductions of an average of 15% were observed for a 100% of the features used. Similarly for the CUCD, the average percentage of identical feature discards reached 22% and for the Caltech dataset 10%. The difference of this percentage between the three datasets can be explained by the larger number of images used in the Caltech data. The same total number of features corresponds to fewer features per image thus reducing the probability of identical patches extracted randomly across salient regions. Discarding identical features improves time (by approximately the same percentage) and computational requirements.

Conclusions

Following the basic cortex-like machine vision models of FHLIB and GBVS, the contribution here has been to enhance object recognition performances in these early models by incorporating the visual saliency into the ventral stream process. The SFHLIB version being a fusion of salience and recognition, has achieved ~6% classification accuracy for the CUUD, 10% for the CUCD and 4.5% for the Caltech dataset better than that of the MFHLIB model. The present work has also highlighted the need of an efficient feature extraction method from the dataset and further alterations on the mechanism of the algorithm revealed the significance of refining the extracted features to improve the integrity of the feature library itself. It has been also found that the computational time of the proposed SFHLIB is faster by a significant percentage than the MFHLIB.

It is planned to use more extensive datasets to verify the newly developed SFHLIB algorithm against its portability and adaptability. Moreover, it is planned to employ a pulsed (spiking) neural network to replace the SVM classifier for object classification in the near future.

Fig. 1 .

 1 Fig.1. FHLIB's architecture by forming a pyramid of various resolutions of the image, followed by tuning the Gabor features in the S layers and max-pooling across the adjacent C layers in the pyramid, then brings spatial information down to feature vectors for classification.

Fig. 2 .

 2 Fig. 2. An example of an original image (left) which at a lower resolution (input image 140 pixels) at the C1 layer (middle, first -finest scale) has retained little of the object's structure. At a higher resolution (input image 240 pixels) the C1 layer shows a more detailed representation (right).

Fig. 3 .

 3 Fig. 3. (a) Four example images (airplanes, bikes, cars, tanks) from the CUUD vehicle classes. No background clutter is present and images contain only one object for classification, (b) four example images (background, bikes, cars, people) from the CUCD classes. Background clutter is present and images in some cases contain more than one object in each image.

Fig. 4 .

 4 Fig. 4. Some examples of classes from the 101 Caltech dataset.

  Table

		Dataset	Dataset	Dataset
		CUUD -	CUCD-	Caltech-
	Method	Classification	Classification	Classification
		Accuracy (%)	Accuracy (%)	Accuracy (%)
	MFHLIB	80	70.6	18.75
	SFHLIB + Circular Gabor	85	80.4	22.4
	SFHLIB +
	S3/C3 Layers	86	76.6	19
	(60% features)
	SFHLIB +
	S3/C3 Layers	81	80.4	21.4
	(100% features)

Acknowledgements

The authors thank Drs C Lewis, R Bower & R Botton of the CPNI. AT thanks EPSRC for the provision of DTA grant and TC & KH thank the DCMT internal funding of their studentships.