8

I have a data classification problem and I'm wondering what is the best machine learning approach to use for the particular constraints of my problem.

My constraints are as follows: - the data points are not linearly separable (in the original space) - I can generate as many training samples of either positive or negative labels - I would like to minimize the number of false positives (i.e. negative samples being wrongly classified as positives) - the classification speed needs to be very fast

I am currently using an SVM but it's not giving me result, particularly on speed. I posted a related question about my problem here: SVM model selection for datasets with sharp corners I'm still waiting for an answer on that, but I started questioning whether I'm even taking the right approach, which is why I've posted this as a separate question.

In case it's relevant, my problem is to use a classifier (or other ML method) as a fast approximate collision detection method (i.e. faster than doing exact collision detection)

Community
  • 1
maditya
  • 205
  • 3
  • 6

2 Answers2

6

Support Vector Machines classify new vectors by comparing them against the set of support vectors. Depending on what parameters you used and the cost function, this set of support vectors might be large. For more than two classes, the number of SVMs needed increases as well, further reducing performance. For better runtime performance, you'll want something that does all of the training upfront.

One such classifier is the neural network. It does all training upfront, leaving classifications as simple calculations. Another is a Bayesian classifier, which requires pdfs of the classes of your expected data. Only probabilities are calculated during classification, so its performance isn't affected by training set size.

If you need your classifier to further minimize the number of false positives at the risk of increasing the number of false negatives, then consider implementing a loss function. With it, you can assign a cost to each type of error. In your example, that means classifying fewer negatives as positives while allowing more positives as negatives. A clear example of loss functions is a test for cancer, where it's assumed to be better to falsely diagnose someone who doesn't have cancer and they live than it is to not diagnose someone who does and they die.

EDIT: Clarified SVM and Bayesian sections. Performance issue with SVMs is that there might be a large amount of SVs to check against new vectors. Generally, more SVs are used to increase fit to the training set (this is okay, but avoid overfitting). The Bayesian classifier simply requires that you know the distribution of your data.

Also, forgot that SVMs are built to only distinguish between 2 classes. To support more classes, multiple SVMs using the one-vs-all approach are merged. This would also impact runtime performance.

clintonmonk
  • 394
  • 1
  • 5
  • Thank you for your answer. It mostly makes sense but I'm a little confused by your line on doing all the training upfront. Does the basic SVM not do that? I don't believe new samples become part of the support vectors ... Secondly, under what circumstances would my data support Bayesian classifiers (or not)? Finally, since my data is not linearly separable, is it sufficient to increase the number of hidden nodes in the neural network for it to work? – maditya Apr 09 '13 at 20:23
  • You're right that new samples don't get added to the SVs, but you do still compare each sample against the set of SVs to see where it falls. My line about Bayesian classifiers meant that you need to have a distribution function for your training and expected data. Lastly, I'm not sure how many hidden nodes you'll need. This linked answer says to use a number between that of your input and output nodes, but you can always test different amounts: [link](http://stats.stackexchange.com/questions/181/how-to-choose-the-number-of-hidden-layers-and-nodes-in-a-feedforward-neural-netw). – clintonmonk Apr 09 '13 at 22:24
  • My data cannot be described using a probability model, so I think the neural network is probably (no pun intended) my best shot. Thank you for your answer and the link! – maditya Apr 09 '13 at 23:16
  • I am not aware why u cannot describe your data using a probability model. If you mean it is difficult to fit a distribution for it, then, just try Naive Bayes Classifier NBC with a Gaussian kernel. It usually performs good and extremely fast. – soufanom Apr 11 '13 at 09:31
3

I would recommend trying Random Ferns -- they are easy to implement, fast to train and even faster to predict, and due to ensemble structure you can easily control their speed/quality balance. Oh, and they are trivially parallel.
They may have problems with accuracy and memory consuption, though; but this depends on the problem and a way you make splits.