CSE
CSE
CSE CSE


AI Seminar

Efficient Algorithms for Learning Combinatorial Structures from Limited Data

Asish Ghoshal


PhD graduate
Purdue University
 
Tuesday, May 21, 2019
1:00pm - 2:00pm
4901 BBB

Add to Google Calendar

About the Event

Recovering combinatorial structures from noisy observations is a recurrent problem in many application domains, including, but not limited to, natural language processing, computer vision, genetics, health care, and automation. For instance, dependency parsing in natural language processing entails recovering parse trees from sentences which are inherently ambiguous. From a computational standpoint, such problems are typically intractable and call for designing efficient approximation or randomized algorithms with provable guarantees. From a statistical standpoint, algorithms that recover the desired structure using an optimal number of samples are of paramount importance. This talk will introduce several such problems in the areas of causal inference, game theory and structured prediction, and present computationally and statistically efficient procedures for the same. Specifically, (i) I will present polynomial-time algorithms for learning linear structural equation models --- which are a widely used class of models for performing causal inference --- that recover the correct directed acyclic graph structure under identifiability conditions that are weaker than existing conditions. I will also show that the sample complexity of our method is information-theoretically optimal. (ii) I will present polynomial-time algorithms for learning the underlying graphical game from observations of the behavior of self-interested agents. The key combinatorial problem here is to recover the Nash equilibria set of the true game from behavioral data. I will present fundamental lower bounds on the number of samples required for learning games and show that our method is statistically optimal. (iii) Lastly, departing from the generative model framework, the talk will delve into the problem of structured prediction where the goal is to learn predictors from data that predict complex structured objects directly from a given input. I will present an efficient learning algorithm for learning structured predictors by approximating the partition function and obtain generalization guarantees for our method. I will demonstrate that randomization can not only improve efficiency but also generalization to unseen data.

Additional Information

Sponsor(s): Strategic Reasoning Group

Faculty Sponsor: Michael Wellman

Open to: Public

Web Page: http://asishghoshal.com/