Book contents
- Frontmatter
- Contents
- Preface
- Acknowledgements
- 1 Introduction
- 2 The data and some applications
- Part I The Tools
- Part II What Does Learning a Language Mean?
- 7 Identifying languages
- 8 Learning from text
- 9 Active learning
- 10 Learning distributions over strings
- Part III Learning Algorithms and Techniques
- References
- Index
10 - Learning distributions over strings
from Part II - What Does Learning a Language Mean?
Published online by Cambridge University Press: 05 July 2014
- Frontmatter
- Contents
- Preface
- Acknowledgements
- 1 Introduction
- 2 The data and some applications
- Part I The Tools
- Part II What Does Learning a Language Mean?
- 7 Identifying languages
- 8 Learning from text
- 9 Active learning
- 10 Learning distributions over strings
- Part III Learning Algorithms and Techniques
- References
- Index
Summary
El azar tiene muy mala leche y muchas ganas de broma.
Arturo Perez ReverteAll knowledge degenerates into probability.
David Hume, A Treatise on Human Nature, 1740If we suppose that the data have been obtained through sampling, that means we have (or at least believe in) an underlying probability over the strings. In most cases we do not have a description of this distribution, and we describe three plausible learning settings.
The first possibility is that the data are sampled according to an unknown distribution, and that whatever we learn from, the data will be measured with respect to this distribution. This corresponds to the well-known PAC-learning setting (probably approximately correct).
The second possibility is that the data are sampled according to a distribution itself defined by a grammar or an automaton. The goal will now no longer be to classify strings but to learn this distribution. The quality of the learning process can then be measured either while accepting a small error (most of the time, since a particular sampling can have been completely corrupted!), or in the limit, with probability one. One can even hope for a combination of both these criteria.
There are other possible related settings that we only mention briefly here: an important one concerns the case where the distribution in the PAC model is computable, without being generated by a grammar or an automaton. The problem remains a classification question for which we have only restricted the class of admissible distributions.
- Type
- Chapter
- Information
- Grammatical InferenceLearning Automata and Grammars, pp. 196 - 214Publisher: Cambridge University PressPrint publication year: 2010