Seminar: NIPS previews

SpeakerStephen Pasteris, Wittawat Jitkrittum, Ricardo Silver
DateFriday, 04 Dec 2015
Time13:00 - 14:00
LocationRoberts G08 (Sir David Davies lecture theatre)
Event seriesMicrosoft Research CSML Seminar Series

Talk 1: Stephen Pasteris will present

Online Prediction at the Limit of Zero Temperature

by Mark Herbster and Stephen Pasteris


We design an online algorithm to classify the vertices of a graph. Underpinning the algorithm is the probability distribution of an Ising model isomorphic to the graph. Each classification is based on predicting the label with maximum marginal probability in the limit of zero-temperature with respect to the labels and vertices seen so far. Computing these classifications is unfortunately based on a #P- complete problem. This motivates us to develop an algorithm for which we give a sequential guarantee in the online mistake bound framework. Our algorithm is optimal when the graph is a tree matching the prior results in [?]. For a general graph, the algorithm exploits the additional connectivity over a tree to provide a per-cluster bound. The algorithm is efficient, as the cumulative time to sequen- tially predict all of the vertices of the graph is quadratic in the size of the graph.

Talk 2: Wittawat Jitkrittum will present

Bayesian Manifold Learning: The Locally Linear Latent Variable Model


Mijung Park, Wittawat Jitkrittum, Ahmad Qamar, Zoltan Szabo, Lars Buesing, Maneesh Sahani

Abstract: We introduce the Locally Linear Latent Variable Model (LL-LVM), a probabilistic model for non-linear manifold discovery that describes a joint distribution over observations, their manifold coordinates and locally linear maps conditioned on a set of neighbourhood relationships. The model allows straightforward variational optimisation of the posterior distribution on coordinates and locally linear maps from the latent space to the observation space given the data. Thus, the LL-LVM encapsulates the local-geometry preserving intuitions that underlie non-probabilistic methods such as locally linear embedding
(LLE). Its probabilistic semantics make it easy to evaluate the quality of hypothesised neighbourhood relationships, select the intrinsic dimensionality of the manifold, construct out-of-sample extensions and to combine the manifold model with additional probabilistic models that capture the structure of coordinates within the manifold.

Talk 3: Ricardo Silver will present

Bandits with Unobserved Confounders: A Causal Approach


Elias Bareinboim
Andrew Forney
Judea Pearl

The Multi-Armed Bandit problem constitutes an archetypal setting for sequential
decision-making, permeating multiple domains including engineering, business,
and medicine. One of the hallmarks of a bandit setting is the agent’s capacity
to explore its environment through active intervention, which contrasts with the
ability to collect passive data by estimating associational relationships between
actions and payouts. The existence of unobserved confounders, namely unmea-
sured variables affecting both the action and the outcome variables, implies that
these two data-collection modes will in general not coincide. In this paper, we
show that formalizing this distinction has conceptual and algorithmic implications
to the bandit setting. The current generation of bandit algorithms implicitly try to
maximize rewards based on estimation of the experimental distribution, which
we show is not always the best strategy to pursue. Indeed, to achieve low regret
in certain realistic classes of bandit problems (namely, in the face of unobserved
confounders), both experimental and observational quantities are required by the
rational agent. After this realization, we propose an optimization metric (employ-
ing both experimental and observational distributions) that bandit agents should
pursue, and illustrate its benefits over traditional algorithms.

iCalendar csml_id_246.ics