![\"FMP\"](\"../data/FMP_Teaser_Cover.png\")
\n",
"![\"AudioLabs\"](\"../data/Logo_AudioLabs_Long.png\"){kind=logo}
\n",
"\n",
"\n",
"![\"C3\"](\"../data/C3_nav.png\")
\n",
"\n", "Following Section 3.2.1 of [Müller, FMP, Springer 2015], we explain in this notebook the basic algorithm for dynamic time warping (DTW). A general introduction can also be found in the following book chapter.\n", "\n", "
![\"C0\"](\"../data/C3/FMP_C3_F12.png\")
\n",
"\n",
"Each of the red bidirectional arrows encodes a correspondence between two elements $x_n$ and $y_m$ for $n\\in[1:N]$ and $m\\in[1:M]$. Such a local correspondence can be modeled by the index pair $(n,m)$. The right side of the above figure illustrates how the alignment shown on the left is encoded by a sequence of index pairs. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Warping Path\n",
"\n",
"To model a global alignment between the elements of the sequences $X$ and $Y$, the idea is to consider a sequence of index pairs that fulfills certain constraints. This leads to the notion of a **warping path**. By definition, an $(N,M)$-warping path of length $L\\in\\mathbb{N}$ is a sequence \n",
"\n",
"\\begin{equation}\n",
"P=(p_1,\\ldots,p_L)\n",
"\\end{equation}\n",
"\n",
"with $p_\\ell=(n_\\ell,m_\\ell)\\in[1:N]\\times [1:M]$ for $\\ell\\in[1:L]$ satisfying the following conditions:\n",
"\n",
"* Boundary condition: $p_1= (1,1)$ and $p_L=(N,M)$\n",
"* Monotonicity condition: $n_1\\leq n_2\\leq\\ldots \\leq n_L$ and $m_1\\leq m_2\\leq \\ldots \\leq m_L$\n",
"* Step-size condition: $p_{\\ell+1}-p_\\ell\\in \\Sigma:=\\{(1,0),(0,1),(1,1)\\}$ for $\\ell\\in[1:L]$\n",
"\n",
"An $(N,M)$-warping path $P=(p_1,\\ldots,p_L)$ defines an alignment between two sequences $X=(x_1,x_2,\\ldots,x_N)$ and $Y=(y_1,y_2,\\ldots,y_M)$ by assigning the element $x_{n_\\ell}$ of $X$ to the element $y_{m_\\ell}$ of $Y$. The boundary condition enforces that the first elements of $X$ and $Y$ as well as the last elements of $X$ and $Y$ are aligned to each other. The monotonicity condition reflects the requirement of faithful timing: if an element in $X$ precedes a second element in $X$, then this should also hold for the corresponding elements in $Y$, and vice versa. Finally, the step size condition with respect to the set $\\Sigma$ expresses a kind of continuity condition: no element in $X$ and $Y$ can be omitted, and there are no replications in the alignment. Note that the step size condition implies the monotonicity condition, which nevertheless has been quoted explicitly for the sake of clarity. The following figure illustrates the conditions by some examples where the conditions (boundary, monotonicity, step size) are violated.\n",
"\n",
"![\"C0\"](\"../data/C3/FMP_C3_F13.png\")
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Cost Matrix and Optimality\n",
"\n",
"Next, we introduce a notion that tells us something about the **quality** of a warping path. To this end, we need a way to numerically compare the elements of the feature sequences $X$ and $Y$. Let $\\mathcal{F}$ be a **feature space** and assume that $x_n,y_m\\in\\mathcal{F}$ for $n\\in[1:N]$ and $m\\in[1:M]$. To compare two different features $x,y\\in\\mathcal{F}$, one needs a **local cost measure**, which is defined to be a function\n",
"\n",
"\\begin{equation}\n",
" c:\\mathcal{F}\\times\\mathcal{F}\\to \\mathbb{R}.\n",
"\\end{equation}\n",
"\n",
"Typically, $c(x,y)$ is small (low cost) if $x$ and $y$ are similar to each other, and otherwise $c(x,y)$ is large (high cost). Evaluating the local cost measure for each pair of elements of the sequences $X$ and $Y$, one obtains a **cost matrix** $C\\in\\mathbb{R}^{N\\times M}$ defined by\n",
"\n",
"\\begin{equation}\n",
"C(n,m):=c(x_n,y_m)\n",
"\\end{equation}\n",
"\n",
"for $n\\in[1:N]$ and $m\\in[1:M]$. A tuple $(n,m)$ representing an entry of the matrix $C$ will be referred to as a **cell** of the matrix. The **total cost** $c_P(X,Y)$ of a warping path $P$ between two sequences $X$ and $Y$ with respect to the local cost measure $c$ is defined as\n",
"\n",
"\\begin{equation}\n",
" c_P:=\\sum_{\\ell=1}^L c(x_{n_\\ell},y_{m_\\ell}) = \\sum_{\\ell=1}^L C(n_\\ell,m_\\ell).\n",
"\\end{equation}\n",
"\n",
"The intuition of this definition is that the warping path accumulates the cost of all cells it runs through. A warping path is \"good\" if its total cost is low, and it is \"bad\" if its total cost is high. Now, we are interested in an **optimal warping path** between $X$ and $Y$, which is defined to be a warping path $P^\\ast$ that has minimal total cost among all possible warping paths. The cells of this warping path encode an overall optimal alignment between \n",
"the elements of the two sequences, where the warping path conditions ensure that each element of sequence $X$ is assigned to at least one element of $Y$ and vice versa. This leads us to the definition of the **DTW distance** denoted as $\\mathrm{DTW}(X,Y)$ between the two sequences $X$ of length $N$ and $Y$ of length $M$, which is defined as the total cost of an optimal $(N,M)$-warping path $P^\\ast$:\n",
"\n",
"\\begin{eqnarray}\n",
" \\mathrm{DTW}(X,Y) :=c_{P^\\ast}(X,Y) = \\min\\{c_P(X,Y)\\mid P \\mbox{ is an $(N,M)$-warping path} \\}\n",
"\\end{eqnarray}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## DTW Algorithm using Dynamic Programming\n",
"\n",
"To determine an optimal warping path $P^\\ast$ for two sequences $X$ and $Y$, one could compute the total cost of all possible $(N,M)$-warping paths and then take the minimal cost. However, the number of different $(N,M)$-warping paths is exponential in $N$ and $M$. Therefore, such a naive approach is computationally infeasible for large $N$ and $M$. We now introduce an $O(NM)$ algorithm that is based on **dynamic programming**. The general idea behind dynamic programming is to break down a given problem into simpler subproblems and then to combine the solutions of the subproblems to reach an overall solution. In the case of DTW, the idea is to derive an optimal warping path for the original sequences from optimal warping paths for truncated subsequences. This idea can then be applied recursively. To formalize this idea, we define the prefix sequences \n",
"$X(1\\!:\\!n) := (x_1,\\ldots x_n)$ for $n\\in[1:N]$ and $Y(1\\!:\\!m) := (y_1,\\ldots y_m)$ for $m\\in[1:M]$ and set\n",
"\n",
"\\begin{equation}\n",
" D(n,m):=\\mathrm{DTW}(X(1\\!:\\!n),Y(1\\!:\\!m)).\n",
"\\end{equation}\n",
"\n",
"The values $D$ define an $(N\\times M)$ matrix $D$, which is also referred to as the **accumulated cost matrix**. Each value $D(n,m)$ specifies the total (or accumulated) cost of an optimal warping path starting at cell $(1,1)$ and ending at cell $(n,m)$. Obviously, one has $D(N,M)=\\mathrm{DTW}(X,Y)$. The following table gives a description of the **DTW Algorithm** based on dynamic programming. In the first part, the accumulated cost matrix $D$ is computed iteratively using a nested loop. In the second part, the optimal warping path is computed using a backtracking procedure. For further details and a proof of the algorithm's correctness, we refer to Section 3.2.1 of [Müller, FMP, Springer 2015].\n",
"\n",
"![\"C0\"](\"../data/C3/FMP_C3_T02.png\")
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Implementation\n",
"\n",
"We now implement the DTW algorithm as described above. As an illustrative example, we consider two sequences of real numbers and the absolute value of differences (one-dimensional Euclidean distance) as cost measure. In other words, we have the feature space $\\mathcal{F}=\\mathbb{R}$ and $c(x,y):=|x-y|$ for $x,y\\in \\mathcal{F}$.\n",
"\n",
"X = X[0], ..., X[N-1] and Y = Y[0], ..., Y[M-1] C[0, 0], ..., C[N-1, M-1] and D[0, 0], ..., D[N-1, M-1]P = P[0], ..., P[L-1] with P[0] = (0, 0) and P[L-1] = (N-1, M-1)![\"C0\"](\"../data/C0_nav.png\") | \n",
" ![\"C1\"](\"../data/C1_nav.png\") | \n",
" ![\"C2\"](\"../data/C2_nav.png\") | \n",
" | \n",
" ![\"C4\"](\"../data/C4_nav.png\") | \n",
" ![\"C5\"](\"../data/C5_nav.png\") | \n",
" ![\"C6\"](\"../data/C6_nav.png\") | \n",
" ![\"C7\"](\"../data/C7_nav.png\") | \n",
" ![\"C8\"](\"../data/C8_nav.png\") | \n",
"