3. Applications of DTW to Stratigraphic Pattern Alignment

The application of DTW to the problem of stratigraphic depth and depth matching was investigated around the same time by Pälike [G2] (software) and Lisiecki and Lisiecki [G3] (software).

In general, these methods try to solve the problem of stratigraphic mapping, as illustrated below:

Fig. 3.1 Conceptual illustration of depth to time conversion with constraints on sedimentation rate and continuity (from [G2])

3.1. Similarities between speech recognition and astronomical tuning

“A literature research revealed that the fields of speech recognition and cyclostratigraphic correlation share a common set of problems. In both fields one aim is to match a data curve (a speech utterance, or a geological data set) to a known reference curve (a characteristic representation of known utterances, or an astronomical time series). Both fields face the problem that data series can be distorted in a non-linear fashion, caused, for example, by varying sedimentation rates in the case of geological data, and by variations in length, pitch and inflection of utterances in the field of speech recognition. These distortions require the alignment of time-correlative features of data and “target” series, subject to a number of constraints. In both fields computational speed is an important consideration, in order to complete pattern matching decisions rapidly, or when dealing with a large number of data points.” (Pälike, 2001):

3.2. A “dynamic programming” approach for optimisation

The method of dynamic programming was first introduced by Bellman [G4], Bellman and Dreyfus [G5]. They formulated the principle of optimality (also known as Bellman's principle). This can be described as [G6]:

An optimal policy has the property that whatever the state the system is in at a particular stage, and whatever the decision taken in that state, then the resulting decisions are optimal for the subsequent state.

and/or

An optimal policy is made up of optimal sub-policies.

or

An optimal policy from any state is independent of how that state was achieved and comprises optimal sub-policies from then on.

To find an optimal path, this can be translated into two rules [G7]:

1. Let \(F^*\) be the optimal global path on the depth-time grid (of dimension \(N\times M\)). If \(F^*\) goes through a point \((D_i,T_j)\), then the optimal path to the \((D_i,T_j)\) point from the point \((D_1,T_1)\) is part of \(F^*\).

2. The optimal path to the point \((D_i,T_j)\) depends only on previous grid points.

These rules then define a recursive relationship, where the problem of finding an optimal path is broken down into the sub-problem of finding an optimal local point given a history of decisions about previous path points. This allows the rapid calculation of the optimal global mapping function, since the number of misfit calculations does not increase as a factorial function of the number of data, but approximately as a quadratic function.

3.3. Slope constraints

Fig. 3.2 Typical slope constraints on the warping function used in dynamic time warping. Arrows indicate from which previous mapping points the next point can be chosen, as indicated by the data curve index \(i\), and the target curve index \(j\). (A) shows a constraint described in \cite{Itakura1975} (“Itakura” local constraint), which results in a minimum slope of 0.5 and a maximum slope of 2 (with respect to the data and target curve indices). The cross indicates that only one consecutive horizontal transition is allowed. This was the local constraint that was employed in this study. (B) to (D) show various constraints as described in [3] (“Sakoe-Chiba” local constraints). Figure modified from [G8])

3.4. Symmetric vs. Asymmetric approaches

It is possible to classify the DTW algorithms into asymmetric and symmetric approaches:

– Asymmetric refers to matching one curve to a fixed target, only modifying the axis of one of the two curves. This is likely the case when matching depth to time/age.

– Symmetric implies that both curves’ depth-axes are warped or modified. This has been generally shown to result in better matching abilities, and is perhaps more useful for depth/depth matching.

3.5. Normalisation of the cost function and the optimisation problem

When comparing data and target patterns with different lengths it is necessary to apply a weighting and normalisation in order to make the total misfit of different possible mapping functions comparable (and “fair”). The weighting of each local misfit measure depends on the chosen local sedimentation rate constraint, while the normalisation depends on the number of data points, the length of the mapping function between end points, as well as the sedimentation rate constraint. Normalization might be difficult if there is slack in the start- and end points.

3.6. Special considerations

Since the DTW approach has some features that require special treatment with respect to geological processes (continuity of time, min/max sedimentation rates + rates of change), various additional local and global contraints typically have to be added to achieve a more geologically plausible depth/time or depth/depth matching.

3.6.1. Section Bibliography

G1

H. Sakoe and S. Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-26(1):43–49, 1978. URL: https://www.irit.fr/~Julien.Pinquier/Docs/TP_MABS/res/dtw-sakoe-chiba78.pdf, doi:10.1109/TASSP.1978.1163055.

G2(1,2)

Heiko Pälike. Extending the astronomical calibration of the Geological Time Scale. PhD thesis, University of Cambridge, 2001. URL: https://eprints.soton.ac.uk/41892/1/HPthesis.pdf, doi:10.17863/CAM.20474.

G3

Lorraine E. Lisiecki and Philip A. Lisiecki. Application of dynamic programming to the correlation of paleoclimate records. Paleoceanography, 17(4):1–1–1–12, 2002. URL: https://agupubs.onlinelibrary.wiley.com/doi/abs/10.1029/2001PA000733, doi:10.1029/2001PA000733.

G4

R. E. Bellman. Dynamic programming. Princeton University Press, Princeton, NJ, USA, 1957.

G5

R. E. Bellman and S. E. Dreyfus. Applied dynamic programming. Princeton University Press, Princeton, NJ, USA, 1962.

G6

D. K. Smith. Dynamic Programming: a practical introduction. Ellis Horwood series in mathematics and its applications. Ellis Horwood, New York, London, 1961.

G7

A. Kassidas, J. F. MacGregor, and P. A. Taylor. Synchronization of batch trajectories using dynamic time warping. A.I.Ch.E (American Institute of Chemical Engineering) Journal, 44(4):864–875, 1998. doi:10.1002/aic.690440412.

G8

A. Kassidas. Fault Diagnosis using speech recognition methods. PhD thesis, Dept. of Chem. Eng., McMaster University, Ontario, Canada, 1997.