Are decision tree algorithms linear or nonlinear

Question

Recently a friend of mine was asked whether decision tree algorithms are linear or nonlinear algorithms in an interview. I tried to look for answers to this question but couldn't find any satisfactory explanation. Can anyone answer and explain the solution to this question? Also, what are some other examples of nonlinear machine learning algorithms?

Answer 1

A decision tree is a non-linear mapping of X to y. This is easy to see if you take an arbitrary function and create a tree to its maximum depth.

For example:

if x = 1, y = 1
if x = 2, y = 15
if x = 3, y = 3
if x = 4, y = 27
...

Of course, this is a completely over-fit tree and won't generalize. But it demonstrates why a decision tree is a non-linear mapping.

Answer 2

Recently a friend of mine was asked whether decision tree algorithm a linear or nonlinear algorithm in an interview

Decision trees is a non-linear classifier like the neural networks, etc. It is generally used for classifying non-linearly separable data.

Even when you consider the regression example, decision tree is non-linear.

For example, a linear regression line would look somewhat like this:

The red dots are the data points.

And a decision tree regression plot would look something like this:

So, clearly decision trees are non-linear

Answer 3

As many pointed out, a regression/decision tree is a non-linear model. Note however that it is a piecewise linear model: in each neighborhood (defined in a non-linear way), it is linear. In fact, the model is just a local constant.

To see this in the simplest case, with one variable, and with one node $\theta$, the tree can be written as a linear regression:

$$y_i = \alpha_1 1(x_i < \theta) + \alpha_2 1(x_i \geq \theta) + \epsilon_i$$

Where $1(A)$ is the indicator function, taking value of 1 if the event A is true, and 0 otherwise.

Answer 4

A decision tree is a non-linear classifier. If your dataset contains consistent samples, namely you don't have the same input features and contradictory labels, decision trees can classify the data entirely and overfit it. To clarify more the $VC$ dimension for decision trees is $2^d$ which $d$ is for the number of the binary features. Consequently, the Hypothesis space contains $2^{2^d}$ different possibilities which can be dealt with using decision trees. One important point is the number of possible leaves that a decision tree can have. Suppose you have $m$ samples with $d$ binary features. Depending on the quantity of each, the number of possibilities is $min(2^d, m)$. Decision trees can overfit the training data-set no matter whether they are linearly separable or not, and that is why people use approaches like ID3 or C4.5 for pruning the tree or setting a threshold for the height and length of the trees in order not to overfit the data.

Answer 5

Decision trees are non linear. Unlike Linear regression there is no equation to express relationship between independent and dependent variables.

Ex:

Linear regression - Price of fruit = b0 + b1*Freshness + b2*Size

Decision tree - Nodes: Ripe - Yes or no | Fresh - Yes or No | Size - <5, >5 but <10 and >10 |

In the second case there is no linear relationship between independent and dependent variables.