2.1 Basic description

The basic data unit in OT is a data triplet (4a), consisting of an underlying form /x/ and two surface forms [y] and [z], both drawn from the set Gen(/x/) of candidates for /x/. By convention, the first candidate [y] in the triplet is the intended winner, while the other candidate [z] is an intended loser. As a useful mnemonic, I adopt the convention of striking out the loser. To illustrate, the data triplet (4b) pairs up the underlying form /rad/ with the two candidates [rad] and [rat]. As the former is the intended winner, this triplet says that there is no final devoicing.

1. (4)

   

An OT-grammar is parameterised by a ranking, which is a linear order ‘≫’ over the constraint set. Constraint C_h is ≫-ranked above constraint C_k, provided C_h≫C_k. A ranking is (OT-)consistent with an underlying/winner/loser form data triplet (/x/, [y], [z]) provided condition (5) holds. (5) says that the intended loser [z] violates the constraints ‘more severely’ than the intended winner [y], in the sense that, among those constraints that distinguish between the winner [y] and the loser [z], the top ≫-ranked one, C_top, assigns more violations to the loser than to the winner.

1. (5)

   

A ranking is (OT-)consistent with a set of data triplets provided it is consistent with every triplet in the set, and a set of data triplets is (OT-)consistent provided it is consistent with at least one ranking.

With these preliminaries in place, an EDRA can be described as follows, after Tesar & Smolensky (Reference Tesar and Smolensky1998). The algorithm maintains a current ranking, which represents its current hypothesis on the target grammar. This current ranking is initialised to an initial ranking, and is updated over time by looping through the three steps (a)–(c) in Fig. 3. At step (a), the algorithm assembles an underlying/winner/loser form triplet. At step (b), the algorithm checks the current ranking against the current underlying/winner/loser form data triplet. If the current ranking is consistent with the current data triplet according to (5), nothing happens: the algorithm goes back to step (a) and waits for another piece of data. Otherwise, the algorithm modifies its current ranking at step (c), and then goes back to step (a).

Figure 3

Main loop of an EDRA.

2.2 Restatement in comparative notation

Given an underlying/winner/loser form data triplet (/x/, [y], [z]), the constraints can be sorted into winner-preferring, loser-preferring or even, as in (6), depending on whether they assign more, fewer or the same number of violations to the loser [z] than to the winner [y].

1. (6)

   

To illustrate, consider again the data triplet (/rad/, [rad], [rat]) in (4b). The positional faithfulness constraint F_pos=Ident[voice]/Onset for voicing is even, as it does not distinguish between the two candidates [rad] and [rat]. The general faithfulness constraint F_gen=Ident[voice] is winner-preferring, as the intended winner [rad] is fully faithful to the underlying form /rad/, as opposed to the intended loser [rat]. Finally, the markedness constraint M=*[+voice] is loser-preferring, as it is violated by the intended winner [rad], and not by the intended loser [rat].

The definition (5) of OT-consistency does not really care about the actual number of constraint violations. It only cares about whether each constraint is winner-preferring, loser-preferring or even. The relevant information concerning this data triplet can thus be represented as in (7), specifying with w, l or e whether each constraint is winner-preferring, loser-preferring or even.

1. (7)

   

In the general case, the information provided by a data triplet that is useful for the sake of OT-consistency can be distilled as in (8), following Prince (Reference Prince2002). The data triplet is paired up with a tuple with n entries (one for every constraint), with the convention that the kth entry is equal to w, l or e, depending on whether the kth constraint C_k is winner-preferring, loser-preferring or even. One such w/l/e n-tuple is an elementary ranking condition (henceforth ERC). I denote an ERC by a and its entries by a ₁, …, a _n.

1. (8)

   

A set of many, say m, data triplets, can be paired up with the corresponding ERC matrix, by organising the ERCs corresponding to each triplet one underneath the other (the order does not matter), into a matrix with n columns (one for every constraint), m rows (one for every data triplet) and entries equal to w, l and e. A denotes an arbitrary OT-comparative matrix; for readability, I often omit e.

With this notation in place, condition (5) for OT-consistency between a ranking and a data triplet can be restated as condition (9) between that ranking and the corresponding ERC. In general, a ranking is (OT-)consistent with an arbitrary ERC provided condition (9) holds, and is (OT-)consistent with an ERC matrix provided it is consistent with every ERC in the matrix. Finally, an ERC matrix is (OT-)consistent provided it is consistent with at least one ranking.

1. (9) Once the n entries of the ERC a are reordered from left to right in decreasing order according to ≫, then the leftmost non-e entry is a w.

To illustrate the notion of OT-consistency in (9), note that the ERC in (7) is consistent with the ranking F_pos≫F_gen≫M, as its columns are ordered from left to right in ≫-decreasing order and the leftmost non-e symbol is w.

In many cases, we are interested in studying the behaviour of EDRAs irrespective of the proper definition of step (a) in Fig. 3, i.e. irrespective of the proper definition of the sub-routines that determine the underlying form and choose a loser form for the winner form the algorithm has been currently fed. In these cases, we can thus assume that the underlying and the loser forms are also provided to the algorithm, along with the winner form. In other words, we can assume that the algorithm is given as input at step (a) an underlying/winner/loser form data triplet, or, equivalently, the corresponding ERC. It is thus useful to restate EDRAs in terms of ERCs, as in Fig. 4. According to Fig. 4, the algorithm is trained on a stream of ERCs, and the current ranking is updated whenever it is inconsistent with the current ERC.

Figure 4

Main loop of an EDRA, restated in ERC notation.

Throughout this paper, I assume that the ERCs fed to the algorithm at step (a) are sampled from a fixed, given input ERC matrix, which I will assume to be consistent. As we will see in §4.3, this assumption can be made without loss of generality in certain applications, as in the case of modelling the acquisition of phonotactics.

2.3 Restatement in terms of ranking vectors

Boersma (Reference Boersma1997, Reference Boersma1998, Reference Boersma2009) points out that rankings can be represented numerically. To illustrate the idea, suppose we have three constraints discussed in §2.2, and let us pair them up with three numbers, as in (10). This triplet of numbers can be interpreted as follows: F_pos is top-ranked, because it corresponds to the largest number, M is bottom-ranked and F_gen is ranked in between.

1. (10)

   

In order for the correspondence in (10) to hold, it is crucial that the three numbers considered are all distinct. What if two of these numbers are identical? Consider for instance the case in (11), where the two constraints F_gen and M are assigned the same number. We can think of this triplet of numbers as simultaneously representing two different rankings, depending on how the tie between F_gen and M is resolved. We can think of these two rankings as two different ways of ‘refining’ the numerical tie.

1. (11)

   

These considerations allow OT grammars to be given a numerical parameterisation, besides the usual combinatorial parameterisation in terms of rankings. Here are the details.

A ranking vector is an n-tuple θ of numbers θ₁, …, θ_n as in (12), one for each of the n constraints. The kth component θ_k is the ranking value (RV) of constraint C_k.

1. (12)

   

A ranking is a refinement of a ranking vector θ=(θ₁, …, θ_n) provided condition (13) holds for any pair of constraints C_h, C_k. If the two RVs θ_h and θ_k tie, the antecedent of (13) fails, and different refinements can break the tie in either way. Otherwise, any refinement satisfies the ordering implicitly defined by the relative size of the two RVs θ_h and θ_k.

1. (13)

   

Once ranking vectors are paired up with rankings through (13), notions that pertain to rankings can be extended to ranking vectors. In particular, we can extend the notion of OT-consistency from rankings to ranking vectors. If a ranking vector admits a unique refinement, then the extension is straightforward: we will say that the ranking vector is consistent with an ERC provided its unique refinement is consistent with that ERC, according to the original notion of OT-consistency in (9). What if instead some of the RVs tie and the ranking vector thus admits multiple refinements? One option would be to declare the ranking vector consistent with an ERC provided at least one of its refinements is consistent with it, in the spirit of Anttila (Reference Anttila1997) and Anttila & Cho (Reference Anttila and Cho1998). At convergence, the algorithm will thus return a ranking vector that has the property that at least one of its refinements is consistent with the input ERC matrix. But this is not very useful: how do we decide for a given refinement whether it is what we want or not? Thus I will require consistency of every refinement in order to declare a ranking vector consistent with an ERC, as in (14).Footnote ³

1. (14) A ranking vector is (OT-)consistent with an ERC provided that each of its refinements is consistent with that ERC, according to the original notion of consistency (9).

For instance, the ranking vector in (10) is consistent with the ERC in (7), as the only refinement of the former is consistent with the latter. But the ranking vector in (11) is not consistent with (7), because of the inconsistent refinement F_pos≫M≫F_gen.

Boersma (Reference Boersma1997, Reference Boersma1998, Reference Boersma2009) suggests restating the EDRA in Fig. 4 in terms of ranking vectors, as in Fig. 5, the final formulation considered in this paper. The current hypothesis on the target grammar is stored by the algorithm as a numerical ranking vector, rather than as a combinatorial ranking. The current ranking vector is updated whenever it is found to be inconsistent with the current ERC.

Figure 5

Main loop of an EDRA, restated in terms of ranking vectors.

This restatement of EDRAs in terms of ranking vectors rather than rankings will prove to be crucial for the development of the theory of EDRAs' convergence.

2.4 Convergent re-ranking rules

Different EDRAs differ (mainly) because of the re-ranking rule used in step (c) of Fig. 5 in order to update the current ranking vector in response to its failure on the current ERC. This re-ranking operation can take various different forms. One option is to demote by a certain demotion amount certain loser-preferring constraints, as those are the constraints responsible for the failure of the current ranking vector on the current ERC. Another option is to promote by a certain promotion amount certain winner-preferring constraints, as those are the constraints that would have helped to avoid the failure of the current ranking vector on the current ERC. These two options are schematised in (15), which thus provides a general scheme for re-ranking rules.

1. (15)

   1. a. Subtract a certain demotion amount from the current RV of some or all of the loser-preferring constraints.

   2. b. Add a certain promotion amount to the current RV of some or all of the winner-preferring constraints.

Re-ranking rules differ along three main dimensions. The first dimension is whether the re-ranking rule only performs constraint demotion or constraint promotion as well. The second dimension is whether the re-ranking rule minimally demotes only the loser-preferrers that need to be demoted or maximally demotes all of them. The third dimension is whether the re-ranking rule performs small, gradual updates or instead updates that are so ‘drastic’ that one update suffices to make the current ranking vector consistent with the current ERC, so that no ERC can trigger two consecutive updates. The re-ranking rules considered in the literature are classified in Fig. 6 according to these three dimensions, together with the name of the corresponding EDRA. §3 reviews what is currently known about re-ranking rules that perform constraint demotion only; §5 reviews what is currently known about re-ranking rules that perform both constraint demotion and promotion.

Figure 6

Taxonomy of the re-ranking rules considered in the literature.

An EDRA (with a specific re-ranking rule and a specific initial ranking vector) is said to converge on a given input ERC matrix provided that the algorithm can perform only a finite number of updates when trained on any stream of ERCs sampled from that ERC matrix. In other words, the algorithm always eventually settles on a ranking vector consistent with each input ERC, so that the algorithm cannot make any more errors, and learning ceases. An EDRA is (universally) convergent provided that it converges no matter what input ERC matrix it is trained on, as long as it is consistent. The restriction to consistent input ERCs makes good sense, as the EDRA could never converge on a consistent ranking otherwise. Furthermore, the restriction to consistent input ERCs can be enforced in some cases without loss of generality, as we will see in §4.3. A convergent EDRA is efficient provided that the number of errors made before convergence grows slowly (polynomially) with the number n of constraints, so that the algorithm also works in the case of very large constraint sets. For each of the main EDRAs considered in the literature, the synopsis in Fig. 6 indicates what is currently known concerning (universal) convergence and efficiency. In particular, it reveals that the ambitious requirement of efficient convergence can be achieved. The next section takes a close look at this result.

3.1 A minimal, gradual demotion-only re-ranking rule

Consider the current ERC (16a) and the current ranking vector (16b). The two constraints C₄ and C₆ are both currently loser-preferrers. Yet there is a crucial difference between them. The current RV of C₆ is 5, which is smaller than the current RV of the winner-preferrer C₁. However, the current RV of C₄ is 15, larger than the current RV of both winner-preferrers C₁ and C₂. This difference is important enough to warrant a name: a loser-preferrer is undominated if there is no winner-preferrer with a strictly larger current RV. Thus C₄ is currently undominated, while C₆ is not.

1. (16)

   

We can now consider the re-ranking rule (17), which demotes all undominated loser-preferrers by a small fixed amount, here set to 1 for concreteness.

1. (17)

   1. a. Decrease the RV of each undominated loser-preferrer by 1.

   2. b. Do nothing to the current RV of the other constraints.

For instance, if the current ERC is (16a) and the current ranking vector is (16b), then the updated ranking vector is (18): the RV of the currently undominated loser-preferrer C₄ is decreased by 1, from 15 to 14; all other RVs are left unchanged.

1. (18)

   

The re-ranking rule (17) is clearly demotion-only, as the current RVs of winner-preferrers are never modified. Furthermore, it is minimal, because it does not demote all loser-preferrers, but only those that really need to be demoted because they are not already ranked underneath a winner-preferrer, i.e. only the undominated ones. We will see in §3.6 why it is indeed a good idea to only demote the currently undominated loser-preferrers. Finally, (17) is gradual, in the sense that updates are performed by a small fixed amount, so that an ERC might have to trigger multiple consecutive updates before the current ranking vector becomes consistent with it. For instance, a single update of the current ranking vector (16b) by the ERC (16a) is not enough to enforce consistency with that ERC, as the updated ranking vector (18) is still not OT-consistent with it. As we will see in §3.7, it is easy to construct the non-gradual counterpart of a gradual re-ranking rule. The EDRA in Fig. 5, together with the re-ranking rule in (17), is Boersma's (Reference Boersma1997) (non-stochastic) minimal demotion-only Gradual Learning Algorithm.

3.2 The idea of the analysis

Suppose that the input ERC matrix is (19a) and the initial ranking values are all null. I provide in (19b) the complete learning paths described by the EDRA with the re-ranking rule (17). Suppose the algorithm receives ERC 1 at the first iteration. Since the initial ranking vector θ¹ is not consistent with that ERC, the algorithm updates θ¹ to θ² by demoting the RV of the currently undominated loser-preferrer C₂ by 1. As θ² is now consistent with ERC 1, no further updates will be performed, until the algorithm is fed ERC 2. When that happens, θ² is updated to θ³ by demoting by 1 the RV of the currently undominated loser-preferrer C₃. And so on.

1. (19)

   

No matter the training sequence of ERCs, after three updates the algorithm entertains the ranking vector θ⁴, whose only refinement is the ranking C₁≫C₂≫C₃. Since this ranking is consistent with both input ERCs, no further update will be triggered.

The input ERC matrix in (19a) is consistent only with the ranking in (20a), where stratum 1 is the top stratum.

1. (20)

   

The RV of C₁ never goes below 0 in (19b), as stated in (20b). In fact, constraint C₁ is never loser-preferring in the input ERC matrix, and is thus never demoted from its initial null RV. Furthermore, the RV of C₂ never goes below −1. Indeed, C₂ can only be demoted through update by ERC 1; in order for that ERC to trigger an update, C₂ must be currently ranked above the winner-preferrer C₁; since C₁ is fixed at the RV θ₁=0, this means that C₂ can only be demoted when its current RV is θ₂=0; therefore C₂ can never be below θ₂=−1. Finally, the RV of C₃ never goes below −2. C₃ can only be demoted through update by ERC 2; in order for that ERC to trigger an update, C₃ must be currently ranked above the winner-preferrer C₂; since C₂ can only drop down to θ₂=−1, this means that C₃ can only be demoted when its current RV is θ₃=0 or θ₃=−1, therefore C₃ can never go below θ₃=−2.

Every time the EDRA makes an error on the current ERC, at least one constraint is demoted. Every time a constraint is demoted, its RV decreases by 1. Thus (20b) says that C₁ can never be demoted, C₂ can be demoted at most once and C₃ at most twice. This means in turn that the EDRA can perform at most 0+1+2=3 errors. We have thus proved convergence on the simple input ERC matrix in (19a).

The conclusion obtained in (20) can be summarised as follows: the RV θ_k of the constraint C_k assigned to the stratum k (with stratum 1 being the top one) can never make it below −(k−1). This statement is called an invariant, as it is a property of the current RVs that holds at any iteration throughout learning. T&S note that this invariant holds in general, as explained in §3.4. The only requirement is consistency of the input ERC matrix, spelled out in §3.3. Efficient convergence then follows straightforwardly from this invariant, as will be shown in §3.5.

3.3 Characterisation of OT-consistency

T&S's analysis of convergence of demotion-only re-ranking rules (as well as the developments of that analysis presented in the rest of this paper) crucially relies on the assumption that convergence is at least in principle achievable, i.e. that the input ERC matrix is consistent with at least a ranking. In order to distil useful computational consequences from this assumption, we need explicit characterisations of OT-consistency. I present here the characterisation of OT-consistency developed by T&S, using the ERC notation of Prince (Reference Prince2002); I revisit the issue of the algorithmic implications of the notion of OT-consistency in Appendix C of the online supplementary materials.

To introduce the idea, consider the ERC matrix in (21a), which is consistent with the ranking C₁≫C₂≫C₃≫C₄≫C₅. Reorder the columns of the matrix from left to right according to this ranking, as in (21b). Then place at the top ERCs a₁ and a₄, which have a w corresponding to C₁, as in (21c). Below them place ERC a₃, which has a w corresponding to C₂, as in (21d).

1. (21)

   

The ERC matrix obtained in (21d) can be described as follows. There is a top block of rows whose first entry is w, and a second block (here just one row) whose first entry is e, followed by w. The first two entries of the rows in the third block are e, and are followed by w. A straightforward generalisation of the procedure illustrated in (21) yields the following characterisation of consistent ERC matrices.

1. (22)

   

3.4 The crucial invariant

Consider a run of the EDRA with the demotion-only re-ranking rule (17) and initial null RVs. As the input ERC matrix is consistent, it can be brought into the form in (22), by Fact 1. The RV θ₁ of constraint C ₁ can never be as low as −1. Suppose by contradiction that it does. As C₁ starts out at θ₁=0, this means that C₁ has been demoted at least once. But that is impossible, as the re-ranking rule (17) only demotes loser-preferrers, and C₁ does not have a single l in (22). The RV θ₂ of constraint C₂ can never be as low as −2. Again, suppose by contradiction that it does. As the re-ranking rule (17) demotes by 1 only the undominated loser-preferrers, this means that at some point C₂ had a current RV of θ₂=−1 and was at that point an undominated loser-preferrer. But that is again impossible: in order for C₂ to be loser-preferring, the current ERC must belong to block 1, in which case C₂ is dominated by the winner-preferrer C₁, as the RV of C₂ is −1 by hypothesis, while the RV of C₁ is always 0, as just shown. The cases of C_k with k>2 are dealt with analogously, by induction on k. We have thus proved the following crucial invariant.

1. (23)

   

3.5 Efficient convergence

Suppose that we could construct a consistent input ERC matrix on which the EDRA run with the demotion-only re-ranking rule (17) does not converge, but rather performs an infinite number of updates. This means in turn that some constraint is demoted an infinite number of times. Its RV thus becomes arbitrarily small, violating the lower-bound (23). Thus the algorithm needs to stop after a finite number T of updates. At each update, one or more demotions are performed. Thus the total number of updates T must be smaller than the total number of demotions, as stated in (24).

1. (24)

   

Without loss of generality, assume that the input ERC matrix is consistent with the ranking C₁≫C₂≫…≫C_n. Fact 2 says that C₁ is never demoted, C₂ is demoted at most once, C₃ is demoted at most twice, and so on. Thus (24) becomes (25).

1. (25)

   

Using the identity 0+1+2+…+(n−1)=n(n−1)/2, we conclude with Theorem 1, which says that demotion-only converges efficiently, with a worst-case number of updates quadratic in the number n of constraints.

The bound n(n−1)/2 on the worst-case number of updates provided by the Theorem is tight, and thus not improvable. In fact, suppose that there are 4 constraints and that the input ERC matrix is (26a), which Riggle (Reference Riggle2009) calls ‘diagonal’. The learning path (26b) takes 4(4−1)/2=6 updates to reach convergence.

1. (26)

   

So far, I have only considered the case of null initial RVs. For the extension to arbitrary initial RVs, see Appendix A of the online supplementary materials.

3.6 Why only demote the loser-preferrers that are undominated?

The re-ranking rule (17) only demotes the loser-preferrers that really need to be demoted, namely the currently undominated ones, which are not currently ranked below a winner-preferrer. What happens if we demote all loser-preferrers, both the dominated and the undominated ones? For the sake of explicitness, consider the variant in (27). The EDRA in Fig. 5 with this re-ranking rule is Boersma's (Reference Boersma1997) (non-stochastic) demotion-only GLA.

1. (27)

   1. a. Decrease the RV of each loser-preferrer by 1.

   2. b. Do nothing to the current RV of the winner-preferrers.

For instance, if the current ERC is again (16a) and the current ranking vector (16b), the updated ranking vector is (28): the RV of both loser-preferrers C₄ and C₆ is decreased by 1, despite the fact that only the former is currently undominated.

1. (28)

   

The invariant (23) says that constraints cannot be demoted too far, as long as we only demote the constraints that need to be demoted, namely the currently undominated loser-preferrers. This invariant no longer holds if all loser-preferrers, both dominated and undominated, are demoted. As a counterexample, consider the run in (29b), with the re-ranking rule (27): the RV of constraint C₂ drops to −3, despite the fact that the input ERC matrix (29a) is consistent with the ranking C₁≫C₂≫C₃≫C₄, which assigns C₂ to stratum 2.

1. (29)

   

In the case of the re-ranking rule (17), which demotes only currently undominated loser-preferrers, the invariant (23) entails efficient convergence, with an error-bound quadratic in the number of constraints. In the case of (27), which demotes all loser-preferrers, convergence still holds, but efficiency does not, as the worst-case number of errors can be shown to be exponential in the number of constraints; see Magri (Reference Magri2009). In conclusion, it is a good idea to demote only those loser-preferrers that need to be demoted, i.e. those that are currently undominated.

3.7 A non-gradual variant

The re-ranking rule in (17) is gradual, as it modifies the current RVs only by a small fixed amount. Thus multiple consecutive updates by a single ERC might be needed in order for the current ranking vector to become consistent with that ERC. For instance, the top path in (19b) shows that two consecutive updates by ERC 2 are needed before the current ranking vector becomes consistent with that ERC. Suppose that we wanted to save time, replacing those two updates with a single step. To achieve this, we would need to have demoted more the first time we encountered ERC 2, so that no further consecutive update by that ERC would have been necessary. A re-ranking rule is non-gradual provided it performs updates large enough that the current ranking vector becomes consistent with the current ERC after a single update, so that no ERC can trigger two consecutive updates. To illustrate, consider re-ranking rule (30), which demotes currently undominated loser-preferrers to a position below the currently top-ranked winner-preferrer. The EDRA in Fig. 5 with this re-ranking rule is T&S's EDCD.Footnote ⁶

1. (30)

   1. a. Decrease the current RV of each undominated loser-preferrer to θ* – 1, where θ* is the largest RV over winner-preferrers.

   2. b. Do nothing to the current RV of the other constraints.

For instance, if the current ERC is again (16a) and the current ranking vector (16b), the updated ranking vector is (31). Only the RV of C₄ is modified, as it is the only currently undominated loser-preferrer. It is decreased from its original value 15 to the updated value 9, i.e. the RV θ*=10 of the currently top-ranked winner-preferrer C₁ further decreased by 1.

1. (31)

   

The undominated loser-preferrer C ₄ is demoted in (31) by 6. This amount is large enough that the updated ranking vector is consistent with the ERC after just one update. Re-ranking rule (30) is non-gradual, because no ERC can trigger two consecutive updates. This non-gradual rule is a ‘speeded up’ version of the gradual re-ranking rule in (17). Thus it comes as no surprise that the analysis developed above for (17) extends to (30), ensuring efficient convergence in the latter case as well.

3.8 Summary

In this section, we have seen that efficient convergence is possible, at least in the case of EDRAs that only perform constraint demotion. The core of the analysis can be summarised as follows: every time the algorithm performs an update, some RVs are decreased; yet RVs cannot be decreased too much, because of the invariant (23); thus the algorithm cannot make too many updates. Furthermore, we have seen two rules of thumb for devising good re-ranking rules. First, not all loser-preferrers should be demoted, but only those that really need to be, the currently undominated ones. Second, we can focus on gradual re-ranking rules, as non-gradual convergent re-ranking rules can then be obtained straightforwardly from gradual ones, by collapsing multiple updates by the same ERC.

4.1 Modelling the early stage of the acquisition of phonotactics

In carefully controlled experimental conditions, nine-month-old infants already react differently to licit and illicit sound combinations (Jusczyk et al. 1993, among others). They thus display knowledge of phonotactics at an early stage, when other linguistic abilities are still not fully developed. In particular, morphology is still lagging behind at this early age, so that the child still has no access to phonological alternations. Hayes (Reference Hayes2004: 165) thus concludes that ‘it seems a reasonable guess that in general, the learning of patterns of alternation [that only comes with knowledge of morphology] lags behind the learning of the contrast and phonotactic systems’. In other words, there is a developmental stage, the early stage of the acquisition of phonotactics, throughout which the child acquires phonotactics without the aid of phonological alternations.

Another crucial property of the acquisition of phonotactics is gradualness: the target adult grammar is approached through a path of intermediate stages (for classical examples, see e.g. Smit et al. Reference Smit, Hand, Freilinger, Bernthal and Bird1990, Levelt et al. Reference Levelt, Schiller and Levelt2000, Pater & Barlow Reference Pater and Barlow2003 and Gnanadesikan Reference Gnanadesikan2004; for reviews, see e.g. McLeod et al. Reference McLeod, Doorn and Reed2001 and Zamuner et al. Reference Zamuner, Gerken and Hammond2005). Assume that this gradualness reflects grammatical development, rather than just the slow development of performance factors that are orthogonal to linguistic competence (say the slow development of the articulators and of the corresponding motor programs); see Smolensky (Reference Smolensky1996a), as well as Hale & Reiss (Reference Hale and Reiss1998) for critical discussion. From this perspective, EDRAs provide an ideal model of the acquisition of phonotactics, as they describe a path within the space of possible phonotactics that can be matched with attested acquisition paths. What should a proper error-driven ranking model of the early stage of the acquisition of phonotactics look like?

To address this question, consider the full-blown description of EDRAs in Fig. 7. The algorithm maintains a current ranking vector, initialises it to an assigned initial ranking vector and keeps updating it by looping through the five steps (a)–(e). At step (a), the algorithm receives a form [y] from the target adult language. At step (b), the algorithm needs to apply some subroutine in order to figure out a corresponding underlying form /x/. And at step (c), it needs to choose a corresponding loser form [z] (up to now, I have collapsed these three steps into a single one, as the focus was on the computational rather than the modelling side). At step (d), the algorithm checks whether the current ranking vector is consistent with the underlying/winner/loser form triplet (/x/, [y], [z]) thus assembled. If it isn't, then it takes action at step (e).

Figure 7

Full-blown description of the main loop of an EDRA.

Various implementation details now need to be specified, concerning the choice of the initial ranking vector, the subroutine that provides the underlying form /x/ at step (b) and the re-ranking rule to be used at step (e).Footnote ⁷ I discuss these three issues in turn in §§4.2–4.4. The conclusion of the argument will be that constraint promotion is crucially needed in order to turn the algorithmic kernel in Fig. 7 into a proper model of the early stage of the child acquisition of phonotactics.

4.2 Choice of the initial ranking vector

There is wide agreement in the literature that markedness constraints should start out initially ranked above faithfulness constraints; see Smolensky (Reference Smolensky1996a, b) for theoretical arguments in favour of this hypothesis, Jusczyk et al. (Reference Jusczyk, Smolensky and Allocco2002) for empirical evidence, Davidson et al. (Reference Davidson, Jusczyk and Smolensky2004) for a review and Hale & Reiss (Reference Hale and Reiss1998) for critical discussion. I thus assume that the initial RV of markedness constraints is larger than that of faithfulness constraints. For instance, assume that the former is some large positive constant θ^init>0, while the latter is zero.

4.3 Choice of the underlying form

At step (a), the EDRA is fed a licit surface form [y] from the target adult language and needs to pick a proper corresponding underlying form /x/ at step (b), as well as a loser form [z] at step (c). To see how to proceed, consider a concrete example. Suppose the learner is provided with the winner form [y]=[rat]. To keep things simple, suppose the only option for the loser is [z]=[rad], and that there are two options for the underlying form: the learner could select the underlying form /x/=/rat/, faithful to the winner, and thus construct the triplet (32a), or it could select the underlying form /x/=/rad/, unfaithful to the winner, and thus construct the triplet (32b).

1. (32)

   

The choice of the non-faithful underlying form in the data triplet (32b) is equivalent to the assumption that the target phonology enforces final devoicing. But this assumption might be dangerous. In fact, a crucial property of the early stage of the acquisition of phonotactics is that the learner is still blind to alternations, as noted above. At this stage, the learner is thus not in a position to evaluate its assumption that the target phonology enforces final devoicing. The choice of a non-faithful underlying form might thus turn out to fool the learner into positing inconsistent data triplets at steps (a)–(c) of Fig. 7. I thus assume that the learner posits an underlying form faithful to the winner, as illustrated in the triplet (32a) and stated in (33). This assumption models the fact that the child is blind to alternations throughout the early stage of the acquisition of phonotactics; see Hayes (Reference Hayes2004) and Prince & Tesar (Reference Prince and Tesar2004).

1. (33) At step (b), the EDRA posits an underlying form /x/ identical to the given surface form [y], thus always building faithful triplets such as (32a).

Of course, this assumption only makes sense provided that the set of underlying forms coincides with the set of surface forms, so that the same phonological structure can be construed both as an underlying and as a surface form. In that case, a result by Tesar (Reference Tesar2008) shows that assumption (33) has a remarkable computational property: the underlying/winner/loser form triplets thus constructed at steps (a)–(c) are always consistent, under only mild assumptions on the constraint set. Tesar's result means in particular that, at least in the case of the acquisition of phonotactics, OT-consistency of the data fed to the algorithm can be assumed without loss of generality.

4.4 Choice of the re-ranking rule

We are now left with the crucial choice of the re-ranking rule that a proper error-driven ranking model of the early stage of the acquisition of phonotactics should use at step (e) of Fig. 7. From a computational perspective, a crucial issue that bears on the choice of the re-ranking rule is that of efficient convergence: which choices ensure that the number of errors is finite and grows slowly with the number of constraints? Suppose that the EDRA indeed converges. Then its final grammar successfully rules in every licit form – otherwise the algorithm could still make mistakes, and therefore could not have converged. Yet phonotactics is the knowledge of the distinction between licit and illicit forms. If, say, the final grammar ranks all faithfulness constraints at the top, then it fails to rule out any illicit form, and the EDRA has effectively learned nothing. A second issue relevant to the choice of the re-ranking rule to be used at step (e) is thus that of restrictiveness: which choices ensure that the final grammar entertained by the EDRA at convergence successfully manages to rule out illicit forms? Finally, suppose that the EDRA converges to a restrictive final grammar. On its way to that grammar, the EDRA entertains a path of intermediate rankings, each corresponding to an intermediate OT phonotactics. Thus the third issue is that of matching: which choices yield learning sequences that best match attested acquisition paths?

The focus of this paper is squarely on the first of these three issues, namely efficient convergence. As reviewed in §3, demotion-only re-ranking rules fare well from the computational perspective of convergence. However, in this subsection I will take a detour from my main focus on convergence, and look at the choice of the re-ranking rule from the modelling perspective of restrictiveness and matching between predicted learning sequences and acquisition paths. I will argue that, from the latter perspective, demotion-only is insufficient and that some degree of constraint promotion is needed. This conclusion will motivate the rest of the paper, which develops provably convergent re-ranking rules that perform both constraint demotion and promotion.

4.4.3 More on restrictiveness and constraint promotion

What happens when an EDRA that performs both constraint demotion and promotion is trained on the two languages in (35)? Is it indeed able to rank the faithfulness constraints correctly, as in the target rankings in (36)? The input ERC matrices corresponding to (35) are provided in (37). Let me explain how matrix (37a), for instance, has been computed. The target language consists of the five surface forms [pa], [ba], [sa], [apsa] and [abza]. Of these five forms, only [ba] and [abza] are informative, as the other three forms are unmarked, and therefore do not contribute to learning (their ERCs never trigger any updates). For the informative form [ba], we need to consider only one underlying/winner/loser triplet, namely the one that pairs this winner surface form with the faithful underlying form /ba/ and the loser form [pa]. For the other informative form, [abza], we need to consider three triplets, which pair this winning form with the faithful underlying form /abza/ and the three loser forms [apsa], [apza] and [absa]. The ERC matrix in (37a) is obtained by assembling, one on top of the other, the ERCs corresponding to these four triplets.

1. (37)

   

I provide in Fig. 8 the dynamics of the RVs of the five constraints predicted by the EDRA with a promotion-demotion re-ranking rule trained on the two input matrices in (37). The initial ranking vector used in the simulations has been chosen according to §4.2: the faithfulness constraints are initially ranked at the bottom (with a null initial RV) and the markedness constraints at the top (with an initial RV of θ^init=10000). The simulations use the (efficiently convergent) re-ranking rule (51) developed below in §6: the details of the re-ranking do not matter here, except for the fact that constraint promotion is performed as well as demotion. Finally, the ERCs are sampled uniformly from the input ERC matrix.

Figure 8

Ranking dynamics predicted by a promotion/demotion EDRA trained on the two ERC matrices (37a) and (b) respectively.

The final ranking vectors that the promotion/demotion EDRA converges to in the two simulations in Fig. 8 are provided in (38a) and (b) respectively.

1. (38)

   

Surprisingly, these two final ranking vectors correctly represent the two target rankings in (36). Consider for instance (38a): the RV of F₁ is larger than both the RVs of M₁ and M₂, thus representing the target rankings (36a.i) and (36a.iii), the RV of M₂ is larger than the RV of F₂ (36a.ii) and the RV of M₃ is larger than the RV of M₂ (36a.iv). In particular, the promotion component of the re-ranking rule has allowed the EDRA to learn the correct relative ranking of the two faithfulness constraints F₁ and F₂.

A quick look at the input ERC matrices in (37) reveals what is behind this success. Consider for instance (37a). The three markedness constraints start out with the same initial RV. After one update by the penultimate ERC, M₁ is demoted and M₃ is promoted. The current ranking vector thus enforces the ranking configuration M₃≫M₁, ensuring consistency with this ERC. Furthermore, this ranking configuration will never be disrupted in the rest of the learning process, as M₃ can never be demoted (because it is never a loser-preferrer) and M₁ can never be promoted (because it is never a winner-preferrer). Thus the penultimate ERC can trigger at most one update, and is therefore pretty much irrelevant for the overall ranking dynamics. Analogous considerations hold for the last ERC, so that the ranking dynamics are completely determined by the first two ERCs. The first ERC promotes only F₁, while the second ERC promotes both F₁ and F₂. Thus a single update by the first ERC is sufficient to ensure that F₁ will be ranked above F₂ from that time on. In other words, a single update by the first ERC is enough to guarantee that the EDRA will converge to the correct relative ranking of the two faithfulness constraints. As F₁ is thus ranked above F₂, the two markedness constraints M₁ and M₂ will intercept F₁ first in their free fall. As soon as they cross F₁, learning ceases, as the current ranking vector has become consistent with the entire ERC matrix. M₁ and M₂ thus find themselves squeezed in between F₁ and F₂, as desired. Although the input ERCs are sampled uniformly in the simulations reported above, the analysis just sketched reveals that the EDRA will converge to the correct final ranking no matter how the input ERCs are sampled, as long as the first ERC gets a chance to trigger a few updates. In conclusion, the OT typology in (34) has the following remarkable property: the only two languages that require a faithfulness constraint to be ranked above another faithfulness constraint correspond to input ERC matrices that are able to train the EDRA to learn that relative ranking.

In Magri (Reference Magri2012b), I show that EDRAs are restrictive on any language that does not require any faithfulness constraint to be ranked above another faithfulness constraint. As expected, such languages constitute the vast majority: the relative ranking of the faithfulness constraints matters for the way illicit structures are repaired, but it matters only rarely for the divide between licit and illicit structures. What about the remaining languages, which require a specific relative ranking of the faithfulness constraints? In Magri (Reference Magri, Heinz, Cahill and Wicentowski2010, to appear a), I show that restrictiveness cannot be achieved in the general case by any algorithmic scheme. In other words, there is no learning algorithm from positive evidence that can ensure restrictiveness, unless we make assumptions about the underlying OT typologies. This result motivates the following conjecture: is it the case that phonologically plausible OT typologies happen to have the property just observed for the typology in (34), i.e. that every language in the typology that requires a certain faithfulness constraint to be ranked above another faithfulness constraint correspond to an input ERC matrix that is able to train the EDRA to learn that relative ranking? If this conjecture turns out to be correct, it will provide formidable support for the hypothesis that error-driven learning is a proper model of the child's acquisition of phonotactics. In Magri (Reference Magri, Carlson, Hölscher and Shipley2011, Reference Magri2012b), I report a first result in this direction. I consider all possible constraints of the type of M₃ in (34), which is responsible for the interaction between the two features that define the typology. And I show that promotion/demotion EDRAs are restrictive, except for phonologically implausible models of feature interaction.

4.5 Summary

Tesar & Smolensky (Reference Tesar and Smolensky1998) develop the first EDRA, error-driven constraint demotion, reviewed in §3. Its signature property is that it performs constraint demotion but no constraint promotion. Lack of constraint promotion allows Tesar & Smolensky to prove that EDCD converges with an efficient error-bound (cf. also Boersma Reference Boersma2009). Although a virtue from a computational perspective, lack of constraint promotion turns out to be a liability from a modelling perspective, as argued in this section. I have looked at one of the main modelling applications of EDRAs, the modelling of the early stages of the acquisition of phonotactics. In this case, it makes sense to assume that the EDRA is provided with winner forms only, and that it assumes underlying forms faithful to the winners. Training on faithful mappings entails that faithfulness constraints are never loser-preferrers. As EDCD only demotes loser-preferrers, it never re-ranks the faithfulness constraints. This cannot be right from the perspective of restrictiveness: if two languages in the typology require the opposite relative ranking of some faithfulness constraints, EDCD fails to learn that. Furthermore, it cannot be right from the perspective of matching the predicted learning sequences with acquisition paths: if an acquisition path shows a succession of different repair strategies for the same marked structure, EDCD fails to model it. In conclusion, EDCD is unable to implement the error-driven learning model of the acquisition of phonotactics. And some amount of constraint promotion is needed, in order to re-rank the faithfulness constraints, despite the fact that they are never loser-preferrers. This conclusion motivates the research question addressed in the rest of this paper: is it possible to devise convergent re-ranking rules that perform constraint promotion in addition to demotion? §5 reviews what is currently known in the OT computational literature concerning constraint promotion.

5.1 The credit problem

Suppose that the current ERC fed to the EDRA has multiple w's; say it has two w's corresponding to the two constraints C_h and C_k, as in (39a). A promotion/demotion EDRA needs to decide which one of the two winner-preferrers, C_h or C_k, should be credited for OT-consistency with the current ERC. And the decision must be taken instantaneously, without looking at the rest of the ERC matrix. This is a very challenging task. In fact, the ERC matrix could contain another ERC like (39b), which says that only C_h should be credited for shielding the loser-preferrer of the ERC in (39a). This is an example of what Dresher (Reference Dresher1999) calls the ‘credit problem’.

1. (39)

   

A demotion-only re-ranking rule gets around the credit problem by avoiding any promotion. But a promotion/demotion re-ranking rule might in principle be fooled by the credit problem, as noted by Tesar & Smolensky (Reference Tesar and Smolensky1998: 244), who explicitly warn against constraint promotion: according to EDCD, ‘all movement of constraints is downward in the hierarchy. One could reasonably ask … couldn't the learner just as easily promote constraints toward the correct hierarchy? The answer is no’.

5.2 Gradualness and the credit problem

Boersma (Reference Boersma1997, Reference Boersma1998) suggests that gradualness might get around the credit problem. Consider a re-ranking rule that makes only small, gradual adjustments at each iteration. Even if at a given iteration the algorithm incorrectly promotes a winner-preferrer that should in the end be at the bottom of the ranking, this will be only a small mistake, and small mistakes will hopefully in the end be overridden by subsequent better moves.

More explicitly, Boersma (Reference Boersma1997, Reference Boersma1998) and Boersma & Hayes (Reference Boersma and Hayes2001) consider the re-ranking rule in (40), whereby loser-preferrers are demoted and winner-preferrers promoted by a small amount, say 1. This is the only example in the current literature of a re-ranking rule that performs both constraint demotion and promotion. The EDRA in Fig. 5 with this re-ranking rule is Boersma's (Reference Boersma1997) (non-stochastic) Gradual Learning Algorithm.Footnote ⁹

1. (40)

   1. a. Decrease the RV of each loser-preferrer by 1.

   2. b. Increase the RV of each winner-preferrer by 1.

For instance, if the current ERC and the current ranking vector are again as in (16), then the updated ranking vector is (41). The RVs of the two loser-preferrers C₄ and C₆ are decreased from 15 and 5 to 14 and 4. And the RVs of the two winner-preferrers C₁ and C₂ are increased from 10 and 5 to 11 and 6.

1. (41)

   

The GLA converges in the case of input ERC matrices that have a unique winner-preferrer per ERC, and thus do not raise any credit problem.Footnote ¹⁰ But what about the case of input ERC matrices with multiple winner-preferrers per ERC? Does Boersma & Hayes' conjecture above, that gradualness gets around the credit problem, prove correct? As observed by Keller & Asudeh (Reference Keller and Asudeh2002), this question remained open for a number of years, until Pater (Reference Pater2008) showed that gradual promotion/demotion re-ranking rules are also indeed fooled by the credit problem, despite the fact that they make only small adjustments to the current RVs. He considers the input ERC matrix (42), which exacerbates the credit problem by stacking multiple ERCs with two winner-preferrers. He reports that the GLA trained on this input ERC matrix (with the ERCs sampled uniformly and with identical initial RVs for the five constraints) keeps increasing its current RVs, without ever converging to an consistent vector.Footnote ¹¹ Pater's counterexample thus settles the issue of the convergence of the GLA.Footnote ¹²

1. (42)

   

Pater does not explain why exactly the specific instance of the credit problem raised by his counterexample fools the GLA. Furthermore, he leaves it open whether the GLA might converge if the strong regularity of the ERC matrix (42) is broken by sampling its rows according to a skewed distribution, rather than the uniform distribution considered in his simulations. In §5.3, I offer a detailed explanation of the failure of the GLA on Pater's counterexample: the algorithm fails because all ranking vectors consistent with the input ERC matrix lie outside its search space. This explanation shows in particular that the GLA fails no matter how the ERCs in (42) are sampled and fed to the algorithm, thus slightly strengthening Pater's counterexample.

5.3 A detailed explanation of Pater's counterexample

Consider a run of the GLA on Pater's counterexample (42), starting from null initial RVs. Every time ERC 1 triggers an update according to (40), the RVs of the winner-preferrers C₁ and C₃ are increased by 1, and the RV of the loser-preferrer C₂ is decreased by 1. Equivalently, the current ranking vector is updated by adding to it the update vector corresponding to ERC 1, i.e. the vector that has a 1 for the two winner-preferrers C₁ and C₃, −1 for the loser-preferrer C₂ and 0 elsewhere. Every time ERC 2 triggers an update according to (40), the RVs of the winner-preferrers C₂ and C₄ are increased by 1, and the RV of the loser-preferrer C₃ is decreased by 1. Equivalently, the current ranking vector is updated by adding to it the update vector corresponding to ERC 2, which has a 1 for the two winner-preferrers C₂ and C₄, −1 for the loser-preferrer C₃ and 0 elsewhere. And so on.

Thus the ranking vector θ entertained by the GLA at a generic iteration has the shape in (43): it is obtained by adding together the four column vectors that appear in (43), each multiplied by a non-negative coefficient α_i. The ith column vector in (43) is the update vector corresponding to the ith ERC of Pater's counterexample (42). It is obtained by replacing each w, l and e in the ERC with 1, −1 and 0 respectively, thus encoding the contribution of the ith ERC to the current ranking vector according to the GLA re-ranking rule in (40). The corresponding coefficient α_i in (43) represents the number of updates triggered by the ith ERC of Pater's tableau in the run up to the time considered.

1. (43)

   

Adding up the corresponding components in (43), we can conclude that the search space of the GLA run on Pater's counterexample, starting from the null initial vector, is a subset of the set of ranking vectors of the form (44), for non-negative coefficients α₁, α₂, α₃, α₄. This conclusion makes good sense. Constraint C₁ starts out with a null initial RV and is promoted by 1 every time ERC 1 triggers an update. Thus the current RV θ₁ of constraint C₁ must always be equal to the number α₁ of updates triggered by ERC 1, as stated in the first equation in (44). Constraint C₂ starts out with a null initial RV, is promoted by 1 every time ERC 2 triggers an update and demoted by 1 every time ERC 1 triggers an update. Thus the current RV θ₂ of constraint C₂ must always be equal to the number α₂ of updates triggered by ERC 2 minus the number α₁ of updates triggered by ERC 1, as stated in the second equation in (44). And so on.

1. (44)

   

There is only one ranking consistent with the ERC matrix in (42), namely C₁≫C₂≫C₃≫C₄≫C₅. Thus, a ranking vector θ=(θ₁, θ₂, θ₃, θ₄, θ₅) is consistent with Pater's ERC matrix only if it univocally represents this ranking, i.e. it satisfies the four strict inequalities θ₁>θ₂>θ₃>θ₄>θ₅. By virtue of the characterisation in (44) of the ranking vectors entertained by the GLA, these four strict inequalities can be rewritten as the four strict inequalities in (45), in terms of the coefficients α₁, α₂, α₃, α₄.

1. (45)

   

Crucially, the four strict inequalities in (45) are not feasible, as there exist no coefficients α₁, α₂, α₃, α₄ that satisfy all four of them at the same time (see Appendix E of the online supplementary materials). In conclusion, the reason why the GLA fails on Pater's counterexample is as follows: the search space of the GLA is limited to ranking vectors of the form (44), but no such ranking vector is consistent with Pater's ERC matrix, as none satisfies the inequalities in (45). In other words, the GLA fails because it struggles to reach a ranking vector that lies beyond its reach.Footnote ¹³ Pater detected the failure of the GLA on (42) through simulations where the various ERCs were sampled uniformly. The explanation just provided slightly strengthens his counterexample, showing that the GLA fails no matter how the input ERCs are sampled and fed to the algorithm.

5.4 Summary

On the one hand, §4 argued in favour of constraint promotion from a modelling perspective: throughout the early stage of the acquisition of phonotactics, the learner can confidently only posit underlying forms faithful to the winners; the faithfulness constraints would therefore never be re-ranked by a demotion-only EDRA, as they are never loser-preferrers; and the predicted learning dynamics would thus be too simple to match the attested typological and acquisition complexity. On the other hand, this section has shown that constraint promotion is hard to devise from a computational perspective, because of the credit problem: only a subset of the current winner-preferrers should be credited for accounting for the current loser-preferrers; it is not possible to promote only these useful winner-preferrers, because we cannot select them based only on the current ERC, and it is not safe to promote all of them, because this strategy leads to repeated promotions of winner-preferrers that should be low-ranked, as in Pater's counterexample. The rest of the paper presents a solution to this impasse, allowing us to move a step forward towards the integration of the modelling and computational perspectives.

6.1 Calibration of the promotion amount

We want the promotion component of the re-ranking rule in (46) not to overwhelm the demotion component, so that it will hopefully not disrupt too much the good convergent behaviour of demotion-only. This requires a proper calibration of the promotion amount p. Let us work through various concrete cases. Consider first the special case where the current input ERC fed to the EDRA has a unique l and a unique w, as in (47).

1. (47)

   

According to (46a), the unique loser-preferrer is demoted by 1 (47a), and the unique winner-preferrer is promoted by the promotion amount p. In order not to disrupt the convergence properties of demotion-only, we should promote less than we demote. We therefore set the promotion amount p smaller than 1, as in (47b).

Consider next the case where the current input ERC again has a unique l, but now has multiple w's. For concreteness, suppose it has two w's, as in (48).

1. (48)

   

The loser-preferrer is again demoted by 1, according to (46a). And both winner-preferrers are promoted by the promotion amount p. Thus the overall promotion is 2p. Again, we should promote less than we demote, which requires 2p to be smaller than 1. Thus, we select a promotion amount smaller than 1/2, as in (48b).

The extension to the case where the current ERC fed to the EDRA has an arbitrary number w of winner-preferrers and again a unique loser-preferrer (49) is straightforward.

1. (49)

   

Once more, the unique loser-preferrer is demoted by 1. Each of the winner-preferrers is promoted by p. As we overall promote by wp, and we want wp to be smaller than 1, p must be smaller than 1/w, as in (49b).

So far, I have only considered the case where the current ERC has a unique loser-preferrer. If such an ERC is not consistent with the current ranking vector, then its unique loser-preferrer must be currently undominated, i.e. it must be ranked above the currently top-ranked winner-preferrer. If the current ERC has multiple loser-preferrers, then some of them might be currently undominated and others might not be. Let l be the total number of currently undominated loser-preferrers. If only one loser-preferrer is currently undominated, then we can of course use again the same re-ranking rule (49). What if the number l of currently undominated loser-preferrers is larger than one?

1. (50)

   

Each of the l undominated loser-preferrers is demoted by 1, by (46a), so that we demote by l overall. Each of the w winner-preferrers is promoted by the promotion amount p, so that the overall promotion is wp. In order not to disrupt the convergent behaviour of demotion-only, wp must be smaller than l. p is therefore smaller than l/w, as in (50b).

In conclusion, the crucial threshold for the calibration of the promotion amount is the ratio l/w between the number l of undominated loser-preferrers and the number w of winner-preferrers. Informally, this threshold can be justified in terms of the two following intuitions. As the number l of undominated loser-preferrers increases, we demote more constraints, which gives us a larger promotion amount, without promotion overwhelming demotion. As the number w of winner-preferrers increases, we promote more constraints, and therefore need to adopt a smaller promotion amount in order for promotion not to overwhelm demotion. This ratio l/w is the calibration threshold. A re-ranking rule of the form (50), whose promotion amount is strictly smaller than the calibration threshold, is calibrated.

For instance, set the promotion amount p equal to l/(w+1). This re-ranking rule (51) is calibrated, as the promotion amount is indeed slightly smaller than the calibration threshold l/w, so that the promotion component of the re-ranking rule never overwhelms the demotion component.

1. (51)

   1. a. Decrease the RV of each of the l undominated loser-preferrers by 1.

   2. b. Increase the RV of each of the w winner-preferrers by p=l/(w+1).

For instance, if the current ERC and ranking vector are again as in (16), then the updated ranking vector is (52). Of the two loser-preferrers C₄ and C₆, only the former is currently undominated. Thus, its RV is decreased by 1. The RV of the two winner-preferrers C₁ and C₂ is increased by 1/3, i.e. the number of undominated loser-preferrers (l=1) divided by the number of winner-preferrers (w=2)+1.

1. (52)

   

The ranking dynamics in the case of (51) are rather complicated, as RVs can oscillate over time, contrary to the monotonically decreasing dynamics predicted by demotion-only re-ranking rules. Despite the complexity of the ranking dynamics, the current RVs display invariant properties, spelled out in §6.2 and §6.3. These invariants lead to efficient convergence, as noted in §6.4. The reasoning turns out to be a small extension of T&S's analysis of demotion-only re-ranking rules.

6.2 T&S's invariant extends beyond demotion-only

As observed in §3, T&S's analysis of demotion-only re-ranking rules rests on the core observation that the current RVs cannot drop too low over time, as stated in Fact 2. A careful look at the proof of this invariant reveals that it does not actually hinge in any way on the demotion-only assumption. Rather, it follows from the fact that not all loser-preferrers are demoted, but only those that really need to be demoted, i.e. the currently undominated ones. In other words, if we only demote the constraints that need to be demoted, we cannot demote too much. T&S's Fact 2 thus extends to an arbitrary promotion/demotion re-ranking rule, as long as it only demotes undominated loser-preferrers, as made explicit in the following generalised formulation of Fact 2.

1. (53)

   

6.3 An invariant for calibrated re-ranking rules

The sum of the current RVs in (16b) is 155 (10+5+20+15+100+5). The updated RVs in (52) add up to 154·6. The fact that the sum of the updated RVs is smaller than that of the current RVs is not a coincidence, but rather a general property of calibrated re-ranking rules. Let me illustrate this, focusing on the calibrated re-ranking rule in (51). Suppose that the ERC triggering the current update has l undominated loser-preferrers and w winner-preferrers. The demotion component (51a) subtracts the demotion amount 1 from the RV of each of the l undominated loser-preferrers, so that the sum of the current RVs is decreased by l=1×l overall. The promotion component (51b) adds the promotion amount l/(w+1) to the RV of each of the w winner-preferrers, thus increasing the sum of the current RVs by (l/(w+1))×w overall. As the amount that is added to the sum of the current RVs (wl/(w+1)) is always smaller than the amount that is subtracted (l), the sum of the current RVs decreases at each update. The amount by which it decreases can be computed as in (54).

1. (54)

   

To trigger an update, the current ERC must have at least one undominated loser-preferrer, i.e. l must be at least 1. As the number of constraints is n and at least one of them is loser-preferring, there can be at most n−1 winner-preferrers, i.e. w can be at most n−1. Replacing l with 1 and w with n−1 in the right-hand side of (54), I conclude that at each update the sum of the current RVs decreases by at least 1/n.

6.4 Calibration ensures efficient convergence

The proof of efficient convergence now follows straightforwardly. Consider a run of the EDRA on a consistent ERC matrix using the calibrated re-ranking rule in (51). Suppose for concreteness that the initial RVs are all null. As the input ERC matrix is consistent by hypothesis, the generalised Fact 2 ensures that the current RVs θ₁, …, θ_n cannot become too small, as in (53). Because of the identity 0+1+2+…+(n −1)=n(n−1)/2, (53) entails that the sum of the current RVs never gets smaller than the constant −n(n−1)/2 (which only depends on the number n of constraints), as stated in (55).

1. (55)

   

By Fact 3, the sum of the current RVs decreases by at least 1/n with every update. After T updates, it thus has decreased by at least T/n. As we start from initial null RVs, the sum of the current RVs after T updates is thus smaller than or at most equal to −T/n, as in (56).

1. (56)

   

By combining together the two inequalities (55) and (56), we get the upper bound (57) on the number T of updates. In other words, as the sum of the current RVs decreases by at least 1/n with every update but cannot get smaller than −n(n−1)/2, then the algorithm cannot perform too many updates, i.e. no more than n ²(n−1)/2.

1. (57)

   

We have thus proved Theorem 2, which guarantees efficient convergence for the calibrated promotion/demotion re-ranking rule in (51). The reasoning just outlined easily extends to an arbitrary calibrated re-ranking rule, with the quality of the error-bound depending on how much the promotion amount is smaller than the calibration threshold l/w; see Appendix B of the online supplementary materials for details. The extension from null initial RVs to arbitrary ones is straightforward, as discussed in Appendix A of the online supplementary materials.

This section started from the intuition that the good convergent behaviour of demotion-only EDRAs should be retained or only slightly affected provided that the promotion component of the re-ranking rule does not overwhelm the demotion component. This requires a proper calibration of the promotion amount, as in the new calibrated re-ranking rule (51). Theorem 2 confirms that this initial intuition is correct. In fact, T&S's Theorem 1 ensures an error-bound for demotion-only that grows only quadratically with the number of constraints, while Theorem 2 provides an error-bound for the new calibrated promotion/demotion re-ranking rule in (51) that is only slightly worse, growing cubically rather than quadratically in the number of constraints.

6.5 Summary

Tesar & Smolensky's (Reference Tesar and Smolensky1998) original proof of convergence for demotion-only, reviewed in §3, was based on two crucial properties of the sum of the current RVs. The first property is that this sum can never become smaller than a certain constant that depends on the number of constraints, as stated in (58a). The second property is that, as long as we perform demotion only, the current RVs can only decrease over time, and in turn their sum can only decrease, as stated in (58b). Convergence immediately follows: as the sum of the current RVs keeps decreasing by (58b), but by (58a) cannot decrease too much, then learning must stop at a certain point.

1. (58) The sum of the current RVs

   1. a. can never become smaller than a certain constant;

   2. b. starts at zero and decreases a little with every update.

Property (58a) has nothing to do with the promotion issue. Rather, it follows from the fact that constraints cannot drop too much, as long as we only demote the constraints that really need to be demoted, namely the currently undominated ones. This property thus extends to any re-ranking rule that only demotes undominated loser-preferrers (generalised Fact 2). The case of property (58b) is more difficult. For instance, it does not hold for Boersma's GLA re-ranking rule in (40): if there are two winner-preferrers that are each promoted by 1 and one loser-preferrer that is demoted by 1, then the sum of the RVs increases by 1, instead of decreasing. Yet property (58b) is not altogether incompatible with constraint promotion. In fact, calibration of the promotion amount was designed in §6.1 in order to ensure that the sum of the current RVs decreases with each update, despite promotion (Fact 3). Convergence for calibrated promotion/demotion re-ranking rules follows again from the two properties in (58).

7.1 Smallest non-calibrated promotion

In this section, I study the re-ranking rule in (59). Its crucial property is that the promotion amount is set equal to the calibration threshold l/w, namely the ratio between the number l of undominated loser-preferrers and the number w of winner-preferrers. In other words, this is the update rule with the smallest possible promotion amount among those which are not calibrated and thus do not fall under the theory developed in §6.

1. (59)

   1. a. Decrease the RV of each of the l undominated loser-preferrers by 1.

   2. b. Increase the RV of each of the w winner-preferrers by l/w.

For instance, if the current ERC and ranking vector are again as in (16), then the updated ranking vector is (60). Of the two loser-preferrers C₄ and C₆, only the former is currently undominated. Its RV is thus decreased by 1. The RV of the two winner-preferrers C₁ and C₂ is increased by 1/2, i.e. the number of undominated loser-preferrers (l=1) divided by the number of winner-preferrers (w=2).

1. (60)

   

7.2 An invariant for smallest non-calibrated promotion

The sum of the current RVs in (16b) is 155. The updated RVs in (60) add up to the same number. The fact that the sum of the current RVs remains constant is not a coincidence. In fact, the promotion component (59b) of the re-ranking rule adds the promotion amount l/w to the RV of each of the w winner-preferrers, so that the sum of the current RVs is increased by (l/w)×w=l overall. Furthermore, the demotion component (59a) subtracts the demotion amount 1 from the RV of each of the l loser-preferrers, so that the sum of the current RVs is decreased by 1×l=l overall. As the same quantity is added to and subtracted from the sum of the current RVs, the promotion and demotion components of the re-ranking rule balance each other, and the sum of the current RVs remains constant over time.

Unfortunately, Fact 4 entails that the strategy used in §6 to prove convergence for the case of calibrated promotion amounts does not extend to the case of the smallest non-calibrated promotion amount (59). T&S's lower bound on the sum of the current RVs holds for any re-ranking rule (as long as only undominated loser-preferrers are demoted), as stated in generalised Fact 2. If the sum of the current RVs decreases with each update (as in the case of demotion-only or calibrated promotion), then T&S's lower bound on the sum of the RVs straightforwardly translates into a bound on the number of possible updates. But if the sum of the current RVs does not decrease with each update, but rather stays constant, T&S's lower bound does not straightforwardly have anything to say about the number of updates. A more indirect reasoning is needed, illustrated in §7.4. This alternative analysis rests on another property of EDRAs discussed in §7.3, namely that they cannot loop.

7.3 EDRAs cannot loop

The sequence of ranking vectors entertained by a demotion-only EDRA cannot contain a sub-sequence such as (61), whereby the same ranking vector θ is entertained at two different times but with some other ranking vector θ′≠θ entertained at some time in between. The reason is straightforward. When moving from the ranking vector θ=(θ₁, …, θ_n) to a different ranking vector θ′=(θ′₁, …, θ′_n), at least one RV must have decreased from θ_k to some smaller value θ′_k. In order for the algorithm to go back from θ′ to θ, that RV would need to increase from θ′_k to its original value θ_k. This is impossible with a demotion-only re-ranking rule, as RVs can only decrease but not increase over time.

1. (61)

   

Thus demotion-only EDRAs cannot loop: once a ranking vector is deemed unsuitable, and is therefore updated, the algorithm can never consider it again in the same learning path. In other words, demotion-only EDRAs explore the search space in an effective way, as they avoid entertaining the same incorrect hypothesis twice.

This special property does not carry over from demotion-only to promotion/demotion EDRAs. A trivial counterexample is provided in (62). Start from a null initial ranking vector. Update in response to the ERC 1, according to the promotion/demotion re-ranking rule in (59). Then update again in response to the ERC 2. The algorithm has looped back to the initial null ranking vector.

1. (62)

   

The details of the re-ranking rule are irrelevant here. The point is that, as soon as we perform some constraint promotion, RVs can oscillate up and down, and in particular can return to values entertained earlier.

Yet the input ERC matrix (62a) used to get the EDRA to loop is inconsistent. What if we restrict ourselves to consistent ERC matrices? Fact 5 ensures that EDRAs cannot loop in this case, even if the re-ranking rule performs constraint promotion as well as demotion. Again, the details of the re-ranking rule do not matter, and the statement holds for any re-ranking rule of the form (46).Footnote ¹⁵

In the demotion-only case, the impossibility of loops follows trivially from the monotonicity of the ranking dynamics, and is thus independent of the properties of the input ERC matrix. In the promotion/demotion case, however, the impossibility of loops follows from a property of the input ERC matrix, namely its consistency. Understanding why promotion/demotion EDRAs cannot loop thus brings out an interesting and non-trivial property of the notion of OT-consistency. In particular, non-looping follows from a connection between OT-consistency and the geometric property of conic independence. The details of this reasoning can be found in Appendix C of the online supplementary materials.

7.4 Convergence

We are now able to prove convergence for the re-ranking rule in (59), with the smallest non-calibrated promotion amount. Recall first generalised Fact 2 from §6.2, which guarantees that T&S's lower bound on the current RVs holds for any re-ranking rule that demotes only the loser-preferrers which need to be demoted, i.e. the undominated ones. Thus, the current RVs in any run of the EDRA with the re-ranking rule (59) cannot become arbitrarily small, provided the input ERC matrix is consistent.

Can the current RVs get arbitrarily large? As seen is §5.2, this is precisely what happens when Boersma's GLA (40) is run on Pater's counterexample in (42): the RVs increase indefinitely. But this cannot happen in the case of (59). In fact, the RVs all start out null. As, by Fact 4, their sum must remain constant over time, the current RVs must always add up to zero. As they cannot become too small and must add up to zero, the current RVs cannot become too large either.

As the current RVs cannot become too large or too small, the current ranking vector must live in a bounded region. Each time a RV is updated, it is increased by 1, or by at least 1/n. This means in turn that the RVs entertained by the EDRA live on a grid of points, separated by at least 1/n from each other. As the search space of the algorithm consists of a bounded grid, it contains only a finite number of ranking vectors. Since the algorithm cannot loop by Fact 5, finiteness of the search space entails finite time convergence. We have thus proved the following convergence theorem.Footnote ¹⁶ For a very different proof, see Magri (to appear b).

7.5 Number of errors

T&S's convergence Theorem 1 for demotion-only EDRAs provides a (tight) bound on the worst-case number of errors. Theorem 2 extends T&S's analysis to calibrated promotion/demotion EDRAs, with a comparable bound on the worst-case number of errors. Unfortunately, that analysis does not extend to the case of the non-calibrated re-ranking rule (59) considered here. An alternative analysis thus had to be developed in order to prove the convergence Theorem 3. This alternative analysis does not provide a bound on the worst-case number of errors. This final section examines this issue, showing that the worst-case number of errors in the case of the non-calibrated re-ranking rule (59) grows exponentially with the number of constraints, so that efficiency is lost.

Following Riggle (Reference Riggle2009), let the diagonal matrix for n constraints be the ERC matrix with n columns and n−1 rows, whose kth row has all entries equal to e, except for the kth entry, which is a w, and the following entry, which is an l. To illustrate, I give in (63) the diagonal ERC matrices for n=4, 5, 6 constraints.

1. (63)

   

For diagonal matrices, a different line of analysis developed in Magri (to appear b) guarantees that the worst-case number of errors made by the EDRA with the non-calibrated re-ranking rule (59) is feasible (smaller than n(n ²−1)/6, where n is the number of constraints).

Pater (Reference Pater2008) considers ERC matrices obtained from the diagonal one by adding a w to the right of every l. More precisely, let Pater's matrix for n constraints be the ERC matrix with n columns and n−1 rows obtained from the diagonal matrix by ‘adding’ a w at the right of every l (except in the last row). The case with n=5 was considered in (42). To illustrate, I give in (64) Pater's matrices for n=4, 5, 6 constraints.

1. (64)

   

The extra w's added at the right of the diagonal in Pater's matrices do not contribute anything to consistency, in the sense that they do not enlarge the set of consistent rankings. They only serve the purpose of confounding re-ranking rules that perform constraint promotion and are thus sensitive to these w's. Indeed, Pater's extra layer of w's is able to fool the GLA, as observed in §5.3. But it is not able to fool the non-calibrated re-ranking rule in (59): the analysis developed in Magri (to appear b) guarantees again a feasible worst-case number of errors (smaller than n ⁵, where n is the number of constraints).

Let us try to further aggravate the learning challenge by adding yet another layer of useless w's. Let the Aggravated Pater's matrix for n constraints be the ERC matrix with n columns and n−1 rows obtained from the diagonal matrix by ‘adding’ two w's (rather than just one) at the right of every l (except for the penultimate row, where only one w is added, and the last row, where no w's are added). In (65) I give the aggravated Pater's matrices for n=4, 5, 6 constraints.

1. (65)

   

Theorem 3 guarantees that the EDRA with the non-calibrated re-ranking rule in (59) converges on aggravated Pater's matrices. Yet it turns out that convergence is not efficient: even in the best, shortest run, the algorithm makes far too many errors before it finally converges on a consistent ranking vector. In Appendix D of the online supplementary materials, I show how to compute the best-case number of mistakes made by the EDRA with rule (59) on aggravated Pater's matrices. The computation is analogous to the explanation provided in §5.3 for Pater's counterexample to the GLA's convergence. The best-case number of errors is provided in Table Ia for various choices of the number n of constraints. For instance, the EDRA will always perform no fewer than 107,920 updates before converging to a ranking vector consistent with the aggravated Pater's matrix corresponding to n=15 constraints.

Table I

(a) best-case number of errors performed by the EDRA with the smallest non-calibrated promotion amount (59), run on the aggravated Pater's matrix for n constraints; (b) value of 2ⁿ for corresponding values of n.

In Table Ib, I report the values of 2ⁿ for the corresponding values of n. The table thus shows that the best-case number of mistakes made by the EDRA with the re-ranking rule (59) on aggravated Pater's matrices grows exponentially with the number of constraints. In other words, the number of mistakes performed before reaching convergence grows so quickly with n that it is unfeasible even for a small number of constraints.

7.6 Summary

This section has studied re-ranking rule (59), which increases the promotion amount to the calibration threshold l/w, namely the ratio between the number l of undominated loser-preferrers and the number w of winner-preferrers. It has shown that convergence is retained in this case, but efficiency is lost: an exponential number of errors might be required before reaching convergence. This result is somewhat surprising. One might expect that, in order to bring down the number of errors from exponential to something feasible, the promotion amount would need to be exponentially reduced, so as to become practically useless from the modelling perspective of §4. This intuitively plausible conjecture turns out to be false. In fact, as seen in §6, it is sufficient to decrease the promotion amount just slightly, for example from l/w to l/(w+1), in order to obtain efficient convergence. This shows the importance of a thorough computational understanding of the algorithm when setting the implementation parameters of the model.