Loose Notions

An interesting talk abstract from Anna Goldenberg at CMU. Some of the corresponding publications are online.

Bayesian Networks have been successfully applied in many areas such as pharmaceutical, decision making by doctors, air control, marketing. Structural learning of Bayesian Networks is usually a desirable but costly operation. In some domains it is possible to collect expert knowledge to manually create a structure for a Bayes Net. However, social networks, warehousing data, or supermarket purchasing records may contain hundreds of thousands of attributes. Providing expert Bayes Net structure in such cases is cumbersome if not impossible, even if as in the case with many of those domains the events are choices of very small subsets of the large pool of available entities. The complexity of existing algorithms for structural search prevents Bayes Net learning on datasets of that size.

This work introduces an algorithm for tractable structural learning in Bayes Nets by exploring structures on the local level. The algorithm exploits the computational efficiency of Frequent Sets for gathering statistics that are most likely to be useful for structure search given the assumption of sparse data. I will show the relevance of this work to modeling Social Networks. Finally, I will present an empirical evaluation of our algorithm applied to several massive datasets.

Note: If the time is left and there is a sufficient interest in the audience, I will in addition present a new generative model for evolution of social networks that I have developed in collaboration with Alice Zheng.