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:Machine Learning Reading Group @ CUED
SUMMARY:A rough guide to the Aldous-Hoover representation
theorem for exchangeable arrays - Dr Daniel Roy (U
niversity of Cambridge)
DTSTART;TZID=Europe/London:20120517T140000
DTEND;TZID=Europe/London:20120517T153000
UID:TALK37509AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/37509
DESCRIPTION:\nExchangeable arrays can be used to model network
s\, graphs\, collaborative filtering\, etc. That
said\, my goal will be to present the essential st
ructure and ideas underlying Aldous's proof of his
representation theorem for exchangeable arrays.
Disclaimer 1: no data or applications will be harm
ed in this presentation. Disclaimer 2: I wouldn't
expect anyone unfamiliar with the proof to get mu
ch out of this unless they pay close attention and
ask questions frequently.\n\nA sequence of random
variables X1\, X2\, ...\, is exchangeable if its
distributions is invariant to permutation of any f
inite number of indices. A classic result by de F
inetti says that such sequences are conditionally
i.i.d.: informally\, we can invent a random variab
le alpha\, such that knowing the value of alpha\,
each element has a distribution that depends only
on alpha and the elements are independent from eac
h other. For binary sequences\, one such alpha tur
ns out to be the limiting ratio of 1's in the sequ
ence\, and P(X1|alpha) is Bernoulli with probabili
ty alpha.\n\nIn 1981\, David Aldous investigated a
rrays X_ij\, (i\,j = 1\,2\,...) of random variable
s whose distributions are invariant to permutation
s of the rows and permutations of the columns. Th
is is an appropriate symmetry to have if the rows
and columns represent\, say\, objects and\, a prio
ri\, all objects are created equal (hence\, the or
dering of the rows and columns was arbitrary). In
his paper "Representations for partially exchange
able arrays of random variables"\, Aldous shows th
at RCE arrays have conditionally independent entri
es and\, in particular\, can be written in the for
m\n\n X_ij = f(\\alpha\, \\xi_i\, \\eta_j\, \\
lambda_ij)\n\nfor some (measurable) function f and
i.i.d. uniform random variables \\alpha\, \\xi_i\
, \\eta_j\, \\lambda_ij (i\,j=1\,2\,...).\n\nIt ma
y be a complete mystery how such a result could be
proven. I'm hoping to give some insight into thi
s by going through the proof and answering questio
ns to the best of my ability. The paper is:\n\n
Representations for partially exchangeable arra
ys of random variables\n David J. Aldous\n
Journal of Multivariate Analysis. Volume 11. Issu
e 4. 1981.\n http://www.sciencedirect.com/scie
nce/article/pii/0047259X81900993\n\nSee also my ma
rginalia:\n\n http://danroy.org/marginalia/Mar
ginalia_for_Noteworthy_Papers
LOCATION:Engineering Department\, CBL Room 438
CONTACT:Konstantina Palla
END:VEVENT
END:VCALENDAR