TY - GEN
T1 - Robust Identification in the Limit from Incomplete Positive Data
AU - Kaelbling, Philip
AU - Lambert, Dakotah
AU - Heinz, Jeffrey
N1 - Publisher Copyright: © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
KW - grammatical inference
KW - identification in the limit
KW - locally testable
KW - model theory
KW - piecewise testable
KW - regular languages
UR - https://www.scopus.com/pages/publications/85174580917
U2 - 10.1007/978-3-031-43587-4_20
DO - 10.1007/978-3-031-43587-4_20
M3 - Conference contribution
SN - 9783031435867
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 276
EP - 290
BT - Fundamentals of Computation Theory - 24th International Symposium, FCT 2023, Proceedings
A2 - Fernau, Henning
A2 - Jansen, Klaus
PB - Springer Science and Business Media Deutschland GmbH
T2 - 24th International Symposium on Fundamentals of Computation Theory, FCT 2023
Y2 - 18 September 2023 through 21 September 2023
ER -