Have you ever wondered why just about every sentence seems like a garden path sentence to parsers? For example in a sentence like "Pat loves cats and dogs," traditional parsers are likely to examine and then abandon the VP structure VP(V(loves) N(cats)) in favor of VP(V(loves) NP(cats and dogs)). This non-deterministic backtracking search process is ubiquitous in our conception of computational linguistics because of the entrenched role of Boolean logic formalisms in linguistics. In this talk, I will introduce an approach based on convex optimizations (i.e., finding the lowest part of bowl-like shapes), which is computationally efficient, deterministic, and has appealing probabilistic and linguistic interpretations.

In my thesis work on recognizing intonation I wanted to approximate an utterance pitch track with a set of connected broken lines. This problem, like parsing, is usually treated as a search problem. It is a difficult problem in that, for example, for 60 possible break locations, there will be 2^60 possible location combinations, the full examination of which would take over 36 million years at the rate of one thousand combinations per second. Just as in parsing, there are clever algorithms for reducing the search (e.g., equivalents of top-down and dynamic programming). I will visually explain an approach that replaces the difficult search with an easy convex optimization. Continuing the bowl analogy, this is like replacing a surface which is essentially bowl shaped but has many uneven parts, with a similar surface that is exactly bowl shaped. This approach is possible because of the inherent structure in utterance pitch tracks.

I suggest that natural language understanding problems also have inherent structure which can be exploited. I will re-cast parsing in a convex optimization framework and demonstrate how this approach scales gracefully to context-sensitive languages and to joint intonation and syntax parsing.