Human Language as a Greedy Algorithm (2009)

Undergraduate: Mason Chua

Faculty Advisor: Randall Hendrick
Department: Mathematics

---

I have taken advantage of existing work in linguistics to create an algorithm that automatically generates natural sentences. The algorithm converts unordered sets of words into grammatically coherent phrases. It does this by treating words as if they were selective magnets: they attract certain other words. For example, "the" attracts a noun after it. The goal of this project is to tune the algorithm so that it is possible to define grammars of human languages, including English, by assigning the right attractions to each word.
From a linguistic standpoint, the algorithm provides a way to find out what linguistic phenomenons its computational processes predict. To start this investigation, I have defined some inputs to the algorithm and shown that they derive a nontrivial subset of English sentence structures. From an engineering standpoint, this algorithm is a step towards helping computer programs generate novel sentences. Automatic translators, for example, cannot simply list phrases in advance, because there are infinitely many possible phrases. Instead, they need a systematic way to generate the right word order to express something. By showing that this algorithm can derive a non-trivial set of English sentences, I have demonstrated its promise as a tool for performing this automatic sentence-generation.