Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-25T12:17:01.214Z Has data issue: false hasContentIssue false
  • English
  • Français

Convergence of error-driven ranking algorithms*

Published online by Cambridge University Press:  06 September 2012

Giorgio Magri
Giorgio Magri
Affiliation:
CNRS, Université Paris 7
Get access Rights & Permissions [Opens in a new window]

Abstract

According to the OT error-driven ranking model of language acquisition, the learner performs a sequence of slight re-rankings triggered by mistakes on the incoming stream of data, until it converges to a ranking that makes no more mistakes. Two classical examples are Tesar & Smolensky's (1998) Error-Driven Constraint Demotion (EDCD) and Boersma's (1998) Gradual Learning Algorithm (GLA). Yet EDCD only performs constraint demotion, and is thus shown to predict a ranking dynamics which is too simple from a modelling perspective. The GLA performs constraint promotion too, but has been shown not to converge. This paper develops a complete theory of convergence of error-driven ranking algorithms that perform both constraint demotion and promotion. In particular, it shows that convergent constraint promotion can be achieved (with an error-bound that compares well to that of EDCD) through a proper calibration of the amount by which constraints are promoted.

Type
Articles
Information
Phonology , Volume 29 , Issue 2 , August 2012 , pp. 213 - 269
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Anttila, Arto (1997). Variation in Finnish phonology and morphology. PhD dissertation, Stanford University.Google Scholar
Anttila, Arto & Cho, Young-mee Yu (1998). Variation and change in Optimality Theory. Lingua 104. 31–56.Google Scholar
Bernhardt, Barbara H. & Stemberger, Joseph P. (1998). Handbook of phonological development from the perspective of constraint-based nonlinear phonology. San Diego: Academic Press.Google Scholar
Boersma, Paul (1997). How we learn variation, optionality, and probability. Proceedings of the Institute of Phonetic Sciences of the University of Amsterdam 21. 43–58.Google Scholar
Boersma, Paul (1998). Functional phonology: formalizing the interactions between articulatory and perceptual drives. PhD dissertation, University of Amsterdam.Google Scholar
Boersma, Paul (1999). Optimality-Theoretic learning in the Praat program. Proceedings of the Institute of Phonetic Sciences of the University of Amsterdam 23. 17–35.Google Scholar
Boersma, Paul (2009). Some correct error-driven versions of the Constraint Demotion Algorithm. LI 40. 667–686.Google Scholar
Boersma, Paul & Hayes, Bruce (2001). Empirical tests of the Gradual Learning Algorithm. LI 32. 45–86.Google Scholar
Boersma, Paul & Levelt, Clara C. (2000). Gradual constraint-ranking learning algorithm predicts acquisition order. In Clark, Eve V. (ed.) Proceedings of the 30th Child Language Research Forum. Stanford: CSLI. 229–237.Google Scholar
Boersma, Paul & Pater, Joe (to appear). Convergence properties of a gradual learning algorithm for Harmonic Grammar. In McCarthy, John J. & Pater, Joe (eds.) Harmonic Grammar and harmonic serialism. London: Equinox.Google Scholar
Cesa-Bianchi, Nicolò & Lugosi, Gábor (2006). Prediction, learning, and games. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Coetzee, Andries W. & Pater, Joe (2008). Weighted constraints and gradient restrictions on place co-occurrence in Muna and Arabic. NLLT 26. 289–337.Google Scholar
Compton, A. J. & Streeter, M. (1977). Child phonology: data collection and preliminary analyses. Papers and Reports on Child Language Development 13. 99–109.Google Scholar
Davidson, Lisa, Jusczyk, Peter W. & Smolensky, Paul (2004). The initial and final states: theoretical implications and experimental explorations of Richness of the Base. In Kager et al. (2004). 321–368.CrossRefGoogle Scholar
Dresher, B. Elan (1999). Charting the learning path: cues to parameter setting. LI 30. 27–67.Google Scholar
Fikkert, Paula & de Hoop, Helen (2009). Language acquisition in optimality theory. Linguistics 47. 311–357.CrossRefGoogle Scholar
Gnanadesikan, Amalia (2004). Markedness and faithfulness constraints in child phonology. In Kager et al. (2004). 73–108.CrossRefGoogle Scholar
Hale, Mark & Reiss, Charles (1998). Formal and empirical arguments concerning phonological acquisition. LI 29. 656–683.Google Scholar
Hayes, Bruce (2004). Phonological acquisition in Optimality Theory: the early stages. In Kager et al. (2004). 158–203.CrossRefGoogle Scholar
Heinz, Jeffrey & Riggle, Jason (2011). Learnability. In van Oostendorp, Marc, Ewen, Colin J., Hume, Elizabeth & Rice, Keren (eds.) The Blackwell companion to phonology. Malden, Mass.: Wiley-Blackwell. 54–78.Google Scholar
Jesney, Karen & Tessier, Anne-Michelle (2007). Re-evaluating learning biases in Harmonic Grammar. University of Massachusetts Occasional Papers in Linguistics 36. 69–110.Google Scholar
Jesney, Karen & Tessier, Anne-Michelle (2009). Gradual learning and faithfulness: consequences of ranked vs. weighted constraints. NELS 38. 375–388.Google Scholar
Jusczyk, Peter W., Friederici, Angela D., Wessels, Jeanine M. I., Svenkerud, Vigdis Y. & Jusczyk, Ann Marie (1993). Infants' sensitivity to the sound patterns of native language words. Journal of Memory and Language 32. 402–420.CrossRefGoogle Scholar
Jusczyk, Peter W., Smolensky, Paul & Allocco, Theresa (2002). How English-learning infants respond to markedness and faithfulness constraints. Language Acquisition 10. 31–73.CrossRefGoogle Scholar
Kager, René (1999). Optimality Theory. Cambridge: Cambridge University Press.Google Scholar
Kager, René, Pater, Joe & Zonneveld, Wim (eds.) (2004). Constraints in phonological acquisition. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Keller, Frank & Asudeh, Ash (2002). Probabilistic learning algorithms and Optimality Theory. LI 33. 225–244.Google Scholar
Kivinen, Jyrki (2003). Online learning of linear classifiers. In Mendelson, Shahar & Smola, Alexander J. (eds.) Advanced lectures on machine learning. Berlin & Heidelberg: Springer. 235–257.Google Scholar
Legendre, Géraldine, Miyata, Yoshiro & Smolensky, Paul (1990a). Harmonic Grammar: a formal multi-level connectionist theory of linguistic well-formedness: an application. In Proceedings of the 12th Annual Conference of the Cognitive Science Society. Hillsdale: Erlbaum. 884–891.Google Scholar
Legendre, Géraldine, Miyata, Yoshiro & Smolensky, Paul (1990b). Harmonic Grammar: a formal multi-level connectionist theory of linguistic well-formedness: theoretical foundations. In Proceedings of the 12th Annual Conference of the Cognitive Science Society. Hillsdale: Erlbaum. 388–395.Google Scholar
Levelt, Clara C., Schiller, Niels O. & Levelt, Willem J. (2000). The acquisition of syllable types. Language Acquisition 8. 237–264.CrossRefGoogle Scholar
Lombardi, Linda (1999). Positional faithfulness and voicing assimilation in Optimality Theory. NLLT 17. 267–302.Google Scholar
McLeod, Sharynne, Doorn, Jan van & Reed, Vicki A. (2001). Normal acquisition of consonant clusters. American Journal of Speech-Language Pathology 10. 99–110.Google Scholar
Magri, Giorgio (2009). A theory of individual-level predicates based on blind mandatory scalar implicatures: constraint promotion for Optimality Theory. PhD dissertation, MIT.Google Scholar
Magri, Giorgio (2010). Complexity of the acquisition of phonotactics in Optimality Theory. In Heinz, Jeffrey, Cahill, Lynne & Wicentowski, Richard (eds.) SIGMORPHON 2010: 11th Meeting of the ACL Special Interest Group on Computational Morphology and Phonology. Uppsala: Association for Computational Linguistics. 19–27.Google Scholar
Magri, Giorgio (2011). An online model of the acquisition of phonotactics within Optimality Theory. In Carlson, Laura, Hölscher, Christoph & Shipley, Thomas F. (eds.) Expanding the space of cognitive science: Proceedings of the 33rd Annual Conference of the Cognitive Science Society. Austin: Cognitive Science Society. 2012–2017.Google Scholar
Magri, Giorgio (2012a). Convergence of error-driven ranking algorithms: extension to the stochastic case. Ms, LFF, CNRS/Université Paris 7.Google Scholar
Magri, Giorgio (2012b). Restrictiveness of error-driven ranking algorithms: an initial assessment. Ms, LFF, CNRS/Université Paris 7.Google Scholar
Magri, Giorgio (2012c). A note on the GLA's choice of the current loser from the perspective of factorizability. Ms, LFF, CNRS/Université Paris 7.Google Scholar
Magri, Giorgio (to appear a). Complexity of the acquisition of phonotactics in Optimality Theory. LI. Earlier version available as ROA-1138 from the Rutgers Optimality Archive.Google Scholar
Magri, Giorgio (to appear b). HG has no computational advantages over OT: towards a new toolkit for Computational OT. LI.Google Scholar
Pater, Joe (2008). Gradual learning and convergence. LI 39. 334–345.Google Scholar
Pater, Joe (2009). Weighted constraints in generative linguistics. Cognitive Science 33. 1–37.CrossRefGoogle ScholarPubMed
Pater, Joe & Barlow, Jessica A. (2003). Constraint conflict in cluster reduction. Journal of Child Language 30. 487–526.CrossRefGoogle ScholarPubMed
Prince, Alan (2002). Entailed ranking arguments. Ms, Rutgers University. Available as ROA-500 from the Rutgers Optimality Archive.Google Scholar
Prince, Alan & Smolensky, Paul (2004). Optimality Theory: constraint interaction in generative grammar. Malden, Mass. & Oxford: Blackwell.Google Scholar
Prince, Alan & Tesar, Bruce (2004). Learning phonotactic distributions. In Kager et al. (2004). 245–291.CrossRefGoogle Scholar
Riggle, Jason (2009). The complexity of ranking hypotheses in Optimality Theory. Computational Linguistics 35. 47–59.CrossRefGoogle Scholar
Smit, Ann Bosma, Hand, Linda, Freilinger, J. Joseph, Bernthal, John E. & Bird, Ann (1990). The Iowa Articulation Norms Project and its Nebraska replication. Journal of Speech and Hearing Disorders 55. 779–798.CrossRefGoogle ScholarPubMed
Smolensky, Paul (1996a). On the comprehension/production dilemma in child language. LI 27. 720–731.Google Scholar
Smolensky, Paul (1996b). The initial state and ‘Richness of the Base’ in Optimality Theory. Ms, Johns Hopkins University. Available as ROA-154 from the Rutgers Optimality Archive.Google Scholar
Stemberger, Joseph P. & Bernhardt, Barbara H. (1999). The emergence of faithfulness. In MacWhinney, Brian (ed.) Emergence of language. Hillsdale: Erlbaum. 417–446.Google Scholar
Stemberger, Joseph P. & Bernhardt, Barbara H. (2001). U-shaped learning in language acquisition, and restrictions on error correction. Available as ROA-472 from the Rutgers Optimality Archive.Google Scholar
Stemberger, Joseph P., Bernhardt, Barbara H. & Johnson, Carolyn (2001). U-shaped learning in phonological development. Available as ROA-471 from the Rutgers Optimality Archive.Google Scholar
Tesar, Bruce (1995). Computational Optimality Theory. PhD dissertation, University of Colorado, Boulder. Available as ROA-90 from the Rutgers Optimality Archive.Google Scholar
Tesar, Bruce (1998). Error-driven learning in Optimality Theory via the efficient computation of optimal forms. In Barbosa, Pilar, Fox, Danny, Hagstrom, Paul, McGinnis, Martha & Pesetsky, David (eds.) Is the best good enough? Optimality and competition in syntax. Cambridge, Mass.: MIT Press. 421–435.Google Scholar
Tesar, Bruce (2004). Using inconsistency detection to overcome structural ambiguity. LI 35. 219–253.Google Scholar
Tesar, Bruce (2008). Output-driven maps. Ms, Rutgers University. Available as ROA-956 from the Rutgers Optimality Archive.Google Scholar
Tesar, Bruce & Smolensky, Paul (1996). Learnability in Optimality Theory (long version). Baltimore: Department of Cognitive Science, Johns Hopkins University.Google Scholar
Tesar, Bruce & Smolensky, Paul (1998). Learnability in Optimality Theory. LI 29. 229–268.Google Scholar
Tesar, Bruce & Smolensky, Paul (2000). Learnability in Optimality Theory. Cambridge, Mass.: MIT Press.Google Scholar
Tessier, Anne-Michelle (2009). Frequency of violation and constraint-based phonological learning. Lingua 119. 6–38.CrossRefGoogle Scholar
Wexler, Kenneth & Culicover, Peter W. (1980). Formal principles of language acquisition. Cambridge, Mass.: MIT Press.Google Scholar
Zamuner, Tania S., Gerken, LouAnn & Hammond, Michael (2005). The acquisition of phonology based on input: a closer look at the relation of cross-linguistic and child language data. Lingua 115. 1329–1474.Google Scholar
Supplementary material: File

Magri et al. supplementary data

Supplementary data

Download Magri et al. supplementary data(File)
File 362 KB
Supplementary material: PDF

Magri supplementary material

Appendix

Download Magri supplementary material(PDF)
PDF 3.4 MB