CART Computational Complexity

[Federica A]

I’ve noticed a few questions which bring up CART computational complexity. What is meant by this? Does it mean training complexity or testing complexity, or both?

From the revision lecture, it seems that training is complex and slow, while testing is extremely simple and fast. If computational complexity is either, it’s fairly easy to answer the question. However, given that we do not have more context (as in knowledge of other algorithms), it would be hard to determine if it was both.

[Simon]

For this course, you do not need to be able to state or derive formally what the computational complexity of algorithms is, although you should understand informally that some algorithms are more complex (i.e., require a larger number of computations) than others.

Nevertheless, it’s still useful to understand computational complexity. Let’s just keep things informal here and only mention the most important case, and that is the complexity of a CART when we are using it at ‘run time’:

Computational complexity of using a CART to classify an unseen data point

This depends on the depth of the tree, because that determines how many questions you need to ask about the predictors. The depth of the tree is proportional to the logarithm (to base 2) of the number of leaves. This is very nice: the logarithm of a number grows slowly as that number gets larger. So, even trees with very large numbers of leaves will not be very deep. For example, a tree with 1000 leaves will only have a depth of around 10. That makes CARTs very fast to use: asking 10 binary questions about predictors will be computationally very fast.

What is the depth of a tree?

This is the number of edges (the edges join up the nodes) from the root to a leaf. The depth might vary in different parts of the tree, of course.

[Author]

Posts