Extending 2-class models to multi-class problems

This paper on Adaboost gives some suggestions and code (page 17) for extending 2-class models to K-class problems. I would like to generalize this code, such that I can easily plug in different 2-class models and compare the results. Because most classification models have a formula interface and a predict method, some of this should be relatively easy. Unfortunately, I haven't found a standard way of extracting class probabilities from 2-class models, so each model will require some custom code.

Here's a function I wrote to break up a K-class problem into 2-class problems, and return K models:

oneVsAll <- function(X,Y,FUN,...) {
models <- lapply(unique(Y), function(x) {
name <- as.character(x)
.Target <- factor(ifelse(Y==name,name,'other'), levels=c(name, 'other'))
dat <- data.frame(.Target, X)
model <- FUN(.Target~., data=dat, ...)
return(model)
})
names(models) <- unique(Y)
info <- list(X=X, Y=Y, classes=unique(Y))
out <- list(models=models, info=info)
class(out) <- 'oneVsAll'
return(out)
}


Here's a prediction method I wrote to iterate over each model and make predictions:

predict.oneVsAll <- function(object, newX=object$info$X, ...) {
stopifnot(class(object)=='oneVsAll')
lapply(object$models, function(x) { predict(x, newX, ...) }) }  And finally, here's a function to turn normalize a data.frame of predicted probabilities and classify the cases. Note that it is up to you to construct the K-column data.frame of probabilities from each model, as there is not a unified way to extract class probabilities from a 2-class model: classify <- function(dat) { out <- dat/rowSums(dat) out$Class <- apply(dat, 1, function(x) names(dat)[which.max(x)])
out
}


Here's an example using adaboost:

library(ada)
library(caret)
X <- iris[,-5]
Y <- iris[,5]
preds <- predict(myModels, X, type='probs')
preds <- data.frame(lapply(preds, function(x) x[,2])) #Make a data.frame of probs
preds <- classify(preds)
>confusionMatrix(preds$Class, Y) Confusion Matrix and Statistics Reference Prediction setosa versicolor virginica setosa 50 0 0 versicolor 0 47 2 virginica 0 3 48  Here is an example using lda (I know lda can handle multiple classes, but this is just an example): library(MASS) myModels <- oneVsAll(X, Y, lda) preds <- predict(myModels, X) preds <- data.frame(lapply(preds, function(x) x[[2]][,1])) #Make a data.frame of probs preds <- classify(preds) >confusionMatrix(preds$Class, Y)
Confusion Matrix and Statistics

Reference
Prediction   setosa versicolor virginica
setosa         50          0         0
versicolor      0         39         5
virginica       0         11        45


These functions should work for any 2-class model with a formula interface and a predict method. Note that you have to manually split up the X and Y components, which is a little ugly, but writing a formula interface is beyond me at the moment.

Does this approach make sense to everyone? Is there any way I can improve it, or is there an existing package to solve this issue?

-
Wow, until you asked and I looked, I'd have been sure that some package (like car, or one of the *lab packages) would have provided a function like yours. Sorry I can't help. I've read a bit about how k-way SVM works and it seems like it was more complicated than I'd have thought. – Wayne Feb 14 '12 at 22:06
@Wayne: Me too! I was certain there'd be some general function that would do this, provided the model has a predict method. – Zach Feb 15 '12 at 14:18

As for existing packages, glmnet supports (regularized) multinomial logit which can be used as a multi-class classifier.
 I'm aware of the many packages in R that support multi-class classification (such as glmnet, random forests, kernlab, rpart, nnet, etc.). I'm more curious about extending binary classification packages (e.g. gbm) to multiclass problems. I'll look into "weighted all pairs." – Zach Feb 15 '12 at 14:16 Also, it's interesting that glmnet includes a multinomial loss function. I wonder if this loss function could be used in other algorithms in R, such as ada or gbm? – Zach Mar 22 '12 at 17:59 Yes, some methods can be extended to support multinomial loss function. For example, kernel logistic regression is extended that way here: books.nips.cc/papers/files/nips14/AA13.pdf As far as know ada is "reserved" for a specific (exponential) loss function, but one could extend another boosting-based method to support the multinomial loss function - e.g. see page 360 of The Elements of Statistical Learning for details on multi-class GBM - K binary trees are built for each boosting iteration where K is the number of classes (just one tree per iteration is needed in binary case). – Yevgeny Mar 23 '12 at 21:38