An Entropy Metric for Regular Grammar Classification and Learning with Recurrent Neural Networks

Area of Science:

• Computer Science
• Artificial Intelligence
• Formal Language Theory

Background:

• Deep learning research has seen a resurgence in formal language theory.
• Most research focuses on representing symbolic knowledge with machine learning, with limited exploration of the fundamental connection between formal languages and deep learning.
• Understanding the internal structures and complexity of regular grammars is crucial for advancing this connection.

Purpose of the Study:

• To categorize regular grammars based on their inherent complexity.
• To establish a theoretical framework for understanding the relationship between grammar structure and learnability.
• To provide a foundation for future research at the intersection of formal language theory and deep learning.

Main Methods:

• Theoretical analysis of regular grammars.
• Introduction of an entropy metric to quantify grammar complexity, relaxing original order information.
• Categorization of regular grammars into polynomial, exponential, and proportional classes based on the entropy metric.
• Empirical validation using recurrent neural networks to learn grammars.

Main Results:

• Regular grammars were successfully categorized into three distinct complexity classes: polynomial, exponential, and proportional.
• Classification theorems were developed for various representations of regular grammars.
• Empirical results confirmed that more complex grammars (higher entropy) are generally more difficult for recurrent neural networks to learn.

Conclusions:

• The proposed entropy metric effectively captures the complexity of regular grammars.
• The categorization provides a novel framework for understanding grammar complexity in the context of machine learning.
• This research bridges formal language theory and deep learning, suggesting complexity as a key factor in learnability.