Abstract
An efficient (polynomial time) algorithm is presented for the problem of learning subsequential transducers given the ability to make two kind of queries; translation queries, where the translation of a given string is returned, and equivalence queries, that are answered either positively or with a counterexample. A probabilistic setting in which equivalence queries are substituted by a random sample oracle is also studied and the corresponding modifications to the algorithm presented.
Supported by a grant of the Spanish Ministerio de Educación y Ciencia
Preview
Unable to display preview. Download preview PDF.
References
D. Angluin: “Learning Regular Sets from Queries and Counterexamples”. Information and Computation, Vol. 75, pp. 87–106, 1987.
D. Angluin: “Negative Results for Equivalence Queries”. Machine Learning, Vol. 5, pp. 121–150, 1990.
J. Berstel: Transductions and Context-Free Languages. Teubner, Stuttgart. 1979.
D. Gildea, D. Jurafsky “Automatic Induction of Finite State Transducers for Simple Phonological Rules”. ICSI. Technical Report, TR-94-052, 1994.
E. M. Gold: “Language Identification in the Limit”. Information and Control, Vol. 10, pp. 447–474, 1967.
V.M. Jiménez, A. Castellanos, E. Vidal, J. Oncina: “Some Results with a Trainable Speech Translation and Understanding System”. Proceedings of the ICASSP-95.
J. Oncina, P. García, E. Vidal: “Learning Subsequential Transducers for Pattern Recognition Interpretation Tasks”. IEEE Transactions on PAMI, Vol. 15, No. 5, pp. 448–458, 1993.
L.G. Valiant: “A theory of the Learnable”, Communications of the ACM, Vol. 27, pp.1134–1142, 1984.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vilar, J.M. (1996). Query learning of subsequential transducers. In: Miclet, L., de la Higuera, C. (eds) Grammatical Interference: Learning Syntax from Sentences. ICGI 1996. Lecture Notes in Computer Science, vol 1147. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0033343
Download citation
DOI: https://doi.org/10.1007/BFb0033343
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61778-5
Online ISBN: 978-3-540-70678-6
eBook Packages: Springer Book Archive