The VC Dimension of Constraint-Based Grammars
Jason Riggle, Morgan Sonderegger and I have posted a paper proving that the VC dimension of Harmonic Grammar is k+1 for k constraints, which is the same value as has been shown for Optimality Theory.
In this paper we analyze the complexity of Harmonic Grammar (HG), a linguistic model in which licit underlying form to surface form mappings are determined by optimization over weighted constraints. We show that the Vapnik-Chervonenkis Dimension of HG grammars with k constraints is k-1. This is the same as the VC dimension of Optimality Theory (OT), which is similar to HG, but uses ranked rather than weighted constraints in optimization. The parity of the VC dimension in these models is surprising because OT defines finite classes of languages — there are at most k! ways to rank k constraints — while HG defines infinite classes of languages. The linear growth of the VC dimension with the number of constraints has broad positive ramifications for the learnability of HG grammars.