The Unreasonable Effectiveness of Random Forests • Hacker News Board

Re: The Unreasonable Effectiveness of Random Forests

#21

Post by reagency » Sat, Sep 19, 2015, 4:25 PM UTC

chestervonwinch wrote: post #16

I'm surprised the author didn't mention model variance reduction, which is what RFs were designed to do. For example, if we generate 100 data sets which are the same except for noise, the 100 decision boundaries drawn by a classification tree will vary much more than the decision boundaries drawn by RFs on the same sets. Here's what this means visually: http://i.imgur.com/IjfXFkm.png There is just one of the 100 data…

Hmm, those CT boundaries aren't just high variance, they have extremely high error, which seems a more significant problem. They are linear!

Re: The Unreasonable Effectiveness of Random Forests

#22

Post by chestervonwinch » Sat, Sep 19, 2015, 4:50 PM UTC

reagency wrote: post #21

chestervonwinch wrote: post #16

I'm surprised the author didn't mention model variance reduction, which is what RFs were designed to do. For example, if we generate 100 data sets which are the same except for noise, the 100 decision boundaries drawn by a classification tree will vary much more than the decision boundaries drawn by RFs on the same sets. Here's what this means visually: http://i.imgur.com/IjfXFkm.png There is just one of the 100 data…

Hmm, those CT boundaries aren't just high variance, they have extremely high error, which seems a more significant problem. They are linear!

Each CT has zero error on its training set. The overall structure in each training set is the same (shown by the circles and triangles). Each CT, however, fits to the noise that is specific each training set. This causes the "linear" regions you mention. This is caused by how CTs recursively subdivide the feature space - these are essentially small subdivision areas fit to noise, which have extended beyond the class region to which they "should" belong.

Re: The Unreasonable Effectiveness of Random Forests

#23

Post by daenz » Sat, Sep 19, 2015, 5:15 PM UTC

Random forests are great. I use them in real-time silhouette identification of people against backgrounds by porting the random forest to the GPU. This allows blazing fast forest evaluation for every pixel of my input image concurrently. I used this paper to implement the design of it http://www.msr-waypoint.com/pubs/71445/ForestFire.pdf

The main trick is in storing the tree as a binary heap in the rows of a texture, with the left and right subtrees at 2i and 2i+1, respectively, and where the attribute index and split value are encoded in the color channels. Your texture width is your tree depth^2-1, and your texture height the number of trees in your forest. The texture ends up looking something like this (scaled up x10) http://i.imgur.com/afH5iFl.png

With a GPU shader, you can navigate these trees very quickly to classify an entire input image at once.

Re: The Unreasonable Effectiveness of Random Forests

#24

Post by ScottBurson » Sat, Sep 19, 2015, 5:49 PM UTC

Here's an interesting paper on learning methods for high-dimensional data: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.149...

The abstract:

In this paper we perform an empirical evaluation of supervised learning on high-dimensional data. We evaluate performance on three metrics: accuracy, AUC, and squared loss and study the effect of increasing dimensionality on the performance of the learning algorithms. Our findings are consistent with previous studies for problems of relatively low dimension, but suggest that as dimensionality increases the relative performance of the learning algorithms changes. To our surprise, the method that performs consistently well across all dimensions is random forests, followed by neural nets, boosted trees, and SVMs.

Re: The Unreasonable Effectiveness of Random Forests

#25

Post by CyberDildonics » Sat, Sep 19, 2015, 6:44 PM UTC

ajtulloch wrote: post #3

The article mentions that "The main drawback of Random Forests is the model size. You could easily end up with a forest that takes hundreds of megabytes of memory and is slow to evaluate." A cool trick for speeding up trained random forests/gradient boosted decision trees is to dump the tree to C/ASM, compile it, and dlopen it as a function pointer. Depending on the model and the architecture, you can get an 8x speed…

Why go through all that though? The fundamental principle is that it is flattening the buffer to one linear section of memory, making the pointers jump to a location that is likely already prefetched and possibly in the same cache line. Dumping to C seems like it is missing the point.

A library like Cereal should be able to do this almost trivially simply by serializing the data, unserializing it to a flat buffer, then pointing to the start of that buffer.

Also I should say that a random forest created by pointer hopping to each new level is a very naive implementation and will take a long time to create due to heap allocation and a long time to traverse due to cache misses.

Re: The Unreasonable Effectiveness of Random Forests

#26

Post by ScottBurson » Sat, Sep 19, 2015, 6:53 PM UTC

ScottBurson wrote: post #24

Here's an interesting paper on learning methods for high-dimensional data: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.149... The abstract: In this paper we perform an empirical evaluation of supervised learning on high-dimensional data. We evaluate performance on three metrics: accuracy, AUC, and squared loss and study the effect of increasing dimensionality on the performance of the learning algorithms…

Another paper comparing classifier methods, that also concludes RF is one of the best: http://jmlr.org/papers/volume15/delgado14a/delgado14a.pdf

Re: The Unreasonable Effectiveness of Random Forests

#27

Post by joe_the_user » Sat, Sep 19, 2015, 6:56 PM UTC

ajtulloch wrote: post #3

The article mentions that "The main drawback of Random Forests is the model size. You could easily end up with a forest that takes hundreds of megabytes of memory and is slow to evaluate." A cool trick for speeding up trained random forests/gradient boosted decision trees is to dump the tree to C/ASM, compile it, and dlopen it as a function pointer. Depending on the model and the architecture, you can get an 8x speed…

Mmmm,

Yeah, as I understand it, the enthusiasm for deep learning comes because it scales well to truly huge data sets where most other machine learning algorithms tend to create artifacts of a similar size to the data in question.

That is to say that deep learning, random trees and SVMs all do approximately the same thing - non-linear regression, equivalently regression on a feature space, roughly drawing curves between two sets on huge dimensional space and using these curves for distinguishing objects.

Also - the linked paper giving all the actual details of the algorithm seems unresponsive.

This link worked for me:

https://www.stat.berkeley.edu/~breiman/randomforest2001.pdf

Re: The Unreasonable Effectiveness of Random Forests

#28

Post by thomyorkie » Sat, Sep 19, 2015, 7:15 PM UTC

xiler wrote: post #5

nl wrote: post #2

This is so true. Random forest should be the default choice for most problem sets. Now we have The Unreasonable Effectiveness of Random Forests and The Unreasonable Effectiveness of Recurrent Neural Networks . We just need The Unreasonable Effectiveness of XGBoost (for winning Kaggle competitions) and we'll have the whole set. [1] http://karpathy.github.io/2015/05/21/rnn-effectiveness/

Another one is The Unreasonable Effectiveness of Deep Learning [1] by LeCun. [1] http://on-demand.gputechconf.com/gtc/2014/webinar/gtc-expres...

Here's a poor quality recording of LeCun's presentation https://www.youtube.com/watch?v=sc-KbuZqGkI&list=PL513vUSBNc...

Re: The Unreasonable Effectiveness of Random Forests

#29

Post by andosa » Sat, Sep 19, 2015, 7:24 PM UTC

stared wrote: post #7

I share the awe of RF (especially as they look naive, but turn out to be extremely good for a wide range of problems), however, the main problem is that they are black boxes. Typically, it is easy to get good results, but almost no insight, or further pointers. Many times I ended up using linear regression (with properly engineered variables), or something as simple, because it gave almost as good results as RF, but…

Random forests being black boxes is something that is widely touted even among active practitioner, but not really true any more. There are methods available for decomposing random forest predictions into feature contributions, so that each prediction is represented as the sum of the bias term and contribution from each feature (similar to what you get in linear regression, but at the level of each individual prediction instead of one for the whole model), see for example http://blog.datadive.net/interpreting-random-forests/. Also there are methods for extracting, pruning and summarizing random forest rules to make them human readable, see for example inTrees package in R.

Re: The Unreasonable Effectiveness of Random Forests

#30

Post by SwellJoe » Sat, Sep 19, 2015, 7:24 PM UTC

Any recommendations for beginner materials about this and other modeling and machine learning topics? I worked for a few years with the folks behind SciPy and NumPy and iPython, and helped package the suite of tools many use for this kind of work, and so I have quite a bit of familiarity with the tools for experimenting with this stuff, but I never dug into the math and I'm not even sure where to start on it.