نظرية الاحتمالات من أجل تقديم دقيقة جسديا

مقدمة

في عملية التقديم ، غالبًا ما يتم استخدام حساب التكاملات المحددة متعددة الأبعاد: على سبيل المثال ، لتحديد مدى رؤية مصادر الضوء المكاني (إضاءة المنطقة) ، اللمعان الذي يصل إلى منطقة البكسل ، اللمعان الذي يصل خلال فترة زمنية ، والإشعاع الذي يدخل خلال نصف الكرة الأرضية. عادةً ما يتم حساب هذه التكاملات باستخدام تكامل مونت كارلو ، حيث يتم استبدال المكمل بتوقع تجربة عشوائية.

في هذه المقالة سوف أتحدث بالتفصيل عن عملية تكامل مونت كارلو الأساسية ، وكذلك العديد من التقنيات لتقليل تباين هذه التقنية. وسيتم ذلك من وجهة نظر عملية - من المفترض أن القارئ ليس على دراية كبيرة بنظرية الاحتمال ، لكنه لا يزال يريد تطوير خوارزميات تقديم فعالة وصحيحة.

التكاملات المعرفة

أكمل لا يتجزأ هو جزء لا يتجزأ من النموذج $$$\ int_ {a} ^ {b} f (x) dx$ حيث $$$[a، b]$ هي شريحة (أو منطقة) ، $$$x$ - العددية ، و $$$f (x)$ - وظيفة يمكن حسابها لأي نقطة في المقطع. كما هو مكتوب في ويكيبيديا ، جزء لا يتجزأ هو منطقة تحمل علامة على متن طائرة $$$x$ محدودة حسب الجدول الزمني $$$و$ ومحور $$$x$ والخطوط العمودية $$$x =$ و $$$x = b$ ( الشكل 1 أ ).

يمتد هذا المفهوم بشكل منطقي إلى عدد أكبر من الأبعاد: بالنسبة إلى تكامل مزدوج معين ، تصبح المنطقة التي تحتوي على علامة وحدة تخزين ذات علامة ( الشكل 1 ب ) ، وبصفة عامة بالنسبة لبعض تكاملات متعددة ، تصبح وحدة تخزين متعددة الأبعاد مع علامة .


الشكل 1: أمثلة لبعض التكاملات.

في بعض الحالات ، يمكن تحديد المنطقة تحليليًا ، على سبيل المثال ، لـ $$$f (x) = 2$ : على الجزء $$$[a، b]$ المنطقة سوف تكون متساوية $$$2 (b-a)$ . في حالات أخرى ، يكون الحل التحليلي مستحيلًا ، على سبيل المثال ، عندما نحتاج إلى معرفة حجم الجزء من الجبل الجليدي فوق الماء ( الشكل 1 ج ). في مثل هذه الحالات $$$f (x)$ في كثير من الأحيان يمكن تحديدها عن طريق أخذ العينات .

التكامل العددي

يمكننا حساب مساحة التكاملات المعقدة تقريبًا باستخدام التكامل العددي . مثال واحد هو مبلغ ريمان . يتم حساب هذا المبلغ عن طريق تقسيم المنطقة إلى أشكال منتظمة (على سبيل المثال ، المستطيلات) ، والتي تشكل معًا مساحة مماثلة لمنطقة حقيقية. يتم تعريف مبلغ ريمان على النحو التالي:

$$

$$\ tag {1} S = \ sum_ {i = 1} ^ {n} f (x_i) \ Delta x_i$$

$$$ن$ هو عدد الفواصل الفرعية ، و $$$\ Delta x_i = \ frac {b-a} {n}$ - عرض فاصل زمني فرعي واحد. لكل فاصل $$$i$ نحن عينة $$$و$ عند نقطة واحدة $$$x_i$ داخل الفاصل الزمني الفرعي (في الشكل 2 ، هذه النقطة هي في بداية الفاصل الزمني الفرعي).


الشكل 2: ريمان المبلغ.

تجدر الإشارة إلى أنه مع زيادة $$$ن$ يتقابل مبلغ ريمان مع القيمة الحقيقية للتكامل:

$$

$$\ tag {2} \ int_ {a} ^ {b} f (x) dx = \ lim_ {|| \ Delta x || \ to 0} \ sum_ {i = 1} ^ {n} f (x_i) \ دلتا x_i$$

يمكن أيضًا استخدام مبلغ ريمان لأبعاد كبيرة ( الشكل 3 ). ومع ذلك ، نحن هنا نواجه مشكلة: بالنسبة لوظيفة ذات معلمتين ، يجب أن يكون عدد الفواصل الفرعية أكبر بكثير إذا أردنا التوصل إلى قرار مشابه لذلك المستخدم في الحالة ثنائية الأبعاد. وتسمى هذه الظاهرة لعنة الأبعاد ، وفي أبعاد أعلى تتفاقم.


الشكل 3: ريمان مبلغ لتكامل مزدوج.

سنقوم الآن بتقييم دقة مبلغ ريمان للوظيفة التالية (اخترنا عمدا وظيفة معقدة):

$$

$$\ tag {3} f (x) = \ left | \ sin \ left (\ frac {1} {2} x + \ frac {\ pi} {2} \ right) \ tan \ frac {x} {27} + \ sin \ left (\ frac {3} {5} x ^ 2 \ right) + \ frac {4} {x + \ pi + 1} -1 \ right |$$

الرسم البياني وظيفة على قطعة $$$[- 2.5،2.5]$ هو مبين أدناه. للإشارة ، قمنا بحساب جزء لا يتجزأ من Wolfram Alpha $$$\ int _ {- 2.5} ^ {2.5} f (x)$ الحصول على المنطقة $$ . يوضح الرسم البياني على اليمين دقة التكامل العددي باستخدام مبلغ ريمان لزيادة $$$ن$ .


الشكل 4: الرسم البياني وظيفة ودقة ريمان المبلغ. حتى مع الصغيرة $$$ن$ نحصل على نتيجة دقيقة إلى حد ما.

للحصول على فكرة عن الدقة ، نعطي الأرقام: من أجل $$$ن = 50 دولا$ الخطأ هو $$$~ 2 \ times10 ^ {- 3}$ . في $$$ن = 100 دولا$ الخطأ هو $$$~ 3 \ times10 ^ {- 4}$ . يتم الحصول على الترتيب التالي من حيث الحجم مع $$$ن = 200 دولا$ .

لمزيد من المعلومات حول مبالغ Riemann ، راجع الموارد التالية:

• أكاديمية خان: https://www.khanacademy.org/math/ap-calculus-ab/ab-accumulation-riemann-sums/ab-riemann-sums/v/simple-riemann-approximation-using-rectangles
• ويكيبيديا: https://en.wikipedia.org/wiki/Riemann_sum

مونت كارلو (1)

عند التقديم ، لا يوجد تقريبًا (وربما لا شيء على الإطلاق؟) هذا يعني أننا سنواجه بسرعة لعنة الأبعاد. بالإضافة إلى ذلك ، فإن أخذ وظيفة على فترات زمنية متساوية يخضع لأخذ عينات وتشويه غير كافيين : يمكننا تخطي القيم المهمة للوظيفة أو الحصول على تداخل متبادل غير مقصود بين وظيفة العينة ونمط أخذ العينات ( الشكل 5 ).


الشكل 5: تؤدي التشوهات إلى فقدان أجزاء من وظيفة العينة (الحمراء) ، وفي هذه الحالة ، إلى تفسير غير صحيح تمامًا للوظيفة.

يتم حل هذه المشكلات باستخدام تقنية تسمى تكامل مونت كارلو . على نحو مشابه لمجموع ريمان ، فإنه يستخدم أيضًا أخذ عينات الدوال في مجموعة من النقاط ، ولكن على عكس نمط مجموع ريمان الحاسم ، فإننا نستخدم مكونًا غير محدد بشكل أساسي: أرقام عشوائية.

يعتمد تكامل مونت كارلو على الملاحظة التالية: يمكن الاستعاضة عن المكمل بتوقع تجربة عشوائية:

$$

$$\ tag {4} \ int_ {a} ^ {b} f (x) dx = (ba) E \ left [f (X) \ right] \ approx \ frac {ba} {n} \ sum_ {i = 1} ^ {n} f (X)$$

وبعبارة أخرى ، نحن عينة وظيفة $$$ن$ مرات في نقاط عشوائية داخل قطعة (يرمز إليها بواسطة رأس المال $$$X$ ) ، متوسط ​​العينات واضربها في عرض القطعة (لوظيفة أحادية البعد). كما في حالة مبلغ ريمان ، متى $$$ن$ إلى ما لا نهاية ، يتقارب متوسط ​​قيمة العينات مع التوقع ، أي القيمة الحقيقية للتكامل.

قليلا من نظرية الاحتمالات

من المهم أن نفهم كل المفاهيم المستخدمة هنا. لنبدأ مع الانتظار : هذه هي القيمة المتوقعة لعينة واحدة. لاحظ أن هذه ليست بالضرورة قيمة ممكنة ، والتي قد تبدو غير بديهية. على سبيل المثال ، عندما ندحرج القالب ، فإن التوقع يساوي $$ - متوسط ​​جميع النتائج المحتملة: $$$(1 + 2 + 3 + 4 + 5 + 6) /6=21/6=3.5$ .

المفهوم الثاني هو أرقام عشوائية . قد يبدو هذا واضحًا ، لكن بالنسبة لتكامل مونتي كارلو ، نحتاج إلى أرقام عشوائية موزعة بشكل موحد ، أي يجب أن يكون لكل قيمة احتمال متساوٍ للجيل. سنتحدث أكثر عن هذا لاحقًا.

المفهوم الثالث هو الانحراف والتباين المرتبط به. حتى عندما نأخذ عددًا صغيرًا من الأرقام ، يجب أن يكون المتوسط ​​المتوقع ، وكذلك توقع كل عينة على حدة ، هو نفسه. ومع ذلك ، عند حساب المعادلة 4 ، نادراً ما نحصل على مثل هذه القيمة. الانحراف هو الفرق بين التوقعات ونتائج التجربة: $$$X-E (X)$ .

في الممارسة العملية ، هذا الانحراف له توزيع مثير للاهتمام:


هذا رسم بياني للتوزيع الطبيعي ، أو التوزيع الغوسي : إنه يوضح أنه ليس كل الانحرافات متساوية. في الواقع ، ما يقرب من 68.2 ٪ من العينات في النطاق $$$-1 \ سيجما. 1 \ سيجما$ حيث $$$\ سيجما$ (سيغما) هو الانحراف المعياري . يمكن وصف الانحراف المعياري بطريقتين:

• الانحراف المعياري هو مقياس لتقلب البيانات.
• 95 ٪ من نقاط البيانات داخل $$$2 \ سيجما$ من المتوسط.

هناك طريقتان لتحديد الانحراف المعياري:

1. الانحراف المعياري $$$\ sigma = \ sqrt {\ frac {1} {n} \ sum_ {i = 1} ^ {n} \ left (X_i-E \ left [X \ right] \ right) ^ 2}$ : يمكن حسابه إذا كان هناك توزيع احتمالي منفصل وكان التوقع معروفًا $$$E [X]$ . هذا صحيح بالنسبة للمكعبات التي $$$X = {1،2،3،4،5،6}$ و $$$E [X] = 3.5 دولا$ . استبدال الأرقام ، نحصل عليها $$$\ سيجما = 1.71 دولا$ .
2. أيضا ، يمكن حساب الانحراف المعياري للعينات $$$\ sigma = \ sqrt {\ frac {1} {n-1} \ sum_ {i = 1} ^ {n} \ left (X_i-X \ right) ^ 2}$ . اقرأ المزيد عن هذا على ويكيبيديا .

تحقق: هل هذا صحيح؟ إذا $$$\ سيجما = 1.71 دولا$ ، نعلن أن 68.2 ٪ من العينات ضمن 1.71 من 3.5. نحن نعرف ذلك $$${2،3،4،5}$ تلبية هذا المعيار ، و $$$1$ و $$ - لا. أربعة من أصل ستة هم 66.7 ٪. إذا كان لدينا مكعب يمكن أن تنتج أي قيمة في الفاصل الزمني $$$[1..6]$ ، ثم سنحصل بالضبط 68.2 ٪.

بدلا من الانحراف المعياري ، يرتبط مفهوم التباين ، والذي يعرف باسم $$$Var \ left [X \ right] = \ sigma ^ 2$ . نظرًا لاستخدام المربع ، يكون التباين إيجابيًا دائمًا ، مما يساعد في العمليات الحسابية.

مونت كارلو (2)

أعلاه ، قمنا بحساب المعادلة 3 تقريبًا باستخدام مجموع Riemann. الآن نكرر هذه التجربة بتكامل مونت كارلو. تذكر أنه يتم تعريف تكامل مونت كارلو على النحو التالي:

$$

$$\ tag {5} \ int_ {a} ^ {b} f (x) dx = (ba) E \ left [f (X) \ right] \ approx \ frac {ba} {n} \ sum_ {i = 1} ^ {n} f (X)$$

دعنا نترجم هذا إلى رمز C:

double sum = 0; for( int i = 0; i < n; i++ ) sum += f( Rand( 5 ) - 2.5 ); sum = (sum * 5.0) / (double)n; 

نتيجة للقيم من $$$ن = 2 دولا$ إلى $$$ن = 200 دولا$ هو مبين في الرسم البياني أدناه. من ذلك ، يمكن افتراض أن تكامل مونت كارلو يتجلى أسوأ بكثير من مبلغ ريمان. يقول فحص دقيق للخطأ ذلك مع $$$ن = 200 دولا$ الخطأ المتوسط ​​لمبلغ ريمان هو $$ ومونت كارلو $$ .


الشكل 6: خطأ مونتي كارلو في عينات 2..200.

في أبعاد أعلى ، يتم تقليل هذا الاختلاف ، ولكن لا يتم القضاء عليه بالكامل. المعادلة الموضحة أدناه هي نسخة موسعة من تلك المستخدمة أعلاه ، وتستقبل معلمتين:

$$

$$f (x، y) = \ left | \ sin \ left (\ frac {1} {2} x + \ frac {\ pi} {2} \ right) \ tan \ frac {x} {27} + \ sin \ left (\ frac {1} {6} x ^ 2 \ right) + \ frac {4} {x + \ pi + 1} -1 \ right | \ left | \ sin \ left (1.1y \ right) \ cos \ اليسار (2.3x \ يمين) \ يمين | (6) دولا$$

الشكل 7: الرسم البياني للمعادلة أعلاه.

في مجال التعريف $$$x∈ [-2.5،2.5] ، y∈ [-2.5،2.5]$ حجم محدود من هذه الوظيفة والطائرة $$$س س$ متساو $$ . في $$$ن = 400 دولا$ (20 × 20 عينة) خطأ مبلغ ريمان هو $$ . بنفس العدد من العينات ، يكون متوسط ​​خطأ تكامل Monte Carlo هو $$ . هذا أفضل من النتيجة السابقة ، لكن الفرق لا يزال كبيراً. لفهم هذه المشكلة ، سوف ندرس تقنية تقليل تشتت تكامل مونت كارلو المعروفة باسم "التقسيم الطبقي".


الشكل 8: تأثير التقسيم الطبقي ؛ عينات ذات توزيع ضعيف ؛ ب) عينات مع توزيع موحد.

التقسيم الطبقي يزيد من توحيد الأرقام العشوائية. في الشكل 8 أ ، تُستخدم ثمانية أرقام عشوائية لأخذ الوظيفة. نظرًا لأن كل رقم يتم اختياره عشوائيًا ، فإنه يتحول في الغالب إلى توزيع غير متساوٍ على مجال التعريف. يوضح الشكل 8 ب تأثير الطبقة: تنقسم منطقة التعريف إلى ثمانية طبقات ، ويتم اختيار موقع عشوائي في كل طبقة ، مما يحسن التوحيد.

التأثير على التباين واضح إلى حد ما. يوضح الشكل 9 أ الرسم البياني للنتائج مع وبدون التقسيم الطبقي. يوضح الشكل 9 ب خطأ القيمة التقريبية. في $$$ن = 10 دولا$ الخطأ المتوسط ​​ل 8 طبقات هو $$ . لمدة 20 طبقة - $$ و 200 طبقة تنخفض إلى $$ . بناءً على هذه النتائج ، يبدو أنه من المفيد استخدام عدد كبير من الطبقات. ومع ذلك ، فإن التقسيم الطبقي له عيوب تزيد مع زيادة عدد الطبقات. أولاً ، يجب أن يكون عدد العينات دائمًا مضاعفًا لعدد الطبقات ؛ ثانياً ، كما هو الحال في مجموع ريمان ، تعاني التقسيم الطبقي من لعنة الأبعاد.


الشكل 9: التقسيم الطبقي والتباين: أ) قيمة تقريبية لعدد العينات من ن = 2 إلى ن = 200 ؛ ب) الانحراف.

أهمية العينة

في الأقسام السابقة ، أخذنا المعادلات بالتساوي. تمديد وظيفة التكامل في مونت كارلو يسمح لنا بتغيير الوضع:

$$

$$\ tag {7} \ int_ {a} ^ {b} f (x) dx = (ba) E \ left [f (X) \ right] \ approx \ frac {ba} {n} \ sum_ {i = 1} ^ {n} \ frac {f (X)} {p (X)}$$

هنا $$$p (X)$ هي دالة كثافة الاحتمال (pdf) : تحدد الاحتمالية النسبية بأن متغير عشوائي سوف يأخذ قيمة معينة.

لمتغير عشوائي موحد في الفاصل الزمني $$$0..1 دولا$ ، pdf هي 1 ( الشكل 10 أ) ، وهذا يعني أن كل قيمة لها نفس الاحتمال في الاختيار. إذا قمنا بدمج هذه الوظيفة $$$[0،0.5]$ ثم نحصل على الاحتمال $$ من ماذا $$$X <\ frac {1} {2}$ . إلى $$$X> \ frac {1} {2}$ من الواضح أننا نحصل على نفس الاحتمال.


الشكل 10: توزيعات الاحتمالات. p) ثابت لقوات الدفاع الشعبي حيث يكون لكل عينة احتمال متساو في الاختيار ؛ ب) قوات الدفاع الشعبي ، حيث العينات أقل من 0.5 لديها احتمال أعلى للاختيار.

يوضح الشكل 10 ب ملف pdf آخر. في هذه الحالة ، يكون احتمال إنشاء رقم أقل $$$\ frac {1} {2}$ يساوي 70 ٪. يمكن تنفيذ ذلك باستخدام مقتطف الشفرة التالي:

 float SamplePdf() { if (Rand() < 0.7f) return Rand( 0.5f ); else return Rand( 0.5f ) + 0.5f; } 

يتم تعريف هذا pdf على النحو التالي:

$$

$$\ tag {8} p (x) = \ left \ {\ start {matrix} 1.4 ، إذا كان x <\ frac {1} {2} \\ 0.6 ، وإلا \ end {matrix} \ right.$$

الأرقام $$ و $$ تعكس الحاجة إلى هذا الاحتمال $$$x <\ frac {1} {2}$ كان يساوي 70 ٪. عند دمج قوات الدفاع الشعبي من قبل $$$[0 .. \ frac {1} {2}]$ يعطي $$$1.4 \ مرة \ frac {1} {2}$ و $$ غير $$ . يوضح هذا مطلبًا مهمًا لجميع ملفات pdf بشكل عام: يجب أن تكون نتيجة دمج pdf 1. والشرط الآخر هو ذلك $$$p (x)$ لا يمكن أن يكون صفرا إذا $$$f (x)$ غير صفري: فهذا يعني أن الأجزاء $$$و$ لديك احتمال أخذ عينات صفر ، مما يؤثر بوضوح على القيمة.

بعض النصائح لفهم مفهوم pdf:

• لا تصف إحدى قيم pdf الاحتمال: لذلك ، يمكن أن يكون pdf محليًا أكبر من 1 (على سبيل المثال ، كما هو الحال في pdf الذي تم فحصه للتو).
• ومع ذلك ، فإن التكامل على نطاق تعريف pdf هو الاحتمال ، مما يعني أن تكامل pdf يعطي 1.

يمكن تفسير قيمة واحدة كإمكانية نسبية لظهور قيمة محددة.

تجدر الإشارة إلى أن التوزيع الطبيعي هو دالة توزيع الاحتمالات: إنه يعطينا احتمال أن يكون بعض المتغير العشوائي في فترة زمنية معينة. في حالة التوزيع الطبيعي ، هذا المتغير العشوائي هو انحراف عن الوسط. مثل أي ملف pdf لائق ، تكون نتيجة دمج التوزيع الطبيعي 1.

لذلك ، تسمح لنا المعادلة 7 بأخذ عينات غير موحدة. إنه يعوضها عن طريق قسمة كل عينة على الاحتمال النسبي الذي تختاره. تظهر أهمية هذا في الشكل 11 أ . يُظهر الرسم البياني للوظائف فاصل زمني مهم حيث تكون قيمته $$$0$ . أخذ العينات في هذا المجال لا طائل منه: لا شيء يضاف إلى المجموع ، فنحن نقسم ببساطة على عدد أكبر. تذكر جبل الجليد من الشكل 1 ج : ليس من المنطقي أخذ عينات من الارتفاع في مساحة كبيرة حول جبل الجليد.


الشكل 11: pdf لوظيفة ذات قيم صفرية.

يظهر الشكل 11 ب ملف pdf الذي يستخدم هذه المعرفة للوظيفة. لاحظ أن هذا pdf هو في الواقع صفر بالنسبة لمجموعة القيم. هذا لا يحولها إلى ملف pdf غير صحيح: في بعض الأماكن ، تكون الدالة صفرية. يمكننا تمديد هذه الفكرة إلى ما وراء الصفر. من الأفضل إنفاق العينات على تلك الأماكن التي تحتوي فيها الوظيفة على قيم كبيرة. في الواقع ، فإن ملف pdf المثالي يتناسب مع وظيفة العينة . يتم عرض ملف pdf جيد جدًا لوظيفةنا في الشكل 12 أ . يظهر أفضل قوات الدفاع الشعبي في الشكل 12B . في كلتا الحالتين ، يجب ألا ننسى تطبيعه بحيث تكامل يساوي 1.


الشكل 12: تعزيز قوات الدفاع الشعبي لوظيفة في الشكل 11.

قوات الدفاع الشعبي في الشكل 12 تشكل مهمتين بالنسبة لنا:

1. كيفية إنشاء قوات الدفاع الشعبي من هذا القبيل ؛
2. كيفية أخذ عينات من قوات الدفاع الشعبي؟

الجواب على كلا السؤالين هو نفسه: نحن لسنا بحاجة للقيام بذلك. في العديد من الحالات ، تكون الوظيفة التي نريد دمجها غير معروفة ، والطريقة الوحيدة لتحديد الأماكن التي تكون فيها مهمة هي أخذ عينات منها ، ولهذا نحتاج إلى pdf ؛ الوضع الكلاسيكي "الدجاج والبيض".

ومع ذلك ، في حالات أخرى ، لدينا فكرة تقريبية عن حيث يمكن للوظيفة إعطاء قيم أعلى أو قيم صفرية. في مثل هذه الحالات ، غالبًا ما يكون ملف pdf التقريبي أفضل من عدم وجود pdf.

أيضا ، قد تكون لدينا الفرصة لإنشاء قوات الدفاع الشعبي على الطاير. تعطي بعض العينات فكرة عن شكل الوظيفة ، وعلى أساسها نوجه العينات التالية إلى تلك الأماكن التي نتوقع فيها قيمًا عالية ، والتي نستخدمها لتحسين pdf ، وما إلى ذلك.

في المقالة التالية ، سوف نطبق هذه المفاهيم على تنفيذ التقديم. التحدي الخطير هو بناء قوات الدفاع الشعبي. ندرس عدة حالات حيث تساعد ملفات pdf في أخذ العينات.