Dynamic time warping

จากวิกิพีเดีย สารานุกรมเสรี
รูปแบบของการจับคู่ลำดับของ DTW และ Euclidean

ไดนามิกไทม์วอร์ปปิง (อังกฤษ: 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 บริเวณสีเข้มในเมทริกซ์แสดงถึงส่วนที่มีต้นทุนต่ำ และบริเวณสีอ่อนแสดงถึงส่วนที่มีต้นทุนสูง

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

  1. เงื่อนไขขอบเขต (Boundary condition) : p_1 = (1, 1) \, และ p_L = (N,M) \,
  2. เงื่อนไขทางเดียว (Monotonicity condition) : n_1 \leqslant n_2 \leqslant . . . \leqslant n_L และ m_1 \geqslant m_2 \geqslant . . . \geqslant m_L
  3. เงื่อนไขขนาดการเดิน (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'\, โดย

DTW (X, Y ) \, := c_{p'} (X, Y ) \,
  = 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 วารสารทางวิชาการของคณะวิศวกรรมศาสตร์ จุฬาลงกรณ์มหาวิทยาลัย ซึ่งได้กล่าวถึงการนำไดนามิกไทม์วอร์ปปิงไปประยุกต์ใช้ในด้านต่างๆ เช่น ค้นหาฐานข้อมูล การรู้จำเสียงพูด วิเคราะห์ข้อมูลทางสถิติ

ดูเพิ่ม[แก้]

อ้างอิง[แก้]