A rough guide to the Aldous-Hoover representation theorem for exchangeable arrays

Add to your list(s) Download to your calendar using vCal

• Dr Daniel Roy (University of Cambridge)
• Thursday 17 May 2012, 14:00-15:30
• Engineering Department, CBL Room 438.

If you have a question about this talk, please contact Konstantina Palla.

Exchangeable arrays can be used to model networks, graphs, collaborative filtering, etc. That said, my goal will be to present the essential structure and ideas underlying Aldous’s proof of his representation theorem for exchangeable arrays. Disclaimer 1: no data or applications will be harmed in this presentation. Disclaimer 2: I wouldn’t expect anyone unfamiliar with the proof to get much out of this unless they pay close attention and ask questions frequently.

A sequence of random variables X1, X2, ..., is exchangeable if its distributions is invariant to permutation of any finite number of indices. A classic result by de Finetti says that such sequences are conditionally i.i.d.: informally, we can invent a random variable alpha, such that knowing the value of alpha, each element has a distribution that depends only on alpha and the elements are independent from each other. For binary sequences, one such alpha turns out to be the limiting ratio of 1’s in the sequence, and P(X1|alpha) is Bernoulli with probability alpha.

In 1981, David Aldous investigated arrays X_ij, (i,j = 1,2,...) of random variables whose distributions are invariant to permutations of the rows and permutations of the columns. This is an appropriate symmetry to have if the rows and columns represent, say, objects and, a priori, all objects are created equal (hence, the ordering of the rows and columns was arbitrary). In his paper “Representations for partially exchangeable arrays of random variables”, Aldous shows that RCE arrays have conditionally independent entries and, in particular, can be written in the form

X_ij = f(\alpha, \xi_i, \eta_j, \lambda_ij)

for some (measurable) function f and i.i.d. uniform random variables \alpha, \xi_i, \eta_j, \lambda_ij (i,j=1,2,...).

It may be a complete mystery how such a result could be proven. I’m hoping to give some insight into this by going through the proof and answering questions to the best of my ability. The paper is:

Representations for partially exchangeable arrays of random variables
David J. Aldous
Journal of Multivariate Analysis. Volume 11. Issue 4. 1981.
http://www.sciencedirect.com/science/article/pii/0047259X81900993

See also my marginalia:

http://danroy.org/marginalia/Marginalia_for_Noteworthy_Papers

This talk is part of the Machine Learning Reading Group @ CUED series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge University Engineering Department Talks
• Cambridge talks
• Centre for Smart Infrastructure & Construction
• Chris Davis' list
• Computational Continuum Mechanics Group Seminars
• Engineering Department, CBL Room 438
• Featured lists
• Guy Emerson's list
• Hanchen DaDaDash
• Inference Group Journal Clubs
• Inference Group Summary
• Information Engineering Division seminar list
• Interested Talks
• ML
• Machine Learning Reading Group
• Machine Learning Reading Group @ CUED
• Machine Learning Summary
• Quantum Matter Journal Club
• Required lists for MLG
• School of Technology
• Simon Baker's List
• TQS Journal Clubs
• Trust & Technology Initiative - interesting events
• bld31
• custom
• ndk22's list
• ob366-ai4er
• rp587
• yk373's list

Note that ex-directory lists are not shown.