Robust Probabilistic Inference

Date

August 29, 2014

Overview

Probabilistic Inference is the task of given a certain set of observations, to deduce the probability of various outcomes. This is a very basic task both in statistics and in machine learning.

Robust probabilistic inference is an extension of probabilistic inference, where some of the observations are adversarially corrupted. Examples of where such a model may be relevant are spam detection, where spammers try adversarially to fool the spam detectors, or failure detection and correction, where the failure can be modeled as a “worse case” failure. The framework can be also used to model selection between a few alternative models that possibly generate the data.

Technically, we model robust probabilistic inference as a zero-sum game between an adversary, who can select a modification rule, and a predictor, who wants to accurately predict the state of nature. Our main result is an efficient near optimal algorithm for the robust probabilistic inference problem. More specifically, given a black-box access to a Bayesian inference in the classic (adversary-free) setting, our near optimal policy runs in polynomial time in the number of observations and the number of possible modification rules.

This is a joint work with Aviad Rubinstein and Moshe Tennenholtz.

Speakers

Yishay Mansour

Prof. Yishay Mansour got his PhD from MIT in 1990, following it he was a postdoctoral fellow in Harvard and a Research Staff Member in IBM T. J. Watson Research Center. Since 1992 he is at Tel-Aviv University, where he is currently a Professor of Computer Science and has serves as the head of the School of Computer Science during 2000-2002. Prof. Mansour has held visiting positions with Bell Labs, AT&T research Labs, IBM Research, and Google Research. Prof. Mansour has published over 50 journal papers and over 100 proceeding paper in various areas of computer science with special emphasis on communication networks machine learning, and algorithmic game theory. Prof. Mansour is currently an associate editor in a number of distinguished journals and has been on numerous conference program committees. He was both the program chair of COLT (1998) and served on the COLT steering committee. He has supervised over a dozen graduate students in various areas including communication networks, machine learning, algorithmic game theory and theory of computing.

People