Subregular Complexity and Machine Learning

Sequences of events are ubiquitous in nature and engineering. Examples include the arrangements of words within sentences, sounds within words, nucleic acid sequences within genomes, and series of actions to be conducted to complete tasks such as robots harvesting grain, or teams of firefighters responding to an emergency. The machine learning of sequential information is therefore important to many disciplines including linguistics, robotic planning and control, emergency response, and molecular biology.

In this talk, we explain how a hierarchy of formal languages can be used to compare and contrast two machine learning techniques for learning sequential information: deep learning and grammatical inference. The conclusion is that grammatical inference methods are indispensable to understanding the information needed to successfully learn sequential patterns.

This work is joint research with Enes Avcu (University of Delaware) and Chihiro Shibata (Tokyo University of Technology).