<OT> New Posting: ROA-979

[roa at ruccs.rutgers.edu]

ROA 979-0608

The Complexity of Ranking Hypotheses in Optimality Theory

Jason Riggle <jriggle at uchicago.edu>

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


Abstract:
Given a constraint set with k constraints in the framework
of Optimality Theory (OT), what is its capacity as a classificati
on scheme for linguistic data? One useful measure of this
capacity is the size of the largest data set of which each
subset is consistent with a different grammar hypothesis.
This measure 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 Elementary Ranking Conditions
to show that the VCD of Optimality Theory with k constraints
is k-1. Analysis of OT in terms of the VCD establishes that
the complexity of OT is a well behaved function of k and
that the �hardness� of learning in OT is linear in k
for a variety of frameworks that employ probabilistic definitions
of learnability.

Comments: This cleaned-up version of the paper will appear in Computational Linguistics (sometime soon) and has benefited tremendously from the comments of two anonymous CL reviewers.
Keywords: Elementary Ranking Conditions, complexity
Areas: Computation,Formal Analysis,Learnability
Type: Journal Article

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