

















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 firstorder 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 semisupervised 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 communityoverlap 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.


























Armen Allahverdyan, Greg Ver Steeg and Aram Galstyan, 2010. Community Detection With and Without Prior Information, in Euro Physics Letters 90, 18002, 2010.
Armen Allahverdyan and Aram Galstyan, 2010. On Maximum a Posteriori Estimation of Hidden Markov Processes, in 25th Conference on Uncertainty in Artificial Intelligence, 2009.













Aram Galstyan (PI) Greg Ver Steeg (Postdoc) 





 

