# Estimating Road Segments Using Kernelized Averaging of GPS Trajectories
## 2 From Dynamic Time Warping to Time Elastic Kernels Averaging
### Kernelized Time Elastic Averaging of a Set of Time Series  
The averaging algorithm that we used to average a set of GPS trajectories is based on a probabilistic interpretation of the kernel alignment matrix (Equation (3)), as derived in [13]. This method is based on the recursive editing distance kernel, named REDK, which instantiates as \(\mathcal{K}_{\text{rdtw}}\) when DTW is considered as the editing distance. The principle behind this interpretation is as follows. If we consider a stochastic alignment automata that, given two time series \(\mathbf{x}\) and \(\mathbf{x^{\prime}}\), provides alignment paths, \(\pi\), according to a probability distribution \(P_{\pi}\approx K_{\pi}\), then the cell \((i,j)\) of the kernel alignment matrix (Figure 3, left) corresponds to the sum of the probabilities of the paths that allow aligning the sub time series \(\mathbf{x}_{0:i}\) and \(\mathbf{x^{\prime}}_{0:j}\). The kernel alignment matrix can thus be understood as a forward probability matrix. \[\mathcal{K}_{\text{rdtw}}(\mathbf{x}_{0:i},\mathbf{x^{\prime}}_{0:j})\approx \sum_{\pi\in\mathcal{A}}P_{\pi}(\mathbf{x}_{0:i},\mathbf{x^{\prime}}_{0:j}) \tag{9}\]  
Similarly, if we consider the backward alignment process (Figure 3, right), the cell \((i,j)\) corresponds to the sum of the probabilities of the paths that allow aligning backwardly the sub time series \(\mathbf{x}_{|x|-1:i}\) and \(\mathbf{x^{\prime}}_{|x^{\prime}|-1:j}\). \[\mathcal{K}_{\text{rdtw}}(\mathbf{x}_{|x|-1:i},\mathbf{x^{\prime}}_{|x^{ \prime}|-1:j})\approx\sum_{\pi\in\mathcal{A}}P_{\pi}(\mathbf{x}_{|x|-1:i}, \mathbf{x^{\prime}}_{|x^{\prime}|-1:j})\]Finally, if we consider the forward-backward \(FB\) alignment matrix, as depicted in Figure 4, the cell \(FB(i,j)=\mathcal{K}_{\text{rdtW}}(\mathbf{x}_{0:i},\mathbf{x}^{\prime}_{0:j}) \cdot\mathcal{K}_{\text{rdtW}}(\mathbf{x}_{|x|-1:i},\mathbf{x}^{\prime}_{|x^{ \prime}|-1:j})\approx\sum\limits_{\pi\in\mathcal{A}}P_{\pi}(\mathbf{x}_{0:i}, \mathbf{x}^{\prime}_{0:j})\cdot\sum\limits_{\pi\in\mathcal{A}}P_{\pi}(\mathbf{ x}_{|x|-1:i},\mathbf{x}^{\prime}_{|x^{\prime}|-1:j})\) represents the sum of the probabilities of all the global alignment paths \(\pi\) that cross cell \((i,j)\). The forward-backward alignment matrix allows for the estimation of the expectation of the samples of \(\mathbf{x}^{\prime}\) that are aligned with sample \(x_{t}\) (given that \(x_{t}\) is aligned) as well as the expectation of time of occurrence, \(t^{\prime}\) of the samples of \(\mathbf{x}^{\prime}\) that are aligned with \(x_{t}\) as follows:  
\[ \begin{split} E(x^{\prime}|x_{i})\propto\sum\limits_{j=0}^{|x^{ \prime}|-1}x^{\prime}_{j}\cdot\frac{FB(i,j)}{\sum_{f^{\prime}}FB(i,f^{\prime}) }\\ E(t^{\prime}|x_{i})\propto\sum\limits_{j=0}^{|x^{\prime}|-1}j \cdot\frac{FB(i,j)}{\sum_{f^{\prime}}FB(i,f^{\prime})}\end{split}  \tag{10}\]  
The expectation equations (Equation (10)) are at the basis of the procedure for averaging a set \(\mathbf{X}=\{\overset{k}{x}_{0:T_{k}}\}_{k=1\cdots N}\) of time series. Let \(r_{0:|r|-1}\) be a reference time series (\(r_{0:|r|-1}\)) that can be initially setup as the medoid of set \(\mathbf{X}\). The centroid estimate of \(\mathbf{X}\) is defined as the pair \((C,\mathcal{T})\) where \(C\) is a time series of length \(|r|\) and \(\mathcal{T}\) is the sequence of time stamps associated to the samples of \(C\)  
\[ \begin{split} C_{t}&=\frac{1}{N}\sum\limits_{k=1}^{N }E(\overset{k}{x}|r_{t})\\ \mathcal{T}_{t}&=\frac{1}{N}\sum\limits_{k=1}^{N}E( \overset{k}{i}|r_{t})\end{split}  \tag{11}\]  
Figure 4: The forward–backward alignment kernel matrix. Figure 3: The forward (**left**) and backward (**right**) alignment kernel matrices. Equations (10) and (11) are at the basis of the iterative agglomerative algorithm, called iTEKA (iterative Time Elastic Kernel Averaging), that provides a refinement of the centroid estimation at each iteration until reaching a (local) optimum, as presented in Algorithm 1.