การกำจัดตัวแปร (VE) เป็น อัลกอริทึม การอนุมานที่ แม่นยำและเรียบง่ายทั่วไป ในแบบจำลองกราฟิกเชิงความน่าจะเป็นเช่นเครือข่ายเบย์เซียนและฟิลด์สุ่มมาร์คอฟ [ ^{1 ] สามารถ}ใช้สำหรับการอนุมาน สถานะ สูงสุดภายหลัง (MAP) หรือการประมาณการการแจกแจงแบบมีเงื่อนไขหรือ แบบชายขอบเหนือชุดย่อยของตัวแปร อัลกอริทึมนี้มีความซับซ้อนของเวลาแบบเอกซ์ โพเนนเชียล แต่ในทางปฏิบัติอาจมีประสิทธิภาพสำหรับกราฟที่มีความกว้างของต้นไม้ต่ำหากใช้ลำดับการกำจัดที่เหมาะสม

ปัจจัยหรือที่เรียกว่าศักยภาพของตัวแปร ซึ่งช่วยลดความซับซ้อนของอัลกอริทึม ได้อย่างมาก คือความสัมพันธ์ระหว่างการกำหนดค่าตัวแปร แต่ละครั้ง กับจำนวนที่ไม่เป็นลบ ซึ่งโดยทั่วไปจะใช้สัญลักษณ์[ ^{2 ] ปัจจัย}ไม่จำเป็นต้องมีการตีความที่กำหนดไว้ตายตัว เราอาจดำเนินการกับปัจจัยที่มีการแสดงที่แตกต่างกัน เช่น การแจกแจงความน่าจะเป็นหรือการแจกแจงแบบมีเงื่อนไข^{[ 2 ]}การแจกแจงร่วมมักจะมีขนาดใหญ่เกินกว่าจะจัดการได้ เนื่องจากความซับซ้อนของการดำเนินการนี้เป็นแบบเลขชี้กำลัง ดังนั้นการกำจัดตัวแปรจึงเป็นไปได้มากขึ้นเมื่อคำนวณเอนทิตีที่แยกตัวประกอบ ${\displaystyle f}$${\displaystyle V}$${\displaystyle v}$${\displaystyle f}$${\displaystyle f(x)}$

อัลกอริทึม 1 เรียกว่า sum-out (SO) หรือ marginalization จะกำจัดตัวแปรเดียวออกจากชุดปัจจัย^{[ 3 ]}และส่งคืนชุดปัจจัยที่ได้ อัลกอริทึม collect-relevant จะส่งคืนปัจจัยเหล่านั้นที่เกี่ยวข้อง กับ ตัวแปร${\displaystyle v}$${\displaystyle \phi }$${\displaystyle \phi }$${\displaystyle v}$

อัลกอริทึม 1 sum-out( , ) ${\displaystyle v}$${\displaystyle \phi }$

${\displaystyle \Phi }$= รวบรวมปัจจัยที่เกี่ยวข้องกับ${\displaystyle v}$

${\displaystyle \Psi }$= ผลคูณของตัวประกอบทั้งหมดใน${\displaystyle \Phi }$

${\displaystyle \tau =\sum _{v}\Psi }$

กลับ${\displaystyle (\phi -\Phi )\cup \{\tau \}}$

ตัวอย่าง

ที่นี่เรามีการแจกแจงความน่าจะเป็นร่วมกันตัวแปร สามารถรวมเข้าด้วยกันได้ระหว่างชุดของการแทนที่ โดยที่ชุดขั้นต่ำจะต้องตรงกันกับตัวแปรที่เหลือ ค่าของไม่เกี่ยวข้องเมื่อเป็นตัวแปรที่จะรวมเข้าด้วยกัน^{[ 2 ]}${\displaystyle v}$${\displaystyle Vv}$${\displaystyle v}$

${\displaystyle V_{1}}$	${\displaystyle V_{2}}$	${\displaystyle V_{3}}$	${\displaystyle V_{4}}$	${\displaystyle V_{5}}$	${\displaystyle Pr(.)}$
จริง	จริง	จริง	เท็จ	เท็จ	0.80
เท็จ	จริง	จริง	เท็จ	เท็จ	0.20

หลังจากกำจัดแล้วการอ้างอิงของมันจะถูกตัดออกไป และเราจะเหลือเพียงการกระจายตัวตามตัวแปรที่เหลืออยู่และผลรวมของแต่ละค่าเท่านั้น ${\displaystyle V_{1}}$

${\displaystyle V_{2}}$	${\displaystyle V_{3}}$	${\displaystyle V_{4}}$	${\displaystyle V_{5}}$	${\displaystyle Pr(.)}$
จริง	จริง	เท็จ	เท็จ	1.0

การแจกแจงผลลัพธ์ที่ตามมาจากการดำเนินการรวมผลลัพธ์จะช่วยตอบคำถามที่ไม่ได้กล่าวถึง[ ^{2 ] นอกจาก}นี้ควรสังเกตว่าการดำเนินการรวมผลลัพธ์นั้นสามารถสลับที่ได้ ${\displaystyle V_{1}}$

การคำนวณผลคูณระหว่างปัจจัยหลายตัวส่งผลให้ได้ปัจจัยที่เข้ากันได้กับการกำหนดค่าเพียงครั้งเดียวในแต่ละปัจจัย^{[ 2 ]}

อัลกอริทึม 2ตัวประกอบหลายตัว ( , ) ^{[ 2 ]}${\displaystyle v}$${\displaystyle \phi }$

${\displaystyle Z}$= การรวมกันของตัวแปรทั้งหมดระหว่างผลคูณของปัจจัย${\displaystyle f_{1}(X_{1}),...,f_{m}(X_{m})}$

${\displaystyle f}$= ตัวประกอบเหนือ ที่ สำหรับทั้งหมด ${\displaystyle f}$${\displaystyle f}$${\displaystyle f}$

สำหรับแต่ละอินสแตนซ์${\displaystyle z}$

สำหรับ 1 ถึง${\displaystyle m}$

${\displaystyle x_{1}=}$การกำหนดค่าตัวแปรให้สอดคล้องกับ${\displaystyle X_{1}}$${\displaystyle z}$

${\displaystyle f(z)=f(z)f_{i}(x_{i})}$

กลับ${\displaystyle f}$

การคูณตัวประกอบไม่เพียงแต่มีคุณสมบัติการสลับที่เท่านั้น แต่ยังมีคุณสมบัติการจัดกลุ่มด้วย

รูปแบบการสอบถามที่พบบ่อยที่สุดคือในรูปแบบที่และเป็นเซตย่อยที่ไม่ซ้ำกันของและสังเกตได้ว่ามีค่าเท่ากับอัลกอริทึมพื้นฐานในการคำนวณ p(X|E = e) เรียกว่าการกำจัดตัวแปร (VE) ซึ่งเสนอครั้งแรกใน^{[ 1 ]}${\displaystyle p(X|E=e)}$${\displaystyle X}$${\displaystyle E}$${\displaystyle U}$${\displaystyle E}$${\displaystyle e}$

นำมาจาก^{[ 1 ]}อัลกอริทึมนี้คำนวณจากเครือข่ายเบย์เซียนแบบไม่ต่อเนื่อง B VE เรียก SO เพื่อกำจัดตัวแปรทีละตัว โดยเฉพาะอย่างยิ่งในอัลกอริทึม 2 คือเซต C ของตารางความน่าจะเป็นแบบมีเงื่อนไข (ต่อไปนี้เรียกว่า "CPTs") สำหรับ B คือรายการของตัวแปรสอบถามคือรายการของตัวแปรที่สังเกตคือรายการค่าที่สังเกตที่สอดคล้องกัน และคือลำดับการกำจัดสำหรับตัวแปรโดยที่หมายถึง ${\displaystyle p(X|E=e)}$${\displaystyle \phi }$${\displaystyle X}$${\displaystyle E}$${\displaystyle e}$${\displaystyle \sigma }$${\displaystyle U-XE}$${\displaystyle XE}$${\displaystyle X\cup E}$

อัลกอริทึมการกำจัดตัวแปร VE( ) ${\displaystyle \phi ,X,E,e,\sigma }$

คูณปัจจัยด้วย CPT ที่เหมาะสมในขณะที่ σ ไม่ว่างเปล่า

ลบตัวแปรแรกออกจาก${\displaystyle v}$${\displaystyle \sigma }$

${\displaystyle \phi }$= ผลรวม${\displaystyle (v,\phi )}$

${\displaystyle p(X,E=e)}$= ผลคูณของตัวประกอบทั้งหมด${\displaystyle \Psi \in \phi }$

กลับ${\displaystyle p(X,E=e)/\sum _{X}p(X,E=e)}$

การหาลำดับที่เหมาะสมที่สุดในการกำจัดตัวแปรเป็นปัญหา NP-hard ดังนั้นจึงมีวิธีการเชิงฮิวริสติกที่สามารถนำมาใช้เพื่อเพิ่มประสิทธิภาพตามลำดับได้:

1. ระดับขั้นต่ำ : กำจัดตัวแปรที่ส่งผลให้สร้างปัจจัยที่เล็กที่สุดที่เป็นไปได้^{[ 2 ]}
2. การเติมขั้นต่ำ: โดยการสร้างกราฟแบบไม่มีทิศทางที่แสดงความสัมพันธ์ของตัวแปรที่แสดงโดย CPT ทั้งหมด ให้กำจัดตัวแปรที่จะส่งผลให้มีขอบน้อยที่สุดที่จะต้องเพิ่มหลังจากการกำจัด^{[ 2 ]}