  Data streams are ubiquitous in modern business and society. In practice, data
streams may evolve over time and cannot be stored indefinitely. Effective and
transparent machine learning on data streams is thus often challenging.
Hoeffding Trees have emerged as a state-of-the art for online predictive
modelling. They are easy to train and provide meaningful convergence guarantees
under a stationary process. Yet, at the same time, Hoeffding Trees often
require heuristic and costly extensions to adjust to distributional change,
which may considerably impair their interpretability. In this work, we revisit
Model Trees for machine learning in evolving data streams. Model Trees are able
to maintain more flexible and locally robust representations of the active data
concept, making them a natural fit for data stream applications. Our novel
framework, called Dynamic Model Tree, satisfies desirable consistency and
minimality properties. In experiments with synthetic and real-world tabular
streaming data sets, we show that the proposed framework can drastically reduce
the number of splits required by existing incremental decision trees. At the
same time, our framework often outperforms state-of-the-art models in terms of
predictive quality -- especially when concept drift is involved. Dynamic Model
Trees are thus a powerful online learning framework that contributes to more
lightweight and interpretable machine learning in data streams.
