Prediction with Unpredictable Feature Evolution
  Learning with feature evolution studies the scenario where the features of
the data streams can evolve, i.e., old features vanish and new features emerge.
Its goal is to keep the model always performing well even when the features
happen to evolve. To tackle this problem, canonical methods assume that the old
features will vanish simultaneously and the new features themselves will emerge
simultaneously as well. They also assume there is an overlapping period where
old and new features both exist when the feature space starts to change.
However, in reality, the feature evolution could be unpredictable, which means
the features can vanish or emerge arbitrarily, causing the overlapping period
incomplete. In this paper, we propose a novel paradigm: Prediction with
Unpredictable Feature Evolution (PUFE) where the feature evolution is
unpredictable. To address this problem, we fill the incomplete overlapping
period and formulate it as a new matrix completion problem. We give a
theoretical bound on the least number of observed entries to make the
overlapping period intact. With this intact overlapping period, we leverage an
ensemble method to take the advantage of both the old and new feature spaces
without manually deciding which base models should be incorporated. Theoretical
and experimental results validate that our method can always follow the best
base models and thus realize the goal of learning with feature evolution.
