Markov โมเดล แบบบ้านๆ ตอนที่ 3 - Hidden Markov Models

ถ้าจะสรุปจากบทความก่อนหน้านี้ เราอาจพอบอกได้ว่า Markov model คือโมเดลรูปแบบหนึ่ง ที่ใช้พยากรณ์เหตุการณ์ใดๆ จากข้อมูลความน่าจะเป็นของเหตุการณ์ในอดีต โดยมีสมมติฐานว่า ความน่าจะเป็นของเหตุการณ์ใด จะขึ้นอยู่กับเหตุการณ์ก่อนหน้านั้นอย่างจำกัดเหตุการณ์ ซึ่งโดยทั่วไปจะสนใจเฉพาะเหตุการณ์ก่อนหน้าเพียงแค่เหตุการณ์เดียว ซึ่งเราเรียกว่า 1st order Markov assumption หรือสั้นๆ แค่ Markov assumption

แล้วอะไรคือ Hidden Markov Model (HMM) ล่ะ

ตามชื่อซึ่งมีคำว่า Hidden ก็หมายถึงว่า เราไม่ทราบเหตุการณ์ก่อนหน้าอย่างชัดเจน หรือการพยากรณ์ต้องใช้ปัจจัยอื่นมาเทียบเคียงด้วย

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

HMM เสนอว่า แม้ว่าเราจะไม่รู้ว่าเหตุการณ์ในอดีตเป็นอย่างไร (แต่ต้องรู้เหตุการณ์เริ่มต้น) ถ้าเราพอทราบเหตุการณ์ที่เกี่ยวเนื่องกัน ก็อาจเทียบเคียงเพื่อใช้พยากรณ์ได้

ตัวอย่างเช่น
สมมติว่าเราถูกขังไว้ในห้อง โดยไม่รู้สภาพอากาศจริง แต่ทราบว่ามีความสัมพันธ์ระหว่างสภาพอากาศกับการใช้ร่มของคนที่มาเยี่ยมเราในทุกๆวัน เช่น

ถ้าสภาพอากาศมีแดด ฝน และ หมอก โอกาสที่คนมาเยี่ยมจะพกร่มจะเป็น 0.1, 0.8 และ 0.3 ตามลำดับ และโอกาสที่คนมาเยี่ยมจะพกร่ม (โดยไม่สนใจสภาพอากาศเลย) คือ 0.5

สมมติว่าวันที่เราถูกขังไว้ในห้องเป็นวันที่มีแดด วันต่อมาคนมาเยี่ยมพกร่มมาด้วย โอกาสที่ฝนจะตกวันนี้เป็นเท่าใด

สิ่งที่เราต้องการจะหาคือ P(w2=rainny | w1=sunny, u2 = true)
เมื่อ w1 และ w2 คือเหตุการณ์สภาพอากาศเมื่อวาน (วันแรก) และวันนี้ (วันที่สอง) ตามลำดับ
และ u2 คือเหตุการณ์ที่คนมาเยี่ยมจะพกร่มในวันนี้ (วันที่สอง)

สิ่งที่เรารู้คือ ความน่าจะเป็นของสภาพอากาศที่ต่อเนื่องกัน P(w2 | w1) และ ความน่าจะเป็นที่ผู้มาเยี่ยมจะพกร่มในสภาพอากาศต่างๆ P(u | w) และความน่าจะเป็นที่ผู้มาเยี่ยมจะพกร่มโดยไม่ขึ้นกับสภาพอากาศ P(u)

ดังนั้นจำเป็นต้องจัดรูปแบบความสัมพันธ์ใหม่ ให้อยู่ในรูปของสามค่านี้

ก่อนอื่น มาทบทวนความน่าจะเป็นแบบมีเงื่อนไขกันเล็กน้อย
P(A|B) = P(A,B) / P(B)
หรือ
P(A,B) = P(A|B) P(B) = P(B|A) P(A)

ดังนั้น จากที่เราต้องการหา P(w2=rainny | w1=sunny, u2 = true)  ผมขอเขียนง่ายๆว่า P(w2 | w1, u2) นะครับ

P(w2 | w1, u2) = P(w2, w1, u2) / P(w1, u2)
= P(w2,w1 | u2) P(u2) / [ P(w1 | u2) P(u2) ]
= P(w2,w1 | u2) / P(w1 | u2)

แต่เนื่องจากเหตุการณ์ w1 กับ u2 ไม่ขึ้นต่อกัน (คนละวัน) P(w1 | u2) = P(w1) ตอนนี้สิ่งที่เราต้องการหาเลยเหลือเป็น
= P(w2, w1  | u2) / P(w1)

แต่เราไม่สามารถหาค่านี้ได้ เพราะสิ่งที่เรารู้มันกลับกันคือ P(u|w) ดังนั้น
เราจะใช้ทฤษฎีของ Bayes ที่เอาไว้เปลี่ยนลำดับของความน่าจะเป็นแบบมีเงื่อนไข
P(A|B) = P(B|A) P(A) / P(B)

= P(w2, w1  | u2) / P(w1)
= P(u2 | w2,w1) P(w2, w1) / P(u2) / P(w1)

จาก Markov assumption เราสนใจเฉพาะข้อมูลสภาพอากาศวันล่าสุดเท่านั้น เลยจะได้ว่า P(u2 | w2,w1) มีค่าเป็น P(u2, w2) ความสัมพันธ์ใหม่ก็เลยเหลือ
= P(u2 | w2) P(w2, w1) / [P(u2) P(w1)]

จัดรูปต่ออีกหน่อย เพราะเหลือค่าที่ไม่รู้คือ P(w2, w1) และ P(w1) ซึ่งเรารู้ว่าค่า P(w2, w1)/P(w1) มีค่าเท่ากับ P(w2 | w1)

สุดท้ายจึงได้
= P(u2 | w2) P(w2 | w1) / P(u2)

ซึ่งเมื่อกลับไปเขียนเต็มๆ จะได้ว่า
= P(u2 = true | w2 = rainy) P(w2 = rainy | w1 = sunny) / P(u2 = true)
และแทนค่าจะได้เป็น
= 0.8 x 0.05 / 0.5
= 0.08

นั่นคือ ความน่าจะเป็นที่ฝนจะตกวันนี้ เมื่อวันนี้คนมาเยี่ยมพกร่ม และเมื่อวานเป็นวันมีแดด คือ 0.08

มันก็จะงงๆตรงความน่าจะเป็นหน่อยนะครับ

Markov โมเดล แบบบ้านๆ ตอนที่ 2 - 1st order Markov assumption

เราลองมาดูตัวอย่างจาก Reference เดิมเพิ่มเติมกันครับ

ตัวอย่างที่แล้ว เราคาดการณ์เหตุการณ์ที่สามและสอง จากเหตุการณ์ที่ 1

จะเป็นอย่างไร ถ้าเราจะคาดการณ์เหตุการณ์ใดๆ จากเหตุการณ์ตั้งต้น เช่น เหตุการณ์ที่สามจากเหตุการณ์ที่ 1 เลย

สมมติว่าเรายังใช้ความน่าจะเป็นจาก finite state automaton รูปนี้

ตัวอย่างที่ 2 ถ้าวันนี้มีหมอก จงหาความน่าจะเป็นที่ฝนจะตกในวันมะรืน

ก่อนอื่นลองพิจารณาดูก่อนว่า จะมีกี่หนทางที่จะเกิดเหตุการณ์นี้ได้ จากสภาพอากาศ
วันนี้ -> พรุ่งนี้ -> มะรืน
ก็จะเป็นไปได้สามรูปแบบคือ
1. หมอก -> หมอก -> ฝน
2. หมอก -> ฝน -> ฝน
3. หมอก -> แดด -> ฝน

นั่นคือ ความน่าจะเป็นที่โจทย์ถาม ก็คือผลรวมของความน่าจะเป็นในแต่ละช่องทาง

P(W_3 = rainy | W1 = foggy)
 = P(W3 = rainy, W2= foggy | W1 = foggy) + P(W3 = rainy, W2= rainy | W1 = foggy) + P(W3 = rainy, W2= sunny | W1 = foggy)

คล้ายๆตัวอย่างที่แล้ว โดยใช้การประมาณ Markov เรารู้ว่า
 P(W3 = rainy, W2= foggy | W1 = foggy)
=  P(W3 = rainy | W2= foggy , W1 = foggy) * P(W2 = foggy | W1= foggy)
=  P(W3 = rainy | W2= foggy) * P(W2 = foggy | W1= foggy)

ดังนั้น ย้อนกลับไปสมการก่อนหน้านี้ จึงได้ว่า
P(W3 = rainy | W1 = foggy)
=  P(W3 = rainy | W2= foggy) * P(W2 = foggy | W1= foggy) + P(W3 = rainy | W2= rainy) * P(W2 = rainy | W1= foggy) + P(W3 = rainy | W2= sunny) * P(W2 = sunny | W1= foggy)
= (0.3*0.5) + (0.6*0.3) + (0.05*0.2)
= 0.15 + 0.18 + 0.01
= 0.34

Markov โมเดล แบบบ้านๆ ตอนที่ 1 - 1st order Markov assumption

วันนี้มาทางวิชาการกันหน่อย ผมจะขอสรุปเนื้อหาของ Markov models ตามเอกสารอ้างอิงนี้
Eric Fosler-Lussier, Markov Models and Hidden Markov Models: A Brief Tutorial, December 1998

ซึ่งเขียนอธิบายไว้ดีมาก รวมกับความเข้าใจของผมเอง อาจจะมีคำบัญญัติภาษาไทยแบบที่ผมเขียนเองบ้าง ขอให้ดูความหมายภาษาอังกฤษกำกับเพื่อเทียบกับตำราเล่มอื่นนะครับ

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


ผมจะลองยกตัวอย่างจากเอกสารอ้างอิงนะครับ

สมมติว่าเราอยากพยากรณ์อากาศของวันพรุ่งนี้ ถ้าเราไม่มีข้อมูลภาพถ่ายดาวเทียมหรือข้อมูลทางภูมิศาสตร์อื่นๆเลย เราอาจจะสามารถทำได้โดยการใช้ข้อมูลของวันที่ผ่านๆมา

ถ้าสภาพอากาศมีแค่สามแบบ คือ มีแดด (sunny) มีฝน (rainy) และ มีหมอก (foggy) ตลอดวันในแต่ละวัน

เมื่อเราลองเก็บสถิติสภาพอากาศในแต่ละวัน แล้วคำนวณหาค่าความน่าจะเป็นของสภาพอากาศวันพรุ่งนี้ เมื่อทราบสภาพอากาศของวันนี้ เราอาจจะได้ตารางความน่าจะเป็นแบบมีเงื่อนไข (conditional probability) ดังข้างล่าง

ความหมายของตารางจะเป็นดังตัวอย่างต่อไปนี้ เช่น
-ถ้าวันนี้มีแดด โอกาสที่พรุ่งนี้จะฝนตกคือ 0.05
ซึ่งเราสามารถเขียนเป็นสมการได้ดังรูป

 P(W2 = rainy | W1=sunny)

 เมื่อ W2 และ W1 แทนสถานะ (สภาพอากาศ) ณ วันพรุ่งนี้และวันนี้ตามลำดับ

ให้สังเกตว่าผลรวมของความน่าจะเป็นในแต่ละแถวจะเท่ากับ 1

ซึ่งก็อาจจะเอามาเขียนเป็น finite state automaton หรือ state transition diagram ได้ตามรูปนี้

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

เพื่อที่จะทำให้งานง่ายลง เราสามารถใช้การประมาณมาทดแทน โดยกำหนดว่าถ้าต้องการพยากรณ์ข้อมูลวันนี้ ให้ใช้ข้อมูลของวันก่อนหน้านี้เท่านั้น นั่นคือ

P(Wn | Wn-1, Wn-2, ..., W1) มีค่าประมาณ P(Wn | Wn-1)

การประมาณนี้มีชื่อเรียกว่า การประมาณ Markov ในลำดับชั้นแรก (First-order Markov assumption) หรือเรียกสั้นๆว่า การประมาณ Markov (Markov assumption) ซึ่งจะทำให้เราลดการเก็บข้อมูลจาก สถานะ^n เหลือแค่ สถานะ^2 เพราะสนใจข้อมูลแค่สองเวลา

กลับมาที่ตัวอย่างเรื่องสภาพอากาศ ถ้าเราใช้การประมาณ Markov แล้วเราจะสามารถตอบคำถาม "สภาพอากาศของวันมะรืนจะเป็นอย่างไร ถ้าทราบสภาพอากาศของวันนี้"

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


ตัวอย่างที่ 1 ถ้าวันนี้มีแดด โอกาสที่พรุ่งนี้จะมีแดด และ วันมะรืนจะฝนตกจะเป็นเท่าใด
เราสามารถแปลงโจทย์เป็นดังนี้

P(W3 = rainy, W2 = sunny | W1 = sunny)

ซึ่งจะมีค่าเท่ากับ

P(W3 = rainy | W2 = sunny, W1 = sunny) * P(W2 = sunny | W1 = sunny)

เมื่อเราใช้ การประมาณ Markov นิพจน์แรกก็จะถูกประมาณให้เหลือแค่ P(W3 = rainy | W2 = sunny) และค่าทั้งหมดก็จะเปลี่ยนเป็น

P(W3 = rainy | W2 = sunny) * P(W2 = sunny | W1 = sunny)

ซึ่งเมื่อแทนค่าจากตารางด้านบน จะได้คำตอบคือ 0.05 * 0.8 = 0.04
นั่นคือ ถ้าวันนี้มีแดด โอกาสที่พรุ่งนี้จะมีแดด และ วันมะรืนจะฝนตกจะเป็น 0.04

เราสามารถคิดอีกแบบ โดยใช้ state diagram ข้างต้นมาคำนวณ โดยคูณความน่าจะเป็นตามการเปลี่ยนสถานะดังรูป คือคูณเส้นสีแดง (พรุ่งนี้มีแดดเมื่อวันนี้มีแดด) กับเส้นสีน้ำเงิน (พรุ่งนี้ฝนตกเมื่อวันนี้มีแดด)

วันนี้ก็คงพอแค่นี้ก่อนนะครับ เดี๋ยวบทความถัดไปลองมาดูตัวอย่างเพิ่มเติมกัน