Mar 15, 2007:

Harmonic Grammar with linear programming

Christopher PottsUniversity of Massachusetts Amherst,
(work done with Joe Pater, Rajesh Bhatt and Michael Becker)

Constraint weighting systems might be extremely promising for linguistic analysis. But the process of finding weightings by hand is long, boring, and hard. This is a huge obstacle to fair assessment. We're here to make life easier. We show that constraint weighting (harmonic) grammars reduce to linear systems, which are solvable using computationally efficient optimization algorithms. We present and discuss our implementation of such an algorithm:

HaLP 2.0: http://web.linguist.umass.edu/~halp/

You upload an OTSoft file (perhaps enriched in a few ways). HaLP converts it into a linear system and solves it using the two-phase simplex method. The output is an HTML file displaying the minimal weighting if there is one, else a verdict of 'infeasible'. To date, the largest problem we have solved with HaLP has 30 constraints and 1000 tableau, each with 10 candidates.