Maximum Margin Interval Trees
  Learning a regression function using censored or interval-valued output data
is an important problem in fields such as genomics and medicine. The goal is to
learn a real-valued prediction function, and the training output labels
indicate an interval of possible values. Whereas most existing algorithms for
this task are linear models, in this paper we investigate learning nonlinear
tree models. We propose to learn a tree by minimizing a margin-based
discriminative objective function, and we provide a dynamic programming
algorithm for computing the optimal solution in log-linear time. We show
empirically that this algorithm achieves state-of-the-art speed and prediction
accuracy in a benchmark of several data sets.
