Institute for Software Research
School of Computer Science, Carnegie Mellon University
Unsupervised Spatial, Temporal and Relational Models
George B. Davis
Ph.D. Thesis (COS)
This thesis addresses two challenges in extracting patterns from social data generated by modern sensor systems and electronic mechanisms. First, that such data often combine spatial, temporal, and relational evidence, requiring models that properly utilize the regularities of each domain. Second, that data from open-ended systems often contain a mixture between entities and relationships that are known a priori, others that are explicitly detected, and still others that are latent but signicant in interpreting the data. Identifying the nal category requires unsupervised inference techniques that can detect certain structures without explicit examples.
I present new algorithms designed to address both issues within three frameworks: relational clustering, probabilistic graphical models, and kernel-conditional density estimation. These algorithms are applied to several datasets, including geospatial traces of international shipping trac and a dynamic network of publicly declared supply relations between US companies. The inference tasks considered include community detection, path prediction, and link prediction. In each case, I present theoretical and empirical results regarding accuracy and complexity, and compare ecacy to previous techniques.