Colloquium 2009 Nov 13

In this work, I present a recursive algorithm for computing the number of rankings consistent with a set of optimal candidates in the framework of Optimality Theory, a quantity that I call the r-volume. I identify two related areas where this metric is useful. First, the ability to measure r- volume makes possible a simple and effective Bayesian strategy in learning -- all else equal, choose candidates preferred by the highest number of constraint rankings consistent with previous observations. Learners using this strategy are guaranteed to make no more than than k log k erroneous predictions while learning rankings of k constraints. This log-linear bound on mistakes is an improvement over Recursive Constraint Demotion's quadratic mistake bound and is within a logarithmic factor of the best possible mistake bound for any ranking algorithm. The second area where r-volume appears to be useful is in modeling typology and free variation. This is supported by recent case studies in which r-volumes are significantly correlated with the frequency with which patterns are attested in free variation and typologically.