[Author Login]
Title:The complexity of hypotheses in Optimality Theory
Authors:Jason Riggle
Abstract:Given a constraint set with k constraints in the framework of Optimality Theory (OT; Prince and Smolensky 1993/2004), what is its capacity as a classification scheme for linguistic data? One useful measure of this capacity is the size of the largest data set (i.e. set of input-output pairs) of which each subset is consistent with a different grammar hypothesis. This metric is known as the Vapnik-Chervonenkis Dimension (VCD) and is a standard complexity measure for concept classes in computational learnability theory. In this work I use the three-valued logic of Prince’s (2002) Elementary Ranking Conditions to show that the VCD of OT with k constraints is k-1. This result establishes that the complexity of Optimality Theory is well behaved as a function of k and that the hardness of OT learning is linear in k for a variety of frameworks that employ probabilistic definitions of learnability.
Type:Paper/tech report
Area/Keywords:Phonology,Computation,Learnability,Formal Analysis
Article:Version 1