Fast Learning Algorithms with Applications to Human-Robot Interactions
Abstract
Learning models from data has a wide range of applications in many areas. One popular learning technique is Graphical Lasso (Glasso), which is a conic optimization method for learning the structure of Gaussian graphicalmodels. The goal is to identify the statistical relationships among the parameters of a given system from observational data. The computational complexity of the existing algorithms for Glasso is high, which restricts its usage to small-sized systems and is not suitable for applications demanding real-time actions. This statistical learning problem becomes significantly more challenging for those systems performing in a dynamic and uncertain environment. This project is motivated by the pressing need to design fast and scalable algorithms for structure learning problems, and its immediate application is in the design of intelligent autonomous agents that are able to quickly learn human movements. This project is based on the observation that the solution of Glasso can be found via a closedform formula for acyclicgraphical models and may be approximated via an explicit formula for sparse graphs, where the complexity of finding such solutions is quadratic time. This result implies that the true computational complexity of Glasso could be muchlower than that of the existing numerical algorithms for this problem. Motivated by these findings, this proposal aims at studying a significantly general form of Glasso, named Constrained Glasso (C-Glasso), for learning different types ofmodels (such as sparse and block sparse) subject to user-defined constraints. The objectives of the proposed project are as follows: 1) To analyze the solution of C-Glasso for different choices of sparsity-promoting peminorms andconstraint sets; 2) To study the effect of the regularization parameter on the sparsification of the solution of C-Glasso; 3) To investigate what subset of the sparsity pattern of the C-Glasso solution could be found via simple thresholdingbased techniques; 4) To design low-complexity algorithms for C-Glasso using the notions of tree decomposition and chordal extension; 5)To investigate the design of linear or quadratic-time algorithms for finding exact or approximate solutions of C-Glasso in the case where a sparse graph is sought; 6) To generalize the results to dynamic constrained graphical modelswhere the system evolves over time; 7) To implement the algorithms in a solver and conduct case studies with Navy applications. The project is interdisciplinary and covers several topics in conic optimization, graph theory, algorithmdesign, computational complexity, and machine learning. This project enables the design of fast and scalable numerical algorithms for important statistical learning problems where a real-time decision-making process is needed.Such algorithms can be used to solve complex, dynamic learning problems with strong theoretical guarantees. An important application of this work is in building intelligent agents that are able to learn human movements very quicklyin uncertain environments. This project impacts DoD capabilities by developing efficient computational methods and algorithms that can be deployed to build smart autonomous agents.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 26, 2018
- Source ID
- N000141812526
Entities
People
- Somayeh Sojoudi
Organizations
- Office of Naval Research
- United States Navy
- University of California Regents