would it be correct to say that learning a decision tree was motivated by data and not by theory?
It depends on what you mean by "motivated by data". There are many different tree building algorithms that have been devised, some with more theoretical underpinnings / justification than others. We tend to define a decision tree as being good by it having the lowest possible depth to obtain the best accuracy, which is NP-hard. So its not an easy problem to solve. All of our difference tree inducing algorithms can be seen as different feeble attempts at producing heuristics for a difficult problem. Though some of the more recent (if rarer) decision tree papers have more theoretical results (See the Extra Trees paper as an example).
k-means is an algorithm similar to decision trees in that we had an initial idea, quickly proved that it was very difficult - and simple came up with heuristics until it worked. Only recently did we get some more theoretical results (k-means++) of real use, but still - its comes off as a very "well, it works!" kinda method.
Regarding classification and regression tress, are there theoretical bounds on the training and testing errors? If so a reference would be great.
There appear to be some, but I don't know how many exist. Especially considering the many different tree learning methods.
