1,356,253 research outputs found
Determining underlying presence in the learning of grammars that allow insertion and deletion
No full textThe simultaneous learning of a phonological map from inputs to outputs and a lexicon of phonological underlying forms has been a focus of several research efforts (Jarosz 2006; Apoussidou 2007; Merchant 2008; Merchant & Tesar 2008; Tesar 2014). One of the numerous challenges is that of computational efficiency, which led to the investigation of learning with output-driven maps (Tesar 2014). Prior work on learning with output-driven maps has focused on systems in which the only disparities between inputs and outputs were segmental identity disparities (differences in the value of a feature). Inclusion of segmental insertion and deletion disparities exacerbates computational concerns, as it increases the number of possible correspondence relations between an input and an output, and makes the space of possible inputs for a word infinite due to the possible presence of an unbounded number of deleted segments. We propose an extension of that earlier work to handle phonologies that permit insertion and deletion, and evaluate the proposal by applying it to cases in Basic CV Syllable Theory (Jakobson 1962; Clements & Keyser 1983; Prince & Smolensky 2004). First, we propose that a learner represent information about the possible presence/absence of a segment in an underlying form via a presence feature. The presence feature can be set using the same inconsistency detection method that has previously been used to set other segmental features. This allows the learner to combine evidence from paradigmatically related words in a single compact representation. Second, we propose that the learner only consider for underlying forms segments that surface in at least one surface realization of the morpheme. This approach is justified by the structure of output-driven maps, and avoids the potential for an unbounded number of possibly deleted segments in an underlying form. A proof is given for the validity of the method for avoiding unbounded deletion. The resulting learner is able to learn some grammatical regularities about segmental insertion and deletion; this is shown via two manual step-by-step applications of the algorithm. Verificatory simulations for learning the entire typology of Basic CV Syllable Theory are left to work in the near future.Peer reviewe
Learning Phonological Grammars for Output-Driven Maps
No full textThe challenge of simultaneously learning a lexicon of underlying forms and a constraint ranking has been addressed by several scholars in recent work (Apoussidou 2007, Jarosz 2006, Merchant 2008, Tesar 2006). In particular, the proposal of Merchant, the Contrast Pair and Ranking information algorithm (CPR), avoids having to explicitly enumerate all possible underlying forms for each morpheme (in contrast to Apoussidou and Jarosz), and also avoids having to explicitly enumerate all possible constraint rankings (in contrast to Jarosz).
While CPR avoids those computational traps, there are still some components of CPR (and of the related work by Tesar) that pose computational difficulties. (1) The focus of CPR on lexical hypotheses for only a pair of related words at a time (a contrast pair) is a vast improvement over simultaneous consideration of all possible lexica, but the space of lexical hypotheses for a single contrast pair still grows exponentially in the number of unset underlying features for the morphemes involved in the pair. (2) The technique of initial lexicon construction, setting in advance features that do not alternate, can restrict further the number of lexical hypotheses that need to be considered, but at the cost of requiring that the learner have a complete paradigm of surface form data before learning of underlying forms can begin. (3) The extraction of ranking information performed by CPR is able to obtain ranking information from contrast pairs for which complete underlying forms have not yet been determined, but also faces exponential computational complexity, due in part to the fact that the procedure is separately computing the ranking implications of each lexical hypothesis in the (exponentially growing) set of possible hypotheses for the contrast pair.
The current paper demonstrates that each of these computational concerns can be significantly improved upon by taking the structure of grammars into greater consideration. The key grammatical structure lies in Tesar's proposal of output-driven map (Tesar 2008). Intuitively, an output-driven map is a phonological map in which all disparities introduced between the input and the output are motivated by conditions on the output. This notion is formalized by the requirement that any grammatical input-output mapping A->C entails the grammaticality of B->C whenever B has 'greater similarity' to C than A does (A->C has every input-output disparity that B->C does, but B->C may lack some disparities of A->C). An output-driven map is necessarily a restricted identity map (Prince and Tesar 2004), meaning that every grammatical form maps to itself, a property assumed to hold of grammars in much learnability work, including that of Merchant. Output-driven maps can be viewed as a strengthened version of restricted identity maps.
The structure of output-driven maps can be exploited in learning via the contrapositive: B~->C entails A~->C. Given a grammatical output C, it is a given that C->C (restricted identity map property). Suppose B has one disparity with C (e.g., they differ in the value of one feature on one segment). If the learner possesses sufficient information to determine that B cannot map to C, then the learner need not bother checking to see if A maps to C; because the map is output-driven, any input which has, relative to C, all of the disparities of B plus additional ones cannot be grammatical. All lexical hypotheses which include all of the disparities of B->C may be dismissed without evaluation. Instead of needing to evaluate all combinations of possible values for all unset features of a word (exponential in the number of unset features), the learner can obtain the same information while only evaluating a single unset feature at a time (linear in the number of unset features), having the other unset features match (temporarily) the values of their output correspondents, addressing concern (1). If a word has eight unset binary features, this means evaluating 8 lexical hypotheses instead of 256. Even greater benefit is realized when obtaining ranking information from forms with unset features, addressing concern (3).
The speed-up realized by exploiting the structure of output-driven maps is significant enough that initial lexicon construction is no longer needed. This frees the learner from needing an entire paradigm before learning commences; the learner can begin learning about underlying forms from even a single datum, addressing concern (2). This algorithm has the notable property that features of underlying forms which cannot be shown to require a particular value remain unset; non-contrastive features are never set, without any need for the learner to separately construct an 'inventory of contrastive features'.The definitive version of this paper is published in NELS 39: Proceedings of the 39th Annual Meeting of the North East Linguistic Society (2011
Phonological Learning with Output-Driven Maps
No full textThe concept of an output-driven map formally characterizes an intuitive notion about phonology: that disparities between the input and the output are introduced only to the extent necessary to satisfy restrictions on outputs. When all of the grammars definable in a phonological system are output-driven, the implied structure provides significant computational benefits to language learners. An output-driven map imposes significant structure on the space of possible inputs for words, which can allow a learner to efficiently learn a lexicon of phonological underlying forms despite the vast number of possible lexica, as well as contend with the challenges of map/lexicon interactions inherent in phonological learning. This article presents a learning algorithm that exploits the structure of output-driven maps, illustrated with a system of grammars based in Optimality Theory. The algorithm highlights the roles played by contrast and paradigmatic information in phonological learning.Peer reviewe
Faithful contrastive features in learning
No full textThis paper pursues the idea of inferring aspects of phonological underlying forms directly from surface contrasts by looking at Optimality Theoretic linguistic systems (Prince & Smolensky, 1993/2004). The main result proves that linguistic systems satisfying certain conditions have the Faithful Contrastive Feature property: whenever two distinct morphemes contrast on the surface in a particular environment, at least one of the underlying features on which the two differ must be realized faithfully on the surface. A learning procedure exploiting the Faithful Contrastive Feature property, Contrast Analysis, can set the underlying values of some features, even where featural minimal pairs do not exist, but is nevertheless fundamentally limited in what it can set. This work suggests that observation of surface contrasts between pairs of words can contribute to the learning of underlying forms, while still supporting the view that interaction with the phonological mapping will be necessary to fully determine underlying forms.Peer reviewe
Learnability in optimality theory
No full textIn this article we show how Optimality Theory yields a highly general Constraint Demotion principle for grammar learning. The resulting learning procedure specifically exploits the grammatical structure of Optimality Theory, independent of the content of substantive constraints defining any given grammatical module. We decompose the learning problem and present formal results for a central subproblem, deducing the constraint ranking particular to a target language, given structural descriptions of positive examples. The structure imposed on the space of possible grammars by Optimality Theory allows efficient convergence to a correct grammar. We discuss implications for learning from overt data only, as well as other learning issues. We argue that Optimality Theory promotes confluence of the demands of more effective learnability and deeper linguistic explanation.Peer reviewe
Enforcing Grammatical Restrictiveness Can Help Resolve Structural Ambiguity
No full textThis paper deals with the interaction between two problems that arise in human language learning, structural ambiguity and the subset problem. The main claim of this paper is that the notion of r-measure, already proposed as a measure of grammatical restrictiveness, can be used to deal with complexities in structural ambiguity that result from interactions with subset learning. The approach combines an algorithm for contending with structural ambiguity, the Inconsistency Detection Learner, with an algorithm for dealing with the subset problem, Biased Constraint Demotion. Biased Constraint Demotion is designed to find, for a set of data, the grammar with the best r-measure, a measure of grammatical restrictiveness based upon a preference for markedness constraints dominating faithfulness constraints. The Inconsistency Detection Learner component tries different combinations of interpretations of structurally ambiguous forms, keeping only those combinations that are consistent with at least one grammar. For each such combination of interpretations, Biased Constraint Demotion is used to find the most restrictive grammar consistent with the interpretations. The different grammars are then compared with respect to their r-measures, and the grammar with the best r-measure is chosen by the learner as the final learned grammar. Computer simulation results, running the algorithm on an example exhibiting interaction between structural ambiguity and the subset problem, are presented
An Iterative Strategy for Learning Metrical Stress in Optimality Theory
No full textOne of the major challenges of language acquisition is the fact that the auditory signal received by a child can underdetermine the structural description of the utterance. This paper presents an approach to the problem via an idea borrowed from statistical learning theory, an approach that depends critically upon the optimizing structure of Optimality Theory. The learner starts with an initial hypothesized ranking of the constraints. It uses that ranking to make a best guess at the full structural description of an observed overt form. The learner then treats this full description as correct, and uses it to refine its ranking hypothesis. The full description and the ranking are alternately refined, each with respect to the other, in iterative fashion. Success is achieved when, despite starting from an incorrect hypothesis ranking, the learner is able to iteratively converge upon the correct ranking, and thus also assign the correct descriptions to observed overt forms. This paper presents some results of simulations applying this approach to an OT system for metrical stress grammars, including quantity sensitivity. The degree of success achieved by a simple implementation of this strategy, which is applicable to OT systems generally, is presented as evidence that the optimizing structure inherent in OT has an important role to play in an overall account of language learning.The definitive version of this paper was published in BUCLD 21: Proceedings of the 21st Annual Boston University Conference on Language Development (1997) and is available at http://www.cascadilla.com/bucld21toc.htm
Computing Optimal Forms in Optimality Theory: Basic Syllabification
No full textIn Optimality Theory, grammaticality is defined in terms of optimization over a large (often infinite) space of candidates. This raises the question of how grammatical forms might be computed. This paper presents an analysis of the Basic CV Syllable Theory (Prince & Smolensky 1993) showing that, despite the nature of the formal definition, computing the optimal form does not require explicitly generating and evaluating all possible candidates. A specific algorithm is detailed which computes the optimal form in time that is linear in the length of the input. This algorithm will work for any grammar in Optimality Theory employing regular position structures and universal constraints which may be evaluated on the basis of local information.An excerpted reprint of this paper was published in Optimality Theory in Phonology: A Reader (2004
The Learnability of Optimality Theory: An Algorithm and Some Basic Complexity Results
No full textIf Optimality Theory (Prince & Smolensky 1991, 1993) is correct, Universal Grammar provides a set of universal constraints which are highly general, inherently conflicting, and consequently rampantly violated in the surface forms of languages. A language’s grammar ranks the universal constraints in a dominance hierarchy, higher-ranked constraints taking absolute priority over lower-ranked constraints, so that violations of a constraint occur in well-formed structures when, and only when, they are necessary to prevent violation of higher-ranked constraints. Languages differ principally in how they rank the universal constraints in their language-specific dominance hierarchies. The surface forms of a given language are structural descriptions of inputs which are optimal in the following sense: they satisfy the universal constraints, or, when these constraints are brought into conflict by an input, they satisfy the highest-ranked constraints possible. This notion of optimality is partly language-specific, since the ranking of constraints is language-particular, and partly universal, since the constraints which evaluate well-formedness are (at least to a considerable extent) universal. In many respects, ranking of universal constraints in Optimality Theory plays a role analogous to parameter-setting in principles-and-parameters theory.A version of this paper was presented at the Rutgers Optimality Workshop #1, October 1993
Computational Optimality Theory
No full textIn Optimality Theory, a linguistic input is assigned a grammatical structural description by selecting, from an infinite set of candidate structural descriptions, the description which best satisfies a ranked set of universal constraints. Cross-linguistic variation is explained as different rankings of the same universal constraints. Two questions are of primary interest concerning the computational tractibility of Optimality Theory. The first concerns the ability to compute optimal structural descriptions. The second concerns the learnability of the constraint rankings. Parsing algorithms are presented for the computation of optimal forms,using dynamic programming. These algorithms work for grammars in Optimality Theory employing universal constraints which may be evaluated on the basis of information local within the structural description. This approach exploits optimal substructure to construct the optimal description, rather than searching for the solution by moving from one entire description to another. A class of learning algorithms, the Constraint Demotion algorithms,are presented, which solve the problem of learning constraint rankings based upon hypothesized structural descriptions (an important sub problem of the general problem of language learning). Constraint Demotion exploits the implicit negative evidence available in the form of the competing (suboptimal) structural descriptions of the input. The data complexity of this algorithm is quadratic in the number of constraints.Ph.D
- …
