Dynamic time warping

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

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

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

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

ขั้นตอนวิธี[แก้]

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

ด้วยความยาว ซึ่งเป็นจำนวนเต็ม
ด้วยความยาว ซึ่งเป็นจำนวนเต็ม

โดยลำดับเหล่านี้อาจจะเป็นสัญญาณที่ไม่ต่อเนื่อง (อนุกรมเวลา) หรือ ลำดับของลักษณะเฉพาะ (feature) ที่ถูกสร้างขึ้นตามช่วงเวลา กำหนดให้ปริภูมิของลักษณะเฉพาะแทนด้วย ดังนั้น สำหรับ และ เพื่อที่จะเปรียบเทียบลักษณะเฉพาะ จึงจำเป็นที่จะต้องคำนวณต้นทุนเฉพาะส่วน (local cost measure) หรือเรียกอีกอย่างได้ว่า การคำนวณระยะทางเฉพาะส่วน (local distance measure) ซึ่งนิยามได้เป็นฟังก์ชัน ซึ่งโดยทั่วไป จะมีค่าน้อย ถ้า และ มีความคล้ายกันมาก ซึ่งสำหรับแต่ละคู่ของลำดับทั้งสอง นำไปสร้าง เมทริกซ์ต้นทุน (cost matrix) นิยามด้วย ดังรูป

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

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

เส้นทางบิดเบือน เป็นลำดับ และ สำหรับ จะสนใจเงื่อนไขดังต่อไปนี้

  1. เงื่อนไขขอบเขต (Boundary condition) : และ
  2. เงื่อนไขทางเดียว (Monotonicity condition) : และ
  3. เงื่อนไขขนาดการเดิน (step size condition) : สำหรับ

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

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

โดยต้นทุนทั้งหมดของเส้นทางบิดเบือน ระหว่าง และ ซึ่งเกี่ยวเนื่องกับการวัดต้นทุนเฉพาะส่วน จะถูกนิยามด้วย

สำหรับ เส้นทางบิดเบือนที่เหมาะสมระหว่าง และ คือระยะทางบิดเบือน ซึ่งมีต้นทุกต่ำที่สุดเมื่อเทียบกับเส้นทางบิดเบือนทั้งหมดที่เป็นไปได้ ระยะทางไดนามิกไทม์วอร์ปปิง ระหว่าง และ จะถูกนิยามเป็นต้นทุนทั้งหมดของ โดย

  เป็นเส้นทางบิดเบือน


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

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

ความซับซ้อนเชิงเวลา[แก้]

ขั้นตอนวิธีไดนามิกไทม์วอร์ปปิงแบบทั่วไปจะมีอัตราการเติบโตแบบชี้กำลัง แต่เมื่อใช้กำหนดการพลวัตในการแก้ปัญหาจะมีความซับซ้อนเชิงเวลาเป็น เมื่อ และ แทนความยาวของข้อมูลในแต่ละลำดับ

การประยุกต์ใช้และโอเพนซอร์ซที่เกี่ยวข้อง[แก้]

  • lbimproved ไลบรารีภาษา C++ ได้นำเอาขั้นตอนวิธี Fast Nearest-Neighbor Retrieval มาใช้ภายใต้ไดนามิกส์ไทม์วอร์ปปิง (GPL) อีกทั้งยังได้จัดเตรียมไดนามิกส์ไทม์วอร์ปปิงไว้ให้ใช้ด้วยภาษา C++
  • R package dtw ได้นำเอาขั้นตอนวิธีในตระกูลไดนามิกไทม์วอร์ปปิงหลากหลายรูปแบบมาใช้งาน รวมไปถึงกฎการเรียกซ้ำ และการจับคู่สายอักขระย่อย
  • mlpy ไลบรารี ภาษา Python ซึ่งได้นำเอาขั้นตอนวิธีไดนามิกไทม์วอร์ปปิงมาใช้
  • kinectdtw โอเพนซอร์ซ เกี่ยวกับการรู้จำท่าทางที่ได้นำเอาขั้นตอนวิธีไดนามิกไทม์วอร์ปปิงมาใช้
  • Chula Engineering Newsletter วารสารทางวิชาการของคณะวิศวกรรมศาสตร์ จุฬาลงกรณ์มหาวิทยาลัย ซึ่งได้กล่าวถึงการนำไดนามิกไทม์วอร์ปปิงไปประยุกต์ใช้ในด้านต่างๆ เช่น ค้นหาฐานข้อมูล การรู้จำเสียงพูด วิเคราะห์ข้อมูลทางสถิติ

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

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