A general optimization framework for dynamic time warping

被引：9

作者：

Deriso, Dave ^{[1
]}

Boyd, Stephen ^{[2
]}

机构：

[1] Stanford Univ, Computat & Math Engn, 475 Via Ortega,Suite 060, Stanford, CA 94305 USA

[2] Stanford Univ, Elecr Engn, 350 Serra Mall,Packard 175, Stanford, CA 94305 USA

来源：

OPTIMIZATION AND ENGINEERING | 2023年 / 24卷 / 02期

关键词：

Time-Series; DTW; Dynamic programming;

D O I：

10.1007/s11081-022-09738-z

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

The goal of dynamic time warping is to transform or warp time in order to approximately align two signals. We pose the choice of warping function as an optimization problem with several terms in the objective. The first term measures the misalignment of the time-warped signals. Two additional regularization terms penalize the cumulative warping and the instantaneous rate of time warping; constraints on the warping can be imposed by assigning the value +oo to the regularization terms. Different choices of the three objective terms yield different time warping functions that trade off signal fit or alignment and properties of the warping function. The optimization problem we formulate is a classical optimal control problem, with initial and terminal constraints, and a state dimension of one. We describe an effective general method that minimizes the objective by discretizing the values of the original and warped time, and using standard dynamic programming to compute the (globally) optimal warping function with the discretized values. Iterated refinement of this scheme yields a high accuracy warping function in just a few iterations. Our method is implemented as an open source Python package GDTW.

引用

页码：1411 / 1432

页数：22

共 28 条

[11]

Hastie T., 2001, The elements of statistical learning, DOI DOI 10.1007/978-0-387-21606-5

[12] Optimizing dynamic time warping's window width for time series data mining applications [J].

Hoang Anh Dau ;

Silva, Diego Furtado ;

Petitjean, Francois ;

Forestier, Germain ;

Bagnall, Anthony ;

Mueen, Abdullah ;

Keogh, Eamonn .

DATA MINING AND KNOWLEDGE DISCOVERY, 2018, 32 (04) :1074-1120

[13]

Huber PJ., 2011, International encyclopedia of statistical science, P1248, DOI [10.1007/978-3-642-04898-2594, DOI 10.1007/978-3-642-04898-2594]

[14] MINIMUM PREDICTION RESIDUAL PRINCIPLE APPLIED TO SPEECH RECOGNITION [J].

ITAKURA, F .

IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 1975, AS23 (01) :67-72

[15] Functional Data Analysis of Amplitude and Phase Variation [J].

Marron, J. S. ;

Ramsay, James O. ;

Sangalli, Laura M. ;

Srivastava, Anuj .

STATISTICAL SCIENCE, 2015, 30 (04) :468-484

[16] PERFORMANCE TRADEOFFS IN DYNAMIC TIME WARPING ALGORITHMS FOR ISOLATED WORD RECOGNITION [J].

MYERS, C ;

RABINER, LR ;

ROSENBERG, AE .

IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 1980, 28 (06) :623-635

[17] A GENERAL METHOD APPLICABLE TO SEARCH FOR SIMILARITIES IN AMINO ACID SEQUENCE OF 2 PROTEINS [J].

NEEDLEMAN, SB ;

WUNSCH, CD .

JOURNAL OF MOLECULAR BIOLOGY, 1970, 48 (03) :443-+

[18]

Rabiner L., 1993, Fundamentals of Speech Recognition

[19]

Rakthanmanon Thanawin, 2012, KDD, V2012, P262, DOI 10.1145/2339530.2339576

[20]

Ramsay J.O., 2005, FITTING DIFFERENTIAL, P327

← 1 2 3 →