استنتاج احتمالی
استنتاج احتمالی، محاسبه احتمال متغیرهای پرسوجو با توجه به شواهد مشاهدهشده در یک مدل احتمالی است که وظیفه اصلی استدلال در شبکههای بیزی و مارکوف محسوب میشود.
Definition
استنتاج احتمالی، یک توزیع پسین، مانند احتمال یک یا چند متغیر پرسوجو مشروط بر شواهد مشاهدهشده، را از یک مدل احتمالی مشخص، به صورت دقیق یا با تقریب، محاسبه میکند.
Scope
این موضوع الگوریتمهایی را پوشش میدهد که به پرسوجوهای احتمالی در مدلهای گرافیکی پاسخ میدهند: روشهای دقیق مانند حذف متغیر، انتشار باور در درختها، و الگوریتم درخت پیوندی (درخت کلاستر)؛ و روشهای تقریبی مانند انتشار باور حلقوی و نمونهبرداری مونت کارلو (نمونهبرداری رد، وزندهی احتمال، و مونت کارلو زنجیره مارکوف). این موضوع به سختی محاسباتی استنتاج و مبادلات بین دقت و مقیاسپذیری میپردازد. ساختار خود مدلها تحت عنوان شبکههای بیزی پوشش داده شده است.
Core questions
- چگونه یک احتمال شرطی یا حاشیهای از یک مدل مشترک بدون شمارش کامل توزیع محاسبه میشود؟
- چگونه حذف متغیر از فاکتورگیری برای محاسبه کارآمد پاسخهای دقیق بهره میبرد؟
- چه زمانی استنتاج دقیق غیرقابل حل است و چه روشهای تقریبی به جای آن استفاده میشود؟
- چگونه روشهای مبتنی بر نمونهبرداری احتمالات پسین را تخمین میزنند؟
Key concepts
- پرسوجوهای حاشیهای و شرطی
- حذف متغیر
- انتشار باور (انتقال پیام)
- درخت پیوندی و عرض درخت
- انتشار باور حلقوی
- نمونهبرداری رد و وزندهی احتمال
- مونت کارلو زنجیره مارکوف
- استنتاج دقیق در مقابل تقریبی
Key theories
- انتشار باور
- در شبکههای با ساختار درختی، پسینهای دقیق را میتوان با ارسال پیامهای محلی بین گرههای همسایه محاسبه کرد؛ انتشار باور پرل این محاسبه توزیعشده را انجام میدهد و با اعمال آن به گرافهای حلقوی، یک روش استنتاج تقریبی پرکاربرد را ارائه میدهد.
- استنتاج درخت پیوندی (درخت کلاستر)
- استنتاج دقیق در شبکههای عمومی را میتوان با خوشهبندی متغیرها به یک درخت از کلاسترها و انتشار پیامها بر روی آن سازماندهی کرد، که پاسخهای صحیح را در زمانی که فقط به بزرگترین کلاستر (عرض درخت) نمایی است، ارائه میدهد.
- استنتاج تقریبی با نمونهبرداری
- هنگامی که استنتاج دقیق غیرممکن است، روشهای مونت کارلو مانند وزندهی احتمال و مونت کارلو زنجیره مارکوف، نمونههایی را مطابق با شواهد برای تخمین احتمالات پسین ترسیم میکنند و دقت تضمینشده را با مقیاسپذیری مبادله میکنند.
Clinical relevance
الگوریتمهای استنتاج هستند که مدلهای احتمالی را قابل استفاده میکنند: آنها سیستمهای تشخیص و پشتیبانی تصمیم، کدهای تصحیح خطا (از طریق انتشار باور)، بینایی کامپیوتر، تشخیص گفتار، و بیوانفورماتیک را با محاسبه احتمالات متغیرهای پنهان با توجه به دادههای مشاهدهشده، قدرت میبخشند.
History
انتشار باور پرل (دهه ۱۹۸۰) استنتاج دقیق را برای شبکههای درختی فراهم کرد، و روش درخت پیوندی لوریتزن و اشپیگلهالتر در سال ۱۹۸۸ استنتاج دقیق را به شبکههای عمومی از طریق محاسبات محلی بر روی کلاسترها گسترش داد. این شناخت که استنتاج دقیق به طور کلی NP-سخت است، کارهای گستردهای را در زمینه نمونهبرداری و تقریبهای واریانسدار تحریک کرد.
Key figures
- Judea Pearl
- Steffen L. Lauritzen
- David J. Spiegelhalter
- Daphne Koller
Related topics
Seminal works
- pearl1986
- lauritzen1988
Frequently asked questions
- آیا استنتاج احتمالی همیشه قابل حل است؟
- خیر. استنتاج دقیق در شبکههای بیزی عمومی NP-سخت است و هزینه آن با عرض درخت شبکه افزایش مییابد. برای شبکههایی که درختی هستند یا عرض درخت پایینی دارند، استنتاج دقیق کارآمد است؛ در غیر این صورت از روشهای تقریبی مانند نمونهبرداری یا انتشار باور حلقوی استفاده میشود.
- تفاوت بین استنتاج دقیق و تقریبی چیست؟
- استنتاج دقیق، مانند حذف متغیر یا الگوریتم درخت پیوندی، احتمالات پسین واقعی را محاسبه میکند. استنتاج تقریبی، مانند نمونهبرداری مونت کارلو یا انتشار باور حلقوی، آنها را تخمین میزند، که در مواقعی که محاسبه دقیق برای یک مدل بزرگ یا با اتصال متراکم بسیار پرهزینه است، ضروری است.