CART: asking a y/n question

[Myron]

I didn’t quite understand how we choose the “right” questions for the building of the tree; based on the predictors table I suppose, but in case of choosing a not so effective one, what’s next? The backtracking is not possible as well, right?

thanks

[Simon]

First: how do we come up with the list of possible questions in the first place?

We use our own knowledge of the problem to design the questions, and indeed to select which predictors to ask questions about. It’s not important to choose only good questions because the CART training procedure will automatically find the best ones and ignore less useful ones. So, we try to think of every possible question that we might ask.

Second: during training, how does the algorithm choose the best question to split the data at the current node?

It tries every possible question, and for each one it makes a note of the reduction in entropy (information gain). It chooses the question that gives the best information gain and puts that in to the tree.

Third: what happens if the training algorithm puts a “not so effective” question into the tree?

This will never happen. If the best available question does not give a large enough information gain, then we terminate and do not split that node any further (although the tree can keep growing the other branches).

There is no backtracking: that would massively increase the computational complexity of the training. So, we call this a “greedy” algorithm.

[Author]

Posts