التطوّر كاستراتيجية بحث | ML-101

لما ميبقاش فيه gradient نمشي وراه

كل طريقة في الكورس ده لحد دلوقتي سألت الـ objective function نفس السؤال: أنهي اتجاه بينزّلنا؟ الـ gradient descent (النزول التدرجي) في الوحدة 2 بيجاوب على السؤال ده بالمشتقة. والـ backpropagation (الانتشار العكسي) في الوحدة 6 بيجاوب بإنه يزقّ المشتقة دي على layers متراصّة. والطريقتين فعّالين لدرجة مذهلة، والاتنين معتمدين على حاجة واحدة تكون صح — إن الكمية اللي عايز تحسّنها تبقى function ناعمة في الأرقام المسموح لك تغيّرها.

أهداف حقيقية كتير مش كده. فيه أربع أنواع بتظهر على طول:

اختيارات منفصلة. أنهي features من الأربعين المرشّحين المفروض الـ model يشوفها؟ مفيش مشتقة لـ «أحط الـ feature رقم 7 ولا لأ» — ده مفتاح أيوه أو لأ، مش مقبض بيتدرّج. بنية combinatorial (توافقية). فريق الصيانة المفروض يزور 20 موقع خدمة موبايل بأنهي ترتيب؟ الإجابة ترتيب لعناصر، وإنك تزقّ ترتيب بمقدار صغير لا نهائي كلام مالوش معنى. أهداف مبنية على المحاكاة. لو الدرجة طالعة من simulator شبكة أو queueing model أو قياس فيزيائي، فمفيش معادلة تتفاضل — فيه إجراء بيتنفّذ. black boxes (صناديق سوداء). لو اللي بتقيّمه ملف تنفيذي من مورّد أو حتة hardware، فإنت بتاخد outputs قصاد inputs ومفيش أي حاجة تانية.

خد حالة الـ feature selection بشكل ملموس. مع 8 features مرشّحة فيه 2⁸ = 256 subset ممكنة، وتقدر تجرّبهم كلهم بسهولة. مع 40 مرشّح فيه 2⁴⁰ = 1,099,511,627,776 subset. ولو التقييم الواحد معناه تدريب model وتقييمه في ثانية واحدة، فالبحث الشامل هيخلص بعد حوالي أربعة وتلاتين ألف سنة. الفضاء محدود ومتعرّف تمامًا، ومفيش أمل تعدّه.

اللي تقدر تعمله رغم كده إنك تقيّم وتقارن. ممكن متعرفش شكل الـ objective function، بس تقدر تدّيها candidate وتقرا منها رقم. ودي الواجهة الوحيدة اللي الـ genetic algorithm محتاجها خالص.

مسألة الـ black-box optimization

x^{\star} = \arg\max_{x \in \mathcal{S}} f(x)

لاقي العضو في فضاء البحث S اللي بياخد أعلى درجة على حسب الـ objective function f. مفيش حاجة هنا بتفترض إن S متصل، ولا إن f ليها مشتقة، ولا حتى إن f مكتوبة صراحةً — f ممكن تبقى simulator أو run تدريب أو قياس في معمل. والعملية الوحيدة المفروض إنها متاحة هي تقييم f عند نقطة إنت بتختارها.

نقطة واحدة بتنزل، ولا population منتشرة

الـ gradient descent بيحتفظ بـ candidate حل واحد بالظبط وبيحرّكه. كل خطوة بتقرا الميل المحلي وتخطي عكسه.

للمقارنة: خطوة الـ gradient

\mathbf{w}_{t+1} = \mathbf{w}_t - \alpha \nabla L(\mathbf{w}_t)

التحديث من الوحدة 2، متكرّر هنا للمقارنة بس. نقطة واحدة، واتجاه واحد، ومعلومات جاية من مشتقة الـ loss عند النقطة دي. خد بالك من الرموز: الوحدات من 1 لـ 3 بتسمّي الـ learning rate α والوحدة 6 بتسمّيه η — نفس الكمية برمزين. ومفيش في الطرق اللي بالـ population أي حاجة تقابل المعادلة دي خالص، لأنها عمرها ما بتحسب ميل.

الطريقة اللي بالـ population (المجتمع) بتحتفظ بـ candidates كتير في نفس الوقت، وبتاخد معلوماتها من المقارنات بينهم. محدش بيسأل أنهي اتجاه أحسن؛ الـ algorithm بيسأل بس أنهي candidate أحسن. والفرق ده بيشتري تلات حاجات:

مناطق كتير في نفس الوقت. متسلّق التل الواحد بيلتزم بالجوار اللي بدأ فيه. أما population من 50 candidate فممكن تبقى قاعدة في كذا حوض في نفس اللحظة، والـ candidates اللي في الأحواض الوحشة رخيصين تسيبهم. أجزاء، مش نقط بس. candidateين متوسطين ممكن كل واحد فيهم يبقى شايل حتة مفيدة — واحد عنده مجموعة الـ features الصح، والتاني قوة الـ regularization الصح. والـ recombination (إعادة التركيب) هي اللي بتخلّي الطريقة تجمّع ابن من الاتنين، ودي المكوّن اللي مفيش طريقة بنقطة واحدة عندها. مفيش شرط نعومة. المقارنة بتشتغل على أي حاجة ينفع تترتّب: أرقام صحيحة، أو permutations (تباديل)، أو أشجار برامج، أو اختيارات فئوية.

الـ population بتكلّف إيه

خليك صريح في الفاتورة. خطوة الـ gradient الواحدة محتاجة forward pass واحد وbackward pass واحد. أما الجيل الواحد فمحتاج تقييم كامل للـ objective function لكل فرد — فـ population من 50 بتشتغل 100 جيل يعني 5,000 تقييم، ولو التقييم معناه تدريب model فدول 5,000 run تدريب. الـ population مش قوة زيادة ببلاش؛ دي تمن إنك معندكش مشتقة تمشي وراها. والدرس 13.4 بيرجع للـ trade-off ده بصراحة.

الأربع مكوّنات

جون هولاند حط المخطط ده في كتابه Adaptation in Natural and Artificial Systems (1975)، وكتاب ديفيد جولدبرج Genetic Algorithms in Search, Optimization, and Machine Learning (1989) هو المرجع اللي نقله للممارسة الهندسية. شيل المفردات البيولوجية وهتلاقي إن أي genetic algorithm (خوارزمية جينية) هي أربع قرارات:

1. الـ representation (التمثيل). الـ candidate الواحد بيتكتب إزاي؟ bit string، أو vector أرقام حقيقية، أو ترتيب عناصر، أو شجرة. والاختيار ده بيقيّد كل اللي بعده، لأن عوامل الـ variation لازم تشتغل على اللي إنت اخترته. 2. الـ fitness (الملاءمة). الرقم الواحد اللي بيقول الـ candidate كويس قد إيه. ده هو الـ objective function، والدرس 13.3 كله متخصّص إنك تجيبه صح. 3. الـ selection (الانتقاء). أنهي candidates يبقوا parents. ومن هنا بييجي اتجاه البحث. 4. الـ variation (التنويع). الأبناء بيختلفوا عن الـ parents إزاي — إعادة تركيب parentين (الـ crossover (التهجين)) وتغيير عشوائي صغير (الـ mutation (الطفرة)).

جيل واحد، بشكل مجرّد

P_{t+1} = \mathrm{var}\big(\mathrm{sel}(P_t, f)\big)

الـ population P بتبقى الـ population اللي بعدها بإنك تطبّق الـ selection sel — ودي الخطوة الوحيدة اللي بتستشير الـ fitness function f — وبعدين الـ variation var. الـ selection بيشيل التنوّع وبيحرّك الـ population ناحية اللي بياخد درجات كويسة أصلًا؛ والـ variation بيعمل تنوّع وبيستكشف. وسلوك الـ genetic algorithm كله هو التوازن بين الضغطين المتعاكسين دول. والدرس 13.2 بيملا اختيارات ملموسة لـ S وV.

الـ selection pressure، والفشل الكلاسيكي

الـ selection pressure (ضغط الانتقاء) هو قد إيه بتفضّل الـ candidates اللي أحسن من المتوسط وإنت بتختار الـ parents. ده أهم إعداد في الطريقة كلها من ناحية الأثر، والغلط فيه هو الطريقة الكلاسيكية اللي الـ genetic algorithm بتفشل بيها وهي باينة إنها ناجحة.

أقدم مخطط، الـ fitness-proportionate selection (الانتقاء التناسبي مع الملاءمة)، بيدّي كل فرد نصيب من مقاعد الأبوّة متناسب مع الـ fitness بتاعته:

الـ fitness-proportionate selection

p_i = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)}

احتمال إن الفرد i يتختار parent. ولأنه بيستخدم قيم الـ fitness الخام، فالضغط اللي بيطبّقه بيعتمد على مقياس القيم دي، مش على ترتيبها بس — ودي نقطة الضعف اللي الـ rank selection اتصمّم عشان يشيلها.

الضغط الزيادة هو شكل الفشل اللي المفروض تخاف منه. لو أحسن فرد خد أغلب مقاعد الأبوّة، نسخه بتملا الـ population في كام جيل. وساعتها التنوّع بيختفي، ومعاه الـ crossover: إعادة تركيب parentين متطابقين تقريبًا بتطلّع نفس الـ parent. ومبيفضلش غير الـ mutation، فالطريقة بتتحوّل بهدوء لـ random walk بطيء حوالين نقطة واحدة — وهو هدوء فعلًا، لأن متوسط الـ fitness بيبطّل يتغيّر والـ run بتبان إنها عملت convergence. ده هو الـ premature convergence (التقارب المبكر)، والدرس 13.3 بيتكلّم إزاي تكشفه وتقاومه.

الضغط الضعيف بيفشل بشكل أقل دراما وبنفس الدرجة من الكمال. لو الـ parents اتختاروا بشكل قريب من المنتظم، البنية الكويسة مش هتتحفظ مدة كفاية عشان تبني عليها، والـ population بتتوه. تبقى دفعت تمن population واشتريت random search.

ليه مقياس أرقام الـ fitness مهم

افترض إن candidateين خدوا 10 و9. الـ fitness-proportionate selection بيدّي الأحسن فيهم 10/19 = 0.53 من مقاعد الأبوّة — ميزة حقيقية. دلوقتي زوّد 990 على كل واحد، وده مبيغيّرش أي حاجة في مين الأحسن: بيبقوا 1000 و999، ونصيب الأحسن بيقع لـ 1000/1999 = 0.5003. الـ selection تقريبًا بيبطّل يميّز، وده بسبب إزاحة ثابتة بس. والـ rank selection بتاع جيمس بيكر (1985) بيشيل ده بإنه يرمي القيم الخام ويختار على الـ rank بس، فإزاحة ثابتة متقدرش تغيّر أي حاجة. وبراد ميلر وديفيد جولدبرج (1995) حلّلوا الـ tournament selection بنفس الروح: حجم الـ tournament مقبض صريح ينفع يتظبط على الـ selection pressure، بدل ما يبقى حادثة عارضة من طريقة قياس الـ objective بتاعك.

الـ genetic algorithm مكانها فين

الـ genetic algorithms اختيار واحد من كذا اختيار لـ objective من غير مشتقة، وبيساعد إنك تشوف العيلة مترتّبة على حسب كمية الـ memory اللي كل طريقة بتحتفظ بيها.

الـ random search (البحث العشوائي) بياخد candidates كل واحد لوحده. مالوش أي memory خالص، فعمره ما بيتحسّن في التخمين — بس متوازي بسهولة تامة، وده baseline جدّي مش straw man. الـ grid search (البحث الشبكي) بيعدّ grid منتظمة. منهجي وبيتعاد، وعدد النقط اللي محتاجها بيتضاعف مع كل بُعد بتزوّده، وعشان كده الدرس 10.2 بيحذّرك منه في tuning الـ hyperparameters اللي أبعادها كتير. الـ hill climbing (تسلّق التل) بيحتفظ بـ candidate واحد وبيقبل الحركات اللي بتحسّن بس. بيعمل exploitation كويس وبيتعلّق في أول local optimum يقابله؛ والـ random restarts هي الرقعة المعتادة. الـ simulated annealing (التلدين المحاكى) كمان بيحتفظ بـ candidate واحد بس بيقبل ساعات حركة أوحش، باحتمال بيقل مع نزول معامل temperature — استكشاف بدري وexploitation متأخر، ونقطة واحدة طول الطريق. الـ genetic algorithms بتحتفظ بـ population وبتزوّد الـ recombination: القدرة إنك تبني ابن من حتت parentين مختلفين. والعامل ده هو اللي بيميّزها عن كل اللي فات، وجولدبرج (1989) صريح إن طرق البحث التقليدية — القايمة على التفاضل، والتعداد، والعشوائية البحتة — كل واحدة فيها بتفشل على نوع مختلف من المسائل، ودي الحجة على إن العيلة دي تبقى متاحة أصلًا.

التطوّر استراتيجية بحث، مش نوع models

ده الإطار اللي المفروض تمسك فيه، وهو عادةً الأكتر لخبطة. الـ genetic algorithm مش منافس للـ random forest أو للـ neural network. مبتتعلّمش من بيانات عليها labels، ومبتطلّعش model. دي طريقة للاختيار — أنهي features، وأنهي hyperparameters، وأنهي architecture، وأنهي جدولة، وأنهي مجموعة قواعد — ونوع الـ model هو اللي الـ fitness function بتدرّبه وتقيّمه جوه الـ loop.

وده بيطلّع حاجتين على طول. الأولى، الـ genetic algorithm مش أحسن من الـ fitness function اللي إدّيتهالها؛ ومفيش عندها حاجة تقابل جملة «بيانات أكتر هتحل المشكلة». التانية، لو الـ objective بتاعك قابل للتفاضل فاستخدم المشتقة. المشتقة بتدّيك اتجاه في تقييم واحد؛ أما الـ population فلازم تستنتج اتجاه من تقييمات كتير. واللجوء للتطوّر والتفاضل متاح هو أشهر طريقة تصرف بيها حساب قد مية مرة مقابل إجابة أوحش — ودي نقطة الدرس 13.4 بيطرحها بحسابات الكلفة مفرودة.

ومفيش حاجة من دي مضمون إنها تلاقي أحسن حل. الـ genetic algorithm heuristic: بتبدّل الضمان بالقدرة إنها تشتغل على مسائل مفيش فيها أي ضمان معروض بأي تمن. اللي إنت متحكّم فيه هو الميزانية — حجم الـ population مضروب في عدد الأجيال — واللي بتاخده هو أحسن candidate شفته جوّاها.

أهم اللي اتعلّمته

الـ gradient descent والـ backpropagation محتاجين objective قابل للتفاضل. والاختيارات المنفصلة والـ permutations وoutputs المحاكاة والـ black boxes مبتدّيهوش، ودي الفجوة اللي البحث التطوّري بيملاها.
إنك تختار features من 40 مرشّح معناه إنك تختار بين 2⁴⁰ = 1,099,511,627,776 subset — محدودة ومتعرّفة تمامًا ومستحيل تتعدّ.
الطريقة اللي بالـ population بتبدّل سؤال «أنهي اتجاه أحسن» بسؤال «أنهي candidate أحسن»، واللي مش محتاج غير القدرة إنك تقيّم وتقارن.
كل genetic algorithm أربع قرارات: الـ representation، والـ fitness، والـ selection، والـ variation. هولاند (1975) حط المخطط، وجولدبرج (1989) نقله للممارسة الهندسية.
الـ selection بيشيل التنوّع والـ variation بيعمله؛ وسلوك الطريقة كلها هو التوازن بين الاتنين.
الـ selection pressure الزيادة بيعمل premature convergence: الـ population بتتملي بنسخ candidate واحد، والـ crossover بيبطّل يعمل أي حاجة، والـ run بتبان إنها عملت convergence وهي متعلّقة وبس.
الـ fitness-proportionate selection حسّاس لمقياس قيم الـ fitness. والـ rank selection (بيكر، 1985) والـ tournament selection (ميلر وجولدبرج، 1995) بيخلّوا الضغط مقبض صريح بدل كده.
بين الطرق اللي من غير مشتقة، الـ recombination هي اللي بتميّز الـ genetic algorithms عن الـ random search والـ grid search والـ hill climbing والـ simulated annealing.
الـ genetic algorithm استراتيجية بحث مش نوع models. ولو الـ objective قابل للتفاضل فاستخدم المشتقة.