StatMech - Statistical Mechanics of Inference and Learning
Many problems in machine learning can be framed as reconstructing a process or a structure based on some noisy observations. For instance, in object tracking one is interested in inferring object's trajectory based on noisy observations of its spatial location. In social network analysis, one is interested in inferring the underlying social structure based on the pattern of interactions between individuals. Despite apparent differences, those problems share some common underlying theoretical issues. One such issue is whether there are fundamental limits on one's ability to infer such processes/structures. It is natural to expect that the quality of inference should degrade with increasing noise levels. What is less trivial, however, is whether and under what circumstances the deterioration is gradual, and when it undergoes drastic changes, indicating instabilities.
We have addressed the above problem using methods from statistical mechanics. In a recent UAI paper, we presented a theoretical analysis of Maximum a Posteriori (MAP) sequence estimation for binary symmetric hidden Markov processes, by reducing it to an appropriately defined Ising spin model. It was shown that MAP is characterized by different operational regimes, which are different thermodynamic phases of the Ising model that are related to each other via first-order phase transitions. Specifically, there is a critical noise intensity above which MAP produces exponential number of solutions to the estimation problem.
As another example, we have studied the problem of community detection in networks, a topic that has attracted a lot of recent attention. In particular, we have examined the impact of prior information in community detection, by assuming that for a fraction the nodes their true cluster assignments are known in advance. This can be understood as a semi-supervised version of community detection, in contrast to unsupervised detection where the only available information is the graph structure. In the unsupervised case, it is known that there is a threshold of the community-overlap beyond which communities cannot be detected. We have demonstrated that any generic amount of prior information, however small, destroys the critical nature of the inference, and shifts the community detection threshold its lowest possible value. This reiterates the value of prior information in such inference tasks.
Modeling Complex Networks
Networks are inherently complex dynamical systems, where both attributes of individuals (nodes) and topology of the network (links) can have inter-coupled dynamics. For instance, it is known that social networks tend to divide into groups, or communities, of like-minded individuals. One can ask whether individuals become likeminded because they are connected via the network, or whether they form network connections
To model the interplay between influence and selction, we have developed a computational models of co-evolving networks based on interacting Hidden Markov Processes. The idea behind this approach is that he network is shaped by the interaction of local dynamical processes unfolding on individual nodes, while those processes themselves are influenced by the changing network structure. This provides a feedback mechanism that is vital for capturing realistic behavior of complex real-world network.
Another model of co-evolving dynamics is based on agents involved in game theoretical interactions. Specifically, we consider network-augmented multi-agent systems where, at each time step, agents choose which neighbor to play with, and which strategy to choose. As agents play repeatedly with each other, they will adapt their behavior by reinforcing (penalizing) both links and strategies that provide good (bad) outcomes. Thus, the reinforcment affects both the strategy and network