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:
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:
Such computations are used, for example, in the kernel-\(k\)-means algorithm (see below).
Global Alignment Kernel¶
The Global Alignment Kernel (GAK) is a kernel that operates on time series.
It is defined, for a given bandwidth \(\sigma\), as:
where \(\mathcal{A}(\mathbf{x}, \mathbf{y})\) is the set of all possible alignments between series \(\mathbf{x}\) and \(\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
tslearn.metrics.sigma_gak:
from tslearn.metrics import gak, sigma_gak
sigma = sigma_gak(X)
k_01 = gak(X[0], X[1], sigma=sigma)
Note however that, on long time series, this estimate can lead to numerical overflows, which smaller values can avoid.
Finally, GAK is related to softDTW 3 through the following formula:
where \(\gamma\) is the hyper-parameter controlling softDTw smoothness, which is related to the bandwidth parameter of GAK through \(\gamma = 2 \sigma^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.
