Can a nuisance multi-class classifier do better than binary classifier? 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.
 A: 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. 
A: #####################################################
# 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
A: I found those two related papers:


*

*"Can subclasses help a multiclass learning problem?", by Yun Luo, and

*"Using subclasses to improve classification learning", by Achim Hoffmann, Rex Kwok and Paul Compton.

