คลังเก็บป้ายกำกับ: Markov Model

Hidden Quantum Markov Model

ตอนนี้งานวิจัยมันก้าวหน้าไปไกลมาก นอกจากจะต้องสนใจเรียนรู้ของเดิมแล้ว เรายังต้องสนใจเรียนรู้ดักทางของใหม่ ๆ อีก

เริ่มแรก Markov Model ซึ่งมีการอนุมานว่าความน่าจะเป็นของ State ปัจจุบัน เกิดจากความน่าจะเป็นของ State ก่อนหน้า ดังนั้น ทุก ๆ State จึงมีการยึดโยงกับ State ก่อนหน้า เหมือนกับการทำนายดินฟ้าอากาศ เพื่อหาความน่าจะเป็นในการเกิดปรากฎการณ์ ฟ้าโปร่ง, ฝนตก หรือ มีเมฆ โดยการหาความน่าจะเป็นในการเกิดปรากฎการณ์นั้น ๆ

แต่เนื่องจาก Markov Model มีข้อจำกัด จึงมีคนคิดค้น Hidden Markov Model ขึ้นมา โดยให้การอนุมานว่า ความน่าจะเป็นของ State ปัจจุบัน เกิดจากความน่าจะเป็นของ State ก่อนหน้าก็จริง แต่เราไม่สามารถรู้สิ่งที่เกิดขึ้นจาก State เหล่านั้นได้ เพราะ State เหล่านั้นถูกซ่อนอยู่ ทำให้เราต้องหาความน่าจะเป็นจาก State ที่ไม่ถูกซ่อนไว้ เหมือนกับการที่เราเป็นนักโทษ เราไม่เห็นเดือนเห็นตะวัน เราไม่รู้หรอกว่าตอนนี้ข้างนอก ฟ้าโปร่ง, ฝนตก หรือ มีเมฆ เราเพียงหาความน่าจะเป็นได้จากผู้คุมนักโทษที่เอาอาหารมาส่งเรา ว่าเขาถือร่มหรือไม่ถือร่มมา จากนั้นเราก็อนุมานต่าง ๆ นา ๆ ว่าอากาศข้างนอกน่าจะ ฟ้าโปร่ง หรือ ฝนตก หรือ มีเมฆ เป็นต้น

มาตอนนี้ไฮเทคกันไปใหญ่ คือ มีการคิดค้น Hidden Quantum Markov Model โดยการกำหนดว่า State ที่ถูกซ่อนไว้ หรือ State ที่ถูกตรวจจับได้ ไม่ได้มีเพียง 1 ค่าในช่วง 1 State หากแต่ในแต่ล่ะ State นั้นมีค่าที่เป็นไปได้มากกว่า 1 ค่า

งานนี้คงได้ Optimization กันแหลก เพราะแค่ของเดิมกว่าจะแก้ปัญหา Non Deterministic Polynomial ได้ก็แทบอ้วกแล้ว นี่เล่น 1 State มีได้มากกว่า 1 ค่า ยิ่งต้องแก้ปัญหา Non Deterministic Polynomial เข้าไปใหญ่

ไม่แน่ใจว่า Hidden Quantum Markov Model นี่ตีพิมพ์หรือยัง ถ้าตีพิมพ์แล้วก็น่าเสียดาย เพราะว่าผมคิดได้แล้วเหมือนกัน เพียงแต่หาสมการคณิตศาสตร์มารองรับไม่ได้เท่านั้นเอง (ก็คือคิดไม่ทันเขานั่นแหล่ะ)

สื่อถึง Markov Model

การจะเข้าใจ Hidden Markov Model ได้ จำเป็นที่จะต้องศึกษา Markov Model ก่อน ซึ่งการศึกษา Markov Model มันก็เหมือนกับการดูละคร คือมันมีตัวละครหลายตัว แต่ล่ะฉากก็จำเป็นที่จะต้องเดินเรื่องเพื่ออธิบายตัวละครแต่ล่ะตัว ทีนี้ผู้จัดทำละครเขาก็ไม่มีปัญญาจะปูพื้นตัวละครแต่ล่ะตัวพร้อม ๆ กันให้เราดูได้ เพราะพวกเราไม่ได้ดูทีวีที่มีหลายหน้าจอพร้อม ๆ กันแบบ CCTV ที่จะมีภาพของตัวละครแต่ล่ะตัวออกมาโลดแล่นให้เห็นพร้อม ๆ กัน ดังนั้น สิ่งที่ผู้จัดทำละครจะทำก็คือ การทยอยอธิบายตัวละครทีล่ะตัว ทีล่ะฉาก แบบเป็นลำดับ จากนั้น จึงตัดฉากไปมาระหว่างแต่ล่ะเหตุการณ์ของตัวละคร ทำให้คนดูไม่รู้สึกสะดุดไหลลื่น และมีความเข้าใจในตัวละครแต่ล่ะตัวได้

การเข้าใจ Markov Model เองก็เช่นเดียวกัน เพราะผู้อธิบายมักจะใช้วิธีการเล่าเรื่องตัดฉากไปมา ระหว่างตัวโมเดล, ไดอะแกรม, ตัวอย่าง และ สมการคณิตศาสตร์ จึงทำให้บางครั้งถ้าเราตามไม่ทัน เราอาจจะงงได้

มายกตัวอย่าง Markov Model อย่างง่ายกันดีกว่า นั่นคือ Model ของความน่าจะเป็นในการโยนเหรียญหนึ่งเหรียญ โดยมีสถานะที่เป็นไปได้สองสถานะคือ หัว และ ก้อย

C360_2013-01-16-10-44-57
ภาพที่ 1

Markov Model มีสมมติฐานที่ว่า ความน่าจะเป็นของสถานะปัจจุบัน จะขึ้นกับความน่าจะเป็นของสถานะก่อนหน้า ดังนั้น ก็เลยมีการวาดความหมายออกมาแบบภาพที่ 1 ซึ่งถ้าเป็นคนมีพื้นฐานก็จะเข้าใจได้อย่างลาง ๆ ว่ามันมีการเคลื่อนผ่านอย่างสัมพันธ์กัน, มีการให้ค่าน้ำหนักกับการเคลื่อนผ่าน และ มีการแทนโน่นนี่นั่นด้วยตัวแปรสองมิติ เป็นต้น

C360_2013-01-16-10-45-28
ภาพที่ 2

ถ้าเราเอาภาพที่ 1 มาทำเป็น Matrix เราก็จะได้เป็นภาพที่ 2 เป็นการย่อภาพแบบ Model ให้กลายเป็นแบบ Matrix ซึ่งจะดูง่ายต่อความเข้าใจมาก ๆ

ภาพที่ 3
ภาพที่ 3

แต่ถึงกระนั้น ก็ยังจำเป็นที่จะต้องอธิบายให้เป็นสมการตามภาพที่ 3 เพื่ออธิบายให้เข้าใจว่า แต่ล่ะแถวของแนวนอนใน Matrix เมื่อบวกรวมกันแล้วต้องได้ค่าเท่ากับ 1 หรือก็คือ ความน่าจะเป็นของการเคลื่อนออกจากสถานะปัจจุบันไปยังสถานะหลาย ๆ อันที่เป็นไปได้ทั้งหมด รวมกันยังไงก็ต้องเท่ากับ 1

ภาพที่ 4
ภาพที่ 4

และยังต้องใช้สมการเพื่ออธิบายในภาพที่ 4 เพื่อให้เข้าใจว่าความน่าจะเป็นของแต่ล่ะเส้นทางมันมาได้ยังไง ซึ่งอ่านแล้วก็ดูเข้าใจยากมาก แต่แปลได้ง่าย ๆ ว่า ความน่าจะเป็นจะเกิดขึ้นได้ ต่อเมื่อมีการเคลื่อนจากสถานะหนึ่งไปยังอีกสถานะหนึ่งนั่นแหล่ะ

ภาพที่ 5
ภาพที่ 5

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

ทีนี้เมื่อเราได้ Model เอย สมการเอย และ Matrix เอยมาเรียบร้อยแล้ว จากนั้นเราก็จำเป็นที่จะต้องมาเข้าใจถึง “ความเป็นไปได้” ในการเกิด “ความน่าจะเป็น” อีกทีนึง

ภาพที่ 6
ภาพที่ 6

จากภาพที่ 6 ซึ่งถูกเรียกด้วยศัพท์เทคนิคว่า Trellis Diagram เผยให้เราเห็นว่า ในแต่ล่ะครั้งที่เราโยนเหรียญ มันมี “ความเป็นไปได้” ทั้งหมดในเส้นทางที่จะเกิด “ความน่าจะเป็น” ยังไงบ้าง ซึ่งภาพที่ 6 นี้สอดคล้องกับภาพที่ 1 คือ ภาพที่ 1 อธิบายในแง่ของการไหลเวียนแบบหยินหยาง ในขณะที่ภาพที่ 2 อธิบายในแง่ของการไหลเวียนตามแกนเวลา

สุดท้าย เมื่อเราเข้าใจในการไหลเวียนแบบหยินหยาง และ เข้าใจในการไหลเวียนตามแกนเวลาแล้ว เราก็จะมาจบที่สมการคณิตศาสตร์ง่าย ๆ ตามภาพที่ 7

ภาพที่ 7
ภาพที่ 7

สมการในภาพที่ 7 ได้อธิบายถึง “ความเป็นไปได้” ที่จะเกิด “ความน่าจะเป็น” ตาม Trellis Diagram ในภาพที่ 6 ซึ่งสมการนี้ดูแล้วปวดกบาลมาก แต่สามารถแปลได้ใจความง่าย ๆ ว่า ถ้าอยากรู้ความน่าจะเป็นของสถานะปัจจุบัน ก็เอาความน่าจะเป็นของสถานะก่อนหน้าซึ่งเป็นไปได้ทั้งหมดมาคูณกันซะ (หรืออาจะมีบวกด้วยถ้าจำเป็น) แล้วพอคำนวณกันเสร็จแล้วก็ไปคูณกับสถานะตั้งต้นนู่น แค่นี้ก็จะรู้ความน่าจะเป็นของสถานะปัจจุบันแล้ว

สรุปที่อยากจะบอกก็คือ อ่านพวกนี้ต้องมองให้เหมือนดูละคร มันมีตัดฉากไปมาหลายที ต้องอ่านแล้วเข้าใจตามมันทัน

ประเด็นความเข้าใจใน Hidden Markov Models

Hidden Markov Models หรือ HMMs เป็นส่วนขยายของ Markov Models ดังนั้น เราจึงต้องศึกษา Markov Models ก่อน ทีนี้พอเราศึกษาเสร็จแล้ว เราก็จะต้องเตรียมพื้นฐานอย่างหนึ่งก่อนศึกษา Hidden Markov Models นั่นก็คือ เราต้องไปศึกษา การอนุมานแบบเบย์ หรือ Bayesian inference ซะก่อน เพราะสมการหลาย ๆ อย่างที่ใช้ใน Hidden Markov Models มันประยุกต์มาจาก Bayesian inference

สิ่งที่เป็นประเด็นอย่างหนึ่งในการทำความเข้าใจกับ Hidden Markov Models ก็คือ จริตของผู้เผยแพร่ความรู้ ผู้เผยแพร่ความรู้บางคนใช้สมการทางคณิตศาสตร์เพื่ออธิบายความเข้าใจ บางคนใช้รูปภาพเพื่ออธิบายความเข้าใจ และบางคนใช้เมตริกซ์เพื่ออธิบายความเข้าใจ

สำหรับผู้เผยแพร่ที่ใช้รูปภาพเพื่ออธิบายความเข้าใจใน Hidden Markov Models ก็มีหลายสำนัก บางสำนักก็ใช้รูปภาพเต็มรูปแบบพร้อมพารามิเตอร์ประกอบ บางสำนักก็ใช้รูปภาพแบบง่ายสุดเพื่ออธิบาย

อีกประเด็นหนึ่งก็คือ การอธิบาย Hidden Markov Models จำเป็นจะต้องอธิบายในทุก ๆ ขั้นตอนอย่างละเอียด แต่ผู้เผยแพร่มักละเลยข้ามจุดเล็ก ๆ น้อย ๆ ซึ่งสำคัญ โดยคิดว่าผู้ศึกษาคงเข้าใจเองได้ว่าจุดเล็ก ๆ ที่ขาดหายไปนั้น ควรจะเอาอะไรมาเติมเต็มให้สมบูรณ์ ยกตัวอย่างเช่น มีการอธิบายว่า Hidden Markov Models ก็คล้าย ๆ กับ Dynamic Bayesian inference และได้ข้ามการพิสูจน์สูตร โดยไม่ได้บอกว่าต้องใช้สูตรของ Bayesian inference เข้ามาช่วยคำนวณด้วย เป็นต้น

นอกจากนี้ ยังมีประเด็นเรื่องของทฤษฎีความน่าจะเป็น ซึ่งเป็นแกนหลักของ Hidden Markov Models ซึ่งอย่างที่เรารู้ ๆ กันว่า ทฤษฎีความน่าจะเป็น คือทฤษฎีที่เราจะคำนวณเพื่อให้ได้ผลลัพท์จากอัตราส่วนของ จำนวนเหตุการณ์ที่เป็นไปได้ หารด้วย จำนวนเหตุการณ์ทั้งหมด โดยบางสำนักที่เผยแพร่ Hidden Markov Models ก็จะเน้นอธิบายถึงแต่วิธีการหา จำนวนเหตุการณ์ที่เป็นไปได้ ในขณะที่บางสำนักก็จะอธิบายถึงแต่ จำนวนเหตุการณ์ทั้งหมด เป็นต้น

สำหรับประเด็นถัดไปก็เป็นเรื่องของการทำให้สมบูรณ์ โดยตัวของ Hidden Markov Models เองนั้น ไม่สามารถนำไปใช้อะไรเป็นเรื่องเป็นราวได้ จำเป็นที่จะต้องถูกนำไปใส่รายละเอียด โดยการคัดเลือกโมเดลและพารามิเตอร์ รวมทั้งใช้อัลกอริทึมต่าง ๆ เพื่อเข้ามาช่วย ดังนั้น เราจึงจำเป็นต้องศึกษาเพิ่มเติมในอัลกอริทึมต่าง ๆ ที่มีคนคิดขึ้นมาแล้ว ไม่ว่าจะเป็น Baum–Welch algorithm, Viterbi algorithm และ Forward–backward algorithm

ถ้าเราเปรียบเทียบว่า Hidden Markov Models เป็นระบบปฏิบัติการ บรรดาอัลกอริทึมต่าง ๆ อย่าง Baum–Welch algorithm, Viterbi algorithm และ Forward–backward algorithm ก็เปรียบได้กับ Device Driver ที่สร้างมาเพื่อใช้กับระบบปฏิบัติการ

ซึ่งถ้าบอกแบบนี้ก็หมายความว่า ยังมีโอกาสอีกมากมายในอนาคต ที่จะมีผู้คิดค้นวิจัยพบอัลกอริทึมใหม่ ๆ เพื่อมาใช้กับ Hidden Markov Models เหมือนกับที่มีการสร้าง Device Driver ใหม่ ๆ เพื่อมาใช้กับระบบปฏิบัติการยังไงอย่างงั้น

ส่วนประเด็นสุดท้ายเป็นเรื่องของการประยุกต์ใช้งาน Hidden Markov Models ไปยังสาขาต่าง ๆ ซึ่งปัจจุบันผู้เผยแพร่ที่ถนัดเฉพาะด้านก็จะเน้นแต่งตำราเพื่อใช้ Hidden Markov Models กับสาขาของตัวเอง โดยหนังสือที่ผมเห็นส่วนใหญ่จะเป็นการประยุกต์ทางด้าน Speech Recognition, การเงิน และ Bioinformatics

โดยสรุปแล้ว การจะทำความเข้าใจกับ Hidden Markov Models ได้ มันจึงเป็นเรื่องลำบากนิดนึง เพราะเราต้องทำความเข้าใจ 4 ลำดับอันได้แก่

  1. ทำความเข้าใจกับทฤษฎีพื้นฐานก่อนจะมาเป็น Hidden Markov Models และทฤษฎีที่เกี่ยวข้องกับมัน
  2. ทำความเข้าใจกับทฤษฎีของตัว Hidden Markov Models เอง
  3. ทำความเข้าใจกับอัลกอริทึมต่าง ๆ ที่สร้างขึ้นมาเพื่อ Hidden Markov Models ซึ่งเปรียบได้กับการทำความเข้าใจ Device Drivers ที่สร้างขึ้นมาเพื่อระบบปฏิบัติการ
  4. ทำความเข้าใจกับวิธีการในการประยุกต์ Hidden Markov Models เพื่อใช้แก้ปัญหาในเรื่องที่เราสนใจ

มันก็เลยเป็นเรื่องที่ไม่ง่าย และจึงเป็นสาเหตุว่าทำไมจึงมีงานวิจัยและวิทยานิพนธ์ในไทย ที่เกี่ยวกับ Hidden Markov Models ตีพิมพ์อยู่ไม่ถึง 50 เรื่องเท่านั้น