Abstract The successful application of machine learning (ML) methods increasingly depends on their interpretability or explainability. Designing explainable ML (XML) systems is instrumental for ensuring transparency of automated decision-making that targets humans. The explainability of ML methods is also an essential ingredient for trustworthy artificial intelligence. A key challenge in ensuring explainability is its dependence on the specific human end user of an ML system. The users of ML methods might have vastly different background knowledge about ML principles, with some having formal training in the specific field and others having none. We use information-theoretic concepts to develop a novel measure for the subjective explainability of predictions delivered by a ML method. We construct this measure via the conditional entropy of predictions, given the user signal. Our approach allows for a wide range of user signals, ranging from responses to surveys to biophysical measurements. We use this measure of subjective explainability as a regularizer for model training. The resulting explainable empirical risk minimization (EERM) principle strives to balance subjective explainability and risk. The EERM principle is flexible and can be combined with arbitrary ML models. We present several practical implementations of EERM for linear models and decision trees. Numerical experiments demonstrate the application of EERM to weather prediction and detecting inappropriate language in social media.

The automatic and accurate analysis of medical images (e.g., segmentation,detection, classification) are prerequisites for modern disease diagnosis and prognosis. Computer-aided diagnosis (CAD) systems empower accurate and effective detection of various diseases and timely treatment decisions. The past decade witnessed a spur in deep learning (DL)-based CADs showing outstanding performance across many health care applications. Medical imaging is hindered by multiple sources of uncertainty ranging fromnteasurement (aleatoric) errors, physiological variability, and limited medical knowledge (epistemic errors). However, uncertainty quantification (UQ) in most existing DL methods is insufficiently investigated, particularly in medical image analysis. Therefore, to address this gap, in this article, we propose a simple yet novel hierarchical attentive multilevel feature fusion model with an uncertainty-aware module for medical image classification coinedHercules. This approach is tested on several real medical image classification challenges. The proposedHerculesmodel consists of two main feature fusion blocks, where the former concentrates on attention-based fusion with uncertainty quantification module and the latter uses the raw features.Herculeswas evaluated across three medical imaging datasets, i.e., retinal OCT, lung CT, and chest X-ray.Herculesproduced the best classification accuracy in retinal OCT (94.21%), lung CT (99.59%), and chest X-ray (96.50%) datasets, respectively, against other state-of-the-art medical image classification methods.

In an era of ubiquitous large-scale evolving data streams, data stream clustering (DSC) has received lots of attention because the scale of the data streams far exceeds the ability of expert human analysts. It has been observed that high-dimensional data are usually distributed in a union of low-dimensional subspaces. In this article, we propose a novel sparse representation-based DSC algorithm, called evolutionary dynamic sparse subspace clustering (EDSSC). It can cope with the time-varying nature of subspaces underlying the evolving data streams, such as subspace emergence, disappearance, and recurrence. The proposed EDSSC consists of two phases: 1) static learning and 2) online clustering. During the first phase, a data structure for storing the statistic summary of data streams, called EDSSC summary, is proposed which can better address the dilemma between the two conflicting goals: 1) saving more points for accuracy of subspace clustering (SC) and 2) discarding more points for the efficiency of DSC. By further proposing an algorithm to estimate the subspace number, the proposed EDSSC does not need to know the number of subspaces. In the second phase, a more suitable index, called the average sparsity concentration index (ASCI), is proposed, which dramatically promotes the clustering accuracy compared to the conventionally utilized SCI index. In addition, the subspace evolution detection model based on the Page-Hinkley test is proposed where the appearing, disappearing, and recurring subspaces can be detected and adapted. Extinct experiments on real-world data streams show that the EDSSC outperforms the state-of-the-art online SC approaches.

This paper formulates and studies a novel algorithm for federated learning from large collections of local datasets. This algorithm capitalizes on an intrinsic network structure that relates the local datasets via an undirected "empirical" graph. We model such big data over networks using a networked linear regression model. Each local dataset has individual regression weights. The weights of close-knit sub-collections of local datasets are enforced to deviate only little. This lends naturally to a network Lasso problem which we solve using a primal-dual method. We obtain a distributed federated learning algorithm via a message passing implementation of this primal-dual method. We provide a detailed analysis of the statistical and computational properties of the resulting federated learning algorithm.

We study the statistical and computational properties of a network Lasso method for local graph clustering. The clusters delivered by nLasso can be characterized elegantly via network flows between cluster boundaries and seed nodes. While spectral clustering methods are guided by a minimization of the graph Laplacian quadratic form, nLasso minimizes the total variation of cluster indicator signals. As demonstrated theoretically and numerically, nLasso methods can handle very sparse clusters (chain-like) which are difficult for spectral clustering. We also verify that a primal-dual method for non-smooth optimization allows to approximate nLasso solutions with optimal worst-case convergence rate.

We apply the network Lasso to classify partially labeled data points which are characterized by high-dimensional feature vectors. In order to learn an accurate classifier from limited amounts of labeled data, we borrow statistical strength, via an intrinsic network structure, across the dataset. The resulting logistic network Lasso amounts to a regularized empirical risk minimization problem using the total variation of a classifier as a regularizer. This minimization problem is a nonsmooth convex optimization problem which we solve using a primal-dual splitting method. This method is appealing for big data applications as it can be implemented as a highly scalable message passing algorithm.

Many applications generate data with an intrinsic network structure such as time series data, image data or social network data. The network Lasso (nLasso) has been proposed recently as a method for joint clustering and optimization of machine learning models for networked data. The nLasso extends the Lasso from sparse linear models to clustered graph signals. This paper explores the duality of nLasso and network flow optimization. We show that, in a very precise sense, nLasso is equivalent to a minimum-cost flow problem on the data network structure. Our main technical result is a concise characterization of nLasso solutions via the existence of certain network flows. The main conceptual result is a useful link between nLasso methods and basic graph algorithms such as clustering or maximum flow.

Automated decision making is used routinely throughout our every-day life. Recommender systems decide which jobs, movies, or other user profiles might be interesting to us. Spell checkers help us to make good use of language. Fraud detection systems decide if a credit card transactions should be verified more closely. Many of these decision making systems use machine learning methods that fit complex models to massive datasets. The successful deployment of machine learning (ML) methods to many (critical) application domains crucially depends on its explainability. Indeed, humans have a strong desire to get explanations that resolve the uncertainty about experienced phenomena like the predictions and decisions obtained from ML methods. Explainable ML is challenging since explanations must be tailored (personalized) to individual users with varying backgrounds. Some users might have received university-level education in ML, while other users might have no formal training in linear algebra. Linear regression with few features might be perfectly interpretable for the first group but might be considered a black-box by the latter. We propose a simple probabilistic model for the predictions and user knowledge. This model allows to study explainable ML using information theory. Explaining is here considered as the task of reducing the “surprise” incurred by a prediction. We quantify the effect of an explanation by the conditional mutual information between the explanation and prediction, given the user background.

We apply network Lasso to semi-supervised regression problems involving network-structured data. This approach lends quite naturally to highly scalable learning algorithms in the form of message passing over an empirical graph which represents the network structure of the data. By using a simple non-parametric regression model, which is motivated by a clustering hypothesis, we provide an analysis of the estimation error incurred by network Lasso. This analysis reveals conditions on the network structure and the available training data which guarantee network Lasso to be accurate. Remarkably, the accuracy of network Lasso is related to the existence of sufficiently large network flows over the empirical graph. Thus, our analysis reveals a connection between network Lasso and maximum network flow problems.

We model the sampling and recovery of clustered graph signals as a reinforcement learning (RL) problem. The signal sampling is carried out by an agent which crawls over the graph and selects the most relevant graph nodes to sample. The goal of the agent is to select signal samples which allow for the most accurate recovery. The sample selection is formulated as a multi-armed bandit (MAB) problem, which lends naturally to learning efficient sampling strategies using the well-known gradient MAB algorithm. In a nutshell, the sampling strategy is represented as a probability distribution over the individual arms of the MAB and optimized using gradient ascent. Some illustrative numerical experiments indicate that the sampling strategies obtained from the gradient MAB algorithm outperform existing sampling methods.

The data streams arising in many applications can be modeled as a union of low-dimensional subspaces known as multi-subspace data streams (MSDSs). Clustering MSDSs according to their underlying low-dimensional subspaces is a challenging problem which has not been resolved satisfactorily by existing data stream clustering (DSC) algorithms. In this paper, we propose a sparse-based DSC algorithm, which we refer to as dynamic sparse subspace clustering (D-SSC). This algorithm recovers the low-dimensional subspaces (structures) of high-dimensional data streams and finds an explicit assignment of points to subspaces in an online manner. Moreover, as an online algorithm, D-SSC is able to cope with the time-varying structure of MSDSs. The effectiveness of D-SSC is evaluated using numerical experiments.

We apply machine learning to automate the root cause analysis in agile software testing environments. In particular, we extract relevant features from raw log data after interviewing testing engineers (human experts). Initial efforts are put into clustering the unlabeled data, and despite obtaining weak correlations between several clusters and failure root causes, the vagueness in the rest of the clusters leads to the consideration of labeling. A new round of interviews with the testing engineers leads to the definition of five ground-truth categories. Using manually labeled data, we train artificial neural networks that either classify the data or pre-process it for clustering. The resulting method achieves an accuracy of 88.9%. The methodology of this paper serves as a prototype or baseline approach for the extraction of expert knowledge and its adaptation to machine learning techniques for root cause analysis in agile environments.

The network Lasso (nLasso) has been proposed recently as an efficient learning algorithm for massive networked data sets (big data over networks). It extends the well-known least absolute shrinkage and selection operator (Lasso) from learning sparse (generalized) linear models to network models. Efficient implementations of the nLasso have been obtained using convex optimization methods lending to scalable message passing protocols. In this letter, we analyze the statistical properties of nLasso when applied to localized linear regression problems involving networked data. Our main result is a sufficient condition on the network structure and available label information such that nLasso accurately learns a localized linear regression model from a few labeled data points. We also provide an implementation of nLasso for localized linear regression by specializing a primal-dual method for solving the convex (non-smooth) nLasso problem.

Prediction of power outages caused by convective storms, which are highly localized in space and time, is of crucial importance to power grid operators. We propose a new machine learning approach to predict the damage caused by storms. This approach hinges identifying and tracking of storm cells using weather radar images on the application of machine learning techniques. Overall prediction process consists of identifying storm cells from CAPPI weather radar images by contouring them with a solid 35-dBZ threshold, predicting a track of storm cells, and classifying them based on their damage potential to power grid operators. Tracked storm cells are then classified by combining data obtained from weather radar, ground weather observations, and lightning detectors. We compare random forest classifiers and deep neural networks as alternative methods to classify storm cells. The main challenge is that the training data are heavily imbalanced, as extreme weather events are rare.

We present a novel condition, which we term the network nullspace property, which ensures accurate recovery of graph signals representing massive network-structured datasets from few signal values. The network nullspace property couples the cluster structure of the underlying network-structure with the geometry of the sampling set. Our results can be used to design efficient sampling strategies based on the network topology.

We characterize the sample size required for accurate graphical model selection from non-stationary samples. The observed samples are modeled as a zero-mean Gaussian random process whose samples are uncorrelated but have different covariance matrices. This includes the case where observations form stationary or underspread processes. We derive a sufficient condition on the required sample size by analyzing a simple sparse neighborhood regression method.

We consider the problem of recovering a smooth graph signal from noisy samples observed at a small number of nodes. The signal recovery is formulated as a convex optimization problem using Tikhonov regularization based on the graph Laplacian quadratic form. The optimality conditions for this optimization problem form a system of linear equations involving the graph Laplacian. We solve this linear system via the iterative Gauss-Seidel method, which is shown to be particularly well-suited for smooth graph signal recovery. The effectiveness of the proposed recovery method is verified by numerical experiments using a real-world data-set.

We formulate and analyze a graphical model selection method for inferring the conditional independence graph of a high-dimensional nonstationary Gaussian random process (time series) from a finite-length observation. The observed process samples are assumed uncorrelated over time but having a time-varying marginal distribution. The selection method is based on testing conditional variances obtained for small subsets of process components. This allows to cope with the high-dimensional regime, where the sample size can be (much) smaller than the process dimension. We characterize the required sample size such that the proposed selection method is successful with high probability.

We consider the problem of recovering a graph signal from noisy and incomplete information. In particular, we propose an approximate message passing based iterative method for graph signal recovery. The recovery of the graph signal is based on noisy signal values at a small number of randomly selected nodes. Our approach exploits the smoothness of typical graph signals occurring in many applications, such as wireless sensor networks or social network analysis. The graph signals are smooth in the sense that neighboring nodes have similar signal values. Methodologically, our algorithm is a new instance of the denoising based approximate message passing framework introduced recently by Metzler et. al. We validate the performance of the proposed recovery method via numerical experiments. In certain scenarios our algorithm outperforms existing methods.

We consider the problem of learning a dictionary matrix from a number of observed signals, which are assumed to be generated via a linear model with a common underlying dictionary. In particular, we derive lower bounds on the minimum achievable worst case mean squared error (MSE), regardless of computational complexity of the dictionary learning (DL) schemes. By casting DL as a classical (or frequentist) estimation problem, the lower bounds on the worst case MSE are derived following an established information-theoretic approach to minimax estimation. The main contribution of this paper is the adaption of these information-theoretic tools to the DL problem in order to derive lower bounds on the worst case MSE of any DL algorithm. We derive three different lower bounds applying to different generative models for the observed signals. The first bound only requires the existence of a covariance matrix of the (unknown) underlying coefficient vector. By specializing this bound to the case of sparse coefficient distributions and assuming the true dictionary satisfies the restricted isometry property, we obtain a lower bound on the worst case MSE of DL methods in terms of the signal-to-noise ratio (SNR). The third bound applies to a more restrictive subclass of coefficient distributions by requiring the non-zero coefficients to be Gaussian. Although the applicability of this bound is the most limited, it is the tightest of the three bounds in the low SNR regime. A particular use of our lower bounds is the derivation of necessary conditions on the required number of observations (sample size), such that DL is feasible, i.e., accurate DL schemes might exist. By comparing these necessary conditions with sufficient conditions on the sample size such that a particular DL technique is successful, we are able to characterize the regimes, where those algorithms are optimal in terms of required sample size.

We propose a method for inferring the conditional independence graph (CIG) of a high-dimensional discrete-time Gaussian vector random process from finite-length observations. Our approach does not rely on a parametric model (such as, e.g., an autoregressive model) for the vector random process; rather, it only assumes certain spectral smoothness properties. The proposed inference scheme is compressive in that it works for sample sizes that are (much) smaller than the number of scalar process components. We provide analytical conditions for our method to correctly identify the CIG with high probability.

Within the framework of compressed sensing, we consider dense signals, which contain both discrete as well as continuous-amplitude components. We demonstrate by a comprehensive numerical study–to the best of our knowledge the first of its kind in the literature–that dense signals can be recovered from noisy, incomplete linear measurements by simple iterative algorithms that are inspired by or are implementations of approximate message passing. Those iterative algorithms are shown to significantly outperform all other algorithms presented so far, when they use a novel noise-adaptive thresholding function that is proposed in this contribution.

The mathematical theory of reproducing kernel Hilbert spaces (RKHSs) provides powerful tools for minimum variance estimation (MVE) problems. Here, we extend the classical RKHS-based analysis of MVE in several directions. We develop a geometric formulation of five known lower bounds on the estimator variance (Barankin bound, Cramér-Rao bound, constrained Cramér-Rao bound, Bhattacharyya bound, and Hammersley-Chapman-Robbins bound) in terms of orthogonal projections onto a subspace of the RKHS associated with a given MVE problem. We show that, under mild conditions, the Barankin bound (the tightest possible lower bound on the estimator variance) is a lower semicontinuous function of the parameter vector. We also show that the RKHS associated with an MVE problem remains unchanged if the observation is replaced by a sufficient statistic. Finally, for MVE problems conforming to an exponential family of distributions, we derive novel closed-form lower bounds on the estimator variance and show that a reduction of the parameter set leaves the minimum achievable variance unchanged.

We consider minimum variance estimation within the sparse linear Gaussian model (SLGM). A sparse vector is to be estimated from a linearly transformed version embedded in Gaussian noise. Our analysis is based on the theory of reproducing kernel Hilbert spaces (RKHS). After a characterization of the RKHS associated with the SLGM, we derive a lower bound on the minimum variance achievable by estimators with a prescribed bias function, including the important special case of unbiased estimation. This bound is obtained via an orthogonal projection of the prescribed mean function onto a subspace of the RKHS associated with the SLGM. It provides an approximation to the minimum achievable variance (Barankin bound) that is tighter than any known bound. Our bound holds for an arbitrary system matrix, including the overdetermined and underdetermined cases. We specialize it to compressed sensing measurement matrices and express it in terms of the restricted isometry constant. For the special case of the SLGM given by the sparse signal in noise model, we derive closed-form expressions of the Barankin bound and of the corresponding locally minimum variance estimator. Finally, we compare our bound with the variance of several well-known estimators, namely, the maximum-likelihood estimator, the hard-thresholding estimator, and compressive reconstruction using orthogonal matching pursuit and approximate message passing.

Estimating the spectral characteristics of a nonstationary random process is an important but challenging task, which can be facilitated by exploiting structural properties of the process. In certain applications, the observed processes are underspread, i.e., their time and frequency correlations exhibit a reasonably fast decay, and approximately time-frequency sparse, i.e., a reasonably large percentage of the spectral values are small. For this class of processes, we propose a compressive estimator of the discrete Rihaczek spectrum (RS). This estimator combines a minimum variance unbiased estimator of the RS (which is a smoothed Rihaczek distribution using an appropriately designed smoothing kernel) with a compressed sensing technique that exploits the approximate time-frequency sparsity. As a result of the compression stage, the number of measurements required for good estimation performance can be significantly reduced. The measurements are values of the ambiguity function of the observed signal at randomly chosen time and frequency lag positions. We provide bounds on the mean-square estimation error of both the minimum variance unbiased RS estimator and the compressive RS estimator, and we demonstrate the performance of the compressive estimator by means of simulation results. The proposed compressive RS estimator can also be used for estimating other time-dependent spectra (e.g., the Wigner-Ville spectrum), since for an underspread process most spectra are almost equal.

We consider estimation of a sparse parameter vector that determines the covariance matrix of a Gaussian random vector via a sparse expansion into known "basis matrices." Using the theory of reproducing kernel Hilbert spaces, we derive lower bounds on the variance of estimators with a given mean function. This includes unbiased estimation as a special case. We also present a numerical comparison of our lower bounds with the variance of two standard estimators (hard-thresholding estimator and maximum likelihood estimator).

We consider estimation of a sparse parameter vector from measurements corrupted by white Gaussian noise. Using the framework of reproducing kernel Hilbert spaces, we derive closed-form expressions of the Barankin bound, i.e., of the minimum locally achievable variance of any estimator with a prescribed bias function, including the unbiased case. We also derive the locally minimum variance (LMV) estimator that achieves the minimum variance, and a necessary and sufficient condition on the prescribed bias function for the existence of finite-variance estimators and, simultaneously, of the LMV estimator. Finally, we present a numerical comparison of the variance of the hard-thresholding estimator with the corresponding minimum achievable variance.

The problem studied in this paper is unbiased estimation of a sparse nonrandom vector corrupted by additive white Gaussian noise. It is shown that while there are infinitely many unbiased estimators for this problem, none of them has uniformly minimum variance. Therefore, the focus is placed on locally minimum variance unbiased (LMVU) estimators. Simple closed-form lower and upper bounds on the variance of LMVU estimators or, equivalently, on the Barankin bound (BB) are derived. These bounds allow an estimation of the threshold region separating the low-signal-to-noise ratio (SNR) and high-SNR regimes, and they indicate the asymptotic behavior of the BB at high SNR. In addition, numerical lower and upper bounds are derived; these are tighter than the closed-form bounds and thus characterize the BB more accurately. Numerical studies compare the proposed characterizations of the BB with established biased estimation schemes, and demonstrate that while unbiased estimators perform poorly at low SNR, they may perform better than biased estimators at high SNR. An interesting conclusion of this analysis is that the high-SNR behavior of the BB depends solely on the value of the smallest nonzero entry of the sparse vector, and that this type of dependence is also exhibited by the performance of certain practical estimators.

We consider the estimation of a sparse parameter vector from measurements corrupted by white Gaussian noise. Our focus is on unbiased estimation as a setting under which the difficulty of the problem can be quantified analytically. We show that there are infinitely many unbiased estimators but none of them has uniformly minimum mean-squared error. We then provide lower and upper bounds on the Barankin bound, which describes the performance achievable by unbiased estimators. These bounds are used to predict the threshold region of practical estimators.

We propose a ldquocompressiverdquo estimator of the Wigner-Ville spectrum (WVS) for time-frequency sparse, underspread, nonstationary random processes. A novel WVS estimator involving the signal's Gabor coefficients on an undersampled time-frequency grid is combined with a compressed sensing transformation in order to reduce the number of measurements required. The performance of the compressive WVS estimator is analyzed via a bound on the mean square error and through simulations. We also propose an efficient implementation using a special construction of the measurement matrix.