2.2.1 Detecting Vehicle-Borne IEDs in Urban Environments

As part of an ongoing counterinsurgency operation by coalition forces in the country of Aragon, focus is placed on monitoring of insurgent movements and activities. Vehicle-borne improvised explosive devices (VBIEDs) have become more frequently used by insurgents in recent months, requiring methods for quick detection and interception. Recent intelligence reports have provided details on the physical appearance of IED-outfitted vehicles in the area. However, due to the time constraints in confirming detections of VBIEDs, methods for autonomous detection become desirable. To support VBIED detection, an IoBT infrastructure has been deployed by coalition forces consisting of a mix of unattended ground sensors (UGSs) and unmanned aerial systems (UASs). In turn, supervised learning methods are employed over sensor data gathered from both sources.

Recent intelligence has indicated that VBIEDs may be used in a city square during the annual Aragonian Independence Festival. A local custom for this festival involves decoration of vehicles with varying articles (including flags and Christmas tree lighting). A UAS drone is tasked with patrolling the airspace over one of the inbound roadways and recoding images of detected vehicles. However, due to the decorations present on many civilian vehicles, confidence in VBIED classification by the UAS is significantly reduced. To mitigate this, the drone flies along a 3-mile stretch of road for 10 minutes to gather new images of the decorated vehicles. In each case the drone generates a classification of each vehicle as VBIED or not, each with a particular confidence value. For low-confidence readings, the drone contacts a corresponding UGS to do the following: (i) take a high-resolution image, and (ii) take readings for presence of explosives-related chemicals in the air nearby, where any detectable explosives confirms the vehicle is a VBIED. Since battery power for the UGS is limited, along with available network bandwidth, the UAS should only request UGS readings when especially necessary. Following receipt of data from a UGS, the UAS performs retraining of the classifier to improve the accuracy of future VBIED classification attempts. Over a short period, the UAS has gathered additional training data to support detection of VBIEDs. Eventually, the drone passes over a 1-mile stretch of road lacking UGSs. At this point the UAS must classify detected vehicles without UGS support (Fig. 2.1).

This example scenario highlights several research issues specific to IoBT settings, as reflected in prior surveys (e.g., Suri et al., 2016; Zheng & Carter, 2015): (i) a needed capability to quickly gather training data reflecting unforeseen learning/classification tasks; (ii) a needed capability to incrementally learn over the stream of field-specific data (e.g., increasing the accuracy of classifying VBIEDs by learning over the stream of pictures of decorated cars collected over 10 minutes of flight time); and (iii) management of limited network bandwidth and connectivity between assets (e.g., between the UAS and UGS along the road) requiring selective asset use to obtain classifier-relevant data that increases the classifier knowledge.

Each of these issues requires the selection of learning and classification methods appropriate to stream-based data sources. Prior research (Bottou, 1998 b; Bottou & Cun, 2004; Vapnik, 2013) demonstrates the equivalence of learning from stream-based data in real time with learning from infinite samples. From this work it follows that statistical-learning methods adept to large-scale data sources may be applicable for stream-based data.

This chapter opens with a survey of classical and modern statistical-learning theory, and how numerical optimization can be used to solve the resulting mathematical problems. The objective of this chapter is to encourage the IoT and ML research communities to revisit the underlying mathematical underpinnings of stream-based learning, as they apply to IoBT-based systems.

2.3.1 Optimization Problem

The standard stochastic optimization problem is:

$\begin{array}{l}\hfill \underset{w}{min}f(w)=\mathbb{E}[F(w;\xi )]\end{array}$

where expectation is taken with respect to the probability distribution of ξ = (X, Y), the explanatory, and response variables. In ML, F(w;ξ) is typically of the form:

$\begin{array}{l}\hfill F(w;\xi )=\ell (h(X,w)-Y)\end{array}$

where ℓ is some loss function, such as ∥⋅∥₂. Most optimization algorithms attempt to optimize what is called the sample-path problem, the solution of which is often referred to as the empirical risk minimizer (ERM). This strategy attempts to solve an approximation to f(w) using a finite amount of training data:

$\begin{array}{l}\hfill \underset{w}{min}\hat{f}(w)=\frac{1}{n}\sum _{i=1}^n\ell (h(x_i,w)-{\mathrm{y}}_i)\end{array}$

This is the problem that the bulk of ML algorithms attempt to minimize. A particular instance is maximum likelihood estimation, perhaps the most widely used estimation method among statisticians. For computer scientists minimizing a loss function (such as ℓ₂ loss) without an explicit statistical model is more common.

Although it may go without saying that minimizing $\hat{f}(w)$ is not the end goal. Ideally we wish to minimize the true objective, f(w). For finite sample sizes one runs into issues of overfitting to the sample problem. An adequate solution to the sample problem may not generalize well to future predictions (especially true for highly complex, over-parameterized models). Some ways of combating this problem include early-stopping, regularization, and Bayesian methods. In a large data setting, however, we can work around this issue. Due to such large sample sizes, we have an essentially infinite amount of data. Additionally, we are often in an online setting where data are continuously incoming, and we would like our model to continuously learn from new data. In this case we can model data as coming from an oracle that draws from the true probability distribution P_ξ (such a scheme is fairly standard among the stochastic optimization community, but is more rare in ML). In this manner we can optimize the true risk (1) with respect to the objective function, f(w).

2.3.2 Stochastic Gradient Descent Algorithm

Algorithm 2.1 shows a generic SGD algorithm to be used to solve (1). The direction of each iteration, g(x_k, ξ_k) depends on the current iterate x_k as well as a random draw ξ_i ∼ P_ξ.

Algorithm 2.1

Generic SGD

The basic SGD algorithm sets n_k = 1, ${\alpha }_k=\mathbb{O}(1/k)$ and computes the stochastic direction as:

$\begin{array}{l}\hfill w_{k+1}=w_k-{\alpha }_k\nabla F(w_k,{\xi }_k)\end{array}$

This is essentially the full-gradient method only evaluated for one sample point. Using the standard full-gradient method would require n gradient evaluations every iteration, but the basic SGD algorithm only requires the evaluation of one. We briefly discuss an implementation for logistic regression.

2.3.3 Example: Logistic Regression

To make this algorithm more concrete, consider the case of binary logistic regression. When the amount of data is manageable, a standard way (Hastie, Tibshirani, & Friedman, 2009) to find the optimal parameters is to apply Newton's method (since there is no closed-form solution) to the log-likelihood for the model:

$\begin{array}{l}\hfill \ell (w;x,y)=\sum _{i=1}^n{y}_i{w}^T{x}_i-log(1+e^{w^T{x}_i})\end{array}$

However, when n is large, this quickly becomes unfeasible. Instead, we could use a simple SGD implementation. In this case we set the stochastic direction to be a random gradient evaluated at ξ_k = (X_k, Y_k), which is sampled from the oracle:

$\begin{array}{ll}\hfill g(x_k,{\xi }_k)& =\nabla F(w_k,{\xi }_k)\hfill \\ \hfill & =\nabla \ell (w_k;x_k,y_k)\hfill \\ \hfill & =x_k\left.y_k-\frac{e^{w^T{x}_k}}{1+e^{w^T{x}_k}}\right)\hfill \end{array}$

The implemented algorithm is then (Algorithm 2.2):

Algorithm 2.2

Basic SGD for Logistic Regression

Again, note that for each iteration only a single training point is evaluated. On the other hand the full-gradient method would have to use the entire dataset for every iteration.

2.3.4 SGD Variants

As mentioned in Section 2.1, the basic SGD algorithm has some room for improvement. In this section we introduce two popular SGD variants: mini-batch SGD and SGD with momentum. Each variant gives a different yet useful way of improving upon the basic SGD algorithm.

2.3.4.1 Mini-Batch SGD

One of the major issues with SGD is that its search directions have high variance. Instead of moving downhill as intended, the algorithm may wander around randomly more than we would like. A natural idea is to use a larger sample size for the gradient estimates. The basic SGD uses a sample size of n = 1, so it makes sense that we might wish to use more draws from the oracle to reduce the variance. Specifically, we would reduce the variance in gradient estimates by a factor of $\frac{1}{n}$, where n is the batch size. The mini-batch algorithm is implemented as shown in Algorithm 2.3.

Algorithm 2.3

Mini-Batch SGD

It is shown in Bottou, Curtis, and Nocedal (2016) that under assumptions of smoothness and strong convexity, standard SGD (sample size n = 1 with fixed α) achieves an error rate of:

$\begin{array}{l}\hfill \mathbb{E}(f(x_k)-f(x⁎))\le \frac{\alpha LM}{2c\mu }+{(1-\alpha c\mu )}^{k-1}\left.f(x_1)-f(x⁎)-\frac{\alpha LM}{2c\mu }\right)\end{array}$

This convergence rate has several assumption-dependent constants such as the Lipschitz constant L and strong-convexity parameter c. However, the defining feature of that algorithm is the (⋅)^k−1 term, which implies that the error decreases exponentially to the constant $\frac{\alpha LM}{2c\mu }$. Using mini-batch SGD, on the other hand, yields the following bound:

$\begin{array}{l}\hfill \mathbb{E}(f(x_k)-f(x⁎))\le \left.\frac{1}{n}\right)\frac{\alpha LM}{2c\mu }+{(1-\alpha c\mu )}^{k-1}\left.f(x_1)-f(x⁎)-\left.\frac{1}{n}\right)\frac{\alpha LM}{2c\mu }\right)\end{array}$

Thus the mini-batch algorithm converges at the same rate, but to a smaller error constant. This is certainly an improvement in terms of the error bound, but of course requires n − 1 more samples at each iteration than the standard SGD. Thus it is not entirely clear which algorithm is better. If one could perform mini-batch in parallel with little overhead cost, the resulting algorithm would achieve the described bound without the cost of sampling n draws sequentially. Otherwise, the tradeoff is somewhat ambiguous.

2.3.5 Nesterov's Accelerated Gradient Descent

Nesterov's accelerated gradient descent (NAGD) algorithm for deterministic settings has been shown to be optimal for a variety of problem assumptions. For example, in the case where the objective is smooth and strongly convex, NAGD achieves the lower complexity bound, unlike standard gradient descent (Nesterov, 2004). Currently, there has not been a lot of attention given to NAGD in the stochastic setting (though, see Yang et al., 2016). We would like to extend NAGD to several problem settings in a stochastic context. Additionally, we would like to incorporate adaptive sampling (using varying batch sizes) into a stochastic NAGD. Adaptive sampling has shown promise, yet has not received a lot of attention.

The development of a more-efficient SGD algorithm would reduce uncertainty in the training of ML models at a faster rate than current algorithms. This is especially important for online learning, where it is crucial that algorithms adapt efficiently to newly observed data in the field.

2.3.6 Generalized Linear Models

The first and simplest choice of estimator function class is $\mathcal{F}={\mathbb{R}}^p$. In this case, the estimator is a generalized linear model (GLM): $\hat{\mathbf{y}}(\mathbf{x})={\mathbf{w}}^T\mathbf{x}$ for some parameter vector $\mathbf{w}\in {\mathbb{R}}^p$ (Nelder & Baker, 1972). In this case optimizing the statistical loss is the stochastic convex optimization problem, stated as:

$\begin{array}{l}\hfill \underset{\mathbf{w}\in {\mathbb{R}}^p}{min}{\mathbb{E}}_{\mathbf{x},\mathbf{y}}[\ell ({\mathbf{w}}^T\mathbf{x},\mathbf{y})]\end{array}$

Observe that to optimize Eq. (2.3), assuming a closed-form solution is unavailable, a gradient descent or Newton's method must be used (Boyd & Vanderberghe, 2004). However, either method requires computing the gradient of $L(\mathbf{w}):={\mathbb{E}}_{\mathbf{x},\mathbf{y}}[\ell ({\mathbf{w}}^T\mathbf{x},\mathbf{y})]$, which requires infinitely many realizations (x_n, y_n) of the random pair (x, y), and thus has infinite complexity. This computational bottleneck has been resolved through the development of stochastic approximation (SA) methods (Bottou, 1998 a; Robbins & Monro, 1951), which operate on subsets of data examples per step. The most common SA method is the SGD, which involves descending along the stochastic gradient ∇_wℓ(w^Tx_t, y_t) rather than the true gradient at each step:

$\begin{array}{l}\hfill {\mathbf{w}}_{t+1}={\mathbf{w}}_t-{\eta }_t{\nabla }_{\mathbf{w}}\ell ({\mathbf{w}}_t^T{\mathbf{x}}_t,{\mathbf{y}}_t)\end{array}$

Use of SGD (Eq. 2.4) is prevalent due to its simplicity, ease of use, and the fact that it converges to the minimizer of Eq. (2.3) almost certainly, and in expectation at a $\mathcal{O}(1/\sqrt{t})$ rate when L(w) is convex and a sublinearly $\mathcal{O}(1/t)$ when it is strongly convex. Efforts to improve the mean convergence rate to $\mathcal{O}(1/t^2)$ through the use of Nesterov acceleration (Nemirovski, Juditsky, Lan, & Shapiro, 2009) have also been developed, whose updates are given as:

$\begin{array}{ll}\hfill {\mathbf{w}}_{t+1}& ={\mathbf{v}}_t-{\eta }_t{\nabla }_{\mathbf{w}}\ell ({\mathbf{v}}_t^T{\mathbf{x}}_t,{\mathbf{y}}_t)\hfill \\ \hfill {\mathbf{v}}_{t+1}& =(1-{\gamma }_t){\mathbf{w}}_{t+1}+{\gamma }_t{\mathbf{w}}_t\hfill \end{array}$

A plethora of tools have been proposed specifically to minimize the empirical risk (sample size N is finite) in the case of GLMs, which achieve even faster linear or superlinear convergence rates. These methods are either based on reducing the variance of the SA (data-subsampling) error of the stochastic gradient (Defazio, Bach, & Lacoste-Julien, 2014; Johnson & Zhang, 2013; Schmidt, Roux, & Bach, 2013) or by using approximate second-order (Hessian) information (Goldfarb, 1970; Shanno & Phua, 1976). This thread has culminated in the fact that quasi-Newton methods (Mokhtari, Gürbüzbalaban, & Ribeiro, 2016) outperform variance reduction methods (Hu, Pan, & Kwok, 2009) for finite-sum minimization when N is large scale. For specifics on stochastic quasi-Newton updates, see Mokhtari and Ribeiro (2015) and Byrd, Hansen, Nocedal, and Singer (2016). However, as $N\to \infty$, the analysis that yields linear or superlinear learning rates breaks down, and the best one can hope for is Nesterov's $\mathcal{O}(1/t^2)$ rate (Nemirovski et al., 2009).

2.3.7 Learning Feature Representations for Inference

Transformations of data domains have become widely used in the past decades, due to their ability to extract useful information from input signals as a precursor to solving statistical inference problems. For instance, if the signal dimension is very large, dimensionality reduction is of interest, which may be approached with principal component analysis (Jolliffe, 1986). If instead one would like to conduct multiresolution analysis, wavelets (Mallat, 2008) may be more appropriate. These techniques, which also include a k-nearest neighbor, are known as unsupervised or signal representation learning (Murphy, 2012). Recently, methods based on learned representations, rather than those fixed a priori, have gained traction in pattern recognition (Elad & Aharon, 2006; Mairal, Elad, & Sapiro, 2008). A special case of data-driven representation learning is dictionary learning (Mairal, Bach, Ponce, Sapiro, & Zisserman, 2008), the focus of this section.

Here we address finding a dictionary (signal encoding) that is well adapted to a specific inference task (Mairal, Bach, & Ponce, 2012). To do so, denote the coding $\mathit{\alpha }(\tilde{\mathbf{D}};\mathbf{x})\in {\mathbb{R}}^k$ as a feature representation of the signal x_t with respect to some dictionary matrix $\tilde{\mathbf{D}}\in {\mathbb{R}}^{p\times k}$. Typically, $\mathit{\alpha }(\tilde{\mathbf{D}};\mathbf{x})$ is chosen as the solution to a lasso regression or approximate solution to an ℓ₀ constrained problem that minimizes some criterion of distance between D^Tα and x to incentivize codes to be sparse. Further introduce the classifier $\mathbf{w}\in {\mathbb{R}}^k$ that is used to predict target variable y_t when given the signal encoding $\mathit{\alpha }(\tilde{\mathbf{D}};\mathbf{x})$. The merit of the classifier $\mathbf{w}\in \mathcal{W}\subset {\mathbb{R}}^k$ is measured by the smooth loss function $\ell (\mathit{\alpha }⁎({\mathbf{w}}^T\mathit{\alpha }(\tilde{\mathbf{D}};\mathbf{x});({\mathbf{x}}_t,{\mathbf{y}}_t)))$ that captures how well the classifier w may predict y_t when given the coding $\mathit{\alpha }(\tilde{\mathbf{D}};{\mathbf{x}}_t)$. Note that α is computed using the dictionary $\tilde{\mathbf{D}}$. The task-driven dictionary learning problem is formulated as the joint determination of the dictionary $\tilde{\mathbf{D}}\in \mathcal{D}$ and classifier $\mathbf{w}\in \mathcal{W}\subset {\mathbb{R}}^k$ that minimize the cost $\ell (\mathit{\alpha }(\tilde{\mathbf{D}};{\mathbf{x}}_t),\mathbf{w};({\mathbf{x}}_t,{\mathbf{y}}_t))$ averaged over the training set:

$\begin{array}{c}\hfill (\tilde{\mathbf{D}}⁎,\mathbf{w}⁎):=\underset{\tilde{\mathbf{D}}\in \mathcal{D},\mathbf{w}\in \mathcal{W}}{argmin}{\mathbb{E}}_{\mathbf{x},\mathbf{y}}[\ell ({\mathbf{w}}^T\mathit{\alpha }(\tilde{\mathbf{D}};{\mathbf{x}}_t);({\mathbf{x}}_t,{\mathbf{y}}_t))]\hfill \end{array}$

In Eq. (2.6) we specify the estimator $\hat{\mathbf{y}}(\mathbf{x})={\mathbf{w}}^T\mathit{\alpha }⁎(\tilde{\mathbf{D}};\mathbf{x})$, which parameterizes the function class $\mathcal{F}$ as the product set $\mathcal{W}\times \mathcal{D}$. For a given dictionary $\tilde{\mathbf{D}}$ and signal sample x_t, we compute the code $\mathit{\alpha }⁎(\tilde{\mathbf{D}};{\mathbf{x}}_t)$ as per some lasso regression problem, for instance, and then predict y_t using w, and measure the prediction error with the loss function $\ell ({\mathbf{w}}^T\mathit{\alpha }(\tilde{\mathbf{D}};{\mathbf{x}}_t),;({\mathbf{x}}_t,{\mathbf{y}}_t))$. The optimal pair $(\tilde{\mathbf{D}}⁎,\mathbf{w}⁎)$ in Eq. (2.6) is the one that minimizes the cost averaged over the given sample pairs (x_t, y_t). Observe that $\mathit{\alpha }⁎(\tilde{\mathbf{D}};{\mathbf{x}}_t)$ is not a variable in the optimization in Eq. (2.6) but a mapping for an implicit dependence of the loss on the dictionary $\tilde{\mathbf{D}}$. The optimization problem in Eq. (2.6) is not assumed to be convex—this would be restrictive because the dependence of ℓ on $\tilde{\mathbf{D}}$ is, partly, through the mapping $\mathit{\alpha }⁎(\tilde{\mathbf{D}};{\mathbf{x}}_t)$ defined by some sparse-coding procedure. In general, only local minima of Eq. (2.6) can be found. This formulation has, nonetheless, been successful in solving practical pattern recognition tasks in vision (Mairal et al., 2012) and robotics (Koppel, Fink, Warnell, Stump, & Ribeiro, 2016).

The lack of convexity of Eq. (2.6) means that attaining statistical consistency for supervised dictionary learning methods is much more challenging than for GLMs. To this end, the prevalence of nonconvex stochastic programs arising from statistical learning based on nonlinear transformations of the feature space $\mathcal{X}$ has led to a renewed interest in nonconvex optimization methods through applying convex techniques to nonconvex settings (Boyd & Vanderberghe, 2004). This constitutes a form of simulated annealing (Bertsimas & Tsitsiklis, 1993) with successive convex approximation (Facchinei, Scutari, & Sagratella, 2015). A compelling achievement of this recent surge is the hybrid convex-annealing approach, which has been shown to be capable of finding a global minimizer (Raginsky, Rakhlin, & Telgarsky, 2017). However, the use of these methods for addressing the training of estimators defined by nonconvex stochastic programs requires far more training examples to obtain convergence than convex problems and requires further demonstration in practice.

2.4.1 Gaussian Process Regression

Gaussian process regression (GPR) is a framework for nonlinear, nonparametric, Bayesian inference (Rasmussen, 2004) (kriging; Krige, 1951). GPR is widely used in chemical processing (Kocijan, 2016), robotics (Deisenroth, Fox, & Rasmussen, 2015), and ML (Rasmussen, 2004), among other applications. One of the main drawbacks of GPR is its complexity, which scales cubically N³ with the training sample size N in batch setting.

GPR models the relationship between random variables $\mathbf{x}\in \mathcal{X}\subset {\mathbb{R}}^p$ and $y\in \mathcal{Y}\subset \mathbb{R}$, that is, $ŷ=f(\mathbf{x})$ by function f(x), which should be estimated upon the basis of N training examples $\mathcal{S}={\{{\mathbf{x}}_n,y_n\}}_{n=1}^N$. Unlike in ERM, GPR does not learn this estimator by solving an optimization problem that assesses the quality of its fitness, but instead assumes that this function f(x) follows some particular parameterized family of distributions, in which the parameters need to be estimated (Krige, 1951; Rasmussen, 2004).

In particular, for GPs, a uniform prior on the distribution of ${\mathbf{f}}_{\mathcal{S}}=[f({\mathbf{x}}_n),\dots ,f({\mathbf{x}}_N)]$ is placed as a Gaussian distribution, namely, ${\mathbf{f}}_{\mathcal{S}}\sim \mathcal{N}(0,{\mathbf{K}}_N)$. Here $\mathcal{N}(\mathit{\mu },\mathbf{\Sigma })$ denotes the multivariate Gaussian distribution in N dimensions with mean vector $\mathit{\mu }\in {\mathbb{R}}^N$ and covariance $\mathbf{\Sigma }\in {\mathbb{R}}^{N\times N}$. In GPR, the covariance ${\mathbf{K}}_N={[\kappa ({\mathbf{x}}_m,{\mathbf{x}}_n)]}_{m,n=1}^{N,N}$ is constructed from a distance-like kernel function $\kappa :\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ defined over the product set of the feature space. The kernel expresses some prior about how to measure distance between points, a common example of which is itself the Gaussian, ${[{\mathbf{K}}_N]}_{mn}=\kappa ({\mathbf{x}}_m,{\mathbf{x}}_n)=exp\{-\parallel {\mathbf{x}}_m-{\mathbf{x}}_n{\parallel }^2/c^2\}$ with bandwidth hyperparameter c.

In standard GPR, a Gaussian prior on the noise will be placed that corrupts ${\mathbf{f}}_{\mathcal{S}}$ to form the observation vector y = [y₁, …, y_N], that is, $\mathbb{P}(\mathbf{y}|{\mathbf{f}}_{\mathcal{S}})=\mathcal{N}({\mathbf{f}}_{\mathcal{S}},{\sigma }^2\mathbf{I})$ where σ² is some variance parameter. The prior can be integrated on ${\mathbf{f}}_{\mathcal{S}}$ to obtain the marginal likelihood for y as:

$\begin{array}{l}\hfill \mathbb{P}(\mathbf{y}|\mathcal{S})=\mathcal{N}(0,{\mathbf{K}}_N+{\sigma }^2\mathbf{I})\end{array}$

Upon receiving a new data point x_N+1, a Bayesian inference ${ŷ}_{N+1}$ can be made, not by simply setting a point estimate $f({\mathbf{x}}_{N+1})={ŷ}_{N+1}$. Instead, the entire posterior distribution can be formulated for y_N+1 as:

$\begin{array}{ll}\hfill \mathbb{P}(y_{N+1}|\mathcal{S}\cup {\mathbf{x}}_{N+1})& =\mathcal{N}({\mathit{\mu }}_{N+1|\mathcal{S}},{\mathbf{\Sigma }}_{N+1|\mathcal{S}})\hfill \\ \hfill {\mathit{\mu }}_{N+1|\mathcal{S}}& ={\mathbf{k}}_{\mathcal{S}}({\mathbf{x}}_{N+1}){[{\mathbf{K}}_N+{\sigma }^2\mathbf{I}]}^{-1}{\mathbf{y}}_N\hfill \\ \hfill {\mathbf{\Sigma }}_{N+1|\mathcal{S}}& =\kappa ({\mathbf{x}}_{N+1},{\mathbf{x}}_{N+1})-\kappa ({\mathbf{x}}_{N+1},{\mathbf{x}}_{N+1}){\mathbf{k}}_{\mathcal{S}}({\mathbf{x}}_{N+1}){[{\mathbf{K}}_N+{\sigma }^2\mathbf{I}]}^{-1}{\mathbf{k}}_{\mathcal{S}}+{\sigma }^2\hfill \end{array}$

While this approach to sequential Bayesian inference provides a powerful framework for fitting a mean and covariance envelope around observed data, it requires for each N the computation of ${\mathit{\mu }}_{N+1|\mathcal{S}}$ and ${\mathbf{\Sigma }}_{N+1|\mathcal{S}}$, which crucially depend on computing the inverse of the kernel matrix K_N every time a new data point arrives. It is well known that matrix inversion has cubic complexity $\mathcal{O}(N^3)$ in the variable dimension N, which may be reduced through use of Cholesky factorization (Foster et al., 2009) or subspace projections (Banerjee, Dunson, & Tokdar, 2012) combined with various compression criteria such as information gain (Seeger, Williams, & Lawrence, 2003), mean square error (Smola & Bartlett, 2001), integral approximation for Nyström sampling (Williams & Seeger, 2001), probabilistic criteria (Bauer, van der Wilk, & Rasmussen, 2016; McIntire, Ratner, & Ermon, 2016), and many others (Bui, Nguyen, & Turner, 2017).

2.4.2 Neural Network

While the mathematical formulation of convolutional neural networks and their variants have been around for decades (Haykin, 1998), their use has only become widespread in recent years as computing power and data pervasiveness has made them not impossible to train. Since the landmark work (Krizhevsky, Sutskever, & Hinton, 2012) demonstrated their ability to solve image recognition tasks on much larger scales than previously addressable, they have permeated many fields, such as speech (Graves, Mohamed, & Hinton, 2013), text (Jaderberg, Simonyan, Vedaldi, & Zisserman, 2016), and control (Lillicrap et al., 2015). An estimator function class $\mathcal{F}$ can be defined by the composition of many functions of the form g_k(x) =w_kσ_k(x). σ_k is a nonlinear “activation function,” which can be, for example, a rectified linear unit ${\sigma }_k(a)=max(a,0)$, a sigmoid σ_k(a) = 1/(1 + e^a), or a hyperbolic tangent σ_k(a) = (1 − e^−2a)/(1 + e^−2a). Specifically, for a K-layer convolutional neural network, the estimator is given as:

$\begin{array}{l}\hfill \hat{\mathbf{y}}(\mathbf{x})=g_1\circ g_2\circ \cdots g_K(\mathbf{x})\end{array}$

and typically one tries to make the distance between the target variable and the estimator small by minimizing their quadratic distance:

$\begin{array}{l}\hfill \underset{{\mathbf{w}}_1,\dots ,{\mathbf{w}}_K}{min}{\mathbb{E}}_{\mathbf{x},\mathbf{y}}{(\mathbf{y}-g_1\circ g_2\circ \cdots g_K(\mathbf{x}))}^2\end{array}$

where each w_k is a vector whose length depends on the number of “neurons” at each layer of the network. This operation may be thought of as an iterated generalization of a convolutional filter. Additional complexities can be added at each layer, such as aggregating values output for the activation functions by their maximum (max pooling) or average. But the training procedure is similar: minimize a variant of the highly nonconvex, high-dimensional stochastic program (Eq. 2.10). Due to their high dimensionality, efforts to modify nonconvex stochastic optimization algorithms to be amenable to parallel computing architectures have gained salience in recent years. An active area of research is the interplay between parallel stochastic algorithms and scientific computing to minimize the clock time required for training neural networks—see Lian, Huang, Li, and Liu (2015), Mokhtari, Koppel, Scutari, and Ribeiro (2017), and Scardapane and Di Lorenzo (2017). Thus far, efforts have been restricted to attaining computational speedup by parallelization to convergence at a stationary point, although some preliminary efforts to escape saddle points and ensure convergence to a local minimizer have also recently appeared (Lee, Simchowitz, Jordan, & Recht, 2016); these modify convex optimization techniques, for instance, by replacing indefinite Hessians with positive definite approximate Hessians (Paternain, Mokhtari, & Ribeiro, 2017).

2.4.3 Uncertainty Quantification in Deep Neural Network

In this section we discuss UQ in neural networks through Bayesian methods, more specifically, posterior sampling. Hamiltonian Monte Carlo (HMC) is the best current approach to perform posterior sampling in neural networks. HMC is the foundation from which all other existing approaches are derived. HMC is an MCMC method (Brooks, Gelman, Jones, & Meng, 2011) that has been a popular tool in the ML literature to sample from complex probability distributions when random walk-based first-order Langevin samplers do not exhibit the desired convergence behaviors. Standard HMC approaches are designed to propose candidate samplers for a Metropolis-Hastings-based acceptance scheme with high acceptance probabilities; since calculation of these M-H ratios necessitates a pass through the entire dataset, scalability of HMC-based algorithms has been limited. This has been addressed recently with the development of stochastic approaches, inspired by the now ubiquitous SGD-based ERM algorithms, where we omit the M-H correction step and calculate the Hamiltonian gradients over random mini-batches of the training data (Chen, Fox, & Guestrin, 2014; Welling & Teh, 2011). Further improvements to these approaches have been done by incorporating Riemann manifold techniques to learn the critically important Hamiltonian mass matrices, both in the standard HMC (Girolami & Calderhead, 2011) and stochastic (Ma, Chen, & Fox, 2015; Roychowdhury, Kulis, & Parthasarathy, 2016) settings. These Riemannian approaches have been shown to noticeably improve the acceptance probabilities of samples following the methods of those proposed by Girolami and Calderhead (2011), and dramatically improve the convergence rates in the stochastic formulations as well (Roychowdhury et al., 2016).

Preliminary experiments show that HMC does not work well in practice. Thus one can identify two challenges with posterior sampling using HMC. First, HMC still has a hard time finding the different modes of the distribution (i.e., if it can escape metastable regions of the HMC Markov chain). Second, as stated earlier, the massive dimensionality of deep neural networks make the most of the posterior probability mass that resides in models with poor classification accuracy. Fig. 2.2 shows sampled neural network models as a function of HMC steps for CIFAR100 image classification task (using a LeNet CNN architecture). In as few as 100 HMC steps, the posterior-sampled models are significantly worse than the best models in both training and validation accuracies. Thus HMC posterior sampling is impractical for deep neural networks, even as the HMC acceptance probability is high throughout the experiment.

It is an open avenue of research to explore a few mode exploration fixes. Here, traditional MCMC methods can be used, such as annealing and annealing importance sampling. Less traditional methods are also explored, such as stochastic initialization and model perturbation.

Regarding the important challenge of posterior sampling accurate models in an given posterior mode, mini-batch stochastic gradient Langevin dynamics (SGLD) (Welling & Teh, 2011) is increasingly credited to being a practical Bayesian method to train neural networks to find good generalization regions (Chaudhari et al., 2017), and it may help in improving parallel SGD algorithms (Chaudhari et al., 2017). The connection between SGLD and SGD has been explored in Mandt, Hoffman, and Blei (2017) for posterior sampling in small regions around a locally optimal solution. To make this procedure a legitimate posterior sampling approach, we explore the use of Chaudhari et al.’s (2017) methods to smooth out local minima and significantly extend the reach of Mandt et al.’s (2017) posterior sampling approach.

This smoothing out has connections to Riemannian curvature methods to explore the energy function in the parameter (weight) space (Poole, Lahiri, Raghu, Sohl-Dickstein, & Ganguli, 2016). The Hessian, which is a diffusion curvature, is used by Fawzi, Moosavi-Dezfooli, Frossard, and Soatto (2017) as a measure of curvature to empirically explore the energy function of learned model with regard to examples (the curvature with regard to the input space, rather than the parameter space). This approach is also related to the implicit regularization arguments of Neyshabur, Tomioka, Salakhutdinov, and Srebro (2017).

There is a need to develop an alternative SGD-type method for accurate posterior sampling of deep neural network models that is capable of giving the all-important UQ in the decision-making problem in C3I systems. Not surprisingly a system that correctly quantifies the probability that a suggested decision is incorrect inspires more confidence than a system that incorrectly believes itself to always be correct; the latter is a common ailment in deep neural networks. Moreover, a general practical Bayesian neural network method would help provide robustness against adversarial attacks (as the attacker needs to attack a family of models, rather than a single model), reduce generalization error via posterior-sampled ensembles, and provide better quantification of classification accuracy and root mean square error (RMSE).