MLRegTest (A Benchmark for the Machine Learning of Regular Languages)

MLRegTest is a benchmark for sequence classification, containing training, development, and test sets from 1,800 regular languages. Regular languages are formal languages, which are sets of sequences definable with certain kinds of formal grammars, including regular expressions, finite-state acceptors, and monadic second-order logic with either the successor or precedence relation in the model signature for words. This benchmark was designed to help identify those factors, specifically the kinds of long-distance dependencies, that can make it difficult for ML systems to generalize successfully in learning patterns over sequences. 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 capabilities of different ML systems to learn such long-distance dependencies. The authors think it will be an important milestone if other researchers are able to find an ML system that succeeds across the board on MLRegTest.