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 เก็บถาวร 2011-09-19 ที่ เวย์แบ็กแมชชีน ไลบรารี ภาษา Python ซึ่งได้นำเอาขั้นตอนวิธีไดนามิกไทม์วอร์ปปิงมาใช้
• kinectdtw เก็บถาวร 2011-09-25 ที่ เวย์แบ็กแมชชีน โอเพนซอร์ซ เกี่ยวกับการรู้จำท่าทางที่ได้นำเอาขั้นตอนวิธีไดนามิกไทม์วอร์ปปิงมาใช้
• Chula Engineering Newsletter เก็บถาวร 2016-03-05 ที่ เวย์แบ็กแมชชีน วารสารทางวิชาการของคณะวิศวกรรมศาสตร์ จุฬาลงกรณ์มหาวิทยาลัย ซึ่งได้กล่าวถึงการนำไดนามิกไทม์วอร์ปปิงไปประยุกต์ใช้ในด้านต่างๆ เช่น ค้นหาฐานข้อมูล การรู้จำเสียงพูด วิเคราะห์ข้อมูลทางสถิติ

ดูเพิ่ม

• 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 เก็บถาวร 2016-03-05 ที่ เวย์แบ็กแมชชีน