{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\"FMP\"\n", "\"AudioLabs\"\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\"C5\"\n", "

Viterbi Algorithm

\n", "
\n", "\n", "
\n", "\n", "

\n", "Following Section 5.3.3.2 of [Müller, FMP, Springer 2015], we describe in this notebook the Viterbi algorithm, which efficiently solves the uncovering problem of hidden Markov models (HMMs). For a detailed introduction of HMMs, we refer to the famous tutorial paper by Rabiner.\n", "\n", "

\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Uncovering Problem and Viterbi Algorithm\n", "\n", "We now consider the [**uncovering problem**](../C5/C5S3_HiddenMarkovModel.html), which is the problem relevant for our [chord recognition scenario](../C5/C5S2_ChordRec_Templates.html), in more detail. As described in the [FMP notebook on Hidden Markov Models (HMMs)](../C5/C5S3_HiddenMarkovModel.html), the goal is to find the **single** state sequence $S=(s_{1},s_{2},\\ldots,s_{N})$ that \"best explains\" a given observation sequence $O=(o_{1},o_{2},\\ldots,o_{N})$. In the chord recognition scenario, the observation sequence is a sequence of [chroma vectors](../C3/C3S1_SpecLogFreq-Chromagram.html) extracted from an audio recording. The optimal state sequence is then the sequence of chord labels, which is the result of the chord recognition procedure. As optimization criterion, one possibility is to choose the state sequence $S^\\ast$ that yields the highest probability $\\mathrm{Prob}^\\ast$ when evaluated against the observation sequence $O$:\n", "\n", "\\begin{eqnarray}\n", " \\mathrm{Prob}^\\ast\n", " &=& \\underset{S=(s_{1},s_{2},\\ldots,s_{N})}{\\max} \\,\\,P[O,S|\\Theta],\\\\\n", " S^\\ast \n", " &=& \\underset{S=(s_{1},s_{2},\\ldots,s_{N})}{\\mathrm{argmax}} \\,\\,\\,P[O,S|\\Theta].\n", "\\end{eqnarray}\n", "\n", "To find the sequence $S^\\ast$ using the naive approach, one would have to compute the probability value $P[O,S|\\Theta]$ \n", "for each of the $I^N$ possible state sequences of length $N$ and then look for the maximizing argument. Fortunately, there is a technique known as the **Viterbi algorithm** for finding the optimizing state sequence in a much more efficient way. The Viterbi algorithm, which is similar to the [DTW algorithm](../C3/C3S2_DTWbasic.html), is based on **dynamic programming**. The idea is to recursively compute an optimal (i.e., probability-maximizing) state sequence from optimal solutions for subproblems, where one considers truncated versions of the observation sequence. Let \n", "$O=(o_{1},o_{2},\\ldots o_{N})$ be the observation sequence. Then, we define the prefix \n", "\n", "$$\n", "O(1\\!:\\!n):=(o_{1},\\ldots,o_{n})\n", "$$ \n", "\n", "of length $n\\in[1:N]$ and set\n", "\n", "\\begin{equation}\n", " \\mathbf{D}(i,n):=\\underset{(s_1,\\ldots,s_n)}{\\max} P[O(1:n),(s_1,\\ldots, s_{n-1},s_n=\\alpha_i)|\\Theta]\n", "\\end{equation}\n", "\n", "for $i\\in[1:I]$. In other words, $\\mathbf{D}(i,n)$ is the highest probability along a single state sequence $(s_{1},\\ldots,s_{n})$ that accounts for the first $n$ observations and ends in state $s_{n}=\\alpha_{i}$. The state sequence yielding the maximal value \n", "\n", "\\begin{equation}\n", "\\label{eq:ChordReco:HMM:Problems:UncovMax} \n", " \\mathbf{Prob}^\\ast = \\underset{i\\in[1:I]}{\\max}\\,\\,\\mathbf{D}(i,N)\n", "\\end{equation}\n", "\n", "is the solution to our uncovering problem. The $(I\\times N)$ matrix $\\mathbf{D}$ can be computed recursively along the column index $n\\in[1:N]$. The following table specifies the Viterbi algorithm. For a detailed explanation of the algorithm, we refer to Section 5.3.3.2 of [Müller, FMP, Springer 2015].\n", "\n", "\"FMP_C5_T02\"\n", "\n", "The following figure illustrates the main steps of the Viterbi algorithm. \n", "\n", "* The blue cells indicate the entries $\\mathbf{D}(i,1)$, which serve as **initialization** of the algorithm. \n", "* The red cells illustrate the computation of the **main iteration**. \n", "* The black cell indicates the **maximizing index** used for the back tracking to obtain the optimal state sequence. \n", "* The matrix $E$ is used to keep track of the maximizing indices in the recursion. This information is needed in the second stage when constructing the optimal state sequence using **backtracking**. \n", "\n", "\"FMP_C5_F27\"\n", "\n", "The overall procedure is similar to the [DTW algorithm](../C3/C3S2_DTWbasic.html), where one first constructs the accumulated cost matrix and then obtains the optimal warping path using backtracking. As illustrated by the previous figure, the Viterbi algorithm proceeds in an iterative fashion building up a graph-like structure with $N$ layers, each consisting of $I$ nodes (the states). Furthermore, two neighboring layers are connected by $I^2$ edges, which also determines the order of the number of operations needed to construct a new layer from a given layer. From this follows that the computational complexity of the Viterbi algorithm is $O(N\\cdot I^2)$, which is much better than $O(I^N)$ required for the naive approach. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Toy Example\n", "\n", "Continuing our toy example from the [FMP notebook on HMMs](../C5/C5S3_HiddenMarkovModel.html), the next figure illustrates the principle of the Viterbi algorithm. At the top, one finds a specification of the HMM. At the bottom, the Viterbi algorithm is applied for an input sequence of length $N=6$.\n", "\n", "\"FMP_C5_F28a\"\n", "\"FMP_C5_F28b\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Implementation of Viterbi Algorithm\n", "\n", "In the next code cell, we provide an implementation of the Viterbi algorithm. \n", "\n", "
\n", "Note: Due to Python conventions, the indexing in the implementation starts with index 0. Also, there is an index shift when applying the algorithm to our toy example, which becomes O = [0, 2, 0, 2, 2, 1].\n", "
" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "execution": { "iopub.execute_input": "2024-02-15T08:55:47.653941Z", "iopub.status.busy": "2024-02-15T08:55:47.653653Z", "iopub.status.idle": "2024-02-15T08:55:50.239068Z", "shell.execute_reply": "2024-02-15T08:55:50.238415Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Observation sequence: O = [0 2 0 2 2 1]\n", "Optimal state sequence: S = [0 0 0 2 2 1]\n", "D =\n", "[[ 0.4200 0.1008 0.0564 0.0135 0.0033 0.0000]\n", " [ 0.0200 0.0000 0.0010 0.0000 0.0000 0.0006]\n", " [ 0.0000 0.0336 0.0000 0.0045 0.0022 0.0003]]\n", "E =\n", "[[0 0 0 0 0]\n", " [0 0 0 0 2]\n", " [0 2 0 2 2]]\n" ] } ], "source": [ "import numpy as np\n", "from numba import jit\n", "\n", "@jit(nopython=True)\n", "def viterbi(A, C, B, O):\n", " \"\"\"Viterbi algorithm for solving the uncovering problem\n", "\n", " Notebook: C5/C5S3_Viterbi.ipynb\n", "\n", " Args:\n", " A (np.ndarray): State transition probability matrix of dimension I x I\n", " C (np.ndarray): Initial state distribution of dimension I\n", " B (np.ndarray): Output probability matrix of dimension I x K\n", " O (np.ndarray): Observation sequence of length N\n", "\n", " Returns:\n", " S_opt (np.ndarray): Optimal state sequence of length N\n", " D (np.ndarray): Accumulated probability matrix\n", " E (np.ndarray): Backtracking matrix\n", " \"\"\"\n", " I = A.shape[0] # Number of states\n", " N = len(O) # Length of observation sequence\n", "\n", " # Initialize D and E matrices\n", " D = np.zeros((I, N))\n", " E = np.zeros((I, N-1)).astype(np.int32)\n", " D[:, 0] = np.multiply(C, B[:, O[0]])\n", "\n", " # Compute D and E in a nested loop\n", " for n in range(1, N):\n", " for i in range(I):\n", " temp_product = np.multiply(A[:, i], D[:, n-1])\n", " D[i, n] = np.max(temp_product) * B[i, O[n]]\n", " E[i, n-1] = np.argmax(temp_product)\n", "\n", " # Backtracking\n", " S_opt = np.zeros(N).astype(np.int32)\n", " S_opt[-1] = np.argmax(D[:, -1])\n", " for n in range(N-2, -1, -1):\n", " S_opt[n] = E[int(S_opt[n+1]), n]\n", "\n", " return S_opt, D, E\n", "\n", "# Define model parameters\n", "A = np.array([[0.8, 0.1, 0.1], \n", " [0.2, 0.7, 0.1], \n", " [0.1, 0.3, 0.6]])\n", "\n", "C = np.array([0.6, 0.2, 0.2])\n", "\n", "B = np.array([[0.7, 0.0, 0.3], \n", " [0.1, 0.9, 0.0], \n", " [0.0, 0.2, 0.8]])\n", "\n", "\n", "O = np.array([0, 2, 0, 2, 2, 1]).astype(np.int32)\n", "#O = np.array([1]).astype(np.int32)\n", "#O = np.array([1, 2, 0, 2, 2, 1]).astype(np.int32)\n", "\n", "# Apply Viterbi algorithm\n", "S_opt, D, E = viterbi(A, C, B, O)\n", "#\n", "print('Observation sequence: O = ', O)\n", "print('Optimal state sequence: S = ', S_opt)\n", "np.set_printoptions(formatter={'float': \"{: 7.4f}\".format})\n", "print('D =', D, sep='\\n')\n", "np.set_printoptions(formatter={'float': \"{: 7.0f}\".format})\n", "print('E =', E, sep='\\n')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Log-Domain Implementation of Viterbi Algorithm\n", "\n", "In each iteration of the Viterbi algorithm, the accumulated probability values of $\\mathbf{D}$ at step $n-1$ are multiplied with two probability values from $A$ and $B$. More precisely, we have\n", "\n", "$$\n", " \\mathbf{D}(i,n) = \\max_{j\\in[1:I]}\\big(a_{ij} \\cdot\\mathbf{D}(j,n-1) \\big) \\cdot b_{i_{k_n}}.\n", "$$\n", "Since all probability values lie the interval $[0,1]$, the product of such values decreases exponentially with the number $n$ of iterations. As a result, for input sequences $O=(o_{1},o_{2},\\ldots o_{N})$ with large $N$, the values in $\\mathbf{D}$ typically become extremely small, which may finally lead to a numerical underflow. A well-known trick when dealing with products of probability values is to work in the **log-domain**. To this end, one applies a logarithm to all probability values and **replaces multiplication by summation**. Since the logarithm is a strictly monotonous function, ordering relations are preserved in the log-domain, which allows for transferring operations such as **maximization** or **minimization**.\n", "\n", "In the following code cell, we provide a **log variant** of the Viterbi algorithm. This variant yields exactly the same optimal state sequence $S^\\ast$ and the same backtracking matrix $E$ as the original algorithm, as well as the accumulated log probability matrix $\\log(\\mathbf{D})$ (`D_log`) (where the logarithm is applied for each entry). We again test the implementation on our toy example. Furthermore, as a sanity check, we apply the exponential function to the computed log-matrix `D_log`, which should yield the matrix `D` as computed by the original Viterbi algorithm above. " ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "execution": { "iopub.execute_input": "2024-02-15T08:55:50.270301Z", "iopub.status.busy": "2024-02-15T08:55:50.269975Z", "iopub.status.idle": "2024-02-15T08:55:50.859362Z", "shell.execute_reply": "2024-02-15T08:55:50.858760Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Observation sequence: O = [0 2 0 2 2 1]\n", "Optimal state sequence: S = [0 0 0 2 2 1]\n", "D_log =\n", "[[ -0.87 -2.29 -2.87 -4.30 -5.73 -714.35]\n", " [ -3.91 -711.57 -6.90 -713.57 -715.00 -7.44]\n", " [-710.01 -3.39 -712.30 -5.40 -6.13 -8.25]]\n", "exp(D_log) =\n", "[[ 0.4200 0.1008 0.0564 0.0135 0.0033 0.0000]\n", " [ 0.0200 0.0000 0.0010 0.0000 0.0000 0.0006]\n", " [ 0.0000 0.0336 0.0000 0.0045 0.0022 0.0003]]\n", "E =\n", "[[0 0 0 0 0]\n", " [0 0 0 0 2]\n", " [0 2 0 2 2]]\n" ] } ], "source": [ "@jit(nopython=True)\n", "def viterbi_log(A, C, B, O):\n", " \"\"\"Viterbi algorithm (log variant) for solving the uncovering problem\n", "\n", " Notebook: C5/C5S3_Viterbi.ipynb\n", "\n", " Args:\n", " A (np.ndarray): State transition probability matrix of dimension I x I\n", " C (np.ndarray): Initial state distribution of dimension I\n", " B (np.ndarray): Output probability matrix of dimension I x K\n", " O (np.ndarray): Observation sequence of length N\n", "\n", " Returns:\n", " S_opt (np.ndarray): Optimal state sequence of length N\n", " D_log (np.ndarray): Accumulated log probability matrix\n", " E (np.ndarray): Backtracking matrix\n", " \"\"\"\n", " I = A.shape[0] # Number of states\n", " N = len(O) # Length of observation sequence\n", " tiny = np.finfo(0.).tiny\n", " A_log = np.log(A + tiny)\n", " C_log = np.log(C + tiny)\n", " B_log = np.log(B + tiny)\n", "\n", " # Initialize D and E matrices\n", " D_log = np.zeros((I, N))\n", " E = np.zeros((I, N-1)).astype(np.int32)\n", " D_log[:, 0] = C_log + B_log[:, O[0]]\n", "\n", " # Compute D and E in a nested loop\n", " for n in range(1, N):\n", " for i in range(I):\n", " temp_sum = A_log[:, i] + D_log[:, n-1]\n", " D_log[i, n] = np.max(temp_sum) + B_log[i, O[n]]\n", " E[i, n-1] = np.argmax(temp_sum)\n", "\n", " # Backtracking\n", " S_opt = np.zeros(N).astype(np.int32)\n", " S_opt[-1] = np.argmax(D_log[:, -1])\n", " for n in range(N-2, -1, -1):\n", " S_opt[n] = E[int(S_opt[n+1]), n]\n", "\n", " return S_opt, D_log, E\n", "\n", "# Apply Viterbi algorithm (log variant)\n", "S_opt, D_log, E = viterbi_log(A, C, B, O)\n", "\n", "print('Observation sequence: O = ', O)\n", "print('Optimal state sequence: S = ', S_opt)\n", "np.set_printoptions(formatter={'float': \"{: 7.2f}\".format})\n", "print('D_log =', D_log, sep='\\n')\n", "np.set_printoptions(formatter={'float': \"{: 7.4f}\".format})\n", "print('exp(D_log) =', np.exp(D_log), sep='\\n')\n", "np.set_printoptions(formatter={'float': \"{: 7.0f}\".format})\n", "print('E =', E, sep='\\n')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "Acknowledgment: This notebook was created by Meinard Müller and Christof Weiß.\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "\n", "
\"C0\"\"C1\"\"C2\"\"C3\"\"C4\"\"C5\"\"C6\"\"C7\"\"C8\"
" ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.16" } }, "nbformat": 4, "nbformat_minor": 1 }