شرح تطبيقي لخوارزمية النزول التدرجي Gradient Descent

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

لماذا نحتاج خوارزمية النزول التدريجي؟ ما الهدف؟

قبل البدء في تعريف الخوارزمية، أٌفضّل التطرق لاسباب نشوؤ مثل هذه الخوارزميات ودواعي الحاجة لها. خوارزمية النزول التدريجي واحدة من أهم الخوارزميات في مجال تعلم الآلة.

من مبادئ "تعلم الآلة machine learning" التركيز على استخراج أفضل تقدير ممكن للقيمة المراد توقعها. مثلاً، يمكن استخدام  الانحدار regression للتنبؤ بقيمة y ذات علاقة خطية مع متغير ما x عن طريق استنباط قيمة المعاملين m و b لانتاج المعادلة الخطية y = mx + b. في هذه الحالة، الهدف هنا ليس "توقع قيمة y" وحسب، بل "استخراج أفضل قيمة m و b تمكننا من الحصول على أدق قيمة متوقعة للقيمة y"، وهناك فرق كبير بينهما. الجملة الثانية هي ما يدفع محلل البيانات للبحث عن تقنيات رديفة أو مكملة لاستخراج أفضل دالة لتوقع القيم. 

ولكن كيف يمكن اختيار أفضل معاملات coefficients ممكنة؟

لكل دالة y = mx + b يوجد العديد من المعاملات الممكن استخدامها بحيث تنتج معادلة "تؤدي الغرض" في التوقع كما هو مؤضح في الصورة التالية. أغلب الخطوط الظاهرة يمكن اعتماد معاملاتها m و b والاعتماد على المعادلة للتبؤ بقيمة y بدقة جيدة، بينما هناك بالتأكيد خط من تلك الخطوط ذو دقة أعلى في التنبؤ. 

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

السؤال الآن هو، كيف يمكن الوصول للخط الأدق في وصف النقاط في العينة؟ بمعنى، كيف يمكن الوصول للمعامين m و b الأفضل في تكوين دالة دقيقة التنبؤ؟

في أي سؤال مفاضلة كالسؤال السابق، نحتاج إلى آلية لتقييم جودة كل دالة لنتمكن من ترتيب المعاملات من الأفضل إلى الأسوأ في تكوين دالة التنبؤ. أفضل طريقة لتقييم جودة دالة ما، هي عن طريق احتساب الفرق بين القيم المتنبئ بها مقارنة بالقيم الواقعية (ويمكن الإشارة للفرق بـ"التكلفة cost"). قيمة التكلفة يمكن استخدامها في ترتيب الدوال وتفضيل الدالة ذات التكلفة الأقل. تسمى هذه الآلية في احتساب الفرق بين القيم المتوقعة والقيم الواقعية بدالة التكلفة cost function (يشار لها بدالة الخسارة loss function في بعض السياقات). يوجد العديد من التطبيقات المختلفة لدوال التكلفة ويصعب التطرق لها هنا فنقتصر على الفهم العام للمصطلح.

وحتى لا يكون الحديث مقتصر على المصطلحات النظرية، أقدم المثال التالي لتوضيح الفكرة بشكل أوضح في الفضاء الثلاثي الأبعاد.

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

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

ملاحظة: تم تنسيب القيم normalization في محوري إعلانات الراديو والتلفاز لتوحيد المقياس 

معادلة السطح هي: z = ax + by + c بالتالي وفيما يخص مثالنا يمكن كتابة معادلة السطح السابق كالتالي:

Sales = a*Radio ads + b*TV ads + c

لكي نضمن إيجاد أفضل سطح مستوي يمثل البيانات السابقة، نطمح للوصول إلى أفضل قيم للمعاملات a,b,c بحيث تقلل قيمة دالة التكلفة cost لأقل قيمة ممكنة. يمكننا ذلك عن طريق احتساب تكلفة جميع التركيبات الممكنة للقيم a,b,c ومن ثم اختيار المعملات ذات التكلفة الأقل.

احتساب تكلفة اختيار سطح ممثل بـ a,b,c معينة، يكون عن طريق احتساب متوسط الفرق بين القيم المتوقعة باستخدام السطح والقيم الواقعية الظاهرة في البيانات الأصلية. كلما زاد الفرق بين القيمتين كلما ارتفعت تكلفة السطح.

في نهاية الخطوة السابقة، يتكون لدينا مصفوفة ثلاثية الأبعاد cost بحيث كل قيمة في المصفوفة [cost[a][b][c تمثل تكلفة اختيار السطح المتمثل في القيم a,b,c.

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

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

تعريف خوارزمية النزول التدرجي: هي خوارزمية استمثال optimization تستخدم لخفض قيمة دالة التكلفة cost function لنموذج ما وبالتالي تحسين دقة النموذج في التنبؤ. النزول التدرجي يمكننا من الوصول لأفضل قيمة في المصفوفة دون الحاجة للاطلاع على جميع القيم فيها. يمكن ذلك عن طريق إيجاد التدرج gradient للتكلفة عند قيمة ما في المصفوفة. 

للتوضيح، لنتخيل مصفوفة التكلفة على أنها سطح surface كالتالي:

كل نقطة على السطح السابق تمثل قيمة التكلفة cost لمعاملين a و b. للوصول إلى أفضل تركيب (a,b) نبحث عن النقطة ذات التكلفة الأقل cost. في المثال، يمكننا أن نستنبط أن أفضل قيمة للمعاملين a,b في خفض قيمة التكلفة هما b = -1 و a = 0 حيث أن أعمق نقطة في السطح تتمثل في تلك النقطة (ممثلة باللون الأزرق الداكن). 

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

بالعودة إلى مثالنا السابق،

 يمكننا تمثيل سطح التكلفة لإيجاد أفضل معاملين a,b للسطح Sales = a*Radio ads + b*TV ads + c كالتالي:

أعمق نقطة في سطح التكلفة في الرسم البياني السابق تمثل أفضل قيم للمعاملين a و b لرسم سطح تنبؤي مثالي للبيانات. يمكننا أيضاً تمثيل دالة التكلفة بالمخطط الكونتوري contour plot التالي. حيث ننظر للرسم البياني للدالة من أعلى نقطة ممكنة:

وهنا يمكننا بسهولة استنباط أفضل قيمة لa و b وهي أعمق نقطة في المخطط الكونتوري حيث a = 3 و b = 4. ولكن، كيف تقوم خوارزمية النزول التدرجي بالوصول لتلك القيمة؟

تبدأ العملية من أي نقطة عشوائية على السطح:

 وتتقدم الخوارزمية كالتالي:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

iterations = 1 for i in range(200): gradient, error = get_gradient_and_error(coefficients,X_scaled,y) new_coefficients = coefficients - alpha * gradient # Print error every 10 iterations if iterations % 10 == 0: print("Iteration: %d - Error: %.4f" % (iterations, error)) old_coefficients.append(new_coefficients) errors.append(error) # Stopping Condition if np.sum(abs(new_coefficients - coefficients)) < tolerance: print("Iteration: %d - Error: %.4f" % (iterations, error)) print('Gradient Descent has converged') break iterations += 1 coefficients = new_coefficients print('coefficients =', coefficients)

في بداية الكود، في السطر 3 القيمة coefficients تمثل قيمة المعاملات العشوائية المبدئية كما تظهر النقطة الحمراء في الرسم البياني السابق. في كل دورة iteration، يتم احتساب التدرج gradient للنقطة coefficients واحتساب تكلفة cost هذه المعاملات. 

في السطر 4 يتم تحديث قيمة المعاملات بناءً على مدى انحدار التدرج "how steep the gradient is" وقوة التعلم للخوارزمية alpha (يمكن الإشارة إلى alpha كالمدى المسموح النزول له).
نقوم بطباعة التكلفة والمعاملات المستنبطة بعد كل 10 دورات لتسهيل عملية رسم القيم لاحقاً كما في الأسطر بين 7 و 10.

السطر 12-19: في حال انخفاض قيمة التكلفة واقترابها من الصفر، تتوقف الخوارزمية ويتم تخزين المعاملات حينها على أنها أفضل معاملات لتكوين السطح الممثل للبيانات (أعمق نقطة في سطح التكلفة).

لتوضيح الخوارزمية السابقة بيانياً، يمكننا الاطلاع على الرسم التالي:

كل سهم في الرسم السابق يمثل عشر دورات في خوارزمية النزول التدرجي. في كل مرة، تقترب الآلة من أعمق نقطة في سطح التكلفة حتى تصل في الأخير إلى النقطة كما هو موضح في الصورة. أعمق نقطة اعتماداً على النزول التدريجي هي: [3.9،2.7].

بالتالي يمكن التعويض في المعادلة السابقة للسطح:

Sales = 2.7*Radio ads + 3.9*TV ads + c

يمكن احتساب قيمة c من قوانين التقاطع (خارج نطاق المقال) والنتيجة هي:

Sales = 2.7*Radio ads + 3.9*TV ads + 14.06

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








بعض المراجع المستفاد منها:

• http://www.adeveloperdiary.com/data-science/how-to-visualize-gradient-descent-using-contour-plot-in-python/
• https://andreask.cs.illinois.edu/cs357-s15/public/demos/12-optimization/Steepest%20Descent.html
• https://medium.com/@faisalshahbaz/best-optimization-gradient-descent-algorithm-4ca5a3be3776
• https://hackernoon.com/gradient-descent-aynk-7cbe95a778da
• https://towardsdatascience.com/gradient-descent-algorithm-and-its-variants-10f652806a3
• https://towardsdatascience.com/gradient-descent-in-python-a0d07285742f
• https://towardsdatascience.com/machine-learning-bit-by-bit-multivariate-gradient-descent-e198fdd0df85