Recently, Algorithm1 has been experimenting with a novel regression algorithm, called a* QTree*.

QTree stands for “Quotient Tree”, though it is not really accurate to call them trees, and they do not necessarily have quotients hanging off them. So you may call them what you like: “rather awesome regression” for example.

**QTrees have some nice properties… **

**• **They do not require a distinction to be made between independent and dependent (response) variables when building a model. They model the interactions between *all* variables, and the same resultant model can be used to predict any of the variables from any of the other variables.

• They can predict multiple response variables simultaneously.

• They can accept error bars in the input at training and test time, and produce error bars or probability distributions in the output.

• They can handle missing values in any of the variables during training and testing.

• They can be adapted to indicate the “plausibility” of a set of measurements, and to identify outliers.

**• In common with Decision Trees:**

• They can capture non-linear interactions.

• They are robust to the sampling distribution; multiple similar samples will not “pull” the data in a given direction.

• They incorporate intrinsic feature selection; not all variables will necessarily impact on a given prediction.

• They can capture “deep” or “high-order” structure in the data; though unlike decision trees, they can generalize rules across different branches of the tree.

• It is possible to impose additional regularization by limiting the shape and complexity of the tree.

**• In common with Ordinary Least Squares regression:**

• They are naturally a regression model.

• QTrees are very efficient: linear in the number of datapoints at learning time.

• They can be used in an “online” setting; they require only one pass over the data and are not sensitive to the order in which the points are presented.

**Road test**

The following plots were generated from QTree models of the UCI Auto MPG Dataset, trained and tested using leave-one-out sampling. The diagonal line indicates where perfect predictions would lie.

The green and red dots indicate the extreme upper and lower bounds estimated by the model (recall that QTrees output a probability distribution, not just a single-valued prediction). The black dots are the actual “best guess” predictions.

These first results are not Earth shattering – more or less in line with a well-chosen linear regression model – but there is an awful lot of scope for improvement in the algorithm yet. And importantly, the way it works is fundamentally different from linear regression – and those who are interested in Heterogeneous Ensembles (you should be) will know that this can only be a good thing!

You can fully expect that QTrees will be incorporated into Algorithm1’s forthcoming super-user-friendly super-powerful predictive analytics platform, along with a veritable Pandora’s Box of other algorithms (Deep Learning and Meta Learning anyone?)

…whoops, did I say that out loud?

– Justin