مقاله تابکاری متغیر در نمودارها برای بهینه سازی ترکیبی

چکیده

Several recent unsupervised learning methods use probabilistic approaches to solve combinatorial optimization (CO) problems based on the assumption of statistically independent solution variables. We demonstrate that this assumption imposes performance limitations in particular on difficult problem instances. Our results corroborate that an autoregressive approach which captures statistical dependencies among solution variables yields superior performance on many popular CO problems. We introduce subgraph tokenization in which the configuration of a set of solution variables is represented by a single token. This tokenization technique alleviates the drawback of the long sequential sampling procedure which is inherent to autoregressive methods without sacrificing expressivity. Importantly, we theoretically motivate an annealed entropy regularization and show empirically that it is essential for efficient and stable learning.

چکیده به فارسی (ترجمه ماشینی)

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