  The performance of machine learning models can significantly degrade under
distribution shifts of the data. We propose a new method for classification
which can improve robustness to distribution shifts, by combining expert
knowledge about the ``high-level" structure of the data with standard
classifiers. Specifically, we introduce two-stage classifiers called memory
classifiers. First, these identify prototypical data points -- memories -- to
cluster the training data. This step is based on features designed with expert
guidance; for instance, for image data they can be extracted using digital
image processing algorithms. Then, within each cluster, we learn local
classifiers based on finer discriminating features, via standard models like
deep neural networks. We establish generalization bounds for memory
classifiers. We illustrate in experiments that they can improve generalization
and robustness to distribution shifts on image datasets. We show improvements
which push beyond standard data augmentation techniques.
