خوارزمية زيغورات (Ziggurat Algorithm)

مقدمة في أخذ العينات بالرفض

أخذ العينات بالرفض هو أسلوب عام يستخدم لتوليد عينات من توزيع احتمالي معين. الفكرة الأساسية هي اختيار عينة من توزيع آخر، يسمى “التوزيع المقترح”، ثم قبول أو رفض هذه العينة بناءً على قيم دالة الكثافة الاحتمالية (PDF) للتوزيع المستهدف. يتم تحديد احتمالية قبول العينة بناءً على نسبة دالة الكثافة الاحتمالية للتوزيع المستهدف إلى دالة الكثافة الاحتمالية للتوزيع المقترح. إذا كانت هذه النسبة كبيرة، فمن المرجح قبول العينة؛ وإذا كانت صغيرة، فمن المرجح رفضها.

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

آلية عمل خوارزمية زيغورات

تعتمد خوارزمية زيغورات على بناء تقريب للتوزيع المستهدف باستخدام سلسلة من المستطيلات والمناطق الخارجية. هذه العملية تتضمن الخطوات التالية:

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

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

التكرار: تكرر عملية أخذ العينات حتى يتم الحصول على العدد المطلوب من العينات.

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

المزايا والعيوب

المزايا:

الكفاءة: تعتبر خوارزمية زيغورات فعالة جدًا في توليد عينات من العديد من التوزيعات الاحتمالية.
السرعة: تتطلب الخوارزمية عددًا صغيرًا من العمليات الحسابية لكل عينة، مما يجعلها سريعة.
البساطة: الخوارزمية سهلة التنفيذ نسبيًا.

العيوب:

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

تطبيقات خوارزمية زيغورات

تستخدم خوارزمية زيغورات في مجموعة واسعة من التطبيقات، بما في ذلك:

المحاكاة الحاسوبية: تستخدم لتوليد متغيرات عشوائية من توزيعات مختلفة لمحاكاة الأنظمة المعقدة.
الإحصاء: تستخدم لأخذ عينات من توزيعات معقدة في التحليل الإحصائي.
الذكاء الاصطناعي: تستخدم في خوارزميات التعلم الآلي لتوليد عينات من توزيعات احتمالية معقدة.
الرسومات الحاسوبية: تستخدم في توليد الضوضاء العشوائية وفي محاكاة الإضاءة.
هندسة البرمجيات: تستخدم في اختبار البرامج وقياس الأداء.

بشكل عام، تعتبر خوارزمية زيغورات أداة قوية ومتعددة الاستخدامات لتوليد الأعداد شبه العشوائية والعينات من التوزيعات الاحتمالية المختلفة.

التحسينات والتعديلات

على مر السنين، تم تطوير العديد من التحسينات والتعديلات على خوارزمية زيغورات لتحسين كفاءتها ودقتها. وتشمل هذه التحسينات:

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

تساعد هذه التحسينات على جعل خوارزمية زيغورات أكثر مرونة وقدرة على التعامل مع مجموعة واسعة من المشاكل.

مقارنة مع خوارزميات أخذ العينات الأخرى

هناك العديد من الخوارزميات الأخرى المستخدمة لأخذ العينات من التوزيعات الاحتمالية، ولكل منها مزاياها وعيوبها. تشمل بعض الخوارزميات الشائعة الأخرى:

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

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

اعتبارات عملية عند تطبيق خوارزمية زيغورات

عند استخدام خوارزمية زيغورات، هناك بعض الاعتبارات العملية التي يجب أخذها في الاعتبار:

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

من خلال الاهتمام بهذه الاعتبارات، يمكن للمستخدمين الاستفادة القصوى من خوارزمية زيغورات.

أمثلة على الشيفرة البرمجية

فيما يلي مثال بسيط لكيفية تطبيق خوارزمية زيغورات بلغة بايثون لتوليد عينات من التوزيع الطبيعي القياسي:

import numpy as np

from scipy.stats import norm
def ziggurat(n=10000):

    # Constants for the standard normal distribution

    V = 991

    X = [0] * V

    Y = [0] * V

    W = [0] * V
    # Precompute constants

    X[0] = 0.0

    Y[0] = float('inf')

    W[0] = 0.0
    for i in range(1, V):

        x = np.sqrt(-2 * np.log(1.0 - float(i) / V))

        X[i] = x

        Y[i] = np.exp(-0.5 * x * x)

        W[i] = x * Y[i] + 1.0

    # Generate samples

    samples = []

    for _ in range(n):

        while True:

            # Sample from a uniform distribution

            u = np.random.rand()

            # Sample from an exponential distribution

            k = int(np.floor(u * V))

            # Generate a random point within the region

            x = np.random.rand()

            # Perform rejection sampling

            if k == 0:

                if x <= np.exp(-0.5 * X[V-1] * X[V-1]):

                    sample = np.random.choice([-1, 1]) * X[V-1]

                    break

            elif x * Y[k-1] <= Y[0]:

                sample = np.random.choice([-1, 1]) * X[k]

                break

            else:

                if (np.random.rand() <= Y[k] / Y[k-1]):

                    sample = np.random.choice([-1, 1]) * X[k]

                    break

                else:

                    continue
        samples.append(sample)

    return samples
# Generate and verify the samples

samples = ziggurat(10000)

print(f"Number of samples generated: {len(samples)}")

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

```