การบิดงอเวลาแบบพลวัต

thumb|รูปแบบของการจับคู่ลำดับของ DTW และ Euclidean
**การบิดงอเวลาแบบพลวัต** () เป็นขั้นตอนวิธีสำหรับการเปรียบเทียบความคล้ายของลำดับที่มีความแตกต่างกันในด้านเวลาหรือความเร็ว เช่น รูปแบบการเดินของคนๆหนึ่งจะถูกนับว่ามีความคล้าย ไม่ว่าคนๆนั้นจะเดินอย่างรวดเร็ว เดินอย่างเชื่องช้า หรือแม้แต่เดินด้วยความเร่ง เมื่อพิจารณาจากผู้สังเกตเดียวกัน ซึ่งการบิดงอเวลาแบบพลวัตสามารถนำไปประยุกต์ได้กับวิดีโอ เสียง และ ภาพ รวมไปถึงข้อมูลต่างๆที่สามารถแปลงให้อยู่ในรูปของข้อมูลเชิงเส้นได้ ตัวอย่างหนึ่งของการประยุกต์ขั้นตอนวิธีนี้ไปใช้คือ การรู้จำคำพูด โดยใช้การบิดงอเวลาแบบพลวัต เพื่อจัดการกับคำพูดที่มีความเร็วไม่เท่ากัน แม้จะสื่อความหมายเดียวกัน

## แนวคิดเบื้องต้น
โดยทั่วไปการบิดงอเวลาแบบพลวัตเป็นวิธีที่ทำให้คอมพิวเตอร์สามารถหาการจับคู่ที่เหมาะสมของลำดับสองชุดได้ภายใต้ข้อจำกัด ลำดับเหล่านั้นจะถูกบิดเบือนแบบไม่คงที่ในหน่วยของเวลา เพื่อที่จะพิจารณาความคล้ายจากการกระจายแบบไม่คงที่ในหน่วยของเวลา โดยจะให้ผลลัพธ์ออกมาเป็นระยะทางและวิถีการปรับแนว (alignment) ที่ดี่สุด ซึ่งวิธีการพิจารณาลำดับเช่นนี้พบได้บ่อยครั้งในแบบจำลองมาร์คอฟซ่อนเร้น

## ขั้นตอนวิธี
เป้าหมายของการบิดงอเวลาแบบพลวัต คือ เพื่อเปรียบเทียบลำดับที่ขึ้นอยู่กับเวลาสองชุด

: 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) \, ดังรูป

[frame|center|Cost matrix]|เมทริกซ์ต้นทุนของลำดับ <math>X</math> และ <math>Y</math> บริเวณสีเข้มในเมทริกซ์แสดงถึงส่วนที่มีต้นทุนต่ำ และบริเวณสีอ่อนแสดงถึงส่วนที่มีต้นทุนสูง](https://th.wikipedia.org/wiki/%E0%B9%84%E0%B8%9F%E0%B8%A5%E0%B9%8C:Cost_matrix.jpg)

โดยเป้าหมายต่อไปคือการหาวิถีการปรับแนวระหว่าง 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 ] 

ซึ่งจะได้ตัวอย่างของเส้นทางบิดเบือนแบบต่าง ๆ ภายใต้เงื่อนไขดังรูป

center|thumb|500px|เส้นทางการบิดเบือนภายใต้เงื่อนไขแบบต่างๆ


โดยต้นทุนทั้งหมดของเส้นทางบิดเบือน 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'\, โดย

ซึ่งสุดท้ายแล้วจะได้ระยะทางบิดเบือนที่เหมาะสมดังรูป

center|thumb|500px|เส้นสีขาวในรูปแสดงถึงเส้นทางการบิดงอเวลาแบบพลวัตบนเมทริกซ์ต้นทุน

## ความซับซ้อนเชิงเวลา
ขั้นตอนวิธีการบิดงอเวลาแบบพลวัตแบบทั่วไปจะมีอัตราการเติบโตแบบชี้กำลัง แต่เมื่อใช้กำหนดการพลวัตในการแก้ปัญหาจะมีความซับซ้อนเชิงเวลาเป็น O (MN) \, เมื่อ M\, และ N\, แทนความยาวของข้อมูลในแต่ละลำดับ

## การประยุกต์ใช้และ[[โอเพนซอร์ส]]ที่เกี่ยวข้อง
* lbimproved ไลบรารีภาษา C++ ได้นำเอาขั้นตอนวิธี Fast Nearest-Neighbor Retrieval มาใช้ภายใต้การบิดงอเวลาแบบพลวัต (GPL) อีกทั้งยังได้จัดเตรียมการบิดงอเวลาแบบพลวัตไว้ให้ใช้ด้วยภาษา C++
* R package dtw ได้นำเอาขั้นตอนวิธีในตระกูลการบิดงอเวลาแบบพลวัตหลากหลายรูปแบบมาใช้งาน รวมไปถึงกฎการเรียกซ้ำ และการจับคู่สายอักขระย่อย
* mlpy  ไลบรารี ภาษา Python ซึ่งได้นำเอาขั้นตอนวิธีการบิดงอเวลาแบบพลวัตมาใช้
* kinectdtw  โอเพนซอร์ซ เกี่ยวกับการรู้จำท่าทางที่ได้นำเอาขั้นตอนวิธีการบิดงอเวลาแบบพลวัตมาใช้
* Chula Engineering Newsletter  วารสารทางวิชาการของคณะวิศวกรรมศาสตร์ จุฬาลงกรณ์มหาวิทยาลัย ซึ่งได้กล่าวถึงการนำการบิดงอเวลาแบบพลวัตไปประยุกต์ใช้ในด้านต่างๆ เช่น ค้นหาฐานข้อมูล การรู้จำเสียงพูด วิเคราะห์ข้อมูลทางสถิติ

## ดูเพิ่ม
* แบบจำลองมาร์คอฟซ่อนเร้น
* การรู้จำคำพูด
* อนุกรมเวลา

## อ้างอิง
* 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 

หมวดหมู่:ขั้นตอนวิธี
หมวดหมู่:ภาษาศาสตร์คอมพิวเตอร์