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

دليلك لفهم خوارزمية أدم ADAM التحسينية الأكثر استخدامًا في التعلم العميق

هذه المقالة هي الجزء 12 من 12 في سلسلة أشهر الخوارزميات التحسينية المستوحاة من الطبيعية

اختيارك للخوارزمية التحسينية المناسبة لتدريب نموذجك للتعلم العميق، يعني مباشرة اختيارك جودة ومدة التنفيذ. فاختيارك هذا له الكلمة الفصل في قدرتك على الحصول على نتائج في دقائق، أو ساعات، أو حتى أيام. أو ربما عدم حصولك على نتيجة خلال فترة حياتك. ومن بين هذه الخوارزميات، نجد أن خوارزمية أدم ADAM هي أحد أكثر الخوارزميات التحسينية استخدامًا في مجال التعلم العميق. وتحديدًا في تدريب الشبكات العصبية الاصطناعية. وقد أشرنا سابقا أن خوارزمية النزول التدرجي ومتحوراتها هم الأكثر استخدامًا في هذا المجال، لكن ما لم نذكره هو أن خوارزمية أدم ADAM هي متحور من متحورات خوارزمية النزول التدرجي. وبالتحديد خوارزمية النزول التدرجي التصادفية Stochastic Gradient descent.

وقد استخدمت خوارزمية النزول التدرجي التصادفية SGD في السنوات الأخيرة بشكل مكثف وكبير في فروع عديدة من الذكاء الاصطناعي، لعل أبرزها هما الرؤية الحاسوبية computer vision، ومعالجة اللغة الطبيعية Natural Language Processing.

ما هي خوارزمية أدم ADAM؟

أصول خوارزمية أدم ADAM

ابتُكرت خوارزمية أدم بهدف استبدال خوارزمية النزول التدرجي التصادفية، وذلك، تحديداً في عملية تدريب نماذج التعلم العميق deep learning. وقد تم اقتراح هذه الخوارزمية من طرف دايديريك كينغما Diederik Kingma رائدة المجال OpenAI و جيمي با Jimmy Ba من جامعة تورونتو سنة 2015 في ورقة بحثية في مؤتمر ICLR باسم “أدم: طريقة للتحسين التصادفي”، Adam: a method for stochastic optimization. تم تسمية هذه الخوارزمية أدم اختصارًا ل: ADAptive Moment estimation <=> ADAM.

مميزات الخوارزمية

في تقديمهم لخوارزمية أدم، وضح الباحثان مميزات هذه الخوارزمية في التعامل مع المشاكل غير المحدبة، أي دالتها الهدف غير محدبة non-convex objective function. من بينها:

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

آلية عمل أدم

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

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

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

Adaptive Gradient Algorithm، أو AdaGrad: والتي هي الأخرى تستعمل حجم خطوة متغير لتعزيز أدائها في حل المشاكل ذات التدرج الضئيل. ما يعني في التعلم العميق أن الشبكة لا تستقبل إشارات كافية لضبط أوزانها. ومن أمثلة هذه المشاكل نجد: معالجة اللغة الطبيعية NLP، و الرؤية الحاسوبية، وغيرها.

خوارزمية انتشار جذر متوسط المربع

Root Mean Square Propagation، أو RMSPropa: التي أيضًا تستعمل خطوة متغيرة. ذلك التغير، بدلالة متوسط مُضمحل للتدرجات الجزئية. ما يعني أن أداء هذه الخوارزمية جيد عند مواجهتها لمشاكل ذات فضاء بحث متغير زمنيًا، أو عند وجود تشويش يغير من قيم التدرج.

كيف تجمع أدم ADAM فوائد هاتين الخوارزميتين؟

فبدلاً من تكييف معدلات التعلم لمتغيرات الدالة الهدف بناءً على متوسط العزم الأول average first moment كما هو الحال في RMSProp، تستخدم آدم أيضا متوسط العزوم الثانية للتدرجات Uncentered variance.

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

رياضيات

العزم

يستعمل العزم لتسريع النزول التدرجي.

تعبر (t)W عن قيمة الأوزان في لحظة t. يمثل ألفا درجة التعلم، أي حجم الخطوة الحالي. كما تمثل (t)m مجموع التدرجات عند اللحظة t.

تمثل (t)m مجموع التدرجات عند اللحظة t أي الدورة الحالية، بينما (t-1)m تعبر عن هذا المجموع في الدورة السابقة. dL هي مشتقة الدالة الهدف، (t)dW مشتقة الأوزان عند اللحظة t. بيتا هي المتغير المتحرك (مفهوم إحصائي).

انتشار جدر متوسط المربع RMSProp

تمثل ε ثابتة صغيرة لتجنب القسمة على صفر.

أدم

انطلاقا من معادلات الطريقتين أعلاه، نتحصل على:

متجهة العزم الأولى (t)m. متجهة العزم الثانية (t)v.

نظرًا لأن كل من mt و vt قد تم تصفيرهما بدئيًا، وكذلك لكون β1 و β2 تأخد قيم تقارب 1، لوحظ تجريبيًا أنهما يكتسبان تحيزًا نحو الصفر. لإصلاح هذا نقوم بحساب قيم تصحيحية. ويتم حساب هذه القيم أيضًا للتحكم في الأوزان عند قرب وصولنا للحل الأمثل وذلك لمنع التذبذبات عالية التردد. والصيغ المستخدمة هي:

ما يمكننا من استبدال mt و vt بقيم مصححة:

نجد (t)w قيم النقطة الحالية عند اللحظة t.

الأداء العملي

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

يبين المنحنى أداء مجموعة من الخوارزميات بالمقارنة مع أداء خوارزمية أدم في التدريب التحسيني لشبكة عصبية متعددة الطبقات على صور MNIST. المصدر غووغل.

مصادر

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

هذه المقالة هي الجزء 5 من 12 في سلسلة أشهر الخوارزميات التحسينية المستوحاة من الطبيعية

في الرياضيات، النزول التدرجي 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، الموضحة في الأسفل.

تعبر القيم Xn و 1-Xn عن النقطة الحالية و النقطة السابقة، تعبر T عن منقولة هذه المصفوفة، لكون الفرق عبارة عن قيمة متعددة الأبعاد، مصفوفة الفرق بين قيمتي النقطة الحالية وسابقتها. في المقام نجد مربع معيار الفرق بين التدرج الحالي وسابقه. الخطوة دائما موجبة لذا تم إضافة القيمة المطلقة للبسط.

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

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

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

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

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

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

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

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

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

التكلفة cost، و iterations هو عدد التكرارت، بينما المنحنى الأحمر يمثل تقليصنا للدالة الهدف على مر التكرارات.

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

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