6
$\begingroup$

I'm interested in exploring autoencoders which can be used to develop a compressed representation of data useful for machine learning.

In my experience random forests are easier to work with and more flexible than linear models and so I'd like to try to use them to build an autoencoder.

One might do this by using random forests to predict multiple outcomes then re-represent each data point as a binary sequence corresponding to the braches that it took. For example if a forest consisted of two trees with three branches then the code 011 101 would represent a datapoint that took the second and third branches of the first tree and took the first and third branch of the second tree.

Is anyone familiar with work like this? I am interested in papers, implementations of multi-outcome random forests, and techniques that convert random forests into binary representations of data points.

Edit: clarifying

$\endgroup$
  • $\begingroup$ Sounds interesting, but because the random forest does not guarantee the same results each iteration, I'm not sure how this would guarantee a fixed encoding/decoding relationship to each party. It might be possible to use some kind of denoiser as mentioned on your link? $\endgroup$ – pat Jan 3 '13 at 20:57
  • $\begingroup$ @pat, I don't see the trouble. Once a forest is fully trained it does not evolve. For example a given forest will make consistent predictions and has a fixed set of trees and branch points. Maybe I don't understand your point. $\endgroup$ – Ben Haley Jan 3 '13 at 21:04
  • 1
    $\begingroup$ If two people run the a random forest on the same dataset, they are not guaranteed to have the same generated tree structure. How would the decoding party know the proper lookup table to decode the data with this uncertainty? Secondly, conditions about what stops the training also have to be taken into consideration (ntrees, etc). $\endgroup$ – pat Jan 3 '13 at 21:11
  • 1
    $\begingroup$ Oh, I think we don't agree on the meaning of autoencoder. I am assuming that a single machine is performing both encoding and decoding and that the compressed encoding layer is being used to help in a classification problem. I will clarify my question to make this clear. Thanks! $\endgroup$ – Ben Haley Jan 3 '13 at 21:13
  • $\begingroup$ One thing that Brieman tried was at each split, we take a subset of features and try various linear combinations on these different subsets, with random weights. Pick the best linear combination to determine split. These are naturally sparse since only a small number of variables are given non-zero weights in every linear combination attempt. This was from his original random forests paper in 2001. $\endgroup$ – Jase Feb 8 '14 at 10:22
2
$\begingroup$

You can use the 1-hot encoding - for a single tree, each example is represented by a vector containing 1 with the selected leaf, and combine these vectors for a forest (either concatenated or OR'ed). This gives you an intermediate representation.

Another option is to use the proximity measure [1] to compute an unsupervised sparse feature representation- a matrix M where M_ij = #times examples i,j terminated in the same leaf (over the entire forest). This matrix is sparse and large but you can reduce its size.

Do either of those give a useful intermediate representation? I don't know of any attempts at deep learning with random forests..

[1] http://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm#prox

$\endgroup$
  • $\begingroup$ Yeah that's really useful, thanks Andy! Since I wrote this I actually have played with the leaf representation you propose. I have a little R code that can convert from gbm to a leaf representation. Let me know if you'd like a copy. $\endgroup$ – Ben Haley May 15 '13 at 15:59
  • $\begingroup$ How did you use the leaf representation in an auto encoder? $\endgroup$ – Andy Twigg May 15 '13 at 16:09
  • $\begingroup$ Well basically I added random noise to the data, and built a gbm model for each feature to predict its original value using the noisy data. Then I pulled the leaf representation for each of these gbm's and called them the new representation for the data. Not a very good one, however, because this representation was too wide. I tried shrinking it using PCA, but I could have not shown that this new representation is any better than the original for practical purposes. $\endgroup$ – Ben Haley May 15 '13 at 18:09
  • $\begingroup$ Did you use one forest per feature, or multivariate trees? Why is being 'too wide' a problem? Did you try feeding this representation into another random forest to get a 'deep' network? $\endgroup$ – Andy Twigg May 16 '13 at 21:00
  • $\begingroup$ Yeah one forest per feature. I would have much preferred multivariate trees, but I could not find a fast implementation. Wide becomes a problem because processing becomes slow. I did try adding a second tier of random forest to get a 'deep' network, but it wasn't able to predict my outcome any better. $\endgroup$ – Ben Haley May 17 '13 at 15:45
2
$\begingroup$

Maybe a little late but...

Ji Feng and Zhi-Hua Zhou (2017) have recently proposed an autoencoder model based on tree ensembles.

They learn a random forest or build a "completely-random forest" for the encoder part. To decode it, they follow tree branchs backward from leaves to the root which gives a series of rules from which they extract the Maximal-Compatible Rule. Then, using this rule, they are able to more or less precisely reconstruct the input.

PS: It could be noted that Biau et al. (2016) showed that tree-ensembles could be seen as a two-layer perceptron. It may be interesting to see the Forest Autoencoder with this scope.

$\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.