A modi ed and fast to converge Perceptron learning rule algorithm is proposed as a general classi cation algorithm for linearly separable data. The strategy of the algorithm takes advantage of training errors to successively re ne an initial Perceptron Classi er. Original Perceptron learning rule uses training errors along with a parameter (learning rate parameter that has to be determined) to de ne a better classi er. The proposed modi cation does not need such a parameter (in fact it is automatically determined during execution of the algorithm). Experimental evaluation of the proposed algorithm on standard text classi cation collections, show that results compared favorably to those from state of the art algorithms such as SVMs. Experiments also show a signi cant improvement of the convergence rate of the proposed Perceptron algorithm compared to the original one. Seeing the problem of this year's Discovery Challenge (Tag Recommendation), as an automatic text classi cation problem, where tags play the role of categories and posts play the role of text documents, we applied the proposed algorithm on the datasets for Task 2. In this paper we brie y present the proposed algorithm and its experimental results when applied on the Challenge's data.
Text categorization is the process of making binary decisions about related or non-related documents to a given set of prede ned thematic topics or categories. This task is an important component in many information management organizations. In our participation on the ECML/PKDD challenge 2009, we treat Task 2 as a standard text classi cation problem and try to solve it using a machine learning, supervised, automatic classi cation method.
The rest of the paper is organized as follows. Section 2 provides a description of the algorithm that we used. Section 3 brie y present the tasks of this year's Challenge. Section 4 presents the experimental setup, data processing and results and nally in section 5 we conclude on the results.
The algorithm that we used is an evolution of the algorithm that appeared in [1] as a text classi cation algorithm and then a revised version in [2] won last year's ECML PKDD Discovery Challenge on Spam Detection. The proposed algorithm is a binary linear classi er and it combines a centroid with a batch perceptron classi er and a modi ed perceptron learning rule that does not need any parameter estimation. Details on this modi ed algorithm, its experimental evaluation, theoretical investigation etc, have already submitted and are under review for publication at the time this paper was written. In the following paragraphs we will brie y describe this method that we used for solving the problem of ECML PKDD 2009 Discovery Challenge, Task 2. 2.1
Linear Classi ers Linear Classi ers is a family of classi ers whose trained model is a linear combination of features. In another perspective linear classi ers train a model which is a hyperplane in a high dimensional feature space. In this space each instance, either of the train set or an unseen, is a point. The goal of a linear classi er is then to nd such a hyperplane that splits the space into two subspaces, where one contains all the points of the positive class and the other contains all the points of the negative class.
Assuming that feature space is of n dimensions, each instance xi will be represented by an n dimensions vector !x i = (wi1; wi2; ; win) where wik is a real value of the kth feature for instance xi.
Apart of each vector representation !x i, each instance xi may bears information about being a member of a class or not. For example a document is known to be spam or an image is known that shows a benign tumor. This information can be coded using a variable yi for each instance xi which takes values as: yi = 1 if xi 2 C+ 1 if xi 2 C That is yi = 1 when xi is member of the positive class C+ and yi = 1 when it is member of the negative class C . So each instance xi is represented by a tuple (!x i; yi). A training set T r would be
T r = f(!x 1; y1) ; (!x 2; y2) ;
A linear classi er then is de ned by a model DW!; bE where W! is a vector in the
same n-dimensional space and b is a scalar bias (threshold) value. This model
de nes a hyperplane h
x + b = 0
(
Perceptron Perceptron is a avor of Linear Classi ers. It starts with an initial model and iteratively re nes this model using the classi cations errors during training. It is the elementary particle of neural networks and it has been investigated and studied since the 1950s [3]. It has been shown that when trained on a linearly separable set of instances, it converges (it nds a separating hyperplane) in a nite number of steps [4] (which depends on the geometric characteristics of the instances on their feature space).
The Perceptron is a Linear Binary Classi er that maps its input !x (a
realvalued vector) to an output value f (!x ) (a single binary value) as:
f (!x ) =
1 if W!
1
!x + b > 0
else
(
We can always assume for convenience that the bias term b is zero. This is not a restriction since an extra dimension n + 1 can be added to all the input vectors !x i with !x i(n + 1) = 1, in which case W!(n + 1) replaces the bias term.
Learning is modeled as the weight vector W! being updated for multiple iterations over all training instances. Let
T r = f(!x 1; y1) ; (!x 2; y2) ;
denote a training set of m training examples (instances). At each iteration k the
weight vector is updated as follows. For each (!x i; yi) pair in T r
W!(k) = W!(k 1) +
(k 1)
yi
f (k 1) (!x i) !x i
(
The training set T r is said to be linearly separable if there exists a positive constant and a weight vector W! such that
! yi W
!x i + b > ; 8 (!x i; yi) 2 T r Noviko [4] proved that the perceptron algorithm converges after a nite number of iterations k if the train data set is linearly separable. The number of mistakes (iterations) is bounded then by
W!(k) = W!(k 1) + (k 1) b(k) = b(k 1) + (k 1)
X (!x i;yi)2Err
yi!x i
X (!x i;yi)2Err
yi k 2R 2 where R = maxfjj!x ijjg is the maximum norm of an input train vector. 2.3
Batch Perceptron Equation 6 de nes a single sample xed increment perceptron learning rule. It is called xed increment because parameter is constant throughout training. In the case where this parameter changes at each iteration, we say that it is a variable increment perceptron. It is also called single sample because this rule applies at each instance xi which was misclassi ed during iteration k. In other words, at iteration k each (!x i; yi) 2 T r is presented to model W!(k 1) and if it is misclassi ed by it (f (k 1) (!x i) 6= yi) then this single instance !x i is used (along with parameter (k 1)) to alter W!(k 1) into W!(k).
A modi cation of this perceptron can be made de ning a set of instances Err T r
Err = f(!x i; yi)g; f (k 1) (!x i) 6= yi
that contains all the misclassi ed examples at iteration k and then modifying
weight vector as:
(
Centroid Classi er A Centroid classi er is a simple linear classi er, that will help us understand the notion behind our modi cation presented in the next Section. In the simple binary case there are two classes, the positive and the negative one. We de ne set C+ and C containing instances from the positive and respectively the negative class. We call Centroid of the positive class and respectively the Centroid of the negative class as
We then de ne a linear classi er as ! C + = !C = 1 1
X
X jC+j !xi 2C+ jC j !xi 2C !xi !xi h : W!
!x + b = 0 W! = !C+ ! C (12) (13) (14) (15) where and bias value b is de ned by some technique we discuss in the following paragraphs.
Figure 1 illustrates a simple case of a centroid classi er in a 2-dimensional space. Sets C+ of the positive class and C of the negative class are shown along with their centroid vectors !C+ and !C respectively. We note that in this simple example, these two classes are linearly separable and therefore it is possible to nd a value for bias b such that h is a perfect separating hyperplane.
A method for nding such a value is Scut [5], where we iteratively choose values for bias b and then keep the one that lead to the best classi er (as measured by some evaluation measurement). Bias takes values as bi = W! !x i; 8!x i 2 T r (16) and then an evaluation measure (for example the F1 measure) is computed for classi er h : W! !x + bi = 0. Finally as bias value is chosen the one that gave the maximum evaluation measure. It is clear that the instance xi that corresponds to the chosen bi lies on hyperplane h. In the shown 2-dimensional example of Figure 1 this instance is marked by point !x Scut.
This simple algorithm has previously investigated and methods have been proposed for altering initial centroids or weights in order to achieve a better classi er [6{8].
In the next subsection we present how ideas from Centroid Classi er and Perceptron are combined to our modi ed version of Perceptron. Centroid Classi er of the previous subsection can be seen as a perceptron with initial weight vector W!(0) = !C+ !C , bias value b as de ned by an Scut method and no other training adjustments at all. The case shown in Figure 1 is an ideal case for a Centroid Classi er, meaning that it is possible to nd a value for b resulting to a perfect separating hyperplane h : W! !x + b = 0.
This is not however true in all cases. Figure 2 shows such a case where nding a perfect separating hyperplane is not possible for a simple Centroid Classi er. Dark regions contains misclassi ed instances that cannot correctly classi ed. A Simple Sample or a Batch Perceptron would use these errors to modify the weight vector W!.
If we de ne sets F P and F N as:
F P = f(!x i; yi)g8xi 2 C ; f (!x i) 6= yi F N = f(!x i; yi)g8xi 2 C+; f (!x i) 6= yi (17) (18) in other words set F P contains negative instances that were misclassi ed as positive (False Positive), whereas set F N contains positive instances that were misclassi ed as negative (False Negative). A Batch Perceptron then using misclassi ed instances modi es weight vector as Equation 10 or equivalently as: W!(k+1) = W!(k) + (k) 0
X
!x i !x i2F N(k)
X !x i2F P (k)
1 !x iA (19)
However there is a parameter , either constant or variable that needs to be estimated. This learning rate parameter is strongly related to the eld on which perceptron learning is applied and train data itself. A way to estimate it is using a validation set of instances and selecting a value for that leads to maximum performance. But this operation must be repeated whenever eld of operation or data is switched and costs very much in terms of time.
Another approach is to use a xed value for the learning rate like = 1 or = 0:5 for example, without attempting to nd a optimal value. However this could result to very unwanted e ects because learning rate is too small or too large for the speci c eld of operation and training instances.
The key idea of our approach is illustrated in Figure 3 where we concentrate
on the misclassi ed regions. Positive class and a portion of negative class are
shown. Initial weight vector W!(0) and hyperplane h(0) are de ned by a simple
Centroid Classi er. The idea is, at the next iteration 1, to modify weight vector
and bias into W!(
We de ne these misclassi ed centroids at each iteration as (20) (21) (22) (23) jF P (k)j !xi 2F P (k) jF N (k)j !xi 2F N(k)
X X !xi !xi where sets F P and F N are de ned in Equations 17 and 18. We then de ne the error vector at each iteration as
Batch Perceptron learning rule of Equation 19 is then modi ed to: We can easily compute the value of this modi ed learning rate 0(k) if we note that misclassi ed centroids F !N(k) and F!P (k) lie by construction on the new hyperplane h(k+1). As a result error vector !e (k) is vertical to the new normal vector W!(k+1). So !(k+1) W
!e (k) = 0 W!(k) + 0(k)!e (k) !(k) W !e (k) + 0(k)jj!e (k)jj2 = 0 0(k) = !(k) W
!e (k) jj!e (k)jj2 And then the modi ed learning rule of Equation 23 is
W!(k+1) = W!(k) !(k) W
!e (k) jj!e (k)jj2 !e (k) This is the normal vector de ning the direction of the next hyperplane h(k+1). The actual position of it is determined by the new bias value which is easily computed (bringing in mind that misclassi ed centroids lie on the new hyperplane): b(k+1) = As last year's, this year's ECML PKDD Discovery Challenge deals with the well known social bookmarking system called Bibsonomy 1. In such systems, users can share with everyone links to web pages or scienti c publications. The former are called bookmark posts, where the later are called bibtex posts. Apart from posting the link to the page or the publication, users can assign tags (labels) to their posts. Users are free to choose their own tags or the system can assist them by suggesting them the appropriate tags.
This year's Discovery Challenge problem is about generating methods that would assist users of social bookmarking systems by recommending them tags for their posts. There are two distinct task for this problem. Task 1 is about recommending tags to posts over an unknown set of tags. That means that the methods developed for Task 1 must be able to suggest tags that are unknown (in other words suggest new tags). Task 2, on the other hand, is about recommending tags that have been already known to be ones. 2 1 http://www.bibsonomy.org 2 More details about tasks can be found on Challenge's site at http://www.kde.cs.uni-kassel.de/ws/dc09/#tasks (24) (25) for evaluating their performance. Both of them where provided as a set of 3 les (tas, bookmark, bibtex). Files bookmark and bibtex contain textual data of the corresponding posts. File tas contains which user assigned which tags to which bookmark or bibtex resource. Each triplet (user,tags,resource) de nes a post. Train and test les where of the same tabular format, except test tas le which of course did not contain tag information, as this was Challenge's goal. 3
More details about preprocessing of the datasets will be given on the following section 4. 4
Challenge's organizers had suggest that graph method would t better to task 2, whereas content based method would t to task 1. In our work we concentrated on task 2, and from this point on whenever we mention a task, we mean task 2. Although organizers suggested graph method for the task, we choose to use our modi ed perceptron rule for solving this problem. We made this decision because we wanted to test the performance and robustness of the proposed algorithm on a domain with a large category set. As we are going to present in our under review paper, we have evaluated the proposed algorithm on standard text classi cation datasets as well as on arti cially generated (and linearly separable) datasets. Although feature spaces of these datasets are of tens or hundreds of thousands features, their categories sets are of few to at most a thousand categories. We wanted to investigate how this method is going to perform when both feature and category spaces are large.
So, Task 2 can be seen as a standard text classi cation problem, and the proposed algorithm as a machine learning, supervised, automatic classi cation method that applies on it. In this problem, tags (labels) that assigned on posts can be seen as categories. On the other hand, posts can be seen as text documents, where category labels (tags) are assigned on them. 4.1
Data Preprocessing Viewing task 2 as a supervised text classi cation problem, implies that datasets must transformed to a vector space, where the proposed linear classi er can be used. For every post (user,tags,resource), we construct a text document and then transform it to the vector space.
We choose to discard user information from the posts, so the only textual information for each post came from the assigned tags and the resource. Furthermore for each bookmark post we kept url, description and extended description elds. For each bibtex post we kept journal, booktitle, url, description, bibtexAbstract, title and author elds.
Fore every post, and using those eld, we construct a text document. We then transform document dataset to a vector space. First tokenization of the 3 More details about datasets can be found at
http://www.kde.cs.uni-kassel.de/ws/dc09/dataset text, then stop word removal, then stemming (using Porter's stemmer [9], then term and feature extraction and nally feature weighting using tf*idf statistics.
The following table 1 presents some statistics about categories (tags) and documents (posts) in the train and the test dataset.
64,120 778 13,276
The following diagram 4 presents the distribution of the sizes of categories in the train dataset. Axis x denotes the number of categories that are of a certain size. Axis y denotes the number of documents that a certain sized category contains.
10000 s 1000 t n e m u c fdo 100 o r e b m u N 10 1 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000
Number of categories
We note that categories sizes are small in general. In fact 10,500 out of 13,276 categories have at most 10 documents. The average size of categories is 1:97 (average posts per tag). After converting documents (posts) into vectors in a high-dimensional space, we can apply the proposed text classi cation method for solving the multilabel classi cation problem. Since the method trains a binary linear classi er, the problem must be transformed into binary classi cation. This is done by cracking the problem into multiple binary classi cation problems. So, at the end we have to solve 13; 276 binary classi cation problems.
The number of problems is quite large and therefore the used method must be as much fast as possible. After the train phase (which nishes after the reasonable time of 2 hours in a mainstream laptop), the nal classi cation system consists of 13; 276 binary classi ers. Test phase consists of presenting each document of the test dataset (778 in total) to every binary classi er resulted from training phase (13; 276 in total). Each classi er decides whether the presented document (post) belongs or not to the corresponding category (tag). Time needed fore presenting all document to all classi ers on a mainstream laptop was about 10 minutes (that is about 0.8 seconds for a document to pass through all classi ers).
We produced 2 types of results. The ones that come from binary classi cation and the ones that come from ranking. During binary classi cation a document could be assigned or not into a category. Therefore a document, after been presented to every binary classi er, could be assigned to zero, one, or more categories (max is 13; 276 of course).
On the ranking mode, a classi er gives a score to each presented document (higher score mean higher con dence of the classi er that this document belongs to the corresponding category). Therefore at this mode, a document can be assigned to any number z of categories we select (simply by selecting the z categories which gave the higher scores).
We chose our submission to the Challenge, to contain results of the ranking mode (by selecting the 5 higher scored categories for each document).
After releasing the original tag assignments of the test dataset, our results of the ranking mode achieved a performance of F1 = 0:1008. The results of the rst mode (binary mode), that where never submitted, achieved a performance of F1 = 0:1622. Of course, those results could not have been known prior releasing original test tas le, but we had a belief that the ranking mode (suggesting 5 tags for every post, instead of less or even zero) would had better results. Unfortunately this belief was false. 5
In this paper we described the application of a modi ed version of the Perceptron learning rule on Task 2 of ECML PKDD Discovery Challenge 2009. This algorithm acts as a supervised machine learning, automatic text classi cation algorithm on the data of the task. Task 2 is transformed to a supervised text classi cation problem by treating users' posts ass text documents and assigned tags as thematic categories.
This algorithm has been prior tested on various text classi cation datasets and arti cially generated linearly separable datasets, and it has shown a robust performance and e ciency. Compared with the original Batch Perceptron learning algorithm, it shows a signi cant improvement on the convergence rate.
Its fast training phase made it feasible to be used on Task 2 dataset, which consists of a large categories set (more than 13; 000 categories) and a linear classi er had to be trained for each category.
Although its results on Task 2 test dataset where not so well, we think that its fast training phase and fast evaluation (since it is just a dot product for each category-document tuple) allow for further investigation.
This paper is part of the 03ED316/8.3.1. research project, implemented within the framework of the "Reinforcement Programme of Human Research Manpower" (PENED) and co- nanced by National and Community Funds (20% from the Greek Ministry of Development-General Secretariat of Research and Technology and 80% from E.U.-European Social Fund).