ขั้นตอนวิธี EM
- ผู้เสนอ
- Dempster, Laird & Rubin
- ปี
- 1977
- ประเภท
- Iterative optimization algorithm
- กลุ่มวิธี
- Estimation
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
ขั้นตอนวิธี Expectation-Maximization (EM) เป็นกระบวนการหาค่าเหมาะสมที่สุดแบบวนซ้ำเพื่อค้นหาค่าประมาณภาวะน่าจะเป็นสูงสุด (maximum likelihood) หรือค่าประมาณภาวะน่าจะเป็นสูงสุด ณ สัจนิยมภายหลัง (maximum a posteriori) ของพารามิเตอร์ในแบบจำลองทางสถิติที่มีตัวแปรแฝงหรือข้อมูลที่ขาดหายไป Dempster, Laird, และ Rubin ได้นำเสนอ EM ในบทความสำคัญของพวกเขาในปี 1977 โดย EM จะสลับระหว่างการคำนวณค่าคาดหวังของล็อกภาวะน่าจะเป็นของข้อมูลสมบูรณ์ (E-step) และการหาค่าสูงสุดของล็อกภาวะน่าจะเป็นนั้นเทียบกับพารามิเตอร์ (M-step) ซึ่งรับประกันว่าภาวะน่าจะเป็นจะไม่ลดลงแบบโมโนโทนในการวนซ้ำแต่ละครั้ง
แนวคิดเบื้องหลังวิธีการ
ลองจินตนาการถึงการพยายามเรียนรู้กฎของเกมโดยการเฝ้าดูผู้เล่นที่คุณมองไม่เห็นไพ่ของพวกเขา ในแต่ละรอบคุณจะเดาว่าพวกเขาน่าจะมีไพ่อะไรบ้างจากสิ่งที่คุณสังเกตเห็น จากนั้นคุณจะปรับปรุงแบบจำลองกฎของคุณโดยสมมติว่าการเดาเหล่านั้นถูกต้อง EM ทำเช่นนี้อย่างแม่นยำ: E-step จะเติมข้อมูลที่ขาดหายไปในเชิงความน่าจะเป็นโดยใช้ค่าประมาณพารามิเตอร์ปัจจุบัน และ M-step จะปรับแบบจำลองใหม่เสมือนว่าค่าที่เติมเข้าไปเหล่านั้นเป็นการสังเกตจริง
ประวัติศาสตร์
ขั้นตอนวิธีนี้ได้รับการรวมและตั้งชื่ออย่างเป็นทางการโดย Arthur Dempster, Nan Laird และ Donald Rubin ในบทความ JRSS-B ปี 1977 ของพวกเขา ซึ่งยังคงเป็นหนึ่งในบทความสถิติที่ถูกอ้างอิงมากที่สุดเท่าที่เคยตีพิมพ์ บทความนี้ได้สรุปขั้นตอนวิธีเฉพาะกรณีที่พัฒนาขึ้นอย่างอิสระสำหรับปัญหาข้อมูลที่ขาดหายไปโดยเฉพาะในช่วงก่อนหน้า ทศวรรษต่อมาได้มีการพัฒนาส่วนขยายจำนวนมาก รวมถึงขั้นตอนวิธี ECM, ECME, AECM และ SEM ซึ่งช่วยขยายขอบเขตการใช้งานและเร่งความเร็วในการลู่เข้าในสถานการณ์จริงหลายประการ
ควรใช้เมื่อใด
ใช้ขั้นตอนวิธี EM เมื่อข้อมูลมีค่าที่ขาดหายไป สถานะที่ซ่อนอยู่ หรือตัวแปรแฝง และคุณต้องการค่าประมาณภาวะน่าจะเป็นสูงสุด เหมาะอย่างยิ่งสำหรับแบบจำลองส่วนผสมเกาส์เซียน (Gaussian mixture models) แบบจำลองมาร์คอฟซ่อนเร้น (hidden Markov models) การวิเคราะห์ปัจจัย (factor analysis) และการเติมข้อมูลที่ขาดหายไป (missing-data imputation) ข้อสมมติฐานที่สำคัญคือข้อมูลที่ขาดหายไปนั้นขาดหายไปแบบสุ่ม (MAR) และแบบจำลองข้อมูลสมบูรณ์สามารถจัดการได้ ข้อจำกัดรวมถึงความไวต่อการกำหนดค่าเริ่มต้น การลู่เข้าสู่จุดสูงสุดเฉพาะที่ที่เป็นไปได้ และการลู่เข้าที่ช้าใกล้จุดอานม้า ทางเลือกอื่น ๆ ได้แก่ การหาค่าเหมาะสมที่สุดแบบใช้เกรเดียนต์ร่วมกับการหาปริพันธ์เชิงตัวเลข (numerical integration) การอนุมานแบบแปรผัน (variational inference) หรือวิธีการ MCMC
ข้อจำกัดและข้อควรพิจารณา
- การลู่เข้าสู่จุดสูงสุดเฉพาะที่แทนที่จะเป็นจุดสูงสุดทั่วโลกเมื่อพื้นผิวภาวะน่าจะเป็นมีหลายโหมด
- อาจแสดงการลู่เข้าที่ช้ามาก (เชิงเส้น) เมื่อสัดส่วนของข้อมูลที่ขาดหายไปมีขนาดใหญ่
- กำหนดให้นักวิเคราะห์ต้องระบุแบบจำลองข้อมูลสมบูรณ์และการแจกแจงของตัวแปรแฝง
- EM มาตรฐานไม่ได้ให้เมทริกซ์ความแปรปรวนร่วมของข้อมูลที่สังเกตได้ของค่าประมาณโดยตรง จำเป็นต้องมีขั้นตอนเสริม (เช่น วิธีของ Louis หรือขั้นตอนวิธี SEM) สำหรับค่าความคลาดเคลื่อนมาตรฐาน
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- รับประกันการเพิ่มขึ้นแบบโมโนโทนของภาวะน่าจะเป็นของข้อมูลที่สังเกตได้ในการวนซ้ำทุกครั้ง ทำให้มั่นใจได้ถึงการลู่เข้าที่เสถียร
- เปลี่ยนปัญหาข้อมูลที่ขาดหายไปที่ยากให้เป็นลำดับของการหาค่าเหมาะสมที่สุดของข้อมูลสมบูรณ์ที่สามารถจัดการได้
- สามารถนำไปใช้ได้อย่างกว้างขวางในแบบจำลองตระกูลเอ็กซ์โพเนนเชียล (exponential-family models) แบบจำลองส่วนผสม (mixture models) และกรอบงานตัวแปรแฝง (latent-variable frameworks)
- มีการอัปเดต M-step ในรูปแบบปิด (closed-form) สำหรับแบบจำลองมาตรฐานหลายแบบ ทำให้การนำไปใช้มีประสิทธิภาพ
การประยุกต์ใช้
- การปรับแบบจำลองส่วนผสมเกาส์เซียนสำหรับการจัดกลุ่มและการประมาณความหนาแน่น
- การฝึกแบบจำลองมาร์คอฟซ่อนเร้นสำหรับการรู้จำเสียงพูดและการวิเคราะห์ลำดับทางชีวภาพ
- การเติมข้อมูลหลายชุดและการวิเคราะห์ข้อมูลที่ขาดหายไปในการวิจัยทางคลินิกและสังคมศาสตร์
- การประมาณพารามิเตอร์ในการวิเคราะห์ปัจจัยและการวิเคราะห์ชั้นแฝง
- การแบ่งส่วนภาพและการสร้างภาพใหม่ในการถ่ายภาพทางการแพทย์
วิธีการทำงาน
วิธีการทำงาน
ก่อนที่การวนซ้ำจะเริ่มต้นขึ้น นักวิเคราะห์จะเลือกค่าเริ่มต้นสำหรับพารามิเตอร์ที่ไม่ทราบค่า ซึ่งระบุด้วย theta-0 ค่าเหล่านี้สามารถเลือกได้แบบสุ่ม จากการปรับแบบจำลองที่ง่ายขึ้น หรือจากความรู้ในสาขา คุณภาพของการกำหนดค่าเริ่มต้นอาจส่งผลต่อจุดสูงสุดเฉพาะที่ที่ขั้นตอนวิธีจะลู่เข้า ดังนั้นการเริ่มต้นใหม่แบบสุ่มหลายครั้งจึงเป็นแนวทางปฏิบัติทั่วไป
สูตร
\text{Choose initial parameter estimates } \theta^{(0)}เมื่อกำหนดค่าประมาณพารามิเตอร์ปัจจุบัน theta-t แล้ว E-step จะคำนวณ Q ซึ่งเป็นค่าคาดหวังของล็อกภาวะน่าจะเป็นของข้อมูลสมบูรณ์เหนือการแจกแจงของตัวแปรแฝง Z ที่ไม่ถูกสังเกต โดยมีเงื่อนไขจากข้อมูลที่สังเกตได้ X ค่าคาดหวังนี้จะแทนที่ปริมาณที่ไม่ทราบค่าด้วยค่าประมาณเชิงความน่าจะเป็นโดยไม่ต้องผูกมัดกับค่าที่ถูกเติมเพียงค่าเดียว
สูตร
Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]M-step จะหาค่าสูงสุดของฟังก์ชัน Q จาก E-step เทียบกับ theta ซึ่งจะให้ค่าประมาณที่อัปเดต theta-(t+1) เนื่องจากล็อกภาวะน่าจะเป็นของข้อมูลสมบูรณ์มักจะง่ายกว่าในการหาค่าสูงสุดเมื่อเทียบกับภาวะน่าจะเป็นของข้อมูลที่สังเกตได้แบบรอบนอก ขั้นตอนนี้จึงมักจะสามารถจัดการได้แม้ว่าการหาค่าภาวะน่าจะเป็นสูงสุดโดยตรงจะไม่สามารถทำได้
สูตร
\theta^{(t+1)} = \arg\max_{\theta} \, Q(\theta \mid \theta^{(t)})E-step และ M-step จะถูกทำซ้ำสลับกันไป หลังจากการวนซ้ำแต่ละรอบ ล็อกภาวะน่าจะเป็นของข้อมูลที่สังเกตได้จะถูกประเมิน การวนซ้ำจะหยุดลงเมื่อการเปลี่ยนแปลงของล็อกภาวะน่าจะเป็น (หรือในเวกเตอร์พารามิเตอร์) ลดลงต่ำกว่าค่าความคลาดเคลื่อน epsilon ที่ผู้ใช้กำหนด Dempster และคณะ ได้พิสูจน์แล้วว่าแต่ละรอบไม่สามารถลดภาวะน่าจะเป็นของข้อมูลที่สังเกตได้ ซึ่งรับประกันการลู่เข้าที่เสถียร
สูตร
\text{Repeat E- and M-steps until } |\ell(\theta^{(t+1)}) - \ell(\theta^{(t)})| < \epsilonข้อผิดพลาดที่พบบ่อย
- การใช้การกำหนดค่าเริ่มต้นแบบสุ่มเพียงครั้งเดียวมีความเสี่ยงที่จะสิ้นสุดที่จุดสูงสุดเฉพาะที่ที่ไม่ดี ควรทำการเริ่มต้นใหม่หลายครั้งเสมอและเลือกผลลัพธ์ที่มีล็อกภาวะน่าจะเป็นสุดท้ายสูงสุด
- การประกาศการลู่เข้าเร็วเกินไปโดยการตรวจสอบเฉพาะการเปลี่ยนแปลงพารามิเตอร์แทนที่จะเป็นล็อกภาวะน่าจะเป็นของข้อมูลที่สังเกตได้ อาจทำให้ได้ค่าประมาณที่ไม่ถูกต้อง
- การใช้ EM เมื่อข้อมูลขาดหายไปโดยไม่เป็นแบบสุ่ม (MNAR) โดยไม่มีการปรับแบบจำลอง อาจทำให้เกิดอคติที่เป็นระบบในค่าประมาณ
- การละเลยปัญหาการสลับป้ายกำกับ (label-switching problem) ในแบบจำลองส่วนผสมนำไปสู่การกำหนดองค์ประกอบที่ไม่สามารถตีความได้แม้หลังจากการลู่เข้าที่ถูกต้อง
คำถามที่พบบ่อย
ขั้นตอนวิธี EM ลู่เข้าสู่จุดสูงสุดทั่วโลกเสมอหรือไม่?
ไม่ EM รับประกันเพียงแค่การค้นหาจุดสูงสุดเฉพาะที่ (หรือจุดอานม้า) ของภาวะน่าจะเป็นของข้อมูลที่สังเกตได้ เมื่อพื้นผิวภาวะน่าจะเป็นมีหลายโหมด ผลลัพธ์สุดท้ายจะขึ้นอยู่กับการกำหนดค่าเริ่มต้น การรันขั้นตอนวิธีจากจุดเริ่มต้นที่แตกต่างกันหลายจุดและเก็บผลลัพธ์ที่มีล็อกภาวะน่าจะเป็นสูงสุดเป็นวิธีแก้ไขปัญหาที่เป็นมาตรฐานในทางปฏิบัติ
EM แตกต่างจากการหาค่าเหมาะสมที่สุดของภาวะน่าจะเป็นสูงสุดโดยตรงอย่างไร?
MLE โดยตรงจะหาค่าสูงสุดของล็อกภาวะน่าจะเป็นของข้อมูลที่สังเกตได้ ซึ่งอาจเกี่ยวข้องกับการหาปริพันธ์ที่จัดการไม่ได้เหนือตัวแปรแฝง EM หลีกเลี่ยงปัญหานี้โดยการหาค่าสูงสุดของค่าคาดหวังของล็อกภาวะน่าจะเป็นของข้อมูลสมบูรณ์แบบวนซ้ำ ซึ่งมักจะสามารถจัดการได้ในเชิงวิเคราะห์ ข้อแลกเปลี่ยนคือ EM อาจลู่เข้าช้า ในขณะที่วิธีการที่ใช้เกรเดียนต์อาจเร็วกว่าเมื่อมีเกรเดียนต์ของภาวะน่าจะเป็นรอบนอก
เมื่อใดที่ควรเลือกการเติมข้อมูลแบบ MICE แทนขั้นตอนวิธี EM?
MICE (Multiple Imputation by Chained Equations) เป็นที่นิยมมากกว่าเมื่อข้อมูลมีตัวแปรประเภทผสม ความสัมพันธ์ที่ไม่เป็นเชิงเส้น หรือโครงสร้างปฏิสัมพันธ์ที่ซับซ้อนซึ่งยากต่อการเข้ารหัสในแบบจำลองข้อมูลสมบูรณ์แบบพารามิเตอร์เดียว EM เป็นธรรมชาติมากกว่าเมื่อมีแบบจำลองร่วมที่ระบุไว้อย่างดีสำหรับตัวแปรทั้งหมดและการอนุมานมีเป้าหมายที่พารามิเตอร์ของแบบจำลองมากกว่าชุดข้อมูลที่ถูกเติม
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B, 39(1), 1–38.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว