Research

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 tutorialcorrelation clusteringonline structured learningmeasure concentrationlearning with inverse optimizationentropy bounds and interactive annotationssampling from the Gibbs distribution using max-solverslearning with super-modular tasks and non-decomposable loss functionsthe 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