13
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Does each entry belong to exactly one class? Or it is possible that some entry belongs to class 12 with certainty 1 and class 34 with certainty 2? $\endgroup$
    – user31264
    Commented Nov 3, 2013 at 1:51
  • $\begingroup$ Each entry belongs to exactly one class, in this case. $\endgroup$
    – grssnbchr
    Commented Nov 5, 2013 at 7:32

4 Answers 4

9
+50
$\begingroup$

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 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).
$\endgroup$
3
  • $\begingroup$ Your first practical consideration, while true, does not apply to libsvm in particular. The libsvm authors provide an alternative version of every release in which instance-weighted classification is possible, avoiding this problem altogether. It is these kinds of things that drive me to generally use algorithm libraries directly, instead of wrappers like Weka/scipy/... csie.ntu.edu.tw/~cjlin/libsvmtools/#weights_for_data_instances $\endgroup$ Commented Nov 5, 2013 at 15:39
  • $\begingroup$ @MarcClaesen: thanks - I hadn't seen that. But wouldn't you need to supply two instances of the same case one weighted say with 1/3 class A and the other with 2/3 class B? In any case, not needing to supply lots of copies of the clear cases will make the tuning less problematic (for my data I anyways have to do the tuning splits externally as I have a "hierarchical" data structure with multiple measurements of the actual cases) $\endgroup$ Commented Nov 5, 2013 at 15:44
  • $\begingroup$ @cbeiteles when an instance may belong to multiple classes you will indeed need to provide it multiple times, even with this instance-weighting. I hadn't considered that possibility. $\endgroup$ Commented Nov 5, 2013 at 15:45
6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ (+1) this is it ! By duplicating instances with different labels and instance weights (aka label certainties), one can also apply algorithms like Random Forests, Naive Bayes etc.. Instance weights are so common, weka has to have learners which support it. Rapidminer (competitor of weka) does. By setting the certainty to 1, one can even model "crisp" multi-label-problems. $\endgroup$
    – steffen
    Commented Nov 4, 2013 at 8:51
  • $\begingroup$ You are correct, WEKA supports LIBSVM, but doesn't support instance weighting, afaik. The idea of duplicating instances is a very good one, I think, especially because every "traditional" learner can deal with it. $\endgroup$
    – grssnbchr
    Commented Nov 5, 2013 at 7:42
3
$\begingroup$

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.)

$\endgroup$
-5
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\begingroup$ What has that got to do with uncertain class labels? $\endgroup$
    – grssnbchr
    Commented Nov 5, 2013 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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