📌 👷 🍄 نظرة عامة على طرق التدرج في مشاكل التحسين الرياضية 🤳🏽 🌠 🤲🏽

مقدمة

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

UPD في التعليقات يكتبون أنه في بعض المتصفحات وفي صيغ تطبيقات الهاتف المحمول لا يتم عرضها. لسوء الحظ ، لا أعرف كيفية التعامل معها. لا يسعني إلا أن أقول أنني استخدمت وحدات الماكرو "المضمنة" و "العرض" لمحرر Habrava. إذا كنت تعرف فجأة كيفية إصلاح ذلك - اكتب في التعليقات ، من فضلك.

ملاحظة من المؤلف

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

بيان المشكلة

قبل وصف الطريقة ، يجب عليك أولاً وصف المشكلة ، وهي: "هناك العديد منها

$\ mathcal {K}$ والوظيفة

$f: \ mathcal {K} \ rightarrow \ mathbb {R}$ بحاجة لإيجاد نقطة

$x ^ * \ in \ mathcal {K}$ مثل هذا

$f (x) \ geq f (x ^ *)$ للجميع

$x \ in \ mathcal {K}$ "، وهو ما يكتب عادة هكذا

$f (x) \ rightarrow \ min_ {x \ in \ mathcal {K}}.$

من الناحية النظرية ، عادة ما يفترض ذلك

$f$ هي دالة محدبة ومحددة

$\ mathcal {K}$ - مجموعة محدبة (وحتى أفضل ، على الإطلاق)

$\ mathcal {K} = \ mathbb {R} ^ n$ ) ، هذا يسمح لنا بإعطاء بعض الضمانات لنجاح تطبيق التدرج. من الناحية العملية ، يتم تطبيق نزول التدرج بنجاح حتى عندما لا تحتوي المهمة على أي من الخصائص المذكورة أعلاه (مثال لاحقًا في المقالة).

القليل من الرياضيات

لنفترض الآن أننا بحاجة فقط إلى إيجاد حد أدنى من وظيفة أحادية البعد

$f (x) \ rightarrow \ min_ {x \ in \ mathbb {R}}.$

في القرن السابع عشر ، توصل بيير فيرمات إلى معيار جعل من الممكن حل مشكلات التحسين البسيطة ، أي إذا

$x ^ *$ - النقطة الدنيا

$f ^ *$ ثم

$f '(x ^ *) = 0$

أين

$f '$ - مشتق

$f$ . يعتمد هذا المعيار على تقريب خطي.

$f (x) \ تقريبا f (x ^ *) + f '(x ^ *) (x-x ^ *).$

أقرب

$x$ ل

$x ^ *$ ، كلما كان هذا التقريب أكثر دقة. على الجانب الأيمن هو تعبير متى

$f '(x ^ *) \ neq 0$ ربما مثل المزيد

$f (x ^ *)$ أقل هو الجوهر الرئيسي للمعيار. في الحالة متعددة الأبعاد ، وبالمثل من التقريب الخطي

$f (x) \ تقريبا f (x ^ *) + \ nabla f (x ^ *) ^ T (x-x ^ *)$ (فيما يلي

$x ^ Ty = \ sum_ {i = 1} ^ nx_iy_i$ - المنتج القياسي القياسي ، ويرجع شكل الكتابة إلى حقيقة أن المنتج القياسي هو نفسه المنتج المصفوفي لمتجه صف بواسطة ناقل عمود) ، يتم الحصول على المعيار

$\ nabla f (x ^ *) = 0.$

القيمة

$\ nabla f (x ^ *)$ - التدرج الوظيفي

$f$ عند هذه النقطة

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

وتجدر الإشارة إلى أن هذه الشروط ضرورية ، لكنها ليست كافية ، وأبسط مثال يساوي 0

$f (x) = x ^ 2$ و

$f (x) = x ^ 3$

هذا المعيار كافٍ في حالة دالة محدبة ، ويرجع ذلك إلى حد كبير إلى هذا أنه كان من الممكن الحصول على العديد من النتائج لوظائف محدبة.

وظائف من الدرجة الثانية

$\ mathbb {R} ^ n$ هي دالة للنموذج

$f (x) = f (x_1، x_2، \ ldots، x_n) = \ frac {1} {2} \ sum_ {i، j = 1} ^ na_ {ij} x_ix_j- \ sum_ {i = 1} ^ n b_ix_i + c$

لتوفير مساحة (ولإزعاج أقل مع الفهارس) ، عادة ما تتم كتابة هذه الوظيفة في شكل مصفوفة:

$f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c،$

أين

$x = (x_1، \ ldots، x_n) ^ T$ ،

$b = (b_1، \ ldots، b_n) ^ T$ ،

$A$ هي مصفوفة عند التقاطع

$i$ سلاسل و

$j$ العمود هو القيمة

$\ frac {1} {2} (a_ {ij} + a_ {ji})$ (

$A$ اتضح أنها متناظرة - هذا أمر مهم). التالي. عند ذكر دالة تربيعية ، سأحصل على الوظيفة المذكورة أعلاه.

لماذا أتحدث عن هذا؟ والحقيقة أن الوظائف التربيعية مهمة في التحسين لسببين:

كما أنها تحدث عمليًا ، على سبيل المثال ، عند إنشاء انحدار خطي أقل مربعًا
التدرج للدالة التربيعية هي دالة خطية ، على وجه الخصوص للدالة أعلاه
$\ frac {\ جزئي} {\ جزئي x_i} f (x_1 ، x_2 ، \ ldots ، x_n) = a_ {ii} x_i + \ sum_ {j \ neq i} \ frac {1} {2} (a_ {ij } + a_ {ji}) x_j -b_i،$

أو في شكل مصفوفة
$\ nabla f (x) = Ax-b،$

وبالتالي فإن النظام $\ nabla f (x) = 0$ - النظام الخطي. نظام أبسط من الخطي غير موجود. الفكرة التي كنت أحاول الوصول إليها هي تحسين الوظيفة التربيعية - أبسط فئة من مشاكل التحسين . من ناحية أخرى ، حقيقة ذلك $\ nabla f (x ^ *) = 0$ - تتيح الشروط الدنيا اللازمة حل الأنظمة الخطية من خلال مشاكل التحسين. بعد ذلك بقليل سأحاول أن أقنعك أن هذا منطقي.

خصائص التدرج المفيدة

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

دعنا نحاول حل مشكلة أبسط: تم إعطاء النقطة

$x$ تجد نقطة

$\ bar {x}$ مثل هذا

$f (\ bar {x}) <f (x)$ . لنأخذ نقطة بجانب

$x$ مرة أخرى باستخدام التقريب الخطي

$f (\ bar {x}) \ تقريبا f (x) + \ nabla f (x) ^ T (\ bar {x} -x)$ . إذا أخذت

$\ bar {x} = x- \ alpha \ nabla f (x)$ ،

$\ alpha> 0$ ثم نحصل

$f (\ bar {x}) \ تقريبا f (x) - \ alpha \ | \ nabla f (x) \ | ^ 2 <f (x).$

وبالمثل ، إذا

$\ alpha <0$ ثم

$f (\ bar {x})$ سيكون أكثر

$f (x)$ (فيما يلي

$|| x || = \ sqrt {x_1 ^ 2 + x_2 ^ 2 + \ ldots + x_n ^ 2} ~$ ) مرة أخرى ، بما أننا استخدمنا التقريب ، فإن هذه الاعتبارات ستكون صحيحة فقط للصغار

$\ alpha$ . لتلخيص ما سبق ، إذا

$\ nabla f (x) \ neq 0$ ، ثم يشير التدرج إلى اتجاه أكبر زيادة محلية في الوظيفة .

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

لاحظ أنه بالنسبة لسطح محدد بواسطة معادلة الشكل

$f (x) = c$ ،

$\ nabla f (x)$ يضبط العادي (في عامة الناس - عمودي) على هذا السطح. لاحظ أيضًا أنه على الرغم من أن التدرج يظهر في اتجاه أكبر زيادة في الوظيفة ، فليس هناك ما يضمن أنه في الاتجاه المعاكس للتدرج ، يمكنك العثور على الحد الأدنى (على سبيل المثال ، الصورة اليسرى).

أصل التدرج

لم يتبق سوى خطوة صغيرة على طريقة نزول التدرج الأساسية: تعلمنا من هذه النقطة

$x$ الحصول على نقطة

$\ bar {x}$ مع قيمة دالة أقل

$f$ . ما الذي يمنعنا من تكرار ذلك عدة مرات؟ في الواقع ، هذا هو أصل التدرج: نبني التسلسل

$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k).$

القيمة

$\ alpha_k$ يسمى حجم الخطوة (في التعلم الآلي - سرعة التعلم ). بضع كلمات حول الاختيار

$\ alpha_k$ : إذا

$\ alpha_k$ - صغير جداً ، يتغير التسلسل ببطء ، مما يجعل الخوارزمية ليست فعالة للغاية ؛ إذا

$\ alpha_k$ كبير جدًا ، ثم يصبح التقريب الخطي رديئًا ، وربما حتى غير صحيح. من الناحية العملية ، غالبًا ما يتم اختيار حجم الخطوة تجريبيًا ؛ من الناحية النظرية ، عادة ما يتم افتراض تدرج Lipschitz ، أي إذا

$\ | \ nabla f (x) - \ nabla f (y) \ | \ leq L \ | x-y \ |$

للجميع

$x، y$ ثم

$\ alpha_k <\ frac {2} {L}$ انخفاض الضمانات

$f (x_k)$ .

تحليل الدوال التربيعية

إذا

$A$ هي مصفوفة عكسية متماثلة ،

$Ax ^ * = b$ ثم للدالة التربيعية

$f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c$ نقطة

$x ^ *$ هي الحد الأدنى ( UPD . شريطة أن يكون هذا الحد الأدنى موجودًا على الإطلاق -

$f$ لا يقترب من

$- \ infty$ القيم فقط إذا

$A$ إيجابي محدد) ، وطريقة هبوط التدرج يمكننا الحصول على ما يلي

$x_ {k + 1} -x ^ * = x_k- \ alpha_k \ nabla f (x_k) -x ^ * = x_k- \ alpha_k (Ax_k-b) -x ^ * =$

$(x_k-x ^ *) - \ alpha_kA (x_k-x ^ *) = (I- \ alpha_k A) (x_k-x ^ *) ،$

أين

$I$ هل مصفوفة الهوية ، أي

$Ix = x$ للجميع

$x$ . إذا

$\ alpha_k \ equiv \ alpha$ سوف يتحول

$\ | x_ {k} -x ^ * \ | = \ | (I- \ alpha A) ^ k (x_0-x ^ *) \ | \ leq \ | I- \ alpha A \ | ^ k \ | x_0 -x ^ * \ |.$

التعبير على اليسار هو المسافة من التقريب الذي تم الحصول عليه في الخطوة

$k$ نزول التدرج إلى الحد الأدنى ، على اليمين - تعبير عن النموذج

$\ lambda ^ k \ beta$ الذي يتحول إلى صفر إذا

$| \ lambda | <1$ (الحالة التي كتبت عنها

$\ alpha$ في الفقرة السابقة ، هذا بالضبط ما يضمن). يضمن هذا التقدير الأساسي تقارب أصل التدرج.

تعديلات نزول التدرج

الآن أود أن أتحدث قليلاً عن التعديلات المستخدمة بشكل شائع من أصل متدرج ، وبشكل أساسي ما يسمى

طرق التدرج بالقصور الذاتي أو المتسارع

يتم التعبير عن جميع طرق هذه الفئة على النحو التالي

$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k) + \ beta_k (x_k-x_ {k-1}).$

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

فهي لا تُعقِّد عمليا أصل التدرج المعتاد في الخطة الحسابية.
مع الاختيار الدقيق $\ alpha_k ، \ beta_k$ هذه الطرق هي ترتيب من حيث الحجم أسرع من نزول التدرج العادي حتى مع خطوة مختارة على النحو الأمثل.

ظهرت واحدة من أولى هذه الطرق في منتصف القرن العشرين وكانت تسمى طريقة الكرة الثقيلة ، والتي تنقل طبيعة القصور الذاتي للطريقة: في هذه الطريقة

$\ alpha_k ، \ beta_k$ بغض النظر عن

$k$ ويتم اختيارها بعناية اعتمادًا على الوظيفة الموضوعية. من الجدير بالذكر أن

$\ alpha_k$ قد يكون أي شيء ولكن

$\ beta_k$ - عادة أقل بقليل من واحد .

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

طريقة Chebyshev

نعم ، نعم ، اخترع Chebyshev الطريقة الأولى من هذا النوع لحل أنظمة المعادلات الخطية. في مرحلة ما من تحليل أصل التدرج ، تم الحصول على المساواة التالية

$x_ {k + 1} -x ^ * = (I- \ alpha_k A) (x_k-x ^ *) = \ ldots =$

$(I- \ alpha_kA) (I- \ alpha_ {k-1} A) \ ldots (I- \ alpha_1A) (x_0-x ^ *) = P_k (A) (x_0-x ^ *) ،$

أين

$P_k$ بعض الحدود كثير درجة

$k$ . لماذا لا تحاول التقاط

$\ alpha_k$ لذلك

$P_k (A) (x_0-x ^ *)$ هل كان أصغر؟ عقدة واحدة من كثيرات الحدود العالمية التي تنحرف عن الصفر هي كثيرة الحدود Chebyshev. تتكون طريقة Chebyshev بشكل أساسي من اختيار معلمات النسب بحيث

$P_k$ كان متعدد الحدود لشيبيشيف. هناك مشكلة صغيرة حقًا: بالنسبة إلى الانحدار الطبيعي للتدرج ، فهذا ببساطة غير ممكن. ومع ذلك ، بالنسبة لطرق القصور الذاتي ، هذا ممكن. هذا يرجع بشكل رئيسي إلى حقيقة أن كثيرات حدود Chebyshev تفي بعلاقة التكرار من الدرجة الثانية

$T_ {n + 1} (x) = 2xT_n (x) -T_ {n-1} (x)،$

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

$\ alpha_k ، \ beta_k$ لا يعتمد عليها

$k$ ولا حجم المساحة

$n$ .

طريقة التدرج المترافقة

حقيقة أخرى مثيرة للاهتمام ومهمة للغاية (نتيجة لنظرية هاميلتون كايلي): لأي مصفوفة مربعة

$A$ الحجم

$n \ مرات n$ هناك كثيرات الحدود

$P$ درجة لا أكثر

$n$ من أجله

$P (A) = 0$ . لماذا هذا مثير للاهتمام؟ الأمر كله يتعلق بنفس المساواة

$x_ {k + 1} -x ^ * = P_k (A) (x_0-x ^ *).$

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

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

يحتوي تكرار واحد من أصل التدرج (بدون مراعاة حسابات المعلمات) على عملية ضرب مصفوفة واحدة بواسطة متجه وإضافات 2-3 متجه
يتطلب حساب المعلمات أيضًا مضاعفة مصفوفة 1-2 بواسطة المتجه ، و 2-3 ضرب ناقلات متجهية حسب المتجه ، والعديد من الإضافات للمتجهات.

إن أصعب شيء في الخطة الحسابية هو مضاعفة المصفوفة بواسطة ناقل ، وعادة ما يتم ذلك في الوقت المناسب

$\ mathcal {O} (n ^ 2)$ ومع ذلك ، من أجل تنفيذ خاص ، يمكن القيام بذلك

$\ mathcal {O} (م)$ أين

$م$ - عدد العناصر غير الصفرية في

$A$ . بالنظر إلى تقارب طريقة التدرج المترافق ، لا يزيد عن

$n$ التكرارات تحصل على التعقيد العام للخوارزمية

$\ mathcal {O} (nm)$ ، وهو ليس أسوأ في جميع الحالات

$\ mathcal {O} (n ^ 3)$ لطريقة Gauss أو Cholesky ، ولكن أفضل بكثير إذا

$m << n ^ 2$ هذا ليس نادرا جدا.

طريقة التدرج المتقارن تعمل أيضًا بشكل جيد إذا

$f$ ليست دالة تربيعية ، لكنها لا تتقارب في عدد محدود من الخطوات وغالبًا ما تتطلب تعديلات إضافية صغيرة

طريقة نيستروف

بالنسبة لمجتمعات التحسين الرياضي وتعلم الآلة ، كان اسم "نيستروف" منذ فترة طويلة اسمًا مألوفًا. في الثمانينيات من القرن الماضي ، Yu.E. جاء نيستروف بنسخة مثيرة للاهتمام من طريقة القصور الذاتي ، والتي لها الشكل

$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k + \ beta_k (x_k-x_ {k-1})) + \ beta_k (x_k-x_ {k-1}) ،$

لا يعني أي حساب معقد

$\ alpha_k ، \ beta_k$ كما هو الحال في طريقة التدرج المترافق ، بشكل عام ، فإن سلوك الطريقة مشابه لطريقة الكرة الثقيلة ، ولكن تقاربها عادة ما يكون أكثر موثوقية من الناحية النظرية والممارسة.

أصل التدرج العشوائي

الاختلاف الرسمي الوحيد من أصل التدرج المعتاد هو استخدام دالة بدلاً من التدرج

$g (x، \ theta)$ مثل هذا

$E_ \ theta g (x، \ theta) = \ nabla f (x)$ (

$E_ \ theta$ - التوقع العشوائي

$\ theta$ ) ، لذا فإن شكل التدرج العشوائي له الشكل

$x_ {k + 1} = x_k- \ alpha_kg (x_k، \ theta_k).$

$\ theta_k$ - هذه بعض المعلمات العشوائية التي لا نؤثر عليها ، ولكن في نفس الوقت في المتوسط نذهب ضد التدرج. كمثال ، ضع في الاعتبار الوظائف

$f (x) = \ frac {1} {2m} \ sum_ {j = 1} ^ m \ | x-y_j \ | ^ 2، ~~ \ nabla f (x) = \ frac {1} {m} \ sum_ {j = 1} ^ m (x-y_j)$

$g (x، i) = x-y_i.$

إذا

$i$ يأخذ القيم

$1 ، \ ldots ، م$ على الأرجح متوسط فقط

$g$ متدرج

$f$ . يشير هذا المثال أيضًا إلى ما يلي: تعقيد حساب التدرج في

$م$ مرات أكثر من التعقيد الحسابي

$g$ . هذا يسمح بالهبوط التدرج العشوائي في نفس الوقت

$م$ مرات تكرار أكثر. على الرغم من حقيقة أن هبوط التدرج العشوائي يتقارب عادةً بشكل أبطأ من المعتاد ، نظرًا لهذه الزيادة الكبيرة في عدد التكرارات ، فمن الممكن تحسين معدل التقارب لكل وحدة زمنية. على حد علمي ، في الوقت الحالي هو التدرج العشوائي هو الطريقة الأساسية لتدريب معظم الشبكات العصبية ، التي يتم تنفيذها في جميع مكتبات ML الرئيسية: tensorflow ، torch ، caffe ، CNTK ، إلخ.

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

$g$ .

نزول التدرج الفرعي

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

$f$ محدبة إذا وفقط إذا

$f (y) \ geq f (x) + \ nabla f (x) ^ T (y-x)$ للجميع

$x، y$ . اتضح أن الدالة المحدبة لا يجب أن تكون قابلة للتمييز ، ولكن لأي نقطة

$x$ بالتأكيد هناك مثل هذا ناقلات

$g$ ذلك

$f (y) \ geq f (x) + g ^ T (y-x)$ للجميع

$y$ . مثل هذا ناقلات

$g$ تسمى عادة subgradient

$f$ عند هذه النقطة

$x$ ، مجموعة من جميع subgradients إلى نقاط

$x$ دعا فرعي

$x$ والدلالة

$\ جزئي f (x)$ (على الرغم من التسمية - لا علاقة لها بالمشتقات الجزئية). في حالة أحادية البعد

$g$ هو رقم ، والخاصية أعلاه تعني ببساطة أن الرسم البياني

$f$ تقع فوق الخط المار

$(x، f (x))$ ومنحدر

$g$ (انظر الصور أدناه). ألاحظ أنه يمكن أن يكون هناك العديد من subgradients لنقطة واحدة ، حتى عدد لا نهائي.

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

$ReLU (x) = \ max (0، x)$ إنهم يحبون استخدامه لمجرد أن التدريب أسرع معه (وهذا ، بالمناسبة ، مثال على وظيفة غير محدبة غير قابلة للتمييز يتم فيها تطبيق نزول التدرج (الفرعي) بنجاح. الوظيفة نفسها

$Relu$ محدبة ولكن تحتوي على شبكة عصبية متعددة الطبقات

$Relu$ وغير محدبة وغير قابلة للتمييز). كمثال ، للدالة

$f (x) = | x |$ يتم حساب الاختلاف الفرعي ببساطة شديدة

$\ جزئي f (x) = \ تبدأ {حالات} 1 ، & x> 0 ، \\ -1 ، & x <0 ، \\ [-1 ، 1] ، و x = 0. \ end {cases}$

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

$f (x) = | x |$ . حتى غياب المشتق عند نقطة واحدة يكسر التقارب:

لنفترض أننا بدأنا من النقطة $x_0$ .
خطوة نزول التدرج الفرعي:
$x_ {k + 1} = \ start {cases} x_ {k} -1، & x> 0، \\ x_k + 1، & x <0، \\ ؟؟؟ & x = 0. \ end {cases}$
إذا $x_0> 0$ ثم الخطوات القليلة الأولى سنطرح واحدة ، إذا $x_0 <0$ ثم أضف. بطريقة أو بأخرى ، سنجد أنفسنا في مرحلة ما في الفاصل الزمني $[0، 1)$ الذي نصل إليه $[- 1 ، 0)$ ، ثم سنقفز بين نقطتين من هذه الفواصل.

من الناحية النظرية ، بالنسبة للنسب دون التدرج ، يوصى باتخاذ سلسلة من الخطوات

$\ alpha_k = \ frac {1} {(k + 1) ^ c}.$

أين

$c$ عادة

$1$ أو

$\ frac {1} {2}$ . عمليا ، كثيرا ما رأيت خطوات ناجحة

$\ alpha_k = e ^ {- ck}$ ، على الرغم من هذه الخطوات بشكل عام لن يكون هناك تقارب.

الطرق القريبة

لسوء الحظ ، لا أعرف ترجمة جيدة لـ "القريبة" في سياق التحسين ، ولهذا السبب سأطلق على هذه الطريقة فقط. ظهرت الأساليب القريبة كتعميم لطرق التدرج الإسقاطي. الفكرة بسيطة للغاية: إذا كانت هناك وظيفة

$f$ ممثلة كمجموع

$f (x) = \ varphi (x) + h (x)$ أين

$\ varphi$ هي دالة محدبة مختلفة

$h (x)$ - محدب ، يوجد فيه عامل داني خاص

$prox_h (x)$ (في هذه المقالة سأقتصر على الأمثلة فقط ، لن أصف بعبارات عامة) ، ثم خصائص التقارب من أصل التدرج ل

$\ varphi$ تبقى ومن أجل التدرج

$f$ إذا قام بعد كل تكرار بتطبيق هذا العامل القريب للنقطة الحالية

$x_k$ وبعبارة أخرى ، يبدو الشكل العام للطريقة القريبة كالتالي:

$x_ {k + 1} = الوكيل _ {\ alpha_kh} (x_k- \ alpha_k \ nabla \ varphi (x_k))$

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

$h (x)$ - دالة المؤشر لمجموعة محدبة $\ mathcal {K}$ هذا هو
$h (x) = \ start {cases} 0 و & x \ in \ mathcal {K} و \\ + \ infty و x \ notin \ mathcal {K}. \\ \ end {cases}$

في هذه الحالة $الوكيل _ {\ alpha_kh} (x)$ هو إسقاط على المجموعة $\ mathcal {K}$ ، أي "الأقرب إلى $x$ نقطة محددة $\ mathcal {K}$ ". وبالتالي ، فإننا نقصر نزول التدرج على المجموعة فقط $\ mathcal {K}$ ، مما يسمح لنا بحل المشاكل مع القيود. لسوء الحظ ، يمكن أن يكون حساب الإسقاط في الحالة العامة أكثر صعوبة ، لذلك يتم استخدام هذه الطريقة عادة إذا كانت القيود بسيطة ، على سبيل المثال ، ما يسمى قيود الصندوق: لكل إحداثي
$l_i \ leq x_i \ leq r_i$
$h (x) = \ lambda \ | x \ | _1 = \ lambda \ sum_ {i = 1} ^ n | x_i |$ - $\ ell_1$ -التنظيم. إنهم يحبون إضافة هذا المصطلح إلى مشاكل التحسين في التعلم الآلي لتجنب إعادة التدريب. يميل التنظيم من هذا النوع أيضًا إلى إبطال المكونات الأقل أهمية. بالنسبة لهذه الوظيفة ، يكون للعامل القريب الشكل (يتم وصف تعبير إحداثيات واحدة أدناه):
$[الوكيل _ {\ alpha h} (x)] _ i = \ start {cases} x_i \ alpha و & x_i> \ alpha و \\ x_i + \ alpha و & x_i <- \ alpha و \\ 0 و x_i \ في [- \ alpha ، \ alpha] ، \ end {cases}$

وهو سهل الحساب.

الخلاصة

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

الأدب المستخدم / الموصى به

بويد. S ، Vandenberghe L. محدب التحسين
Shewchuk JR مقدمة لطريقة التدرج المترافق بدون ألم مؤلم
نظرية التحسين Bertsekas DP

Nesterov Yu. طرق التحسين المحدبة
Gasnikov A.V. منحدر عالمي متدرج

نظرة عامة على طرق التدرج في مشاكل التحسين الرياضية