Approximate inference in Bayesian networks: Parameterized complexity results

محاسبه احتمالات خلفی و حاشیه ای، ستون فقرات تقریبا همه ی نتیجه گیری ها در شبکه های بیس را تشکیل می دهد. این محاسبات به طور کلی شناخته شده است، به طور دقیق و دقیق محاسبه می شود (به عنوان مثال با الگوریتم های نمونه گیری). در حالی که تحت آنچه محدودیت محاسبات دقیق را می توان قابل ردیابی (یعنی محدود کردن عرض درخت از شبکه های اخلاقی و محدود کردن توانایی متغیرها) شناخته شده است، کمتر شناخته شده تحت چه محدودیت استنتاج بیزی است قابل محاسبه است. در اینجا، ما چارچوب رسمی موجود را برای کشف پذیری تصادفی ثابت (یک آنالوگ تصادفی از قابلیت ثابت پارامتر) گسترش می دهیم و از آن برای حل این مشکل استفاده می کنیم، هر دو با تفسیر مجدد نتایج شناخته شده از ادبیات و با ارائه برخی نتایج جدید اضافی ، از جمله نتایج در پارامتر ثابت ردگیری تصادفی از نتیجه گیری تقریبی.