الخوارزمية تحاكي سرعة لفة النرد المحملة

محاكاة لفة النرد المحملة

معلومة تهمك

الخوارزمية تحاكي سرعة لفة النرد المحملة
كتب :ايهاب محمد زايد-مصر
قد يساعد نهج توليد الأرقام بشكل عشوائي في تحليل الأنظمة المعقدة ، من مناخ الأرض إلى الأسواق المالية.
لطالما كان التوليد السريع والفعال للأرقام العشوائية تحديًا مهمًا. لقرون ، اعتمدت ألعاب الحظ على رمي النرد ، أو قلب العملة ، أو خلط الأوراق لإضفاء بعض العشوائية على الإجراءات.
في النصف الثاني من القرن العشرين ، بدأت أجهزة الكمبيوتر في تولي هذا الدور ، للتطبيقات في التشفير والإحصاء والذكاء الاصطناعي ، وكذلك لعمليات المحاكاة المختلفة – المناخية والوبائية والمالية وما إلى ذلك.
طور باحثو معهد ماساتشوستس للتكنولوجيا الآن خوارزمية حاسوبية قد تنتج ، على الأقل لبعض المهام ، أرقامًا عشوائية مع أفضل مزيج من متطلبات السرعة والدقة والذاكرة المنخفضة المتاحة اليوم.
تم إنشاء الخوارزمية ، التي تسمى Fast Loaded Dice Roller (FLDR) ، من قبل طالب الدراسات العليا بمعهد ماساتشوستس للتكنولوجيا فراس سعد ، وعالم الأبحاث كاميرون فرير ، والبروفيسور مارتن رينارد ، وعالم الأبحاث الرئيسي فيكاش مانسينغكا ، وسيتم تقديمها الأسبوع المقبل في المؤتمر الدولي الثالث والعشرين في الذكاء الاصطناعي والإحصاء.
ببساطة ، FLDR هو برنامج كمبيوتر يحاكي لفة النرد لإنتاج أعداد صحيحة عشوائية. يمكن أن يكون للنرد أي عدد من الجوانب ، ويتم “تحميلها” أو ثقلها لجعل بعض الجوانب أكثر احتمالًا من غيرها.
لا يزال بإمكان القوالب المحملة إنتاج أرقام عشوائية – حيث لا يمكن التنبؤ مسبقًا بالجانب الذي سيظهر – ولكن العشوائية مقيدة لتلبية توزيع احتمالي محدد مسبقًا. يمكن للمرء ، على سبيل المثال ، استخدام النرد المحشو لمحاكاة نتيجة لعبة البيسبول ؛ بينما من المرجح أن يفوز الفريق المتفوق ، في يوم معين ، يمكن أن ينتهي الأمر بأي من الفريقين في المقدمة.
مع FLDR ، يتم تحميل النرد “بشكل مثالي” ، مما يعني أنها تحقق بالضبط الاحتمالات المحددة. في حالة النرد بأربعة جوانب ، على سبيل المثال ، يمكن للمرء أن يرتب الأشياء بحيث تظهر الأرقام 1،2،3 و 4 بالضبط 23 بالمائة و 34 بالمائة و 17 بالمائة و 26 بالمائة من الوقت على التوالي.
لمحاكاة لفة النرد المحملة التي تحتوي على عدد كبير من الجوانب ، كان على فريق معهد ماساتشوستس للتكنولوجيا أولاً الاعتماد على مصدر أبسط للعشوائية – وهو إصدار محوسب (ثنائي) من رمي العملة ، ينتج إما 0 أو 1 ، لكل منها احتمال 50 بالمائة. تعتمد كفاءة طريقتهم ، وهي معيار تصميم رئيسي ، على عدد المرات التي يتعين عليهم فيها الاستفادة من هذا المصدر العشوائي – عدد “رميات العملة” ، بمعنى آخر – لمحاكاة كل لفة نرد.
في ورقة بحثية تاريخية عام 1976 ، ابتكر عالما الكمبيوتر دونالد كنوث وأندرو ياو خوارزمية يمكنها محاكاة لفة النرد المحملة بأقصى قدر ممكن من الكفاءة نظريًا. يوضح سعد: “بينما كانت الخوارزميات الخاصة بهم فعالة على النحو الأمثل فيما يتعلق بالوقت” ، مما يعني أنه حرفياً لا يمكن أن يكون أي شيء أسرع ، “فهي غير فعالة من حيث المساحة ، أو ذاكرة الكمبيوتر ، اللازمة لتخزين تلك المعلومات”.
في الواقع ، يزداد حجم الذاكرة المطلوبة بشكل كبير ، اعتمادًا على عدد الجوانب على النرد وعوامل أخرى. وهذا يجعل طريقة Knuth-Yao غير عملية ، كما يقول ، باستثناء الحالات الخاصة ، على الرغم من أهميتها النظرية.
تم تصميم FLDR لتحقيق فائدة أكبر. يقول سعد: “نحن موفرون للوقت تقريبًا ، لكن ترتيب الحجم أفضل من حيث كفاءة الذاكرة”. يمكن أن يستخدم FLDR مساحة تخزين ذاكرة أقل بما يصل إلى 10000 مرة من نهج Knuth-Yao ، بينما لا يستغرق أكثر من 1.5 مرة لكل عملية.
في الوقت الحالي ، المنافس الرئيسي لـ FLDR هو طريقة Alias ​​، والتي كانت التكنولوجيا المهيمنة في المجال لعقود. عند تحليله نظريًا ، وفقًا لـ Freer ، يتمتع FLDR بميزة واضحة واحدة على الاسم المستعار: فهو يجعل الاستخدام الأكثر كفاءة للمصدر العشوائي – “رميات العملة” ، للاستمرار في هذا الاستعارة – من الاسم المستعار. علاوة على ذلك ، في بعض الحالات ، يكون FLDR أيضًا أسرع من الاسم المستعار في توليد لفات النرد المحملة.
لا يزال FLDR ، بالطبع ، جديدًا تمامًا ولم يشهد استخدامه على نطاق واسع بعد. لكن مطوريها يفكرون بالفعل في طرق لتحسين فعاليتها من خلال هندسة البرمجيات والأجهزة. لديهم أيضًا تطبيقات محددة في الاعتبار ، بصرف النظر عن الحاجة العامة الدائمة للأرقام العشوائية.
يقترح مانسينجكا أن أكثر المجالات التي يمكن أن يساعد فيها FLDR هو جعل ما يسمى بمحاكاة مونت كارلو وتقنيات استدلال مونت كارلو أكثر كفاءة. تمامًا كما يستخدم FLDR تقليب العملات لمحاكاة لفة أكثر تعقيدًا من الزهر الموزون متعدد الجوانب ، تستخدم محاكاة مونت كارلو لفة النرد لإنشاء أنماط أكثر تعقيدًا من الأرقام العشوائية.
تدير الأمم المتحدة ، على سبيل المثال ، عمليات محاكاة للنشاط الزلزالي تُظهر متى وأين تحدث الزلازل أو الهزات الأرضية أو التجارب النووية في العالم. تنفذ الأمم المتحدة أيضًا استنتاج مونت كارلو: إجراء عمليات محاكاة عشوائية تولد تفسيرات محتملة للبيانات الزلزالية الفعلية.
يعمل هذا عن طريق إجراء سلسلة ثانية من محاكاة مونت كارلو ، والتي تختبر بشكل عشوائي المعلمات البديلة لمحاكاة زلزالية أساسية للعثور على قيم المعلمات التي من المرجح أن تعيد إنتاج البيانات المرصودة. تحتوي هذه المعلمات على معلومات حول متى وأين قد تكون الزلازل والتجارب النووية قد حدثت بالفعل.
يقول مانسينجكا: “يمكن أن يتطلب استدلال مونت كارلو أعدادًا عشوائية تزيد بمئات الآلاف من المرات عن محاكاة مونت كارلو”. “هذا هو عنق الزجاجة الكبير حيث يمكن أن يساعد FLDR حقًا. تعد خوارزميات المحاكاة والاستدلال في مونت كارلو أيضًا مركزية للبرمجة الاحتمالية ، وهي منطقة ناشئة من الذكاء الاصطناعي مع تطبيقات واسعة. ”
يرى رايان ريفكين ، مدير الأبحاث في Google ، إمكانات كبيرة لـ FLDR في هذا الصدد. يقول ريفكين ، الذي لم يشارك في الدراسة: “تعد خوارزميات الاستدلال في مونت كارلو مركزية في هندسة الذكاء الاصطناعي الحديثة … والنمذجة الإحصائية واسعة النطاق”. ال “FLDR هو تطور واعد للغاية قد يؤدي إلى طرق لتسريع اللبنات الأساسية لتوليد الأرقام العشوائية ، وقد يساعد Google في جعل استنتاج مونت كارلو أسرع وأكثر كفاءة في استخدام الطاقة.”
على الرغم من مستقبله المشرق على ما يبدو ، لم يظهر FLDR تقريبًا إلى النور. ظهرت تلميحات منه لأول مرة من ورقة سابقة نشرها نفس الباحثين الأربعة في معهد ماساتشوستس للتكنولوجيا في ندوة في يناير ، والتي قدمت خوارزمية منفصلة. في هذا العمل ، أظهر المؤلفون أنه إذا تم تخصيص قدر محدد مسبقًا من الذاكرة لبرنامج كمبيوتر لمحاكاة لفة النرد المحملة ، يمكن أن تحدد الخوارزمية الخاصة بهم الحد الأدنى من “الخطأ” الممكن – أي مدى قرب المرء من الاجتماع الاحتمالات المحددة لكل جانب من جوانب النرد.
إذا لم يقيد المرء الذاكرة مسبقًا ، فيمكن تقليل الخطأ إلى الصفر ، لكن سعد لاحظ متغيرًا به خطأ صفري يستخدم ذاكرة أقل بشكل كبير وكان بنفس السرعة تقريبًا. في البداية اعتقد أن النتيجة قد تكون تافهة للغاية بحيث لا يمكن تحملها.
لكنه ذكر ذلك لفرير الذي أكد لسعد أن هذا الطريق يستحق المتابعة. نشأت FLDR ، الخالية من الأخطاء في هذا الصدد ، من تلك الأصول المتواضعة ولديها الآن فرصة لتصبح تقنية رائدة في مجال توليد الأرقام العشوائية. هذه ليست مسألة تافهة بالنظر إلى أننا نعيش في عالم تحكمه ، إلى حد كبير ، عمليات عشوائية – وهو مبدأ ينطبق على توزيع المجرات في الكون ، وكذلك على نتائج لعبة كرابس المفعمة بالحيوية.
المصدر
https://news.mit.edu

تنبيه هام، المنشور يعبر عن رأي الكاتب ويتحمل مسؤوليته، دون ادنى مسؤولية علي الجريدة

تنبيه

احصل على تحديثات في الوقت الفعلي مباشرة على جهازك ، اشترك الآن.

معلومة تهمك

اترك رد

لن يتم نشر عنوان بريدك الإلكتروني.

%d مدونون معجبون بهذه: