A bottom-up efficient algorithm learning substitutable languages from positive examples

François Coste 1 Gaelle Garet 1 Jacques Nicolas 1
1 Dyliss - Dynamics, Logics and Inference for biological Systems and Sequences
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : Based on Harris’s substitutability criterion, the recent definitions of classes of substitutable languages have led to interesting polynomial learnability results for expressive formal languages. These classes are also promising for practical applications: in natural language analysis, because definitions have strong linguisitic support, but also in biology for modeling protein families, as suggested in our previous study introducing the class of local substitutable languages. But turning recent theoretical advances into practice badly needs truly practical algorithms. We present here an efficient learning algorithm, motivated by intelligibility and parsing efficiency of the result, which directly reduces the positive sample into a small non-redundant canonical grammar of the target substitutable language. Thanks to this new algorithm, we have been able to extend our experimentation to a complete protein dataset confirming that it is possible to learn grammars on proteins with high specificity and good sensitivity by a generalization based on local substitutability.
Type de document :
Communication dans un congrès
Alexander Clark; Makoto Kanazawa; Ryo Yoshinaka. ICGI (International Conference on Grammatical Inference), Sep 2014, Kyoto, Japan. 34, pp.49--63, 2014, Proceedings of Machine Learning Research. 〈http://proceedings.mlr.press/v34/coste14a.html〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01080249
Contributeur : François Coste <>
Soumis le : mardi 4 novembre 2014 - 17:23:12
Dernière modification le : mercredi 16 mai 2018 - 11:23:35

Identifiants

  • HAL Id : hal-01080249, version 1

Citation

François Coste, Gaelle Garet, Jacques Nicolas. A bottom-up efficient algorithm learning substitutable languages from positive examples. Alexander Clark; Makoto Kanazawa; Ryo Yoshinaka. ICGI (International Conference on Grammatical Inference), Sep 2014, Kyoto, Japan. 34, pp.49--63, 2014, Proceedings of Machine Learning Research. 〈http://proceedings.mlr.press/v34/coste14a.html〉. 〈hal-01080249〉

Partager

Métriques

Consultations de la notice

438