# prequential evaluation - classification

I perform prequential evaluation like this: start with a training set, classify a number of examples, then add the correctly classified examples in the training set and continue to classifying the next number of unseen examples. Is this supposed to increase performance as examples are added to the training set or this doesn't apply to every case? By increasing performance I mean if the average F1, not only accuracy, of the second piece of unseen examples must be higher than that of the first or is it possible for a latter piece to have worse average F1 than a former? And if it has worse, what does this could be possibly mean? Could it mean a problem with training data?

This paper Sentiment Knowledge Discovery in Twitter Streaming Data describes prequential evaluation. It experiments with Naive Bayes and not SVMs, probably for the reasons mentioned in comments below.

• If you add the already correctly classified examples in the training set, this won't improve your performance (often the model will not change). What classification algorithm are you using? – Marc Claesen May 23 '13 at 10:29
• Support Vector Machines. Can you please explain why the model will not change? Also are there cases where adding the correctly classified examples can decrease performance? – guest May 23 '13 at 10:55
• An SVM model will not change if you duplicate points it already classified correctly. The support vectors will remain exactly the same. – Marc Claesen May 23 '13 at 10:57
• Thank you for your comments! Before classification I also perform feature selection. And I have noticed that when I add examples the information gain of the features changes and this could lead to worse performance. Is this a possible reason for decreasing performance at some chunks? Also if I experiment with Naive Bayes, correctly classified examples should increase performance at least in theory, right? – guest May 23 '13 at 11:43
• I missed completely the fact that you only add the correctly classified examples, but even if that is the case, the effects are not clearly defined and they depend on the model. Example, in Naive Bayes they will change the probability distributions of terms over classes that might imply some documents are now misclassified. However, in general, more data does not decrease quality. @MarcClaesen, what about the cases that are correctly classified but they will become support vectors if included, therefore changing the decision boundary? This will imply a change in the model, right? – miguelmalvarez May 23 '13 at 14:57

I would say that "in theory" the quality should increase until it reaches a saturation point, as it usually happens when you apply Active Learning. This should be true in general.

If adding more information you consistently get worse results, that would suggest that the new data is wrongly labelled, noisy or that it contradicts the previously seen one for some reason (e.g., some information might have changed over time).

I hope this helps,

• Thank you for your response! It is not actually decreasing over time. I would say that is not increasing in a stable manner. For example, there might be a piece where average F1 is 65%, then the next one is 70%, then again 68%. It's more like this. Could you please explain more the last phrase, "some information might have changed over time" ? – guest May 23 '13 at 9:40
• The trend should be to increase with respect to the amount of data, small decrease in quality is normal for some chunks. Btw, what quality measure are you using? and how you average over classes (micro vs macro-averaged)? What I mean by some information can change over time is that some datasets (mainly news or real-time data) can have a temporal dimension. For instance, the meaning or topic associated to a word can change radically over time. For instance Egypt was mainly related to "tourism" topic in 2006 but in 2010 it was mainly related to "politics". – miguelmalvarez May 23 '13 at 9:58
• If your dataset spans over a large period of time that should be considered as you do not want to have the same weight on the old and new "concepts". This is basically what is called time-aware Information retrieval. However, it is usually not applied to classification. That is probably not your case though. – miguelmalvarez May 23 '13 at 9:59
• By average F1 I mean the sum of F1s of the classes divided by the number of classes. Yes, I have seen that there are methods, which give more weight to new examples, but I don't know how to decide the weights or which concepts are defined as old. Moreover, I would like to ask why the trend is to increase with respect to the amount of data. If we have a model that has high bias, then increasing the training set will not help, right? – guest May 23 '13 at 10:17
• I am not sure this answers you but, in general, the more information you have the better the system will work until some point when it will basically remain the same. This means that not new relevant information is learn. – miguelmalvarez May 23 '13 at 14:51

new data is wrongly labelled

same weight on the old and new "concepts"

Likely need to detect and adapt to concept drift and/or imbalanced data.

"Prequential AUC for Classifier Evaluation and Drift Detection in Evolving Data Streams" http://www.cs.put.poznan.pl/dbrzezinski/publications/PrequentialAUC_LNCS.pdf

"we advocate the use of the area under the ROC curve (AUC) in imbalanced data stream settings and propose an efficient incremental algorithm that uses a sorted tree structure with a sliding window to compute AUC using constant time and memory"

The Apache MOA framework implements prequential evaluation of machine learning models (as opposed to holdout evaluation in batch/traditional learning).