Dynamic time warping

ไดนามิกไทม์วอร์ปปิง (Dynamic time warping : DTW) เป็นขั้นตอนวิธีสำหรับการเปรียบเทียบความคล้ายของลำดับที่มีความแตกต่างกันในด้านเวลาหรือความเร็ว เช่น รูปแบบการเดินของคนๆหนึ่งจะถูกนับว่ามีความคล้าย ไม่ว่าคนๆนั้นจะเดินอย่างรวดเร็ว เดินอย่างเชื่องช้า หรือแม้แต่เดินด้วยความเร่ง เมื่อพิจารณาจากผู้สังเกตเดียวกัน ซึ่งไดนามิกไทม์วอร์ปปิงสามารถนำไปประยุกต์ได้กับวิดีโอ เสียง และภาพ รวมไปถึงข้อมูลต่างๆที่สามารถแปลงให้อยู่ในรูปของข้อมูลเชิงเส้นได้ ตัวอย่างหนึ่งของการประยุกต์ขั้นตอนวิธีนี้ไปใช้คือ การรู้จำคำพูด โดยใช้ไดนามิกไทม์วอร์ปปิง เพื่อจัดการกับคำพูดที่มีความเร็วไม่เท่ากัน แม้จะสื่อความหมายเดียวกัน
== แนวคิดเบื้องต้น ==
โดยทั่วไปไดนามิกไทม์วอร์ปปิงเป็นวิธีที่ทำให้คอมพิวเตอร์สามารถหาการจับคู่ที่เหมาะสมของลำดับสองชุดได้ภายใต้ข้อจำกัด ลำดับเหล่านั้นจะถูกบิดเบือน (warp) แบบไม่คงที่ในหน่วยของเวลา เพื่อที่จะพิจารณาความคล้ายจากการกระจายแบบไม่คงที่ในหน่วยของเวลา โดยจะให้ผลลัพธ์ออกมาเป็นระยะทางและวิถีการปรับแนว (alignment) ที่ดี่สุด ซึ่งวิธีการพิจารณาลำดับเช่นนี้พบได้บ่อยครั้งใน แบบจำลองฮิดเดนมาร์คอฟ (hidden Markov models)
== ขั้นตอนวิธี ==
เป้าหมายของไดนามิกไทม์วอร์ปปิง คือ เพื่อเปรียบเทียบลำดับที่ขึ้นอยู่กับเวลาสองชุด
X := (x_1, x_2, . . . , x_N) \, ด้วยความยาว N\, ซึ่งเป็นจำนวนเต็ม
Y := (y_1, y_2, . . . , y_M) \, ด้วยความยาว M\, ซึ่งเป็นจำนวนเต็ม
โดยลำดับเหล่านี้อาจจะเป็นสัญญาณที่ไม่ต่อเนื่อง (อนุกรมเวลา) หรือ ลำดับของลักษณะเฉพาะ (feature) ที่ถูกสร้างขึ้นตามช่วงเวลา กำหนดให้ปริภูมิของลักษณะเฉพาะแทนด้วย F\, ดังนั้น x_n, y_m \in F  สำหรับ  n \in [1 : N] และ m \in [1 : M] เพื่อที่จะเปรียบเทียบลักษณะเฉพาะ x, y \in F  จึงจำเป็นที่จะต้องคำนวณต้นทุนเฉพาะส่วน (local cost measure) หรือเรียกอีกอย่างได้ว่า การคำนวณระยะทางเฉพาะส่วน (local distance measure) ซึ่งนิยามได้เป็นฟังก์ชัน c: F \times F\rightarrow R \geqslant 0 ซึ่งโดยทั่วไป c (x,y) \, จะมีค่าน้อย ถ้า x\, และ y\, มีความคล้ายกันมาก ซึ่งสำหรับแต่ละคู่ของลำดับทั้งสอง นำไปสร้าง เมทริกซ์ต้นทุน (cost matrix) C \in R^{N \times M}  นิยามด้วย C (n,m) := c (x_n, y_m) \, ดังรูป
]
โดยเป้าหมายต่อไปคือการหาวิถีการปรับแนวระหว่าง X\, และ Y\, ที่มีต้นทุนรวมน้อยที่สุด โดยปกติแล้ว วิถีการปรับแนว จะวิ่งไปตามทางที่ต้นทุนต่ำภายในเมทริกซ์ต้นทุน ด้วยรูปแบบดังนี้
เส้นทางบิดเบือน  (N,M) \, เป็นลำดับ p = (p_1, . . . , p_L) \, และ p_l = (n_l,m_l) \in [1 : N] \times [1 : M] สำหรับ l \in [1 : L]จะสนใจเงื่อนไขดังต่อไปนี้
เงื่อนไขขอบเขต (Boundary condition) : p_1 = (1, 1) \, และ p_L = (N,M) \,
เงื่อนไขทางเดียว (Monotonicity condition) : n_1 \leqslant n_2 \leqslant . . . \leqslant n_L และ m_1 \geqslant m_2 \geqslant . . . \geqslant m_L
เงื่อนไขขนาดการเดิน (step size condition) : p_{l+1} - p_l \in \{ (1, 0), (0, 1), (1, 1) \} สำหรับ l \in [ 1 : L - 1 ] 
ซึ่งจะได้ตัวอย่างของเส้นทางบิดเบือนแบบต่างๆภายใต้เงื่อนไขดังรูป

โดยต้นทุนทั้งหมดของเส้นทางบิดเบือน p\, ระหว่าง X\, และ Y\, ซึ่งเกี่ยวเนื่องกับการวัดต้นทุนเฉพาะส่วน c\, จะถูกนิยามด้วย
 c_p (X,Y) := \sum_{l=1}^{L} c (x_{n_l},y_{n_l}) 
สำหรับ เส้นทางบิดเบือนที่เหมาะสมระหว่าง X\, และ Y\, คือระยะทางบิดเบือน p'\, ซึ่งมีต้นทุกต่ำที่สุดเมื่อเทียบกับเส้นทางบิดเบือนทั้งหมดที่เป็นไปได้ ระยะทางไดนามิกไทม์วอร์ปปิง DTW (X, Y ) \, ระหว่าง X\, และ Y\, จะถูกนิยามเป็นต้นทุนทั้งหมดของ p'\, โดย
{| align = "center"
|-
| DTW (X, Y ) \, || := c_{p'} (X, Y ) \,
|-
| || &nbsp; = min\{ c_p (X, Y ) | p \, เป็นเส้นทางบิดเบือน  (N,M) \} \,
|}
ซึ่งสุดท้ายแล้วจะได้ระยะทางบิดเบือนที่เหมาะสมดังรูป

== ความซับซ้อนเชิงเวลา ==
ขั้นตอนวิธีไดนามิกไทม์วอร์ปปิงแบบทั่วไปจะมีอัตราการเติบโตแบบชี้กำลัง แต่เมื่อใช้กำหนดการพลวัตในการแก้ปัญหาจะมีความซับซ้อนเชิงเวลาเป็น O (MN) \, เมื่อ M\, และ N\, แทนความยาวของข้อมูลในแต่ละลำดับ
== การประยุกต์ใช้และโอเพนซอร์ซที่เกี่ยวข้อง ==
lbimproved ไลบรารีภาษา C++ ได้นำเอาขั้นตอนวิธี Fast Nearest-Neighbor Retrieval มาใช้ภายใต้ไดนามิกส์ไทม์วอร์ปปิง (GPL) อีกทั้งยังได้จัดเตรียมไดนามิกส์ไทม์วอร์ปปิงไว้ให้ใช้ด้วยภาษา C++
R package dtw ได้นำเอาขั้นตอนวิธีในตระกูลไดนามิกไทม์วอร์ปปิงหลากหลายรูปแบบมาใช้งาน รวมไปถึงกฎการเรียกซ้ำ และการจับคู่สายอักขระย่อย
mlpy  ไลบรารี ภาษา Python ซึ่งได้นำเอาขั้นตอนวิธีไดนามิกไทม์วอร์ปปิงมาใช้
kinectdtw  โอเพนซอร์ซ เกี่ยวกับการรู้จำท่าทางที่ได้นำเอาขั้นตอนวิธีไดนามิกไทม์วอร์ปปิงมาใช้
Chula Engineering Newsletter  วารสารทางวิชาการของคณะวิศวกรรมศาสตร์ จุฬาลงกรณ์มหาวิทยาลัย ซึ่งได้กล่าวถึงการนำไดนามิกไทม์วอร์ปปิงไปประยุกต์ใช้ในด้านต่างๆ เช่น ค้นหาฐานข้อมูล การรู้จำเสียงพูด วิเคราะห์ข้อมูลทางสถิติ
== ดูเพิ่ม ==
Hidden Markov model
Speech recognition
Time series
== อ้างอิง ==
Sakoe, H. and Chiba, S., Dynamic programming algorithm optimization for spoken word recognition, IEEE Transactions on Acoustics, Speech and Signal Processing, 26 (1) pp. 43- 49, 1978, ISSN: 0096-3518
C. S. Myers and L. R. Rabiner.A comparative study of several dynamic time-warping algorithms for connected word recognition. The Bell System Technical Journal, 60 (7) :1389-1409, September 1981.
L. R. Rabiner and B. Juang.Fundamentals of speech recognition. Prentice-Hall, Inc., 1993 (Chapter 4)
Müller, Meinard, Information Retrieval for Music and Motion, 2007 (Chapter 4)
เทคนิคการใช้ไดนามิกไทม์วอร์ปปิงในการทำเหมืองข้อมูลอนุกรมเวลา Time Series Mining using Dynamic Time Warping Technique, Chula Engineering Newsletter 
ขั้นตอนวิธี
ภาษาศาสตร์คอมพิวเตอร์