Spring 2010

ABSTRACT: Machine learning is a confluence of computer science and statistics that is empowering technologies such as search engines, robotics, and personalized medicine. Fundamentally, the goal of machine learning is to develop computer programs that predict well, according to some measure of risk or accuracy. The predictions should get better as more historical data become available. The field is developing interesting and useful frameworks for building such programs, which often demand large computational resources. Theoretical analyses are also being advanced to help understand the tradeoffs between computation, data, and risk that are inherent in statistical learning. Two types of results have been studied: the consistency and scaling behavior of specific convex optimization procedures, which have polynomial computational efficiency, and lower bounds on any statistically efficient procedure, without regard to computational cost. This talk will give a survey of some of these developments, with a focus on structured learning problems for graphs and shared learning tasks in high dimensions.

ABSTRACT: A vast amount of text and speech data is now available in electronic form, making methods that recover structure in this data increasingly important. In this talk I’ll describe work on machine learning approaches for the analysis of natural language. The central question addressed in the talk will be the following: how can we design statistical models, and associated learning algorithms, that operate over rich linguistic representations? As examples of work in this area, I will describe models for syntax (parsing), semantics (mapping sentences to underlying representations of their meaning) and machine translation. While the focus of this talk will be on language, many of the techniques I will describe are applicable to machine learning problems in other fields, for example speech recognition, computer vision, and computational biology.

ABSTRACT: Complex phenomena such as animal morphology, human motion, and large fluid systems challenge even our most so- phisticated simulation and control techniques. My overarching research goal has been to develop fundamentally new methods to approach such high-dimensional and nonlinear problems. This talk presents my work solving these problems across a wide range of phenomena, including a new model-reduction approach to fluids that is orders-of-magnitude faster than standard simulation methods and enables interactive high- resolution fluid simulation for the first time. Another example is a continuum approach to crowd dynamics which efficiently reproduces empirical aspects of large crowd behavior that would be difficult or impossible to achieve with traditional agent models. The talk will also cover work on several other phenomena in- cluding human animation, animal morphology, and protein folding. Such new algorithmic approaches advance not only our ability to simulate and control complex systems but also our understanding of the systems themselves.

ABSTRACT: Digital doubles have not only evolved into prevalent elements of motion pictures and games, but are also finding an ever growing application base including medical diagnostics, surgical planning and design of vehicles and crafts. At the same time, current and developing applications demand improved photorealism, enhanced biomechanical accuracy, better subject-specificity and faster simulation algorithms. As these demands often outgrow the evolution of computer hardware, new algorithms for biomechanical modeling andsimulation are necessary to ensure that upcoming computational platforms are utilized to the best of their capacity. Additionally, biomechanical simulation has provided a great opportunity for transformative advances in medical practice using virtual models of the human body for disease prevention and treatment. These emerging applications mandate an increased level of attention to the unique demands of subject-specificity and anatomical accuracy for clinical uses of biomechanical modeling and simulation. This talk will outline a number of techniques that were designed to facilitate modeling and simulation of digital doubles with high fidelity and efficiency. Finally, I will discuss the cross-cutting impact of such advances on character animation, scientific computing and virtual surgery.

ABSTRACT: In the past decade, models and approaches from Game Theory and Economics have been widely applied in the study of large-scale competitive environments such as the Internet and e-commerce. The concept of equilibria, i.e., that of stable states, serves as one of the key tools in such studies, and its computation has attracted great attention. In this talk, we will focus on the problem of computing equilibria in two of the most fundamental models of competitions in Game Theory and Economics: games and markets. Both problems have a long intellectual history. In 1950, Nash showed that every game has an equilibrium. In 1954, Arrow and Debreu showed that under very mild conditions, every market has an equilibrium. While games and Nash equilibria are used to predict the behavior of selfish agents in conflicting situations, the study of markets and market equilibria laid down the foundation of competitive pricing. Other than the fact that both existence proofs heavily rely on fixed point theorems, the two models look very different from each other. In this talk, we will review the recent characterizations of how difficult it is to compute or to approximate Nash equilibria in two-player games. We will then show that these results also significantly advanced our understanding about equilibria in the market setting.

ABSTRACT: Extracting the full economic and scientific value of the “data deluge”, which follows from the information produced and consumed online by individuals, is redefining the frontier of computer science. Five years after one of the first experiments on mobile social dynamics, the size and scope of data collected or accessed through mobile devices have increased dramatically. In this talk, it is argued that understanding and releasing the potential of mobile social networks is possible provided that three key challenges are addressed: the lack of a guiding theory, the need to design algorithms exploiting social properties, and the presence of entities with competing goals. Although these broad challenges are likely to exist for some time, this talk presents three examples in which these issues are addressed, using new analytical and algorithmic tools, to improve the efficiency of information dissemination.