خوارزمية الأغلبية المرجحة العشوائية

خوارزمية الأغلبية المرجحة العشوائية هي خوارزمية في نظرية التعلم الآلي تُستخدم لتجميع تنبؤات الخبراء لسلسلة من مسائل اتخاذ القرار. ^{[ 1 ]} وهي طريقة بسيطة وفعالة تعتمد على التصويت المرجح، وتُحسّن من هامش الخطأ لخوارزمية الأغلبية المرجحة الحتمية . في الواقع، في النهاية، يمكن أن يكون معدل تنبؤها قريبًا جدًا من معدل تنبؤ أفضل خبير.

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

في مجال تعلم الآلة ، تُعد خوارزمية الأغلبية المرجحة (WMA) خوارزمية حتمية للتعلم الفائق تُستخدم لتجميع تنبؤات الخبراء. ويمكن كتابة خوارزمية الأغلبية المرجحة (WMA) بلغة شبه برمجية كما يلي:

قم بتهيئة جميع الخبراء بوزن 1 لكل جولة: أضف وزن كل خبير إلى الخيار الذي توقعه. توقع الخيار الذي يحقق أكبر مجموع مرجح اضرب أوزان جميع الخبراء الذين تنبأوا بشكل خاطئ في${\displaystyle {\frac {1}{2}}}$

لنفترض أن هناك${\displaystyle n}$الخبراء وأفضل الخبراء يصنعون${\displaystyle m}$أخطاء. عندئذٍ، ترتكب خوارزمية الأغلبية المرجحة (WMA) على الأكثر${\displaystyle 2.4(\log _{2}n+m)}$الأخطاء. يُعد هذا الحد إشكاليًا للغاية في حالة الخبراء المعرضين للخطأ بشكل كبير. لنفترض، على سبيل المثال، أن أفضل خبير يرتكب خطأً بنسبة 20% من الوقت؛ أي في${\displaystyle N=100}$الجولات باستخدام${\displaystyle n=10}$الخبراء، أفضل الخبراء يصنعون${\displaystyle m=20}$الأخطاء. عندئذٍ، لا تضمن خوارزمية الأغلبية المرجحة سوى حد أعلى لـ${\displaystyle 2.4(\log _{2}10+20)\approx 56}$أخطاء.

بما أن هذا قيد معروف لخوارزمية الأغلبية المرجحة، فقد تم استكشاف استراتيجيات مختلفة لتحسين الاعتماد على${\displaystyle m}$وعلى وجه الخصوص، يمكننا أن نحقق نتائج أفضل من خلال إدخال العشوائية.

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

تُعد خوارزمية الأغلبية المرجحة العشوائية محاولة لتحسين اعتماد حد الخطأ لخوارزمية الأغلبية المرجحة على${\displaystyle m}$بدلاً من التنبؤ بناءً على تصويت الأغلبية، يتم استخدام الأوزان كاحتمالات لاختيار الخبراء في كل جولة ويتم تحديثها بمرور الوقت (ومن هنا جاء اسم الأغلبية المرجحة العشوائية).

بالضبط، إذا${\displaystyle w_{i}}$وزن الخبير${\displaystyle i}$، يترك${\displaystyle W=\sum _{i}w_{i}}$سنتبع نصائح الخبراء${\displaystyle i}$باحتمال${\displaystyle {\frac {w_{i}}{W}}}$ينتج عن ذلك الخوارزمية التالية:

قم بتهيئة جميع الخبراء بوزن 1. لكل جولة: اجمع أوزان جميع الخبراء معًا للحصول على الوزن الإجمالي${\displaystyle W}$ اختر خبيرًا${\displaystyle i}$عشوائياً باحتمالية${\displaystyle {\frac {w_{i}}{W}}}$ توقع كما يتوقع الخبير المختار اضرب أوزان جميع الخبراء الذين تنبأوا بشكل خاطئ في${\displaystyle \beta }$

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

تُعدّ الخوارزمية العشوائية أفضل في أسوأ الحالات من الخوارزمية الحتمية ( خوارزمية الأغلبية المرجحة ): ففي الأخيرة، كانت أسوأ الحالات عندما تم تقسيم الأوزان بالتساوي (50/50). أما في النسخة العشوائية، وبما أن الأوزان تُستخدم كاحتمالات، فستظل هناك فرصة متساوية (50/50) للوصول إلى النتيجة الصحيحة. إضافةً إلى ذلك، يمكن تعميم ذلك بضرب أوزان الخبراء غير الصحيحين في${\displaystyle \beta <1}$بدلاً من بشكل صارم${\displaystyle {\frac {1}{2}}}$يسمح لنا ذلك بالموازنة بين الاعتماد على${\displaystyle m}$و${\displaystyle \log _{2}n}$سيتم تحديد هذه المقايضة كمياً في قسم التحليل.

يترك${\displaystyle W_{t}}$يشير إلى الوزن الإجمالي لجميع الخبراء في الجولة${\displaystyle t}$دع أيضًا${\displaystyle F_{t}}$يشير إلى نسبة الوزن الممنوح للخبراء الذين يتوقعون الإجابة الخاطئة في الجولة${\displaystyle t}$وأخيرًا، دع${\displaystyle N}$ليكن العدد الإجمالي للجولات في العملية.

بحسب التعريف،${\displaystyle F_{t}}$هل احتمال أن ترتكب الخوارزمية خطأً في الجولة${\displaystyle t}$ويترتب على خطية التوقع أنه إذا${\displaystyle M}$يشير إلى إجمالي عدد الأخطاء التي ارتكبت خلال العملية بأكملها،${\displaystyle E[M]=\sum _{t=1}^{N}F_{t}}$.

بعد الجولة${\displaystyle t}$، ينخفض ​​الوزن الإجمالي بمقدار${\displaystyle \ (1-\beta )F_{t}W_{t}}$، حيث يتم ضرب جميع الأوزان المقابلة للإجابة الخاطئة بـ${\displaystyle \ \beta <1}$ويترتب على ذلك أن${\displaystyle W_{t+1}=W_{t}(1-(1-\beta )F_{t})}$عن طريق التلسكوب، منذ${\displaystyle W_{1}=n}$وبناءً على ذلك، فإن الوزن الإجمالي بعد انتهاء العملية هو

${\displaystyle {\begin{aligned}W=n\prod _{t=1}^{N}(1-(1-\beta )F_{t}).\end{aligned}}}$

من ناحية أخرى، لنفترض أن${\displaystyle \ m}$يمثل عدد الأخطاء التي يرتكبها الخبير الأفضل أداءً. وفي النهاية، يكون لهذا الخبير وزنٌ كبير.${\displaystyle \ \beta ^{m}}$وبناءً على ذلك، فإن الوزن الإجمالي لا يقل عن هذا القدر؛ بعبارة أخرى،${\displaystyle \W\geq \beta ^{m}}$تشير هذه المتباينة والنتيجة المذكورة أعلاه إلى

${\displaystyle {\begin{aligned}n\prod _{t=1}^{N}(1-(1-\beta )F_{t})\geq \beta ^{m}.\end{aligned}}}$

بأخذ اللوغاريتم الطبيعي لكلا الطرفين نحصل على

${\displaystyle {\begin{aligned}\ln n+\sum _{t=1}^{N}\ln(1-(1-\beta )F_{t})\geq m\ln \beta .\end{aligned}}}$

أما متسلسلة تايلور للوغاريتم الطبيعي فهي

${\displaystyle {\begin{aligned}\ln(1-x)=-x-{\frac {x^{2}}{2}}-{\frac {x^{3}}{3}}-\cdots \end{aligned}}}$

وبناءً على ذلك، فإن${\displaystyle \ \ln(1-(1-\beta )F_{t})<-(1-\beta )F_{t}}$. هكذا،

${\displaystyle {\begin{aligned}\ln n-(1-\beta )\sum _{t=1}^{N}F_{t}\geq m\ln \beta .\end{aligned}}}$

مع التذكير بأن${\displaystyle E[M]=\sum _{t=1}^{N}F_{t}}$وبإعادة الترتيب، يترتب على ذلك أن

${\displaystyle {\begin{aligned}E[M]\leq {\frac {m\ln(1/\beta )+\ln(n)}{1-\beta }}={\frac {\ln(1/\beta )}{1-\beta }}m+{\frac {1}{1-\beta }}\ln(n).\end{aligned}}}$

الآن، كما${\displaystyle \beta \to 1}$من الأسفل، يميل الثابت الأول إلى${\displaystyle 1}$ومع ذلك، يميل الثابت الثاني إلى${\displaystyle +\infty }$ولتحديد هذه المفاضلة كمياً، حدد${\displaystyle \varepsilon =1-\beta }$لتكون العقوبة المرتبطة بالتنبؤ الخاطئ. ثم، بتطبيق متسلسلة تايلور للوغاريتم الطبيعي مرة أخرى،

${\displaystyle {\begin{aligned}{\frac {\ln(1/\beta )}{1-\beta }}=-{\frac {\ln(\beta )}{1-\beta }}={\frac {-\ln(1-\varepsilon )}{\varepsilon }}={\frac {\varepsilon +{\frac {\varepsilon ^{2}}{2}}+{\frac {\varepsilon ^{3}}{3}}+\cdots }{\varepsilon }}=1+{\frac {\varepsilon }{2}}+O(\varepsilon ^{2})\end{aligned}}}$

ويترتب على ذلك أن حد الخطأ، بالنسبة للصغيرة${\displaystyle \varepsilon }$، ويمكن كتابتها بالشكل${\displaystyle \ \left(1+{\frac {\epsilon }{2}}+O(\varepsilon ^{2})\right)m+\epsilon ^{-1}\ln(n)}$.

في اللغة الإنجليزية، كلما قلّت عقوبة الخبراء على أخطائهم، زادت احتمالية حدوث أخطاء أولية نتيجةً لوجود خبراء إضافيين، ولكننا مع مرور الوقت نقترب أكثر من محاكاة دقة التنبؤ لأفضل خبير. وبالتحديد، إذا كانت قيمة منخفضة بما فيه الكفاية لـ${\displaystyle \varepsilon }$وبعد عدد كافٍ من الجولات، يمكن لخوارزمية الأغلبية المرجحة العشوائية أن تقترب بشكل تعسفي من معدل التنبؤ الصحيح لأفضل خبير.

وعلى وجه الخصوص، طالما${\displaystyle m}$كبيرة بما يكفي مقارنة بـ${\displaystyle \ln(n)}$(بحيث تكون نسبتهم صغيرة بما فيه الكفاية)، يمكننا أن نخصص

${\displaystyle {\begin{aligned}\varepsilon ={\sqrt {\frac {\ln(n)}{m}}}\end{aligned}}}$

يمكننا الحصول على حد أعلى لعدد الأخطاء يساوي

${\displaystyle {\begin{aligned}m+O({\sqrt {m\ln(n)}}).\end{aligned}}}$

وهذا يعني أن "حد الندم" على الخوارزمية (أي مدى سوء أدائها مقارنة بأفضل خبير) هو دون الخطي، عند${\displaystyle O({\sqrt {m\ln(n)}})}$.

تذكر أن الدافع وراء خوارزمية الأغلبية المرجحة العشوائية كان مثالًا حيث يرتكب أفضل خبير خطأً بنسبة 20% من الوقت. تحديدًا، في${\displaystyle N=100}$جولات، مع${\displaystyle n=10}$الخبراء، حيث يصنع أفضل الخبراء${\displaystyle m=20}$في حالة الأخطاء، تضمن خوارزمية الأغلبية المرجحة الحتمية حدًا أعلى فقط لـ${\displaystyle 2.4(\log _{2}10+20)\approx 56}$بناءً على التحليل أعلاه، يتبين أن تقليل عدد الأخطاء المتوقعة في أسوأ الحالات يعادل تقليل الدالة

${\displaystyle {\begin{aligned}{\frac {\ln(1/\beta )}{1-\beta }}20+{\frac {1}{1-\beta }}\ln(10).\end{aligned}}}$

تُظهر الطرق الحسابية أن القيمة المثلى تقريبًا${\displaystyle \beta \approx 0.641}$مما ينتج عنه الحد الأدنى لعدد الأخطاء المتوقعة في أسوأ الحالات لـ${\displaystyle E[M]\approx 31.19}$عندما يزداد عدد الجولات (مثلاً إلى${\displaystyle N=1000000}$بينما يظل معدل دقة أفضل خبير ثابتًا، يمكن أن يكون التحسن أكثر دراماتيكية؛ إذ تضمن خوارزمية الأغلبية المرجحة معدل خطأ في أسوأ الحالات يبلغ 48.0% فقط، ولكن خوارزمية الأغلبية المرجحة العشوائية، عند ضبطها بشكل صحيح على القيمة المثلى لـ${\displaystyle \varepsilon \approx 0.0117}$، يحقق معدل خطأ في أسوأ الحالات بنسبة 20.2%.

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

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

• مشكلة اللص متعدد الأذرع .
• خوارزمية فعالة لبعض الحالات التي تضم العديد من الخبراء.
• إعداد خبراء النوم / "المتخصصين".

• التعلم الآلي
• خوارزمية الأغلبية المرجحة
• نظرية الألعاب
• لص متعدد الأذرع

• الأغلبية المرجحة والأغلبية المرجحة العشوائية
• نظرية التعلم الآلي لأفريم بلوم (2004)
• روب شابير، 2006، أسس التعلم الآلي
• التنبؤ بناءً على نصائح الخبراء
• أوري فيج، روبي كروثجامير، موني ناعور. نظرية اللعبة الخوارزمية
• نيكا هاغتالاب 2020 الأسس النظرية للتعلم الآلي (ملاحظات)