| Title: |
Robust Identification in the Limit from Incomplete Positive Data |
| Authors: |
Kaelbling, Philip; Lambert, Dakotah; Heinz, Jeffrey |
| Contributors: |
Wesleyan University; Laboratoire Hubert Curien (LabHC); Institut d'Optique Graduate School (IOGS)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS); Stony Brook University SUNY (SBU); State University of New York (SUNY); Support was granted from the Data + Computing = Discovery summer REU program at the Institute for Advanced Computational Science at Stony Brook University, supported by the NSF under award 1950052; Henning Fernau; Philipp Kindermann; Zhidan Feng; Kevin Mann |
| Source: |
Lecture Notes in Computer Science ; 24th International Symposium Fundamentals of Computation Theory ; https://hal.science/hal-04237264 ; 24th International Symposium Fundamentals of Computation Theory, Henning Fernau; Philipp Kindermann; Zhidan Feng; Kevin Mann, Sep 2023, Trier, Germany. pp.276-290, ⟨10.1007/978-3-031-43587-4_20⟩ |
| Publisher Information: |
CCSD; Springer Nature Switzerland |
| Publication Year: |
2023 |
| Collection: |
Université Jean Monnet – Saint-Etienne: HAL |
| Subject Terms: |
identification in the limit; grammatical inference; regular languages; model theory; locally testable; piecewise testable; [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG]; [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] |
| Subject Geographic: |
Trier; Germany |
| Description: |
International audience ; Intuitively, a learning algorithm is robust if it can succeed despite adverse conditions. We examine conditions under which learning algorithms for classes of formal languages are able to succeed when the data presentations are systematically incomplete; that is, when certain kinds of examples are systematically absent. One motivation comes from linguistics, where the phonotactic pattern of a language may be understood as the intersection of formal languages, each of which formalizes a distinct linguistic generalization. We examine under what conditions these generalizations can be learned when the only data available to a learner belongs to their intersection. In particular, we provide three formal definitions of robustness in the identification in the limit from positive data paradigm, and several theorems which describe the kinds of classes of formal languages which are, and are not, robustly learnable in the relevant sense. We relate these results to classes relevant to natural language phonology. |
| Document Type: |
conference object |
| Language: |
English |
| DOI: |
10.1007/978-3-031-43587-4_20 |
| Availability: |
https://hal.science/hal-04237264; https://hal.science/hal-04237264v1/document; https://hal.science/hal-04237264v1/file/main.pdf; https://doi.org/10.1007/978-3-031-43587-4_20 |
| Rights: |
http://hal.archives-ouvertes.fr/licences/copyright/ ; info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.530F2C4F |
| Database: |
BASE |