6 ms·

The often-overlooked random forest kernel

201 points by stablemap 9y ago

RMarcus 9y ago
I'm the author -- this is a technique to use a trained random forest as a kernel function for similar data. It can be used as a sort of primitive transfer learning, or just as a way to get a very high quality kernel for a (labeled) dataset. Happy to answer any questions!
- danharaj 9y ago
  In your mnist example, what is the relationship between all of the kernels you get for training to distinguish each pair of digit classes? Is there a natural way to intersect random forests or their kernels to get at their "common knowledge"? Is there a way to union them to get their "collective knowledge", and if so, how does that fare against an algorithm that learns all the classes simultaneously?
  - RMarcus 9y ago
    These are all great questions. The simplicity of the kernels produced might make them very amenable to analysis. I'm not sure I have the technical skills to do it though...
- stochastic_monk 9y ago
  Very interesting; I've ignored random forests more than I should. Thank you! I won't comment on your methods except to say that comparing classification over linear PCA against a kernel PCA in linearly unseparable data isn't exactly fair, and I think that providing an SVM performed on a different kernel PCA decomposition or a kernel SVM itself would be more illustrative. (Is your code available?) I generally think of neural networks as enormous meta-kernels. (Composites of <composites of...> kernels) This generally leads me to think of ways that kernels can be turned into neural network layers. Great work has been done turning powerful tools like Random Fourier Features/Kitchen Sinks into layers in neural networks (e.g., Alex Smola's Deep-Fried ConvNets [https://arxiv.org/abs/1412.7149 https://arxiv.org/abs/1412.7149] and Choromanski's Structured Adaptive/Random Spinners[https://arxiv.org/abs/1610.06209] https://arxiv.org/abs/1610.06209]). Deep Forest [https://arxiv.org/abs/1702.08835 https://arxiv.org/abs/1702.08835] is a method which claims to work well, but it's somewhat odd; It's not quite what I would have imagined. My biggest criticism of random forests is that the more expressive models are more memory-hungry and expensive at both training-time and run-time than many comparable methods. But bounded-complexity trees with smart implementations seem to be a lot more useful and have broader applications than I give them credit for.
  - RMarcus 9y ago
    I agree the comparison could be a lot more fair. My goal was to show how adding in labels can give you better principle components, but I should've used an RBF kernel, or some kind of unsupervised kernel, instead of linear PCA. I really should go and make the code available. I spent a lot of time writing the RF kernel in Cython to get it to be fast. But it is so fragile and incomplete, I'm not sure I am ready to release and maintain it. Maybe I'll just post the scripts. Thanks for the links and insights about ANNs as combined kernel learners + classifiers. I'll check out the papers (I'm also surprised at what Deep Forest is. Not what I was expecting.)
    - theSage 9y ago
      What were you expecting deep forests to be like?
- PaulHoule 9y ago
  Do you see this as being competitive with Siamese networks for one-shot learning?
  - RMarcus 9y ago
    I have no idea :). I don't think this approach is state of the art, but I think the advantages are that RFs are lightweight when compared to ANNs.
- j2kun 9y ago
  Do you have any insights as to why random forests are better (are they better?) in this context (or any context?) than boosted decision trees?
  - RMarcus 9y ago
    I've done no experiment, but I predict a boosted forest would perform poorly here. Since the first tree learns the majority of the information (and each of the following trees only fits the errors, and are therefore less "meaningful"). Since the kernel approach suggested here weights all the trees equally, the results probably won't be as good. Maybe if you gave the first trees more weight, though...
    - j2kun 9y ago
      > Maybe if you gave the first trees more weight, though That is exactly what boosting does...and one would weight the kernel computation in the same way.
zintinio5 9y ago
This is really awesome, thanks for posting! I was not yet aware that random forests could be used as kernels, and the link to Davies and Ghahramani is especially useful, definitely will read through later.
- amelius 9y ago
  That reference indeed seems very accessible.
srean 9y ago
Let me add another often-overlooked tweak that you can use with a random forest: applying random rotations before one learns the trees. This is extremely powerful. To give you some intuition on why this is so, recall that simple trees do axis parallel splits of the space. If the trees have to approximate an inclined line, they have to do a high resolution stair stepping to approximate it, -- like so -- __ | ------ | --------- |_______ this ends up requiring a lot of trees or a very deep one. Now if you equip the algorithm with a few inclined splits, which is exactly what a random rotations would do, you gain a lot of power.
- haeffin 9y ago
  How is that different from allowing non-axis-aligned splits?
  - tlarkworthy 9y ago
    its all much of a muchness. You can use a linear function at the nodes to project the space before applying a >. However, all these tweaks tend to just consume CPU for marginal benefit. You can still appoximate a non axis aligned decision boundary with a series of stepwise aligned splits, albeit less compactly. But if your aim is to just generate a ton of non linear distance functions ... a la random forest, focusing on tree expressivity is the wrong thing. Why not spend your CPU cycles on more trees instead instead, which leads to smoother decision boundaries in general when mixing their responses. There is a ton of tweaks you can do, but unless you are expressly researching ML algorithms, the pragmatist should not care and just try a few options from whatever comes in scipy.
  - srean 9y ago
    That is a very interesting question and one can go deep into the woods with that, not everything is known about this question. There are two distinct effects at play here, computational cost and learning efficiency. A brutally shortened response would be that searching for non-axis aligned splits in the nodes can be very expensive CPU wise. This addresses the first effect at play. Applying a random rotation on the other hand is quite cheap. The second effect at play is that ensembling loses its power when you optimize over oblique splits because of lost diversity. It comes down to a trade off.
jdonaldson 9y ago
This is a nice article, but there's some caveats with this approach that deserve a note: 1) Random forests are by nature supervised learners. They will completely ignore information that they can't use to predict their target output. This will have a big impact on any similarity scores derived from these types of models. At best, you'll see which observations the model considers to be similar in the training set (for the purposes of predicting the given output). This is still useful, but not as generalizable. 2) Even when considering the above, the distribution of splits is commonly skewed or biased in some way. The depth of the trees in the forest will vary. The distribution of training data at leaf nodes will vary. Categorical features may cause more splits than numeric features, etc. Some manner of re-weighting (a la information gain ratio) needs to be used to balance feature importance on the overall model behavior. I think this is a useful technique, and I would like to see more tree-based metrics used. The metrics just need some adjustments to account for all the distributional kinks in the trees, and the users need to know what kind of caveats are applicable for their data.
- tvladeck 9y ago
  > 1) Random forests are by nature supervised learners You can run unsupervised random forests. The way this procedure works is to first make a "copy" of the original dataset (the reason for the quotes will be evident in a second), and then train the forest to distinguish the original data from the copy with a binary target vector. The "copy" is made by sampling column-wise from the original dataset, so that, in the copy, each variable has the same univariate distribution as the original, but any interdependencies are destroyed. The forest then learns to distinguish the original from the copy, and the only information that it has at its disposal are interdependencies in the original dataset.
- RMarcus 9y ago
  Both good considerations! This approach can be used to build a kernel that measures the similarity of two items with respect to the labels learned by the forest. I don't doubt that the specific algorithm used to grow the forest. Luckily, any kernel made from any forest will have a positive semi-definite Gram matrix. But that doesn't mean it'll be a good one. I would summarize this approach as "learning a kernel that compares items w.r.t. the labels learned by the tree."

201 points by stablemap 9y ago

I'm the author -- this is a technique to use a trained random forest as a kernel function for similar data. It can be used as a sort of primitive transfer learning, or just as a way to get a very high quality kernel for a (labeled) dataset. Happy to answer any questions!

danharaj 9y ago
In your mnist example, what is the relationship between all of the kernels you get for training to distinguish each pair of digit classes? Is there a natural way to intersect random forests or their kernels to get at their "common knowledge"? Is there a way to union them to get their "collective knowledge", and if so, how does that fare against an algorithm that learns all the classes simultaneously?
- RMarcus 9y ago
  These are all great questions. The simplicity of the kernels produced might make them very amenable to analysis. I'm not sure I have the technical skills to do it though...
stochastic_monk 9y ago
Very interesting; I've ignored random forests more than I should. Thank you! I won't comment on your methods except to say that comparing classification over linear PCA against a kernel PCA in linearly unseparable data isn't exactly fair, and I think that providing an SVM performed on a different kernel PCA decomposition or a kernel SVM itself would be more illustrative. (Is your code available?) I generally think of neural networks as enormous meta-kernels. (Composites of <composites of...> kernels) This generally leads me to think of ways that kernels can be turned into neural network layers. Great work has been done turning powerful tools like Random Fourier Features/Kitchen Sinks into layers in neural networks (e.g., Alex Smola's Deep-Fried ConvNets [https://arxiv.org/abs/1412.7149 https://arxiv.org/abs/1412.7149] and Choromanski's Structured Adaptive/Random Spinners[https://arxiv.org/abs/1610.06209] https://arxiv.org/abs/1610.06209]). Deep Forest [https://arxiv.org/abs/1702.08835 https://arxiv.org/abs/1702.08835] is a method which claims to work well, but it's somewhat odd; It's not quite what I would have imagined. My biggest criticism of random forests is that the more expressive models are more memory-hungry and expensive at both training-time and run-time than many comparable methods. But bounded-complexity trees with smart implementations seem to be a lot more useful and have broader applications than I give them credit for.
- RMarcus 9y ago
  I agree the comparison could be a lot more fair. My goal was to show how adding in labels can give you better principle components, but I should've used an RBF kernel, or some kind of unsupervised kernel, instead of linear PCA. I really should go and make the code available. I spent a lot of time writing the RF kernel in Cython to get it to be fast. But it is so fragile and incomplete, I'm not sure I am ready to release and maintain it. Maybe I'll just post the scripts. Thanks for the links and insights about ANNs as combined kernel learners + classifiers. I'll check out the papers (I'm also surprised at what Deep Forest is. Not what I was expecting.)
  - theSage 9y ago
    What were you expecting deep forests to be like?
PaulHoule 9y ago
Do you see this as being competitive with Siamese networks for one-shot learning?
- RMarcus 9y ago
  I have no idea :). I don't think this approach is state of the art, but I think the advantages are that RFs are lightweight when compared to ANNs.
j2kun 9y ago
Do you have any insights as to why random forests are better (are they better?) in this context (or any context?) than boosted decision trees?
- RMarcus 9y ago
  I've done no experiment, but I predict a boosted forest would perform poorly here. Since the first tree learns the majority of the information (and each of the following trees only fits the errors, and are therefore less "meaningful"). Since the kernel approach suggested here weights all the trees equally, the results probably won't be as good. Maybe if you gave the first trees more weight, though...
  - j2kun 9y ago
    > Maybe if you gave the first trees more weight, though That is exactly what boosting does...and one would weight the kernel computation in the same way.

zintinio5 9y ago

This is really awesome, thanks for posting! I was not yet aware that random forests could be used as kernels, and the link to Davies and Ghahramani is especially useful, definitely will read through later.

amelius 9y ago
That reference indeed seems very accessible.

srean 9y ago

Let me add another often-overlooked tweak that you can use with a random forest: applying random rotations before one learns the trees. This is extremely powerful. To give you some intuition on why this is so, recall that simple trees do axis parallel splits of the space. If the trees have to approximate an inclined line, they have to do a high resolution stair stepping to approximate it, -- like so -- __ | ------ | --------- |_______ this ends up requiring a lot of trees or a very deep one. Now if you equip the algorithm with a few inclined splits, which is exactly what a random rotations would do, you gain a lot of power.

haeffin 9y ago
How is that different from allowing non-axis-aligned splits?
- tlarkworthy 9y ago
  its all much of a muchness. You can use a linear function at the nodes to project the space before applying a >. However, all these tweaks tend to just consume CPU for marginal benefit. You can still appoximate a non axis aligned decision boundary with a series of stepwise aligned splits, albeit less compactly. But if your aim is to just generate a ton of non linear distance functions ... a la random forest, focusing on tree expressivity is the wrong thing. Why not spend your CPU cycles on more trees instead instead, which leads to smoother decision boundaries in general when mixing their responses. There is a ton of tweaks you can do, but unless you are expressly researching ML algorithms, the pragmatist should not care and just try a few options from whatever comes in scipy.
- srean 9y ago
  That is a very interesting question and one can go deep into the woods with that, not everything is known about this question. There are two distinct effects at play here, computational cost and learning efficiency. A brutally shortened response would be that searching for non-axis aligned splits in the nodes can be very expensive CPU wise. This addresses the first effect at play. Applying a random rotation on the other hand is quite cheap. The second effect at play is that ensembling loses its power when you optimize over oblique splits because of lost diversity. It comes down to a trade off.

jdonaldson 9y ago

This is a nice article, but there's some caveats with this approach that deserve a note: 1) Random forests are by nature supervised learners. They will completely ignore information that they can't use to predict their target output. This will have a big impact on any similarity scores derived from these types of models. At best, you'll see which observations the model considers to be similar in the training set (for the purposes of predicting the given output). This is still useful, but not as generalizable. 2) Even when considering the above, the distribution of splits is commonly skewed or biased in some way. The depth of the trees in the forest will vary. The distribution of training data at leaf nodes will vary. Categorical features may cause more splits than numeric features, etc. Some manner of re-weighting (a la information gain ratio) needs to be used to balance feature importance on the overall model behavior. I think this is a useful technique, and I would like to see more tree-based metrics used. The metrics just need some adjustments to account for all the distributional kinks in the trees, and the users need to know what kind of caveats are applicable for their data.

tvladeck 9y ago
> 1) Random forests are by nature supervised learners You can run unsupervised random forests. The way this procedure works is to first make a "copy" of the original dataset (the reason for the quotes will be evident in a second), and then train the forest to distinguish the original data from the copy with a binary target vector. The "copy" is made by sampling column-wise from the original dataset, so that, in the copy, each variable has the same univariate distribution as the original, but any interdependencies are destroyed. The forest then learns to distinguish the original from the copy, and the only information that it has at its disposal are interdependencies in the original dataset.
RMarcus 9y ago
Both good considerations! This approach can be used to build a kernel that measures the similarity of two items with respect to the labels learned by the forest. I don't doubt that the specific algorithm used to grow the forest. Luckily, any kernel made from any forest will have a positive semi-definite Gram matrix. But that doesn't mean it'll be a good one. I would summarize this approach as "learning a kernel that compares items w.r.t. the labels learned by the tree."