Counting rankings
Jason Riggle · 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). 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.