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

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

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

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

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

ขั้นตอนวิธี

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

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

ดูเพิ่ม

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

อ้างอิง

• 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 ที่ เวย์แบ็กแมชชีน