  Evaluating machine learning (ML) systems on their ability to learn known
classifiers allows fine-grained examination of the patterns they can learn,
which builds confidence when they are applied to the learning of unknown
classifiers. This article presents a new benchmark for ML systems on sequence
classification called MLRegTest, which contains training, development, and test
sets from 1,800 regular languages. Different kinds of formal languages
represent different kinds of long-distance dependencies, and correctly
identifying long-distance dependencies in sequences is a known challenge for ML
systems to generalize successfully. MLRegTest organizes its languages according
to their logical complexity (monadic second order, first order, propositional,
or monomial expressions) and the kind of logical literals (string, tier-string,
subsequence, or combinations thereof). The logical complexity and choice of
literal provides a systematic way to understand different kinds of
long-distance dependencies in regular languages, and therefore to understand
the capacities of different ML systems to learn such long-distance
dependencies. Finally, the performance of different neural networks (simple
RNN, LSTM, GRU, transformer) on MLRegTest is examined. The main conclusion is
that their performance depends significantly on the kind of test set, the class
of language, and the neural network architecture.
