LANS Informal Seminar: Matt Menickelly

Seminar Title: Cardinality-Constrained Sparse Inverse Covariance Estimation: An Algorithm and an Application to Anomaly Localization
Speaker: Matt Menickelly, Postdoctoral Appointee, MCS Division

Date/Time: 2018-03-21 10:30
Location: Bldg. 240, 4301

Description:
A common machine learning task is that of learning conditional dependences in a Gaussian graphical model via sparse inverse covariance estimation (SICE). Sparsity is desirable in this setting for the sake of interpretability – a zero in a learned inverse covariance matrix indicates a conditional independence between corresponding variables. In practical settings (especially when the number of nodes/variables is large), this sparsity is achieved via l1-regularization. However, in some settings, part of the conditional dependence structure of a graphical model are known a priori, and explicit bounds can be imposed on the number of nonzeros in the inverse covariance matrix using domain knowledge. Thus, we consider the problem of cardinality-constrained SICE with possible (simple) additional side constraints. We propose a projected Newton algorithm with a homotopy scheme for solving this problem. Although we can only prove a result demonstrating that all accumulation points of the algorithm iterates satisfy necessary optimality conditions, we achieve convincing empirical performance on real-world and synthetic data problems.

This particular work was motivated by a more specific problem of anomaly localization, particularly in monitoring sensor data of an oil compressor system for potential anomalies. Multivariate time series data is collected from across a sensor network and graphical models of the network are learned over sliding time windows using our proposed algorithm. Anomaly scores are then computed for each variable (sensor) based on various statistical difference measures between the series of learned graphical models and a reference graphical model, allowing the user to identify not only whether or not an anomaly has occurred within the network (anomaly detection), but to pinpoint which sensors are exhibiting anomalous behavior (hence, anomaly localization). Some empirical results of these anomaly localization methods will be discussed.