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

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

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

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

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

ขั้นตอนวิธี

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

$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\to R⩾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⩽n_2⩽...⩽n_L$ และ $m_1⩾m_2⩾...⩾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^{\prime }$ ซึ่งมีต้นทุกต่ำที่สุดเมื่อเทียบกับเส้นทางบิดเบือนทั้งหมดที่เป็นไปได้ ระยะทางการบิดงอเวลาแบบพลวัต $DTW(X,Y)$ ระหว่าง $X$ และ $Y$ จะถูกนิยามเป็นต้นทุนทั้งหมดของ $p^{\prime }$ โดย

$DTW(X,Y)$	$:=c_{p^{\prime }}(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 แม่แบบ:Webarchive ไลบรารี ภาษา Python ซึ่งได้นำเอาขั้นตอนวิธีการบิดงอเวลาแบบพลวัตมาใช้
• kinectdtw แม่แบบ:Webarchive โอเพนซอร์ซ เกี่ยวกับการรู้จำท่าทางที่ได้นำเอาขั้นตอนวิธีการบิดงอเวลาแบบพลวัตมาใช้
• Chula Engineering Newsletter แม่แบบ:Webarchive วารสารทางวิชาการของคณะวิศวกรรมศาสตร์ จุฬาลงกรณ์มหาวิทยาลัย ซึ่งได้กล่าวถึงการนำการบิดงอเวลาแบบพลวัตไปประยุกต์ใช้ในด้านต่างๆ เช่น ค้นหาฐานข้อมูล การรู้จำเสียงพูด วิเคราะห์ข้อมูลทางสถิติ

ดูเพิ่ม

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

อ้างอิง

• 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 แม่แบบ:Webarchive