11.2.1 Kernelization of the Metric

A common place in clustering algorithms is to compute distances (e.g., Euclidean) between points. If we map data into , we can compute distances therein without explicitly knowing the mapping ϕ or the explicit coordinates of the mapped data points as follows:

(11.1)

Actually, for any positive‐definite kernel, we assume that the mapped data in are distributed in a surface smooth enough to be considered a Riemannian manifold (Burges, 1999). The line element of can be expressed as

(11.2)

where superscripts a and b correspond to the vector space , g_μν is the induced metric, and the surface is parameterized by x^μ. Note that Einstein’s summation convention over repeated indices is used. Computing the components of the (symmetric) metric tensor only needs the kernel function:

(11.3)

For the RBF kernel with a given σ parameter, this metric tensor becomes flat, g_μν = δ_μν/σ², and the squared geodesic distance between ϕ(x) and ϕ(x^′) becomes

(11.4)

Note that the metric solely depends on the original data points yet computed implicitly in a higher dimensional feature space , whose notion of distance is controlled by the parameter σ: the larger σ is the smoother (linear) is the space. Actually, reduces the RBF kernel to approximately compute the Euclidean distance between vectors, which reduces the metric tensor to g_μν = 1.

Kernel Online Anomaly Detector

Let us imagine now that we receive incoming samples online. The problem now is to select the informative samples and discard the anomalous ones. This way the machine will not grow indefinitely and will retain only the information contained in the most useful incoming data points. Studying how rare a sample is becomes very complex with kernels because we do not have the inverse function from Hilbert space to input space to measure normality in physically meaningful units. Remember that, even though we never actually map samples to Hilbert spaces explicitly, the model and the metric are both defined therein. However, we can actually estimate distances in Hilbert spaces implicitly via reproducing kernels. For this, one only has to check if, given a previous set of N examples x_i, a test incoming point x_* is inside a sufficiently big ball of mean :

(11.5)

Note that one has to estimate distances to empirical means in Hilbert spaces. On the one hand, it is straightforward to show that we can compute distances between points using kernels, as before:

(11.6)

On the other hand, one can readily define the distance to the empirical mean in as , and we can compute it via kernels:

(11.7)

Therefore, we only have to test the following condition over x_* to check for largely anomalous points in Hilbert spaces:

(11.8)

Therefore, from an operational point of view, one only has to store a scalar accounting for the maximum similarity (minimum distance) among all the training samples, and then to check if the new example x_* is beyond that threshold θ. This procedure is known as the KOAD, and has been successfully used in several applications, including the detection of anomalies in backbone routers communications (Ahmed et al., 2007).

Difference Kernels for Change Detection

We can use the previous property of kernels to define particular kernels for change detection. Let us now define a temporal classification scenario, in which we aim to detect the presence or absence of changes in the acquisition. This is a standard problem in surveillance applications and change detection from satellite imagery (Camps‐Valls et al., 2008). A standard, extremely simple technique is called the change vector analysis in which a threshold on the difference vector between two consecutive acquisitions t and t − 1 (i.e., d = x^t − x^t−1) is applied to detect changes. This difference vector can be formulated in the kernel feature space by defining a proper kernel mapping function:

We should note that the implementation is easy as it only involves application of kernel functions to define the differential metric among observations. Such a difference kernel can then be included in any supervised or unsupervised kernel classifier.³

11.2.2 Clustering in Feature Spaces

A complementary way to perform clustering in feature spaces is to follow the standard kernelization procedure. Let us introduce in this section the main concepts involved before defining the following kernel methods. Clustering methods try to obtain partitions of the data based on the optimization of a particular objective function, giving as result separation hypersurfaces among clusters. To handle nonlinearly separable clusters, the methods often define multiple centroids to provide a richer description of the dataset at hand.

Notationally, let us consider a set of data points so . The set of centroids for this dataset is called a codebook, and is defined as , with c ≪ N. Each element of , , is called a centroid or codevector. Each centroid defines the so‐called Voronoi region as the set of vectors fulfilling the following condition (Aurenhammer, 1991): . Each Voronoi region is convex and its boundaries are linear segments. A further definition we need is the Voronoi set, , of the centroid , being the subset of for which the centroid is the nearest vector; that is, . A partition of ℝ^d induced by all Voronoi regions is called a Voronoi tessellation or Dirichlet tessellation (Aurenhammer, 1991).

Kernel k‐Means

Let us start by summarizing the formulation and optimization of the standard k‐means, and then we will show how to kernelize it. The goal of the canonical k‐means is to construct a Voronoi tessellation by moving k centroids to the arithmetic mean of their Voronoi sets. To achieve this, the k‐means algorithm searches the elements of that jointly minimize the empirical quantization error

(11.9)

which can be achieved if each centroid fulfills the centroid condition

(11.10)

In the case of using the Euclidean distance, such a condition reduces to

(11.11)

where denotes the cardinality of . The k‐means algorithm is defined by the following steps: (1) choose the number k of clusters; (2) initialize with a set of centroids randomly selected; (3) compute the Voronoi set for each centroid ; (4) move each centroid to the mean of using Equation 11.11; and (5) stop the algorithm if no changes are observed, otherwise go to step 3. Note that the k‐means algorithm is an example of an EM algorithm. Step 3 is the expectation, and step 4 is the maximization. The convergence of the k‐means algorithm is guaranteed since each EM algorithm is always convergent to a local minimum (Bottou and Bengio, 1995).

In order to obtain the kernel k‐means algorithm, we just translate the definitions and concepts before to a feature space. The first step is mapping our dataset to a high‐ dimensional feature space using a nonlinear map ϕ. The codebook is defined in the feature space as V_ϕ = {ϕ(v₁), …, ϕ(v_k)}. We have a Voronoi region in the feature space defined by , and the Voronoi set of the centroid ϕ() defined as . In this case, the Voronoi regions induce a Voronoi tessellation in the feature space.

The steps of the k‐means algorithm in the feature space are the same as the ones described in Section 11.2.1. The only difference is that the maximization step is computed using the following equation:

(11.12)

The problem is that we do not explicitly know ϕ and cannot move the centroid using Equation 11.12. This issue is solved using the representer theorem (Schölkopf and Smola, 2002), so that we can write each centroid in the feature space as a linear combination of the mapped data vectors, . By replacing the expansion into Equation 11.12, and noting that α_ij should be zero if , we obtain

(11.13)

which allows us to compute the closest feature space centroid for each sample, and update the coefficients α_ij accordingly. As in the standard k‐means algorithm, the procedure is repeated until all α_ij do not change significantly.

Kernel Fuzzy Clustering

Fuzzy clustering is essentially dealing with the elusive definition of hard and fuzzy partitions (Pal et al., 2005). Clustering solutions, such those offered by k‐means, do not offer disambiguation of cluster membership of samples that do not fit exactly to one single cluster but to several clusters in different degrees. Let us define a fuzzy‐c partition (or clustering) as

(11.14)

where the set can be defined with the membership matrix U of size c × N, with 2 ≤ c < N and . Each element U_ij is the membership of the jth pattern to the ith cluster, and the constraints ensure that (1) the sum of the membership of a pattern to all clusters is one (probabilistic constraint), and (2) a cluster cannot by empty or contain all samples.

Now, given a codebook and a membership set , the fuzzy c‐means algorithm (Pal et al., 2005) minimizes the functional

(11.15)

subject to , ∀j. The parameter m establishes the fuzziness of the membership. For m = 1 the classic k‐means hard clustering algorithm is obtained, whereas large values of m tend to set all memberships the same, and hence no structure is found on the data.

The functional in Equation 11.15 is minimized defining a Lagrangian function for each sample x_j:

(11.16)

and deriving with respect to and U_ij and setting to zero we obtain the following two equations:

(11.17)

(11.18)

This pair of equations is used with a Picard iteration method (Pal et al., 2005) composed of two steps. In the first step, the membership variables U_ij are kept fixed and the codevectors are optimized. Then, the second step optimizes the membership variables while the codevectors are fixed. These two steps are repeated until the variables change less than a predefined threshold. Equation 11.18 shows that the fuzzy membership of an input sample decreases as the distance increases. The sum in the denominator acts as a normalization factor.

Next, we show two approaches to obtain a kernel version of the fuzzy clustering algorithm. One is based in the kernelization of the metric, and the other directly solves the equations of fuzzy c‐means in feature space.

Kernel Fuzzy Clustering Based on the Metric Kernelization

The functional to minimize is the same as in Equation 11.15 but in a high‐dimensional feature space:

(11.19)

subject to , ∀i. In order to minimize this cost function, we take derivatives with respect to v_j and U_ij. To be able to apply the kernel trick and obtain a practical solution, we explicitly compute the derivatives of the kernel function, which for the RBF kernel the result is as follows:

Computing all the derivatives and equating them to zero we obtain the following equations for the Picard iteration method:

(11.20)

(11.21)

which are now solely based on evaluating kernel functions, and hence the method can be easily implemented.

Kernel Fuzzy Clustering in Feature Space

The functional to minimize is shown in Equation 11.19. Instead of obtaining a solution taking derivatives using and U_ij, now we use the representer theorem to express ϕ() as a linear combination of samples in feature space; that is, . This will allow us to compute the distance appearing in Equation 11.19 just in terms of the kernel function as in Equation 11.1. Therefore, let us rewrite the functional as

(11.22)

where k_j is the jth row of the kernel; that is, k_j := [K(x_j, x₁), …, K(x_j, x_N)]^T, and β = [β₁, …, β_N] are the weights for the ϕ(v) codevector, and K is the whole kernel matrix. This functional can be derived with respect to the variables β_i and U_ij, obtaining the equations we need for the Picard iteration method:

(11.23)

(11.24)

There is an alternative pair of equivalent equations that we can obtain using the following reasoning. Deriving the functional in Equation 11.19 directly with respect to ϕ() we will obtain, similarly to Equation 11.17, the expansion

(11.25)

where we have defined a_i as

(11.26)

With Equations 11.26 and 11.25 we can rewrite Equation 11.24 as

(11.27)

where u_i := [(u_i1)^m, …, (u_in)^m]^T. It is clear that Equations 11.24 and 11.27 are equivalent, noting that, by definition, . However, the Picard iteration method is easier to implement using Equations 11.26 and 11.27.

Kernel Self‐Organizing Maps

A self‐organized map (SOM) (Kohonen, 1990) is a type of artificial NN trained to obtain a low‐dimensional (most of the times 2D) representation of the input data. The training phase is unsupervised where SOM defines a function that tries to preserve the topological properties of the input dataset. SOMs are typically used to obtain low‐dimensional visualizations of high‐dimensional data. As for other NNs, an SOM consists of a series of interconnected nodes or neurons. Each node has a weight vector of the same dimension as the input data samples, and a location in the map space, while each vector of the input space is placed on the map space by finding the closest/nearest node in the map space.

Let us define our coodebook, denoted , as the set of neurons (centroids) that will compose the map. The first step of the training phase is to randomly select the weights of the neurons in . Alternatively, Kohonen (1990) showed that it is possible to speed up the training phase by evenly sampling the subspace spanned by the two largest principal component eigenvectors, instead of randomly selecting the first neurons’ weights. The second step is to take an input sample x from and obtain the nearest neuron using a distance function d (Euclidean of Manhattan distances are the most often used). The shortest distance would be the one that solves . Then the weights of the neurons are adapted using a standard gradient descent strategy:

(11.28)

where h is a decreasing function of the distance d; for example, . Here, σ(t) is a decreasing function of t, , ε(t) is also a decreasing function of t, , and where the subscripts “i” and “f” indicate the initial and final values respectively. The adaptation of neurons v_j in Equation 11.28 is repeated until a predefined number of iterations is achieved; that is, t = t_max.

In order to reformulate the SOM in the feature space, we need to first define our set of initial neurons ϕ(v_j). Since we do not know ϕ explicitly, we use the representer theorem to write each neuron as a combination of mapped input samples:

(11.29)

and we randomly initialize the coefficients α_jl. Then, given an input sample ϕ(x_i), we need to compute the nearest neuron to it:

which, after applying the kernel trick, translates into

(11.30)

Finally, the neurons in the feature space are updated as

(11.31)

which according to Equation 11.29 can be expressed as

(11.32)

from which we can now obtain the update rule for α_jl as follows:

(11.33)

Note that the updating rule can be obtained iteratively until convergence.

11.3.1 Support Vector Domain Description

A different problem statement for classification is given by the SVDD (Tax and Duin, 1999). The SVDD is a method to solve one‐class problems, where one tries to describe one class of objects, distinguishing them from all other possible objects.

The problem notation is defined as follows. Let be a dataset belonging to a given class of interest. The purpose is to find a minimum volume hypersphere in a high‐dimensional feature space , with radius R > 0 and center , which contains most of these data objects (Figure 11.1a). Since the training set may contain outliers, a set of slack variables ξ_i ≥ 0 is introduced, and the problem becomes

(11.34)

constrained to

(11.35)

(11.36)

where parameter C controls the trade‐off between the volume of the hypersphere and the permitted errors. Parameter ν, defined as ν = 1/(NC), can be used as a rejection fraction parameter to be tuned, as noted by Schölkopf et al. (1999).

The dual functional is a QP problem that yields a set of Lagrange multipliers (α_i) corresponding to constraints in Equation 11.35. When free parameter C is adjusted properly, most of the α_i are zero, giving a sparse solution. The Lagrange multipliers are also used to calculate the distance from a test point to the center R(x_*):

(11.37)

which is compared with ratio R. Unbounded support vectors are those samples x_i satisfying , while bounded support vectors are samples whose associated α_i = C, which are considered outliers.

11.3.2 One‐Class Support Vector Machine

In the OC‐SVM, instead of defining a hypersphere containing all examples, a hyperplane that separates the data objects from the origin with maximum margin is defined (Figure 11.1b). It can be shown that, when working with normalized data and the RBF Gaussian kernel, both methods yield the same solution (Schölkopf et al., 1999).

Notationally, in the OC‐SVM, we want to find a hyperplane w which separates samples x_i from the origin with margin ρ. The problem thus becomes

(11.38)

constrained to

(11.39)

(11.40)

The problem is solved through its Lagrangian dual introducing a set of Lagrange multipliers α_i. The margin ρ can be computed as .

11.3.3 Relationship Between Support Vector Domain Description and Density Estimation

Let us now point out the connection between pdf estimation and the previous one‐class kernel classifiers. The goal of kernel density estimation (KDE) is to estimate the unknown pdf p(x) given N i.i.d. samples {x₁, …, x_N} drawn from it. The kernel (Parzen) estimate of the pdf using an arbitrary kernel function K_σ(⋅) parameterized with a length‐scale parameter σ is given by

(11.41)

where K is typically a Gaussian kernel, and the hyperparameters of the model (e.g., the length scale or kernel width) can be obtained via ML estimation or fixed through ad hoc rule of thumb rules, such as Silverman’s rule. Other kernel functions can be used: uniform, normal, triangular, bi‐weighted, tri‐weighted, just to name a few. The Epanechnikov kernel, for example, is optimal in an MSE sense. The interested reader can explore the MATLAB function ksdensity.m and the MATLAB KDE toolbox available oin the book’s web page.

Density estimates can be used to characterize distributions and to design anomaly detection schemes. Note, for instance, that once is obtained, an anomaly detector can be readily defined simply as

(11.42)

Now, by plugging the previous Gaussian kernel estimate in here and defining a centroid in the feature space as the mean of the mapped samples, a KDE‐based anomaly detector can be readily derived by simply kernelizing the distance between a test point x_* and all the training points (see Section 11.2.1):

(11.43)

Note that definition of SVDD seen previously in Equations 11.34 and 11.35 leads to an SVDD anomaly detector in the form

(11.44)

where α_i > 0 are support vectors. Comparing Equation 11.43 with Equation 11.44 we see they are very similar, except that the SVDD anomaly detector places unequal weights on the training points x_i. In other words, while the kernel KDE works as an unsupervised method where the centroid is placed at , the SVDD is a supervised method that uses training (labeled) samples to place the centroid at . Figure 11.2 shows a toy example comparing the boundaries obtained by the SVDD (centroid at a) and KDE (centroid at μ_ϕ).

11.3.4 Semi‐supervised One‐Class Classification

Exploiting unlabeled information in one‐class classifiers can be done via semi‐supervised versions of the OC‐SVM. A particularly convenient instantiation is the biased‐SVM (b‐SVM) classifier, which was originally proposed by Liu et al. (2003) for text classification using only target and unlabeled data. The underlying idea of the method lies on the assumption that if the sample size is large enough, minimizing the number of unlabeled samples classified as targets while correctly classifying the labeled target samples will give an accurate classifier.

Let us consider again the dataset made up of l labeled samples and u unlabeled samples (N = l + u). The l labeled samples all belong to the same class: the target class. Concerning unlabeled samples, they are treated by the algorithm as being all outliers, although their class is unknown. This characteristic makes b‐SVM a sort of semi‐supervised classifier. Under these assumptions, the b‐SVM formulation is defined as

(11.45)

subject to

(11.46)

where ξ_i ≥ 0 are slack variables, and C_t and C_o are the costs assigned to errors on target and outlier (unlabeled) classes, respectively. The two cost values should be adjusted to fulfill the goal of classifying the target class correctly while at the same time trying to minimize the number of unlabeled samples classified as target class. To achieve this goal, C_t should have a large value, as initially we trust our labeled training set, and C_o a small value, because it is unknown whether the samples unlabeled are actually targets or outliers.

11.4.1 Kernel Orthogonal Subspace Projection

The OSP algorithm (Harsanyi and Chang, 1994) tries to maximize the SNR in the subspace orthogonal to the background subspace. OSP has been widely adopted in the community of automatic target recognition because of its simplicity (only depends on the noise second‐order statistics) and its good behavior. In the standard formulation of the OSP algorithm (Harsanyi and Chang, 1994), a linear mixing model is assumed for each d‐dimensional observed point r as follows:

where M is the matrix of size (d × p) containing the p endmembers (i.e., pure constituents of the observed mixture) contributing to the mixed point r, contains the weights in the mixture (sometimes called abundance vector), and stands for an additive zero‐mean Gaussian noise vector. In order to identify a particular desired point d in a data set (e.g., a pixel in an image) with corresponding abundance α_p, the earlier expression can be organized by rewriting the M matrix in two submatrices M = [U|d] and α = [γ, α_p]^T, so that

(11.47)

where the columns of U represent the undesired points and γ contains their abundances. The OSP operator that maximizes the SNR performs two steps. First, an annihilating operator rejects the background points so that only the desired point should remain in the data subspace. This operator is given by the (d × d) matrix , where U^† is the right Moore–Penrose pseudoinverse of U. The second step of the OSP algorithm is represented by the filter w that maximizes the SNR of the filter output; that is, the matched filter w = kd, where k is an arbitrary constant (Harsanyi and Chang, 1994; Kwon and Nasrabadi, 2005b). The OSP detector is given by  = d^Tr, and the output of the OSP classifier is

(11.48)

By using the singular‐value decomposition of U = BΣA^T, where B is the eigenvector of UU^T = BΣΣ^TB^T and A is the eigenvector of U^TU = AΣ^TΣA. The annihilating projector operator becomes , where the columns of B are obtained from the eigenvectors of the covariance matrix of the background samples. This finally yields the expression

(11.49)

Figure 11.3 shows the effect of the OSP algorithm on a toy data set.

A nonlinear kernel‐based version of the OSP algorithm can be devised by defining a linear OSP in an appropriate Hilbert feature space where samples are mapped to through a kernel mapping function ϕ(⋅). Similar to the previous linear case, let us define the annihilating operator now in the feature space as  = I_ϕ − B_ϕ. Then, the output of the OSP classifier in the feature space is now trivially given by

(11.50)

The columns of matrix B_ϕ (e.g., denoted as b_ϕ^j) are the eigenvectors of the covariance matrix of the undesired background signatures. Clearly, each eigenvector in the feature space can be expressed as a linear combination of the input vectors in the feature space transformed through the function ϕ(⋅). Hence, one can write b_ϕ^j = Φ_bβ^j – where Φ_b contains the mapped background points X_b, and β^j are the eigenvectors of the (centered) Gram matrix , whose entries are K_bb(b_i, b_j) = ϕ(b_i)^Tϕ(b_j), and b_i are background points.⁴ The kernelized version in Equation 11.50 is given (Kwon and Nasrabadi, 2005b) by

(11.51)

where k are column vectors referred to as the empirical kernel maps and the subscripts indicate the elements entering the corresponding kernel function: d for the desired target, r the observed point, and subscript m indicates the concatenation of both; that is, X_m = [X_b|d]. Also is the matrix containing the eigenvectors β^j described earlier; and ? is the matrix containing the eigenvectors υ^j, similar to β^j yet obtained from the centered kernel matrix K_{m, m} thus working with the expanded matrix X_m. Listing 11.1 illustrates the simplicity of the code for the KOSP method.

11.4.2 Kernel Spectral Angle Mapper

The spectral angle mapper (SAM) is a method for directly comparing image spectra (Kruse et al., 1993). Since its seminal introduction, SAM has been widely used in chemometrics, astrophysics, imaging, hyperspectral image analysis, industrial engineering, and computer vision applications (Ball and Bruce 2007; Cho et al. 2010; García‐Allende et al. 2008; Hecker et al. 2008), just to name a few. The measure achieved widespread popularity thanks to its implementation in software packages, such as ENVI or ArcGIS. The reason is simple: SAM is invariant to (unknown) multiplicative scalings of spectra due to differences in illumination and angular orientation (Keshava, 2004). SAM is widely used for fast spectral classification, as well as to evaluate the quality of extracted endmembers, and the spectral quality of an image compression algorithm.

The popularity of SAM is mainly due to its simplicity and geometrical interpretability. However, the main limitation of the measure is that it only considers second‐order angle dependencies between spectra. In the following, we will see how to generalize the SAM measure to the nonlinear case by means of kernels (Camps‐Valls and Bruzzone, 2009). This short note aims to characterize KSAM theoretically, and to show its practical convenience over the widespread linear counterpart. KSAM is very easy to compute, and can be used in any kernel machine. KSAM also inherits all properties of the original distance, is a valid reproducing kernel, and is universal. The induced metric by the kernel will be easily derived by traditional tensor analysis, and tuning the kernel hyperparameter of the squared exponential kernel function used is shown to be stable. KSAM is tested here in a target detection scenario for illustration purposes. The spatially explicit detection and metric maps give us useful information for semiautomatic anomaly/target detection.

Given two d‐dimensional samples, , the SAM measures the angle θ between them:

(11.52)

KSAM requires the definition of a feature mapping ϕ(⋅) to a Hilbert space endorsed with the kernel reproducing property. Now, if we simply map the original data to with a mapping , the SAM can be expressed in as

(11.53)

Having access to the coordinates of the new mapped data is not possible unless one explicitly defines the mapping function ϕ. It is possible to compute the new measure implicitly via kernels:

(11.54)

Popular examples of reproducing kernels are the linear kernel K(x, z) = x^Tz, the polynomial K(x, z) = (x^Tz + 1)^d, and the RBF kernel . In the linear kernel, the associated RKHS is the space ℝ^d itself and KSAM reduces to the standard linear SAM. In polynomial kernels of degree d, KSAM effectively only compares moments up to order d. For the Gaussian kernel, the RKHS is of infinite dimension and KSAM measures higher order feature dependences. In addition, note that for RBF kernels, self‐similarity K(x, x) = 1, and thus the measure simply reduces to , 0 ≤ θ_K ≤ π/2. Following the code in Listing 11.1, we show a simple (just one line) snippet of KSAM in Listing 11.2.

11.5.1 Linear Anomaly Change Detection Algorithms

A family of linear ACD can be framed using solely cross‐covariance matrices, as illustrated in Theiler et al. (2010). Notationally, given two samples , the decision of anomalousness is given by

where , , and , , and C_z = Z^TZ, C_x = X^TX, and C_y = Y^TY are the estimated covariance matrices with the available data. Parameters β_x, β_y ∈{0, 1} and the different combinations give rise to different anomaly detectors (see Table 11.1). These methods and some variants have been widely used in image analysis settings because of their simplicity and generally good performance (Chang and Lin 2002; Kwon et al. 2003; Reed and Yu 1990).

However, these methods are hampered by a fundamental problem: the assumption of Gaussianity that is implicit in the formulation. Accommodating other data distributions may not be easy in general. Theiler et al. (2010) introduced an alternative ACD to cope with EC distributions (Cambanis et al., 1981): roughly speaking, the idea is to model the data using the multivariate Student distribution. The formulation introduced in (Theiler et al., 2010) gives rise to the following decision of EC anomalousness:

(11.55)

where ν controls the shape of the generalized Gaussian: for the solution approximates the Gaussian and for ν → 2 it diverges.

11.5.2 Kernel Anomaly Change Detection Algorithms

Note that the previous methods solely depend on estimating covariance matrices with the available data, and use them as a metric for testing. The methods are fast to apply, delineate pointwise nonlinear decision boundaries, but still rely on second‐order statistics. We solve the issue as usual using reproducing kernel functions.

For the sake of simplicity, we just show how to estimate the anomaly term ξ_x in the Hilbert space, . The other terms are derived in the same way. Notationally, let us map all the observations to a higher dimensional Hilbert feature space by means of the feature map ϕ : x → ϕ(x). The mapped training data matrix is now denoted as . Note that one could think of different mappings: ϕ : x → ϕ(x) and ψ : y → ψ(y). However, in our case, we are forced to consider mapping to the same Hilbert space because we have to stack the mapped vectors to estimate ξ_z; that is, . The mapped training data to Hilbert spaces are denoted as respectively. In order to estimate for a test example x_*, we first map the test point ϕ(x_*) and then apply

Note that we do not have access to either the samples in the feature space or the covariance. We can, nevertheless, estimate the eigendecomposition of the covariance matrix in kernel feature space; that is, , where Λ_ℋ is a diagonal matrix containing the eigenvalues and V_ℋ contains the eigenvectors in columns. It is worth noting that the maximum number of eigenvectors equals the number of examples used N. Plugging the eigendecomposition of the covariance pseudoinverse , and after some linear algebra, one can express the term as

We can replace all dot products by reproducing kernel functions using the representer theorem (Kimeldorf and Wahba, 1971; Shawe‐Taylor and Cristianini, 2004), and hence , where contains the similarities between x_* and all training points X; that is, k_* := [K(x_*, x₁), …, K(x_*, x_N)]^T, and stands for the kernel matrix containing all training data similarities. The solution may need extra regularization , . Therefore, in the kernel case, the decision of anomalousness is given by

where now , , and .

Equivalently, including these expressions in Equation 11.55, one obtains the EC kernel versions :

(11.56)

In the case of β_x = β_y = 0, the algorithm reduces to kernel RX which was introduced in Kwon and Nasrabadi (2005c). As in the linear case, one has to center the data before computing either covariance or Gram (kernel) matrices. This is done via the kernel matrix operation , where H_ij = δ_ij − (1/n), and δ represents the Kronecker delta δ_{i, j} = 1 if i = j and zero otherwise.

Two parameters need to be tuned in the kernel versions: the regularization parameter λ and the kernel parameter σ. In the examples, we will use two different isotropic kernel functions, : the standard Gaussian kernel d_ij = ∥x_i − x_j∥, and the SAM kernel . We should note that, when a linear kernel is used, , the proposed algorithms reduce to the linear counterparts proposed in Theiler et al. (2010). Working in the dual (or Q‐mode) with the linear kernel instead of the original linear versions can be advantageous only in the case of higher dimensionality than available samples, d > N.

11.6.1 Distribution Embeddings

Recall that our current motivation is to test statistical differences between distributions with kernels. Therefore, it is natural to ask ourselves about which are the appropriate descriptors of distributions embedded into possibly infinite‐dimensional Hilbert spaces. The distributions’ components therein can be described by the so‐called covariance operators and mean elements (Eric et al. 2008; Fukumizu et al. 2007; Harchaoui et al. 2013; Vakhania et al. 1987).

Notationally, let us consider a random variable x taking values in and a probability distribution ℙ. The mean element μ_ℙ associated with x is the unique element of the RKHS , such that, for all , we obtain

and the covariance operator attached to x fulfills

In the empirical case, we are given a set of i.i.d. samples {x₁, …, x_N} drawn from ℙ, so we have to replace the previous population statistics by their empirical approximations to obtain the empirical mean

and the empirical covariance operator :

Interestingly, it can be shown that, for a large class of kernels, an embedding function m(⋅) that maps data into the kernel feature mean is injective (Harchaoui et al., 2013). Now, if we consider two probability distributions ℙ and ℚ on , and for all the equality holds, then for dense kernel functions K. This property has been exploited to define independence tests and hypothesis testing methods based on kernels, since it ensures that two distributions have the same RKHS mean iff they are the same, as we will see in Chapter 12.

11.6.2 Maximum Mean Discrepancy

Among several hypothesis testing algorithms, such as the kernel Fisher discriminant analysis and the kernel density‐ratio test statistic revised in Harchaoui et al. (2013), a simple and effective one is the maximum mean discrepancy (MMD) statistic. Gretton et al. (2005b) introduced the MMD statistic for comparing the means of two samples in kernel feature spaces; see Figure 11.11. Notationally, we are given samples from a so‐called source distribution, ℙ_x, and samples drawn from a second target distribution, ℙ_y. MMD reduces to estimate the distance between the two sample means in an RKHS where data are embedded:

This estimate can be shown to be equivalent to

where

and L_ij = 1/N² if x_i and x_j belong to the source domain, if x_i and x_j belong to the target domain, and L_ij = −1/(NM) if x_i and x_j belong to the cross‐domain. MMD tends asymptotically to zero when the two distributions ℙ_x and ℙ_y are the same.

It is worth mentioning that MMD was concurrently introduced in the field of signal processing under the formalism of information‐theoretic learning (Principe, 2010). In such a framework, it can be shown that MMD corresponds to a Euclidean divergence. This can be shown easily. Let us assume two distributions p(x) and q(x) with N₁ and N₂ samples. The Euclidean divergence between them can be computed by exploiting the relation to the quadratic Rényi entropies (see Chapter 2 of Principe (2010)):

where G(⋅) denotes Gaussian kernels with standard deviation σ. This divergence reduces to compute the norm of the difference between the means in feature spaces:

which is equivalent to the MMD estimate introduced from the theory of covariance operators in Gretton et al. (2005b).

11.6.3 One‐Class Support Measure Machine

Let us give now an example of a kernel method for anomaly detection based on RKHS embeddings. A field of anomaly detection that has captured the attention recently is the so‐called grouped anomaly detection. The interest here is that the anomalies often appear not only in the data themselves, but also as a result of their interactions. Therefore, instead of looking for pointwise anomalies, here one is interested in groupwise anomalies. A recent method, based on SVC, was been introduced by Muandet and Schölkopf (2013). An anomalous group could be defined as a group of anomalous samples, which is typically easy to detect. However, anomalous groups are often more difficult to detect because of their particular behavior as a core group and the higher order statistical relations among them. Importantly, detection can only be possible in the space of distributions, which can be characterized by recent kernel methods relying on concepts of RKHS embeddings of probability distributions, mainly mean elements and covariance operators. The method presented therein is called the one‐class support measure machine (OC‐SMM) and makes uses of the mean embedding representation, which is defined as follows.

Let denote an RKHS of functions endorsed with a reproducing kernel . The kernel mean map from the set of all probability distributions into is defined as

Assuming that K(x, ⋅) is bounded for any , we can show that for any ℙ, letting , the , for all .

The primal optimization problem for the OC‐SMM can be formulated in an analogous way to the OC‐SVM (or ν‐SVM):

(11.59)

constrained to

(11.60)

(11.61)

where the meaning of the hyperparameters stands the same, but they are now instead associated with distributions (note the appearance of the mean distribution appears as a constraint in Equation 11.60). By operating in the same way, one obtains that the dual form is again a QP problem that depends on the inner product that can be computed using the mean map kernel function:

where are the samples belonging to distribution i, and N_i represents its cardinality. Links to MATLAB source code for this method are available on the book’s web page.

11.7.1 Example on Kernelization of the Metric

Let us see the relation described in this chapter for kernelization of the metric in a simple code example, given in Listing 11.3. We generate the well‐known Swiss roll dataset, then compute both the Euclidean distances in the original space and the Hilbert space (with a specific σ parameter for the kernel).

Figure 11.4 illustrates the behavior of the distance values in the input space against the distances computed in the Hilbert space. We can see how some of the distances have decreased values with respect to the input space in the range [0, 1/2] and the remaining distances have increased in the Hilbert space. The shape of the curve shows the nonlinear relation between distances.

11.7.2 Example on Kernel k‐Means

The code in Listing 11.4 runs the k‐means function of MATLAB and an implementation of kernel k‐means for the problem of concentric rings. Figure 11.5 illustrates the final solution of both methods: k‐means could not achieve a good solution (left) compared to kernel k‐means which finally converges to the correct solution (right).

11.7.3 Domain Description Examples

This section compares different standard one‐class classifiers and kernel detectors: Gaussian (GDD), mixture of Gaussians (MoGDD), k‐NN (KnnDD), and the SVDD (with the RBF kernel). All one‐class domain description classifiers have a parameter to adjust, which is the fraction rejection, that controls the percentage of target samples the classifier can reject during training. Some other parameters need to be tuned depending on the classifier. For instance, the Gaussian classifier has a regularization parameter in the range [0, 1] to estimate the covariance matrix, using all training samples or only diagonal elements.

With regard to the mixture of Gaussian classifier, four parameters must be adjusted: the shape of the clusters to estimate the covariance matrix (e.g., full, diagonal, or spherical), a regularization parameter in the range [0, 1] used in the estimation of the covariance matrices, the number of clusters used to model the target class, and the number of clusters to model the outlier class. The most important advantage of this classifier with respect to the Gaussian classifier, apart from the obvious improvement of modeling a class with several Gaussian distributions, is the possibility of using outliers information when training the classifier. This allows the tracing of a more precise boundary around the target class, improving classification results notably. However, having a total of five parameters to adjust constitutes a serious drawback for this method, making it difficult to obtain a good working model.

With respect to the k‐NN classifier, only the number of k neighbors used to compute the distance of each new sample to its class must be tuned. Finally, for the SVDD, the width of the RBF kernel (σ) has to be adjusted. In all the experiments, except the last one, σ is selected among the following set of discrete values between 5 and 500. It is worth stressing here that the SVDD is one of the methods among those considered, together with the mixture of Gaussians, that allows one to use outliers information to better define the target class boundary. In addition, it has the important advantage that only two free parameters have to be adjusted, thus making it relatively easier to define a good model.

In all the experiments, 30% of the samples available are used to train each classifier. In order to adjust free parameters, a cross‐validation strategy with four folds is employed. Once the classifier is trained and adjusted, the final test is done using the remaining 70% of the samples. In all our experiments, we used the dd_tools and the libSVM software packages.

Two different synthetic problems are tested here. In each problem, binary classification is addressed, thus having two sets of targets and outliers. Each class contains 500 samples generated from different distributions. The two problems analyzed are mixture of two Gaussian distributions and a mixture of Gaussian and logarithmic distributions; both of them are strongly overlapped. Our goal here is testing the effectiveness of the different methods with standard and simple models but in very critical conditions on the overlapping of class distributions.

In order to measure the capability of each classifier to accept targets and reject outliers, the confusion matrix for each problem is obtained, and the kappa coefficient (κ) is estimated, which gives a good trade‐off between the capability of the classifier to accept its samples (targets) and reject the others (outliers). Table 11.2 shows the results for the tests, and Figure 11.6 shows graphical representations of the classification boundary defined by each method. In each plot, the classifier decision boundary levels is represented with a blue curve. Listing 11.5 shows the code that has been used for generating these results. Functions getsets.m, train_basic.m, and predict_basic.m can be seen in the code (not included here for brevity).

Several conclusions can be obtained from these tests. First, MoGDD and SVDD obtain the highest accuracies in our problems. When mixing two Gaussians, none of the classifiers shows a good behavior, as in our synthetic data the distributions are strongly overlapped. This is a common situation in the remote‐sensing field when trying to classify classes very similar to each other. Mixture of overlapped Gaussian and logarithmic features is a difficult problem. In this synthetic example, we can see that the SVDD performs slightly better, since it does not assume any a priori data distribution.

11.7.4 Kernel Spectral Angle Mapper and Kernel Orthogonal Subspace Projection Examples

The following two experiments have the aim of comparing KSAM and KSOM (and also their linear versions) in terms of real data problems. In the former, a QuickBird image of a residential neighborhood of Zürich, Switzerland, is used for illustration purposes. The image size is (329 × 347) pixels. A total of 40 762 pixels were labeled by photointerpretation and assigned to nine land‐use classes (see Figure 11.8). Four target detectors are compared in the task of detecting the class “Soil”: OSP (Harsanyi and Chang, 1994), its kernel counterpart KOSP (Kwon and Nasrabadi, 2007), standard SAM (Kruse et al., 1993), and the extension KSAM.

Figure 11.7 shows the receiver operating characteristic (ROC) curves and the area under the ROC curves (AUC) as a function of the kernel length‐scale parameter σ. KSAM shows excellent detection rates, especially remarkable in the inset plot (note the logarithmic scale). Perhaps more importantly, the KSAM method is relatively insensitive to the selection of the kernel parameter compared with the KOSP detector, provided that a large enough value is specified.

The latter experiments allow us to use a traditional prescription to fix the RBF kernel parameter σ for both KOSP and KSAM as the mean distance among all spectra, d_M. Note that after data standardization and proper scaling, this is a reasonable heuristic σ ≈ d_M = 1. The thresholds were optimized for all methods. OSP returns a decision function strongly contaminated by noise, while the KOSP detector results in a correct detection. Figure 11.8 shows the detection maps and the metric learned. The (linear) SAM gives rise to very good detection but with strong false alarms in the bottom left side of the image, where the roof of the commercial center saturates the sensor and thus returns a flat spectrum for its pixels in the morphological features. As a consequence, both the target and the roof vectors have flat spectra and their spectral angle is almost null. KSAM can efficiently cope with these (nonlinear) saturation problems. In addition, the metric space derived from the kernel suggests high discriminative (and spatially localized) capabilities.

11.7.5 Example of Kernel Anomaly Change Detection Algorithms

In this section we show the usage of the proposed methods in several simulated and real examples of pervasive and anomalous changes. Special attention is given to detection ROC curves, robustness to number of training samples, low‐rank approximation of the solution, and the estimation of Gaussianity in kernel feature space. Comparisons between the hyperbolic (HACD), elliptical (EC), kernelized (K‐HACD), and elliptical kernelized (K‐EC‐HACD) versions of the algorithms are included. Results can be reproduced using the script demoKACD.m available in the book’s repository.

This example follows the simulation framework used in Theiler (2008). The dataset (see Figure 11.9) is an image acquired over the Kennedy Space Center, Florida, on March 23, 1996, by the Airbone Visible Infrared Imaging Spectrometer (AVIRIS). The data were acquired from an altitude of 20 km and have a spatial resolution of 18 m. After removing low SNR and water absorption bands, a total of 176 bands remain for analysis. More information can be found at http://www.csr.utexas.edu/. To simulate a pervasive change, global Gaussian noise, , was added to all the pixels in the image to produce a second image. Then, anomalous changes are produced by scrambling the pixels in the target image. This yields anomalous change pixels whose components are not individually anomalous.

In all experiments, we used hyperbolic detectors (i.e., β_x = β_y = 1), as they generalize RX and chronocrome ACD algorithms, and have shown improved performance (Theiler et al., 2010). In this example, we use the SAM kernel, which is more appropriate to capture hyperspectral pixel similarities than the standard RBF kernel. We tuned all the parameters involved (estimated covariance C_z and kernel K_z, ν for the EC methods, length‐scale σ parameter for the kernel versions) through standard cross‐validation in the training set, and show results on the independent test set. We used λ = 10⁻⁵/N, where N is the number of training samples, and the σ kernel length‐scale parameter is tuned in the range of 0.05–0.95 percentiles of the distances between all training samples, d_ij.

Figure 11.10 shows the ROC curves obtained for the linear ACD and KACD methods. The dataset was split into small training sets of only 100 and 500 pixels, and results are given for 3000 test samples. The results show that the kernel versions improve upon their linear counterparts (between 13–26% in Gaussian and 1–5% in EC detectors). The EC variants outperform their Gaussian counterparts, especially in the low‐sized training sets (+30% over HACD and +18% over EC‐HACD in AUC terms). Also noticeable is that results improve for all methods when using 500 training samples. The EC‐HACD is very competitive compared with the kernel versions in terms of AUC, but still K‐EC‐HACD leads to longer tails of false‐positive detection rates (right figure, inset plot in log‐scale).

11.7.6 Example on Distribution Embeddings and Maximum Mean Discrepancy

Let us exemplify the use of the concept of distribution embeddings and MMD in a simple example comparing two distributions ℙ_x and ℙ_y. We draw samples from (i) two Gaussians with different means, (ii) Gaussians with the same means but different variance, and (iii) from a Gaussian and a Laplace distributions. A code snippet is given in Listing 11.6 illustrating the ability of MMD to detect such differences. The results obtained are shown in Figure 11.11.