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

Zhang, Kaixuan and Wang, Qinglong and Giles, C. Lee (2021) An Entropy Metric for Regular Grammar Classification and Learning with Recurrent Neural Networks. Entropy, 23 (1). p. 127. ISSN 1099-4300

[thumbnail of entropy-23-00127.pdf] Text
entropy-23-00127.pdf - Published Version

Download (2MB)

Abstract

Recently, there has been a resurgence of formal language theory in deep learning research. However, most research focused on the more practical problems of attempting to represent symbolic knowledge by machine learning. In contrast, there has been limited research on exploring the fundamental connection between them. To obtain a better understanding of the internal structures of regular grammars and their corresponding complexity, we focus on categorizing regular grammars by using both theoretical analysis and empirical evidence. Specifically, motivated by the concentric ring representation, we relaxed the original order information and introduced an entropy metric for describing the complexity of different regular grammars. Based on the entropy metric, we categorized regular grammars into three disjoint subclasses: the polynomial, exponential and proportional classes. In addition, several classification theorems are provided for different representations of regular grammars. Our analysis was validated by examining the process of learning grammars with multiple recurrent neural networks. Our results show that as expected more complex grammars are generally more difficult to learn.

Item Type: Article
Uncontrolled Keywords: entropy; regular grammar classification; complexity analysis; recurrent neural network
Subjects: STM Repository > Physics and Astronomy
Depositing User: Managing Editor
Date Deposited: 13 Mar 2023 07:15
Last Modified: 16 Jul 2024 06:55
URI: http://classical.goforpromo.com/id/eprint/425

Actions (login required)

View Item
View Item