BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Probabilistic programs and the computability and complexity of Bay
 esian reasoning - Daniel Roy\, University of Cambridge
DTSTART:20111101T140000Z
DTEND:20111101T150000Z
UID:TALK34332@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:When is Bayesian reasoning possible? and when is it efficient?
 \n\nThere has been a recent surge of interest in probabilistic programming
  languages and general-purpose inference engines. By providing languages f
 or specifying large\, modular\, potentially recursively-defined probabilis
 tic models\, these systems make it possible to tackle very complex inducti
 ve inference problems\, opening up new avenues for AI and applications. \n
 \nWe present recent results elucidating aspects of the theoretical underpi
 nnings of probabilistic programming systems\, especially those whose under
 lying probabilistic languages have\, in a technical sense\, the same expre
 ssive power as probabilistic Turing machines.  This algorithmic perspectiv
 e on probability distributions\, combined with new general purpose Monte C
 arlo inference strategies\, presents a host of challenges and opportunitie
 s for theoretical computer science.\n\nIn particular\, we investigate the 
 class of computable probability distributions---distributions for which th
 ere exists a probabilistic program for generating exact samples---and expl
 ore the fundamental limitations on performing Bayesian reasoning with prob
 abilistic program representations.  We ask\, when does a conditional distr
 ibution have such a representation and when can we compute it?  In additio
 n to highlighting some positive results demonstrating that Bayesian reason
 ing is possible when the prior distribution has additional structure such 
 as exchangeability or noise\, we prove the nonexistence of algorithms (eve
 n inefficient ones) for Bayesian reasoning in the general case.  We close 
 with some complexity-theoretic aspects.
LOCATION:Small public lecture room\, Microsoft Research Ltd\, 7 J J Thomso
 n Avenue (Off Madingley Road)\, Cambridge
END:VEVENT
END:VCALENDAR