Skip to content
بازگشت به نتایج جست‌وجو

تکنیک‌های کاهش واریانس برای شبیه‌سازی مونت کارلو

معرفی‌شده توسط
Hammersley & Morton (antithetic variates, 1956); Lavenberg & Welch (control variates, 1981); importance sampling roots in Kahn & Marshall (1953)
سال
1950s–1980s (technique family)
نوع
Simulation variance-reduction technique family

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

تکنیک‌های کاهش واریانس خانواده‌ای از روش‌ها هستند که با دستیابی به دقت تخمین یکسان با تعداد کمتری نمونه‌گیری تصادفی، کارایی شبیه‌سازی مونت کارلو را بهبود می‌بخشند. این خانواده که از دهه ۱۹۵۰ به تدریج توسعه یافته است — با واریانس‌های پادهم‌نام (antithetic variates) که به همرسلی و مورتون نسبت داده می‌شود، واریانس‌های کنترل (control variates) که توسط لاونبرگ و ولش فرموله شده است، و نمونه‌گیری اهمیت (importance sampling) که ریشه در کَهن و مارشال دارد — شامل واریانس‌های پادهم‌نام (AV)، واریانس‌های کنترل (CV)، نمونه‌گیری اهمیت (IS) و طبقه‌بندی (stratification) است که هر کدام از یک ویژگی ساختاری متفاوت کمیت هدف برای کاهش واریانس تخمین‌گر بدون ایجاد بایاس بهره می‌برند.

شهود پشت روش

مونت کارلو استاندارد با میانگین‌گیری از تعداد زیادی نمونه‌گیری تصادفی مستقل کار می‌کند. نقطه ضعف آن این است که نمونه‌گیری‌های کاملاً تصادفی می‌توانند تکراری باشند — بسیاری از نمونه‌ها در مناطقی قرار می‌گیرند که اطلاعات کمی ارائه می‌دهند، و خطاهای مثبت و منفی به طور مؤثر خنثی نمی‌شوند. تکنیک‌های کاهش واریانس با مهندسی تصادفی بودن این مشکل را برطرف می‌کنند. واریانس‌های پادهم‌نام هر نمونه را با تصویر آینه‌ای آن جفت می‌کند تا خطاها تمایل به خنثی شدن داشته باشند؛ واریانس‌های کنترل تخمین را با استفاده از یک کمیت همبسته که میانگین واقعی آن شناخته شده است، تنظیم می‌کند؛ نمونه‌گیری اهمیت نمونه‌ها را در جایی که بیشترین اهمیت را دارند متمرکز می‌کند؛ و طبقه‌بندی تضمین می‌کند که نمونه‌گیری فضای ورودی را به طور یکنواخت پوشش می‌دهد. نتیجه، دقت یکسان با ارزیابی‌های تابعی بسیار کمتر است.

تاریخ

بنیان‌های کاهش واریانس برای شبیه‌سازی مونت کارلو در دهه ۱۹۵۰ پایه‌گذاری شد. کَهن و مارشال (۱۹۵۳) نمونه‌گیری اهمیت را در زمینه انتقال ذرات هسته‌ای معرفی کردند. همرسلی و مورتون (۱۹۵۶) واریانس‌های پادهم‌نام را به عنوان راهی برای بهره‌برداری از تقارن در ورودی‌های تصادفی فرموله کردند. واریانس‌های کنترل توسط لاونبرگ و ولش در دهه ۱۹۸۰ برای استفاده در شبیه‌سازی تصادفی سیستماتیک شدند. تک‌نگاشت پل گلسرمن در سال ۲۰۰۳ نظریه و عمل این تکنیک‌ها را برای مهندسی مالی یکپارچه کرد و کتاب درسی شلدون راس در مورد شبیه‌سازی از آن زمان آن‌ها را به بخشی استاندارد از آموزش شبیه‌سازی در مقطع تحصیلات تکمیلی تبدیل کرده است. امروزه این تکنیک‌ها در امور مالی محاسباتی، مهندسی قابلیت اطمینان و هر میدانی که اجرای شبیه‌سازی پرهزینه است، مرکزی هستند.

چه زمانی استفاده شود

هنگامی که مونت کارلو استاندارد تنها با تعداد زیادی اجرا، دقت قابل قبولی ارائه می‌دهد، از تکنیک‌های کاهش واریانس استفاده کنید. AV برای انتگرال‌ده‌های هموار و یکنواخت مناسب است؛ CV برای مسائلی که در آن‌ها یک کمیت کمکی همبسته با میانگین شناخته شده در دسترس است، مناسب است؛ IS برای تخمین رویدادهای نادر یا انتگرال‌گیری روی دُم‌های سنگین مناسب است؛ طبقه‌بندی برای فضاهای ورودی با ابعاد کم مناسب است. همه تکنیک‌ها حداقل به چند صد — ایده‌آل چند هزار — تکرار نیاز دارند تا مزیت کاهش واریانس قابل مشاهده شود. آن‌ها برای کمیت‌های تصادفی پیوسته و برای هر حوزه کاربردی که در آن هزینه شبیه‌سازی محدودکننده است، مناسب هستند.

محدودیت‌ها و ملاحظات

  • هر تکنیک به دانش ساختاری مسئله نیاز دارد: AV به انتگرال‌ده یکنواخت نیاز دارد، CV به میانگین کمکی شناخته شده تحلیلی نیاز دارد، IS به توزیع پیشنهادی خوش‌طراحی شده نیاز دارد.
  • یک توزیع پیشنهادی ضعیف انتخاب شده برای نمونه‌گیری اهمیت می‌تواند واریانس را به جای کاهش، افزایش دهد.
  • ترکیب چندین تکنیک پیچیدگی پیاده‌سازی را افزایش می‌دهد و می‌تواند به طور غیرمنتظره‌ای با هم تعامل داشته باشد.
  • مزیت کاهش واریانس در تعداد تکرارهای بسیار کم (کمتر از حدود ۱۰۰۰ اجرا) ناچیز است.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • تعداد اجرای شبیه‌سازی مورد نیاز برای رسیدن به دقت هدف را به طور قابل توجهی کاهش می‌دهد و هزینه محاسباتی را کم می‌کند.
  • تکنیک‌ها را می‌توان برای کاهش واریانس مرکب ترکیب کرد (به عنوان مثال، AV با CV).
  • هیچ بایاسی معرفی نمی‌شود: تمام تکنیک‌های استاندارد تخمین‌گرهای بدون بایاس تولید می‌کنند.
  • در حوزه‌های مختلف — مالی، مهندسی، مراقبت‌های بهداشتی، تحقیق در عملیات — در هر کجا که انتگرال‌گیری مونت کارلو استفاده می‌شود، کاربرد گسترده‌ای دارد.

کاربردها

  • قیمت‌گذاری اختیار معامله در امور مالی محاسباتی، که در آن نمونه‌گیری اهمیت، نمونه‌ها را بر روی مسیرهای سودآور متمرکز می‌کند.
  • تحلیل قابلیت اطمینان و ریسک، که در آن احتمالات شکست نادر با اجرای شبیه‌سازی بسیار کمتر با استفاده از IS تخمین زده می‌شود.
  • تحلیل عملکرد صف و سیستم‌های خدماتی با استفاده از AV و CV برای کاهش طول اجرا.
  • شبیه‌سازی هزینه-اثربخشی مراقبت‌های بهداشتی، که در آن CV از یک تقریب تحلیلی شناخته شده برای مدل هزینه بهره می‌برد.
  • طراحی مهندسی تحت عدم قطعیت، که در آن نمونه‌گیری طبقه‌بندی شده پوشش در سراسر فضای پارامتر ورودی را تضمین می‌کند.

چگونه کار می‌کند

چگونه کار می‌کند

1

با بیان کمیت مورد علاقه به صورت امید ریاضی شروع کنید — به عنوان مثال، میانگین تابعی که بر روی ورودی‌های تصادفی اعمال می‌شود. این چارچوب مشخص می‌کند که نمونه‌ها از کدام توزیع احتمال می‌آیند و تخمین‌گر خام مونت کارلو قبل از اعمال هرگونه کاهش واریانس چگونه به نظر می‌رسد.

2

تکنیکی را انتخاب کنید که با ساختار مسئله مطابقت داشته باشد. واریانس‌های پادهم‌نام زمانی کار می‌کند که انتگرال‌ده (integrand) نسبت به ورودی یکنواخت باشد، بنابراین جفت کردن هر نمونه یکنواخت u با متمم آن ۱ − u همبستگی منفی و خنثی شدن خطاها را تضمین می‌کند. واریانس‌های کنترل زمانی کار می‌کند که یک کمیت همبسته با امید ریاضی تحلیلی شناخته شده وجود داشته باشد؛ تخمین‌گر با اختلاف بین میانگین شبیه‌سازی شده کنترل و میانگین شناخته شده آن تنظیم می‌شود. نمونه‌گیری اهمیت زمانی کار می‌کند که احتمال رویدادهای نادر یا با وزن بالا نیاز به افزایش داشته باشد؛ یک توزیع پیشنهادی (proposal distribution) که در دُم‌ها سنگین‌تر است جایگزین توزیع اصلی می‌شود و هر نمونه با نسبت احتمال بازوزن‌دهی می‌شود. طبقه‌بندی فضای ورودی را به طبقه‌ها تقسیم می‌کند و نمونه‌ها را به نسبت تخصیص می‌دهد و تضمین می‌کند که هیچ منطقه‌ای بیش از حد یا کمتر از حد نمونه‌گیری نشده است. تکنیک‌ها را می‌توان برای صرفه‌جویی بیشتر ترکیب کرد — به عنوان مثال، CV و AV با هم.

3

نمونه‌ها را بر اساس تکنیک انتخاب شده استخراج کنید. برای AV، نمونه‌های جفتی (u, ۱ − u) تولید کنید؛ برای IS، از توزیع پیشنهادی استخراج کنید و وزن‌های اهمیت را ثبت کنید؛ برای طبقه‌بندی، در هر طبقه استخراج کنید. تعداد تکرارها باید حداقل در حد هزاران باشد تا مزایای کاهش واریانس قابل اندازه‌گیری باشد.

4

نمونه‌ها را در یک تخمین نقطه‌ای و یک تخمین واریانس تجمیع کنید. برای AV، تخمین‌گر میانگین مقادیر تابعی جفتی است. برای CV، میانگین خام با ضریب بهینه ضربدر انحراف میانگین نمونه کنترل از امید ریاضی شناخته شده آن تصحیح می‌شود. برای IS، هر ارزیابی تابع قبل از میانگین‌گیری در وزن اهمیت آن ضرب می‌شود.

5

واریانس تخمین‌گر کاهش‌یافته واریانس را با واریانس یک تخمین‌گر مونت کارلو ساده با تعداد نمونه‌های یکسان مقایسه کنید. نسبت دو واریانس — ضریب کاهش واریانس — سود را کمی می‌کند. اگر ضریب نزدیک به ۱ باشد، تکنیک از ساختار مسئله بهره نمی‌برد و ممکن است به رویکرد متفاوتی یا تکرارهای بیشتری نیاز باشد.

دام‌های رایج

  • استفاده از واریانس‌های پادهم‌نام زمانی که انتگرال‌ده نسبت به ورودی‌ها یکنواخت نیست: فرض همبستگی منفی از بین می‌رود و روش ممکن است در واقع واریانس را افزایش دهد.
  • تخمین توزیع پیشنهادی نمونه‌گیری اهمیت که نسبت به توزیع هدف دُم‌های سبک‌تری دارد: رویدادهای نادر کمتر نمونه‌گیری می‌شوند و واریانس تخمین‌گر می‌تواند منفجر شود.
  • تخمین ضریب CV از همان نمونه‌ای که برای تخمین‌گر استفاده می‌شود بدون در نظر گرفتن بایاس القایی در اندازه‌های نمونه کوچک.
  • اجرای تکرارهای کم (کمتر از حدود ۱۰۰۰): ضریب کاهش واریانس را نمی‌توان به طور قابل اعتماد اندازه‌گیری کرد و مزیت نسبت به مونت کارلو ساده نامرئی است.
  • ترکیب AV و CV بدون تأیید اینکه ترکیب، همبستگی منفی را حفظ می‌کند: تخمین‌گر ترکیبی ممکن است به صرفه‌جویی مورد انتظار دست نیابد.

پرسش‌های متداول

کدام تکنیک را باید انتخاب کنم — AV، CV، IS، یا طبقه‌بندی؟

بر اساس ساختار مسئله خود انتخاب کنید. اگر انتگرال‌ده نسبت به ورودی‌ها یکنواخت باشد، AV ساده و مؤثر است. اگر کمیت مرتبطی دارید که امید ریاضی آن را می‌توان به صورت تحلیلی محاسبه کرد، CV معمولاً قدرتمندترین گزینه است. اگر نیاز به تخمین احتمال یک رویداد نادر یا انتگرال‌گیری روی دُم‌های سنگین دارید، IS ابزار مناسبی است. طبقه‌بندی در ابعاد کم تا متوسط که می‌خواهید پوشش یکنواخت فضای ورودی داشته باشید، خوب عمل می‌کند. تکنیک‌ها را می‌توان برای سود بیشتر ترکیب کرد.

به چند اجرای شبیه‌سازی نیاز دارم؟

مزیت کاهش واریانس تنها زمانی قابل اندازه‌گیری است که حداقل چند صد اجرا داشته باشید؛ چند هزار اجرا آستانه مطمئن‌تری است. با تعداد تکرارهای بسیار کم، ضریب کاهش واریانس را نمی‌توان به طور پایدار تخمین زد و یک تخمین‌گر مونت کارلو ساده ممکن است در واقع عملکرد مشابهی داشته باشد. به عنوان یک قاعده عملی، از این تکنیک‌ها با کمتر از ۱۰۰۰ تکرار استفاده نکنید.

آیا تکنیک‌های کاهش واریانس می‌توانند بایاس ایجاد کنند؟

خیر — تمام چهار تکنیک استاندارد (AV، CV، IS، طبقه‌بندی) در صورت پیاده‌سازی صحیح، تخمین‌گرهای بدون بایاس تولید می‌کنند. تخمین‌گر CV به تخمین دقیقی از ضریب بهینه نیاز دارد؛ تخمین آن از یک نمونه آزمایشی کوچک و استفاده مجدد از همان نمونه برای تخمین اصلی می‌تواند بایاس محدود نمونه‌ای ایجاد کند، بنابراین بهترین روش استفاده از یک نمونه آزمایشی جداگانه یا یک فرمول ضریب معتبر مجانبی است.

اگر پیشنهاد نمونه‌گیری اهمیت من ضعیف انتخاب شده باشد چه اتفاقی می‌افتد؟

یک توزیع پیشنهادی که نسبت به توزیع هدف در دُم‌ها خیلی سبک باشد، می‌تواند باعث افزایش فاجعه‌بار واریانس شود و IS را بدتر از مونت کارلو ساده کند. همیشه تأیید کنید که پیشنهاد در ناحیه مربوطه دُم‌های سنگین‌تری نسبت به هدف دارد و واریانس وزن‌های اهمیت را به عنوان یک تشخیص بررسی کنید — مقادیر وزن بسیار بزرگ نشان‌دهنده یک پیشنهاد ضعیف است.

روش‌های مرتبط

منابع

  1. Ross, S.M. (2012). Simulation (5th ed.). Academic Press.

    شابک: 978-0124158252
    کپی شد.
  2. Glasserman, P. (2003). Monte Carlo Methods in Financial Engineering. Springer.

    باز کردن مرجع DOI
    کپی شد.