3
$\begingroup$

This is rather a theoretical question in order to save the trouble in trying to do empirical testing and is part of a bet, so I hope I am right...

Say there are M classes in the data BUT you want to classify JUST between to subsets of these classes: M1 and M2 (M1+M2 = M). For example all M1 are different types of fraud and all M2 are different types of genuine users. Notice that the type of fraud/user is nuisance information and only the label fraud/genuine is of importance.

One approach would be to use a multi-class classifier and then see if the estimated class is within M1 or M2. An alternative would be to use a binary classifier, disregarding the multiple labels and just using label = 1 for M1 and label = 2 for M2.

Which classifier will work better in the general case? If the answer depends on data distribution, please explain.

Thanks, Hanan

p.s. my intuition says that binary will work better: the hypothesis space is smaller, so generalization error is smaller too.

$\endgroup$
  • $\begingroup$ When I think of it again, I guess there is a chance for the multiclass to outperform, only if the binary classifier has a large bias (bad performance on the training set). In these cases, the multiclass artificially increases the hypothesis space and thus increase performance. However, when the training performance is good (low bias), than adding more nuisance labels may degrade performance. $\endgroup$ – Hanan Shteingart Apr 8 '14 at 19:01
3
$\begingroup$

There are cases where the multiclass approach would better; imagine that you have classes A1, A2 (both A) and B1 (only B class) and want to discriminate between A and B. Also consider that when looking at the predictors, B lies between A1 and A2; this already works in 1D or 2D. Some methods like linear discriminant analysis or logistic regression will fail miserably. That's because in a basic sense they will try to find a separating hyperplane, which will not work because A1 and A2 would lie on different sides (or all three classes would lie on the same). The same algorithms combined with a softmax extension to handle multiclass work fine when predicting A1, A2 and B1 individually.

So, the answer is that it will depend on your data and your algorithm. I feel that if the subclasses are very distinct it makes more sense to give the model this additional structure, but there's no general law for all algorithms. But in a optimal situation more information is always better than less information. However, if the subclasses are so similar that the additional information does not help it just adds noise.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hi Erik, I agree with your example, and this is what I had in mind, but I was thinking on more advance algorithms than just linear classifiers. For example Kernel-based SVM or Random Forest. Since this can learn any distribution, I believe that in the general case, using more labels has disruptive effect the binary problem. $\endgroup$ – Hanan Shteingart Apr 8 '14 at 15:22
  • $\begingroup$ I don't think this will change the situation; for example, with SVM it becomes dependant on the kernel bandwidth. If it's too large you still have the same situation as with the simple methods and with the a very small bandwidth you will have overfitting. But I can't easily prove this. $\endgroup$ – Erik Apr 8 '14 at 15:38
  • $\begingroup$ Perhaps as an aside example, simple methods are not only simple but also usually make assumption of a parametric model. If these assumptions holds they are usually better or competitive with much more complicated algorithms; that's why I would be careful to use the word advanced concerning kernel SVM and random forest or imply that they are generally superior and draw conclusions from that. $\endgroup$ – Erik Apr 8 '14 at 15:41
  • $\begingroup$ Note that using multiple sub-labels will reduce the training set size per class. However, I agree with the last comment "it will depend on your data and your algorithm", and I am not sure you can give a general statement for all learning algorithms and all target functions. $\endgroup$ – emem Dec 31 '17 at 13:10
0
$\begingroup$
#####################################################
# This example shows a huge difference between the 
# two approaches
#####################################################

library(MASS)
set.seed(123);
n <- 100;
x <- rep(c(1,1,-1,-1), n) + 0.5 * rnorm(4*n);
y <- rep(c(1,-1,1,-1), n) + 0.5 * rnorm(4*n);
z <- as.factor(rep(c(1,2,3,4), n));
xor.example <- data.frame(z, x, y);
str(xor.example);
plot(xor.example$x, xor.example$y, col = xor.example$z, pch = 19, cex = 0.5);
    train <- 1:(2*n);
    lda.fit  <- lda(z~x+y,data=xor.example[train,])
    lda.pred <- predict(lda.fit, xor.example[-train,])$class
acc.4 <- sum(lda.pred == xor.example[-train,]$z)/(2*n)

z.2 <- as.factor(z == 1 | z == 4)
xor.example <- data.frame(z.2, x, y);
plot(xor.example$x, xor.example$y, col = xor.example$z.2, pch = 19, cex = 0.5);
    train <- 1:(2*n);
    lda.fit  <- lda(z.2~x+y,data=xor.example[train,])
    lda.pred <- predict(lda.fit, xor.example[-train,])$class
acc.2 <- sum(lda.pred == xor.example[-train,]$z)/(2*n)

Liran Katzir

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks Liran, this is the classical XOR example that a linear classifier cannot solve but union of classifiers can. Nevertheless, I was thinking more on algorithms which can learn ANY distribution such as Random Forest, Nearest Neighbour, Neural Networks, SVM + Kernel etc. $\endgroup$ – Hanan Shteingart Apr 8 '14 at 18:23
0
$\begingroup$

I found those two related papers:

| cite | improve this answer | |
$\endgroup$

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.