Live data from Hacker News

Decision trees – the unreasonable power of nested decision rules

mlu-explain.github.io

41–50 of 89 posts

Re: Decision trees – the unreasonable power of nested decision rules

#41
post #26

Earlier quoted context omitted.

I missed a word "recursively", that I have edited in my original comment now. Consider connected regions in the domain that have the same label. Much like countries on a political map. The situation where this has a short description in terms of recursive subdivision of space, is what I am calling a partitioned structure. It's really rather tautological.

"recursively partitioned" sounds like a fractal to me. Not sure what you really mean.

Taken to the limit you are absolutely right.

It turns out many dataset have such a fractal like nature but where the partitioning needs to be cut off at a certain depth and not continued till infinity.

Re: Decision trees – the unreasonable power of nested decision rules

#42
post #4
post #2

Interesting website and great presentation. My only note is that the color contrast of some of the text makes it hard to read.

exactly my thought. and here thr reader view of FF is a godsend. having 'accessible' content is not only for people with disabilities, it also help with bad color taste. well, at least bad taste for readable content ;)

The FF reader view here starts from "We just saw how a Decision Tree", gobbling up half the article. Simply disabling CSS works better. Though in both cases, it seems that ordering might be a bit mixed up.

Re: Decision trees – the unreasonable power of nested decision rules

#43
post #22

Earlier quoted context omitted.

I think data frames are quite memory efficient and can store non-uniform data types (as can vectors in Guile). Generally, a ton of work has gone into making operations on data frames fast. I don't think a normal vector or multi-dimensional array can easily compete. Data frames are probably also compiled to some quite efficient machine code. Not sure whether Guile's native data structures can match that. Maybe they ca…

For linear algebraic transformation applied to several rows at once, I wholeheartedly agree. Not so convinced about decision trees though (that process one row at a time). Yeah, unless you had to deal with arbitrarily large integer features, Guile integers would come with a big efficiency hit.

What do you mean by processing one row at a time?

I think one could parallelize processing rows, at the very least when classifying from learned model. Probably also during learning the model.

Re: Decision trees – the unreasonable power of nested decision rules

#44
post #22

Earlier quoted context omitted.

For linear algebraic transformation applied to several rows at once, I wholeheartedly agree. Not so convinced about decision trees though (that process one row at a time). Yeah, unless you had to deal with arbitrarily large integer features, Guile integers would come with a big efficiency hit.

What do you mean by processing one row at a time? I think one could parallelize processing rows, at the very least when classifying from learned model. Probably also during learning the model.

Yes you can certainly do that.

What I had not articulated well is that linear classifiers have the opportunity to use matvecs that have a different level of L1 L2 cacheable goodness and non-branchy code. There using proper memory layout gives an outstanding win. The win for decision trees are less impressive in comparison, so you needn't be feeling bad about your code.

Re: Decision trees – the unreasonable power of nested decision rules

#45
post #19

A 'secret weapon' that has served me very well for learning classifiers is to first learn a good linear classifier. I am almost hesitant to give this away (kidding). Use the non-thresholded version of that linear classifier output as one additional feature-dimension over which you learn a decision tree. Then wrap this whole thing up as a system of boosted trees (that is, with more short trees added if needed). One of…

I think it's worth mentioning, that the achilles heel of DT, is in fact, data (more specifically feature) engineering. If one does not spend significant time cleaning and engineering the features, the results would be much worse than, say a "black box" model, like NN. This is the catch. Ironically, NN can detect such latent features, but very difficult to interpret why.

Re: Decision trees – the unreasonable power of nested decision rules

#47
post #45
post #19

A 'secret weapon' that has served me very well for learning classifiers is to first learn a good linear classifier. I am almost hesitant to give this away (kidding). Use the non-thresholded version of that linear classifier output as one additional feature-dimension over which you learn a decision tree. Then wrap this whole thing up as a system of boosted trees (that is, with more short trees added if needed). One of…

I think it's worth mentioning, that the achilles heel of DT, is in fact, data (more specifically feature) engineering. If one does not spend significant time cleaning and engineering the features, the results would be much worse than, say a "black box" model, like NN. This is the catch. Ironically, NN can detect such latent features, but very difficult to interpret why.

That has not been my experience though, apart from the need of standard data hygiene that one has to maintain for any ML exercise.

Normalising the numeric features to a common range has been adequate. This too is strictly not necessary for DTs, but pretty much mandatory for linear models. (DTs are very robust to scale differences among features, linear models quite vulnerable to the same.)

One can think of each tree path from root to leaf as a data driven formulation/synthesis of a higher level feature built out of logical conjunctions ('AND' operation).

These auto-synthesized / discovered features are then ORed at the top. DTs are good at capturing multi-feature interactions that single layer linear models can't.

NNs certainly synthesize higher level features, but what does not get highlighted enough is that learning-theory motivated Adaboost algorithm and it's derivatives do that too.

Their modus operandi is "BYOWC, bring your own weak classifier, I will reweigh the data in such a way that your unmodified classifier will discover a higher level feature on its own. Later you can combine these higher features linearly, by voting, or by averaging".

I personally favor differentiable models over trees, but have to give credit where it's due, DTs work great.

What leaves me intellectually unsatisfied about decision trees is that the space of trees cannot be searched in any nice principled way.

Or to describe in terms of feature discovery, in DT, there's no notion of progressing smoothly towards better high level features that track the end goal at every step of this synthesis (in fact greedy hill climbing hurts performance in the case of decision trees). DTs use a combinatorial search over the feature space partitioning, essentially by trial and error.

Neural nets have a smooth way of devising these higher level features informed by the end goal. Roll infinitesimally in the direction of steepest progress -- that's so much more satisfying than trial and error.

As for classification performance where DT have struggled are cases where columns are sparse (low entropy to begin with).

Another weakness of DT is the difficulty of achieving high throughput runtime performance, unless the DT is compiled into machine code. Walking a runtime tree structure with not so predictable branching probabilities that doe'snt run very fast on our standard machines. Compared to DNNs though this is a laughable complaint, throughput of DTs are an order of one or two faster.

Re: Decision trees – the unreasonable power of nested decision rules

#48

When I worked at CERN around 2010, Boosted Decision Trees were the most popular classifier, exactly due to the (potential for) explainability along with its power of expression. We had a cultural aversion for neural networks back then, especially if the model was used in physics analysis directly. Times have changed…

I used to be in physics but theory, not experiment. I have experience at work with decision trees in a different field.

I've always thought that the idea that decision trees are "explainable" is very overstated. The moment that you go past a couple of levels in depth, it becomes an un-interpretable jungle. I've actually done the exercise of inspecting how a 15-depth decision trees makes decision, and I found it impossible to interpret anything.

In a neural network you can also follow the successive matrix multiplications and relu etc through the layers, but you end up not knowing how the decision is made.

Thoughts?

Re: Decision trees – the unreasonable power of nested decision rules

#49
The killer feature of DTs is how fast they can be. I worked very hard on a project to try and replace DT based classifiers with small NNs in a low latency application. NNs could achieve non-trivial gains in classification accuracy but remained two orders of magnitude higher latency at inference time.
Post reply on HN