Learning with Changing Features

Amit Dhurandhar, Steve Hanneke, Liu YangarXiv 2017 · arXiv

Introduction

In traditional machine learning, a common assumption is that the relationship between input features ($X$) and the target output ($Y$) remains stable over time. However, in dynamic environments such as high-tech manufacturing or global retail, this assumption often fails. Features can change their relevance or "meaning" due to external factors—a new sensor being integrated into a factory line or a sudden shift in consumer sentiment.

This paper addresses the challenge of identifying the exact moment when these feature relationships shift. By introducing a formal framework for detecting change points in a distribution-independent setting, the authors provide a method for models to pivot and adapt to new data dynamics effectively.

The Problem: Supervised vs. Unsupervised Drift

Most existing research on "concept drift" focuses on unsupervised shifts, where the underlying distribution of the data itself changes. This paper targets the supervised gap: scenarios where the distribution of $X$ might remain identical, but the relationship $X \to Y$ is altered.

Consider two real-world examples:

  1. Manufacturing: A semiconductor factory introduces a high-precision tool. While the tool produces data immediately, there is a specific, unknown point in time when its measurements actually begin to correlate with the final quality of the chip.
  2. Retail: A news scandal changes how customers perceive a brand. Suddenly, historical loyalty metrics become less predictive of sales than real-time social media mentions.

Identifying these transition points is critical for maintaining model accuracy and ensuring that "new" features are utilized only when they become informative.

Methodology: Search-and-Split (SaS)

The authors propose a strategy called Search-and-Split (SaS), which treats change point detection as an optimization problem.

The Core Algorithm

SaS is a variant of Empirical Risk Minimization (ERM). The algorithm iterates through every possible time point ($t$) in a dataset. For each potential split, it trains two separate models: one for the data preceding $t$ and one for the data following $t$. The algorithm then selects the split point that minimizes the total combined Mean Squared Error (MSE) across the entire timeline.

Efficiency Optimizations (SaSF)

Retraining models for every possible time point is computationally prohibitive ($O(m)$ iterations). To address this, the authors introduced SaS Fast (SaSF), which utilizes two primary shortcuts:

  • Grid Search: Instead of evaluating every point, SaSF checks a grid of points (approximately $\sqrt{m}$). The authors provide mathematical proof that this reduction only degrades performance by a constant factor while significantly decreasing compute time.
  • Incremental Updates: Rather than retraining from scratch, the algorithm uses meta-algorithms to update existing models with new features as the search progresses.

Theoretical Guarantees

A key contribution of this work is the provision of "distribution-independent excess risk guarantees." The authors prove that SaS performs nearly as well as an oracle with perfect knowledge of the true change point, regardless of the underlying data distribution.

Experimental Validation

The framework was tested across three distinct environments to verify its robustness and practical utility.

1. Synthetic Benchmarking

Using 100 datasets of 10,000 samples each, the authors simulated 1,000-dimensional Gaussians where feature correlations were flipped at the midpoint. SaS and SaSF adapted to these split points almost seamlessly, significantly outperforming standard drift adaptation methods like Gradual or Abrupt Forgetting, which took much longer to recover accuracy.

2. Retail and Market Sentiment

In a massive 4TB dataset tracking 80 million online customers over two years, the SaS algorithm identified a specific change point in October. Post-analysis revealed this coincided exactly with a series of unflattering news stories about the brand. This suggests the algorithm can effectively "sense" external real-world events by monitoring shifts in data relationships.

3. Advanced Manufacturing

In a semiconductor plant study involving 8,926 wafers, the model tracked 2,287 initial measurements and 1,030 "downstream" features. The SaS framework successfully identified when the downstream features became relevant to predicting wafer speed, leading to a dramatic improvement in predictive performance once the change point was reached.

Conclusion and Future Work

The Search-and-Split framework provides a mathematically rigorous and computationally viable method for detecting supervised change points. While the current iteration is optimized for "sudden" shifts, it establishes a foundation for more complex temporal modeling.

The authors acknowledge that searching for multiple change points simultaneously remains a computational challenge. Future research directions include the application of Dynamic Programming to efficiently identify multiple transitions, further reducing the complexity of the search for industrial-scale applications.

Summary updated

Abstract

In this paper we study the setting where features are added or change interpretation over time, which has applications in multiple domains such as retail, manufacturing, finance. In particular, we propose an approach to provably determine the time instant from which the new/changed features start becoming relevant with respect to an output variable in an agnostic (supervised) learning setting. We also suggest an efficient version of our approach which has the same asymptotic performance. Moreover, our theory also applies when we have more than one such change point. Independent post analysis of a change point identified by our method for a large retailer revealed that it corresponded in time with certain unflattering news stories about a brand that resulted in the change in customer behavior. We also applied our method to data from an advanced manufacturing plant identifying the time instant from which downstream features became relevant. To the best of our knowledge this is the first work that formally studies change point detection in a distribution independent agnostic setting, where the change point is based on the changing relationship between input and output.
BibTeX
@misc{dhurandhar2017learning,
  author = {Amit Dhurandhar and Steve Hanneke and Liu Yang},
  title = {{Learning with Changing Features}},
  year = {2017},
  eprint = {1705.00219},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1705.00219},
}
Figure