Phase 01: Math Foundations

التحسين الملتوي

المشاكل الملتوية لديها وادي واحد شبكات عصبية لديها ملايين معرفة الفرق مهم

Type: Build

Languages: Python, TypeScript

Prerequisites: Phase 1, Lessons 04 (Calculus for ML), 08 (Optimization)

Time: ~90 minutes

أهداف التعلم

  • اختبار ما إذا كانت الوظيفة متواصلة باستخدام التعريف والمشتق الثاني والمعايير الهسسي
  • قم بتطبيق طريقة نيوتن ومقارنة التقارب التربيعي له مع تراجع التراجع
  • حل مشاكل التحسين المحدود باستخدام مضاعفات لاجرنج وتفسير ظروف KKT
  • شرح لماذا لا تكون المناظر الطبيعية للخسائر في الشبكات العصبية متواصلة ومع ذلك فإن SGD لا تزال تجد حلول جيدة

المشكلة

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

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

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

المفهوم

مجموعات متواصلة

مجموعةSهو متواصل إذا كان لأي نقطتين في S، وقطاع الخط بينهم يقع تماما فيS. . .

Convex setsNot convex
Rectangle: any two points inside can be connected by a line segment that stays insideStar/crescent shape: a line between two interior points can pass outside the set
Triangle: same property holds for all interior pointsDonut/annulus: the hole means some line segments leave the set
The line segment between any two points stays within the setThe line segment between some pairs of points exits the set

الاختبار الرسمي: لأي نقطةx, yفيSو أيّةt \in [0, 1]، النقطةtx + (1-t)yهو أيضا في S. . .

أمثلة على مجموعات متواصلة:

  • خط، طائرة، كل شيء\mathbb{R}^n
  • كرة (حلقة، كرة، هائبرسفيرة)
  • نصف الفضاء:\lbrace x : a^T x \le b \rbrace
  • التقاطع لأي عدد من مجموعات الملتوية

أمثلة على مجموعات غير متواصلة:

  • كعك (أنولوس)
  • اتحاد دوائر منفصلة
  • أي مجموعة مع "دنت" أو "ثقب"

وظائف متواصلة

وظيفةfهو متواصل إذا كان مجالها هو مجموعة متواصلة و لأي نقطتين x, yفي مجالها و أيt \in [0, 1]:

f(tx + (1-t)y) \le t f(x) + (1-t) f(y)

جغرافيا: القطاع الخطوي بين أي نقطتين على الرسم البياني يقع فوق أو على الرسم البياني.

PropertyConvex functionNon-convex function
Line segment testThe line between any two points on the graph lies above or on the curveThe line between some points on the graph dips below the curve
ShapeSingle bowl/valley curving upwardMultiple peaks and valleys with mixed curvature
Local minimaEvery local minimum is the global minimumMultiple local minima may exist at different heights

الوظائف الملتوية المشتركة:

  • f(x) = x^2(مثل)
  • f(x) = \lvert x \rvert(قيمة مطلقة)
  • f(x) = e^x(معدل)
  • f(x) = \max(0, x)(المركز الرئيسي، على الرغم من قطعة خطية)
  • f(x) = -\log(x)لـx > 0(سجل سلبي)
  • أي وظيفة خطية f(x) = a^T x + b(ملتوي ومتوت)

اختبار التخثر

ثلاثة اختبارات عملية، من أسهل إلى أكثر صرامة.

Test 1: Second derivative test (1D).إذاf''(x) \ge 0للجميعx، ثمfهو مخروط.

  • f(x) = x^2: f''(x) = 2 \ge 0-مُتَوَجِّه
  • f(x) = x^3: f''(x) = 6x- سلبيx < 0ليس مخروطاً
  • f(x) = e^x: f''(x) = e^x > 0-مُتَوَجِّه

Test 2: Hessian test (multivariate).إذا كانت المصفوفة الهسسيّةH(x)هو إيجابي نصف محدد للجميعx، ثمfهو مخروط. هي ماريخ المشتقات الجزئية الثانية.

Test 3: Definition test.تحقق من عدم المساواةf(tx + (1-t)y) \le t f(x) + (1-t) f(y)مباشرة. مفيد للعمل حيث المشتقات صعبة الحساب.

لماذا الارتباط مهم

النظريه المركزية لتحسين الملتوي:

For a convex function, every local minimum is a global minimum.

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

graph LR
    subgraph "Convex: ONE answer"
        direction TB
        C1["Loss surface has no false valleys"] --> C2["Gradient descent with a suitable step converges to the global minimum"]
    end
    subgraph "Non-convex: MANY traps"
        direction TB
        N1["Loss surface has multiple valleys and peaks"] --> N2["Gradient descent may get stuck in a local minimum"]
        N2 --> N3["Global minimum might be missed"]
    end

النتائج:

  • لا حاجة لإعادة تشغيل عشوائي
  • لا حاجة إلى جدول أعمال معقدة
  • إثباتات التقارب ممكنة (تعتمد المعدل على خصائص الوظيفة)
  • الحل فريد (حتى المناطق المستقرة)

المواصلات المواصلة مقابل غير المواصلة في ML

ProblemConvex?Why
Linear regression (MSE)YesLoss is quadratic in weights
Logistic regressionYesLog-loss is convex in weights
SVM (hinge loss)YesMaximum of linear functions
LASSO (L1 regression)YesSum of convex functions is convex
Ridge regression (L2)YesQuadratic + quadratic = convex
Neural network (any loss)NoNonlinear activations create non-convex landscape
k-means clusteringNoDiscrete assignment step
Matrix factorizationNoProduct of unknowns

النماذج الخطية مع الخسائر الملتوية هي الملتوية. في اللحظة التي تضيف فيها طبقات مخفية مع تنشيطات غير خطية، تتوقف الملتوية.

المصفوفة الهيسي

الهيسيين Hمن وظيفة f: \mathbb{R}^n \to \mathbb{R}هل هوn \times nالمصفوفة من المشتقات الجزئية الثانية.

H_{ij} = \frac{\partial^2 f}{\partial x_i \, \partial x_j}

لأجلf(x, y) = x^2 + 3xy + y^2:

\begin{gathered} \begin{aligned} \frac{\partial f}{\partial x} &= 2x + 3y & \frac{\partial^2 f}{\partial x^2} &= 2 & \frac{\partial^2 f}{\partial x \, \partial y} &= 3 \\ \frac{\partial f}{\partial y} &= 3x + 2y & \frac{\partial^2 f}{\partial y \, \partial x} &= 3 & \frac{\partial^2 f}{\partial y^2} &= 2 \end{aligned} \\[8pt] H = \begin{bmatrix} 2 & 3 \\ 3 & 2 \end{bmatrix} \end{gathered}

"الهيسي" يخبرك عن التوتر:

  • قيمة خاصة كلها إيجابية: تعمل المادية نحو الأعلى في كل اتجاه (ملتوية في تلك النقطة)
  • القيم الخاصة كلها سلبية: منحنى إلى أسفل في كل اتجاه (مؤثرة، أقصى محلية)
  • علامات مختلطة: نقطة السرير (تلتوي في بعض الاتجاهات، وتتوي في بعضها)
  • القيمة الفردية الصفرة: مسطحة في هذا الاتجاه (تدهور)

لتحقيق التخفيف، يجب أن يكون الهيسيان إيجابي شبه محدد (جميع القيم الخاصة \ge 0) في كل مكان، وليس فقط في نقطة واحدة.

طريقة نيوتن

يستخدم طريقة نيوتن معلومات من النظام الثاني (الهيسيان). يتناسب مع تقريب مربع في النقطة الحالية ويقفز مباشرة إلى الحد الأدنى من ذلك التربيعي.

\begin{aligned} \text{Update rule:} \quad & x_{\text{new}} = x - H^{-1} \cdot \text{gradient} \\ \text{Compare to gradient descent:} \quad & x_{\text{new}} = x - \text{lr} \cdot \text{gradient} \end{aligned}

طريقة نيوتن تحل محل معدل التعلم المتعدد بالهسيان المعاكس. هذا يعدل تلقائيًا حجم الخطوة والاتجاه بناءً على التوتر المحلي.

graph TD
    subgraph "Gradient Descent"
        GD1["Start"] --> GD2["Step 1"]
        GD2 --> GD3["Step 2"]
        GD3 --> GD4["..."]
        GD4 --> GD5["Step ~500: Converged"]
        GD_note["Follows gradient blindly — many small steps"]
    end
    subgraph "Newton's Method"
        NM1["Start"] --> NM2["Step 1"]
        NM2 --> NM3["..."]
        NM3 --> NM4["Step ~5: Converged"]
        NM_note["Uses curvature for optimal steps"]
    end

المزايا:

  • التقارب التربيعي بالقرب من الحد الأدنى (مربع الخطأ في كل خطوة)
  • لا معدل تعلم للتنسيق
  • متغير النطاق (يعمل بغض النظر عن كيفية تعريف المشكلة)

الإعاقة:

  • حساب التكاليف الهسية O(n^2)الذاكرة وO(n^3)لتحويل
  • لشبكة عصبية مع مليون وزن، وهذا هو 10^{12}الإدخالات و10^{18}العمليات
  • غير مميز للتعلم العميق

التحسين المحدود

التحسين غير المقيد: تقليل f(x)على كل شيءx. . .

التحسين المحدود: تقليل f(x)تخضع لقيود

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

graph LR
    subgraph "Unconstrained"
        U1["Loss function"] --> U2["Free minimum: lowest point of the loss surface"]
    end
    subgraph "Constrained"
        C1["Loss function"] --> C2["Constrained minimum: lowest point within the feasible region"]
        C3["Constraint boundary limits the search space"]
    end

مضاعفات اللجرنج

طريقة مضاعفات لاغرانج تحويل مشكلة مقيدة إلى مشكلة غير مقيدة.

المشكلة: تقليلf(x)تخضع لـg(x) = 0. . .

الحل: إدخال متغير جديد (مضاعف لاغرانج \lambda) وحل المشكلة غير المحدودة:

L(x, \lambda) = f(x) + \lambda g(x)

عند الحل، تراجع Lهو صفر:

\begin{aligned} \frac{\partial L}{\partial x} &= \frac{\partial f}{\partial x} + \lambda \frac{\partial g}{\partial x} = 0 \\ \frac{\partial L}{\partial \lambda} &= g(x) = 0 \end{aligned}

الحد الأدنى المحدود، تراجع fيجب أن تكون متوازية مع تراجع القيود gإذا لم تكن متوازية، يمكنك التحرك على طول سطح القيود وتقليلf-إلى أبعد من ذلك

graph LR
    A["Contours of f(x,y): concentric ellipses"] --- S["Solution point"]
    B["Constraint curve g(x,y) = 0"] --- S
    S --- C["At the solution, gradient of f is parallel to gradient of g"]

مثال: تقليلf(x,y) = x^2 + y^2تخضع لـx + y = 1. . .

\begin{aligned} L &= x^2 + y^2 + \lambda(x + y - 1) \\[4pt] \frac{\partial L}{\partial x} &= 2x + \lambda = 0 \implies x = -\lambda/2 \\ \frac{\partial L}{\partial y} &= 2y + \lambda = 0 \implies y = -\lambda/2 \\ \frac{\partial L}{\partial \lambda} &= x + y - 1 = 0 \\[4pt] &\text{From first two: } x = y \\ &\text{Substituting: } 2x = 1, \text{ so } x = y = 0.5, \ \lambda = -1 \end{aligned}

أقرب نقطة على الخطx + y = 1إلى المنشأ هو (0.5, 0.5). . .

شروط الـ KKT

ظروف كاروش-كوهن-توكر تمتد مضاعفات لاجرنج إلى قيود عدم المساواة.

المشكلة: تقليلf(x)تخضع لـg_i(x) \le 0لـi = 1, \ldots, m. . .

ظروف KKT (التي تكون ضرورية لتحقيق التكمل الأمثل):

\begin{aligned} &\text{1. Stationarity:} && \frac{\partial f}{\partial x} + \sum_i \lambda_i \frac{\partial g_i}{\partial x} = 0 \\ &\text{2. Primal feasibility:} && g_i(x) \le 0 \quad \text{for all } i \\ &\text{3. Dual feasibility:} && \lambda_i \ge 0 \quad \text{for all } i \\ &\text{4. Complementary slackness:} && \lambda_i \, g_i(x) = 0 \quad \text{for all } i \end{aligned}

التباطل المكمل هو المفهوم الرئيسي: إما أن القيود نشطة (g_i = 0، يقع الحل على الحدود) أو المضاعف هو صفر (القيود لا يهم).\lambda = 0. . .

ظروف كيكت هي المركزية لسي.إف.إم. المتجهات الداعمة هي نقاط البيانات التي يكون فيها القيود نشطا (\lambda > 0كل نقاط البيانات الأخرى لديها\lambda = 0ولا تؤثر على حدود القرار

التنظيم كتحسين محدود

إن تنظيم L1 و L2 ليسوا خدوش تعسفية بل مشاكل تحسين محدودة في التظاهر.

L2 regularization (Ridge):

\begin{aligned} &\text{minimize } \text{Loss}(w) \text{ subject to } \lVert w \rVert^2 \le t \\[4pt] &\text{Equivalent unconstrained form:} \\ &\text{minimize } \text{Loss}(w) + \lambda \lVert w \rVert^2 \end{aligned}

القيود\lVert w \rVert^2 \le tيحدد الكرة (حلقة في 2D، كرة في 3D). الحل هو حيث أن خطوط الخسارة تلمس هذه الكرة أولا.

L1 regularization (LASSO):

\begin{aligned} &\text{minimize } \text{Loss}(w) \text{ subject to } \lVert w \rVert_1 \le t \\[4pt] &\text{Equivalent unconstrained form:} \\ &\text{minimize } \text{Loss}(w) + \lambda \lVert w \rVert_1 \end{aligned}

القيود\lVert w \rVert_1 \le tيحدد الماس (الرابع المدوّر في 2D).

PropertyL2 constraint (circle)L1 constraint (diamond)
Constraint shapeCircle (sphere in higher dims)Diamond (rotated square in 2D)
Where loss contour touchesSmooth boundary — any point on the circleCorner — aligned with an axis
Solution behaviorWeights are small but nonzeroSome weights are exactly zero (sparse)
ResultWeight shrinkageFeature selection

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

الثنائي

كل مشكلة تحسين مقيد (الأولي) لديها مشكلة رفيقة (المتزامن). بالنسبة للمشاكل المتواصلة، فإن الأولي والمتزامن لديهم نفس القيمة المثلى. هذه ثنائية قوية.

وظيفة لاجرنجية مزدوجة:

\begin{aligned} &\text{Primal:} && \text{minimize } f(x) \text{ subject to } g(x) \le 0 \\ &\text{Lagrangian:} && L(x, \lambda) = f(x) + \lambda g(x) \\ &\text{Dual function:} && d(\lambda) = \min_x L(x, \lambda) \\ &\text{Dual problem:} && \text{maximize } d(\lambda) \text{ subject to } \lambda \ge 0 \end{aligned}

لماذا الثنائيات مهمة:

  • المشكلة المزدوجة أسهل في بعض الأحيان لحلها من المشكلة الأساسية
  • يتم حل SVM في شكلها المزدوج ، حيث تعتمد المشكلة على منتجات النقاط بين نقاط البيانات (تمكين خدعة النواة)
  • يقدم المزدوج حدوداً أدناه على المثالي الأولي، مفيدًا للتحقق من جودة الحل

بالنسبة لـ (SVM) على وجه التحديد:

code
Primal: find w, b that maximize the margin 2/||w|| subject to
        y_i(w^T x_i + b) >= 1 for all i

Dual:   maximize sum(alpha_i) - 0.5 * sum_ij(alpha_i * alpha_j * y_i * y_j * x_i^T x_j)
        subject to alpha_i >= 0 and sum(alpha_i * y_i) = 0

The dual only involves dot products x_i^T x_j.
Replace x_i^T x_j with K(x_i, x_j) to get the kernel trick.

لماذا يتحسن التعلم العميق على الرغم من عدم التواصل

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

Most local minima are good enough.في المساحات العالية الأبعاد، النقاط الحرجة العشوائية (حيث يكون التراجع صفر) هي نقاط القيادة بشكل ساحق، وليس الحد الأدنى المحلي. القليل من الحد الأدنى المحلي الموجودة تميل إلى أن يكون لها قيم الخسارة القريبة من الحد الأدنى العالمي. فمن غير المرجح للغاية أن تكون عالقة في الحد الأدنى المحلي الفظيع عندما يكون مساحة المعلمات مليوني أبعاد.

Saddle points, not local minima, are the real obstacle.في وظيفة معnفي المعلمات، نقطة السرير لديها مزيج من اتجاهات التوتر الإيجابية والسلبية. بالنسبة لمكان حرج عشوائي في أبعاد عالية، احتمال جميع nالقيم الخاصة تكون إيجابية (الأدنى المحلي) تقريبًا 2^{-n}تقريباً كل النقاط الحرجة هي نقاط السرير ضوضاء المراقبة تساعد على الهروب منها

Overparameterization smooths the landscape.شبكات ذات ملامح أكثر من أمثلة التدريب لديها أسطح الخسارة أكثر سلاسة، والمزيد من الاتصال. شبكات أوسع لديها أدنى الحد الأدنى المحلي السيئ. هذا غير بديهي ولكن ثابت تجريبيا.

Loss landscape structure:

PropertyLow-dimensional spaceHigh-dimensional space
LandscapeMany isolated peaks and valleysSmoothly connected valleys
MinimaMany isolated local minimaFew bad local minima; most are near-optimal
NavigationHard to find global minimumMany paths lead to good solutions
Critical pointsMix of local minima and saddle pointsOverwhelmingly saddle points, not local minima

Stochastic noise acts as implicit regularization.تضيف SGD الارتباطات الصغيرة الضجيج الذي يمنع الاستقرار في الحد الأدنى الحاد. الحد الأدنى الحاد يزيد من التكيف؛ الحد الأدنى السطح يعملي. التحيز الضجيج تحسين نحو المناطق السطحية لمشهد الخسائر.

أساليب النظام الثاني في الممارسة العملية

طريقة نيوتن النقية غير عملية للنماذج الكبيرة. العديد من التقارير تجعل المعلومات من الدرجة الثانية قابلة للاستخدام.

L-BFGS (Limited-memory BFGS):يقترب من الـ Hessian المُعكس باستخدام آخر mالاختلافات في التراجع.O(mn)الذاكرة بدلاً منO(n^2)يعمل بشكل جيد للمشاكل التي تصل إلى ~ 10,000 ملامح. يستخدم في ML الكلاسيكية (التراجع اللوجستي ، CRFs) ولكن ليس التعلم العميق.

Natural gradient:يستخدم مصفوفة معلومات فيشر (الهيسيان المتوقع من احتمالات التسجيل) بدلاً من المصفوفة المعتادة. هذا يعطي حساب لجيومétrي توزيعات الاحتمالات. K-FAC (Kronecker-Factored Approximate Curvature) يقترب من مصفوفة فيشر كمنتج كروينكر ، مما يجعلها عملية للشبكات العصبية.

Hessian-free optimization:يستخدم التراجع المشترك لحلHx = gدون أن تتشكل أبداًH. فقط يتطلب محولات متجهة هيسيان، والتي يمكن حسابها في O(n)الوقت عن طريق التمييز الآلي.

Diagonal approximations:اللحظة الثانية لآدم هي تقارب متقطع مع متقطع هيسيان. يمتد AdaHessian هذا باستخدام عناصر متقطع هيسيان الفعلية عبر مقياس هاتشينسون.

MethodMemoryPer-step costWhen to use
Gradient descentO(n)O(n)Baseline, large models
Newton's methodO(n^2)O(n^3)Small convex problems
L-BFGSO(mn)O(mn)Medium convex problems
AdamO(n)O(n)Deep learning default
K-FACO(n)O(n) per layerResearch, large-batch training

بناءها

الخطوة الأولى: فحص التوتر

بناء وظيفة التي تختبر التخفيف تجريبيا عن طريق أخذ عينات من نقاط وتحقق من التعريف.

python
import random
import math

def check_convexity(f, dim, bounds=(-5, 5), samples=1000):
    violations = 0
    for _ in range(samples):
        x = [random.uniform(*bounds) for _ in range(dim)]
        y = [random.uniform(*bounds) for _ in range(dim)]
        t = random.uniform(0, 1)
        mid = [t * xi + (1 - t) * yi for xi, yi in zip(x, y)]
        lhs = f(mid)
        rhs = t * f(x) + (1 - t) * f(y)
        if lhs > rhs + 1e-10:
            violations += 1
    return violations == 0, violations

الخطوة الثانية: طريقة نيوتن للثانية

قم بتطبيق طريقة نيوتن باستخدام هسيان صريح. قارن سرعة التقارب مع انخفاض التراجع.

python
def newtons_method(f, grad_f, hessian_f, x0, steps=50, tol=1e-12):
    x = list(x0)
    history = [x[:]]
    for _ in range(steps):
        g = grad_f(x)
        H = hessian_f(x)
        det = H[0][0] * H[1][1] - H[0][1] * H[1][0]
        if abs(det) < 1e-15:
            break
        H_inv = [
            [H[1][1] / det, -H[0][1] / det],
            [-H[1][0] / det, H[0][0] / det],
        ]
        dx = [
            H_inv[0][0] * g[0] + H_inv[0][1] * g[1],
            H_inv[1][0] * g[0] + H_inv[1][1] * g[1],
        ]
        x = [x[0] - dx[0], x[1] - dx[1]]
        history.append(x[:])
        if sum(gi ** 2 for gi in g) < tol:
            break
    return history

الخطوة الثالثة: محلل مضاعف اللجرنج

حل التحسين المحدود باستخدام انخفاض التدرج على لغرانجي.

python
def lagrange_solve(f_grad, g_val, g_grad, x0, lr=0.01,
                   lr_lambda=0.01, steps=5000):
    x = list(x0)
    lam = 0.0
    history = []
    for _ in range(steps):
        fg = f_grad(x)
        gv = g_val(x)
        gg = g_grad(x)
        x = [
            xi - lr * (fgi + lam * ggi)
            for xi, fgi, ggi in zip(x, fg, gg)
        ]
        lam = lam + lr_lambda * gv
        history.append((x[:], lam, gv))
    return history

الخطوة الرابعة: مقارنة النظام الأول والنظام الثاني

أستخدم طريقة نيوتن على نفس المرتبة، و أعد الخطوات إلى التقارب

python
def quadratic(x):
    return 5 * x[0] ** 2 + x[1] ** 2

def quadratic_grad(x):
    return [10 * x[0], 2 * x[1]]

def quadratic_hessian(x):
    return [[10, 0], [0, 2]]

طريقة نيوتن سوف تتحرك في خطوة واحدة (إنها دقيقة بالنسبة إلى التربيعية). سيقوم التنزل التدريجي بمئات الخطوات لأن القيم الخاصة لـ Hessian تختلف بمعدل 5 ، مما يخلق واديًا مُطولًا.

استخدمها

تحليل التخثر ينطبق مباشرة عند اختيار نماذج وموصلات ML.

بالنسبة للمشاكل المتعثرة (التراجع اللوجستي، SVMs، LASSO):

  • استخدام حلول مخصصة (liblinear، CVXPY، scipy.optimize.minimize مع طريقة='L-BFGS-B')
  • توقع حل عالمي فريد
  • أساليب النظام الثاني عملية و سريعة

بالنسبة للمشاكل غير الملتوية (شبكات عصبية):

  • استخدام أساليب النظام الأول (SGD، آدم)
  • اقبل أن الحل يعتمد على البداية والتصوير عشوائي
  • استخدام المقاييس المفرطة، الضوضاء، وخطوط جدول معدل التعلم كتنظيم ضمني
  • لا تضيعوا الوقت في البحث عن الحد الأدنى العالمي. الحد الأدنى المحلي الجيد يكفي.
python
from scipy.optimize import minimize

result = minimize(
    fun=lambda w: sum((y - X @ w) ** 2) + 0.1 * sum(w ** 2),
    x0=np.zeros(d),
    method='L-BFGS-B',
    jac=lambda w: -2 * X.T @ (y - X @ w) + 0.2 * w,
)

بالنسبة لـ SVM، يسمح لك الصيغة المزدوجة باستخدام خدعة النواة:

python
from sklearn.svm import SVC

svm = SVC(kernel='rbf', C=1.0)
svm.fit(X_train, y_train)
print(f"Support vectors: {svm.n_support_}")

التمارين

  1. Convexity gallery.اختبر هذه الوظائف لتحديد الارتباط باستخدام المحقق: f(x) = x^4،f(x) = \sin(x)،f(x,y) = x^2 + y^2،f(x,y) = xy،f(x) = \max(x, 0)اشرح لماذا كل نتيجة لها معنى
  1. Newton vs gradient descent race.أستخدم كلا الطرقينf(x,y) = 50x^2 + y^2من نقطة البداية(10, 10)كم خطوة تحتاج كل واحد للوصول إلى الخسارة < 1e-10؟ ماذا يحدث لسقوط التراجع عند زيادة عدد الحالة (النسبة من أكبر إلى أصغر قيمة خاصة هيسسي) ؟
  1. Lagrange multiplier geometry.تقليلf(x,y) = (x-3)^2 + (y-3)^2تخضع لـx + 2y = 4التحقق من الحل عن طريق التحقق من أن تراجعfهو متوازي مع تراجع gفي الحل
  1. Regularization constraint.تنفيذ التحسينات المحدودة لـ L1: تقليل(x-3)^2 + (y-2)^2تخضع لـ\lvert x \rvert + \lvert y \rvert \le 1. إظهار أن الحل لديه إحداثيات تساوي الصفر (المتناثرة من قيود الماس).
  1. Hessian eigenvalue analysis.احسب Hessian من وظيفة روزنبروك في (1,1) و (-1,1). احسب القيم الخاصة في كلا النقاط. ماذا تخبرك القيم الخاصة عن التوتر في الحد الأدنى مقابل بعيدا عنه؟

إشارات

Exercise 1.توقع كل نتيجة قبل أن تهربcheck_convexity: في بعد واحد، انظر إلى علامةf''(x)في ابعدين، انظر إلى القيم الخاصة لـ Hessian.f(x,y) = xy، والهسسي لديها قيم خاصة 1 و -1, لذلك يجب على المحقق الإبلاغ عن أنه ليس متواضع.

Exercise 2.اتصلoptimize_gdوnewtons_methodمع التراجع والهسسي fطريقة نيوتن تحل مربع في خطوة واحدة. لتنزيل التراجع، يجب أن يكون معدل التعلم أقل من 2/100بسبب50x^2المفهوم، لذلك yاتجاه يتحرك ببطء. كرر مع 100x^2و أعد الخطوات مرة أخرى

Exercise 3.استخدامlagrange_solveمعg(x,y) = x + 2y - 4عند الإجابة، تحقق من ذلكx + 2y = 4و هذا\nabla f = (2(x-3), 2(y-3))هو مضاعف من\nabla g = (1, 2). . .

Exercise 4.الحد الأدنى غير المقيد (3, 2) خارج الماس، لذلك الجواب على حدودها. استخدم انخفاض تراجعي مشروع: اتخاذ خطوة تراجعي، ثم إلقاء العودة على \lvert x \rvert + \lvert y \rvert \le 1تحقق من أن النتيجة تلبي القيود مع المساواة ومقارنة معdemo_regularization_geometry. . .

Exercise 5.اتصلrosenbrock_hessianفي كل نقطة ونقل النتيجة إلىhessian_eigenvalues_2dعند (1, 1) ، كل من القيم الخاصة إيجابية ونسبةهم كبيرة جدا، لذلك الوادي ضيق في اتجاه واحد وسط في الآخر. مقارنة هذا النسبة مع النسبة في (-1, 1).

الشروط الرئيسية

TermWhat it means
Convex setA set where the line segment between any two points in the set stays inside the set
Convex functionA function where the line between any two points on its graph lies above or on the graph. Equivalently, Hessian is positive semidefinite everywhere
Local minimumA point lower than all nearby points. For convex functions, every local minimum is the global minimum
Global minimumThe lowest point of a function over its entire domain
Hessian matrixThe matrix of all second partial derivatives. Encodes curvature information
Positive semidefiniteA matrix whose eigenvalues are all non-negative. The multidimensional analogue of "second derivative >= 0"
Condition numberRatio of largest to smallest eigenvalue of the Hessian. High condition number means elongated valleys and slow gradient descent
Newton's methodSecond-order optimizer that uses the inverse Hessian to determine step direction and size. Quadratic convergence near the minimum
Lagrange multiplierA variable introduced to convert a constrained optimization problem into an unconstrained one
KKT conditionsNecessary conditions for optimality with inequality constraints. Generalize Lagrange multipliers
Complementary slacknessAt the solution, either a constraint is active or its multiplier is zero. Never both nonzero
DualityEvery constrained problem has a companion dual problem. For convex problems, both have the same optimal value
Strong dualityPrimal and dual optimal values are equal. Holds for convex problems satisfying Slater's condition
L-BFGSApproximate second-order method that stores the last m gradient differences instead of the full Hessian
Saddle pointA point where the gradient is zero but it is a minimum in some directions and a maximum in others
OverparameterizationUsing more parameters than training examples. Smooths the loss landscape and reduces bad local minima

المزيد من القراءة

This free lesson is part of the AI Engineering from Scratch curriculum. Read the full explanation, run the lesson code, and verify the result in the interactive reader or from the repository source.

Browse the complete course catalog or open this lesson on GitHub.