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

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

โปรดทราบว่าขั้นตอนสุดท้ายนี้ไม่มีประสิทธิภาพสำหรับกราฟที่มีtreewidth ขนาดใหญ่ การคำนวณข้อความที่จะส่งผ่านระหว่าง supernode เกี่ยวข้องกับการทำ marginalization ที่แม่นยำเหนือตัวแปรใน supernode ทั้งสอง การดำเนินการอัลกอริทึมนี้สำหรับกราฟที่มี treewidth k จะต้องมีการคำนวณอย่างน้อยหนึ่งครั้งซึ่งใช้เวลาแบบเลขชี้กำลังใน k เป็นอัลกอริทึมการส่งข้อความ^{[ 3 ]}อัลกอริทึม Hugin ใช้การคำนวณ น้อยกว่า ในการหาคำตอบเมื่อเทียบกับ Shafer-Shenoy

• คำนวณแบบเรียกซ้ำ^{[ 3 ]}
• การเรียกซ้ำหลายครั้งของอัลกอริทึม Shafer-Shenoy ส่งผลให้เกิดอัลกอริทึม Hugin ^{[ 4 ]}
• พบโดยสมการการส่งข้อความ^{[ 4 ]}
• ศักยภาพของ ตัวแยกจะไม่ถูกจัดเก็บ^{[ 5 ]}

อัลกอริทึม Shafer-Shenoy เป็นผลคูณของต้นไม้เชื่อมต่อ^{[ 6 ]} อัลกอริทึม นี้ใช้เพราะสามารถรันโปรแกรมและสอบถามข้อมูลได้อย่างมีประสิทธิภาพมากกว่าอัลกอริทึม Hugin อัลกอริทึมนี้ทำให้การคำนวณเงื่อนไขสำหรับฟังก์ชันความเชื่อเป็นไปได้^{[ 7 ]} จำเป็นต้องมีการแจกแจงร่วม เพื่อให้การคำนวณในพื้นที่เกิดขึ้นได้ ^{[ 7 ]}

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

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

ขั้นตอนที่สามคือการตรวจสอบให้แน่ใจว่ากราฟเป็นคอร์ดัลหากยังไม่เป็นคอร์ดัล นี่คือขั้นตอนสำคัญแรกของอัลกอริธึม โดยใช้ทฤษฎีบทต่อไปนี้: ^{[ 8 ]}

ทฤษฎีบท:สำหรับ กราฟ แบบไม่มีทิศทาง G คุณสมบัติต่อไปนี้ถือว่าเทียบเท่ากัน:

• กราฟ G เป็นกราฟสามเหลี่ยม
• กราฟคลิกของ G มีต้นไม้เชื่อมต่อ
• มีการจัดลำดับการกำจัดสำหรับ G ที่ไม่ก่อให้เกิดขอบเพิ่มเติมใดๆ

ดังนั้น โดยการสร้างสามเหลี่ยมให้กับกราฟ เราจึงมั่นใจได้ว่าต้นไม้เชื่อมต่อที่สอดคล้องกันนั้นมีอยู่จริง วิธีปกติในการทำเช่นนี้คือ การกำหนดลำดับการกำจัดสำหรับโหนดต่างๆ แล้วจึงเรียกใช้อัลกอริทึมการกำจัดตัวแปร อัลกอริทึมการ กำจัดตัวแปรระบุว่าต้องเรียกใช้อัลกอริทึมทุกครั้งที่มีการสอบถามที่แตกต่างกัน^{[ 1 ]}ซึ่งจะส่งผลให้มีการเพิ่มขอบมากขึ้นให้กับกราฟเริ่มต้น ในลักษณะที่ผลลัพธ์จะเป็นกราฟคอร์ดัลกราฟคอร์ดัลทั้งหมดมีต้นไม้เชื่อมต่อ^{[ 4 ]}ขั้นตอนต่อไปคือการสร้างต้นไม้เชื่อมต่อในการทำเช่นนั้น เราใช้กราฟจากขั้นตอนก่อนหน้า และสร้างกราฟคลิกที่ สอดคล้องกัน ^{[ 9 ]}ตอนนี้ทฤษฎีบทต่อไปนี้ให้วิธีการค้นหาต้นไม้เชื่อมต่อแก่เรา: ^{[ 4 ]}

ทฤษฎีบท:กำหนดให้กราฟสามเหลี่ยมหนึ่งกราฟ ให้กำหนดน้ำหนักของขอบของกราฟคลิกด้วยจำนวนสมาชิก |A∩B| ของจุดตัดของคลิกที่อยู่ติดกัน A และ B จากนั้น ต้นไม้แผ่คลุมที่มีน้ำหนักสูงสุดของกราฟคลิกใดๆ จะเป็นต้นไม้เชื่อมต่อ

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

การใช้งาน:กราฟต้นไม้เชื่อมต่อใช้เพื่อแสดงภาพความน่าจะเป็นของปัญหา ต้นไม้สามารถกลายเป็นต้นไม้ไบนารีเพื่อสร้างโครงสร้างต้นไม้จริงได้^{[ 11 ]}การใช้งานเฉพาะเจาะจงสามารถพบได้ในตัวเข้ารหัสอัตโนมัติซึ่งรวมกราฟและเครือข่ายการส่งผ่านในขนาดใหญ่โดยอัตโนมัติ^{[ 12 ]}

การแพร่กระจายความเชื่อแบบวนลูป:วิธีการตีความกราฟที่ซับซ้อนอีกวิธีหนึ่งการแพร่กระจายความเชื่อแบบวนลูปใช้เมื่อต้องการวิธีแก้ปัญหาโดยประมาณแทนที่จะเป็นวิธีแก้ปัญหาที่แน่นอน^{[ 13 ]}เป็นการอนุมานโดยประมาณ^{[ 3 ]}

การปรับเงื่อนไข Cutset:ใช้กับชุดตัวแปรที่เล็กกว่า การปรับเงื่อนไข Cutsetช่วยให้สร้างกราฟที่ง่ายขึ้น อ่านง่ายขึ้น แต่ไม่แม่นยำ^{[ 3 ]}

• Lauritzen, Steffen L.; Spiegelhalter, David J. (1988). "การคำนวณเฉพาะที่ด้วยความน่าจะเป็นบนโครงสร้างกราฟิกและการประยุกต์ใช้กับระบบผู้เชี่ยวชาญ" วารสารของราชสมาคมสถิติ ซีรีส์ B (ระเบียบวิธี) 50 (2): 157– 224. doi : 10.1111 /j.2517-6161.1988.tb01721.x . JSTOR  2345762 . MR  0964177 .
• Dawid, AP (1992). "การประยุกต์ใช้อัลกอริทึมการแพร่กระจายทั่วไปสำหรับระบบผู้เชี่ยวชาญเชิงความน่าจะเป็น" สถิติและการคำนวณ 2 ( 1): 25– 26. doi : 10.1007/BF01890546 . S2CID  61247712 .
• Huang, Cecil; Darwiche, Adnan (1996). "การอนุมานในเครือข่ายความเชื่อ: คู่มือขั้นตอน"วารสารนานาชาติของการให้เหตุผลโดยประมาณ 15 ( 3): 225– 263. CiteSeerX  10.1.1.47.3279 . doi : 10.1016/S0888-613X(96)00069-2 .
• Lepar, V., Shenoy, P. (1998). "การเปรียบเทียบสถาปัตยกรรม Lauritzen-Spiegelhalter, Hugin และ Shenoy-Shafer สำหรับการคำนวณค่าขอบของความน่าจะเป็น" https://arxiv.org/ftp/arxiv/papers/1301/1301.7394.pdf