Classifier for uncertain class labels

Question

Let's say I have a set of instances with class labels associated. It does not matter how these instances were labelled, but how certain their class membership is. Each instancs belongs to exactly one class. Let's say I can quantify the certainty of each class membership with a nominal attribute that goes from 1 to 3 (very certain to uncertain, respectively).

Is there some sort of classifier that takes into consideration such a certainty measure and if yes, is it available in the WEKA toolkit?

I imagine this situation occurs quite often, for example when instances are classified by human beings which are not always completely sure. In my case, I have to classify images, and sometimes an image could belong to more than one class. If this happens, I give the class a high uncertainty, but still classify it with only one class.

Or are there any other approaches to this problem, without a specialized classifier? E.g. only taking "certain" classifications for training? I fear that in this case, there will be more misclassifications because "border" cases are not covered.

Answer 1

First of all, as @Marc Claesen already explained, semi-supervised classification is one of the techniques to take care of the situation where you know that the classes are really distinct, but you are not certain which class the case actually belongs to.

However, there are related situations as well, where the the "reality" isn't that clear, and the assumption of having really distinct classes is not met: bordeline cases may be a "physical" reality (see below for papers about an application where we met such a condition).

There is one crucial assumption for semi-supervised classifers that you need to make sure is met: the assumption that in feature space, class boundaries come along with low sample density. This is referred to as the cluster assumption.
Even if the reality underlying your data has distinct classes, your data set may have disproportionally more borderline cases: e.g. if your classification technique is targeted at classifying difficult cases, while the clear and easy cases are not of interest and already your training data reflects this situation.

only taking "certain" classifications for training? I fear that in this case, there will be more misclassifications because "border" cases are not covered.

I fully agree with you that excluding the borderline cases is often a bad idea: by removing all difficult cases you end up with an artificially easy problem. IMHO it is even worse that excluding borderline cases usually does not stop with model training, but the borderline cases are also excluded from testing, thus testing the model only with easy cases. With that you'd not even realize that the model does not perform well with borderline cases.

Here are two papers we wrote about a problem that differs from yours in that in our application also the reality can have "mixed" classes (a more general version of your problem: uncertainty in reference labels is covered as well).

• The appliation: brain tumour diagnostics. We used logistic regression. Semi-supervised modeling was not appropriate as we cannot assume low sample density at class boundaries.
  C. Beleites, K. Geiger, M. Kirsch, S. B. Sobottka, G. Schackert and R. Salzer: Raman spectroscopic grading of astrocytoma tissues: using soft reference information, Anal. Bioanal. Chem., 400 (2011), 2801 - 2816.
• Theory paper deriving a general framework for measuring the performance of the classifier for borderline cases.
  C. Beleites, R. Salzer and V. Sergo:
  Validation of Soft Classification Models using Partial Class Memberships: An Extended Concept of Sensitivity & Co. applied to Grading of Astrocytoma Tissues
  Chemom. Intell. Lab. Syst., 122 (2013), 12 - 22.

The links go to a project page of an R package I developed to do the performance calculations. There are further links to both the official web page and my manuscripts of the papers. While I have not used Weka so far, I understand that an interface to R is available.

---

practical considerations:

• While the copy-and-label-differently approach is straightforward, it does not work well with all classifiers and implementations in practice. E.g. AFAIK there is no way to tell libSVMs tuning by cross validation that all copies of each data point need to be kept in the same cross validation fold. Thus libSVMs tuning would probably yield a massively overfit model.
• Also for logistic regression, I found that many implementations did not allow the partial membership labels I needed.
• The implementation I used for the papers above is actually an ANN without hidden layer using the logistic as sigmoidal link function (nnet::multinom).

Answer 2

This is one of the generalizations of classification that are tackled in semi-supervised learning. If you have a measurement of certainty you can use approaches that allow weighting of training instances. The higher the certainty, the larger the corresponding instance weight. Examples of such approaches include instance-weighted SVM and logistic regression.

I'm sure weka has implementations of these algorithms. If all else fails, sample multiple instances from the instances with high certainty. You can use this approach for traditional SVM or LR.

Example: SVM

If I am not mistaken, weka has interfaces to LIBSVM. LIBSVM allows you to solve class-weighted SVM in all its releases, and instance-weighted SVM in special versions of each release. I'm going to assume weka does not support the latter (which is what you need).

Class weighted SVM minimizes the following objective function: $$ \min_{\mathbf{w},\xi} \|\mathbf{w}\|^2 + {\color{blue}C_{pos}} \sum_{i \in \mathcal{P}} \xi_i + {\color{blue}C_{neg}} \sum_{i \in \mathcal{N}} \xi_i, $$ with $\mathbf{w}$ the separating hyperplane in feature space, $\xi$ the slack variables (which model training misclassification) and $\mathcal{P}$ and $\mathcal{N}$ the set of support vectors belonging to the positive and negative class, respectively. Using the weights $C_{pos}$ and $C_{neg}$ you can assign different misclassification penalties between classes.

Based on your question, it seems like you would ideally want to use 6 different weights (2 classes $\times$ 3 levels of certainty). You can achieve this for many approaches by duplicating samples of the points with high certainty.

For example, in terms of SVM, using the same data instance twice yields an identical solution to doubling its associated $C$ value. This is a very easy way to assign high misclassification penalties to certain data instances. You can follow the same approach for logistic regression.

Answer 3

The difficulty of the problem is highly dependent on how erroneous the uncertain labels can be. If the the uncertain labels are right, say, 90% of the time, you can probably get away with just using logistic regression. On the other hand, if the labels are wrong almost half the time, you may need to resort to some special techniques. Here's one stab I took at a very similar problem. (We had multiple observations per label, but otherwise the setup is quite similar.)

Answer 4

I had a brief run in with image recognition and classification.

Random Forests is an easy to use technique. I've implemented it on R, it should be available on Weka as well. Ease of use trumps prediction accuracy though. If you have a large enough training set, it can classify multiple labels.

It worked to recognize handwritten digits quite well, but if your images are more complex, then only a trial would tell you if it does well.