Research interests
Perturbation models: Statistically reasoning about complex systems involves a probability distribution over exponentially many configurations. For example, semantic labeling of an image requires to infer a discrete label for each image pixel, hence resulting in possible segmentations which are exponential in the numbers of pixels. Standard approaches such as Gibbs sampling are slow in practice and cannot be applied to many real-life problems. However, In recent years novel combinatorial and primal-dual optimization methods were developed and in practice they successfully recover the most probable assignment in such problems. Our goal is to integrate these techniques to define new statistical framework for which sampling and parameter estimation in complex systems are efficient. This framework is based on measuring the stability of maximum a-posteriori prediction to random changes in the potential interactions.
Relevant materials: UAI 2014 tutorial, correlation clustering, online structured learning, measure concentration, learning with inverse optimization, entropy bounds and interactive annotations, sampling from the Gibbs distribution using max-solvers, learning with super-modular tasks and non-decomposable loss functions, the partition function and extreme value statistics.
max-solution | perturb-max samples |
Markov random fields, convex duality and message-passing: To efficiently predict outcomes in complex systems one can use graphical models and structured predictors. In this setting each predictor provides partial outcomes, e.g., the semantic labels of a region in an image, and global consistency for the structured prediction is maintained by passing messages between these regions. These concepts, emerging from Judea Pearl’s belief propagation algorithm, can be interpreted in terms of optimization theory. Applying Fenchel duality we develop the convex norm-product belief propagation, and its high-oder extensions, which enforce consistency between overlapping predictors using dual block coordinate descent. This provides us with the means to use cloud computing platforms to distribute and parallelize the prediction while maintaining consistency between its subproblems (code available, also for Amazon EC2). Estimating the parameters of region based predictors increase their accuracy in many real-life programs, and currently we achieve with these methods state-of-the-art results in various computer vision applications.
Machine learning applications: Our research is motivated by real life problems, mostly in computer vision but also in computational biology and language processing. For example, interactive annotation, correlation clustering, depth estimation, 3D scene understanding, protein reconstruction and speech recognition