Document Classification: how to boost your classifier

Time ago, we discussed about ADAboost as a meta algorithm useful to improve the accuracy of a weak classifier and I showed a sample on a boolean classification problem.
Frund and Schapire in this excellent paper proposed a version of this algorithm adapted to work with "multi labels" classifiers.

The two variants proposed in such paper are based on the trick to assign a weight to each sample of the training set in according with the error committed by the classifier, so it forces the classifier to be focused on the hard instances of the problem.
The improved classifier is finally obtained as a weighted combination of each version of the weak algorithm improved at each iteration.

Adaption of AdaBoost.M1 to a classifier SVM based.

ADaBoost.M1 tries to improve step by step the accuracy of the classifier analyzing its behavior on training set. (Of course you cannot try to improve the classifier working with the test set!!).
Here lays the problem, because if we choose as "weak algorithm" an SVM, we know that almost always it returns excellent accuracy on the training set with results closed to 100% (in term of true positive).
In this scenario, try to improve the accuracy of classifier assigning different weights to the training set doesn't work!

The idea of AdaBoost.M1 is still valid also with SVM classifiers, but I noticed that instead of to improve step by step the single SVM classifier,  we can train different SVM classifiers (with different parameters) and assign the score to each classifier based on the error committed on a part of the training set not used to train the SVM.
Let me explain better the procedure:

1. Split the training set in two different sets: training set (80% of the volume of the original training set), boosting set (20% of the volume of the original training set).
2. train k SVM classifiers with different parameters.
3. test the above SVM on the boosting set and calculate the beta score as done in the original implementation of ADAboost.M1.
4. The final answer of the boosted classifier is obtained as proposed by the original implementation of the Adaboost.M1

As you can notice, the method basically assigns to the k classifiers a "trustability score".


Real Case
Let's see what happens with our REUTERS-2158 data set:
I tried to classify the documents belonging to the categories: "GRAIN","CRUDE", "TRADE","OIL".
I trained four different SVM. Here you are what are the results of each classifier:

The Confusion Matrix for the Classifier I.The principal diagonal represents the True Positive.
In The circle the worst result for this classifier.

The Confusion Matrix for the Classifier II.The principal diagonal represents the True Positive.
In The circle the worst result for this classifier. 

The Confusion Matrix for the Classifier III.The principal diagonal represents the True Positive.
In The circle the worst result for this classifier. 

The Confusion Matrix for the Classifier IV.The principal diagonal represents the True Positive.
In The circle the worst result for this classifier. 

And after the application of the meta algorithm, here you are the confusion matrix for the improved classifier:

The Confusion Matrix for the Boosted classifier

As you can see the boosting provides us really good results! 

Here the same results showed in terms of precision and recall:

 

The Precision/Recall chart for the four weak classifiers.
(The ring shows the worst case for each classifier)

And here you are the Precision/Recall for the boosted classifier:

As usual Stay Tuned

Cristian

Document Classification part 1 - Data Set Analysis

As promised, in this post I'm going to discuss about an important branch of text analytics: the text categorization.
Step by step, we will build a classifier going through the following steps:

• Data set preparing.
• feature extraction.
• feature reduction comparing different techniques like PCA, C4.5, and other algos.
• Translation of the documents in the proper form to feed the classification algorithms.
• Classification via SVM ...we will explore different strategies to adapt a boolean classifier to multi class algorithm 
• Benchmarking with other classifiers like C4.5, naive Bayes Classifier.

As you can see, it will take plenty time to show every method, and I really hope you will attend proactively to exchange experiences.

After the pcreambolus, let's start with the first step: "data set preparing".

I decided to use for this experiment a very common standard data set: the Reuters-21578 data set.

It is a data set often used in academical context to perform benchmark tests over different strategies. 

It is organized in tagged files (sgm) easy to handle to build ad hoc data set, and you can download it at: http://www.daviddlewis.com/resources/testcollections/

Here you are the composition of the data set:

The Reuters-21578 data set composition

As you can see it is a multi dimensional data set, that is you can perform classification tasks across different kind of categories.

For example, you could build a data set considering "TOPICS" classes where "PLACES" = "Canada" and so on.

For our tests I decided to work with categories TOPICS: there are documents belonging to 135 different classes of TOPICS.

In a realistic scenario (by enterprise prospective) build an efficient classifier for 135 classes is too much expensive in terms of efforts to achieve good accuracy for each class, in terms of maintenance, and in terms of computational efforts.

So, if there aren't business constraints, is important perform a quantitative analysis to detect which are the most common classes.

The most important classes for "TOPICS" categories

The important question is:

How many classes have I to consider to cover at least X% of the entire amount of documents?

x- axis = classes (sorted by volume) --- y-axis % of documents covered 

As you can see, considering for example only 20 classes instead of 135, we are able to cover around 80% of all documents in the data set: this is the "Pareto Principle"!

If you are interested to play with the Reuters data set and follow the step by step classifier building, I arranged a Wolfram Mathematica notebook to extract automatically training/test set, using custom categories. Contact me directly at cristian.mesiano@gmail.com