I’m happy to unveil a new paper, “A sequence of relaxations constraining hidden variable models”.

Depending on your interests, I’m including two different overviews. One comes from the social networks perspective and the other from the quantum physics perspective. Fundamentally, they are both about detecting hidden variables.

I’ll be giving a plenary talk about this paper at UAI 2011. So if you like hidden variables and you like Barcelona, come see me there!

[Update: Best paper runner-up!]

Quantum perspective

When people like Einstein realized that quantum physics predicts that the outcomes of some experiments are uncertain, he, logically, concluded that the theory is incomplete. There must be some hidden variable that would allow you to predict the outcome perfectly. “God does not play dice.”

On the other hand, Bell’s theorem provides a remarkable retort to this view. Bell showed that there is a limit to how strongly correlated two particles can be if the following assumptions are true:

1) Free will. (We are able to freely choose between two incompatible measurements.)

2) No faster than light signaling. (My choice of measurement on one particle is not instantly transmitted to the other particle.)

3) Hidden variables. (This hidden variable would perfectly predict the outcome of my experiment, regardless of which distant measurements were chosen.)

These assumptions limit how strongly correlated two particles can be. “Entangled” particles in quantum physics go beyond this limit and therefore violate at least one of these assumptions. Einstein called this “spooky action at a distance”.

One amazing thing about Bell’s test is that it made no assumption on what kind of “local hidden variables” were allowed. Despite this, he was able to find a test that conclusively rules them out as an explanation. My paper is, essentially, about how we can easily find tests for hidden variables in other contexts. (The answer: finding the best test can be hard, but we can find good tests using semidefinite relaxations.)

Social networks perspective

You may remember a recent study in the news that said “obesity is contagious“. You may have wondered if it is really possible to show such a thing. Cosma Shalizi wondered the same thing (paper here)and showed that the answer is, generally, no. You can always find an equally good explanation without invoking contagion or influence, that attributes correlations to some hidden variable. For instance, there is some hidden attribute of Alice and Bob that causes them to become friends, and also predisposes them to becoming obese.

How much correlation on a social network can be attributed to these “hidden variable theories”? If these properties are true:

1) No influence

2) Hidden variables (Each person’s actions depend only on their previous actions and the hidden variable.)

3) Stationarity (The hidden variable does not change with time.)

Then we can derive a limit to how correlated two people’s actions can be. Violation of this limit implies either that some influence is involved, or that the hidden variable is changing in time.

Intuitively, imagine I flip a coin and I start calling out the results: “Heads, Heads, Tails, Heads…”. Now, my friend Ditto starts calling out shortly thereafter: “Heads, Heads, Tails, Heads…”. At some point we can be fairly convinced I’m influencing Ditto. The paper just quantifies when we can do this and how confident we can be!

My ISI web page got moved to a new framework, so it could get integrated with our group web page more easily.

After several hours of work, the result is marginally better looking than my old web page.

I’m giving a talk at USC on May 20 for the quantum information and condensed matter physics seminar. It will be about phase transitions in the graph partitioning problem along with wild speculation about the implications for adiabatic quantum computation.

I’m also going to the International Conference on Complex Systems this summer, talking about the partitioning problem but without the wild speculation.

I should hear back from UAI soon about my paper on using semidefinite relaxations to create statistical tests for hidden variables. After I hear back, I’ll post the paper on arxiv along with an explanation here.

That conference (UAI) is in Barcelona this summer. I already mentioned I’ll be at ICWSM, and also at another workshop about the “Future of Social Web”.

It will be a busy summer!

The last Big Bang Theory episode was about information diffusion in social networks. The science consultant for the show asked my colleague Kristina Lerman to write about the topic for the Big Bang Theory blog. She mentions our recent paper (previous post). Unfortunately, although she gave the science consultant some of our graphs to put in the show, none of them were in the final cut.  I never thought I’d do research of interest to popular culture!

I have a new revision available on arxiv of the paper What stops social epidemics? I’ll be presenting the paper at ICWSM 2011 in Barcelona.

How likely is it for a virus or piece of information to spread through a network? If, on average, each person spreads the virus to more than one person than the virus will propagate through the entire network, an epidemic. If, on the other hand, each person spreads it to less than one person, the outbreak will die out very quickly, most likely after a handful of people have seen it.

For social epidemics on the Digg network, neither of these things happened. Stories would spread to a few hundred friends in the network, then stop without reaching even 0.1% of the whole network. There are many reasons for the slow-down of epidemics, but we identified two crucial, complementary ingredients.

• Most people who are exposed to a story are exposed by multiple friends
• More friends exposing you to a story does not make you more likely to spread the story yourself

Why does this slow down the epidemic? The first (primary) story spreader exposes some number of new people. Some fraction of those people are interested and spread the story themselves. If the people following these new (secondary) spreaders were a new, totally random group of people that looked just like the one the first spreader had, the story would merrily keep spreading. This kind of assumption is, roughly, a “mean field approximation”. But that’s not what happens. Instead, many of the friends of the secondary spreaders were already exposed by the primary spreader. Those people didn’t spread the story after one exposure, and they will continue to ignore it now. Fewer new people are reached in each round of spreading until the story dies out with a whimper.

A lovely day at the Huntington.

I had posters in two sessions:

Machine learning for social computing

and

Networks across disciplines

I got some great feedback and actually managed to understand a few talks. One interesting thing that I saw a few presentations about involved decomposing a matrix as a sum of a low rank and a sparse matrix. This can be cast as everybody’s favorite thing, and SDP! And it seems a very intuitive approach towards noisy data. I’d also like to read up about some nice posters I saw on efficient MMSBs and structure learning structure for sparse graphical models.

I almost missed my wordpress domain mapping expiring, I guess that’s what happens when you never blog.

What has happened since March? Oh, we bought a house and moved. More friends got their PhDs and moved on. My sister got married. Lots of fun summer stuff in LA. I got rid of my car, got a scooter, and am a week or two away from getting my motorcycle license.

I’m still enjoying research at ISI, but I should really write about that on my even more neglected ISI web page.

I still haven’t done any updating. But I saw a great talk at the ISI retreat about maintaining your research web page. Bibbase automatically converts bibtex files into awesome dynamical web code.

My digital self needs a real facelift.

I’m sort of annoyed that any institution specific research web page vanishes when you leave. Therefore I’m considering either keeping all research related notes on this website or on my nascent academia.edu web page.

In the past year, I finished my PhD in physics at Caltech, did a brief stint at Google, and am now doing research as a postdoc at the Information Science Institute. Somewhere in there I got married, and visited my wife’s family in India.