Scalable Methods in Machine Learning
Many large scale machine learning problems are formulated as optimization problems, in which some measure of error or loss is to be minimized over a suitable training corpus. Real problems have too many data points to fit in a single computer. Hence the data and/or computation must be distributed over a network of computers. Often the only practical methods for extremely large problems are so-called splitting methods, but their convergence properties are extremely variable: sometimes very fast, sometimes very slow, in ways that can be hard to predict. The goal of this project is to gain a better understanding of the convergence behavior and to use this understanding to construct accelerated algorithms with more consistent convergence properties. This will allow the application of machine learning techniques to a much wider class of problems.
Click here for more information on this project.
Unsupervised Document Set Exploration Using Divisive Partitioning
Click here for more information on this project.
This is part of a larger project entitled "WebACE: Web Agent for Automated
Categorization and Exploration,"
with Daniel Boley, Maria Gini, Vipin Kumar, Bamshad Mobasher, and others.
The challenge addressed in this project is the unsupervised exploration
and categorization of large unstructured data sets using a recently
developed algorithm based on divisive partitioning. Initial experiments
on World Wide Web document sets have demonstrated that this algorithm,
called Principal Direction Divisive Partitioning, is effective at
extraction of meaningful clusters while being scalable to large document
sets. The investigations within this project will include:
(i) a thorough study of its scalability properties and comparison with other methods,
(ii) utilization of the hierarchical structures already generated within the algorithm to create taxonomies on the document set and to classify new documents autonomously,
(iii) adaptation and utilization as a supervised learning method,
(iv) extension to other applications and domains, including a study of the algorithm's effectiveness in domains beyond document sets. Potential applications and domains to be explored in this project include
(a) incorporation within autonomous agents for exploring the World Wide Web, such as WebACE,
(b) classification of documents in large but more homogeneous medical or legal databases,
(c) discovery of patterns within chemical toxicology data,
(d) extraction of clusters within genetic sequence databases. The goal is to establish the divisive partitioning method as an effective alternative among existing unsupervised clustering tools for use on document sets and other domains.
Numerical Algorithms for Very Large, Sparse Dynamical Systems
Daniel Boley, Gary Balas, Youcef Saad
We develop and experiment with a variety of core numerical algorithms for large sparse or structured linear algebra problems. Part of the research is the development of effective algorithms for the analysis and design of very large control models such as those related to large flexible space structures. To accomplish this, a major focus of this research will be the design of effective and efficient linear algebra algorithms. Examples of problems we address are large Lyapunov equations, large order matrix pencils, large eigenvalue and singular values solvers. Parallel algorithms will be explored and exploited. Approximate solutions obtained via Krylov space methods, or other methods, will be analyzed. A standard sparse matrix library (SPARSKIT) will be used as the foundation for the software development. To evaluate the effectiveness of the algorithms, the quality of controller designs obtained from the approximate solutions will be explored.
Vehicle Navigation and Localization using Multiple Navigation Aids
Daniel Boley and Nikolaos Papanikolopoulos
This research aims to test the feasibility of combining two or more navigation methods in a simple manner to achieve higher accuracy and robustness than is possible with any single system. The aim is to do it with algorithms and computer processing that is fast enough on processors simple enough to consider installing in a vehicle. The methods combine fixes from the different aids, update a least-squares fit to the fixes, to obtain an improved fix and an estimate of the error in the fix. We will demonstrate a new paradigm that can deliver locations estimates of higher overall accuracy using fewer readings than the Kalman filter, and is capable of combining fixes from several different sources and paradigms, even if some sources yield fixes only sporadically. We use a total least squares estimate that can treat errors from dead reckoning with the same importance as errors from GPS or visual tracking. The method will also be able to combine partial fixes from each system to obtain a full fix, in cases where one or more sensors have a intermittent or temporary failure, or the environment changes.
Backward Error Assertions
We develop an assertion scheme based on the backward error analysis for error detection in algorithms that solve dense systems of linear equations, A x = b. Unlike previous methods, this Backward Error Assertion Model is specifically designed to operate in an environment of floating point arithmetic subject to round-off errors, and can be easily instrumented in a Watchdog processor environment. The complexity of verifying assertions is order n squared compared to the order n cubed complexity of algorithms solving A x = b. Unlike other proposed error detection methods, this assertion model does not require any encoding of the matrix A. Experimental results under various error models are presented to validate the effectiveness of this assertion scheme.
Genetic Algorithms for Robotics Applications
We use a Genetic Programming paradigm to have a robot learn to carry out simple navigation tasks in the presence of unknown obstacles. We have built a package to allow the use to design different room layouts and evaluate the performance of the generated algorithms under different conditions. A simple graphical interface makes it easy to design different layouts and operating conditions.