Dynamic time warping

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

รูปแบบของการจับคู่ลำดับของ DTW และ Euclidean

แนวคิดเบื้องต้น

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

ขั้นตอนวิธี

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

${\displaystyle X:=(x_{1},x_{2},...,x_{N})\,}$  ด้วยความยาว ${\displaystyle N\,}$  ซึ่งเป็นจำนวนเต็ม

${\displaystyle Y:=(y_{1},y_{2},...,y_{M})\,}$  ด้วยความยาว ${\displaystyle M\,}$  ซึ่งเป็นจำนวนเต็ม

โดยลำดับเหล่านี้อาจจะเป็นสัญญาณที่ไม่ต่อเนื่อง (อนุกรมเวลา) หรือ ลำดับของลักษณะเฉพาะ (feature) ที่ถูกสร้างขึ้นตามช่วงเวลา กำหนดให้ปริภูมิของลักษณะเฉพาะแทนด้วย ${\displaystyle F\,}$  ดังนั้น ${\displaystyle x_{n},y_{m}\in F}$  สำหรับ ${\displaystyle n\in [1:N]}$  และ ${\displaystyle m\in [1:M]}$  เพื่อที่จะเปรียบเทียบลักษณะเฉพาะ ${\displaystyle x,y\in F}$  จึงจำเป็นที่จะต้องคำนวณต้นทุนเฉพาะส่วน (local cost measure) หรือเรียกอีกอย่างได้ว่า การคำนวณระยะทางเฉพาะส่วน (local distance measure) ซึ่งนิยามได้เป็นฟังก์ชัน ${\displaystyle c:F\times F\rightarrow R\geqslant 0}$  ซึ่งโดยทั่วไป ${\displaystyle c(x,y)\,}$  จะมีค่าน้อย ถ้า ${\displaystyle x\,}$  และ ${\displaystyle y\,}$  มีความคล้ายกันมาก ซึ่งสำหรับแต่ละคู่ของลำดับทั้งสอง นำไปสร้าง เมทริกซ์ต้นทุน (cost matrix) ${\displaystyle C\in R^{N\times M}}$  นิยามด้วย ${\displaystyle C(n,m):=c(x_{n},y_{m})\,}$  ดังรูป

 

เมทริกซ์ต้นทุนของลำดับ ${\displaystyle X}$  และ ${\displaystyle Y}$  บริเวณสีเข้มในเมทริกซ์แสดงถึงส่วนที่มีต้นทุนต่ำ และบริเวณสีอ่อนแสดงถึงส่วนที่มีต้นทุนสูง

โดยเป้าหมายต่อไปคือการหาวิถีการปรับแนวระหว่าง ${\displaystyle X\,}$  และ ${\displaystyle Y\,}$  ที่มีต้นทุนรวมน้อยที่สุด โดยปกติแล้ว วิถีการปรับแนว จะวิ่งไปตามทางที่ต้นทุนต่ำภายในเมทริกซ์ต้นทุน ด้วยรูปแบบดังนี้

เส้นทางบิดเบือน ${\displaystyle (N,M)\,}$  เป็นลำดับ ${\displaystyle p=(p_{1},...,p_{L})\,}$  และ ${\displaystyle p_{l}=(n_{l},m_{l})\in [1:N]\times [1:M]}$  สำหรับ ${\displaystyle l\in [1:L]}$ จะสนใจเงื่อนไขดังต่อไปนี้

1. เงื่อนไขขอบเขต (Boundary condition) : ${\displaystyle p_{1}=(1,1)\,}$  และ ${\displaystyle p_{L}=(N,M)\,}$ 
2. เงื่อนไขทางเดียว (Monotonicity condition) : ${\displaystyle n_{1}\leqslant n_{2}\leqslant ...\leqslant n_{L}}$  และ ${\displaystyle m_{1}\geqslant m_{2}\geqslant ...\geqslant m_{L}}$ 
3. เงื่อนไขขนาดการเดิน (step size condition) : ${\displaystyle p_{l+1}-p_{l}\in \{(1,0),(0,1),(1,1)\}}$  สำหรับ ${\displaystyle l\in [1:L-1]}$ 

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

 

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

โดยต้นทุนทั้งหมดของเส้นทางบิดเบือน ${\displaystyle p\,}$  ระหว่าง ${\displaystyle X\,}$  และ ${\displaystyle Y\,}$  ซึ่งเกี่ยวเนื่องกับการวัดต้นทุนเฉพาะส่วน ${\displaystyle c\,}$  จะถูกนิยามด้วย
${\displaystyle c_{p}(X,Y):=\sum _{l=1}^{L}c(x_{n_{l}},y_{n_{l}})}$ 

สำหรับ เส้นทางบิดเบือนที่เหมาะสมระหว่าง ${\displaystyle X\,}$  และ ${\displaystyle Y\,}$  คือระยะทางบิดเบือน ${\displaystyle p'\,}$  ซึ่งมีต้นทุกต่ำที่สุดเมื่อเทียบกับเส้นทางบิดเบือนทั้งหมดที่เป็นไปได้ ระยะทางไดนามิกไทม์วอร์ปปิง ${\displaystyle DTW(X,Y)\,}$  ระหว่าง ${\displaystyle X\,}$  และ ${\displaystyle Y\,}$  จะถูกนิยามเป็นต้นทุนทั้งหมดของ ${\displaystyle p'\,}$  โดย

${\displaystyle DTW(X,Y)\,}$	${\displaystyle :=c_{p'}(X,Y)\,}$
	${\displaystyle =min\{c_{p}(X,Y)|p\,}$  เป็นเส้นทางบิดเบือน ${\displaystyle (N,M)\}\,}$

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

 

เส้นสีขาวในรูปแสดงถึงเส้นทางไดนามิกไทม์วอร์ปปิงบนเมทริกซ์ต้นทุน

ความซับซ้อนเชิงเวลา

ขั้นตอนวิธีไดนามิกไทม์วอร์ปปิงแบบทั่วไปจะมีอัตราการเติบโตแบบชี้กำลัง แต่เมื่อใช้กำหนดการพลวัตในการแก้ปัญหาจะมีความซับซ้อนเชิงเวลาเป็น ${\displaystyle O(MN)\,}$  เมื่อ ${\displaystyle M\,}$  และ ${\displaystyle 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