4
$\begingroup$

I'm currently trying to improve on a classifier. The current method used is a neural network, and the method I've found to be better is a random forest (or even just a single tree). With 40 trees, the classification is much better than the neural network. However, it takes 40 minutes(using 4 parallel workers due to running out of memory) to classify a large block of data; whereas, the neural network takes ~5 minutes(using 8 parallel workers). Is there a way to improve the speed of prediction? And does anyone know the reason for this huge slow down? I'm guessing it is due to the number of trees, and also the number of workers I can use.

MATLAB was used to create and run both the network and the forest.

40 features, 13 outputs, training set size: ~800,000, individual block size: ~500x500, whole file to be classfied: 1+GB along with other files containing more information

The data is not sparse.

$\endgroup$
  • 1
    $\begingroup$ Prediction-time scales in a linear way with the number of trees. The actual tree-depth is much more important here. Assuming the depth of the tree is O(log n), prediction costs O( ntree * n * log(n)). Prediction-complexity of NN should scale with the depth (#layers) their size. $\endgroup$ – sascha Jun 2 '16 at 14:38
  • $\begingroup$ Edit your question to add the following details: how many features you have, your sample size, and how large the "large blocks" are. $\endgroup$ – Kodiologist Jun 2 '16 at 15:49
  • $\begingroup$ Most probably it would be, because you are using high depth and large number of trees. $\endgroup$ – user2542275 Jun 3 '16 at 10:41
4
$\begingroup$

The comments are quite accurate, to summarize (and calling $p$ the number of simulateneous workers you have) the complexities should be (depending on the implementations) :

  • Random Forest : $O(n_{trees}*n* \log (n) / p)$
  • Neural Network : $O(n_{neurons}*size_{neurons}*n/p)$

The speed will also depend on the implementation, the $O$ just gives information about the scalability of the prediction part. The constant term omitted with the $O$ notations can be critical.

Indeed, you should expect random forests to be slower than neural networks.

To speed things up, you can try :

  • using other libraries (I have never used Matlab's random forest though)

  • reducing the depth of the trees (which will replace the $\log(n)$ by a constant term and allow you to use more workers - but this may harm the accuracy of the classifier)

  • check for duplicate features / constant columns in your data set and remove them (they do not improve accuracy and are responsible for a greater memory usage)

  • [Edit] is your data sparse ? I observed huge speed-ups using the "sparse" representations of the data (as long as the learning algorithms support it)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is great information, thanks! The data is not sparse and all of the features are carefully chosen. I'm in the process of finding a way to effectively reduce the complexity of the tree(depth,splits) without decreasing accuracy. I will look into other libraries, but this one seems to be the best suited. $\endgroup$ – Nicole Jun 3 '16 at 17:26
  • $\begingroup$ The h2o random forest is quite impressive. I like to use it via 'R', and using the "Flow" web interface. $\endgroup$ – EngrStudent Jun 3 '16 at 19:46
4
$\begingroup$

If tweaking the software and model architecture doesn't do the trick, there's another interesting approach. Say you have a large ensemble model (like a random forest) that has good prediction performance but slow runtime. It's possible to translate the ensemble model into a more efficient neural net. This paper describes how:

Bucila et al. (2006). Model compression.

The idea is to generate synthetic, unlabeled data that mimics the distribution of the training data. Arbitrarily many synthetic data points can be generated (e.g. more than in the original training set). Alternatively, real unlabeled data can be used if a source is readily available. The synthetic data is fed through the ensemble model to generate labels. The synthetic data and labels are then used to train a neural network.

Here's a talk by Geoff Hinton describing a similar approach.

| cite | improve this answer | |
$\endgroup$

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.