Modern machine learning faces a critical challenge: the "triangular" trade-off between accuracy, privacy, and interpretability. While deep learning models achieve state-of-the-art accuracy, they often operate as "black boxes" that can inadvertently leak sensitive training data. This paper, presented at AAAI-20, introduces a novel architecture designed to navigate these competing demands.
The Challenge of Modern AI Constraints
In the regulatory landscape defined by the General Data Protection Regulation (GDPR), machine learning practitioners must address two major hurdles: the "Right to Explanation" and strict data privacy. Users increasingly demand to know why an algorithm reached a specific decision, yet models must also ensure that no individual's data can be reconstructed from the model's parameters.
Standard deep neural networks are notoriously difficult to interpret. Post-hoc methods like saliency maps often become noisy and nonsensical when the model is trained with Differential Privacy (DP). Conversely, inherently interpretable models like logistic regression often lack the capacity to achieve high accuracy on complex, high-dimensional datasets. This research seeks a "Goldilocks" model that satisfies all three requirements simultaneously.
Methodology: Locally Linear Maps (LLM)
The authors propose Locally Linear Maps (LLM), a family of models that approximate complex decision boundaries using a collection of simple linear functions. Instead of a single monolithic neural network, the LLM uses $M$ linear maps for each class.
Architecture and Training
For any given input, the model employs a "softmax" weighting mechanism to determine which linear maps are most relevant. This makes the model piece-wise linear: locally, it behaves like a simple, understandable linear classifier, while globally, it can capture the complex patterns necessary for high accuracy.
To ensure privacy, the model is trained using DP-SGD (Stochastic Gradient Descent), which involves clipping gradients and adding Gaussian noise. To combat the "curse of dimensionality"—where high-dimensional data requires more noise, thus destroying accuracy—the authors utilize the Johnson-Lindenstrauss transform. By projecting high-dimensional inputs into a lower-dimensional space using a fixed, data-independent matrix, they improve the privacy-accuracy trade-off without consuming the privacy budget.
Key Insights and Results
The LLM was evaluated on MNIST, Fashion-MNIST, and a real-world medical dataset from Henan Renmin Hospital. The results demonstrate that LLMs can achieve competitive accuracy while maintaining superior interpretability compared to traditional private models.
- Accuracy: On MNIST, the LLM achieved 94.2% accuracy with a privacy budget of $\epsilon=2$. On the medical dataset, it reached 82.0% accuracy, trailing a non-private deep neural network by only 2%.
- Inherent Interpretability: Unlike post-hoc explanations for black-box models, LLMs are inherently interpretable. The linear maps act as "prototypes" or templates. While standard attribution maps degrade into noise under high privacy constraints, LLM filters remain recognizable.
Conclusion
Locally Linear Maps provide a robust middle ground for privacy-sensitive applications. By combining the simplicity of linear models with the flexibility of piece-wise approximation and the efficiency of random projections, the authors demonstrate that it is possible to build models that are accurate, private, and explainable. Future work will focus on scaling these models to higher-resolution datasets and exploring more flexible DP-compliant gradient information.
Summary updated