التحسين بالجبر الخطي

نزول التدرج

في الدرس السابق رأينا أن التدرج ∇f(x) يشير في اتجاه أشد صعود في دالة f. نتيجةً مباشرة لذلك: إذا أردنا تصغير f، فعلينا التحرك في الاتجاه المعاكس — أي في اتجاه سلبي التدرج −∇f. هذه الفكرة البسيطة هي جوهر نزول التدرج، الخوارزمية التي تقع في قلب تدريب الشبكات العصبية وتحسين النماذج الحديثة.

قاعدة تحديث نزول التدرج تأخذ الشكل التالي: من النقطة الحالية x_k، نحسب التدرج عندها، ثم نتخذ خطوة بحجم α (يُسمى معدل التعلم أو حجم الخطوة) في الاتجاه السالب:

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

التقارب يعتمد على طبيعة الدالة: للدوال المحدبة التربيعية، يتقارب نزول التدرج بمعدل هندسي — كل تكرار يُقلص المسافة إلى الحد الأدنى بعامل ثابت. وبدقة أكبر، من أجل f(x) = ½xᵀAx − bᵀx مع A موجبة التعريف، يحقق الخطأ عند الخطوة k الحد ‖x_k − x*‖ ≤ ((λ_max − λ_min)/(λ_max + λ_min))^k ‖x_0 − x*‖. النسبة κ = λ_max/λ_min هي رقم تكييف A: كلما كبر، أبطأ التقارب، ولا يُنجيك ضبط α مهما أحسنته. ولهذا تهمّ التهيئة المسبقة عمليًا — أي تحويل المسألة لتصغير κ. للدوال المحدبة العامة، يتقارب بمعدل O(1/k) حيث k عدد التكرارات. وللدوال غير المحدبة، يصل إلى نقطة حرجة (قد تكون حدًا أدنى محليًا، حدًا أقصى، أو نقطة سرج) وليس بالضرورة إلى الحد الأدنى العالمي.

ولا يلزم أن يكون α ثابتًا. في الدوال غير التربيعية يمكن تكييف حجم الخطوة في كل تكرار بـبحث خطي: بدلًا من تثبيت α، ابحث عن α_k الذي يُصغّر f(x_k − α∇f(x_k)) على طول اتجاه التدرج. أما في التعلم العميق فالبحث الخطي الدقيق مكلف جدًا، فيلجأ الممارسون إلى معدلات تعلم ثابتة مع جدول تخفيض، أو إلى الزخم (إضافة جزء من الخطوة السابقة إلى الحالية)، أو إلى طرق متكيّفة مثل Adam تقدّر حجم خطوة لكل معامل على حدة.

مشهد الخسارة

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

الدوال المحدبة لها مشهد خسارة "وادٍ واحد": أي نقطة حرجة هي الحد الأدنى العالمي، وأي خوارزمية تحسين محلية ستجد الحل الأمثل. الدوال غير المحدبة — مثل دوال الخسارة في الشبكات العصبية — لها مشاهد معقدة بحدود دنيا محلية متعددة، ونقاط سرج كثيرة، ومنحدرات حادة.

• الحد الأدنى العالمي: أصغر قيمة لـ f على كامل المجال. لا يوجد غيره للدوال المحدبة الصارمة.
• الحد الأدنى المحلي: نقطة أصغر من جميع النقاط المجاورة، لكن ربما لا الأصغر عالميًا.
• نقطة السرج: نقطة حرجة (∇f = 0) ليست حدًا أدنى ولا أقصى — تنحدر في بعض الاتجاهات وترتفع في أخرى. كثيرة في الشبكات العميقة.
• الانبعاج: منطقة مستوية تقريبًا يتباطأ فيها نزول التدرج. يمكن أن تُعيق التقارب لفترات طويلة.

رقم التكييف κ = λ_max / λ_min (نسبة أكبر قيمة ذاتية للهيسيان إلى أصغرها) يقيس مدى "استطالة" مشهد الخسارة. رقم التكييف الكبير (κ >> 1) يعني أن بعض الاتجاهات أشد انحدارًا بكثير من غيرها، مما يُبطئ نزول التدرج ويجعله يتذبذب في "الممرات الضيقة".

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

طريقة نيوتن

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

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

لكن الثمن باهظ: حساب الهيسيان H يكلف O(n²) في الذاكرة وO(n³) في العمليات لكل تكرار (لحل نظام نيوتن H δ = −∇f عبر تحليل تشولسكي). هذا يجعل طريقة نيوتن الكاملة غير عملية للمسائل ذات الأبعاد العالية: عند n = 10⁶، وهو حجم شبكة عصبية عادية، الأمر مستحيل تمامًا. وهناك عقبة ثانية في المسائل غير المحدبة: إذا كان H غير محدد الإشارة، فقد يشير اتجاه نيوتن صعودًا لا هبوطًا، ولذلك يلزم تعديل الهيسيان — إضافة λI لإجباره على أن يكون موجب التعريف. لهذا السبب تُستخدم في التطبيقات الهندسية طرق شبه-نيوتنية مثل L-BFGS التي تُقرّب H⁻¹ من فروق التدرجات بين التكرارات وتُحقّق تقاربًا فوق-خطيًا دون أن تُكوّن الهيسيان صراحةً أبدًا. ومع ذلك تبقى طريقة نيوتن المعيار الذهبي مفهوميًا: كل خوارزمية تحسين متقدمة يمكن قراءتها كتقريب لها أو تعديل عليها.

الإيجابية المحددة والتحدب

من المفاهيم الجوهرية في التحسين: ما هي العلاقة بين إيجابية الهيسيان والتحدب الهندسي للدالة؟ الجواب أنهما مترادفان للدوال الملساء: دالة قابلة للتفاضل مرتين f محدبة إذا وفقط إذا كان هيسيانها H(x) موجب شبه التعريف في كل نقطة x.

التحدب الهندسي يعني أن القطعة المستقيمة بين أي نقطتين تقع فوق (أو عليه) الرسم البياني للدالة. رياضيًا، f محدبة إذا كان لكل x, y في المجال ولكل λ ∈ [0, 1]:

الأهمية العملية للتحدب في التحسين هائلة:

• الحد الأدنى المحلي = العالمي: للدوال المحدبة، أي حد أدنى محلي هو بالضرورة الحد الأدنى العالمي. هذا يعني أن نزول التدرج أو طريقة نيوتن ستجد الحل الأمثل بغض النظر عن نقطة البداية.
• شرط كافٍ لاختبار الرتبة الثانية: إذا كان ∇f(x*) = 0 وH(x*) موجبًا التعريف، فإن x* حد أدنى محلي صارم (وعالمي إذا كانت f محدبة).
• ضمانات التقارب: للدوال المحدبة، يتمتع نزول التدرج بضمانات تقارب صارمة وبمعدلات محددة.

ومن الدوال المحدبة المهمة في الهندسة: أي معيار ‖·‖، والمعايير المربّعة ‖Ax − b‖²، وlog-sum-exp المستخدمة في الانحدار اللوجستي، وسالب لوغاريتم الأرجحية لتوزيعات العائلة الأسية. ثم إن مجموع دالتين محدبتين محدب، والتركيب f(Ax + b) محدب متى كانت f محدبة، وأكبر دالتين محدبتين محدب أيضًا. هذه خصائص إغلاق تجعلك تتعرف على التحدب في أهداف معقدة دون أن تحسب هيسيانًا واحدًا.

الأشكال التربيعية وتحسينها

الأشكال التربيعية — الدوال من الشكل f(x) = xᵀAx + bᵀx + c حيث A مصفوفة n × n، b متجه، c ثابت — هي الفئة الأكثر دراسةً في تحسين الجبر الخطي. تظهر مباشرةً في:

• المربعات الصغرى: تصغير ‖Ax − b‖² = xᵀAᵀAx − 2bᵀAx + bᵀb
• التحليل التربيعي: الطاقة في الأنظمة الميكانيكية والكهربائية
• تقدير الإحصاء الباييزي: دوال اللوغاريتم الأرجح لتوزيع غاوس متعدد الأبعاد
• توسيع تايلور من الرتبة الثانية: أي دالة ملساء تُشبه شكلًا تربيعيًا محليًا

لتحسين الشكل التربيعي f(x) = xᵀAx + bᵀx + c مع افتراض A متماثلة، نساوي التدرج بالصفر ونحل النظام الخطي الناتج:

الأشكال التربيعية أمثلة مثالية لطريقة نيوتن: لأن f تربيعية بالفعل، تتقارب طريقة نيوتن في خطوة واحدة بالضبط. الهيسيان ثابت (لا يتغير مع x) وهو H = 2A، وخطوة نيوتن تُعطي مباشرةً الحل الأمثل.

والصلة بالأنظمة الخطية أعمق من مجرد تشابه في الصيغة: حل نظام خطي موجب التعريف Ax = b وتصغير الشكل التربيعي f(x) = ½xᵀAx − bᵀx مسألتان مكافئتان تمامًا. لكن حل النظام مباشرةً يكلف O(n³). لذلك في التطبيقات الضخمة (مثل حل أنظمة طاقة أو نماذج مناخ)، تُستخدم طريقة التدرج المترافق (Conjugate Gradient) التي تستغل هذه الثنائية: هي في الوقت نفسه خوارزمية جبر خطي (تحل Ax = b) وخوارزمية تحسين (تُصغّر f). وهي مثالية بمعنى محدد: تُصغّر f على فضاءات كريلوف الفرعية، فتتقارب في n خطوة على الأكثر لمصفوفة n × n — وفي الممارسة تتقارب في أقل من ذلك بكثير للمصفوفات جيدة التكييف.

مثال انحدار ريدج

انحدار ريدج (التنظيم بمعيار ℓ₂) يوضح التحسين التربيعي على أكمل وجه. الهدف هو f(w) = ‖Xw − y‖² + λ‖w‖² = wᵀ(XᵀX + λI)w − 2yᵀXw + yᵀy، أي A = XᵀX + λI و b = −2Xᵀy. وحدّ التنظيم λ‖w‖² يضيف λ إلى كل قيمة ذاتية من قيم XᵀX، فيضمن أن A موجبة التعريف حتى لو كانت X ناقصة الرتبة. والحل المغلق هو w* = (XᵀX + λI)⁻¹Xᵀy، أي المعادلات الطبيعية المنظَّمة. وحين λ → 0 نستعيد المربعات الصغرى العادية؛ وحين λ → ∞ نحصل على w* → 0، أي تنظيم مفرط أفرغ النموذج من محتواه. أما للمسائل ناقصة الرتبة فقد يُستخدم المعكوس الزائف بدلًا من التنظيم.

مضاعفات لاغرانج — المنظور الجبري

كثير من مسائل التحسين الواقعية تأتي مع قيود: صغّر f(x) بشرط g(x) = 0. صغّر استهلاك الطاقة بشرط معدل بيانات محدد؛ صغّر الوزن بشرط حمل إنشائي؛ صغّر تباين المحفظة wᵀΣw بشرط عائد متوقع معيّن (نموذج ماركويتز)؛ صغّر خطأ إعادة البناء بشرط أن يكون المتجه واحدي المعيار (كما في تحليل المركبات الرئيسية). في هذه المسائل، لا يمكن تجاهل القيود والتحسين بحرية.

تقنية مضاعفات لاغرانج تحوّل مسألة التحسين المقيّد إلى مسألة تحسين حر عبر إدخال متغيرات جديدة λ (المضاعفات) تُعاقب خرق القيد. والفكرة هندسية بحتة: عند الحل الأمثل المقيّد، يجب أن يكون تدرج الهدف تركيبًا خطيًا من تدرجات دوال القيد — وإلا لوُجد اتجاه مسموح يُنقص f ويبقى على سطح القيد في الوقت نفسه. وهذا الشرط الهندسي، ∇f = λᵀ∇g، هو بعينه شرط المثالية من الرتبة الأولى.

شروط KKT (كاروش-كوهن-تاكر) هي تعميم لشرط "التدرج الصفري" لمسائل التحسين المقيّد. وهي شروط ضرورية للمثالية تحت فرضيات انتظام معينة (مثل كون القيود متزنة):

• الاستواء التام (Stationarity): ∇f(x*) = λᵀ ∇g(x*) — تدرج الهدف هو تركيب خطي من تدرجات القيود
• الأهلية التكميلية (Complementary Slackness): λᵢ · gᵢ(x*) = 0 — كل مضاعف إما صفر أو قيده فعّال
• الجدوى الأصلية: g(x*) = 0 — القيد متحقق
• الجدوى الثنائية: λ ≥ 0 للقيود من نوع المتباينات (للقيود المتساوية λ حر)

في البرمجة التربيعية (تصغير شكل تربيعي مع قيود خطية)، تُعطي شروط KKT نظامًا خطيًا يمكن حله مباشرةً. فإذا كان القيد خطيًا g(x) = Cx − d، وكان الهدف f(x) = xᵀAx + bᵀx، فإن رصف شرطَي الاستواء والجدوى يعطي نظامًا خطيًا كتليًا:

[2A, Cᵀ؛ C, 0] [x؛ λ] = [−b؛ d]

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

مسائل القيم الذاتية كتحسين مقيّد

وهنا صلة جميلة بمسائل القيم الذاتية. خُذ المسألة: كبّر xᵀAx بشرط ‖x‖ = 1، أي هدف تربيعي على الكرة الواحدية. دالة لاغرانج هي ℒ(x, λ) = xᵀAx − λ(xᵀx − 1). ساوِ ∇_x ℒ = 2Ax − 2λx بالصفر فتحصل على Ax = λx — معادلة القيم الذاتية بعينها! أي أن أكبر قيمة لـ xᵀAx على الكرة الواحدية تساوي λ_max، أكبر قيمة ذاتية لـ A، وتتحقق عند المتجه الذاتي المقابل. هذا يبرهن نظرية حاصل رايلي، ويكشف أن تحليل المركبات الرئيسية — أي البحث عن اتجاه أقصى تباين — ليس إلا مسألة تحسين مقيّد حلّها هو المتجه الذاتي الأول لمصفوفة التغاير.

التطبيقات

تعلم الآلة

كل نموذج تعلم آلة يُدرَّب بنزول التدرج هو تطبيق مباشر لهذا الدرس. في الانحدار اللوجستي، الخسارة L(w) = −Σ yᵢ log σ(wᵀxᵢ) − (1−yᵢ) log(1−σ(wᵀxᵢ)) محدبة في w — لأن هيسيانها XᵀDX مع D قطرية موجبة، وهو موجب شبه التعريف — فيجد نزول التدرج الحل الأمثل العالمي. أما في الشبكات العميقة فالخسارة غير محدبة، ومع ذلك أثبت نزول التدرج العشوائي (SGD) ومشتقاته — SGD بالزخم وAdam وAdaGrad — فعالية عالية عمليًا. وتُستخدم النسخة العشوائية لكفاءتها الحسابية: كل خطوة تحسب التدرج على دفعة صغيرة (mini-batch) بدلًا من كامل مجموعة البيانات. ويحتفظ Adam بتقديرات جارية للعزم الأول والثاني للتدرج، فيبني فعليًا تقريبًا قطريًا لـ H⁻¹ يُكيّف حجم الخطوة لكل معامل على حدة. وقاعدة تحديثه هي θ ← θ − η m̂/(√v̂ + ε)، حيث m̂ وv̂ تقديرا العزم بعد تصحيح الانحياز — أي إنه في جوهره نسخة قطرية متطورة من طريقة نيوتن متنكّرة في ثوب بسيط.

معالجة الإشارات ومرشح فينر

مرشح فينر هو المرشح الخطي الأمثل لتقدير الإشارة بمعنى أصغر متوسط لمربع الخطأ (MMSE). أمام إشارة مطلوبة d وإشارة مرصودة مشوّشة x، يُصغّر المرشح الأمثل w* المقدار E[‖d − wᵀx‖²] على كل متجهات الأوزان w. ساوِ ‪∂/∂w‬ بالصفر فتحصل على معادلات فينر-هوبف: R_xx w = r_xd، حيث R_xx = E[xxᵀ] مصفوفة الارتباط الذاتي للدخل وr_xd = E[xd] متجه الارتباط المتقاطع. وهذه هي بعينها مسألة التحسين التربيعي Aw = b، مع A = R_xx (موجبة شبه التعريف بحكم بنائها) وb = r_xd. الحل w* = R_xx⁻¹ r_xd هو مرشح فينر — تطبيق مباشر لحل نظام خطي موجب التعريف نابع من تحسين تربيعي. وخوارزمية LMS ليست إلا نزول تدرج على هذا الشكل التربيعي: w_{k+1} = w_k + μ e_k x_k حيث e_k = d_k − w_kᵀx_k هو الخطأ الحالي — أي تقريب لحظي لمرشح فينر بنزول التدرج العشوائي.

أنظمة التحكم

المنظّم الخطي التربيعي (LQR) يُصغّر تكلفة تربيعية J = Σ (xᵀQx + uᵀRu) على متتالية تحكم u، بشرط ديناميكا حالة خطية x_{k+1} = Ax_k + Bu_k. هذه برمجة تربيعية مقيّدة في متغيرات التحكم. ويُستخرج حلها — متحكم LQR الأمثل — من حل معادلة ريكاتي الجبرية المتقطعة، وهي معادلة مصفوفية غير خطية حلّها P يعطي التكلفة المتبقية المثلى. والمتحكم الناتج خطي: u* = −Kx مع K = (R + BᵀPB)⁻¹BᵀPA. هذه النتيجة الأنيقة — متحكم خطي لهدف تربيعي مع قيود خطية — هي جوهرة نظرية الأنظمة الخطية، وتقوم بالكامل على التحسين التربيعي بأدوات الجبر الخطي.

وفي التحكم التنبؤي النموذجي (MPC) — المُستخدم في السيارات ذاتية القيادة، وخطوط الإنتاج الصناعية، وأنظمة الطاقة — نحل المسألة نفسها في الوقت الفعلي عند كل خطوة زمنية: صغّر التكلفة التربيعية (الانحراف عن المسار المرغوب + جهد التحكم) مع قيود على حالة النظام وأوامر التحكم. وشروط KKT هي ما يحوّل المسألة إلى نظام نقطة السرج الخطي الذي رأيته أعلاه.