السَّمْت

التحسين1951تأسيسي8 دقيقة قراءة

أسلوب التقريب العشوائي

A Stochastic Approximation Method

Robbins, H. · Monro, S. — The Annals of Mathematical Statistics

المشكلة

لديك دالة M(x) تمثّل القيمة المتوقعة لنتيجة تجربة عند المستوى x، وتعلم أن لها جذرًا عند نقطة مجهولة θ حيث M(θ) = α. المشكلة أنك لا تستطيع قياس M(x) مباشرةً؛ كل تجربة تعيد قيمة مُشوَّشة Y = M(x) + خطأ عشوائي. الطرق الكلاسيكية — — تحتاج إلى قيم الدالة ومشتقاتها بدقة تامة. فكيف تجد θ وكل ما بيدك ملاحظات مُشوَّشة تُؤخَذ مرة واحدة فقط؟

الإسهام

خوارزمية تكرارية تعثر على θ بالاعتماد فقط على ملاحظات مُشوَّشة: في الخطوة n، ارصد Yₙ عند المستوى xₙ، ثم حدِّث القيمة وفق xₙ₊₁ = xₙ − aₙ(Yₙ − α). حجم الخطوة aₙ يجب أن يستوفي شرطين: Σaₙ = ∞ لضمان القدرة على الوصول إلى أي هدف، وΣaₙ² < ∞ لإخماد أثر الضجيج. تحت شروط رتابة بسيطة على M، تتقارب القيم xₙ نحو θ احتماليًّا. كانت هذه أول خوارزمية تقدّم منهجًا مبدئيًّا للأمثلة تحت الضجيج.

الأثر

هذه الورقة — سبع صفحات فقط — هي البذرة التي خرجت منها الأمثلة العشوائية الحديثة بأكملها. ، أي الخوارزمية التي تدرّب كل شبكة عصبية اليوم، سليلٌ مباشر لها: استبدل بتدرّج محسوب من دُفعة مصغّرة وستحصل على تحديث روبنز-مونرو بعينه. آدم وRMSProp وكل مُحسِّن تكيُّفي يرث منها منطق التحكم في حجم الخطوة. بدون هذه الورقة لا توجد طريقة عملية نماذج التعلم العميق على بيانات أكبر من أن تسعها الذاكرة.

تخيّل أنك معصوب العينين وسط حقل وَعِر، تحاول الوصول إلى قاع الوادي. لا ترى الميل، لكن معك بوصلة مُشوَّشة — تشير تقريبًا نحو الأسفل، لكن إبرتها تهتزّ عشوائيًّا كل مرة تنظر إليها.

الحتمي يقول: «اقرأ البوصلة وامشِ تمامًا حيث تشير.» لكن الاهتزاز يجعلك تتعرّج بلا نهاية.

روبنز ومونرو يقولان: «اقرأ البوصلة، لكن قصِّر خطواتك كلما تقدّمت.» في البداية تخطو بجرأة لتقترب سريعًا. ثم تتقلّص خطواتك حتى لا يستطيع الاهتزاز إبعادك. مع مرور الوقت تتلاشى الأخطاء العشوائية بالمتوسط، فتستقرّ في قاع الوادي — رغم أنك لم تَرَه بوضوح قطّ.

المشكلة: كيف تجد جذرًا لا تراه؟

لنأخذ مثالًا عمليًّا: تُجري تجربة طبية، وعند كل جرعة xx تكون القيمة المتوقعة لاستجابة المريض هي M(x)M(x). هدفك إيجاد الجرعة θ\theta التي يتحقّق عندها M(θ)=αM(\theta) = \alpha — مثلًا الجرعة التي يستجيب عندها 50% من المرضى. لكن أمامك عقبتان أساسيتان:

لا يمكنك رؤية M(x)M(x) مباشرةً. كل مريض يعطيك نتيجة واحدة مُشوَّشة YY، وليس المتوسط الحقيقي. مريضان يتلقّيان الجرعة ذاتها قد يستجيبان بشكل مختلف تمامًا.

لديك فرصة واحدة لكل مستوى. الأساليب الكلاسيكية كالتنصيف تفترض أنك تستطيع حساب قيمة الدالة بدقة. في وجود الضجيج، ملاحظة مُشوَّشة واحدة عند xx لا تخبرك بالكثير عن M(x)M(x).

طريقة نيوتن تحتاج إلى المشتقة M′(x)M'(x)، وتقديرها من بيانات مُشوَّشة أصعب بكثير. قبل عام 1951 لم يكن هناك حلٌّ منهجي لهذه المشكلة.

افتح في المختبر
الخط الأخضر هو الدالة المخفية M(x). أنت لا ترى سوى النقاط الحمراء المُشوَّشة. راقب كيف يتقارب التكرار الأخضر نحو θ رغم الضجيج.
تستيقظ التجربة عند وصولك…

الفكرة: قلِّص خطواتك ودَع الضجيج يتلاشى

اقترح روبنز ومونرو إجراءً بسيطًا وأنيقًا. ابدأ بتخمين أوّلي x1x_1، ثم في كل خطوة nn:

  1. أَجرِ تجربة واحدة عند المستوى xnx_n وارصد الناتج المُشوَّش YnY_n.
  2. احسب : كم يبتعد YnY_n عن القيمة المستهدفة α\alpha؟
  3. تحرّك في الاتجاه المعاكس بمقدار يتناسب مع هذا الخطأ، لكن مضروبًا في متقلِّص ana_n.

بكاملها:

xn+1=xn−an(Yn−α)x_{n+1} = x_n - a_n \left( Y_n - \alpha \right)
تحديث روبنز-مونرو — سَلَف الانحدار التدريجي العشوائي — xₙ = التخمين الحالي · Yₙ = الملاحظة المُشوَّشة عند xₙ · α = القيمة المستهدفة · aₙ = حجم الخُطوة الذي يتقلّص مع n · التحديث يتحرك في المتوسط نحو θ
افتح في المختبر
اضغط «التالية» للمرور بخطوات تكرار واحد من الخوارزمية.
تستيقظ التجربة عند وصولك…

فكِّر في الخوارزمية وكأنها حلقة تغذية راجعة — مثل ضبط مقود سيارة على طريق ضبابي: لا ترى الطريق بوضوح بسبب الضجيج، لكن كل تصحيح صغير يُبقيك قريبًا من المسار. الملاحظة الجوهرية هنا أن هذه التصحيحات يجب أن تتقلّص مع الوقت: تصحيحات كبيرة في البداية لتقترب بسرعة، ثم تصحيحات دقيقة لاحقًا لتستقرّ بدقة.

شروط حجم الخُطوة: المحرِّك الذي يضمن التقارب

النظرية بأكملها تقوم على شرطين يحكمان أحجام الخطوات ana_n. هذان أشهر شرطين في العشوائية، وكل مُحسِّن استخدمته في حياتك يرثهما. قبل أن نعرض الصيغ الرياضية، لنفهم ما الذي يمنعه كل شرط:

الشرط الأول يمنع التوقف المبكر. إذا تقلّصت الخطوات بسرعة مفرطة (مثلًا an=1/n2a_n = 1/n^2)، فإن مجموعها الكلي ∑an\sum a_n يتقارب — بمعنى أن الخوارزمية لا تستطيع أن تقطع سوى مسافة محدودة من نقطة البداية. فإن كانت θ\theta أبعد من ذلك، فلن تصلها أبدًا. لذلك نحتاج أن تكون ميزانية المسافة الكلية لانهائية.

الشرط الثاني يمنع التجوال الأبدي. إذا لم تتقلّص الخطوات أصلًا (مثلًا an=ca_n = c ثابت)، فالضجيج يظلّ يدفع التكرارات في كل اتجاه — تتأرجح لكنها لا تستقرّ أبدًا. نحتاج أن تكون القدرة التراكمية للضجيج ∑an2\sum a_n^2 محدودة حتى يخمد أثره.

∑n=1∞an=∞and∑n=1∞an2<∞\sum_{n=1}^{\infty} a_n = \infty \quad \text{and} \quad \sum_{n=1}^{\infty} a_n^2 < \infty
شروط حجم الخُطوة لروبنز-مونرو — الشرط الأول: مدى لانهائي — القدرة على قطع أي مسافة · الشرط الثاني: قدرة ضجيج محدودة — الضجيج يخمد في النهاية
افتح في المختبر
قارن بين ثلاثة جداول. الجدول 1/n وحده يستوفي الشرطين معًا.
تستيقظ التجربة عند وصولك…

مبرهنة التقارب

أثبت روبنز ومونرو أنه بتوفّر الشروط التالية على M(x)M(x)، فإن التكرارات xnx_n تتقارب نحو θ\theta بمفهوم :

  • الرتابة: M(x)M(x) غير متناقصة. هذا يضمن أن إشارة الخطأ Yn−αY_n - \alpha تحمل الإشارة الصحيحة في المتوسط، فتوجّه الخوارزمية نحو θ\theta.
  • وجود الجذر: يوجد θ\theta وحيد بحيث M(θ)=αM(\theta) = \alpha.
  • تباين محدود: الضجيج Y−M(x)Y - M(x) له محدود، Var(Y)≤C\text{Var}(Y) \leq C لكل xx. هذا يمنع أي ملاحظة منفردة من أن تكون مُضلِّلة بشكل كارثي.
  • شروط حجم الخُطوة: ∑an=∞\sum a_n = \infty و ∑an2<∞\sum a_n^2 < \infty. بتوفّر هذه الشروط، لأي ε>0\varepsilon > 0 ينطبق: P(∣xn−θ∣>ε)→0P(|x_n - \theta| > \varepsilon) \to 0 عندما n→∞n \to \infty. أي أن التكرارات تتقارب نحو الجذر الحقيقي احتماليًّا — ليس بيقين مطلق في كل تشغيل، لكن احتمال الابتعاد يتلاشى مع ازدياد عدد الخطوات.
افتح في المختبر
خمسة تشغيلات مستقلة من نقاط بداية مختلفة — جميع المسارات تتقارب نحو θ.
تستيقظ التجربة عند وصولك…

الخوارزمية في سطور برمجية

التقريب العشوائي لروبنز-مونرو، كاملًاpython

مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.

import numpy as np

def robbins_monro(M_noisy, alpha, x0, n_steps=100):
    """
    أوجد θ حيث E[M(θ)] = α باستخدام ملاحظات مُشوَّشة فقط.

    M_noisy(x) : دالة — تعيد عيّنة مُشوَّشة Y عند المستوى x
    alpha      : القيمة المستهدفة
    x0         : التخمين الأولي
    """
    x = x0
    history = [x]

    for n in range(1, n_steps + 1):
        a_n = 1.0 / n          # حجم الخُطوة: Σ(1/n) = ∞, Σ(1/n²) < ∞
        Y_n = M_noisy(x)       # ملاحظة مُشوَّشة واحدة
        x = x - a_n * (Y_n - alpha)   # التحديث
        history.append(x)

    return x, history

# مثال: M(x) = 2x − 6، الجَذر عند θ = 3
def experiment(x):
    return 2*x - 6 + np.random.randn() * 1.5   # M الحقيقية + ضجيج

theta_hat, path = robbins_monro(experiment, alpha=0, x0=0.5)
print(f"التقدير: {theta_hat:.3f}")   # ≈ 3.0

من إيجاد الجذور إلى تدريب الشبكات العصبية

العلاقة بين هذه الورقة و الحديث علاقة مباشرة وعميقة. عند تدريب ، نريد تصغير L(θ)=E[ℓ(θ;ξ)]\mathcal{L}(\theta) = \mathbb{E}[\ell(\theta; \xi)] بالنسبة لـ النموذج θ\theta. النهاية الصغرى تحدث عندما يكون مساويًا للصفر: ∇L(θ∗)=0\nabla \mathcal{L}(\theta^*) = 0. هذه في جوهرها مسألة إيجاد جذور.

لا نستطيع حساب التدرّج الحقيقي ∇L\nabla \mathcal{L} لأن ذلك يتطلّب حساب المتوسط على مجموعة البيانات كاملةً، وهذا مكلف جدًّا. بدلًا من ذلك، نقدّره من عشوائية، فنحصل على تدرّج مُشوَّش ∇ℓ(θ;ξt)\nabla \ell(\theta; \xi_t). وهذه هي بالضبط الملاحظة المُشوَّشة في إطار روبنز-مونرو.

الانحدار التدريجي العشوائي ليس سوى أسلوب روبنز-مونرو مطبَّقًا على إيجاد جذور التدرّجات. شروط عام 1951 — ∑an=∞\sum a_n = \infty و∑an2<∞\sum a_n^2 < \infty — هي المبرّر النظري لـ التي يستخدمها كل ممارسٍ اليوم، حتى وإن لم يسمع باسمَي روبنز ومونرو.

افتح في المختبر
بدِّل بين المنظورين — قاعدة التحديث متطابقة.
تستيقظ التجربة عند وصولك…

لماذا كانت هذه الورقة مفصليّة؟

  1. 1951

    روبنز-مونرو

    أسلوب التقريب العشوائي — إيجاد الجذور في وجود الضجيج عبر أحجام خطوات متقلِّصة.

  2. 1952

    كيفر-وولفوفيتز

    وسّع التقريب العشوائي ليشمل الأمثلة باستخدام الفروق المحدودة، دون الحاجة إلى تدرّجات تحليلية.

  3. 1958

    التوزيع المقارب الطبيعي لساكس

    أثبت أن √n(xₙ − θ) يتقارب نحو توزيع طبيعي، ما يتيح بناء فترات ثقة للتقدير.

  4. 1951

    ولادة الانحدار التدريجي العشوائي

    تطبيق تحديث روبنز-مونرو على إيجاد جذور التدرّج أنتج الانحدار التدريجي العشوائي، وإن جاء الاسم لاحقًا.

  5. 2015

    مُحسِّن آدم

    آدم يُضيف معدّلات تعلّم تكيُّفية لكل معامل على حدة، مع زَخَم، ضمن إطار روبنز-مونرو — وهو أكثر المُحسِّنات انتشارًا في التعلم العميق.

  6. 2024

    مُحسِّنات عصر التوسّع

    تدريب النماذج الضخمة ذات التريليون معامل يعتمد على جداول أحجام خطوات مضبوطة بعناية — وكلها أحفاد شروط 1951.

المرجعRobbins, H. and Monro, S.. A Stochastic Approximation Method. The Annals of Mathematical Statistics, 1951.

مصطلحات هذه الورقة