• Calendar

May 11, Wednesday
14:00 – 15:20

I discuss the syntactic-parsig problem: the automatic assignment of syntactic structure to sentences in natural language text, with a focus on parsing Hebrew, a language with rich morphology. Syntactic-parsing is an instance of a structured-prediction, a subfield of machine-learning concerned with learning to map complex inputs (like sentences) to complex outputs (like trees). I present the common framework for structured prediction, based on problem-decomposition and dynamic-programming, and show some cases in natural language where independence assumptions of that framework fail. I then present Easy-First parsing, a novel algorithm for syntactic parsing which is based on a different set of assumptions, and which makes it easy to incorporate a much richer feature sets than the dynamic-programming approach. The algorithm works by modeling the set of decisions made by constructing the output structure instead of directly modeling the structure itself. As a consequence, at each step the algorithm can observe partial structures and exploit rich contextual information to guide further decisions. The algorithm works in a greedy fashion by delegating the search to the training phase, making it particularly fast at inference time. I present results of experiments on Hebrew data sets indicating a parsing accuracy of up to 81.5%, a substantial improvement over other approaches. The method also works well for English, leading to state-of-the-art parsing results.

Structured prediction techniques have applications in other domains, I briefly report on application to computational biology (RNA structured prediction) where we also reach state-of-the-art results (joint work with Shay Zakov and Michal Ziv-Ukelson).