1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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)

H

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

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 
$\endgroup$
  • $\begingroup$ Thank you for the detailed answer. I really should have tried decision trees first instead of going directly to SVMs. Unfortunately I don't have access to a C++ implementation of the GBM, but just the decision tree seems to be good enough and fast enough for what I need. Also, your "fuzz" parameter defines how much the samples are likely to overlap, yes? In my case, the training samples will not overlap at all so I think this is good news for me. $\endgroup$ – maditya Apr 10 '13 at 0:17
  • $\begingroup$ @maditya: yes, that's what the fuzz parameter does. If you have access to a good library for decision trees, random forests are actually pretty easy to implement. Just fit ~100 decision trees, and average their predictions. Give each one a bootstrap sample of your original dataset, as well 2 randomly selected predictor variables. GBMs are harder. $\endgroup$ – Zach Apr 10 '13 at 1:06
  • $\begingroup$ Actually I found the Shark ML library (image.diku.dk/shark/sphinx_pages/build/html/index.html) for C++, which has an implementation for random forests. So I'll probably go with that for now (I'm working on a thesis and I need to finish soon). Thanks again for your help! $\endgroup$ – maditya Apr 10 '13 at 2:15

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.