การอนุมานเชิงความน่าจะเป็น

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

Definition

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

Scope

หัวข้อนี้ครอบคลุมอัลกอริทึมที่ตอบคำถามเชิงความน่าจะเป็นในแบบจำลองกราฟิก: วิธีการที่แม่นยำ เช่น การกำจัดตัวแปร, การแพร่กระจายความเชื่อในต้นไม้, และอัลกอริทึมต้นไม้เชื่อมโยง (clique-tree); และวิธีการโดยประมาณ เช่น การแพร่กระจายความเชื่อแบบวนซ้ำและการสุ่มตัวอย่างแบบมอนติคาร์โล (การสุ่มตัวอย่างแบบปฏิเสธ, การถ่วงน้ำหนักความน่าจะเป็น, และมอนติคาร์โลลูกโซ่มาร์คอฟ) โดยกล่าวถึงความยากลำบากในการคำนวณของการอนุมานและการแลกเปลี่ยนระหว่างความแม่นยำและความสามารถในการปรับขนาด โครงสร้างของแบบจำลองเองจะครอบคลุมภายใต้เครือข่ายแบบเบย์

Core questions

• จะคำนวณความน่าจะเป็นแบบมีเงื่อนไขหรือแบบมาร์จินัลจากแบบจำลองร่วมได้อย่างไรโดยไม่ต้องแจกแจงการแจกแจงทั้งหมด?
• การกำจัดตัวแปรใช้ประโยชน์จากการแยกตัวประกอบเพื่อคำนวณคำตอบที่แม่นยำอย่างมีประสิทธิภาพได้อย่างไร?
• เมื่อใดที่การอนุมานที่แม่นยำทำได้ยาก และใช้วิธีการประมาณค่าใดแทน?
• วิธีการที่ใช้การสุ่มตัวอย่างประมาณค่าความน่าจะเป็นภายหลังได้อย่างไร?

Key concepts

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

Key theories

การแพร่กระจายความเชื่อ

ในเครือข่ายที่มีโครงสร้างแบบต้นไม้ สามารถคำนวณค่าภายหลังที่แม่นยำได้โดยการส่งข้อความแบบโลคัลระหว่างโหนดที่อยู่ใกล้เคียง; การแพร่กระจายความเชื่อของ Pearl ทำการคำนวณแบบกระจายนี้ และเมื่อนำไปใช้กับกราฟแบบวนซ้ำ จะให้วิธีการอนุมานโดยประมาณที่ใช้กันอย่างแพร่หลาย

การอนุมานแบบต้นไม้เชื่อมโยง (clique-tree)

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

การอนุมานโดยประมาณโดยการสุ่มตัวอย่าง

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

Clinical relevance

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

History

การแพร่กระจายความเชื่อของ Pearl (ทศวรรษ 1980) ให้การอนุมานที่แม่นยำสำหรับเครือข่ายต้นไม้ และวิธีการต้นไม้เชื่อมโยงของ Lauritzen และ Spiegelhalter ในปี 1988 ได้ขยายการอนุมานที่แม่นยำไปยังเครือข่ายทั่วไปผ่านการคำนวณแบบโลคัลบนคลิก การตระหนักว่าการอนุมานที่แม่นยำเป็น NP-hard โดยทั่วไปได้กระตุ้นให้เกิดการทำงานอย่างกว้างขวางเกี่ยวกับการสุ่มตัวอย่างและการประมาณค่าแบบแปรผัน

Key figures

• Judea Pearl
• Steffen L. Lauritzen
• David J. Spiegelhalter
• Daphne Koller

Seminal works

• pearl1986
• lauritzen1988

Frequently asked questions

การอนุมานเชิงความน่าจะเป็นสามารถจัดการได้เสมอหรือไม่?

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

ความแตกต่างระหว่างการอนุมานที่แม่นยำและการอนุมานโดยประมาณคืออะไร?

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