TL;DR
GapTV is a new approach for low-dimensional regression and classification that balances accuracy with high interpretability. By combining a data-adaptive grid (tuned via the "gap statistic") with fast Total Variation (TV) denoising, it partitions feature space into sharp, constant-value "plateaus" that are easier for humans to understand than complex non-linear models.
What Problem Does This Paper Address?
In the era of "big data," many machine learning models (like deep neural networks) prioritize predictive accuracy (low RMSE) at the expense of interpretability. However, in "small data, few features" scenarios—such as making business decisions, setting policy, or anonymizing spatial demographic data—understanding why a model makes a specific prediction is often more important than a marginal gain in accuracy.
Existing methods like CART (Classification and Regression Trees) produce interpretable "sharp" partitions but often over-smooth the data, missing important nuances. Conversely, newer methods like CRISP (Convex Regression via Interpretable Sharp Partitions) can become overly complex and "blurry" as sample sizes grow. The authors sought a method that provides the global optimization benefits of convex regression while maintaining the clean, blocky interpretability of tree-based models.
Methods
GapTV operates in two primary stages:
- Data-Adaptive Gridding: The algorithm divides the feature space into a $q \times q$ grid. Unlike previous methods that use a fixed or arbitrarily large $q$, GapTV uses a novel application of the gap statistic (traditionally used in clustering) to find the optimal granularity. This ensures the grid is fine enough to capture signal but coarse enough to prevent the model from being overwhelmed by noise.
- Graph-based Total Variation (TV) Denoising: Once the grid is set, the model fits values to each cell jointly. It uses a TV penalty, which encourages adjacent cells to have the same value unless the data strongly suggests a "jump." This results in connected regions of constant value (plateaus).
The authors reformulate the optimization problem into a weighted least-squares form, allowing it to be solved efficiently using fast, proximal optimization algorithms (like ADMM). Crucially, the method is fully auto-tuned, handling hyperparameter selection (like the grid size $q$ and regularization $\lambda$) automatically.
Datasets
The authors evaluated GapTV using both simulated and real-world data:
- Synthetic Benchmark: 100 independent 100x100 grids containing six randomly generated "plateaus" of different values with added Gaussian noise. This allowed for controlled testing across varying sample sizes (from $N=50$ to $N=10,000$).
- Austin & Chicago Crime Data: Real-world datasets of publicly available crime report counts from 2014 (Austin, TX) and 2015 (Chicago, IL). The data was binned into fine-grained grids based on latitude and longitude to test the model's ability to identify meaningful spatial crime patterns.
Key Insights and Ideas
- The "Goldilocks" Grid: A major insight is that standard TV denoising fails when the grid is too fine ($q$ is too large), leading to over-smoothing. By using the gap statistic to find the "just right" grid size, GapTV prevents the model from "blurring" the edges of important features.
- Interpretability as "Sharpness": The authors quantify interpretability by counting the number of constant-value plateaus. A model with 10 large, distinct regions is considered more interpretable than one with 1,000 tiny, fragmented ones.
- Convexity Matters: Unlike CART, which uses a "greedy" search to split data, GapTV uses convex optimization. This means it looks at the entire feature space simultaneously to find the best partitions, leading to more stable and often more accurate results.
Key Results
- Better Trade-offs: In synthetic tests, GapTV achieved similar accuracy (RMSE) to CRISP but with significantly fewer plateaus. For example, at large sample sizes, CRISP created thousands of tiny regions (approaching one per cell), while GapTV maintained a much smaller, more interpretable set of plateaus.
- Superior AIC: When using the Akaike Information Criterion (AIC)—a metric that rewards accuracy but penalizes complexity—GapTV consistently outperformed CART, CRISP, and a hybrid "GapCRISP" method.
- Real-World Performance: On the Austin crime data, GapTV achieved the best (lowest) AIC score. Qualitatively, the resulting maps (Figure 5) show that GapTV identifies clear, contiguous high-crime neighborhoods, whereas CART was too "blocky" and CRISP was too fragmented to be easily interpreted by a human observer.
Limitations and Future Work
- Dimensionality: The paper focuses on 2D and 3D scenarios. While the math extends further, the visual interpretability of "sharp partitions" is most potent in low dimensions. Scaling to high-dimensional feature spaces remains a challenge.
- Computational Cost: While more efficient than some predecessors, the initial step of calculating the gap statistic involves iterating through multiple candidate grid sizes, which could be slow for extremely large datasets.
- Anonymization Proofs: While the authors suggest GapTV is useful for creating "areal data" to help anonymize sensitive information, they note that they do not provide formal mathematical proofs for specific privacy guarantees like $k$-anonymity.
Summary updated