# Invariance, encodings, and generalization: learning identity effects with neural networks

arXiv: https://arxiv.org/abs/2101.08386 · HTML: https://mlsanity.com/paper/2101.08386/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 40 references that are in the map.
- First posted on arXiv 21 Jan 2021.

## Builds on (most cited first, 8 of 8)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [LSTM: A Search Space Odyssey](https://mlsanity.com/paper/1503.04069/) (2015)
- [Generalizing Outside the Training Set: When Can Neural Networks Learn Identity Effects?](https://mlsanity.com/paper/2005.04330/) (2020)
- [Which Learning Algorithms Can Generalize Identity-Based Rules to Novel Inputs?](https://mlsanity.com/paper/1605.04002/) (2016)
- [What do AI algorithms actually learn? - On false structures in deep learning](https://mlsanity.com/paper/1906.01478/) (2019)

## Built on by (most cited first, 5 of 5)

- [Dimensionless machine learning: Imposing exact units equivariance](https://mlsanity.com/paper/2204.00887/) (2022)
- [On the approximation capability of GNNs in node classification/regression tasks](https://mlsanity.com/paper/2106.08992/) (2021)
- [Ensembles provably learn equivariance through data augmentation](https://mlsanity.com/paper/2410.01452/) (2024)
- [VC dimension of Graph Neural Networks with Pfaffian activation functions](https://mlsanity.com/paper/2401.12362/) (2024)
- [Generalization Limits of Graph Neural Networks in Identity Effects Learning](https://mlsanity.com/paper/2307.00134/) (2023)

## Abstract (arXiv)

Often in language and other areas of cognition, whether two components of an object are identical or not determines if it is well formed. We call such constraints identity effects. When developing a system to learn well-formedness from examples, it is easy enough to build in an identify effect. But can identity effects be learned from the data without explicit guidance? We provide a framework in which we can rigorously prove that algorithms satisfying simple criteria cannot make the correct inference. We then show that a broad class of learning algorithms including deep feedforward neural networks trained via gradient-based algorithms (such as stochastic gradient descent or the Adam method) satisfy our criteria, dependent on the encoding of inputs. In some broader circumstances we are able to provide adversarial examples that the network necessarily classifies incorrectly. Finally, we demonstrate our theory with computational experiments in which we explore the effect of different input encodings on the ability of algorithms to generalize to novel inputs. This allows us to show similar effects to those predicted by theory for more realistic methods that violate some of the conditions of our theoretical results.