تعرف على خوارزمية النزول التدرجي الأشهر في الخوارزميات التحسينية

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

تتمحور آلية عمل هذه الخوارزمية حول فكرة أخذ عدد من الخطوات في المنحى المعاكس للتدرج negative gradient، أو التدرج التقريبي، في النقطة الحالية. وذلك لكون هذا المنحى هو منحى النزول الأشد إنحداراً steepest descent. وعلى النقيض، التقدم باتجاه منحى التدرج سيقودنا بالطبع للقيمة القصوى أو قيمة قصوى محلية للدالة.

أصول خوارزمية النزول التدرجي

عموما، تم الاجماع على نسب هذه الخوارزمية إلي عالم الرياضيات أوغستين لوي كوشي A.L. Cauchy. والذي كان أول من اقترحها في سنة 1847. تم اقتراح طريقة مشابهة، بشكل مستقل، من طرف جاك هادامار أيضًا سنة 1907. كما تم دراسة خاصيات هذه الخوارزميات للتقارب حول الحل الأمثل في المشاكل التحسينية غير الخطية، أول مرة، من طرف هاسكل كاري Haskell Curry سنة 1944. وتم دراسة خوارزمية النزول التدرجي واستخدامه، وقدمت أعداد كبيرة من الإسهامات، من متحورات وطرق استخدام أفضل، بشكل كبير في السنوات التي تلت.

مثال لفهم آلية عمل خوارزميات النزول التدرجي

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

باستعمال هكذا مقاربة ستجد نفسك، في النهاية، قد وصلت أسفل الجبل، أو بلغت حفرة تمتلأ بالماء ليلاً مما قد يتسبب في موتك.

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

في هذه المماثلة، يعبّر الشخص الخاضع لهذه الصعوبات عن الخوارزمية، كما يمثل المسار الذي يسلكه نقاط الفضاء التي ستمر الخوارزمية منها عند تعدد التكرارات. ويمثل الانحدار ممال الدالة عند نقطة القياس. كما يمثل الجهاز الذي يحدد الانحدار، عملية الاشتقاق. ويعتبر أسفل الجبل، القيمة الدنيا للدالة أي الحل الأمثل، بينما الحفر والبحيرات الجبلية تعبر عن الحلول المحلية للدالة أي النقاط الدنيا المحلية. إضافة لذلك، نجد أن منحى الحركة هو سالب الانحدار negative gradient، أي (x)F∇-. كما أن المدة الزمنية بين كل قياس باستعمال الجهاز، هي الخطوة γn.

شرح رياضي لآلية عمل خوارزمية النزول التدرجي

لارتكاز هذه الخوارزمية بشكل أساسي على دراسة الدالة الهدف (x)F متعددة المتغيرات، المعرفة والقابلة للاشتقاق، يكون تناقصها عند أقصى قيمة عند الذهاب من النقطة الحالية باتجاه المنحى المعاكس للتدرج (x)F∇-.

مع العلم أن x متغير متعدد الأبعاد أي نقطة في فضاء متعدد الأبعاد. بحيث تمثل n دورة التكرار الحالية. نبدأ ب n=0 أو الدورة صفر أي القيمة البدئية قبل بداية التكرارات. تمثل γn حجم الخطوة الذي يمكن أن يتغير من دورة لأخرى.

أهمية حجم الخطوة γ ومنحى النزول

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

للحرص على تحقيق كل هذا، يوجد عدد من الطرق الرياضية منها:

• البحث الخطي الذي يستوفي شروط وولف Wolfe conditions.
• البحث الخطي التراجعي backtracking line search.
• طريقة Barzilai–Borwein، الموضحة في الأسفل.

يكون التقارب لحل محلي أمرًا مضموناً دائمًا. وإن كانت الدالة الهدف محدبة convex، يكون التقارب للحل الأمثل مسلمًا به نظرًا لتطابق الحلين المحلي والأمثل.

متحورات خوارزمية النزول التدرجي

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

نزول الدفعة التدرجي Batch Gradient Descent

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

نزول الدفعة المصغرة التدرجي Mini-batch Gradient Descent

بدلًا من معالجة كل الأمثلة عند كل دورة نقسم الأمثلة لمجموعات صغيرة ونقوم بمعالجتها كل على حدى. دائمًا ما نأخد حجم العينات من أُس 2 أي 2 4 8 16 32 64 128 256 …… يرجع هذا لكون عدد من الهاردوير، مثل وحدة معالجة الرسوميات GPU، تحقق سرعة تنفيذ جيدة عند تقسيم هذه العينات بهذه الطريقة.

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

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

خوارزمية النزول التدرجي التصادفية Stochastic Gradient Descent

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

مصادر

1. Medium
2. GeeksforGeeks
3. Wikipedia
4. TowardsDataScience