# Parameter-Free Ordered Partial Match Alignment with Hidden State Time Warping
###### Abstract  
This paper investigates an ordered partial matching alignment problem, in which the goal is to align two sequences in the presence of potentially non-matching regions. We propose a novel parameter-free dynamic programming alignment method called hidden state time warping that allows an alignment path to switch between two different planes: a \"visible\" plane corresponding to matching sections and a \"hidden\" plane corresponding to non-matching sections. By defining two distinct planes, we can allow different types of time warping in each plane (e.g., imposing a maximum warping factor in matching regions while allowing completely unconstrained movements in non-matching regions). The resulting algorithm can determine the optimal continuous alignment path via dynamic programming, and the visible plane induces a (possibly) discontinuous alignment path containing matching regions. We show that this approach outperforms existing parameter-free methods on two different partial matching alignment problems involving speech and music. hidden state time warping; alignment; dynamic programming; partial matching; DTW  
Many works have proposed variations or extensions of DTW. These works generally fall into one of two categories. The first category focuses on mitigating the quadratic runtime or memory costs of DTW, which make it prohibitive for processing long sequences. Some works approach this by proposing approximations of DTW, e.g., by imposing fixed boundaries on the alignment path (e.g., Sakoe-Chiba band [1] and the Itakura parallelogram [2]), estimating the alignment at a coarse resolution and iteratively refining the alignment path [3; 4], estimating the alignment path with a limited amount of memory [5], or using a parallelizable time warping algorithm [6]. Other works approach this by computing exact DTW in a more efficient way, e.g., by using lower bounds [7; 8], early abandoning [9; 10], utilizing multiple cores [11; 12] or specialized hardware [13; 14], or performing the dynamic programming along diagonals rather than rows/columns to allow for parallelization [15]. The second category focuses on extending the behavior of DTW in some way. Some examples in the audio processing literature include performing time warping in an online fashion [16; 17], handling repeats and jumps in music [18; 19; 20], handling subsequence alignments [21; 22], handling pitch drift in a capella performances [23], and utilizing multiple performances to improve alignment accuracy [24]. This paper proposes an alignment algorithm called hidden state time warping (HSTW) that can handle ordered partial matching. In particular, HSTW allows for aligning two sequences whose alignment may contain discontinuities due to non-matching regions, as shown in Figure 1. Rather than computing a cumulative cost matrix \(D\in\mathbb{R}^{N\times M}\), we instead compute a cumulative cost tensor \(D\in\mathbb{R}^{2\times N\times M}\) containing two different planes: a \"visible\" plane corresponding to matching sections and a \"hidden\" plane corresponding to non-matching sections. The alignment path can transition between the visible and hidden planes. By defining two distinct planes, we can use different dynamic programming rules to treat matching and non-matching sections differently (e.g., imposing a maximum time warping factor in matching sections while allowing unconstrained movements in non-matching sections). Furthermore, we can find the optimal (continuous) alignment path through the entire double plane using a dynamic programming framework and then induce a discontinuous optimal matching alignment path by considering only the path elements in the visible plane.