Competitive grammar...

[trochee]

Today's [ed -- monday's] project was bizarre, but entertaining. We were asked to work in teams to compete to write grammars of English, that were scored against each other.



Each team wrote a context-free-grammar from a fixed-vocabulary of English, and assigned probabilities to each expansion. Then each sentence generated (and ranked as grammatical by blinded judges) was piped through each grammar, and the grammar that assigned the highest combined entropy was the victor.

My team came in dead last. I know too much about the linguistics, and we didn't scope the project work properly. By the time they announce "five minutes to begin the competition" we had uncovered the massive holes in our ideas and just barely managed to add enough rules to assign non-zero probabilities to all possible sentences.

Sadly, our grammar was not successful in generating many sentences.

I've never played competitive grammar building before. I want a copy of the harness code for my computational linguistics students...

Comments

Crikey!

[lx.livejournal.com]

Sounds fascinating!

How did you notate/enter the rules in this context-free-grammar? Or is the answer over my non-linguistics-studying head? :) And what kind of harness code was involved?

Re: Crikey!

[trochee.livejournal.com]

I hope it's not too late to answer this question... I've had kinda poor internet access, despite this being a computer language conference.

The rules looked like this (sorta):

1   S     NP VP

1   NP    ProperName
1   NP    Det NBar

1   NBar  Adj NBar
1   NBar  N

1   VP    VTrans NP
1   VP    VIntrans

1   VTrans   kiss
1   VTrans   smite
1   VTrans   carry

1   VIntrans rise
1   VIntrans fall

1   Adj      red
1   Adj      blue
1   Adj      heavy

1   ProperName Arthur
1   ProperName Gwen

1   Det      a
1   Det      an
1   Det      the

1   N        sparrow
1   N        coconut
1   N        wind

The first column indicates relative weight (likelihood in text generation, score in parsing), the second column indicates the symbol.

The harness code was made up of two things:

1. a parser that, given a sentence, searched this grammar for the highest "weight" sentence
2. a generator that began at the S token and randomly selected expansions ("randomly" being "according to their proportional weight").

I doubt that programmers would find this part challenging -- the hard part was trying to write a CFG for English.