Practical methods for inferring meaningful structure in complex systems
Practical, meaningful, complex: pick any two. For instance, linear regression is practical and works for complex systems, but what do the results mean? Causality is certainly meaningful, but current approaches tend to only be practical for simple systems. Information theory provides meaningful measures of complex systems, but estimating high-dimensional probability distributions is usually impractical.
The most notable example of "meaningful structure" is causality, for which the standard approach is to do randomized interventions in multiple controlled experiments. Unfortunately, there are many situations where this is not possible. Advances in the formal study of causality have given us tools to deduce causal relationships from observations alone under certain (structural) assumptions. Unfortunately, the types of assumptions made are usually unsuitable for complex systems. What are the minimal reasonable assumptions we need to deduce causal relationships in complex systems?
My recent work has applied this perspective to the problem of understanding influence and information diffusion in social networks using two main approaches. First, the information-theoretic approach looks for predictive relationships between users' activities, without making any assumptions about what these behaviors may look like. The second approach is to construct statistical tests that work even in the presence of hidden variables. What are the minimal assumptions under which we can identify influence in social networks? Can we predict a user's future activity from the content or temporal pattern of their friends' activity? How can we effectively take into account contextual information, e.g. spatial and temporal, in a model-free way?
I received my PhD in physics from Caltech in June 2009 for research in quantum information theory. My research is informed by ideas from classical and quantum information theory and statistical physics. I am also involved in a quantum computing initiative at ISI.
Below are details of a few active research directions.
-
Information theoretic methods for learning:
- Influence in time series. Transfer entropy provides a powerful, general framework for discovering connections between variables. Unfortunately, it is rarely used for this purpose because of the difficulty of estimating probability densities. Recent advances in nonparametric entropy estimators allow us to side-step the density estimation problem to get at entropies directly. This allows us to estimate useful, higher-order entropies such as transfer entropy, which is a measure of how well one system helps us predict the future of another system. We have already applied this perspective successfully to discover influential relationships in social networks using timing of activity and content of tweets.
- Unsupervised learning. How can we use information theory to learn structure in complex systems? Work in progress considers the pitfalls of information-theoretic clustering and the possibilities for deep learning.
-
Bell inequalities for complex networks, or Statistical tests for hidden variables
- Generally, I would like to extend the notion in quantum physics of a test for hidden variables (the Bell inequalities, e.g.) to various hidden variable models in machine learning contexts (latent homophily being only one example). This differs from the typical computer science approaches. For instance, hypothesis testing generally considers a null hypothesis, an alternate hypothesis, and the relative likelihood. We take a hidden variable model as the null hypothesis and construct a test to rule it out altogether. The other approach taken is to assume hidden variables exist and then use some learning algorithm to find their most likely values. This approach gives you an answer but it doesn't tell you if you asked the wrong question! With Aram Galstyan.
- Many papers have differentiated influence and homophily on social networks, but Shalizi and Thomas have pointed out that latent homophily can not be distinguished from influence. We have shown how to lower bound the strength of causal effects in social networks.
- Mapping graph clustering to an Ising problem gives us a framework for asking several questions. When are clusters detectable? Is clustering always stable? Which prior information would affect these properties? With Aram Galstyan and Armen Allahverdyan.
- A new generation of quantum chips made by D-wave solve Ising problems using a quantum annealing process. Our work on clusters shows that not all Ising problems are created equal: there is a rich phase structure. How does this structure affect the quality of solutions achievable through quantum annealing?
Teaching
Aram Galstyan and I designed and taught CS 599, "Computation and physics" in Spring 2012.