الهبوط المنسق

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 16 صور
الموسوعة الحرة

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

وصف

تعتمد طريقة الهبوط الإحداثي على فكرة أن تقليل دالة متعددة المتغيراتF(x){\displaystyle F(\mathbf {x} )}يمكن تحقيق ذلك بتقليلها على طول اتجاه واحد في كل مرة، أي حل مسائل التحسين أحادية المتغير (أو على الأقل مسائل أبسط بكثير) في حلقة تكرارية. [ 1 ] في أبسط حالات انحدار الإحداثيات الدوري ، يتم التكرار بشكل دوري عبر الاتجاهات، اتجاهًا تلو الآخر، مع تقليل دالة الهدف بالنسبة لكل اتجاه إحداثي على حدة. أي، البدء بقيم المتغيرات الأولية.

x0=(x10،...،xن0){\displaystyle \mathbf {x} ^{0}=(x_{1}^{0},\ldots ,x_{n}^{0})}،

دائريك+1{\displaystyle k+1}يُعرّفxك+1{\displaystyle \mathbf {x} ^{k+1}}منxك{\displaystyle \mathbf {x} ^{k}}من خلال حل مسائل التحسين أحادية المتغير بشكل متكرر

xأناك+1=أرزمأنانy∈Rو(x1ك+1،...،xأنا-1ك+1،y،xأنا+1ك،...،xنك){\displaystyle x_{i}^{k+1}={\underset {y\in \mathbb {R} }{\operatorname {arg\,min} }}\;f(x_{1}^{k+1},\dots ,x_{i-1}^{k+1},y,x_{i+1}^{k},\dots ,x_{n}^{k})}[ 2 ]

لكل متغيرxأنا{\displaystyle x_{i}}لx{\displaystyle \mathbf {x} }، لأنا{\displaystyle i}من 1 إلىن{\displaystyle n}.

وهكذا، يبدأ المرء بتخمين أوليx0{\displaystyle \mathbf {x} ^{0}}كحد أدنى محلي لـF{\displaystyle F}ويحصل على تسلسل x0،x1،x2،...{\displaystyle \mathbf {x} ^{0},\mathbf {x} ^{1},\mathbf {x} ^{2},\dots }بشكل متكرر.

من خلال إجراء بحث خطي في كل تكرار، يحصل المرء تلقائيًا على

F(x0)≥F(x1)≥F(x2)≥....{\displaystyle F(\mathbf {x} ^{0})\geq F(\mathbf {x} ^{1})\geq F(\mathbf {x} ^{2})\geq \dots .}

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

يوضح الشكل أدناه هذه العملية.

حالة قابلة للتفاضل

في حالة الدالة القابلة للتفاضل باستمرار F ، يمكن رسم خوارزمية هبوط الإحداثيات على النحو التالي: [ 1 ]

  • اختر متجه المعلمات الأولي x .
  • حتى يتم الوصول إلى التقارب، أو لعدد ثابت من التكرارات:
    • اختر فهرسًا i من 1 إلى n .
    • اختر حجم الخطوة α .
    • قم بتحديث x i إلى x i − α ⁠ ∂ F / ∂ x i ⁠ ( x ) .

يمكن اختيار حجم الخطوة بطرق مختلفة، على سبيل المثال، عن طريق إيجاد القيمة الصغرى الدقيقة للدالة f ( x i ) = F ( أي F مع تثبيت جميع المتغيرات باستثناء x i )، أو عن طريق معايير البحث الخطي التقليدية. [ 1 ]

القيود

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

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

التطبيقات

تحظى خوارزميات الانحدار الإحداثي بشعبية واسعة بين الممارسين نظرًا لبساطتها، إلا أن هذه الخاصية نفسها دفعت باحثي التحسين إلى تجاهلها إلى حد كبير لصالح طرق أكثر تعقيدًا. [ 1 ] كان أحد التطبيقات المبكرة لتحسين الانحدار الإحداثي في ​​مجال التصوير المقطعي المحوسب [ 7 ] ، حيث وُجد أنها تتميز بتقارب سريع [ 8 ] ، واستُخدمت لاحقًا في إعادة بناء صور الأشعة المقطعية الحلزونية متعددة الشرائح في المجال السريري. [ 9 ] كما طُبقت خوارزمية الانحدار الإحداثي الدوري (CCD) في التنبؤ ببنية البروتين. [ 10 ] علاوة على ذلك، ازداد الاهتمام باستخدام الانحدار الإحداثي مع ظهور المشكلات واسعة النطاق في مجال التعلم الآلي ، حيث أظهر الانحدار الإحداثي قدرة تنافسية على الطرق الأخرى عند تطبيقه على مشكلات مثل تدريب آلات المتجهات الداعمة الخطية [ 11 ] (انظر LIBLINEAR ) وتحليل المصفوفات غير السالبة . [ 12 ] إنها جذابة للمسائل التي يكون فيها حساب التدرجات غير عملي، ربما لأن البيانات المطلوبة للقيام بذلك موزعة عبر شبكات الحاسوب. [ 13 ]

انظر أيضاً

مراجع

  1. 1 2 3 4 رايت، ستيفن ج. (2015). "خوارزميات التدرج الإحداثي". البرمجة الرياضية . 151 (1): 3-34 . arXiv : 1502.04759 . doi : 10.1007/s10107-015-0892-3 . S2CID 15284973 . 
  2. ↑ غوردون، جيف؛ تيبشيراني، رايان (خريف 2012). "الانحدار الإحداثي" (ملف PDF) . التحسين 10-725 / 36-725 . جامعة كارنيجي ميلون.
  3. ↑ سبال، جيه سي (2012). "عملية الميزان الدورية للتحسين والتحديد". مجلة نظرية التحسين وتطبيقاتها . 154 (1): 187-208 . doi : 10.1007/s10957-012-0001-1 . S2CID 7795605 . 
  4. ↑ Zheng, J.; Saquib, SS; Sauer, K.; Bouman, CA (2000-10-01). "خوارزميات التصوير المقطعي البايزي المتوازية ذات التقارب السريع والمضمون". معاملات IEEE في معالجة الصور . 9 (10): 1745-1759 . Bibcode : 2000ITIP....9.1745Z . CiteSeerX 10.1.1.34.4282 . doi : 10.1109/83.869186 . ISSN 1057-7149 . PMID 18262913 .   
  5. ↑ فيسلر، جيه إيه؛ فيكارو، إي بي؛ كلينثورن، إن إتش؛ لانج، كيه. (1997-04-01). "خوارزميات الصعود الإحداثي المجمع لإعادة بناء صور الإرسال باحتمالية معاقبة". معاملات IEEE في التصوير الطبي . 16 (2): 166-175 . doi : 10.1109/42.563662 . hdl : 2027.42/86021 . ISSN 0278-0062 . PMID 9101326. S2CID 1523517 .   
  6. ↑ وانغ، شياو؛ سابني، أميت؛ كيسنر، شيرمان؛ راغوناثان، أناند؛ بومان، تشارلز؛ ميدكيف، صموئيل (2016-01-01). "إعادة بناء الصور باستخدام نموذج عالي الأداء". وقائع ندوة ACM SIGPLAN الحادية والعشرين حول مبادئ وممارسات البرمجة المتوازية . PPoPP '16. نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 2:1-2:12. doi : 10.1145/2851141.2851163 . ISBN  9781450340922. S2CID 16569156 . 
  7. ↑ ساور، كين؛ بومان، تشارلز (فبراير 1993). "استراتيجية تحديث محلية لإعادة البناء التكراري من الإسقاطات" (ملف PDF) . معاملات IEEE في معالجة الإشارات . 41 (2): 534-548 . Bibcode : 1993ITSP...41..534S . CiteSeerX 10.1.1.135.6045 . doi : 10.1109/78.193196 . 
  8. ↑ يو، تشو؛ تيبو، جان بابتيست؛ بومان، تشارلز؛ ساور، كين؛ هسيه، جيانغ (يناير 2011). "إعادة بناء سريعة للتصوير المقطعي المحوسب بالأشعة السينية باستخدام نموذج مُحسَّن بتقنية ICD غير المتجانسة مكانيًا" (ملف PDF) . مجلة IEEE لمعالجة الصور . 20 (1): 161-175 . Bibcode : 2011ITIP...20..161Y . doi : 10.1109/TIP.2010.2058811 . PMID: 20643609. S2CID : 9315957 .  
  9. ↑ تيبو، جان بابتيست؛ ساور، كين؛ بومان، تشارلز؛ هسيه، جيانغ (نوفمبر 2007). "نهج إحصائي ثلاثي الأبعاد لتحسين جودة الصورة في التصوير المقطعي الحلزوني متعدد الشرائح" (ملف PDF) . الفيزياء الطبية . 34 (11): 4526-4544 . Bibcode : 2007MedPh..34.4526T . doi : 10.1118/1.2789499 . PMID 18072519 . 
  10. ↑ كانوتيسكو، أ.أ.؛ دنبراك، ر.ل. (2003). " النزول الإحداثي الدوري: خوارزمية روبوتية لإغلاق حلقات البروتين" . علم البروتين . 12 (5): 963-972 . doi : 10.1110/ps.0242703 . PMC 2323867. PMID 12717019 .  
  11. ↑ هسيه، سي جيه؛ تشانغ، كيه دبليو؛ لين، سي جيه؛ كيرثي، إس إس؛ سونداراراجان، إس. (2008). "طريقة هبوط الإحداثيات المزدوجة لآلة المتجهات الداعمة الخطية واسعة النطاق" (ملف PDF) . وقائع المؤتمر الدولي الخامس والعشرين للتعلم الآلي - ICML '08 . ص 408. doi : 10.1145/1390156.1390208 . ISBN  9781605582054. S2CID 7880266 . 
  12. ↑ هسيه، سي جيه؛ ديلون، آي إس (2011). طرق التدرج الإحداثي السريع مع اختيار المتغيرات لتحليل المصفوفات غير السالبة (PDF) . وقائع المؤتمر الدولي السابع عشر لجمعية ACM SIGKDD حول اكتشاف المعرفة واستخراج البيانات - KDD '11. ص 1064. doi : 10.1145/2020408.2020577 . ISBN  9781450308137.
  13. ↑ نيستيروف، يوري (2012). "كفاءة طرق التدرج الإحداثي في ​​مسائل التحسين واسعة النطاق" (ملف PDF) . مجلة SIAM للتحسين ، 22 (2): 341-362 . CiteSeerX 10.1.1.332.3336 . doi : 10.1137/100802001 . 
  • بيزديك، جيه سي؛ هاثاواي، آر جيه؛ هوارد، آر إي؛ ويلسون، سي إيه؛ ويندهام، إم بي (1987)، "تحليل التقارب المحلي لنسخة المتغيرات المجمعة من خوارزمية التدرج الإحداثي"، مجلة نظرية التطبيقات الأمثلية ، المجلد  54، العدد  3، دار نشر كلوير الأكاديمية/بلينوم، الصفحات 471-477 ، doi : 10.1007/BF00940196 ، S2CID 120052975  
  • بيرتسيكاس، ديمتري ب. (1999). البرمجة غير الخطية، الطبعة الثانية. أثينا ساينتيفيك، بلمونت، ماساتشوستس. ISBN 1-886529-00-0.
  • لو، تشيكوان؛ تسينغ، ب. (1992)، "حول تقارب طريقة الانحدار الإحداثي للتصغير التفاضلي المحدب"، مجلة نظرية التطبيقات الأمثلية ، المجلد  72، العدد  1، دار نشر كلوير الأكاديمية/بلينوم، الصفحات 7-35 ، doi : 10.1007/BF00939948 ، hdl : 1721.1/3164 ، S2CID 121091844  .
  • وو، تونغ تونغ؛ لانج، كينيث (2008)، "خوارزميات انحدار الإحداثيات لانحدار لاسّو المعاقب"، حوليات الإحصاء التطبيقي ، المجلد  2، العدد  1، معهد الإحصاء الرياضي، الصفحات 224-244 ، arXiv : 0803.3876 ، doi : 10.1214/07-AOAS147 ، S2CID 16350311  .
  • ريشتاريك، بيتر؛ تاكاك، مارتن (أبريل 2011)، "تعقيد التكرار لطرق الهبوط الإحداثي العشوائي للكتل لتقليل دالة مركبة"، البرمجة الرياضية ، المجلد  144، العدد 1-2 ، سبرينغر، الصفحات 1-38 ، arXiv : 1107.2848 ، doi : 10.1007/s10107-012-0614-z ، S2CID 16816638   .
  • ريشتاريك، بيتر؛ تاكاك، مارتن (ديسمبر 2012)، "طرق الانحدار الإحداثي المتوازي لتحسين البيانات الضخمة"، ArXiv:1212.0873 ، arXiv : 1212.0873.