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

การบิดงอเวลาแบบพลวัต  เป็นขั้นตอนวิธีสำหรับการเปรียบเทียบความคล้ายของลำดับที่มีความแตกต่างกันในด้านเวลาหรือความเร็ว เช่น รูปแบบการเดินของคนๆหนึ่งจะถูกนับว่ามีความคล้าย ไม่ว่าคนๆนั้นจะเดินอย่างรวดเร็ว เดินอย่างเชื่องช้า หรือแม้แต่เดินด้วยความเร่ง เมื่อพิจารณาจากผู้สังเกตเดียวกัน ซึ่งการบิดงอเวลาแบบพลวัตสามารถนำไปประยุกต์ได้กับวิดีโอ เสียง และ ภาพ รวมไปถึงข้อมูลต่างๆที่สามารถแปลงให้อยู่ในรูปของข้อมูลเชิงเส้นได้ ตัวอย่างหนึ่งของการประยุกต์ขั้นตอนวิธีนี้ไปใช้คือ การรู้จำคำพูด โดยใช้การบิดงอเวลาแบบพลวัต เพื่อจัดการกับคำพูดที่มีความเร็วไม่เท่ากัน แม้จะสื่อความหมายเดียวกัน
แนวคิดเบื้องต้น.
โดยทั่วไปการบิดงอเวลาแบบพลวัตเป็นวิธีที่ทำให้คอมพิวเตอร์สามารถหาการจับคู่ที่เหมาะสมของลำดับสองชุดได้ภายใต้ข้อจำกัด ลำดับเหล่านั้นจะถูกบิดเบือนแบบไม่คงที่ในหน่วยของเวลา เพื่อที่จะพิจารณาความคล้ายจากการกระจายแบบไม่คงที่ในหน่วยของเวลา โดยจะให้ผลลัพธ์ออกมาเป็นระยะทางและวิถีการปรับแนว (alignment) ที่ดี่สุด ซึ่งวิธีการพิจารณาลำดับเช่นนี้พบได้บ่อยครั้งในแบบจำลองมาร์คอฟซ่อนเร้น
ขั้นตอนวิธี.
เป้าหมายของการบิดงอเวลาแบบพลวัต คือ เพื่อเปรียบเทียบลำดับที่ขึ้นอยู่กับเวลาสองชุด
 <math>X := (x_1, x_2, . . . , x_N) \,</math> ด้วยความยาว <math>N\,</math> ซึ่งเป็นจำนวนเต็ม
 <math>Y := (y_1, y_2, . . . , y_M) \,</math> ด้วยความยาว <math>M\,</math> ซึ่งเป็นจำนวนเต็ม
โดยลำดับเหล่านี้อาจจะเป็นสัญญาณที่ไม่ต่อเนื่อง (อนุกรมเวลา) หรือ ลำดับของลักษณะเฉพาะ (feature) ที่ถูกสร้างขึ้นตามช่วงเวลา กำหนดให้ปริภูมิของลักษณะเฉพาะแทนด้วย <math>F\,</math> ดังนั้น <math>x_n, y_m \in F </math> สำหรับ <math> n \in [1 : N]</math> และ <math>m \in [1 : M]</math> เพื่อที่จะเปรียบเทียบลักษณะเฉพาะ <math>x, y \in F </math> จึงจำเป็นที่จะต้องคำนวณต้นทุนเฉพาะส่วน (local cost measure) หรือเรียกอีกอย่างได้ว่า การคำนวณระยะทางเฉพาะส่วน (local distance measure) ซึ่งนิยามได้เป็นฟังก์ชัน <math>c: F \times F\rightarrow R \geqslant 0</math> ซึ่งโดยทั่วไป <math>c (x,y) \,</math> จะมีค่าน้อย ถ้า <math>x\,</math> และ <math>y\,</math> มีความคล้ายกันมาก ซึ่งสำหรับแต่ละคู่ของลำดับทั้งสอง นำไปสร้าง เมทริกซ์ต้นทุน (cost matrix) <math>C \in R^{N \times M} </math> นิยามด้วย <math>C (n,m) := c (x_n, y_m) \,</math> ดังรูป
โดยเป้าหมายต่อไปคือการหาวิถีการปรับแนวระหว่าง <math>X\,</math> และ <math>Y\,</math> ที่มีต้นทุนรวมน้อยที่สุด โดยปกติแล้ว วิถีการปรับแนว จะวิ่งไปตามทางที่ต้นทุนต่ำภายในเมทริกซ์ต้นทุน ด้วยรูปแบบดังนี้
เส้นทางบิดเบือน <math> (N,M) \,</math> เป็นลำดับ <math>p = (p_1, . . . , p_L) \,</math> และ <math>p_l = (n_l,m_l) \in [1 : N] \times [1 : M]</math> สำหรับ <math>l \in [1 : L]</math>จะสนใจเงื่อนไขดังต่อไปนี้
ซึ่งจะได้ตัวอย่างของเส้นทางบิดเบือนแบบต่าง ๆ ภายใต้เงื่อนไขดังรูป
โดยต้นทุนทั้งหมดของเส้นทางบิดเบือน <math>p\,</math> ระหว่าง <math>X\,</math> และ <math>Y\,</math> ซึ่งเกี่ยวเนื่องกับการวัดต้นทุนเฉพาะส่วน <math>c\,</math> จะถูกนิยามด้วย
<math> c_p (X,Y) := \sum_{l=1}^{L} c (x_{n_l},y_{n_l}) </math>
สำหรับ เส้นทางบิดเบือนที่เหมาะสมระหว่าง <math>X\,</math> และ <math>Y\,</math> คือระยะทางบิดเบือน <math>p'\,</math> ซึ่งมีต้นทุกต่ำที่สุดเมื่อเทียบกับเส้นทางบิดเบือนทั้งหมดที่เป็นไปได้ ระยะทางการบิดงอเวลาแบบพลวัต <math>DTW (X, Y) \,</math> ระหว่าง <math>X\,</math> และ <math>Y\,</math> จะถูกนิยามเป็นต้นทุนทั้งหมดของ <math>p'\,</math> โดย
ซึ่งสุดท้ายแล้วจะได้ระยะทางบิดเบือนที่เหมาะสมดังรูป
ความซับซ้อนเชิงเวลา.
ขั้นตอนวิธีการบิดงอเวลาแบบพลวัตแบบทั่วไปจะมีอัตราการเติบโตแบบชี้กำลัง แต่เมื่อใช้กำหนดการพลวัตในการแก้ปัญหาจะมีความซับซ้อนเชิงเวลาเป็น <math>O (MN) \,</math> เมื่อ <math>M\,</math> และ <math>N\,</math> แทนความยาวของข้อมูลในแต่ละลำดับ