SVM model selection for datasets with sharp corners

Question

I'm working with an artificially generated dataset that is separated by many sharp corners. As an example, imagine an H-shape in a 3D (or higher-dimensional) space. Points within the H are positive, points outside are negative. In my application, many new points will be generated at runtime. I would like to classify them as being inside the H-shape or not.

I currently do an exact check for these points using standard collision detection methods, but since this is proving expensive I would like to do much faster classification at the expense of some accuracy. For instance, 90-95% correct classifications at an order of magnitude or more faster speed than exact checking is ideal for me.

I'm using an SVM with the radial basis function (RBF) kernel since my dataset is not linearly separable in the original space. I've trained it using grid-search on the parameters gamma and nu, with 3-fold cross validation, varying both the range and granularity of the search. However, the best I can do is about 80-85% accuracy, and a running time of 6-10s for 100,000 new datapoints, which is about the same time as it takes to do the exact check.

Where am I going wrong? I particularly suspect that the RBF is poor at handling sharp corners (e.g. the H-shape that I described, whose boundary separates positive and negative points). Should I be using a different kernel that is more suited to these parameters? Should I use some combination of kernels? Should I do some form of region decomposition, and train separate kernels for each region? Should I be using a different ML approach (e.g. neural networks) instead?

Answer 1

I think a tree-based method, such as random forest or GBM would be work for this problem.

This does NOT seem like a problem where an SVM would be immediately applicable. "Sharp Corners" just screams "trees" at me, as they excel at detecting thresholds and interactions. Maybe try a simple decision tree, and compare the speed and accuracy to your SVM.

/edit: Here's a quick example dataset with an H:

#Random sample of data
rm(list = ls(all = TRUE)) 
set.seed(42)
n <- 1000
fuzz <- .1
x <- runif(n)
y <- runif(n)

#Generate an H
target <- rep('No', n)
target[x < .1-rnorm(n)*fuzz] <- 'Yes'
target[x > .9-rnorm(n)*fuzz] <- 'Yes'
target[(y > .45-rnorm(n)*fuzz) & (y < .55-rnorm(n)*fuzz)] <- 'Yes'
target <- factor(target)
plot(x, y, col=target, pch=16)

We can fit a few different binary classification models to this data using the caret package:

library(caret)
myControl <- trainControl(
  method='boot',
  number=25,
  index=createResample(target, 25),
  classProbs=TRUE,
  summaryFunction=twoClassSummary
  )
dat <- data.frame(x, y, target)
model_linear <- train(target~., dat, method='lda', metric='ROC', trControl=myControl)
model_svm <- train(target~., dat, method='svmRadial', metric='ROC', trControl=myControl)
model_rpart <- train(target~., dat, method='rpart', metric='ROC', trControl=myControl)
model_rf <- train(target~., dat, method='rf', metric='ROC', trControl=myControl)
model_gbm <- train(target~., dat, method='gbm', metric='ROC', trControl=myControl)

A quick plot of the out-of-sample area under the ROC Curve for each model shows that you might want to try a GBM on your dataset (though the SVM does surprisingly well). If you set the fuzz parameter smaller, the tree-based methods will start to greatly outperform the SVM:

all.models <- list(
  linear=model_linear,
  svm=model_svm,
  tree=model_rpart,
  forest=model_rf,
  boost=model_gbm
)
results <- resamples(all.models)
dotplot(results, metric='ROC')

Finally, it appears the GBM fits faster than the SVM (on this dataset)

> sort(sapply(all.models, function(x) x$times$final['elapsed']))
linear.elapsed   tree.elapsed  boost.elapsed    svm.elapsed forest.elapsed 
          0.00           0.00           0.06           0.25           0.39