พิชัยยุทธนอกตำรา
Introduction to EM algorithm
สมมติว่าคุณคือสุมาอี้
คุณโดนกวนอู เตียวหุย และจูล่ง ล้อมเมืองอยู่ ตามภาพข้างบน
เมื่อวานหลังจากถูก 3 ทัพรุมตี กองทัพคุณเหลืออยู่เพียง ทหารม้า 25 และพลธนู 10
พรุ่งนี้ขงเบ้งจะเดินทางมาถึง ดังนั้นคุณต้องตัดสินใจคืนนี้แล้วว่าจะตั้งรับอย่างไร หรือตีฝ่าทางทัพใดดี
ข้อมูลเสริมเพื่อประกอบการตัดสินใจคือ ก่อนที่เมืองจะถูกตี สายสืบของคุณได้รายงานจำนวนทหารของแต่ละกองทัพมาดังนี้
- กวนอู: ทหารม้า 10 ทหารเดินเท้า 100 และพลธนู 10
- เตียวหุย: ทหารม้า 50 ทหารเดินเท้า 50 และพลธนู 10
- จูล่ง: ทหารม้า 60 ทหารเดินเท้า 50 และพลธนู 30
หลังจากที่ 3 ทัพถอยไปคุณได้นับจำนวนทหารข้าศึกที่เสียชีวิตได้ดังนี้
- ทหารม้า 70 ทหารเดินเท้า 100 และพลธนู 30
จากข้อมูลทั้งหมดนี้คุณควรตัดสินใจอย่างไรดี?
เพื่อความสนุกกำหนดให้
- 2 ทหารเดินเท้า = ทหารม้า
- 2 พลธนู = ทหารเดินเท้า
- 2 ทหารม้า = พลธนู
ลองคิดดูเล่น ๆ ก่อนนะครับ แล้วค่อยมาดูวิธีผมข้างล่าง
Mixture Model และ missing information
จากรายงานของสายสืบ เราสามารถประมาณอัตราส่วนของทหารแต่ละกองทัพได้ดังนี้
- กวนอู: ทหารม้า 0.08 ทหารเดินเท้า 0.84 และพลธนู 0.08
- เตียวหุย: ทหารม้า 0.455 ทหารเดินเท้า 0.455 และพลธนู 0.09
- จูล่ง: ทหารม้า 0.43 ทหารเดินเท้า 0.36 และพลธนู 0.21
เราสามารถมองตัวเลขข้างบนเป็น “ความน่าจะเป็นของทหารแต่ละประเภท ในแต่ละกองทัพ” เช่น P(ทหาร=ทหารม้า|ทัพ=กวนอู) = 0.08
เราเรียกค่านี้ว่าเป็น likelihood สำหรับทหารม้าของทัพกวนอู
สำหรับทหารคนหนึ่งความน่าจะเป็นที่เขาจะเป็น “ทหารม้า” นั้นคำนวณได้จาก
P(ทหาร=ทหารม้า) = P(ทหาร=ทหารม้า|ทัพ=กวนอู) P(ทัพ=กวนอู)
+ P(ทหาร=ทหารม้า|ทัพ=เตียวหุย) P(ทัพ=เตียวหุย)
+ P(ทหาร=ทหารม้า|ทัพ=จูล่ง) P(ทัพ=จูล่ง)
“P(ทัพ=กวนอู)” คือ “ความน่าจะเป็นที่ทหารคนหนึ่ง ๆ จะมาจากทัพของกวนอู”
เราเรียกค่าความน่าจะเป็นนี้ว่า prior ของทัพกวนอู
ก่อนที่เราจะถูกทัพทั้ง 3 โจมตีเราสามารถเอาอัตราส่วนของทหารทัพกวนอูเมื่อเทียบกับทหารทั้งหมดมาเป็นค่า prior นี้ได้ แต่เมื่อเรามีข้อมูลเพิ่ม นั่นคือจำนวนของทหารต่าง ๆ ที่เสียชีวิต เราก็น่าจะสามารถคำนวณค่า prior ที่เหมาะสมกว่าได้
ในส่วนที่เหลือนี้เราจะละ “ทหาร=” และ “ทัพ=” ไว้เพื่อความสะดวกและให้อ่านได้ง่าย
เราเรียกแบบจำลองความน่าจะเป็นแบบข้างบนนี้ว่า “แบบจำลองผสม (mixture model)” ซึ่งมีประโยชน์มากในงานด้านการรู้จำรูปแบบ
ในกรอบการทำงานของแบบจำลองผสมเราเรียกทัพต่าง ๆ นี้ว่า องค์ประกอบ (component)
ปัญหาหลักในการประมาณค่าตัวแปรของแบบจำลองผสมคือเรามีข้อมูลไม่ครบ หรือเราเรียกว่าเรามี missing information ซึ่งทำให้เราไม่สามารถประมาณค่าตัวแปรได้ตามปกติ
เช่นถ้าเราพิจารณาแบบจำลอง Gaussian เราคำนวณค่าเฉลี่ย (mean) ได้จากค่าเฉลี่ยเลขคณิต (arithmetic mean) ของค่าที่เราสังเกตได้ แต่ถ้าเราพิจารณาแบบจำลองผสม Gaussian เราไม่สามารถคำนวณค่าเฉลี่ยของแต่ละองค์ประกอบเช่นนี้ได้ ด้วยสูตรเดียวกัน เป็นต้น
EM algorithm
ในตัวอย่างนี้เมื่อเรานับจำนวนทหารที่เสียชีวิต เราไม่รู้ว่าทหารเหล่านั้นมาจากทัพใด ดังนั้นเราไม่สามารถประมาณค่า prior ของทัพต่าง ๆ ที่เข้าโจมตีได้อย่างตรงไปตรงมา
อัลกอริทึมมาตรฐานในการประมาณค่าของตัวแปรของแบบจำลองผสม (prior ในตัวอย่างนี้) คือ Expectation-Maximization (EM) algorithm
แนวความคิดของ EM แบบง่ายสุด ๆ คือ
- สมมติว่าเรามีข้อมูลที่ขาด แล้วให้เราเขียนสมการในการคำนวณตัวแปรของระบบจากตัวอย่างทั้งหมดที่มี
เช่นให้ s(1), …, s(200) เป็นทหารที่เสียชีวิต s(t) อาจเป็นทหารม้า ทหารเดินเท้า หรือพลธนูก็ได้
สมมติว่าเรารู้ว่าทหารคนใดบ้างมาจากทัพกวนอู ให้ g(1), …, g(200) แทนข้อมูลนี้โดยให้ g(t)=1 ถ้าทหาร s(t) มาจากทัพกวนอู และ =0 ถ้ามาจากทัพอื่น
ในกรณีนี้เราคำนวณ prior ของทัพกวนอูได้จากผลบวก
P(กวนอู) = (g(1)+g(2)+…+g(200)) / 200
(นั่นคือเราประมาณค่า prior จากอัตราส่วนของทหารทัพกวนอูนั่นเอง) - แทนที่ค่าถ่วงน้ำหนัก 0–1 ในสมการที่ได้ใน step ก่อนนี้ด้วย ความน่าจะเป็นภายหลัง (posterior probability) เราจะได้สมการการ update ตัวแปรของแบบจำลองเราในแบบของ EM
ในกรณีนี้คือให้เราแทนที่ g(t) ด้วย P(กวนอู|s(t)) และผลที่ได้คือ
P(กวนอู) = (P(กวนอู|s(1))+P(กวนอู|s(2))+…+P(กวนอู|s(200))) / 200
เรารู้ว่าทหาร s(1), …, s(200) นั้นแบ่งเป็น ทหารม้า 70 ทหารเดินเท้า 100 และพลธนู 30 ดังนั้นสมการข้างบนเขียนใหม่ได้ว่า
P(กวนอู) = 0.35 P(กวนอู|ทหารม้า)
+ 0.5 P(กวนอู|ทหารเดินเท้า)
+0.15 P(กวนอู|พลธนู)
สำหรับการคำนวณความน่าจะเป็นภายหลังนั้นทำได้โดย
P(กวนอู|ทหารม้า) = P(ทหารม้า|กวนอู) P(กวนอู) / P(ทหารม้า)
จะเห็นว่าค่า prior P(กวนอู) นั้นปรากฏอยู่ในการคำนวณความน่าจะเป็นภายหลัง และเราก็นำเอาค่าที่ได้นี้มาคำนวณ P(กวนอู) ใหม่
นั่นคือการทำงานของ EM algorithm นั้นอยู่ในรูปวนซ้ำ เราใช้ค่าตัวแปรปัจจุบันในการคำนวณความน่าจะเป็นภายหลัง และเราเอาค่าความน่าจะเป็นภายหลังนี้กลับมาใช้ในการปรับค่าตัวแปร สลับกันไปมา จนกว่าค่าที่ได้จะนิ่ง
ลงมือคำนวณ
สำหรับโจทย์ของเราเมื่อเรานำเอาค่า likelihood ต่าง ๆ มาใส่จะได้ว่า
- P(ทหารม้า) = 0.08 P(กวนอู) + 0.455 P(เตียวหุย) + 0.43 P(จูล่ง)
- P(ทหารเดินเท้า) = 0.84 P(กวนอู) + 0.455 P(เตียวหุย) + 0.36 P(จูล่ง)
- P(พลธนู) = 0.08 P(กวนอู) + 0.09 P(เตียวหุย) + 0.21 P(จูล่ง)
และเมื่อเรานำมาใส่สูตรการ update ค่า prior จะได้ว่า
- P(กวนอู)* = 0.028 P(กวนอู)/P(ทหารม้า)
+ 0.42 P(กวนอู)/P(ทหารเดินเท้า)
+0.012 P(กวนอู)/P(พลธนู) - P(เตียวหุย)* = 0.15925 P(เตียวหุย)/P(ทหารม้า)
+ 0.2275 P(เตียวหุย)/P(ทหารเดินเท้า)
+0.0135 P(เตียวหุย)/P(พลธนู) - P(จูล่ง)* = 0.1505 P(จูล่ง)/P(ทหารม้า)
+ 0.18 P(จูล่ง)/P(ทหารเดินเท้า)
+0.0315 P(จูล่ง)/P(พลธนู)
เราใส่ดอกจันไว้ข้างซ้ายเพื่อจะบอกว่ามันคือค่าใหม่ที่ได้ในแต่ละ iteration
เราสามารถกำหนดค่าตั้งต้นให้กับ prior P(กวนอู), P(เตียวหุย) และ P(จูล่ง) = 1/3 ก็ได้ หรือจะประมาณเอาจากจำนวนทหารในทัพก็ได้ เมื่อเราทำการปรับไป 10–20 ครั้งค่า prior ที่ได้ไม่ต่างกันมาก คือประมาณ 0.24, 0.3, 0.46 สำหรับ P(กวนอู), P(เตียวหุย) และ P(จูล่ง) ตามลำดับ
หนีไงดี
จากค่า prior ที่ได้ (0.24, 0.3, 0.46) เรานำไปประมาณจำนวนทหารที่เสียชีวิตของทัพต่าง ๆ ได้ (อันนี้ไม่เกี่ยวกับ EM แระ แค่เอาค่าความน่าจะเป็นมาใช้)
ก่อนอื่นเราสามารถคำนวณความน่าจะเป็นภายหลังได้ดังต่อไปนี้
P(กวนอู|ทหารม้า) = 0.08 P(กวนอู) / (0.08 P(กวนอู) + 0.455 P(เตียวหุย) + 0.43 P(จูล่ง))
= 0.08*0.24/( 0.08*0.24 + 0.455*0.3 + 0.43*0.46)
= 0.05 (โดยประมาณ)
ด้วยวิธีเดียวกันจะได้ว่า P(เตียวหุย|ทหารม้า) =0.39 และ P(จูล่ง|ทหารม้า) = 0.56
ดังนั้นจากทหารม้า 70 คนก็ควรจะมาจากทัพทั้ง 3 ดังต่อไปนี้ 4, 27, 39
ด้วยวิธีเดียวกันจะได้ว่า P(กวนอู|ทหารเดินเท้า) =0.4, P(เตียวหุย|ทหารเดินเท้า) =0.27 และ P(จูล่ง|ทหารเดินเท้า) =0.33
นั่นคือทหารเดินเท้า 100 คนน่าจะมาจากทัพทั้ง 3 ดังต่อไปนี้ 40, 27, 33
และด้วยวิธีเดียวกันจะได้ว่า P(กวนอู|พลธนู) = 0.13, P(เตียวหุย|พลธนู) = 0.19
P(จูล่ง|พลธนู) = 0.68
พลธนู 30 คนนั้นน่าจะมาจากทัพทั้ง 3 ดังต่อไปนี้ 4, 6, 20
ดังนั้นทัพทั้ง 3 จะเหลือทหารคือ
- กวนอู: ทหารม้า 6 ทหารเดินเท้า 60 และพลธนู 6
- เตียวหุย: ทหารม้า 23 ทหารเดินเท้า 23 และพลธนู 4
- จูล่ง: ทหารม้า 21 ทหารเดินเท้า 17 และพลธนู 10
เราเหลือทหารม้า 25 และพลธนู 10
- ถ้าเราหนีไปทางทัพกวนอู ทหารม้าเราไม่สามารถกำจัดทหารเดินเท้าได้หมดแน่ ๆ ทหารเดินเท้าที่เหลือก็จะเก็บพลธนูเราได้
- ถ้าเราหนีไปทางทัพเตียวหุย พลธนูเราพอจะจัดการกับพลธนูเขาได้หมดและจัดการกับทหารม้าได้ครึ่งหนึ่ง จากนั้นทหารม้าเราสามารถตีฝ่าทหารเดินเท้าหนีได้สบาย ๆ
- ถ้าเราหนีไปทางทัพจูล่ง ทหารม้าและพลธนูเรากับเขาจะหักล้างกันเกือบพอดี แต่ทหารเราที่เหลือไม่พอที่จะตีฝ่าทหารเดินเท้าได้
ถ้าให้ผมเลือก ผมคงเลือกหนีทางทัพเตียวหุยนั่นเอง ถ้าเราจัดทัพดี ๆ คือไม่ปล่อยให้ทหารเดินเท้าเขามาจัดการพลธนูเราก่อน เราก็พอจะตีฝ่าได้ ถ้าไปอีก 2 ทางคงไม่รอด
(หวังว่าผมจะไม่คำนวณผิดนะ 555)
ส่งท้าย
โจทย์นี้มาจากความพยายามหา application ของ EM algorithm ที่ไม่ใช่พวก การเรียนของ Gaussian mixture model หรือ HMM ตามปกติ
หวังว่าจะทำให้คนสนใจ EM algorithm มากขึ้นนะครับ
ปล. แนวความคิดของ EM แบบง่าย ๆ ข้างบนนี้ใช้ได้ดีในกรณีง่าย ๆ แต่บางกรณีเช่นเมื่อองค์ประกอบต่าง ๆ ในแบบจำลองใช้ตัวแปรร่วมกัน การคำนวณเช่นนี้อาจให้ผลที่ผิดได้ ในกรณีนี้ต้องไปดู EM algorithm ฉบับเต็มนะครับ
Have fun :)
