التطوّر بيكسب إمتى — وبيخسر إمتى | ML-101

فين الـ genetic algorithm تستاهل تكلفتها، وفين فيه طريقة أرخص أصلًا، وحجة التكلفة اللي بتحسم أغلب ده.

السؤال الأمين

الدرس 13.1 صاغ التطوّر كـاستراتيجية بحث مش كنوع models، والصياغة دي بتحسم الدرس ده كله. فالسؤال عمره ما بيبقى «هل الـ genetic algorithm كويسة؟» — لكن «هل في مسألتي بنية طريقة أرخص تقدر تستغلها، وأنا بتجاهلها؟» الـ genetic algorithm مبتطلبش من المسألة تقريبًا أي حاجة: لا مشتقات، ولا convexity (تحدُّب)، ولا اتصال، ولا حتى تمثيل رقمي. والعمومية دي هي بالظبط سبب بطئها. فإنت بتدفع تمن كل افتراض بترفض تفترضه.

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

لو الـ objective قابل للتفاضل، استخدم الـ gradient

دي أهم قاعدة في الوحدة، وهي عن كمية المعلومات لكل وحدة حساب مش عن الأناقة. لما الـ loss function تبقى قابلة للتفاضل بالنسبة للـ parameters بتاعتها، الـ backpropagation (الانتشار الخلفي) (الدرس 6.3) بيحسب المشتقة الجزئية الدقيقة بالنسبة لـ كل parameter في backward pass واحد، بتكلفة في حدود forward pass واحد تقريبًا.

اللي backward pass واحد بيرجّعه

\nabla_{\boldsymbol{\theta}} L = \left[\frac{\partial L}{\partial \theta_1}, \; \frac{\partial L}{\partial \theta_2}, \; \ldots, \; \frac{\partial L}{\partial \theta_d}\right]

كل الـ d مكوّن مرة واحدة، وكل واحد بيقولّك المفروض تحرّك الـ parameter ده في أنهي اتجاه وبقوة قد إيه. أما الطريقة اللي بالـ population فبتاخد مقابل P تقييم P رقم scalar، وبعدين لازم تستنتج منهم اتجاه في d بُعد.

وفي شبكة بملايين الـ parameters، الفرق ده مش فرق في الدرجة. فإنك تطوّر weights شبكة كبيرة بقيم الـ fitness بس معناه إنك بترمي معلومات المشتقة اللي الـ model اتبنى عشان يدّيهالك. ولو الـ objective قابل للتفاضل — وكل الـ loss functions في الوحدات 2 و6 و7 و8 و9 كده — فالـ gradient مش بس الاختيار الأسرع، ده الاختيار اللي بيستفيد من معرفتك.

حجة التكلفة في سطر واحد

الـ genetic algorithm بتصرف عدد تقييمات بيساوي حجم الـ population في عدد الأجيال عشان تحقق تقدّم الـ model القابل للتفاضل بيحقّقه بـ forward pass وbackward pass واحد لكل خطوة. فاستخدم التطوّر لما المسألة تفرض عليك الـ trade-off ده، مش لما إنت تختاره.

الميزانية اللي بتلتزم بيها

N_{\text{eval}} = P \cdot G, \qquad T_{\text{wall}} \approx \frac{P \cdot G \cdot t_{\text{eval}}}{K}

نفس الحساب اللي في الدرس 13.3. ولما التقييم الواحد نفسه يبقى تدريب كامل لـ model، بيبقى P وG معاملين ضرب على التكلفة دي — وعشان كده الأقسام اللي تحت مهتمة جدًا بالتقييم الواحد غالي قد إيه.

البحث عن الـ hyperparameters

الـ hyperparameters مش قابلة للتفاضل بأي شكل مفيد، وبتخلط اختيارات مستمرة ومنفصلة وشرطية، وكل تقييم فيها تدريب كامل. وده black box حقيقي، فالـ genetic algorithm مقبولة هنا على الأقل — وده مش نفس القول إنها الأداة الصح. والدرس 10.2 درّس البدائل قبل كده؛ والغرض من القسم ده إنه يحط التطوّر بينهم بأمانة.

الطريقة	بتختار النقطة الجاية إزاي	التوازي	بتطلب منك إيه
الـ grid search	بيعدّ grid متثبّتة قبل أول run	متوازي تمامًا	grid، وأبعاد قليلة كفاية عشان التكلفة تتستحمل
الـ random search	بيسحب عينات من مديات إنت بتحدّدها، وبيتجاهل كل النتايج	متوازي تمامًا	مديات وتوزيعات معقولة
الـ Bayesian optimization	بيعمل fit لـ surrogate model على كل النتايج وبعدين بيحسّن acquisition function	تسلسلي بالتصميم؛ والـ batches محتاجة آلية زيادة	فضاء بحث الـ surrogate model يقدر يمثّله
الـ genetic algorithm	بتعيد تركيب وتعمل mutation للأحسن في الـ population الحالية	متوازي تمامًا جوه الجيل	encoding، وoperators بتحترمه

تلات ملاحظات على مستوى الآلية، ومن غير أي ادعاء — بقصد — عن مين بيكسب:

الـ Bayesian optimization بيطلّع أكتر من كل تقييم. بيعمل model لقيمة الـ objective وعدم اليقين فيها في كل حتة مبصّش فيها. أما الـ tournament أو الـ rank selection في الـ genetic algorithm فبيستخدم ترتيب الجيل بس، وبيرمي المقادير. ولما التقييمات تبقى المورد النادر، الاستفادة الأكبر من كل واحد فيها هي الاختيار السليم بنيويًا.
الـ genetic algorithm بتستخدم الـ hardware المتوازي بشكل أطبع. كل فرد في الجيل مستقل، فـ P worker بيشتغلوا من غير أي نظرية زيادة. أما الـ Bayesian optimization فتسلسلي في شكله الأساسي لأن كل اختيار بيعتمد على النتيجة اللي قبله.
فضاءات البحث المش مريحة بترجّح التطوّر. الـ configurations اللي طولها متغيّر، ورصّات الـ layers، والـ parameters الشرطية اللي مبتبقاش موجودة غير لو حاجة تانية اتختارت، والـ permutations — كل ده تقدر تعمل له encoding على طول وتكتب operators تخلّيه صالح. أما إنك تخلّي surrogate model يتعامل مع نفس الحاجات فمحتاج kernel متعرّف عليها.

والخطوة الأولى الأمينة قبل كل ده: لعدد قليل من الـ hyperparameters، الـ random search على مديات معقولة بيفضل default قوي. Bergstra وBengio (2012) بيّنوا إن الـ random search بيلاقي configurations كويسة زي الـ grid search أو أحسن بنفس الميزانية، لأن أغلب فضاءات الـ hyperparameters البُعد الفعّال بتاعها قليل. فمتبدأش بطريقة بالـ population لمسألة مية تجربة عشوائية بتحسمها.

الـ feature selection كبحث في الـ subsets

إنك تختار أنهي features من d تخلّيها بيناسب طبيعيًا الـ binary encoding بتاع الدرس 13.2: bit لكل feature، وstring لكل subset مرشّحة. وفضاء البحث هو كل الـ subsets.

فضاء الـ subsets والـ fitness

|\mathcal{S}| = 2^{d}, \qquad F(S) = \mathrm{CV}(S) - \alpha \cdot \frac{|S|}{d}

مع 50 feature عدد الـ subsets بيعدّي 10 أُس 15، فالتعداد مستبعد. والـ fitness هي نتيجة cross-validation مع penalty على الـ features اللي بتفضل، لأن subset بتاخد نفس النتيجة بأعمدة أقل هي الأحسن.

دي wrapper method: الـ fitness هي أداء الـ model الفعلي، فتقدر تلاقي تركيبات features مبتنفعش غير مع بعض — وده اللي filter بيرتّب كل feature لوحدها ميقدرش يشوفه. وده معناه كمان إن كل تقييم cross-validation كامل، وده بيحط حساب التكلفة بتاع الدرس 13.3 في القيادة تمامًا.

الفخ: الـ overfitting على نتيجة الـ validation

إنت على وشك تختار الحد الأقصى لعشرات الآلاف من نتايج cross-validation فيها noise. والـ subset الكسبانة هتبان أحسن من حقيقتها، لأن جزء من تفوّقها الظاهر حظ في الـ folds دي بالذات. فاحجز test set البحث عمره ما يلمسها وبلّغ عن الرقم النهائي عليها — ده نفس الانضباط اللي الدرسين 1.4 و10.2 مُصرّين عليه، وهو أهم هنا لأن البحث بيقيّم نتيجة الـ validation مرات كتير جدًا.

وبدائل أرخص لازم تستبعدها الأول: الـ L1 regularization بيزقّ الـ coefficients لصفر بالظبط كأثر جانبي لـ fit model واحد (الدرس 2.3)؛ والـ feature importance المبنية على الـ trees والـ permutation importance بييجوا تقريبًا ببلاش من model إنت دربته أصلًا (الدرس 3.2)؛ والـ greedy forward أو backward selection بيكلّف في حدود d تربيع تقييم مش بحث كامل بـ population. والـ genetic algorithm بتستاهل التكلفة الزيادة لما الـ features تتفاعل بقوة كفاية إن المسار الـ greedy يتكعبل.

الـ neuroevolution

الـ neuroevolution (التطور العصبي) معناه تطوير الـ neural networks، وبيتقسم لمهمتين مختلفين خالص.

تطوير الـ weights

اعمل encoding للـ weights كـ real-valued vector واختار على حسب الأداء. وبحكم حجة الـ gradient اللي فوق، ده الاختيار الغلط لما يبقى فيه loss function قابلة للتفاضل — يعني في أغلب الـ supervised learning. وبيبقى معقول بالظبط لما ميبقاش فيه واحدة: لما الـ feedback الوحيد يبقى نتيجة simulation أو لعبة، أو لما الـ reward توصل بعد الأفعال اللي استحقّتها بكتير، أو لما output الشبكة يعدّي على حاجة مش قابلة للتفاضل قبل ما النتيجة تبان. وخد بالك إن الوحدة 14 بتهاجم نفس النوع من المسائل بالـ reinforcement learning (التعلّم المعزَّز)، اللي بيبني تقدير للـ gradient من الـ reward، فالتطوّر اختيار هناك مش الاختيار الوحيد.

تطوير الـ architecture

الـ topology منفصلة: كام layer، وبأي عرض، وأنهي connections موجودة. ومفيش gradient متاح بالنسبة للاختيارات دي، فالبحث هو الطريقة الأمينة والتطوّر بيناسبها طبيعيًا. وNEAT — من Stanley وMiikkulainen (2002)، Evolving Neural Networks through Augmenting Topologies — بيطوّر weights الـ connections والـ topology مع بعض، وأفكاره التلاتة المعروفة كل واحدة بتحل مسألة محدّدة بتظهر أول ما البنية تبقى قابلة للتغيير:

ابدأ بأقل حاجة وبعدين عقّد. ابدأ بأبسط الشبكات وزوّد الـ nodes والـ connections على مدار الـ run، فالبحث ميبدأش في فضاء أكبر من اللازم.
الـ historical markings (العلامات التاريخية). كل عنصر بنيوي جديد بياخد معرّف أول ما يظهر، وده بيخلّي الـ crossover يصطف على الـ genes اللي شبكتين ورثوها من جد مشترك بدل ما يزاوج حتت ملهاش علاقة ببعض.
الـ speciation (التنويع النوعي). الأفراد بيتنافسوا أساسًا جوه الـ species بتاعتهم، فالبنية اللي اتزوّدت جديد بتتحمى مدة كفاية عشان الـ weights بتاعتها تتحسّن. ومن غير كده الابتكار الجديد عادةً بيبقى أوحش لما يوصل والـ selection بيشيله قبل ما يتاح له ينجح.

الـ symbolic regression والـ genetic programming

في الـ genetic programming (البرمجة الجينية) الفرد برنامج مش vector. وKoza (1992) في Genetic Programming: On the Programming of Computers by Means of Natural Selection بيمثّل البرامج كـ expression trees على مجموعة متختارة من الـ functions والـ terminals؛ والـ crossover بيبدّل الـ subtrees بين parentين، والـ mutation بتبدّل subtree بواحدة جديدة. ولأن الـ operators بتشتغل على الأشجار، الـ candidate بيفضل برنامج صالح — ودي فكرة الحفاظ على الـ feasibility من الدرس 13.3، متطبّقة على الـ code.

ولما تطبّق ده على fit البيانات بيبقى الـ symbolic regression (الانحدار الرمزي): بحث في التعبيرات عن تعبير بيعمل fit وينفع يتقري في نفس الوقت. والـ output مش مجموعة weights لكن حاجة أقرب لمعادلة تقدر تحطها في تقرير وتفكّر فيها، وده output مختلف عن كل model تاني في الكورس ده. وهنا بالظبط بتبقى مجزية — لما تبقى عايز العلاقة، مش التنبؤ بس.

الـ parsimony pressure

F(p) = -\,\mathrm{error}(p) \; - \; \beta \cdot \mathrm{size}(p)

الأشجار بتميل تكبر على مدار الـ run من غير تحسّن في الـ fitness — واسمها الـ bloat (التضخّم) — وتعبير حجمه ضخم بيبوّظ الهدف من استخدام الطريقة دي أصلًا. والـ penalty على الحجم هي الإجراء المضاد المعتاد؛ والمعامل بيتا بيحدّد قد إيه من الدقة إنت مستعد تبدّله بقابلية القراية.

إمتى متلجأش لـ genetic algorithm

الـ objective قابل للتفاضل. استخدم الـ gradient. وده بيغطّي أغلب الكورس ده.
المسألة convex أو linear أو integer program معتاد. solver مخصوص بيرجّع إجابة ومعاها حد على بعدها عن الأمثل. أما الـ genetic algorithm فبترجّع حل كويس ومن غير أي حد.
المسألة ليها بنية combinatorial معروفة. أقصر المسارات، والـ matchings، ومسائل الجدولة اللي ليها algorithm دقيق — طريقة دقيقة بتستغل البنية بتغلب بحث عام بيتجاهلها.
فضاء البحث صغير. كام ألف candidate؟ عِدّهم كلهم. هتاخد الأمثل الحقيقي وcode أبسط.
الـ fitness فيها noise جامد. الـ selection محتاج يقدر يفرّق بين candidateين. ولو الـ noise عدّى الفروق، الـ population بتتوه والـ run بتبان ناجحة وهي مش كده.
متقدرش تكتب fitness function تثق فيها. يبقى المشكلة هي الدرس 13.3 مش الـ algorithm، ومفيش أي قدر من الـ tuning هينقذها.
ميزانية التقييمات صغيّرة جدًا. شوية تقييمات غالية بتناسب طريقة بتعمل model للـ objective؛ أما population من 100 فرد فلسه مخلّصتش أول جيل.

checklist القرار

أقدر أفاضل الـ objective؟ لو أيوه، وقّف هنا واستخدم الـ gradient.
هل المسألة بتطابق نوع اتحل؟ convex، linear، integer program، مسألة graph — استخدم الطريقة المخصوصة وخد ضمان.
هل الفضاء صغير كفاية للتعداد، أو للحسم بـ random search؟ جرّب الرخيص الأول، وخلّيه الـ baseline اللي البحث لازم يغلبه.
التقييم الواحد بيكلّف قد إيه، وأقدر أستحمل كام تقييم؟ القليل جدًا والغالي جدًا بيرجّح طريقة surrogate model؛ والكتير الرخيص المتوازي بيرجّح population.
هل الـ representation بتاعي مش مريح — طول متغيّر، شرطي، permutations، أشجار؟ هنا التطوّر بيبقى مرتاح فعلًا والطرق التانية محتاجة سقالات زيادة.
أنا واثق في الـ fitness function؟ اقرا الدرس 13.3 تاني قبل ما تصرف الميزانية.
ثبّت الـ baseline الأمين؟ random search بنفس ميزانية التقييمات. بلّغ عن الاتنين، وإلا المقارنة مالهاش معنى.

أهم النقط

الـ genetic algorithm مبتفترضش تقريبًا أي حاجة عن المسألة، وبتدفع تمن العمومية دي تقييمات. ولو الـ objective قابل للتفاضل فاستخدم الـ gradient: backward pass واحد بيدّي المشتقة الدقيقة لكل parameter، أما P تقييم فبيدّوا P رقم scalar. والتطوّر مقبول للبحث عن الـ hyperparameters، بس قارنه بأمانة بالـ grid والـ random والـ Bayesian search (الدرس 10.2) — الـ Bayesian optimization بيطلّع أكتر من كل تقييم، والـ genetic algorithm بتتوازى بشكل أطبع، وفضاءات البحث المش مريحة بترجّح التطوّر، والـ random search (Bergstra وBengio، 2012) هو الـ baseline اللي كلهم لازم يغلبوه. والـ feature selection كبحث في الـ subsets بتشتغل، وبتعمل overfitting على نتيجة الـ validation لو سبتها. وتطوير الـ architecture أوجه من تطوير الـ weights، وNEAT (Stanley وMiikkulainen، 2002) بيوضّح السبب: بدايات بأقل حاجة، وhistorical markings، وspeciation. والـ genetic programming (Koza، 1992) هي الحالة اللي الـ output فيها تعبير ينفع يتقري، مع الـ bloat كخطر دايم. ولما طريقة أرخص تناسب المسألة، استخدمها.