2.1 Preliminaries: ranking, weighting and probability

Before we turn to the problem of hidden structure learning in Stochastic OT and Noisy HG, these frameworks are briefly reviewed here (for further reading see Boersma Reference Boersma1997, Boersma & Hayes Reference Boersma and Hayes2001, Boersma & Pater Reference Boersma, Pater and McCarthy2008, Pater Reference Pater2009b, to appear). In Stochastic OT (Boersma Reference Boersma1997, Boersma & Hayes Reference Boersma and Hayes2001) constraints are associated with a ranking value along a continuous scale. At evaluation time, random noise (sampled from a normal distribution centred around zero) is added to the ranking value of each constraint independently, and the resulting relative ordering is interpreted as a strict ranking for optimisation. In this way, Stochastic OT defines a probability distribution over total orderings of constraints, with re-ranking likely for constraints with similar ranking values and unlikely for constraints ranked far apart. The Gradual Learning Algorithm (GLA) for Stochastic OT (Boersma Reference Boersma1997, Boersma & Hayes Reference Boersma and Hayes2001) makes use of the continuous scale by making small, repeated updates to the ranking values of constraints during learning.

In Harmonic Grammar (Legendre et al. Reference Legendre, Miyata and Smolensky1990, Smolensky & Legendre Reference Smolensky and Legendre2006, Pater Reference Pater2009a, Reference Paterb), constraints are weighted rather than strictly ranked. A candidate's harmony is defined as a weighted sum of constraint violations, with each violation multiplied by the weight of the corresponding constraint. Constraint violations are generally expressed as negative integers, and the candidate with the highest (closest to zero) harmony is optimal. This is illustrated in the simple example in (1), with three candidates and three constraints.

1. (1)

   

The weight of each constraint is multiplied by the number of constraint violations, and summed over all constraints to yield the harmony, shown on the right. This example illustrates how in HG, in contrast to OT, lower-weighted constraints can overpower higher-weighted constraints: here, Candidate B is optimal, with a harmony of −5, even though it violates the highest-weighted constraint, while the other candidates do not. In Noisy HG (Boersma & Pater Reference Boersma, Pater and McCarthy2008, Pater Reference Pater2009b, to appear), random noise is added to the constraint weights in the same way that it is added to the ranking values in Stochastic OT. After noise has been added to the weights in Noisy HG, the resulting weighting is used to calculate the optimal candidate. Weighted grammars can be learned using an online learning algorithm that relies on the perceptron update rule (Rosenblatt Reference Rosenblatt1958, Soderstrom et al. Reference Soderstrom, Mathis, Smolensky, Smolensky and Legendre2006) and is otherwise identical to the Gradual Learning Algorithm for Stochastic OT. Following Boersma & Pater (Reference Boersma, Pater and McCarthy2008) and Pater (Reference Pater2009b), this paper refers to both algorithms as GLA, and uses OT-GLA and HG-GLA to distinguish the ranking and weighting versions respectively. Thus HG-GLA makes use of the continuous weighting scale by making small adjustments to constraint weights, just as OT-GLA does for constraint-ranking values. This paper focuses on learning in the Noisy HG version of weighted grammars; however, the findings have implications for learning in related weighted grammar frameworks such as maximum entropy grammars, which are briefly discussed in §4.1 (Johnson Reference Johnson, Merlo and Stevenson2002, Goldwater & Johnson Reference Goldwater, Johnson, Spenador, Eriksson and Dahl2003, Fischer Reference Fischer2005, Jäger Reference Jäger, Zaenen, Simpson, King, Grimshaw, Maling and Manning2007, Hayes & Wilson Reference Hayes and Wilson2008).

2.2 Error-driven learning and hidden structure

OT-GLA and HG-GLA are both error-driven learning algorithms (Rosenblatt Reference Rosenblatt1958, Wexler & Culicover Reference Wexler and Culicover1980, Tesar Reference Tesar1995, Tesar & Smolensky Reference Tesar and Smolensky1998). Although the current paper focuses on learning in the stochastic setting, this section also reviews Error-Driven Constraint Demotion (EDCD) and its extensions to the problem of structural ambiguity, since it is in this context that RIP was developed (Tesar Reference Tesar1995, Tesar & Smolensky Reference Tesar and Smolensky1998). Error-driven learning means that updates to the learner's grammar are driven by errors made by the learner while processing the learning data. Specifically, for each learning datum, the learner uses its current grammar to generate its own output for that datum. If the learner's output does not match the learning datum, the learner compares its output (the loser) to the learning datum (the winner) in order to determine how to adjust the grammar. For example, suppose that the learner is presented with the form [tε(ˈlεfɔn)] while learning a language much like Polish, with regular penultimate stress (Rubach & Booij Reference Rubach and Booij1985), and that the learner must correctly rank constraints preferring right and left alignment of feet, AllFeet-R and AllFeet-L respectively, and constraints preferring right-headed and left-headed feet, Iambic and Trochaic respectively. If the learner's current ranking is AllFeet-R≫Iambic≫Trochaic≫AllFeet-L, the learner will generate the incorrect [tε(lεˈfɔn)] for the input /tεlεfɔn/, as shown in (2), where W and L denote winner and loser respectively.

1. (2)

   

As an error-driven learner, the learner will then compare the violations of the loser with the violations of the winner in order to determine which constraints favour the winner and which favour the loser. The precise update rules vary between EDCD, OT-GLA and HG-GLA, but all involve adjusting the relative rankings or weighting of loser-preferring and winner-preferring constraints so as to increase the harmony of the winner compared to the loser. The EDCD learner demotes all undominated loser-preferring constraints to a stratum immediately below the highest ranked winner-preferring constraint (Tesar Reference Tesar1995, Tesar & Smolensky Reference Tesar and Smolensky1998).

The update rules for the OT-GLA (Boersma Reference Boersma1997, Boersma & Hayes Reference Boersma and Hayes2001) and HG-GLA (Boersma & Pater Reference Boersma, Pater and McCarthy2008; see also Rosenblatt Reference Rosenblatt1958, Soderstrom et al. Reference Soderstrom, Mathis, Smolensky, Smolensky and Legendre2006, Jäger Reference Jäger, Zaenen, Simpson, King, Grimshaw, Maling and Manning2007) learners are shown in (3a) and (b) respectively. As shown in (3a), for each constraint i, OT learners compare the violations of the winner W and loser L for constraint i, i.e. c _i(W) and c _i(L) respectively (c_i(X) is the number of violations which constraint i (c_i) assigns to candidate X). Constraint i's ranking value r is increased by ε (the learning rate or plasticity) when the loser has more violations than the winner, and decreased by ε when the winner has more violations than the loser (the sgn function returns −1 for negative, 1 for positive and 0 for zero). Thus ε is added to the ranking values of winner-preferring constraints and subtracted from those of the loser-preferring constraints.

1. (3)

   

The update rule for HG is identical, as shown in (3b), except that the plasticity is multiplied by the difference in the number of violations assigned to the loser and the winner. The HG update rule is an adapted form of the perceptron update rule for training connectionist networks (Rosenblatt Reference Rosenblatt1958), which is itself an adaptation of the standard machine-learning technique gradient ascent, whose online variant is known as stochastic gradient ascent (see Jäger Reference Jäger, Zaenen, Simpson, King, Grimshaw, Maling and Manning2007 for in-depth discussion). In sum, both OT-GLA and HG-GLA slightly decrease the ranking or weighting of all loser-preferring constraints and slightly increase the ranking or weighting of all winner-preferring constraints. In order to calculate the update, both algorithms compare the violations assigned to the loser to the violations assigned to the winner.

In the example in (2), candidate (c) is the winner for the penultimate stress language, while the loser, the learner's own output, is candidate (d). Comparing the violations incurred by candidates (c) and (d), the learner determines that Iambic favours the loser, and Trochaic favours the winner, while the remaining constraints have no preference. Based on this, the learner calculates the update rule, which indicates that Iambic must be demoted, and in OT-GLA and HG-GLA that Trochaic must also be promoted. Despite the differences in update rules between the three algorithms, the processing required to calculate the update is the same: a comparison of the violations incurred by the winner and loser.

The learning strategy just described assumes that the learner is provided with full structural descriptions of the learning data. This means the learner has access to hidden structure such as footing and syllabification, as well as underlying representations, which are not available to the human learner. Access to such hidden structure is crucial for identifying the violations incurred by the winners, which, as just discussed, are crucial for calculating the update. This is because every overt form is structurally ambiguous and corresponds to numerous candidates, each with different hidden structures and therefore distinct constraint violations. In the example above, the learner was presented with a learning datum together with hidden structure, the footing, i.e. [tε(ˈlεfɔn)]. It is this footing that identifies candidate (c) as the winner. In a more realistic learning context, where the learner observes only the overt [tεˈlεfɔn], the learning datum would be ambiguous between candidates (b) and (c). Without full structural descriptions, the learner cannot be sure which of (b) and (c) is actually the winner in this language. The problem is that the constraint violations needed to calculate the grammar update depend on which structure, or parse, is selected. The hidden structure is what determines whether constraints like Iambic are violated. The example in the preceding paragraph made the simplifying assumption that this hidden structure was available to the learner. The same assumption is made by all algorithms, such as EDCD and GLA, whose performance or proofs of correctness presuppose access to full structural descriptions. This is unrealistic, because children acquiring language do not have access to this information. Indeed, determining whether (b) or (c) is the winner is part of learning the grammar of the target language, since different languages may parse a form like [tεˈlεfɔn] differently. In essence, full structural descriptions provide the learner with parses, or analyses, of all the learning data, providing the constraint violations of the learning data to which the learner's losers can be directly compared.

Structural ambiguity thus presents a difficult learning challenge, because it obscures the constraint violations incurred by the learning data, thereby obscuring the update needed to favour the winner (the learning datum) over the loser (the learner's output). In the example in (2), candidates (b) and (c) have drastically different consequences for the resulting grammar. As explained above, selecting candidate (c) as the winner results in an adjustment to the constraints Iambic and Trochaic. On the other hand, if the learner mistakenly selects (b) as the winner, the update will instead involve adjustment of AllFeet-R relative to AllFeet-L, leading to a grammar that is more likely to align feet with the left edge of the word. Furthermore, there is no way to definitively identify the correct parse for a form in isolation – the correct parse can ultimately be determined only by consulting other learning data. For example, in order to determine that the correct analysis involves right-aligned trochees rather than left-aligned iambs, the learner must process other forms that disambiguate between these possibilities, such as disyllabic forms with initial stress. In a more realistic setting, with many more constraints contributing to the selection of the correct hidden structure, the learning data are massively more ambiguous than in this simple example (see e.g. Tesar Reference Tesar2004, Prince Reference Prince2010). Nonetheless, the learner must somehow effectively navigate this huge ambiguous space of possibilities.

2.3 Robust Interpretive Parsing

Within OT, learning in the face of structural ambiguity has been a topic of ongoing work since at least Tesar (Reference Tesar1998) and Tesar & Smolensky (Reference Tesar and Smolensky1998, Reference Tesar and Smolensky2000). In order to apply error-driven learning in the presence of structural ambiguity, Tesar & Smolensky (Reference Tesar and Smolensky1998) propose Robust Interpretive Parsing (RIP), which provides an educated guess, based on the current constraint ranking, about the structure of the observed datum. Specifically, RIP uses the learner's current hierarchy to select the most harmonic candidate among the structural descriptions consistent with an overt form. That is, for a given learning datum, RIP uses standard OT evaluation, but limits candidates to those that share the learning datum's overt form, thereby selecting the most harmonic among the possible structural descriptions, or parses, of the overt form according to the current grammar. The parse produced by RIP is treated as the intended winner and compared to the learner's own output, which is generated by applying the usual ‘production-directed parsing’: the process of mapping the underlying form to its optimal structural description. As shown in (4), this means that when the learner is presented with the unstructured overt form [tεˈlεfɔn], it performs interpretive parsing by finding the most harmonic candidate matching this overt form.

1. (4)

   

In this example, only two candidates, (b) and (c), match the overt form. According to the current ranking, candidate (c), [tε(ˈlεfɔn)], is more harmonic and is therefore selected as the RIP parse and winner. In this case, this is the correct parse for a language like Polish that has right-aligned trochees. Crucially, the learner is capable of identifying the correct parse even though the current grammar is not the target grammar for the penultimate stress language. This crucial property is why Tesar & Smolensky refer to the interpretive parsing procedure as ‘robust’. If learning is to be successful, it is essential for the learner to be able to assign structure to the learning data throughout the learning process. Parsing must be possible even when the learner's grammar differs from the target grammar and does not generate the datum being processed (otherwise, the learner would only be able to parse and learn from data consistent with its initial grammar). This is exactly the solution which RIP provides. Once the learner has assigned a structural description to the learning datum using RIP, production-directed parsing is applied to the underlying form /tεlεfɔn/, producing candidate (d), [tε(lεˈfɔn)]. The winner provided by interpretive parsing, candidate (c), is compared to the result of production-directed parsing, candidate (d), yielding an error. Given the winner and the loser, the grammar update, comparing the violations of the parsed winner to that of the loser, can proceed as usual, according to the update rules discussed above.

As discussed by Tesar & Smolensky (Reference Tesar and Smolensky1998), however, RIP is not foolproof. It can select the wrong parse for the target language, leading the learner astray. This may happen, for example, if the learner in (4) is actually trying to learn a language with left-aligned iambs, corresponding to candidate (b). The learner can sometimes overcome such parsing mistakes, given subsequent disambiguating data. However, the learner can also get stuck in a perpetual loop of mistaken parses and grammars. Tesar & Smolensky (Reference Tesar and Smolensky2000) present simulation results for a RIP version of Error Driven Constraint Demotion (RIP/EDCD) on a large metrical phonology test set with structural ambiguity. They found that RIP/EDCD learned just 60·5% of the languages in the system correctly when starting from an unranked initial hierarchy. In fact, this success rate assumes that learning produces stratified hierarchies and that pooling ties are used to deal with tied constraints, which, as discussed by Boersma (Reference Boersma2009), can mask crucial rankings needed to uniquely select the target output forms under strict ranking. As discussed below, the performance of EDCD drops when evaluation assumes strict ranking. In general, these results indicate that RIP's potential to lead the learner astray is not just hypothetical, since about half of the languages in the system cannot be learned.

RIP has subsequently been extended in several directions. It has been applied to the problem of structural ambiguity using OT-GLA (Apoussidou & Boersma Reference Apoussidou and Boersma2003, Boersma Reference Boersma2003, Apoussidou Reference Apoussidou2007) and HG-GLA (Boersma & Pater Reference Boersma, Pater and McCarthy2008). Another line of work extends Stochastic OT with lexical constraints, constraints that control the choice of underlying representations, and uses RIP/GLA in this context to learn a different kind of hidden structure, namely underlying representations (Apoussidou Reference Apoussidou2006, Reference Apoussidou2007). The performance of these stochastic and weighted variants of RIP is also mixed. Boersma & Pater report on simulations comparing the performance of RIP variants of EDCD, OT-GLA and HG-GLA on the test set used by Tesar & Smolensky (Reference Tesar and Smolensky2000). Their implementation of RIP/EDCD differs from Tesar & Smolensky's: rather than using pooling ties, they use permuting ties (see Boersma Reference Boersma2009 for discussion), and they require EDCD to learn strict rankings. This lowers the performance of RIP/EDCD to 47%. They also find that both OT and HG variants of RIP/GLA outperform RIP/EDCD, with RIP/GLA for Noisy HG displaying the highest performance overall, learning almost 89% of the languages in the system on average. While the performance of RIP/HG-GLA is encouraging, Boersma & Pater find that RIP performs poorly for both classical OT and Stochastic OT, with RIP/OT-GLA learning only around 59% of the languages in the test set. Overall, therefore, Boersma & Pater's results suggest a strong advantage for the HG learners in this context.

As noted above, much other work in OT and related constraint-based frameworks has explored alternative approaches to the hidden structure problem. The present paper, however, takes a closer look at how RIP has been formulated for the stochastic setting, namely the applications of RIP to OT-GLA and HG-GLA. After reviewing the previous computational results more carefully, the following sections identify two main problems with the formulation of RIP for the stochastic setting and propose adjustments to the parsing process that dramatically improve performance.

2.4 The metrical phonology test set and previous results

The simulations presented in this paper rely on the same metrical phonology test set used to evaluate RIP/EDCD, RIP/GLA for OT and RIP/GLA for HG in previous work (Tesar & Smolensky Reference Tesar and Smolensky2000, Boersma Reference Boersma2003, Boersma & Pater Reference Boersma, Pater and McCarthy2008, Jarosz to appear).Footnote ² This allows for replication of and direct comparison with previously reported results using RIP. This section presents that test set and reviews the previous results in more detail.

This test set, first defined and examined by Tesar & Smolensky (Reference Tesar and Smolensky2000), consists of 124 constructed languages that can be modelled by the set of twelve metrical structure constraints shown in (5).

1. (5)

   

Most of these constraints are well known from the literature, with origins in the early OT literature (McCarthy & Prince Reference McCarthy and Prince1993, Prince & Smolensky Reference Prince and Smolensky2004) and pre-OT metrical phonology (Liberman & Prince Reference Liberman and Prince1977, Prince Reference Prince1990, Hayes Reference Hayes1995). One exception is the non-standard formulation of the constraint favouring trochees: FootNon-fin (Tesar Reference Tesar2000). The interaction of these twelve constraints produces a complex artificial system, inspired by natural language stress systems and capable of describing a range of diverse metrical phenomena. The test system has the crucial property of generating structural ambiguity – overt stress patterns in this system are consistent with multiple structural descriptions, and successful learning requires disentangling interdependent and ambiguous requirements made by the individual learning data.Footnote ³ Tesar & Smolensky selected 124 languages from the factorial typology generated by this constraint set to represent a wide range of metrical phenomena. Each language in the system is defined by a set of surface stress patterns for 62 words that can be generated from this constraint set. Words are sequences of light (L) or heavy (H) syllables ranging in length between two and seven syllables (e.g. [H L H L]). Each word is associated with a surface stress pattern (e.g. [ˈH L ˌH L]), indicating placement of primary and secondary stress (if any). Any given ranking or weighting of the constraints assigns a particular foot structure and stress pattern (e.g. [(ˈH L) (ˌH) L]). Indeed, it is the footing that underlies the systematic stress patterns in the system. The learner, however, is exposed only to the overt stress patterns (e.g. [ˈH L ˌH L]) and must infer a ranking or weighting of constraints (and an associated footing) capable of generating the observed surface stress patterns. The learner is considered successful when it has acquired a grammar that is consistent with all the learning data it is exposed to, i.e. when it assigns the correct surface stress patterns to all the words of the language.Footnote ⁴

In addition to examining the learning of various metrical patterns, this system presents a more fundamental challenge to learning models. As discussed earlier, much work in OT decouples the learning strategies from the specific phenomena learners must cope with, focusing on developing learners that are successful regardless of the exact constraints and representations used (Tesar Reference Tesar1995, Reference Tesar2004, Boersma & Pater Reference Boersma, Pater and McCarthy2008, Pater Reference Pater2008, Magri Reference Magri2012). This consideration has played an important role in OT learnability from the beginning: Tesar's (Reference Tesar1995) foundational work proved that, in general, constraint demotion is guaranteed to converge on any target language in its hypothesis space, given fully structured data. One can ask an analogous question about learning in the context of structural ambiguity (see e.g. Tesar Reference Tesar2004): can a given learning algorithm successfully learn a grammar for any structurally ambiguous language in its hypothesis space, regardless of the constraint set? Testing learners on this test set therefore also addresses this more general question. Viewed from this perspective, the test set provides a relatively large and diverse set of challenging target languages to the learners, which compares favourably with previous work in terms of the number of systems tested. For example, Heinz (Reference Heinz2009) considers 109 stress patterns, Gupta & Touretzky (Reference Gupta and Touretzky1994) considered 19 and a number of previous studies examine only a handful of stress systems. Thus, from this computational perspective, good performance on this system reflects the ability to handle a wide range of patterns.

Another perspective, and one that is an important direction for future work, is that of typology and its interaction with learnability. While it is important to determine whether a fully general and feasible solution to structural ambiguity exists, the possibility that successful learnability relies on substantive or formal restrictions on the hypothesis space must also be investigated. Accordingly, it is important to investigate the learnability of attested stress systems and to determine whether structural ambiguity in natural language has particular formal properties that are crucial to its learnability. Metrical phonology is an especially promising domain for such research, since stress typology has been extensively studied, large typologies of stress systems have been developed and large stress databases are available (Hayes Reference Hayes1995, Gordon Reference Gordon2002, van der Hulst et al. Reference Hulst, Goedemans and van Zanten2010). A number of the previous studies discussed earlier examine learning of attested languages (Dresher & Kaye Reference Dresher and Kaye1990, Goldsmith Reference Goldsmith, Cole and Kisseberth1994, Gupta & Touretzky Reference Gupta and Touretzky1994, Heinz Reference Heinz2009), and this is an important direction for future work with constraint-based learners as well. While the Tesar & Smolensky system was inspired by stress typology, it is nonetheless an artificial system, with no direct correspondence to attested languages. In addition, recent theoretical and typological developments have identified some problematic predictions made by the constraints it assumes (McCarthy Reference McCarthy2003, Hyde Reference Hyde2007, Pruitt Reference Pruitt2010). Development of large test sets for constraint learning based on natural language stress typologies will require the integration of theoretical, computational and typological work in order to create a computational implementation of a theory (or theories) of constraints that can be used to model the entire typology. Given the significant recent developments in all of these areas, this presents an exciting opportunity for integration of work from these diverse perspectives.

Thus the test set is not without limitations, but it allows for the primary concerns of the present work to be addressed: namely, the relative performance of different learning models on structurally ambiguous learning data, and the finding from previous work suggesting an advantage for HG on the basis of experiments with this test set. As discussed above, Tesar & Smolensky (Reference Tesar and Smolensky2000) and Boersma & Pater (Reference Boersma, Pater and McCarthy2008) report on RIP simulations with this test set. The results for RIP/EDCD, RIP/OT-GLA and RIP/HG-GLA are summarised in Table I.Footnote ⁵

Table I

Performance of RIP algorithms reported in previous work.

Boersma & Pater allowed each run of each algorithm a maximum of 1,000,000 iterations, where an iteration corresponds to the processing of one overt form. The reported performance is the average of ten separate runs for each algorithm. Performance of RIP/EDCD in both studies was deemed successful when the algorithm had converged to a hierarchy that correctly predicted the stress patterns for each of the 62 forms in the language, making no further errors on the data. As shown in Table I, RIP/EDCD learns roughly between 47% and 60% of the languages in the system correctly, depending on whether pooling or permuting ties are used. As discussed above, the permuting tie simulations make the more standard assumption that target languages must be total rankings. For RIP/OT-GLA and RIP/HG-GLA, Boersma & Pater set the learning rate (plasticity) to 0·10, the evaluation noise to 2 and the initial weights/ranking values to 10. They consider a language to be successfully learned if, when evaluation noise is set to zero, the resulting ranking/weighting correctly generates the stress patterns for all 62 forms in the language. Using these evaluation criteria, they find the performance of RIP/OT-GLA to be about 59%, and that of RIP/HG-GLA to be about 89%, as shown in Table I.

As Boersma & Pater discuss, these results look promising for stochastic approaches and for weighted constraints. The following sections, however, take a closer look at the RIP/GLA algorithms for OT and HG, identifying two main problems with how RIP has been formulated in the stochastic setting. These problems turn out to have significant consequences for the performance of the stochastic RIP learning algorithms.

3.1 Reformulating RIP: resampling

The problem with the original RIP application in the stochastic setting is highlighted when the algorithm is slightly reformulated as in (7) below. The original formulation defines an error in terms of a mismatch between the fully structured Output and the fully structured Parse. It may therefore appear that forms whose overt stress patterns match may be counted as errors if their foot structure differs. However, in the present learning context, where underlying representations are fixed for each learning datum (since they are recoverable from the learning datum), this situation can never arise during learning – whenever the Output and Parse match in their overt stress pattern, they necessarily match in their full structural descriptions. If the Output matches the stress contour of the learning datum, this means the most harmonic candidate according to G′ is a candidate with the observed stress contour. In this context, where underlying forms are held fixed for interpretive parsing, the set of candidates competing with one another for interpretive parsing will be a subset of the candidates competing with one another in production, namely the subset whose overt portion matches the learning datum. Thus the candidate selected as optimal in production is also a candidate for interpretive parsing. If G′ selects a particular candidate as optimal among the full set of candidates, it will also select the same candidate as optimal in a subset containing that candidate. This is true regardless of whether weighting or ranking is used.

Consequently, in the original formulation of RIP, errors only occur when the Output and Parse differ in their overt forms. Therefore, the comparison between the winner and loser can be converted from applying to fully structured forms to applying to the overt forms without affecting the behaviour of the algorithm. This is exactly what the reformulation in (7) does.

1. (7)

   

Note that in the formulation in (6), the RIP step 2b was needed in order to generate the Parse to which the Output could be compared and from which the Input was derived. In the reformulation, RIP parsing is not necessary for checking whether an error has been produced, since only the overt portion of the learning datum is consulted (step 2d). Also, as discussed above, the Input can be recovered directly from the learning datum without parsing. This means the parsing step can therefore be moved inside the conditional, as shown in step 2d.i of the reformulated algorithm. This reformulation does not affect the behaviour of the algorithm, but it does serve to highlight a peculiar aspect of interpretive parsing. Specifically, from the reformulation it is clear that parsing is only relevant in case the selected grammar G′ generates an error. At the point when parsing is required, the learner knows G′ is the wrong grammar, since G′ generated an error for this form. What is odd about this use of interpretive parsing in the stochastic setting, then, is that the learner nonetheless uses the known-to-be-incorrect G′ for interpretive parsing. In the original formulation of RIP in classical OT (Tesar & Smolensky Reference Tesar and Smolensky1998), the learner has no better alternative. In classical OT, the learner's current grammar is a single, categorical ranking, and the learner has no choice but to use this ranking, its current best guess about the target language, for RIP. In the stochastic setting, however, each grammar defines a distribution over rankings (or weightings), and the learner's current knowledge about the target language is richer. The learner has a whole distribution of rankings or weightings available for parsing, and does not need to rely on a ranking or weighting that produced an error.

A simple modification to RIP, Resampling RIP (RRIP), solves this problem, and is defined in (8).

1. (8)

   

The only difference between the algorithms in (7) and (8) is that the new algorithm samples a new grammar for interpretive parsing: this is shown in step 2d.i. Specifically, if the learner's output fails to match the learning datum, the learner simply samples another grammar G″ from G_i, and uses it for interpretive parsing. This is the simplest possible way for the learner to reference its stochastic grammatical knowledge, relying only on mechanisms (sampling a random grammar) that are needed anyway. To see the effect of this resampling, consider a learner which has not yet settled on the target grammar, but whose current stochastic grammar generates the target ranking or weighting with some probability. This is the situation the learner starts out in if all constraints are ranked or weighted equally. Initially, all rankings or weightings are equally likely, and, as learning progresses, the distribution over rankings or weightings narrows, focusing gradually on more suitable grammars. If the learner samples an incorrect G′ for production and makes an error, the original RIP algorithm will nonetheless consistently use G′ for parsing. In contrast, RRIP will select another grammar, according to its current knowledge about which rankings or weightings are likely. Whereas RIP is doomed to use an incorrect ranking or weighting for parsing, RRIP's resampling makes it possible for the learner to select a correct ranking or weighting to use for interpretive parsing, increasing the likelihood that the resulting parse will be correct for the target language. Put differently, when the learner's ranking or weighting fails to produce the observed stress pattern, the learner falls back on its rich stochastic grammatical knowledge to select another ranking or weighting it has some confidence in. It uses its stochastic grammar to select with high probability those rankings or weightings that provide the current best guess about the hidden structure. There is a chance that resampling will end up selecting the same parse, but, unlike RIP, RRIP also has a chance of selecting a different grammar, and it does so in proportion to its confidence in different grammars.Footnote ⁶ In this way, the learner takes advantage of the rich information represented by its stochastic grammar.

Clearly, the computational differences between RIP and RRIP are minimal. The computational cost of resampling is negligible, since selecting a random ranking or weighting from the current stochastic grammar can be done very efficiently. In fact, RRIP has a potential computational advantage, since it performs parsing (and resampling) only when there is an error, whereas RIP automatically parses each overt form. It is worth noting that the reformulation in (7) is crucial for the resampling modification. Simply resampling from the grammar in (6) prior to production would not work, since in (6) errors are defined in terms of fully structured candidates. Such a learner would count as errors not only outputs that fail to match the datum, but also outputs that match the datum but, due to a random and arbitrary difference between G′ and G″, differ from the parse with respect to their structure. The randomly occurring differences in grammars between the two samplings would therefore lead to many spurious errors and grammar updates. Of course, such a variant would be equivalent in behaviour to RRIP (albeit less efficient) if, in addition to resampling, the error was defined in terms of overt forms only, as in (7) and (8). In sum, there are two crucial computational differences between RIP and RRIP: (i) RRIP selects a new random ranking or weighting for parsing rather than using the one used in production, and (ii) it defines errors as mismatches in overt forms rather than fully structured forms.

The next section explores the effect these differences have on performance. The simulations focus on RIP and RRIP versions of GLA for OT and HG. The modifications in RRIP would have no effect on the performance of EDCD, since in EDCD there only is one ranking that can be used for parsing. However, it is useful to keep in mind the performance of RIP/EDCD reported in previous work and summarised in Table I, as it provides a point of reference for performance of RIP in classical OT.

3.2 Resampling Robust Interpretive Parsing simulations and results

Simulations were performed in order to compare the performance of HG and OT variants of RIP/GLA and RRIP/GLA. As discussed earlier, all simulations were performed with the grammatical stress test system developed by Tesar & Smolensky (Reference Tesar and Smolensky2000). One goal of the simulations is to replicate Boersma & Pater's (Reference Boersma, Pater and McCarthy2008) results and to determine the robustness and variability of RIP for OT and HG. Simulations of RIP for both OT-GLA and HG-GLA were therefore performed with the parameters used by Boersma & Pater: learning rate (plasticity) of 0·10, evaluation noise of 2 and initial ranking/weighting values of 10. Following Boersma & Pater, all runs were allowed a maximum of 1,000,000 iterations for learning. Also following Boersma & Pater, success was defined as correct generation of stress patterns for all 62 overt forms in a language, using the learner's grammar with evaluation noise set to zero. Since the algorithms are non-deterministic, ten runs each of RIP/OT-GLA and RIP/HG-GLA with these parameter settings were performed, in order to calculate average performance and variation in performance from run to run.

In addition, simulations with a range of other parameter settings were performed, in order to examine sensitivity of the algorithms to the learning parameters. Specifically, in addition to the learning rate of 0·10, both OT and HG variants of RIP were tested with learning rates of 0·05, 0·25 and 0·50. Finally, all the same manipulations were performed for the new RRIP algorithm for both the OT and HG versions. The results of these 160 simulated learners on the 124 languages in the system (a total of 19,840 separate runs) are summarised in Table II, which shows the average percentage of languages learned correctly and the sample standard deviation for each algorithm/plasticity combination.

Table II

Success rate (in %) of RIP and RRIP across various parameter settings. Sample standard deviation is given in parentheses. Shaded cells replicate the results of Boersma & Pater (2008). Best scores for each model are shown in bold.

Consider first the simulations shown in the shaded cells of Table II, which replicate the results reported by Boersma & Pater (Reference Boersma, Pater and McCarthy2008), summarised earlier in Table I. The performance for RIP/HG-GLA shown here (88·71%) is nearly identical to the results reported by Boersma & Pater (88·63%). The performance of RIP/OT-GLA, 56·13%, is a few percentage points lower than the earlier result of 58·95%. This difference of 2·82 is suspiciously high for the sample standard deviation of 1·62. The discrepancy may be due to a difference in terminating conditions. All performance results presented here assume that learning continues for the maximum number of iterations as long as the learner's stochastic grammar continues to make errors, even if the grammar with noise removed correctly generates the data. Occasionally, learners temporarily enter a grammar that makes no errors with evaluation noise removed, but because their stochastic grammars have not actually converged, they later change their grammars to ones that do produce errors on subsequent iterations. In the results reported here, learners were only counted as successful if they made no errors on subsequent iterations. If, however, these learners were counted as successful and the subsequent iterations ignored, the performance of RIP/OT-GLA in the current simulations would increase to 59·84%, comparable to Boersma & Pater's result of 58·95%. Thus, apart from what may be a difference in terminating conditions, the present simulations do replicate Boersma & Pater's reported results. Importantly, the present results replicate the major effects identified by Boersma & Pater.

The results confirm Boersma & Pater's finding that RIP/HG-GLA dramatically outperforms RIP/OT-GLA. Furthermore, the results in Table II show performance of RIP/OT-GLA and RIP/HG-GLA at several additional learning rates. These results indicate that learning rate does affect the performance of the algorithms, with the HG learners showing rather more sensitivity to learning rate. RIP/HG-GLA performs better at lower learning rates, while RIP/OT-GLA performs somewhat better at higher learning rates. In general, however, the variation in performance on runs of RIP/OT-GLA and runs of RIP/HG-GLA is very small in comparison to differences in performance between the OT-GLA and HG-GLA algorithms. RIP/HG-GLA performs significantly better than RIP/OT-GLA across all learning rates tested (p<0·001; Welch two-sample t-test), confirming that the substantial difference in performance between RIP/OT-GLA and RIP/HG-GLA is meaningful.

The results most central to the present work concern the performance of RRIP relative to RIP. As shown in Table II, the difference in performance between RIP/OT-GLA and RRIP/OT-GLA is substantial: the gain in performance is apparent across parameter settings and is about 25 percentage points. Whereas RIP/OT-GLA learns only 56–58% of the languages correctly, RRIP/OT-GLA learns 80–84% of languages correctly, depending on learning rate. This difference in performance between RIP/OT-GLA and RRIP/OT-GLA is substantial, and highly significant across all learning rates (p<0·001; Welch two-sample t-test). RRIP/OT-GLA appears to be a little more sensitive than RIP/OT-GLA to learning rate, with better performance at lower learning rates. Despite the increase in performance for OT-GLA, RRIP/OT-GLA nonetheless performs worse than RRIP/HG-GLA; this difference is significant at all learning rates (p<0·05; Welch two-sample t-test). Finally, the effect of using RRIP rather than RIP with HG-GLA is less clear. Performance of RRIP/HG-GLA is numerically better than RIP/HG-GLA, but the difference is small, and significant only at learning rate 0·25 (p<0·05; Welch two-sample t-test). Based on these parameter settings, therefore, it is not entirely clear whether RRIP/HG-GLA is an improvement over RIP/HG-GLA. However, §4.4 explores additional parameter settings for HG-GLA, where the difference in performance between RIP and RRIP becomes clearer.

4.1 The mismatch

The parsing–production mismatch is equally relevant for RIP and RRIP. Both procedures rely on selecting a ranking or weighting randomly according to the stochastic grammar, and then using that ranking or weighting to identify the most harmonic of the possible parses. The problem is that the probability with which this two-step parsing process generates parses does not match the relative probabilities of producing those parses under the stochastic grammar.

To see this mismatch, consider the example in (9), in which stress and footing is assigned to the input /L L L/.

1. (9)

   

Suppose the learner's current Stochastic OT grammar has a tie between AllFeet-L and AllFeet-R, for example by ranking both constraints at 300, and the next highest-ranked constraint is Trochaic, at 200, and finally Iambic, at 100. Such a Stochastic OT grammar will generate two rankings with equal probability: AllFeet-L≫AllFeet-R≫Trochaic≫Iambic and AllFeet-R≫AllFeet-L≫Trochaic≫Iam-bic. Assuming a standard noise setting of 2, all other rankings will have a probability so low as to be zero for practical purposes. The two rankings generate two distinct outputs. If AllFeet-L is highest-ranked, the output will be [(ˈL L) L], candidate (a), whereas if AllFeet-R is highest-ranked, the output will be [L (ˈL L)], candidate (c). Thus, this grammar generates each of [(ˈL L) L] and [L (ˈL L)] approximately 50% of the time. Note that these outputs have different stress patterns, and that each stress pattern is generated with a unique structure. In particular, the grammar generates the pattern [L ˈL L] using right-aligned trochees: [L (ˈL L)].

Suppose the learning datum is [L ˈL L] and the learner must use its stochastic grammar to parse this datum. To perform Robust Interpretive Parsing, the learner restricts optimisation to (9b) and (c), those candidates that match the overt stress pattern. Given [L ˈL L], what parses does RIP generate? The generated parse depends on the relative ranking of AllFeet-L and AllFeet-R, with both relative rankings occurring about 50% of the time under the current grammar. Thus, RIP will select both candidate (b), the parse [(L ˈL) L], and candidate (c), the parse [L (ˈL L)], about 50% of the time. In other words, RIP identifies two possible parses for [L ˈL L], and generates them with equal probability. The problem is that, as discussed above, the grammar only generates [L ˈL L] using one of these parses, namely [L (ˈL L)]. In other words, according to the learner's current grammar, [L (ˈL L)] is the only possible parse of [L ˈL L], but RIP fails to reflect this categorical restriction imposed by the grammar. Put differently, the learner's current grammar already reflects the ranking conditions inherent to selecting trochees. After all, the grammar ranks Trochaic above Iambic, indicating its preference for trochees. RIP, however, fails to capitalise on this knowledge during interpretive parsing, allowing incompatible parses to be generated.Footnote ⁷

The failures of RIP to rely on accumulated grammatical knowledge are not restricted to categorical ranking information. Suppose that Trochaic, instead of being strictly ranked above Iambic, is partially tied with it, so that the probability of Trochaic≫Iambic is 90%, with the opposite ranking occurring 10% of the time. This grammar, which is otherwise the same as the one above, has some probability of generating candidates (b) and (d). In particular, this grammar generates each of (a) and (c) with 45% probability and each of (b) and (d) with 5% probability. Thus the new grammar generates [L ˈL L] using two different structures, but it considers the right-aligned parse to be nine times more likely than the left-aligned parse. All the same, RIP is oblivious to this statistical preference. For the choice between candidates (b) and (c), the relative ranking of AllFeet-L and AllFeet-R is decisive, making the relative ranking of Trochaic and Iambic irrelevant. Since AllFeet-L is highest-ranked 50% of the time, candidate (b), the parse [(L ˈL) L], is selected 50% of the time. Thus, although in production the grammar generates [(L ˈL) L] nine times less often than it generates [L (ˈL L)], in parsing RIP generates both structures equally often. In this example, RIP fails to reflect the soft preferences inherent in the learner's current grammar, in the same way that it failed to reflect the categorical restrictions imposed by the grammar in the example above.

RIP therefore fails to reflect the probability distribution which the grammar assigns to the data. This occurs because, by restricting the set of candidates, RIP changes the constraint interactions that are relevant for selecting candidates. The set of candidates consistent with an overt form is generally a small subset of the full space of candidates. This smaller space changes the relative probabilities of the parses, because fewer constraint interactions are relevant for selecting optima among this reduced set of candidates. In the example above, the presence or absence of candidates (a) and (d) alters the constraint interactions. In production, the relative ranking of lower-ranked foot-form constraints is crucial, but in parsing, the absence of (a) and (d) means foot-form constraints are irrelevant. Ranking conditions crucially rely on the set of alternatives, and when RIP alters this set, it alters the likelihood of the various parses relative to one another. Clearly, any parsing procedure must alter the absolute probabilities of candidate parses if the production grammar assigns any probability to forms with other stress contours. The problem, however, concerns the relative probability assigned to competing parses when mismatching candidates are added or removed from the competition. In the second example above, candidates (b) and (c) are generated with 5% and 45% probability respectively in production, a relative proportion of 1 to 9, but RIP generates both parses with equal probabilities of 50%, a proportion of 1 to 1. In this way, reducing the candidate set can dramatically alter the relative probabilities of candidate parses from their relative probabilities in production.

It is this mismatch in the relative probabilities which is the problem, and occurs in RIP versions of both Stochastic OT and Noisy HG, because in both frameworks the relative probability of two candidates depends on what else is in the candidate set. Interestingly, the mismatch appears to be less severe for probabilistic weighting than for probabilistic ranking, at least for the kinds of constraint interactions and hidden structures typically found in stress systems. Consider again the example in (9), this time in a weighted grammar. Suppose that in the learner's current Noisy HG weighting AllFeet-L and AllFeet-R have weights of 300, Trochaic 200 and Iambic 100, as shown in (10).

1. (10)

   

In contrast to the analogous example in OT, the Noisy HG example does not exhibit a severe mismatch. Just as in OT, this grammar generates candidates (a) and (c) with equal probability, roughly 50%, in production. The weightings of the foot-form constraints limit candidates to those parsed with trochees, while noise allows AllFeet-L and AllFeet-R to vary in relative weighting, producing variation between left-aligned and right-aligned trochees. Unlike in OT, however, RIP selects candidate (c) with near certainty as the parse for [L ˈL L]. This is because what matters in HG is the overall difference in the weighted sum of violations between the two candidates. The foot-form constraints, weighted 100 points apart, are decisive in parsing, just as they are in production. Although the alignment constraints have high weights, their relative weighting is of little consequence, because it is the difference in overall harmony that determines the winner. Noise cannot overwhelm the 100-point harmony difference between candidates (b) and (c). Therefore, in this example RIP succeeds in making use of categorical grammatical knowledge favouring trochees.

Probabilistic weighting is not totally immune to the parsing–production mismatch problem, however. Mismatches do occur, especially when decisive constraints are variably weighted or when variably weighted constraints have multiple violations. For example, in a case identical to (10) except with the weight of Iambic set to 198, so that foot-form constraints can vary in weight, there is a statistical mismatch.Footnote ⁸ Under this weighting, candidates (a), (b), (c) and (d) have approximately 42%, 8%, 42% and 8% probability respectively. Therefore, in production, candidate (c) is more than five times as likely as candidate (b). RIP, however, selects candidate (c) about 76% of the time, about three times as often as candidate (b). This example is qualitatively similar to the second OT example above: a strong statistical preference for trochees in production is not fully respected in parsing. Quantitatively, the mismatch is not as severe as in OT, however, since RIP merely weakens the statistical preference without eliminating it entirely. In general, strict ranking creates more opportunities for the parsing–production mismatch, because crucial relative rankings can be made completely irrelevant when the candidate set is reduced (as in (9)). On the other hand, in HG all differences in weighting, even for constraints with low weights, are always relevant for both the full and reduced set of candidates. Nevertheless, statistical mismatches occur in both frameworks, because the presence or absence of alternative candidates affects the relative probabilities with which parses are selected as optimal.

The above discussion has implications for the learning of structural ambiguity in a variant of stochastic weighted grammars known as maximum entropy grammars (Johnson Reference Johnson, Merlo and Stevenson2002, Goldwater & Johnson Reference Goldwater, Johnson, Spenador, Eriksson and Dahl2003, Jäger Reference Jäger, Zaenen, Simpson, King, Grimshaw, Maling and Manning2007). As discussed above, the relative probability of two candidates in Stochastic OT and Noisy HG depends on what other candidates are considered. This is not so in maximum entropy grammars, in which the probability of a candidate is calculated directly from the harmony: specifically, it is proportional to the exponential of the candidate's harmony. Since the harmony does not depend on other candidates, the relative probabilities of two candidates are fixed, regardless of what other candidates are considered. This means that, by the very definition of candidate probability in these models, maximum entropy grammars are not subject to the parsing–production mismatch problem. RRIP for maximum entropy grammars will therefore select parses according to their production probabilities. The consequences of this observation for learning in the face of structural ambiguity are not explicitly explored here, but future work must also consider RRIP versions of maximum entropy grammars.

RIP is attractive because it provides a simple way to use the learner's current grammar for both production and parsing. However, as this section has shown, using the same procedure for parsing and production actually results in incompatible parsing and production distributions for both OT and HG, and a failure to fully exploit existing grammatical knowledge during interpretive parsing. The following sections explore the consequences of this mismatch in more depth by introducing and testing learning models without a parsing–production mismatch.

4.2 Expected Interpretive Parsing

How could the learner better exploit its current stochastic grammatical knowledge during parsing? A general solution to this question comes from the statistical learning literature. The well-known Expectation-Maximisation (EM) algorithm (Dempster et al. Reference Dempster, Laird and Rubin1977) is a general procedure for learning in the face of hidden structure and has been applied to learning with a variety of language models. Formally, EM characterises learning as maximisation of likelihood, which is a measure of fitness, quantifying the grammar's ability to generate the language data. A major advantage of EM is that, with each iteration of learning (where an iteration is a pass through the learning data), the learner is guaranteed to improve its ability to generate the learning data (or to converge). Thus EM provides a general approach to hidden structure that indicates how to learn from ambiguous data so as to improve the overall fitness of the grammar based on the most complete information available in the current stochastic grammar. Informally, EM uses its current grammar to parse the learning data, assigning parses in proportion to their probability under the grammar. It then updates the grammar based on these ‘expected’ parses, rewarding grammars that are capable of generating the data with high likelihood. The essential insight of EM is that parses should be weighted by the learner in proportion to the probability with which the current grammar generates them.

In fact, EM was Tesar & Smolensky's original inspiration for RIP, which they reinterpreted for a non-probabilistic classical OT setting. The stochastic grammar setting provides the opportunity to make this connection tighter, since probability is an essential component of EM's solution to hidden structure. However, as shown in the previous section, the original formulation of RIP for the stochastic setting does not fully exploit the connection with EM, since in RIP/OT-GLA and RIP/HG-GLA parses are not selected according to their probability under the grammar. Other work within the probabilistic constraint ranking setting does explore this connection: Jarosz (Reference Jarosz2006a, Reference Jarosz, Wicentowski and Kondarkb) adapts EM to the problem of learning probabilistic OT grammars, and illustrates the capacity of these models to deal with hidden structure in the general case, learning both structural ambiguity and underlying representations in several computational case studies. However, the full EM calculations are computationally costly, involving explicit enumeration and calculation of the expected probabilities of possible parses (or their components) for all the learning data in batch. The present work investigates an alternative solution that harnesses the basic insight underlying Jarosz's model and EM's solution to hidden structure but relies on the sampling strategy inherent to the online error-driven learners, OT-GLA and HG-GLA.

EM's basic insight can be applied to OT-GLA and HG-GLA simply by selecting parses in proportion to their probability under the learner's current grammar. The formulation in (11) defines this new parsing algorithm for GLA, Expected Interpretive Parsing (EIP).

1. (11)

   

This formulation is identical to the one for RRIP in (8), except that resampling and Robust Interpretive Parsing steps are replaced with sampling from the conditional probability of the parse given the current grammar and the learning datum: P(parse|G_i, d) (step 2d.i). Thus EIP defines the probability according to which parses should be sampled as the probability of those parses under the current grammar, the relative production probabilities discussed in the previous section. Consider again the example in (9), and a grammar, G_A, with FootNon-fin≫Iambic. For this grammar and the overt datum [L ˈL L], the probability of the trochaic parse, P([L (ˈL L)]|G_A, [L ˈL L]), is 100%, while the probability of the iambic parse, P([(L ˈL) L]|G_A, [L ˈL L]) is 0%. For the second grammar discussed earlier, with FootNon-fin≫Iambic only 90% of the time, these parsing probabilities would be 90% and 10% respectively.

In EIP, interpretive parsing is defined as sampling from these distributions. Whereas in true EM parses (or their components) are enumerated, and the grammar update is weighted by this probability, in EIP this weighting is accomplished indirectly by repeated sampling from this distribution. More probable parses are sampled more often, causing their respective updates to the grammar to be made more often. In sum, EIP addresses the parsing–production mismatch problem discussed in the last section by defining the parsing procedure in terms of the current production grammar. In this way, EIP resurrects the connection with EM that originally inspired RIP, applying EM's approach to hidden structure to two online sampling learning algorithms for stochastic constraint-based grammars.

4.3 Expected Interpretive Parsing simulations and results

The previous sections showed that (R)RIP does not parse according to the current (production) grammar, and introduced an algorithm, Expected Interpretive Parsing, that does parse according to the current grammar. This section presents simulations illustrating how parsing consistently with the learner's production affects performance.

As discussed earlier, an advantage of RIP is that parsing can be accomplished by using standard optimisation, albeit with a different candidate set. Sampling parses from the conditional probability P(parse|G_i, d) requires another computational approach. The simulations presented here use a Monte Carlo method of rejection sampling which relies on the learner's production module. Specifically, in case of an error on datum d, the learner's current grammar is used to generate output forms for the underlying form of d. As soon as one of the output forms matches the overt stress pattern of d, it is used as the parse. Outputs that do not match the surface stress pattern of d are discarded. By using only those samples that match the overt stress pattern, this method effectively samples from the conditional probability of various parses of d, given its overt stress pattern and the current grammar, exactly the probability distribution required for EIP.

Consider once again the example in (9) and the grammar with FootNon-fin≫Iambic. If the learner needs to generate a parse for [L ˈL L], the learner will simply use the current grammar to generate outputs for /L L L/ until one matches [L ˈL L], in which case that output will be used as the parse. Recall that this grammar generates each of [(ˈL L) L] and [L (ˈL L)] about 50% of the time. Since only [L (ˈL L)] matches the stress pattern of the datum and only outputs matching the overt stress pattern are used as parses, the sampler generates outputs until it generates [L (ˈL L)], and then uses this output as its parse. In this example, the chance of parsing [L ˈL L] as [L (ˈL L)] is therefore 100%, as required by EIP. In the example grammar with FootNon-fin≫Iambic only 90% of the time, the grammar again has a 50% probability of generating [L ˈL L], but this grammar generates [L ˈL L] with two different parses. It generates [L (ˈL L)] with 45% probability and [(L ˈL) L] with 5% probability. Since the sampler only keeps those outputs that match the stress pattern, its chance of parsing [L ˈL L] as [L (ˈL L)] is 45/50, or 90%, and its chance of parsing [L ˈL L] as [(L ˈL) L] is 5/50, or 10%. In both examples, since the probability of selecting the overt stress pattern is 50%, the sampler has a 50% chance each time it generates an output of keeping it as the parse.

In general, the number of outputs that need to be generated until a match is found depends directly on the probability of the overt form under the grammar. In general, the more likely the overt form is according to the current grammar, the more quickly a parse for it will be found. This parsing method thus has the advantage that parsing becomes more efficient as learning continues, and the learner's grammar becomes more and more likely to generate the surface stress pattern of the target language. However, if the learner's grammar generates the overt form with very low probability, it can take many samples before a match is found, meaning that selecting a parse can require more effort when the learner's current grammar is very far from the target grammar.

One further detail is crucial in implementing this sampling method for EIP. When the learner converges on a grammar that is incorrect for the target language, i.e. when learning is unsuccessful, the learned grammar often fails to generate one or two of the data forms in the language entirely, assigning (near) zero probability to them. Without some terminating condition, the sampler will loop indefinitely in these cases, since it cannot generate a matching stress pattern for such data forms. In the simulations reported here, this problem was avoided by allowing each form a maximum of 1000 samples from the grammar to generate a parse. If 1000 samples failed to provide a parse of the datum, the learner did not make an update to its grammar and did not learn from this error.Footnote ⁹ The remaining simulation details are identical to the earlier set-up for RIP and RRIP. All learning rate/algorithm combinations were repeated ten times for each of the 124 languages (constituting a total of 9920 separate runs of EIP), as before, with average success rates and sample standard deviations calculated.

The performance results of EIP for OT-GLA and HG-GLA at the four learning rates are shown in Table III. The results for RIP and RRIP are repeated from Table II for convenience.

Table III

Success rate (in %) of RIP, RRIP and EIP across various parameter settings. Sample standard deviation is given in parentheses. Best scores for each model are shown in bold.

Comparing EIP/OT-GLA to the other OT-GLA variants reveals that Expected Interpretive Parsing dramatically improves performance over RIP and RRIP. Whereas RRIP's performance of roughly 81–84% is dramatically higher than RIP's performance of roughly 56–58%, EIP's performance of about 93–94% is substantially higher than both RIP and RRIP. On average, EIP improves upon the performance of RRIP by about 10 percentage points, and this difference is highly significant at all learning rates (p<0·001; Welch two-sample t-test). For the HG learners, examination of EIP/HG-GLA's performance at the parameter settings tested indicates that EIP/HG-GLA performs comparably to RRIP/HG-GLA and RIP/HG-GLA. Comparing performance of EIP/OT-GLA and EIP/HG-GLA suggests that HG-GLA no longer has an edge over OT-GLA. Indeed, for the parameters tested here, EIP/OT-GLA's performance is better than EIP/HG-GLA's performance by several points. However, the following sections explore HG-GLA's performance with different parsing strategies at a wider range of parameter settings, and shows that the above results do not represent HG-GLA's best performance.

4.4 Parameter settings and probabilistic ranking vs. weighting

One puzzling aspect of the above results is the apparent lack of effect of parsing strategy on the HG-GLA. The best performance of HG-GLA reported above is about 88–89%, regardless of the strategy adopted. One aspect of this puzzle is why EIP/HG-GLA fails to improve over RRIP/HG-GLA. A possible answer to this question was alluded to in the earlier discussion of the parsing–production mismatch. The mismatches discussed earlier were much more severe for OT than for HG. If these examples are representative of the kinds of constraint interactions that typically occur in stress systems such as this one, mismatches may be dramatically less pervasive in HG than in OT on typical learning trials. Weak mismatches would cause RRIP to perform similarly to EIP, since the only difference between these two algorithms is the distribution according to which parses are sampled. Since RIP and EIP perform comparably, the results are largely consistent with this possibility. However, if the parsing–production mismatch in HG is weak, rather than non-existent, some improvement would be expected from EIP. Furthermore, the parsing–production mismatch does not explain why RIP/HG-GLA and RRIP/HG-GLA perform comparably. Why does parsing strategy seem to have no effect whatsoever on HG-GLA? This section considers this question more carefully and reveals that part of the explanation lies in differences in how the parameter settings affect learning in HG-GLA as opposed to OT-GLA.

The simulations presented here include a range of parameter settings for all the algorithms. These provide a reasonable starting point for exploring how parameter settings affect performance in the various algorithms. Although the results presented here consider the same range of parameter settings for Stochastic OT and Noisy HG algorithms, this range provides a more complete picture of the performance range for Stochastic OT than it does for Noisy HG. There are three parameters to set: initial weights or ranking values, learning rate and noise. If all the constraints are initially tied, as they are in these simulations, the initial ranking values for the OT learners are irrelevant, since all that matters is whether one constraint is ranked higher or lower than another – its numerical value is not important. In other words, if noise is held constant, it does not matter whether the ranking values of two constraints are 1 and 10 or 1001 and 1010. Therefore, for Stochastic OT, if constraints start out tied, there are only two meaningful parameters: noise and learning rate. It is possible to hold one parameter constant and vary the other to get a good idea of the performance range. This is exactly what the current results reflect. The same range of performance would be expected for higher/lower noise values, with best performance shifted to higher/lower learning rate values. Since the best performance for EIP/OT-GLA occurs at one of the intermediate parameter values tested, it is likely that this combination of parameter settings is close to the best possible performance EIP/OT-GLA can achieve on this test set. The best performance of RIP/OT-GLA shown in the results above occurs at the highest learning rate tested. To determine whether performance of RIP/OT-GLA improves at even higher plasticity values, two additional parameter settings were tested, with ten runs each: plasticity of 1·0 and plasticity of 2·0. The results indicate that higher learning rates cannot save RIP/OT-GLA – performance at these higher learning rates is on average 57·18% and 56·35% respectively. It is possible that some plasticity value intermediate between the range of 0·25 and 2·0 would slightly improve performance, but the results indicate that 57% is a good estimate of the best performance for RIP/OT-GLA on this test set. Finally, performance of RRIP/OT-GLA is highest at the lowest learning rate, so it is worth checking whether even lower learning rates would improve performance. In fact, they do not – performance at a learning rate of 0·01 drops to 83·17%. Overall, the results for RIP, RRIP and EIP versions of the OT-GLA presented here provide good estimates of the best performance that can be expected from these algorithms on this test set. This means we can be reasonably confident that the performance gains of EIP/OT-GLA over RRIP/OT-GLA and RRIP/OT-GLA over RIP/OT-GLA are robust, and representative of the range of possible parameter settings.

In contrast, the performance range for the variants of the HG-GLA algorithms presented here is not likely to be similarly comprehensive. This is because the current results represent a smaller portion of the space of crucial parameter combinations for HG-GLA, simply because more parameter settings are crucial for the HG-GLA. Indeed, all three parameter settings – initial weights, noise and plasticity – have consequences for the HG-GLA, and their possible combinations create a large space of possibilities. A weighting difference of 10 and 1 is not equivalent to a weighting difference of 1010 and 1001. This is because harmony in HG depends on a multiplicative interaction between constraint weights and their violations, which means that the relative harmony of two candidates may depend on the ratio of their weights. Consider the simple example in (12).

1. (12)

   

Each violation of C₂ incurred by Candidate A is added to the candidate's total score. This means in order for Candidate A to win, the weight of C₁ must be more than three times that of the weight of C₂. Therefore, if the weights of C₁ and C₂ are 10 and 1 respectively, Candidate A is optimal. However, if the weights of C₁ and C₂ are 1010 and 1001 respectively, Candidate B is optimal. Thus, because optimality is determined in terms of multiplicative weighting interactions in HG, the absolute weight assigned to a constraints initially during learning matters. If the learner starts out with C₁ and C₂ with weights of 1, the weights will only have to shift by a total of about 2 for Candidate A to be selected as optimal. In contrast, if the learner begins with both constraints weighted at 100, it will take many more iterations (or a much higher learning rate) to reach a weighting with C₁ weighted three times higher than C₂. The metrical stress system investigated here involves forms with multiple feet, stresses and syllables, and therefore candidates with multiple violations for constraints are very common, often yielding multiplicative weighting interactions.

A further consequence of this multiplicative interaction is that Noisy HG is less sensitive to evaluation noise, and the interaction between noise and weighting is more complex. Consider again the example above, and suppose that both C₁ and C₂ are weighted or ranked equally at 10. In Stochastic OT, regardless of the noise setting, Candidates A and B are equally likely to be generated. Not so in Noisy HG. In Noisy HG with a standard noise setting of 2, the chances that the weight of C₁ will randomly be selected to be three times higher than C₂ are very low. This means Noisy HG will almost always generate candidate B. Note that this interacts in a non-trivial way with the weighting value: if the constraints are both tied at 100 rather than 10, with noise still set to 2, the probability of generating Candidate A becomes vanishingly small.

Since the test system investigated here does involve a number of gradient constraints that frequently assign multiple violations, the effect of a given level of noise should be weaker for Noisy HG than for Stochastic OT. If this is true, it is possible that the lack of an effect of the parsing mechanism for HG-GLA could be due to a lack of sufficient noise. If, despite the noise, Noisy HG grammars are consistently selecting the same candidates as the winners, there would be no effect of resampling and no effect of parsing strategy. In other words, if Noisy HG is so insensitive to noise as to assign nearly all probability to a single candidate, the parsing strategy should be largely inconsequential.

This possibility was investigated in two ways. First, the expected interpretive parsing outcomes of Stochastic OT and Noisy HG were qualitatively examined at the initial weighting/ranking of 10 and noise of 2, with learning updates turned off. This was done in order to determine whether the choice of OT vs. HG affected the variability in parses. A grammar with all constraints tied generates a wide range of rankings and weightings, and provides an opportunity to observe the variability in parsing outcomes that operates in all target languages before any learning has taken place. In Stochastic OT, there is indeed a great deal of variation between the parses selected for the overt forms. In contrast, parses selected by Noisy HG are much more consistent, with most overt forms being consistently parsed in only one way. Thus it is clear that the same level of noise results in much more parsing variation in Stochastic OT than in Noisy HG. This raises the question of how the performance of HG-GLA would be affected if noise were increased. To investigate this, additional runs of each of the HG-GLA variants were performed at noise settings of 4 and 8. All runs used a learning rate of 0·10, and were set up as before, with initial weights of 10. As before, each run was repeated ten times, with the average and sample standard deviation calculated.

The results are summarised in Table IV, with the previous results of HG-GLA with noise set to 2 repeated for convenience.

Table IV

Success rate (in %) of RIP and RRIP across various parameter settings. Sample standard deviation is given in parentheses. Best scores are shown in bold.

These results are consistent with the hypothesis discussed earlier, namely, that it is insensitivity to noise that causes the HG-GLA algorithms to show no effect of parsing strategy. When noise is increased to 4, EIP does yield an improvement in performance over RRIP, and RRIP does yield an improvement over RIP. These gains in performance are relatively small, but they are both highly significant (p<0·01; Welch two-sample t-test). This means that better parsing can yield better performance for both HG-GLA and OT-GLA. Furthermore, the results also indicate that, for a learning rate of 0·10 and initial weights of 10, overall performance is best at noise set to around 4, with lower performance when noise is increased to 8. These results increase the upper range of the performance for the HG-GLA algorithms presented in the previous section (and in previous work). Importantly, the performance of EIP/HG-GLA at noise set to 4 is comparable to the best performance of EIP/OT-GLA (p>0·1; Welch two-sample t-test).

In sum, the discussion and simulations in this section have shown that HG-GLA is highly sensitive to the combinations of parameter settings. While varying one parameter in the OT-GLA provides a fairly comprehensive view of its range of performance, the space of crucial parameter settings is more complex for the HG-GLA, and requires more extensive exploration. Additional exploration of this space revealed that the amount of variability produced at a noise setting of 2 in this stress system is quite limited. This explains why the choice of parsing strategy has little effect at this noise setting. At higher settings, differences between the parsing strategies emerge, and indicate that EIP does improve performance over RRIP, which in turn is better than RIP. The gains in the performance are small compared to the gains for OT-GLA, but they nonetheless indicate that parsing strategy does matter for HG-GLA when the noise level is high enough to produce some variability in parses. Parsing with a known loser (RIP) leads to poorer performance than resampling (RRIP). Likewise, the parsing–production mismatch problem does exist for Noisy HG, albeit weakly, and leads to poorer performance of RRIP in comparison with EIP. As discussed above, the interactions of parameter settings for HG-GLA are complex, and further work is needed to provide a comprehensive picture of how the performance of HG-GLA in the domain of hidden structure depends on the various parameter settings, the types of constraints (gradient or binary) and their interactions.