I have read that decision trees can represent any hypothesis and are thus completely expressive. So how do we represent the hypothesis of linear regression in the form of a decision tree ? I am referring to the equation
w0 + w1.x1 + w2.x2 + .... + wn.xn = yn
The basic idea would be to divide up your feature space in small multi-dimensional intervals, and then assign to each point in a given interval the average value that your linear regression model has in that interval. This is something you can do with a tree.
This is similar in spirit to approximating (in 1D space) the function $y = x$ with a "piecewise constant", "staircase-like" function like http://mathworld.wolfram.com/NearestIntegerFunction.html: you could divide your 1D space in equal intervals (e.g. of length 1), and you'd assign to each interval the average value that the function $y = x$ has in it.
Note that such "piecewise constant" function can be defined as a tree: suppose you wanted to know the "tree" approximation of $y = x$ for $x^* = \pi = 3.14159..$, then you could do:
Is $x^* > 0$? Yes
- Is $x^* < 0.5$? No (if it was, I would have approximated $x^*$ with 0)
- - Is $x^* < 1.5$? No (if it was, I would have approximated with 1)
- - - Is $x^* < 2.5$? No (if it was...)
- - - - Is $x^* < 3.5$? Yes -> I approximate $x^*$ with $3$ (3 is the average of $y = x$ between 2.5 and 3.5).
Note that as the size of the intervals shrinks (in "tree language", as you grow your tree more and more), the better the approximation would become. Also, rather than decision one would speak of regression tree in this context.
To generalize this idea, just imagine that you could carry out a similar procedure for any linear function in 1D $y = ax + b$ using a "staircase-like" function, and in N dimensions for any linear function in N-D $y = a_0 + a_1 x_1 + \cdots + a_n x_x$.
Actually, you don't have to restrain to linear functions, as as you said trees are more flexible still (you just need to appropriately assign the values to each interval of your feature space)!
