THE DISSERTATION DEFENSE FOR THE DEGREE OF Ph.D. IN COMPUTER SCIENCE FOR

                                                                                Arvind Agarwal

In machine learning, the standard goal of a learning problem is to find an appropriate statistical model from a model space based on the training data from a data space, while in data mining, the goal is to find interesting patterns in the data from a data space. In both fields, for many problems, these spaces carry geometric structures that can be exploited using geometric methods, or the problems themselves can be formulated in a way that naturally appeals to these methods. In such cases, studying these geometric structures and then using appropriate geometry-driven methods not only gives insight into existing algorithms, but also helps build new and better algorithms. In my research, I develop methods that exploit the geometric structure of the problem, for a variety of machine learning and data mining problems, and provide strong theoretical and empirical evidence in favor of using them.

My dissertation is divided into two parts. In the first part, I develop algorithms to solve a well known problem in data mining i.e. distance embedding problem. In particular, I use tools from computation geometry to build a unified framework for solving a distance embedding problem known as multidimensional scaling (MDS). This geometry-inspired framework results in algorithms that can solve different variants of MDS better than previous state-of-the-art methods. In addition, these algorithms come with many other attractive properties: they are simple, intuitive, easily parallelizable, scalable, and can handle missing data. Furthermore, I extend my generalized MDS framework to build scalable algorithms for dimensionality reduction, and also to solve a sensor network localization problem for mobile sensors. Experimental results show the effectiveness of this framework across all problems.

In the second part of my dissertation, I turn to the problems in machine learning, and use geometry to reason about the appropriateness of conjugate priors, develop a model that hybridizes between discriminative and generative frameworks, and build a new set of generative-process-driven kernels. More specifically, this part of my dissertation is devoted to the study of the geometry of the space of probabilistic models associated with the statistical generative process. This study --- based on the theory well grounded in information geometry --- allows me to reason about the appropriateness of conjugate priors from a geometric perspective, and hence gain insight into the large number of existing models that rely on these priors. Furthermore, I use this study to build hybrid models more naturally i.e., by combining discriminative and generative methods using the geometry underlying them, and also to build a family of kernels called generative kernels that can be used as off-the-shelf tool in any kernel learning method such as support vector machines. My experiments of generative kernels demonstrate their effectiveness providing further evidence in favor of using geometric methods.

Examining Committee:

Committee Chair:                       Dr. Hal Daume III

Dean's Representative:              Dr. Min Wu

Committee Members:                Dr. Amol Deshpande

                                                Dr. Suresh Venkatasubraminian

                                                 Dr. Jordan Boyd-Graber