Explainable Natural Language Processing with Matrix Product States
  Despite empirical successes of recurrent neural networks (RNNs) in natural
language processing (NLP), theoretical understanding of RNNs is still limited
due to intrinsically complex non-linear computations. We systematically analyze
RNNs' behaviors in a ubiquitous NLP task, the sentiment analysis of movie
reviews, via the mapping between a class of RNNs called recurrent arithmetic
circuits (RACs) and a matrix product state (MPS). Using the von-Neumann
entanglement entropy (EE) as a proxy for information propagation, we show that
single-layer RACs possess a maximum information propagation capacity, reflected
by the saturation of the EE. Enlarging the bond dimension beyond the EE
saturation threshold does not increase model prediction accuracies, so a
minimal model that best estimates the data statistics can be inferred. Although
the saturated EE is smaller than the maximum EE allowed by the area law, our
minimal model still achieves ~99% training accuracies in realistic sentiment
analysis data sets. Thus, low EE is not a warrant against the adoption of
single-layer RACs for NLP. Contrary to a common belief that long-range
information propagation is the main source of RNNs' successes, we show that
single-layer RACs harness high expressiveness from the subtle interplay between
the information propagation and the word vector embeddings. Our work sheds
light on the phenomenology of learning in RACs, and more generally on the
explainability of RNNs for NLP, using tools from many-body quantum physics.
