<OT> New Posting: ROA-888

[roa at ruccs.rutgers.edu]

ROA 888-1206

The complexity of hypotheses in Optimality Theory

Jason Riggle <jriggle at uchicago.edu>

Direct link: http://roa.rutgers.edu/view.php3?roa=888


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.

Comments: 
Keywords: complexity, Elementary Ranking Conditions, probabilistic learning
Areas: Phonology,Computation,Learnability,Formal Analysis
Type: Manuscript

Direct link: http://roa.rutgers.edu/view.php3?roa=888