^April May – 2011

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).

Galperin and Wigderson proposed a succinct representation for graphs, that uses number of bits that is logarithmic in the number of nodes. They proved complexity results for various decision problems on graph properties, when the graph is given in a succinct representation. Later, Papadimitriou and Yannakakis showed, that under the same succinct encoding method, certain class of decision problems on graph properties becomes exponentially hard. We consider the complexity of the Permanent problem when the graph/matrix is given in a restrict succinct representation. We present an optical architecture that is based on the holographic concept for solving balanced inputs of the Succinct Permanent problem.

The talk will include both a theoretical results (relating establishing a computational complexity of some problems) and an optical implementation of the proposed algorithm.