2.1 Convergence and efficiency

Assume that the learner is provided with the space of grammars G₁, G₂, etc. The learner maintains a current grammar, which represents its current hypothesis on the target adult grammar. Data come in a stream. Whenever the current grammar (say G₁) makes an error on the current piece of data (say datum 1), it is updated to a slightly different one (say G₂). The current piece of data is then discarded, and the learner waits for the next piece of data to evaluate the performance of the updated grammar, as in Fig. 1.

Figure 1

Schematic representation of error-driven learning.

This learning scheme is called error-driven because the learning dynamics are driven by the errors made on the incoming stream of data. This scheme has been thoroughly investigated in the machine learning literature (under the heading of online learning; for reviews, see Kivinen Reference Kivinen, Mendelson and Smola2003, Cesa-Bianchi & Lugosi Reference Cesa-Bianchi and Lugosi2006: chs 11, 12 and Mohri et al. Reference Mohri, Rostamizadeh and Talwalkar2012: ch. 7). Within the language-acquisition literature, this learning scheme has been endorsed at least since Wexler & Culicover (Reference Wexler and Culicover1980), for two reasons. First, an error-driven learner describes a sequence of grammars in the typological space which provides a tool to model child acquisition paths. Second, an error-driven learner does not keep track of previously seen data: the current piece of data is compared with the current grammar and then discarded.Footnote ² It is thus perfectly suited to model the early stages of language acquisition prior to the development of the native language lexicon, such as the early acquisition of phonotactics (Hayes Reference Hayes2004).

The most basic question of the computational theory of error-driven learning concerns convergence: is it possible to guarantee that the learner makes only a finite number of errors? Convergence is crucial, because it entails that the learner eventually settles on a final grammar which will never be further updated and thus counts as the grammar learned by the algorithm. Of course, there is little difference between the number of errors being infinite and it being finite but astronomically large. The next crucial question of the computational theory of error-driven learning thus concerns efficiency: is the number of errors not only finite but also small enough that the final grammar is efficiently converged on? Of course, the number of errors made by the learner should be allowed to grow with the complexity of the learning task. In constraint-based phonology, the simplest measure of complexity is the number of phonological constraints. Thus the number of errors is ‘small’ (and the learner efficient) provided it grows slowly (polynomially) with the number of constraints.

2.2 Stochastic tolerance

The implementation of error-driven learning schematised in Fig. 1 is called deterministic, to distinguish it from the stochastic implementation (Boersma Reference Boersma1997, Reference Boersma1998, Boersma & Hayes Reference Boersma and Hayes2001, Coetzee & Pater Reference Coetzee and Pater2008, Reference Coetzee, Pater, Goldsmith, Riggle and Yu2011, Coetzee & Kawahara Reference Coetzee and Kawahara2013, Jarosz Reference Jarosz2013, Boersma & Pater Reference Boersma, Pater, McCarthy and Pater2016) schematised in Fig. 2. The latter differs because the current piece of data (say datum 1) is compared not with the current grammar (say G₁), but with a variant thereof (say G′₁), sampled from the neighbourhood of the current grammar (shown as a circle centred at G₁).

Figure 2

Schematic representation of stochastic error-driven learning.

Assume that the stochastic error-driven learner is trained on a sequence of data generated by some (deterministic) target grammar.Footnote ³ In the worst-case scenario, the stochastic learner can make more errors than the deterministic learner, because the stochastic component can derail the learner from the most straightforward learning path (the simulations reported in §5 will show that to indeed be the case). The worst-case number of errors made by a stochastic learner can thus be expressed as the sum of two terms, as in (1). The first is the worst-case number of errors made by the deterministic learner, which measures the difficulty of error-driven learning. The second is the worst-case number of additional errors made by the stochastic learner, which measures the slow-down due to the stochastic implementation.

1. (1)

   

The next question for the theory of error-driven learning concerns its tolerance of the stochastic component: is the number of additional errors due to the stochastic implementation (the second term on the right-hand side of (1)) small enough not to disrupt efficiency? Again, this number of additional errors should be allowed to grow with the complexity of the learning task, measured as the number of constraints. Thus the number of additional errors is ‘small’ (and the learner tolerant of the stochastic component) provided it grows slowly (polynomially) with the number of constraints.Footnote ⁴

2.3 Noise robustness

So far, I have assumed that the learner is trained on a stream of pristine data generated by some target grammar in the typology. A more realistic learning setting needs instead to allow for the possibility that a small portion of the training data could have been corrupted by transmission noise or speech errors (Gibson & Wexler Reference Gibson and Wexler1994, Frank & Kapur Reference Frank and Kapur1996, Boersma & Hayes Reference Boersma and Hayes2001, Bíró Reference Bíró2006). I schematise this more realistic noisy setting as in Fig. 3, where the data not located on the dotted line (such as datum 2) are meant to be corrupted by noise and thus inconsistent with the rest of the pristine data.

Figure 3

Schematic representation of error-driven learning in a noisy setting.

Suppose that the (possibly infinite) sequence of pristine training data is interspersed with a finite amount of data corrupted by noise. No assumptions are made on the corrupted data apart from there being only a finite number.Footnote ⁵ The corrupted data make the learning problem harder (Magri Reference Magri2013a: §2), and might thus force the learner to make more errors. In other words, the number of errors made by the learner on a possibly corrupted training sequence can be expressed as the sum of two terms, as in (2). The first term is the number of errors which would have been made on the sequence of pristine data with the corrupted data removed, and the second is the number of additional errors due to the corrupted data.

1. (2)

   

The final question for the theory of error-driven learning concerns its robustness to noise: is the number of additional errors due to the corrupted data small enough not to disrupt efficiency? Again, the number of additional errors should be allowed to grow with the complexity of the learning task, measured as the number of constraints (as well as, of course, the number of pieces of corrupted data and the size of the faulty updates they cause). Thus the number is ‘small’ (and the learner robust to noise) provided it grows slowly (polynomially) with the number of constraints.

2.4 Constraint-dependent and independent perspectives

Tesar (Reference Tesar2013: 18) summarises the core tenet of generative linguistics as follows: ‘for language learning to be possible, the linguistic theory must have some kind of non-trivial structure … that can be exploited by a learner’. What type of non-trivial structure yields guarantees for convergence, efficiency, stochastic tolerance and noise robustness of error-driven learning? Within constraint-based phonology, ‘phonological theory contains two parts: a theory of substantive universals of phonological well-formedness and a theory of formal universals of constraint interaction’ (Prince & Smolensky Reference Prince and Smolensky2004: 80). Correspondingly, computational guarantees for error-driven learning can be developed from either of two perspectives (Tesar & Smolensky Reference Tesar and Smolensky2000: §1.2). The constraint-independent perspective derives computational guarantees from the formal properties of the mode of constraint interaction alone (e.g. the logic of transitive orders in the case of OT or the linear algebra underlying HG). It does not make any substantive assumptions on the phonological content of the constraints. The constraint-dependent perspective instead derives computational guarantees from the additional structure brought about through substantive restrictions on the phonological content of the constraints.Footnote ⁶ It is standard practice in the literature to adopt the constraint-independent perspective as the starting point, and to resort to the alternative constraint-dependent perspective only when the former fails. For instance, Eisner (Reference Eisner, Eisner, Karttunen and Thériault2000: 23) writes: ‘The algorithms for learning … are designed to be general for any [constraint set] … That is, these methods are not tailored (as others might be) to exploit the structure of some specific, putatively universal [constraint set]’. The main reason for the privileged status accorded to the constraint-independent perspective is that, when it succeeds, it yields stronger results, namely computational guarantees that hold for a completely arbitrary constraint set. It thus circumvents the contentious issue of characterising phonologically plausible constraint sets, and it ensures that the computational theory won't have to be revised whenever new phonological data are uncovered or better analyses developed.

2.5 Summary

The computational theory of error-driven learning in constraint-based phonology outlined in this section is summarised in Fig. 4. The theory aims at computational guarantees for convergence, efficiency, stochastic tolerance and noise robustness, corresponding to the four rows. It adopts a constraint-independent or dependent perspective, corresponding to the two columns. The horizontal arrows encode the privileged status accorded to the constraint-independent perspective: they say that a constraint-dependent question (in the right column) is tackled only when the corresponding constraint-independent question (in the left column) has been answered negatively. The vertical arrows encode additional dependencies among the eight questions. For instance, it only makes sense to investigate efficiency (i.e. whether the number of errors is small) if convergence has been established (i.e. the number of errors is finite), as encoded by the two arrows between questions (a) and (b) and between (e) and (f). Furthermore, it only makes sense to investigate stochastic tolerance and noise robustness for a certain constraint set after efficiency has been established for that constraint set, as encoded with the two arrows between question (f) and questions (g) and (h). In fact, a learner which is inefficient in its deterministic implementation and in a noise-free setting is useless to start with. On the other hand, even if efficiency fails from the ambitious constraint-independent perspective, it could still be the case that the number of additional errors in (1) and (2) due to the stochastic implementation or the noisy data remains small for any constraint set. There is therefore no arrow relating question (b) to (c) and (d).

Figure 4

Structure of the computational theory of error-driven learning in constraint-based phonology.

3.1 Algorithmic core

The HG typology of grammars is parameterised with a weight vector θ  = (θ ₁, θ ₂, …), which assigns a weight θ _k to each constraint C _k . The OT typology is parameterised with a constraint ranking. A ranking can be represented numerically with a ranking vector θ  = (θ ₁, θ ₂, …), which assigns a ranking value θ _k to each constraint C _k : a constraint is ranked above another constraint whenever the ranking value of the former is larger than the ranking value of the latter (Boersma Reference Boersma1997, Reference Boersma1998, Reference Boersma2009). The error-driven learning scheme sketched in Fig. 1 can then be formalised as in Fig. 5 within either HG and OT. The learner maintains a current vector θ of weights or ranking values. For concreteness, I assume that its components are initially set all equal to zero. The current vector θ is then updated by looping through steps (a)–(c). At step (a), the learner receives the current piece of data. At step (b), it checks whether the OT or HG grammar corresponding to the current vector θ is consistent with that piece of data. If that is the case, the learner has nothing to learn from the current piece of data, loops back to step (a) and waits for more data. Otherwise, the learner updates the current vector θ at step (c) and then loops back to step (a) and starts all over again. The rest of this section describes steps (a)–(c).

Figure 5

Algorithmic core of error-driven learning in HG and OT.

3.2 Data

At step (a) in Fig. 5, the learner receives a piece of data. At a minimum, this piece of data consists of a surface form y, say some form which is licit according to the phonotactics corresponding to the target grammar the learner is being trained on. In some applications, the corresponding underlying form x can be assumed to be provided as well. In other applications, the learner instead needs to be endowed with an additional subroutine to reconstruct the underlying form (e.g. set the current underlying form x identical to the current surface form y; Hayes Reference Hayes2004, Prince & Tesar Reference Prince and Tesar2004, Magri Reference Magriforthcoming). Since this paper abstracts away from the proper definition of this subroutine, the underlying form is assumed to be provided along with the surface form at step (a). The mapping (x, y) of the underlying form x to the surface form y must beat the mapping (x, ƶ) of x to any other loser candidate ƶ (I adopt the convention of striking out loser candidates). The learner thus needs to focus on one such loser candidate. Usually, this loser candidate is chosen through a proper subroutine. This paper also abstracts away from the proper definition of this subroutine. The loser form is thus assumed to be provided along with the underlying and winner forms at step (a). In the end, the piece of data fed to the learner at step (a) consists of an underlying/winner/loser triplet (x, y, ƶ).

3.3 Update conditions

At step (b) in Fig. 5, the error-driven learner checks whether the HG or OT grammar corresponding to the current weight or ranking vector θ  = (θ ₁, θ ₂, …) is consistent with the current underlying/winner/loser form triplet (x, y, ƶ), i.e. whether it makes the current winner y beat the current loser ƶ for the underlying form x. In the case of HG, this consistency condition is (3). The violation difference corresponding to constraint C _k is the difference between the number of violations C _k (x, ƶ) it assigns to the loser ƶ minus the number of violations C _k (x, y) it assigns to the winner y. Condition (3) thus requires the average of the constraint-violation differences weighted by the weights θ _k to be strictly positive.

1. (3)

   

In the case of OT, the consistency condition checked at step (b) is (4). This condition requires the highest-ranking value among the winner-preferring constraints in W (i.e. those constraints which have a positive violation difference, assigning fewer violations to the intended winner than to the intended loser) to be larger than the highest-ranking value among the loser-preferring constraints in L (those constraints which have a negative violation difference, assigning more violations to the intended winner than to the intended loser).Footnote ⁷

1. (4)

   

Conditions (3) and (4) will be referred to as the HG and OT update conditions, as the learner performs an update only in case these conditions fail. Note that neither update condition depends on the actual number of constraint violations, but only on the constraint-violation differences.

3.4 Update rules

At step (c) in Fig. 5, the error-driven learner updates the current weight or ranking vector in case the corresponding grammar has failed on the current piece of data. In the case of HG, the literature has adopted the perceptron (or ‘delta’) update rule in (5) (Coetzee & Pater Reference Coetzee and Pater2008, Reference Coetzee, Pater, Goldsmith, Riggle and Yu2011, Jesney & Tessier Reference Jesney and Tessier2011, Coetzee & Kawahara Reference Coetzee and Kawahara2013, Boersma & Pater Reference Boersma, Pater, McCarthy and Pater2016). If a constraint C _k is winner-preferring (or loser-preferring), its violation difference C _k (x, ƶ) − C _k (x, y) is positive (or negative), so that its weight is increased (or decreased) by (5). I refer to the algorithm in Fig. 5 with the HG update condition in (3) at step (b) and the reweighting rule in (5) at step (c) as the (perceptron) HG error-driven learning algorithm.Footnote ⁸

1. (5)

   

Despite its wide use in the current HG literature, this perceptron update rule runs into the following problem. Constraints express penalties in constraint-based phonology, never rewards (Keller Reference Keller2000, Legendre et al. Reference Legendre, Sorace and Smolensky2006). Constraint weights must therefore be required to be non-negative in order for HG to avoid undesired typological predictions. Yet the perceptron reweighting rule in (5) does not in any way guarantee non-negativity of the current and final weights entertained by the learner. A natural strategy to overcome this problem is to resort to the variant in (6), which truncates the updates at zero (Boersma & van Leussen Reference Boersma and van Leussen2014: §5, Magri Reference Magri2015, Boersma & Pater Reference Boersma, Pater, McCarthy and Pater2016: 19). The algorithm in Fig. 5 with the HG update condition (3) at step (b) and this new reweighting rule (6) at step (c) can be called the truncated perceptron HG learner.

1. (6)

   

Turning to OT, the generic reranking rule used by the error-driven learner at step (c) in Fig. 5 is given in (7). The promotion component (7a) of the reranking rule promotes the winner-preferring constraints by a promotion amount which is equal to the inverse of the number w of winner-preferring constraints scaled by a constant c (Magri Reference Magri2012b). This constant, used to calibrate the promotion amount on the number of winner-preferring constraints, can be zero (in which case the learner performs no constraint promotion) or positive. In the rest of the paper, I will assume that c is larger than zero, so that the reranking rule performs both constraint demotion and promotion and thus comes closer to the reweighting rule (5)/(6) used by the HG learner. To illustrate, if c = 1/2 (this is the choice used in the simulations reported in the rest of the paper; see Appendix E) and there are three winner-preferring constraints, each will be promoted by c/w = 1/6.

1. (7)

   

The demotion component (7b) of the reranking rule demotes by a fixed amount (say 1) those loser-preferring constraints that really need to be demoted, namely those that are not currently ranked underneath a winner-preferring constraint, and are therefore undominated (Tesar & Smolensky Reference Tesar and Smolensky1998). The algorithm in Fig. 5 with the update condition (4) at step (b) and the reranking rule (7) at step (c) is a (calibrated and gradual) OT error-driven ranking algorithm. Note that both the HG reweighting rules and the OT reranking rule do not depend on the actual number of constraint violations, but only on the constraint-violation differences.

3.5 Stochastic implementation

At step (b) in Fig. 5, the deterministic error-driven learner checks the update condition (3) or (4) for HG and OT respectively. The only innovation of the stochastic implementation sketched in Fig. 2 is that the update condition is checked not for the current weights or ranking values θ ₁, θ ₂, …, but for their stochastic counterpart θ ₁+ε ₁, θ ₂+ε ₂, …, where ε ₁, ε ₂, … are sampled independently from each other. The algorithm in Fig. 5 with this stochastic update condition at step (b) is called the OT/HG stochastic error-driven learner (Boersma Reference Boersma1997, Reference Boersma1998).Footnote ⁹ The stochastic values εk are usually sampled according to a Gaussian distribution, with zero mean and small variance. Since the tails of the Gaussian distribution decrease exponentially fast, these stochastic values are bounded with high probability between some thresholds −Δ and +Δ. From an analytical perspective, it is nonetheless convenient to assume they are deterministically bounded, i.e. sampled according to a distribution concentrated between −Δ and +Δ. The analyses carry over with high probability to the Gaussian distribution (Magri & Storme Reference Magri and Stormeforthcoming).Footnote ¹⁰

4.1 A counterexample for the truncated perceptron

Prince & Smolensky (Reference Prince and Smolensky2004: §10.2.2) put forward a simple counterexample to HG error-driven learning.Footnote ¹¹ The counterexample is shown in (8a) for an arbitrary number n of constraints and illustrated in (8b) for n=5.

1. (8)

   

The n constraints C₁, C₂, …, C _n are listed at the top of the matrix in (8). The learner is trained on n−1 underlying/winner/loser form triplets (x, y, ƶ _i ), corresponding to a single underlying form x, the winner candidate y, and n−1 loser candidates ƶ ₁ , ƶ ₂ , …, ƶ _n−1. Since the update conditions and update rules described in §3 only depend on the constraint-violation differences, the counterexample is described by providing these violation differences for each constraint and each triplet (for readability, null violation differences are represented with empty entries). Thus the diagonal of entries equal to 1 in (8) shows that constraint C _k assigns one more violation to the loser ƶ _k than to the winner y. The diagonal of entries equal to −2 shows that constraint C _k+1 assigns two more violations to the winner y than to the loser ƶ _k . All other violation differences are null.

For concreteness, I focus on the case in (8b), with five constraints. The bottom row of the matrix requires the weight of constraint C₄ to be more than twice as large as the weight of C₅. The penultimate row requires the weight of C₃ to be more than twice as large than the weight of C₄ and thus more than 2² = 4 times as large as the weight of C₅. And so on until the top row, which requires the weight of C₁ to be more than 2⁴ = 16 times as large as the weight of C₅. In other words, the weight of C₁ starts as null, and has to climb to a final value 2 ⁿ⁻¹, which grows exponentially in the number of constraints. Yet the weights are incremented only by 1 with each update, since the positive violation differences in (8) are all equal to 1. We thus expect that a number of updates exponential in n is needed in order to converge to a final weight vector which assigns a sufficiently large weight to constraint C₁.

This prediction is borne out in the case of the HG error-driven learner with the truncated perceptron reweighting rule in (6). I ran this learner ten times on the counterexample in (8), with the number n of constraints between five and ten (see Appendix E: Table III for simulation results). The solid line in Fig. 6a plots the largest number of errors made by the HG learner over the ten runs as a function of the number of constraints.Footnote ¹² Comparison with the function 162×4 ⁿ⁻⁵ plotted by the dashed line shows that the number of errors grows fast (exponentially) with the number of constraints.Footnote ¹³ Indeed, the number of errors grows so fast that the learner makes more than 180,000 errors in the case with ten constraints. The solid line in Fig. 6b plots the final weight of constraint C₁ (which is constant across the ten runs) as a function of the number of constraints. Comparison with the function 15×2 ⁿ⁻⁵ plotted by the dashed line shows that this final weight grows fast (exponentially) with the number of constraints, as predicted by Prince & Smolensky's reasoning. The counterexample in (8) thus shows that no constraint-independent guarantees are possible for the efficiency of the HG error-driven learner with the truncated perceptron reweighting rule. Any such guarantees will have to be restricted through specific assumptions on the constraint set.

Figure 6

Simulation results for the truncated perceptron on counterexample (8).

Yet this counterexample does not defeat the HG learner with the original perceptron reweighting rule in (5). Indeed, that learner converges after only n−1 updates; thus nine updates suffice in the case with ten constraints (see Appendix E: Table V for simulation results). The final weights do not depend on the number of constraints, and are small: the final weight of constraint C₁ is always equal to 1, the final weight of constraint C _n is always equal to −2, and the other final weights are all equal to −1. By resorting to negative weights, the original perceptron thus defies Prince & Smolensky's challenge. How should we interpret the original and truncated perceptrons’ drastically different performances on the counterexample in (8)? Does it show that the two learners have substantially different properties and that HG's assumption of non-negative weights is particularly troublesome from a learnability perspective? Or is it possible to twist the counterexample to extend it to the original perceptron reweighting rule, thus showing that the two implementations are on a par? The latter turns out to be the case.

4.2 A counterexample to both the original and the truncated perceptron

Consider the counterexample described in (9a) for an arbitrary number of constraints and illustrated in (9b) for the case with five constraints. There are two differences in comparison with the counterexample considered in §4.1 (see §4.3.4 and §4.3.5 for discussion). The first difference is that each negative entry is followed by two positive entries equal to 1, except for the penultimate row (where we can fit only one positive entry after the negative entry) and the last row (where we can fit none). Thus all rows have three positive entries, apart from the penultimate row (which has only two positive entries) and the last row (which has only one). The second difference is that the size of the negative entries is readjusted, so that it is equal to the number of positive entries per row. Thus the negative entry of each row is −3, apart from the penultimate row (whose negative entry is −2) and the last row (whose negative entry is −1).

1. (9)

   

The solid lines in Fig. 7a plot the largest number of errors made by the HG error-driven learner with the two reweighting rules (5) and (6) over ten runs on the counterexample in (9) corresponding to a number of constraints between five and ten (see Appendix E: Tables VI, VII for simulation results). Comparison with the function 550 × 6 ⁿ⁻⁵ plotted by the dashed line shows that the number of errors grows fast (exponentially) with the number of constraints for both reweighting rules. Indeed, the HG learner with the original perception reweighting rule makes over five million errors in the case with just ten constraints, and over six million with the truncated rule. The solid line in Fig. 7b plots the final weight of constraint C₁ in the longest of the ten runs as a function of the number of constraints. Comparison with the function 19 × 2.5 ⁿ⁻⁵ plotted by the dashed line shows that this final weight again grows fast (exponentially) with the number of constraints.

Figure 7

Simulation results for the original and truncated perceptron on counterexample (9).

I conclude that the counterexample in (9) shows that no constraint-independent efficiency guarantees are possible in the case of the HG error-driven learner, independently of the issue of non-negative weights and thus of the choice between the original and the truncated perceptron reweighting rule. Any efficiency guarantees will have to be restricted through specific assumptions on the constraint set. §4.3 discusses the counterexample in (9).

4.3 Discussion

4.3.1 The margin

The HG error-driven learner with the perceptron reweighting rule (5) converges (Boersma & Pater Reference Boersma, Pater, McCarthy and Pater2016, building on guarantees for the perceptron algorithm: Rosenblatt Reference Rosenblatt1958, Reference Rosenblatt1962, Block Reference Block1962, Novikoff Reference Novikoff1962, Minsky & Papert Reference Minsky and Papert1969, Cristianini & Shawe-Taylor Reference Cristianini and Shawe-Taylor2000: Theorem 2.3, Cesa-Bianchi & Lugosi Reference Cesa-Bianchi and Lugosi2006: ch. 12, Mohri et al. Reference Mohri, Rostamizadeh and Talwalkar2012: ch. 7). Whenever this HG learner is trained on data consistent with some HG grammar and with bounded violation differences, it can only make a finite number of errors, which can be bounded as in (10), in terms of the number of constraints and a quantity that captures a property of the training data, namely their margin (of separability).Footnote ¹⁴

1. (10)

   

The precise definition of the margin (of separability) which appears in the denominator of the error-bound is somewhat involved, and therefore relegated to Appendix A. The following intuitive illustration suffices for the rest of the paper. The error-bound holds under the assumption that the training data are consistent with some HG grammar. Yet consistent training data can differ in their degree of consistency. The data have a high degree of consistency if they are consistent with a certain HG grammar, and remain consistent when the corresponding weight vector is tampered with. The data have a low degree of consistency if even a slight modification of any consistent weight vector affects consistency. The margin which appears in the denominator of (10) can be interpreted as the degree of consistency of the training data. Intuitively, training data with a large degree of consistency should require fewer updates: it should be easier to find a consistent weight vector. While training data with a small degree of consistency should require more updates: a careful aim is required to target a consistent weight vector precisely. The error-bound in (10) formalises this intuition: training data with a high degree of consistency have a large margin, yielding a small error-bound in (10), which provides guarantees for a better performance by the HG learner, and vice versa for training data with a low degree of consistency.

As the number of constraints grows, the constraint interactions can become more subtle and delicate, and the freedom in the choice of the weights thus decreases, shrinking the degree of consistency of the data, namely their margin. If the margin in the denominator of (10) shrinks fast (exponentially) with the number of constraints, it trumps the slow (linear) growth of the numerator. The overall error-bound thus grows fast (exponentially) and provides no guarantees on the efficiency of the HG learner. This is precisely what happens in the case of counterexample (9) – analogous considerations hold for the original counterexample in (8). The inverse of the squared margin is plotted by the black circles in Fig. 8, as computed in Appendix B. Comparison with the function 400×6 ⁿ⁻⁵ plotted by the dashed line shows that it grows fast (exponentially) with the number of constraints.

Figure 8

Squared inverse margin of separation of the data corresponding to counterexample (9).

In conclusion, the error-bound in (10) settles question (a) in Fig. 4, concerning constraint-independent convergence of the HG perceptron learner. But because of its dependence on the margin, that bound does not settle question (b), concerning constraint-independent efficiency. That question is answered negatively by counterexamples such as the one in §4.2, which shows that constraint-independent efficiency guarantees are impossible.

These considerations extend from the original to the truncated perceptron reweighting rule in (6). To illustrate the intuition, suppose that at a certain iteration the original perceptron demotes the weight of some constraint C _k from 0 to the forbidden negative value −1. The truncated perceptron is unable to mimic that demotion and will thus leave the weight of C _k at 0. Yet the learning dynamics of the two algorithms can be realigned by assuming that, immediately after that offending demotion, the original perceptron is fed with a piece of dummy data whose constraint-violation differences are all null, apart from the one corresponding to C _k , which is +1. Since the current weight of C _k is negative, the original perceptron will perform an update in response to this piece of dummy data. This update promotes the weight of C _k back to the value 0, where the truncated perceptron had left it. A formalisation of this reasoning (Magri Reference Magri2015) shows that the error-bound in (10) for the original perceptron extends to the truncated variant, only with the margin of the training data replaced by the margin of the training + dummy data, as in (11).

1. (11)

   

The inverse of the squared margin of the training + dummy data in the case of counterexample (9) is plotted by the grey squares in Fig. 8. Again, it grows fast (exponentially) in the number of constraints, so that the error-bound in (11) for the truncated perceptron HG learner only guarantees constraint-independent convergence, not efficiency.

Extending the training data with additional data can only decrease the degree of consistency, namely the margin. Thus, the margin of the training data extended with the dummy data which appears in the error-bound in (11) for the truncated perceptron should be equal to or smaller than the margin of just the original data which appears in the error-bound in (10) for the original perceptron. The gap between the two solid lines in Fig. 8 quantifies the difference between the two margins in this case. Thus, the error-bound in (11) for the truncated perceptron is worse than (i.e. at least as large as) the error-bound in (10) for the original perceptron. Indeed, the truncated perceptron performs more errors in the simulations plotted in Fig. 7a. The difference between the two margins quantifies the price that needs to be paid for HG's assumption of non-negative weights.

4.3.2 Comparison with OT

The solid line in Fig. 9 plots the largest number of errors made by the OT learner over ten runs on counterexample (9) corresponding to a number of constraints between five and ten (see Appendix E for simulation details, in particular Table VIII for results). Comparison with the function n2 plotted by the dashed line shows that the number of errors grows slowly (subquadratically) with the number of constraints, so that the learner makes fewer than fifty errors in the case with ten constraints.Footnote ¹⁵

Figure 9

Simulation results for the OT learner on counterexample (9).

These simulation results are not surprising. In fact, suppose that the OT learner does not promote ‘too much’, i.e. it adopts a promotion component (7a) corresponding to a calibration constant c which is not ‘too large’, i.e. strictly smaller than 1. Whenever trained on data consistent with some OT grammar, this OT learner converges, and the number of errors is bounded by (12), in terms of the number of constraints and the calibration constant c used in the definition of the promotion amount (Boersma Reference Boersma1997: 323–327, Reference Boersma2009, Tesar & Smolensky Reference Tesar and Smolensky1998, Magri Reference Magri2012a, b).

1. (12)

   

This error-bound depends on the number of constraints only through its numerator. Thus it grows slowly (quadratically) in the number of constraints. Furthermore, this error-bound requires no assumptions on the constraints. In conclusion, this error-bound provides a positive answer to questions (a) and (b) in Fig. 4 concerning constraint-independent efficient convergence of the deterministic OT error-driven learner.

4.3.6 The HG learner is slow even on the most favourable training sequence

The solid lines in Fig. 7 plot the largest number of errors made by the HG learner over ten runs on the counterexample (9). These simulation results leave open the possibility that there exist some particularly favourable sequences of training data where the learner manages to converge after a smaller number of errors. Such a scenario would leave open the possibility of constraint-independent efficiency guarantees, through proper restrictive assumptions on the training sequences. However, this possibility can be ruled out as well. Appendix D shows how to compute analytically a lower bound on the best-case number of errors made by the HG perceptron learner: it guarantees that the number of errors needed to reach convergence can never be smaller than a certain quantity, even on the most favourable training sequence.Footnote ¹⁸ This lower bound on the best-case number of errors is plotted by the solid line in Fig. 10 as a function of the number of constraints between five and ten. Comparison with the function 400 × 6.3 ⁿ⁻⁵ plotted by the dashed line shows that also the best-case number of errors on the counterexample grows fast (exponentially) with the number of constraints. Furthermore, comparison with the actual number of errors plotted in Fig. 7 shows that the very large number of actual errors in the simulations is very close to the best-case number of errors, and thus cannot be due to particularly unfavourable learning sequences.

Figure 10

Best-case number of errors of the original perceptron on counterexample (9).

4.4 Summary

This section has compared the OT and HG implementations of error-driven learning from the perspective of constraint-independent efficiency: how fast does the worst-case number of errors grow with the number of constraints? The error-bound for the OT implementation grows slowly with the number of constraints and thus provides constraint-independent efficiency guarantees. The error-bound for the HG implementation instead depends on the margin, and can therefore grow fast with the number of constraints. It is indeed possible to construct cases where the HG and OT typologies coincide, and yet the HG learner makes over five million errors with just ten constraints, which compares poorly with the fewer than fifty errors made by the OT learner. These simulation results show that no constraint-independent efficiency guarantees are possible for the HG learner.

5.1 A counterexample for the original and truncated perceptron

Consider again the counterexample in (9). For each value of the number of constraints between five and ten, I ran the deterministic and stochastic HG learner ten times, with both the original and the truncated perceptron reweighting rule (see Appendix E for simulation details and in particular Tables VI and VII for results). The two solid lines in Fig. 11a plot the difference between the largest number of errors made by the stochastic learner with the two reweighting rules over the ten runs minus the number of errors made by the deterministic learner on that same training sequence. In other words, they plot the additional number of errors due to the stochastic component. Comparison with the function 166×6 ⁿ⁻⁵ plotted by the dashed line shows that the number of additional errors grows fast (exponentially) with the number of constraints. Indeed, in the case with just ten constraints, the stochastic learner performs almost one and a half million additional errors compared with the deterministic learner, which in turn is already performing over five million errors. For completeness, the solid lines in Fig. 11b plot the difference between the final weight of constraint C₁ entertained by the stochastic learner with the two reweighting rules at the end of the longest run minus the final weight of C₁ entertained by the deterministic learner at the end of that same run. In other words, they plot the increase in the final weight of constraint C₁ due to the stochastic component. Comparison with the function 8 × 2.3 ⁿ⁻⁵ plotted by the dashed line shows that the increase grows fast (exponentially) with the number of constraints.

Figure 11

Simulation results for the stochastic original and truncated perceptron on counterexample (9).

In conclusion, this counterexample shows that it is not possible to develop constraint-independent guarantees that the HG error-driven learner (with either reweighting rule) tolerates the stochastic implementation, namely that the number of additional errors due to the stochastic component remains small. Any such guarantees will crucially have to be restricted by specific assumptions on the constraint set.

5.2 Discussion

5.2.2 Comparison with OT

The solid line in Fig. 12 plots the difference between the largest number of errors made by the stochastic OT learner over ten runs on counterexample (9) minus the number of errors made in that same run by the deterministic learner (see Appendix E: Table VIII for simulation results). Comparison with the function 5×n ² plotted by the dashed line shows that the number of additional errors due to the stochastic component grows slowly with the number of constraints, so that the learner makes fewer than 200 additional errors in the case with ten constraints.Footnote ²⁰

Figure 12

Simulation results for the stochastic OT learner on counterexample (9).

These simulation results are not surprising. In fact, assume that the stochastic OT learner does not promote ‘too much’, i.e. adopts a promotion component (7a) corresponding to a calibration constant which is not ‘too large’ (strictly smaller than 1). Whenever it is trained on data consistent with an OT grammar, the number of errors is bounded by (17), which depends on the number of constraints and on the calibration constant c (Magri Reference Magri2016).Footnote ²¹

1. (17)

   

This error-bound in (17) is the sum of two terms. The first term coincides with the error-bound in (12) for the deterministic implementation. The second term thus expresses the number of additional errors due to the stochastic implementation. This additional term grows slowly (quadratically) with the number of constraints. Furthermore, the bound requires no assumptions on the constraints. It thus settles question (c) in Fig. 4 concerning constraint-independent guarantees that the OT learner tolerates the stochastic component.

5.3 Summary

§4 compared the OT and HG deterministic implementations of error-driven learning. This section has extended the comparison to the stochastic implementations. It has focused on the number of additional errors made by the learner because of the stochastic component. The error-bound for the OT stochastic learner provides constraint-independent guarantees that it tolerates the stochastic component. The constraint-independent bound currently available for the HG stochastic learner instead does not guarantee stochastic tolerance, because of its dependence on the margin of the data. Indeed, the HG learner does not tolerate the stochastic implementation constraint-independently: with just ten constraints, the stochastic HG learner can make almost one and a half million additional errors.

6.1 A counterexample for the original and truncated perceptron

Faulty updates triggered by corrupted data disrupt the current weights or ranking values and thus require additional updates by pristine data to recover. The learner is robust to noise provided the number of updates it takes to recover is small. To estimate noise robustness, we need to inflict the largest damage with each single corrupted piece of data. For concreteness, I focus on the HG learner with the truncated reweighting rule (the reasoning extends straightforwardly to the original perceptron reweighting rule). Consider again counterexample (9). Table I reports the final weights learned at the end of a run on the counterexample corresponding to a number of constraints between five and ten.

Table I

Final weights learned by the truncated perceptron on counterexample (9).

In §4, we focused on constraint C₁ and the fact that its final weight grows exponentially with the number of constraints. We now focus instead on the last two constraints, C _n−1 and C _n . Table I shows that their weights always differ by just one at convergence. We can take advantage of this fact as follows. Let's train the learner on pristine data sampled from counterexample (9) until it converges to the final weights in Table I. At that point, we feed the learner just one corrupted piece of data such as (18): the violation difference corresponding to C₁ is −1; the violation difference corresponding to the penultimate constraint, C _n−1, is +1; the violation difference corresponding to the last constraint, C _n , is +2; all other violation differences are null.

1. (18)

   

Since the violation difference corresponding to C₁ is negative in (18) and the weight of C₁ is very large in Table I, this corrupted piece of data is inconsistent with the weights in Table I, which are therefore updated to the weights in Table II, where the updated weights are given in bold. Because of the careful choice of the violation difference corresponding to the last two constraints, C _n−1 and C _n , they end up with the same weight, 2, in Table II. Consistency with the pristine training data in (9) requires the weight of C _n−1 to be larger than the weight of C _n . In order to recover the consistent weight configuration, the bottom row of counterexample (9) has to trigger an update. That update will promote C _n−1 by 1, to weight 3. But constraints C _n−2 and C _n−1 will then have exactly the same weight, 3. Consistency with the pristine training data requires the weight of C _n−2 to be larger than the weight of C _n−1. As this reasoning can be repeated backward for all the constraints, we predict a domino effect.

Table II

Weights entertained by the truncated perceptron after the update triggered by the corrupted piece of data in (18).

Indeed, the solid line in Fig. 13 plots the largest number of errors made by the HG learner (with the truncated perceptron reweighting rule) over ten runs on counterexample (9), starting from the weights in Table II (see Appendix E: Table XI for simulation results). Comparison with the function 40×4 ⁿ⁻⁵ plotted by the dashed line shows that the number of updates needed to recover from just a single small faulty update grows fast (exponentially) with the number of constraints, so fast that the learner requires over 64,000 updates in the case with just ten constraints, despite the weights in Table I and Table II before and after the faulty update being so similar.

Figure 13

Simulation results for the truncated perceptron in the noisy setting on counterexample (9).

In conclusion, this counterexample shows that constraint-independent guarantees of noise robustness for the HG error-driven learner are impossible, as a single faulty update can require a large number of updates to recover. Any such guarantees will have to be restricted by specific assumptions on the constraints.

6.2 Discussion

6.3 Summary

§4 and §5 compared the OT and HG implementations of error-driven learning in the noise-free setting. This section has extended the comparison to the noisy learning setting. It has focused on the number of additional errors made by the learner to recover from the faulty updates triggered by corrupted training data. The OT learner comes with a bound on the number of additional errors which provides constraint-independent guarantees on its noise robustness. The constraint-independent bound currently available for the HG learner instead does not guarantee noise robustness, because of its dependence on the margin of the data. Indeed, the HG learner is not noise robust constraint-independently: with just ten constraints, the HG learner can make more than 64,000 additional updates to recover from a faulty update triggered by a single piece of corrupted data.