An Entropy Metric for Regular Grammar Classification and Learning with Recurrent Neural Networks
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 connec...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-01-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/23/1/127 |
| _version_ | 1797409713856446464 |
|---|---|
| author | Kaixuan Zhang Qinglong Wang C. Lee Giles |
| author_facet | Kaixuan Zhang Qinglong Wang C. Lee Giles |
| author_sort | Kaixuan Zhang |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T04:19:45Z |
| format | Article |
| id | doaj.art-066b3087db984f71849d2171f49f969a |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-09T04:19:45Z |
| publishDate | 2021-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-066b3087db984f71849d2171f49f969a2023-12-03T13:49:04ZengMDPI AGEntropy1099-43002021-01-0123112710.3390/e23010127An Entropy Metric for Regular Grammar Classification and Learning with Recurrent Neural NetworksKaixuan Zhang0Qinglong Wang1C. Lee Giles2Information Sciences and Technology, Pennsylvania State University, University Park, PA 16802, USAAlibaba Group, Building A2, Lane 55 Chuan He Road Zhangjiang, Pudong New District, Shanghai 200135, ChinaInformation Sciences and Technology, Pennsylvania State University, University Park, PA 16802, USARecently, 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.https://www.mdpi.com/1099-4300/23/1/127entropyregular grammar classificationcomplexity analysisrecurrent neural network |
| spellingShingle | Kaixuan Zhang Qinglong Wang C. Lee Giles An Entropy Metric for Regular Grammar Classification and Learning with Recurrent Neural Networks Entropy entropy regular grammar classification complexity analysis recurrent neural network |
| title | An Entropy Metric for Regular Grammar Classification and Learning with Recurrent Neural Networks |
| title_full | An Entropy Metric for Regular Grammar Classification and Learning with Recurrent Neural Networks |
| title_fullStr | An Entropy Metric for Regular Grammar Classification and Learning with Recurrent Neural Networks |
| title_full_unstemmed | An Entropy Metric for Regular Grammar Classification and Learning with Recurrent Neural Networks |
| title_short | An Entropy Metric for Regular Grammar Classification and Learning with Recurrent Neural Networks |
| title_sort | entropy metric for regular grammar classification and learning with recurrent neural networks |
| topic | entropy regular grammar classification complexity analysis recurrent neural network |
| url | https://www.mdpi.com/1099-4300/23/1/127 |
| work_keys_str_mv | AT kaixuanzhang anentropymetricforregulargrammarclassificationandlearningwithrecurrentneuralnetworks AT qinglongwang anentropymetricforregulargrammarclassificationandlearningwithrecurrentneuralnetworks AT cleegiles anentropymetricforregulargrammarclassificationandlearningwithrecurrentneuralnetworks AT kaixuanzhang entropymetricforregulargrammarclassificationandlearningwithrecurrentneuralnetworks AT qinglongwang entropymetricforregulargrammarclassificationandlearningwithrecurrentneuralnetworks AT cleegiles entropymetricforregulargrammarclassificationandlearningwithrecurrentneuralnetworks |