14
$\begingroup$

I am new to Machine Learning. At the moment I am using a Naive Bayes (NB) classifier to classify small texts in 3 classes as positive, negative or neutral, using NLTK and python.

After conducting some tests, with a dataset composed of 300,000 instances (16,924 positives 7,477 negatives and 275,599 neutrals) I found that when I increase the number of features, the accuracy goes down but the precision/recall for positive and negative classes goes up. is this a normal behavior for a NB classifier? Can we say that it would be better to use more features?

Some data:

Features: 50    
Accuracy: 0.88199
F_Measure Class Neutral 0.938299
F_Measure Class Positive 0.195742
F_Measure Class Negative 0.065596

Features: 500   
Accuracy: 0.822573
F_Measure Class Neutral 0.904684
F_Measure Class Positive 0.223353
F_Measure Class Negative 0.134942

Thanks in advance...

Edit 2011/11/26

I have tested 3 different feature selection strategies (MAXFREQ, FREQENT, MAXINFOGAIN) with the Naive Bayes classifier. First here are the Accuracy, and F1 Measures per class:

enter image description here

Then I have plotted the train error and test error with an incremental training set, when using MAXINFOGAIN with the top 100 and the top 1000 features:

enter image description here

So, it seems to me that although the highest accuracy is achieved with FREQENT, the best classifier is the one using MAXINFOGAIN, is this right ? When using the top 100 features we have bias (test error is close to train error) and adding more training examples will not help. To improve this we will need more features. With 1000 features, the bias gets reduced but the error increases...Is this ok ? Should I need to add more features ? I don't really know how to interpret this...

Thanks again...

$\endgroup$
  • 1
    $\begingroup$ It depends on what you mean with "best classifier", if your task is building a classifier with good accuracy overall, I would choose FREQENT. On the other hand, if, like in the most of rare class classification tasks, you want to classify better the rare class (that could be the "negative" or the "positive" class) I would choose MAXINFOGAIN. I think your learning curves interpretation is correct: with 100 features you have bias and you may add them, with 1000 you have variance and you may remove them. Maybe you can try a trade-off between 100 and 1000 features to get better results. $\endgroup$ – Simone Nov 26 '11 at 14:59
  • $\begingroup$ Thanks for your help, Simone! I understood everything but the last part... Could you please tell me how you see the high variance with the 1000 features ? Since the difference between the test and train errors does not seem to be that much it still looks like bias to me... $\endgroup$ – kanzen_master Nov 26 '11 at 15:17
  • $\begingroup$ I put some examples on my reply. When the curves are not so close the problem is classified as with high variance. In your case, maybe I told you that because with less features you get better performances, and so with 1000 features is likely to be a problem of high variance. Rather than plot the results of features selection algorithms with measures computed on the training set, try to split your data in training (2/3 of them) and validation, then perform the features selection on the training set and evaluate it on the test set. You should find a maximum in the middle of the plot. $\endgroup$ – Simone Nov 26 '11 at 22:01
  • $\begingroup$ Thank for the reply. The 3rd example of your updated post (good result, train, test error curves are neither too near neither too far) looks like the learning curve I plotted using 1000 features, so I thought using around 1000 features would be a "good result". However, in this case the error is higher, which is not good. But, just looking at the distance between the curves, I cannot see high variance with 1000 features... (By the way, I am already splitting the data in 2/3 as training set, 1/3 as test set, performing feature selection on the training set, and evaluating on the test set...) $\endgroup$ – kanzen_master Nov 27 '11 at 1:45
  • 1
    $\begingroup$ OK. I'm quite new to learning curves and your examples were really interesting and made me gain insights on them. Thus, thanks D T. Yes, there might be bias in both cases. According to me, you have a very skewed data set and rather than testing accuracy it is important to have a look to F-measure. Having a look to your plots, it seems that the more features you have the better it is; in fact, F-measure improves. I heard that in text classification, if you features are the word frequency in your text, it is common to use a lot features; btw I'm not used to it and I can't tell you more. $\endgroup$ – Simone Nov 27 '11 at 12:36
17
$\begingroup$

Accuracy vs F-measure

First of all, when you use a metric you should know how to game it. Accuracy measures the ratio of correctly classified instances across all classes. That means, that if one class occurs more often than another, then the resulting accuracy is clearly dominated by the accuracy of the dominating class. In your case if one constructs a Model M which just predicts "neutral" for every instance, the resulting accuracy will be

$acc=\frac{neutral}{(neutral + positive + negative)}=0.9188$

Good, but useless.

So the addition of features clearly improved the power of NB to differentiate the classes, but by predicting "positive" and "negative" one missclassifies neutrals and hence the accuracy goes down (roughly spoken). This behavior is independent of NB.

More or less Features ?

In general it is not better to use more features, but to use the right features. More features is better insofar that a feature selection algorithm has more choices to find the optimal subset (I suggest to explore: feature-selection of crossvalidated). When it comes to NB, a fast and solid (but less than optimal) approach is to use InformationGain(Ratio) to sort the features in decreasing order and select the top k.

Again, this advice (except InformationGain) is independent of the classification algorithm.

EDIT 27.11.11

There has been a lot of confusion regarding bias and variance to select the correct number of features. I therefore recommend to read the first pages of this tutorial: Bias-Variance tradeoff. The key essence is:

  • High Bias means, that the model is less than optimal, i.e. the test-error is high (underfitting, as Simone puts it)
  • High Variance means, that the model is very sensitive to the sample used to build the model. That means, that the error highly depends on the training set used and hence the variance of the error (evaluated across different crossvalidation-folds) will extremely differ. (overfitting)

The learning-curves plotted do indeed indicate the Bias, since the error is plotted. However, what you cannot see is the Variance, since the confidence-interval of the error is not plotted at all.

Example: When performing a 3-fold Crossvalidation 6-times (yes, repetition with different data partitioning is recommended, Kohavi suggests 6 repetitions), you get 18 values. I now would expect that ...

  • With a small number of features, the average error (bias) will be lower, however, the variance of the error (of the 18 values) will be higher.
  • with a high number of features, the average error (bias) will be higher, but the variance of the error (of the 18 values) lower.

This behavior of the error/bias is exactly what we see in your plots. We cannot make a statement about the variance. That the curves are close to each other can be an indication that the test-set is big enough to show the same characteristics as the training set and hence that the measured error may be reliable, but this is (at least as far as I understood it) not sufficient to make a statement about the variance (of the error !).

When adding more and more training examples (keeping the size of test-set fixed), I would expect that the variance of both approaches (small and high number of features) decrease.

Oh, and do not forget to calculate the infogain for feature selection using only the data in the training sample ! One is tempted to use the complete data for feature selection and then perform data partitioning and apply the crossvalidation, but this will lead to overfitting. I do not know what you did, this is just a warning one should never forget.

$\endgroup$
  • $\begingroup$ Thank you very much for your reply, very clear explanation. I am using maximum information gain as my feature selection strategy, and testing using 5-fold cross validation. I guess that in order to know which top k features should I take I need to iteratively test the algorithm increasing the number of features each time, and taking the k which gives highest f_score. However, I guess that "top k" is likely to change depending on the data set...right? $\endgroup$ – kanzen_master Nov 23 '11 at 12:39
  • 1
    $\begingroup$ Correct. But if the new dataset is similar to the old one (same features with same distributions) k remains the same. You can add a genetic algorithm to search the space of possible solutions faster or (even better) use a genetic algorithm to find the optimal feature subset independent of InformationGain ... so many ways to go. $\endgroup$ – steffen Nov 23 '11 at 13:28
  • 1
    $\begingroup$ According to Stanford's lectures, if you see well separated training and test curves varying the # of training examples it actually means that there is variance. Of course a better approach would be to estimate confidence intervals. $\endgroup$ – Simone Nov 27 '11 at 13:39
  • 1
    $\begingroup$ @DT 1. I do not know the lecture, hence I cannot connect Andrewg's explanation with mine, sorry. 2. No. Small number of features => overfitting => low bias,high variance. High number of features => underfitting => high bias, low variance. I really suggest to plot the variance of the error of the cv-folds for different number of features and training examples. $\endgroup$ – steffen Nov 27 '11 at 15:05
  • 2
    $\begingroup$ 1. steffen, the lecture is available here: ml-class.org/course/video/preview_list (Part X, Section "Learning Curves") 2. I see. I was thinking that when lots of features learned during training => model gets complex, and overfits the training set => Variance... $\endgroup$ – kanzen_master Nov 27 '11 at 16:07
5
$\begingroup$

In order to know if it is useful to use more features I would plot learning curves. I think this is clearly explained in the 10th Unit of Stanford's Machine Learning class, named "Advise for applying machine learning", that you can find here: http://www.ml-class.org/course/video/preview_list.

Plotting learning curves you can understand if your problem is either the high bias or the high variance. As long as you increase the number of training example you should plot the training error and the test error (ie 1-accuracy), the latter is the error of your classifier estimated on a different data set. If these curves are close to each other you have an high bias problem and it would probably be beneficial to insert more features. On the other hand, if your curves are quite separated as long as you increase the number of training examples you have a high variance problem. In this case you should decrease the number of features you are using.

Edit

I'm going to add some examples of learning curves. These are learning curves obtained with a regularized logistic regression. Different plots are related to different $\lambda$ to tune the power of regularization.

With a small $\lambda$ we have overfitting, thus high variance.

High variance

With a large $\lambda$ with have underfitting, thus high bias.

High bias

A good result is obtained setting $\lambda=1$ as trade-off.

Good result

$\endgroup$
  • $\begingroup$ Great! Thank you very much! Since both answers were really helpful but I can't mark both of them as replies, I will mark the first one as the answer. But this is definitely the best way to check, I think. $\endgroup$ – kanzen_master Nov 23 '11 at 14:20
  • $\begingroup$ By the way, I am trying to plot the learning curve of a classifier that uses the top 100 features with Maximum Information Gain score. While increasing the training data set size I want to plot training error and test error. Which should be the sizes for the initial train data set (to be gradually increased) and for the test data set (static for all tests) ? Thanks again... $\endgroup$ – kanzen_master Nov 25 '11 at 16:26
  • 2
    $\begingroup$ Split your data set in a training set and a test set. Start from very few training records and then continue to add records. For every iteration compute the training set error with the records you have used to train your classifier and then compute the test set error always with all test records. I know this is a standard method used in common practise. It would be interesting to see your results! Cheers, Simone. $\endgroup$ – Simone Nov 25 '11 at 16:43
  • 1
    $\begingroup$ Simone, I have updated the first post with some results of accuracy, f1 measures, and learning curves, and my interpretation in the bottom, could you please check it ? Thanks... $\endgroup$ – kanzen_master Nov 26 '11 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.