Kredalnät minskar det exakta sannolikhetskravet för Bayesiska nät, vilket möjliggör en rikare representation av osäkerhet i form av slutna konvexa uppsättningar av sannolikhetsåtgärder. Den ökade expressiviteten sker på bekostnad av högre beräkningskostnader. I detta dokument presenterar vi en ny variabel elimineringsalgoritm för exakt computing posterior inferences i omfattande specificerade credal nätverk, som empiriskt visas överträffa en state-of-the-art algoritm. Algoritmen omvandlas sedan till ett bevisligen bra approximationssystem, det vill säga ett förfarande som för alla indata garanteras att returnera en lösning som inte är sämre än den optimala av en given faktor. Anmärkningsvärt visar vi att när nätverken har avgränsat trädbredden och begränsat antalet tillstånd per variabel körs approximationsalgoritmen i tid polynom i indatastorleken och i omvänt av felfaktorn, vilket är det första kända helt polynom-tids approximeringsschemat för inferens i credal nätverk.
Mauá, de Campos och Zaffalon REF visade att det fanns ett system med fullständig tillnärmning i polynomtid för nätverk av avgränsad trädbredd och avgränsad variabel kardinalitet.
Updating Credal Networks is Approximable in Polynomial Time
{'venue': 'Int. J. Approx. Reason.', 'journal': 'Int. J. Approx. Reason.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}