3. Kernel Methods#

In the following, we will discuss the use of kernels to compare time series. A kernel \(k(\cdot, \cdot)\) is such that there exists an unknown map \(\Phi\) such that:

\[k(\mathbf{x}, \mathbf{y}) = \left\langle \Phi(\mathbf{x}), \Phi(\mathbf{y}) \right\rangle_{\mathcal{H}}\]

i.e. \(k(\cdot, \cdot)\) is the inner product between \(\mathbf{x}\) and \(\mathbf{y}\) in some (unknown) embedding space \(\mathcal{H}\). In practice, \(k(\mathbf{x}, \mathbf{y})\) will be large when \(\mathbf{x}\) and \(\mathbf{y}\) are similar and close to 0 when they are very dissimilar.

A large number of kernel methods from the machine learning literature rely on the so-called kernel trick, that consists in performing computations in the embedding space \(\mathcal{H}\) without ever actually performing any embedding. As an example, one can compute distance between \(\mathbf{x}\) and \(\mathbf{y}\) in \(\mathcal{H}\) via:

\[\begin{split}\| \Phi(\mathbf{x}) - \Phi(\mathbf{y})\|_\mathcal{H}^2 &= \left\langle \Phi(\mathbf{x}) - \Phi(\mathbf{y}), \Phi(\mathbf{x}) - \Phi(\mathbf{y}) \right\rangle_{\mathcal{H}} \\ &= \left\langle \Phi(\mathbf{x}), \Phi(\mathbf{x}) \right\rangle_{\mathcal{H}} + \left\langle \Phi(\mathbf{y}), \Phi(\mathbf{y}) \right\rangle_{\mathcal{H}} - 2 \left\langle \Phi(\mathbf{x}), \Phi(\mathbf{y}) \right\rangle_{\mathcal{H}} \\ &= k(\mathbf{x}, \mathbf{x}) + k(\mathbf{y}, \mathbf{y}) - 2 k(\mathbf{x}, \mathbf{y})\end{split}\]

Such computations are used, for example, in the kernel-\(k\)-means algorithm (see below).

3.1. Global Alignment Kernel#

The Global Alignment Kernel (GAK) is a kernel that operates on time series.

The unnormalized GAK is defined, for a given bandwidth \(\sigma\), as:

\[k(\mathbf{x}, \mathbf{y}) = \sum_{\pi \in \mathcal{A}(\mathbf{x}, \mathbf{y})} \prod_{i=1}^{ | \pi | } \exp \left( - \frac{ \left\| x_{\pi_1(i)} - y_{\pi_2{j}} \right\|^2}{2 \sigma^2} \right)\]

where \(\mathcal{A}(\mathbf{x}, \mathbf{y})\) is the set of all possible alignments between series \(\mathbf{x}\) and \(\mathbf{y}\).

Note that the function gak is normalized in tslearn: it corresponds to the quotient

\[\text{gak}(\mathbf{x}, \mathbf{y}) = \frac{k(\mathbf{x}, \mathbf{y})}{\sqrt{k(\mathbf{x}, \mathbf{x})k(\mathbf{y}, \mathbf{y})}}\]

This normalization ensures that \(\text{gak}(\mathbf{x}, \mathbf{x})=1\) for all \(\mathbf{x}\) and \(\text{gak}(\mathbf{x}, \mathbf{y}) \in [0, 1]\) for all \(\mathbf{x}, \mathbf{y}\).

It is advised in [1] to set the bandwidth \(\sigma\) as a multiple of a simple estimate of the median distance of different points observed in different time-series of your training set, scaled by the square root of the median length of time-series in the set. This estimate is made available in tslearn through sigma_gak:

from tslearn.metrics import gak, sigma_gak

sigma = sigma_gak(X)
k_01 = gak(X[0], X[1], sigma=sigma)

gak and cdist_gak are normalized in log space, so they stay accurate whatever the length of the time series. The unnormalized kernel \(k(\mathbf{x}, \mathbf{y})\) returned by unnormalized_gak, however, sums over every possible alignment and therefore leaves the range of a 64-bit float for time series longer than about 405 samples, in which case inf is returned.

Finally, the unnormalized GAK is related to softDTW [3] through the following formula:

\[k(\mathbf{x}, \mathbf{y}) = \exp \left(- \frac{\text{softDTW}_\gamma(\mathbf{x}, \mathbf{y})}{\gamma} \right)\]

where \(\gamma\) is the hyper-parameter controlling softDTw smoothness, which is related to the bandwidth parameter of GAK through \(\gamma = 2 \sigma^2\).

3.2. Clustering and Classification#

Kernel \(k\)-means [2] is a method that uses the kernel trick to implicitly perform \(k\)-means clustering in the embedding space associated to a kernel. This method is discussed in our User Guide section dedicated to clustering.

Kernels can also be used in classification settings. tslearn.svm offers implementations of Support Vector Machines (SVM) that accept GAK as a kernel. This implementation heavily relies on scikit-learn and libsvm. One implication is that predict_proba and predict_log_proba methods are computed based on cross-validation probability estimates, which has two main implications, as discussed in more details in scikit-learn’s user guide:

1. setting the constructor option probability to True makes the fit step longer since it then relies on an expensive five-fold cross-validation;

2. the probability estimates obtained through predict_proba may be inconsistent with the scores provided by decision_function and the predicted class output by predict.

For kernel="gak", tslearn.svm.TimeSeriesSVC and tslearn.svm.TimeSeriesSVR interpret gamma as a bandwidth-squared scale, \(\gamma = 2 \sigma^2\) (equivalently \(\sigma = \sqrt{\gamma / 2}\)), rather than the inverse-width coefficient used by an RBF kernel. gamma="auto" sets this value with gamma_soft_dtw on the training series and the estimator’s random_state, and the fitted value is reused at prediction time. That call follows the median-distance heuristic of [1] described above and returns \(2 \sigma^2\). It is a heuristic rather than a guaranteed optimum, and it depends on the scale of the input for both univariate and multivariate series. A positive numeric value selected using validation or cross-validation can replace it. Arbitrary grids, and the same grid on differently scaled inputs, need not perform comparably. If the candidates are multiples of the automatic estimate, compute that estimate separately within each training fold so held-out series do not leak into the bandwidth.

3.3. Examples Using Kernel Methods#

SVM and GAK

Kernel k-means