Learning from data streams is emerging as an important application area. When the environment changes, as is increasingly the case when considering unending streams and long-life learning, it is necessary to rely on on-line learning with the capability to adapt to changing conditions a.k.a. concept drifts. Previous works have focused on means to detect changes and to adapt to them. Ensemble methods relying on committees of base learners have been among the most successful approaches.

In this paper, we go one step further by introducing a second-order learning mechanism that is able to detect relevant states of the environment, to recognize recurring contexts and to anticipate likely concepts changes. Results of an empirical comparison with adaptive methods show that, for a very slight price in memory and computation load, the proposed algorithm always improves on, or at worst equals, the prediction performance of a mere adaptive approach.