Skip to content
กลับไปยังผลการค้นหา

ขั้นตอนวิธี 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) สำหรับแบบจำลองมาตรฐานหลายแบบ ทำให้การนำไปใช้มีประสิทธิภาพ

การประยุกต์ใช้

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

วิธีการทำงาน

วิธีการทำงาน

1

ก่อนที่การวนซ้ำจะเริ่มต้นขึ้น นักวิเคราะห์จะเลือกค่าเริ่มต้นสำหรับพารามิเตอร์ที่ไม่ทราบค่า ซึ่งระบุด้วย theta-0 ค่าเหล่านี้สามารถเลือกได้แบบสุ่ม จากการปรับแบบจำลองที่ง่ายขึ้น หรือจากความรู้ในสาขา คุณภาพของการกำหนดค่าเริ่มต้นอาจส่งผลต่อจุดสูงสุดเฉพาะที่ที่ขั้นตอนวิธีจะลู่เข้า ดังนั้นการเริ่มต้นใหม่แบบสุ่มหลายครั้งจึงเป็นแนวทางปฏิบัติทั่วไป

สูตร
\text{Choose initial parameter estimates } \theta^{(0)}
2

เมื่อกำหนดค่าประมาณพารามิเตอร์ปัจจุบัน 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)]
3

M-step จะหาค่าสูงสุดของฟังก์ชัน Q จาก E-step เทียบกับ theta ซึ่งจะให้ค่าประมาณที่อัปเดต theta-(t+1) เนื่องจากล็อกภาวะน่าจะเป็นของข้อมูลสมบูรณ์มักจะง่ายกว่าในการหาค่าสูงสุดเมื่อเทียบกับภาวะน่าจะเป็นของข้อมูลที่สังเกตได้แบบรอบนอก ขั้นตอนนี้จึงมักจะสามารถจัดการได้แม้ว่าการหาค่าภาวะน่าจะเป็นสูงสุดโดยตรงจะไม่สามารถทำได้

สูตร
\theta^{(t+1)} = \arg\max_{\theta} \, Q(\theta \mid \theta^{(t)})
4

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 เป็นธรรมชาติมากกว่าเมื่อมีแบบจำลองร่วมที่ระบุไว้อย่างดีสำหรับตัวแปรทั้งหมดและการอนุมานมีเป้าหมายที่พารามิเตอร์ของแบบจำลองมากกว่าชุดข้อมูลที่ถูกเติม

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. 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
    คัดลอกแล้ว