Maximum-Variance Total Variation Denoising for Interpretable Spatial Smoothing

Wesley Tansey, Jesse Thomason, James G. Scott

Abstract

Maximum-Variance Total Variation (MVTV) is a spatial regression framework designed to generate "sharp partitions"—regions of constant value with well-defined boundaries. While traditional methods like CART often over-smooth data and modern convex approaches like CRISP tend to under-smooth, MVTV utilizes a data-adaptive grid-selection heuristic combined with graph-based total variation denoising to find an optimal balance. Evaluations on synthetic benchmarks and real-world crime datasets from Austin and Chicago, alongside human interpretability studies, demonstrate that MVTV produces models that are both more accurate and significantly more interpretable than existing baselines.

Introduction

Spatial data is a cornerstone of decision-making in fields such as epidemiology, urban planning, and criminology. For these data-driven decisions to be actionable, the underlying models must be interpretable to human stakeholders. Humans typically favor spatial models that divide territory into clear, constant-value neighborhoods rather than complex, continuous gradients. However, achieving this "sharp partition" effect while maintaining predictive accuracy remains a challenge for current smoothing algorithms.

The Problem with Existing Methods

Standard smoothing techniques, such as Kriging, often assume global smoothness, which blurs critical boundaries. Conversely, interpretable methods like Classification and Regression Trees (CART) frequently over-smooth, creating regions too coarse to capture local nuances. More recent convex methods, such as CRISP, often under-smooth, resulting in "blurry" maps with thousands of tiny, non-intuitive regions that hinder human comprehension.

Methodology

MVTV addresses these issues through a two-stage automated process:

  1. Maximum-Variance Grid Selection: Instead of a fixed resolution, MVTV employs a heuristic to select a grid granularity ($q$) that maximizes the sum of variances across all cells. This ensures the grid is fine enough to capture the signal without overfitting to noise.
  2. Graph-Based Total Variation (TV) Denoising: The model treats grid cells as nodes in a graph and applies a Total Variation penalty. This encourages the merging of adjacent cells into flat "plateaus," resulting in the desired sharp boundaries.

Results and Discussion

The authors compared MVTV against CART and CRISP using synthetic data and crime reports. Visual analysis reveals that MVTV successfully recovers underlying plateaus without the over-smoothing of CART or the fragmentation of CRISP.

Visual comparison of spatial smoothing methods (CART, CRISP, MV-CRISP, MVTV) across varying sample sizes (N).

Quantitatively, MVTV achieves superior Akaike Information Criterion (AIC) scores, indicating a better balance between model fit and complexity. In a human study involving 207 participants, MVTV-smoothed maps led to significantly higher accuracy in predicting missing values, confirming that the method aligns with human spatial intuition.

Quantitative performance metrics (RMSE, Plateau Count, and AIC) for MVTV compared to baselines across different sample sizes.

Conclusion

MVTV provides a robust, fully automated solution for interpretable spatial smoothing. By prioritizing the creation of sharp partitions, it bridges the gap between high-accuracy statistical modeling and human-centric decision support.

Summary updated

Abstract

We consider the problem of spatial regression where interpretability of the model is a high priority. Such problems appear frequently in a diverse set of fields from climatology to epidemiology to predictive policing. For cognitive, logistical, and organizational reasons, humans tend to infer regions or neighborhoods of constant value, often with sharp discontinuities between regions, and then assign resources on a per-region basis. Automating this smoothing process presents a unique challenge for spatial smoothing algorithms, which tend to assume stationarity and smoothness everywhere. To address this problem, we propose Maximum Variance Total Variation (MVTV) denoising, a novel method for interpretable nonlinear spatial regression. MVTV divides the feature space into blocks of constant value and smooths the value of all blocks jointly via a convex optimization routine. Our method is fully data-adaptive and incorporates highly robust routines for tuning all hyperparameters automatically. We compare our approach against the existing CART and CRISP methods via both a complexity-accuracy tradeoff metric and a human study, demonstrating that that MVTV is a more powerful and interpretable method.
BibTeX
@inproceedings{tansey2018maximum,
  author = {Wesley Tansey and Jesse Thomason and James G. Scott},
  title = {{Maximum-Variance Total Variation Denoising for Interpretable Spatial Smoothing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11893},
}
Figure