Digital Repository at the University of Maryland (DRUM)  >
Theses and Dissertations from UMD  >
UMD Theses and Dissertations 

Please use this identifier to cite or link to this item:

Title: Scalable machine learning for massive datasets: Fast summation algorithms
Authors: Raykar, Vikas Chandrakant
Advisors: Duraiswami, Ramani
Department/Program: Computer Science
Type: Dissertation
Sponsors: Digital Repository at the University of Maryland
University of Maryland (College Park, Md.)
Subjects: Computer Science
Artificial Intelligence
Engineering, Electronics and Electrical
Issue Date: 25-Apr-2007
Abstract: Huge data sets containing millions of training examples with a large number of attributes are relatively easy to gather. However one of the bottlenecks for successful inference is the computational complexity of machine learning algorithms. Most state-of-the-art nonparametric machine learning algorithms have a computational complexity of either O(N^2) or O(N^3), where N is the number of training examples. This has seriously restricted the use of massive data sets. The bottleneck computational primitive at the heart of various algorithms is the multiplication of a structured matrix with a vector, which we refer to as matrix-vector product (MVP) primitive. The goal of my thesis is to speedup up some of these MVP primitives by fast approximate algorithms that scale as O(N) and also provide high accuracy guarantees. I use ideas from computational physics, scientific computing, and computational geometry to design these algorithms. The proposed algorithms have been applied to speedup kernel density estimation, optimal bandwidth estimation, projection pursuit, Gaussian process regression, implicit surface fitting, and ranking.
Appears in Collections:Computer Science Theses and Dissertations
UMD Theses and Dissertations

Files in This Item:

File Description SizeFormatNo. of Downloads
umi-umd-4283.pdf3.33 MBAdobe PDF666View/Open

All items in DRUM are protected by copyright, with all rights reserved.


DRUM is brought to you by the University of Maryland Libraries
University of Maryland, College Park, MD 20742-7011 (301)314-1328.
Please send us your comments