BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Microsoft Research Machine Learning and Perception
Seminars
SUMMARY:Probabilistic programs and the computability and c
omplexity of Bayesian reasoning - Daniel Roy\, Uni
versity of Cambridge
DTSTART;TZID=Europe/London:20111101T140000
DTEND;TZID=Europe/London:20111101T150000
UID:TALK34332AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/34332
DESCRIPTION:When is Bayesian reasoning possible? and when is i
t efficient?\n\nThere has been a recent surge of i
nterest in probabilistic programming languages and
general-purpose inference engines. By providing l
anguages for specifying large\, modular\, potentia
lly recursively-defined probabilistic models\, the
se systems make it possible to tackle very complex
inductive inference problems\, opening up new ave
nues for AI and applications. \n\nWe present recen
t results elucidating aspects of the theoretical u
nderpinnings of probabilistic programming systems\
, especially those whose underlying probabilistic
languages have\, in a technical sense\, the same e
xpressive power as probabilistic Turing machines.
This algorithmic perspective on probability distr
ibutions\, combined with new general purpose Monte
Carlo inference strategies\, presents a host of c
hallenges and opportunities for theoretical comput
er science.\n\nIn particular\, we investigate the
class of computable probability distributions---di
stributions for which there exists a probabilistic
program for generating exact samples---and explor
e the fundamental limitations on performing Bayesi
an reasoning with probabilistic program representa
tions. We ask\, when does a conditional distribut
ion have such a representation and when can we com
pute it? In addition to highlighting some positiv
e results demonstrating that Bayesian reasoning is
possible when the prior distribution has addition
al structure such as exchangeability or noise\, we
prove the nonexistence of algorithms (even ineffi
cient ones) for Bayesian reasoning in the general
case. We close with some complexity-theoretic asp
ects.
LOCATION:Small public lecture room\, Microsoft Research Ltd
\, 7 J J Thomson Avenue (Off Madingley Road)\, Cam
bridge
CONTACT:Microsoft Research Cambridge Talks Admins
END:VEVENT
END:VCALENDAR