Invited talk: Counting Rankings
Jason Riggle · Meeting of the Association for Computational Linguistics · 2008
In this talk, I present a recursive algorithm to calculate the number of rankings that are consistent with a set of data (optimal candidates) in the framework of Optimality Theory (OT; Prince and Smolensky 1993).1 Computing this quantity, which I call r-volume, makes possible a simple and effective Bayesian heuristic in learning – all else equal, choose candidates that are preferred by the highest number of rankings consistent with previous observations. This heuristic yields an r-volume learning algorithm (RVL) that is guaranteed to make fewer than k lg k errors while learning rankings of k constraints. This log-linear error bound is an improvement over the quadratic bound of Recursive Constraint Demotion (RCD; Tesar and Smolensky 1996) and it is within a logarithmic factor of the best possible mistake bound for any OT learning algorithm. Computing r-volume: The violations in an OT tableau can be given as a [n × k] array of integers in which the first row t1 corresponds to the winner. Following Prince (2002), the ranking information can be extracted by comparing t1 with each ‘losing’ row t2, ..., tn to create an Elementary Ranking Condition as follows: erc(t1, ti) = 〈α1, ..., αk〉 where αj = L if t1,j ti,j , and αj = e otherwise. The meaning of α is that at least one constraint associated with W dominates all those associated with L. input C1 C2 C3 candidate t1 * ** winner candidate t2 ** * erc(t1, t2) = 〈W, L, e 〉 i.e. t1 beats t2 if C1 outranks C2 candidate t3 ** erc(t1, t3) = 〈L, L, W〉 i.e. t1 beats t3 if C3 outranks C1 and C2 candidate t4 *** * erc(t1, t4) = 〈L, W, W〉 i.e. t1 beats t4 if C2 or C3 outranks C1 For a set E of length-k ERCs, E−wi denotes a set E′ derived from E by removing ERCs with W in column i and removing column i. r-vol ( Ek ) = ∑ 1≤i≤k ⎧⎨ ⎩ 0 if xi = L for any x ∈ E (k − 1)! if xi = W for all x ∈ E r (E − wi) otherwise Mistake bounds: To make predictions, RVL selects in each tableau the candidate that yields the highest r-volume when the ERCs that allow it to win are combined with E (the ERCs for past winners). To establish a mistake bound, assume that the RVL chooses candidate e when, in fact, candidate o was optimal according to the target ranking RT . Assuming e = o, the rankings that make o optimal must be half or fewer of the rankings consistent with E or else RVL would have chosen o. Because all rankings that make candidates other than o optimal will be eliminated once the ERCs for o are added to E, each error reduces the number of rankings consistent with all observed data by at least half and thus there can be no more than lg k! errors. Applications: The r-volume seems to encode ‘restrictiveness’ in a way similar to Tesar and Prince’s (1999) r-measure. As a factor in learning, it predicts typological frequency (cf. Bane and Riggle 2008) and priors other than the ‘flat’ distribution over rankings can easily be included to test models of ranking bias. More generally, this research suggests the concept of g-volume for any parameterized model of grammar. Full bibliography available on the Rutgers Optimality Archive (roa.rutgers.edu) with the paper Counting Rankings.