بهینه‌سازی کوژ در یادگیری ماشین: از ماتریس هسیان تا روش نیوتن و شرایط KKT

در الگوریتم‌های گرادیان کاهشی و روش‌های رایج بهینه‌سازی، حرکت به‌سمت پایین‌ترین نقطه هیچ تضمین قطعی برای رسیدن به بهترین پاسخ سراسری ارائه نمی‌دهد. وقتی با شبکه‌های عصبی کار می‌کنید، با هزاران دره و کمینه‌ی محلی روبه‌رو هستید که الگوریتم ممکن است در آن‌ها به دام بیفتد یا ساعت‌ها نوسان کند؛ اما آیا تمام مسائل یادگیری ماشین همین‌قدر غیرقابل پیش‌بینی هستند؟

پاسخ منفی است. بخش وسیعی از مدل‌های استاندارد مثل رگرسیون خطی، رگرسیون لجستیک و SVM در دسته‌ی مسئله‌های بهینه‌سازی کوژ (Convex Optimization) قرار می‌گیرند. در توابع کوژ، هر کمینه‌ی محلی تضمین‌شده همان کمینه‌ی سراسری است و دیگر نیازی به راه‌اندازی‌های مکرر یا حدس زدن شانس‌محور نرخ یادگیری نخواهید داشت.

در این درس یاد می‌گیرید که چگونه با ابزارهایی مانند ماتریس هسیان (Hessian) کوژ بودن یک تابع را بیازمایید، بهینه‌سازی‌های مقید را با ضرایب لاگرانژ و شرایط KKT حل کنید، و با روش‌های مرتبه دومی مثل روش نیوتن به همگرایی فوق‌العاده سریع برسید. همچنین متوجه خواهید شد چرا شبکه‌های عصبی با وجود تمام ناکوژ بودنشان، در عمل با بهینه‌سازهای ساده به نتایج مطلوبی می‌رسند.

مسئله‌های کوژ تنها یک دره دارند، اما شبکه‌های عصبی میلیون‌ها دره دارند. درک این تفاوت اهمیت زیادی دارد.

اهداف یادگیری

• بررسی کوژ بودن یک تابع با استفاده از تعریف، مشتق دوم و معیارهای هسیان (Hessian)
• پیاده‌سازی روش نیوتن (Newton's method) و مقایسه‌ی همگرایی مرتبه دو (quadratic convergence) آن با گرادیان کاهشی (gradient descent)
• حل مسئله‌های بهینه‌سازی مقید با استفاده از ضرایب لاگرانژ (Lagrange multipliers) و تفسیر شرایط KKT
• توضیح اینکه چرا چشم‌انداز زیان در شبکه‌های عصبی ناکوژ (non-convex) است، اما SGD همچنان راه‌حل‌های مناسبی پیدا می‌کند

صورت مسئله

در درس 08 با گرادیان کاهشی، تکانه (momentum) و Adam آشنا شدید. این بهینه‌سازها روی هر سطحی به‌سمت پایین حرکت می‌کنند؛ اما هیچ تضمینی به شما نمی‌دهند. اجرای گرادیان کاهشی روی یک چشم‌انداز ناکوژ ممکن است به یک کمینه‌ی محلی (local minimum) نامطلوب ختم شود، در یک نقطه‌ی زینی (saddle point) گیر کند یا تا ابد دچار نوسان شود. با این حال باز هم از آن استفاده کردید، چون شبکه‌های عصبی ناکوژ هستند و گزینه‌ی دیگری وجود ندارد.

اما بسیاری از مسئله‌ها در یادگیری ماشین کوژ (convex) هستند: رگرسیون خطی، رگرسیون لجستیک، SVMها، LASSO و رگرسیون ستیغی (ridge regression). برای این موارد، ابزار بسیار قدرتمندتری در دست داریم: بهینه‌سازی با تضمین‌های ریاضی. یک مسئله‌ی کوژ هیچ دره‌ی کاذبی ندارد؛ در این توابع هر کمینه‌ی محلی همان کمینه‌ی سراسری (global minimum) است. برای یک تابع کوژ هموار که کمینه دارد، گرادیان کاهشی با اندازه‌ی گام مناسب قطعاً به آن همگرا می‌شود؛ بدون نیاز به راه‌اندازی‌های مجدد، بدون نیاز به زمان‌بندی نرخ یادگیری، و بدون دست به دامن شانس شدن.

درک کوژی (convexity) سه فایده‌ی مهم دارد. اول، مشخص می‌کند مسئله‌ی شما ساده (کوژ) است یا دشوار (ناکوژ). دوم، ابزارهای سریع‌تری مثل روش نیوتن را برای مسئله‌های کوژ در اختیارتان می‌گذارد. سوم، مفاهیمی را روشن می‌کند که در سراسر یادگیری ماشین به چشم می‌خورند: منظم‌سازی به‌شکل یک قید، دوگانگی (duality) در SVMها، و این‌که چرا یادگیری عمیق علی‌رغم نقض تمام ویژگی‌های خوب کوژی، همچنان موفق عمل می‌کند.

مفاهیم پایه

مجموعه‌های کوژ

مجموعه‌ی $S$ را کوژ می‌نامیم اگر برای هر دو نقطه‌ی دلخواه در $S$، پاره‌خط بین آن‌ها نیز به‌طور کامل درون $S$ قرار بگیرد.

آزمون صوری: به ازای هر نقطه‌ی $x, y$ در $S$ و هر $t \in [0, 1]$، نقطه‌ی $tx + (1-t)y$ نیز درون $S$ قرار دارد.

نمونه‌هایی از مجموعه‌های کوژ:

• خط، صفحه، کل فضای $\mathbb{R}^n$
• گوی (دایره، کره، ابرکره)
• نیم‌فضا (halfspace): $\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)$$

از نظر هندسی: پاره‌خط رابط میان هر دو نقطه روی نمودار تابع، همواره بالای نمودار یا روی آن قرار می‌گیرد.

توابع کوژ رایج:

• $f(x) = x^2$ (سهمی)
• $f(x) = \lvert x \rvert$ (قدر مطلق)
• $f(x) = e^x$ (نمایی)
• $f(x) = \max(0, x)$ (ReLU، گرچه تکه‌به‌تکه خطی است)
• $f(x) = -\log(x)$ به ازای $x > 0$ (منفی لگاریتم)
• هر تابع خطی $f(x) = a^T x + b$ (هم کوژ و هم کاو)

آزمون‌های بررسی کوژی

سه آزمون کاربردی، از ساده‌ترین تا دقیق‌ترین روش:

آزمون 1: آزمون مشتق دوم (یک‌بعدی). اگر برای تمام $x$ داشته باشیم $f''(x) \ge 0$، آنگاه $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$. کوژ است.

آزمون 2: آزمون هسیان (چندمتغیره). اگر ماتریس هسیان $H(x)$ برای تمام $x$ مثبت نیمه‌معین (positive semidefinite) باشد، تابع $f$ کوژ است. ماتریس هسیان، ماتریسی متشکل از مشتقات پاره‌ای مرتبه دوم است.

آزمون 3: آزمون با تعریف. نامساوی $f(tx + (1-t)y) \le t f(x) + (1-t) f(y)$ را مستقیماً بررسی کنید. این آزمون برای توابعی که محاسبه‌ی مشتق آن‌ها دشوار است کاربرد دارد.

چرا کوژی اهمیت دارد؟

قضیه‌ی بنیادین بهینه‌سازی کوژ:

در یک تابع کوژ، هر کمینه‌ی محلی همان کمینه‌ی سراسری است.

این یعنی گرادیان کاهشی نمی‌تواند در یک کمینه‌ی محلی نامطلوب گیر بیفتد. هر کمینه‌ای که الگوریتم به آن برسد مقدار زیان یکسانی دارد. برای یک تابع کوژ هموار که کمینه دارد، همگرایی گرادیان کاهشی با اندازه‌ی گام مناسب به مقدار بهینه تضمین‌شده است.

پیامدها:

• نیازی به راه‌اندازی‌های تصادفی مجدد نیست
• به زمان‌بندی‌های پیچیده برای نرخ یادگیری احتیاجی ندارید
• اثبات ریاضی همگرایی ممکن است (سرعت همگرایی به ویژگی‌های تابع بستگی دارد)
• پاسخ مسئله یکتا است (به‌جز در بخش‌های کاملاً مسطح)

مسئله‌های کوژ در برابر غیرکوژ در یادگیری ماشین

مدل‌های خطی با توابع زیان کوژ، کوژ هستند. اما به‌محض این‌که لایه‌های پنهان را با توابع فعال‌ساز غیرخطی اضافه کنید، خاصیت کوژی از بین می‌رود.

ماتریس هسیان

ماتریس هسیان $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}$$

روش نیوتن نرخ یادگیری اسکالر را با معکوس ماتریس هسیان جایگزین می‌کند. این کار اندازه‌ی گام و جهت حرکت را به‌طور خودکار بر اساس انحنای محلی تنظیم می‌کند.

مزایا:

• همگرایی درجه دو در نزدیکی کمینه (خطا در هر گام به توان دو می‌رسد)
• عدم نیاز به تنظیم نرخ یادگیری
• مستقل از مقیاس (صرف‌نظر از نحوه‌ی پارامتربندی مسئله کار می‌کند)

معایب:

• محاسبه‌ی هسیان به حافظه‌ای از مرتبه‌ی $O(n^2)$ نیاز دارد و معکوس کردن آن هزینه‌ی محاسباتی $O(n^3)$ دارد
• برای یک شبکه‌ی عصبی با 1 میلیون وزن، این یعنی ذخیره‌ی $10^{12}$ درایه و انجام $10^{18}$ عملیات محاسباتی
• برای یادگیری عمیق عملی نیست

بهینه‌سازی مقید

بهینه‌سازی نامقید: کمینه‌سازی $f(x)$ روی تمام مقادیر $x$. بهینه‌سازی مقید: کمینه‌سازی $f(x)$ با رعایت قیدها.

مسئله‌های واقعی همواره قید دارند. می‌خواهید هزینه را کمینه کنید اما بودجه‌تان محدود است. می‌خواهید خطا را به حداقل برسانید اما پیچیدگی مدل باید مهار شود.

ضرایب لاگرانژ

روش ضرایب لاگرانژ مسئله‌ی مقید را به یک مسئله‌ی نامقید تبدیل می‌کند.

صورت مسئله: کمینه‌سازی $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$ را از این هم کمتر کنید.

مثال: کمینه‌سازی $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

شرایط کاروش-کون-تاکر (Karush-Kuhn-Tucker یا 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}$$

سستی مکمل (Complementary slackness) نکته‌ی کلیدی است: یا قید فعال است ($g_i = 0$، یعنی جواب دقیقاً روی مرز قرار دارد) یا ضریب لاگرانژ صفر است (یعنی قید اهمیتی ندارد). قیدی که تاثیری روی پاسخ نگذارد، دارای ضریب $\lambda = 0$ خواهد بود.

شرایط KKT نقش محوری در SVMها دارند. بردارهای پشتیبان دقیقاً همان نقاط داده‌ای هستند که قید آن‌ها فعال است ($\lambda > 0$). سایر نقاط داده دارای $\lambda = 0$ هستند و هیچ اثری روی مرز تصمیم‌گیری نمی‌گذارند.

منظم‌سازی به‌شکل بهینه‌سازی مقید

منظم‌سازی‌های L1 و L2 صرفاً ترفندهایی اختیاری نیستند، بلکه در اصل همان مسئله‌های بهینه‌سازی مقید هستند.

منظم‌سازی L2 (ستیغی):

$$\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$ یک گوی تعریف می‌کند (دایره در دوبعد، کره در سه‌بعد). نقطه‌ی بهینه جایی است که خطوط تراز (کانتور) زیان برای اولین بار با این گوی مماس می‌شوند.

منظم‌سازی L1 (الگوریتم 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$ یک لوزی تعریف می‌کند (مربع چرخانده‌شده در فضای دوبعدی).

این تفاوت نشان می‌دهد چرا L1 مدل‌هایی تنک (با قابلیت انتخاب ویژگی) تولید می‌کند اما L2 فقط وزن‌ها را منقبض می‌کند. لوزی گوشه‌هایی دارد که در راستای محورها قرار گرفته‌اند؛ بنابراین احتمال برخورد خطوط کانتور زیان با یک گوشه بسیار بیشتر است که باعث می‌شود یک یا چند وزن دقیقاً برابر صفر شوند.

دوگانگی

هر مسئله‌ی بهینه‌سازی مقید (مسئله‌ی اولیه یا primal)، یک مسئله‌ی همزاد (مسئله‌ی دوگان یا dual) دارد. در مسئله‌های کوژ، مقدار بهینه‌ی مسئله‌ی اولیه و دوگان یکسان است؛ به این پدیده دوگانگی قوی (strong duality) می‌گویند.

تابع دوگان لاگرانژ:

$$\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ها در فرمول‌بندی دوگان حل می‌شوند، جایی که مسئله به ضرب داخلی بین نقاط داده وابسته است (و امکان استفاده از ترفند کرنل یا kernel trick را فراهم می‌کند).
• مسئله‌ی دوگان یک کران پایین برای مقدار بهینه‌ی اولیه فراهم می‌کند که برای سنجش کیفیت جواب بسیار مفید است.

به‌طور خاص برای SVMها:

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.

چرا یادگیری عمیق با وجود ناکوژ بودن کار می‌کند؟

توابع زیان در شبکه‌های عصبی به‌شدت ناکوژ هستند. طبق تمام معیارهای کلاسیک، بهینه‌سازی آن‌ها باید با شکست مواجه می‌شد. با این حال، بهینه‌ساز گرادیان کاهشی تصادفی (SGD) به‌طور پیوسته جواب‌های خوبی پیدا می‌کند. چند عامل این موضوع را توضیح می‌دهند:

بیشتر کمینه‌های محلی به‌اندازه‌ی کافی خوب هستند. در فضاهایی با ابعاد بالا، نقاط بحرانی تصادفی (جاهایی که گرادیان صفر است) به‌احتمال قریب به اتفاق نقاط زینی هستند، نه کمینه‌های محلی. کمینه‌های محلی اندکی هم که وجود دارند، مقادیر زیانشان بسیار نزدیک به کمینه‌ی سراسری است. گیر افتادن در یک کمینه‌ی محلی فاجعه‌بار در فضایی با میلیون‌ها بُعد، بی‌نهایت بعید است.

نقاط زینی مانع اصلی هستند، نه کمینه‌های محلی. در تابعی با $n$ پارامتر، یک نقطه‌ی زینی دارای ترکیبی از جهات با انحنای مثبت و منفی است. برای یک نقطه‌ی بحرانی تصادفی در ابعاد بالا، احتمال اینکه تمام $n$ مقدار ویژه مثبت باشند (کمینه‌ی محلی) تقریباً برابر با $2^{-n}$ است. تقریباً تمام نقاط بحرانی در واقع نقاط زینی هستند؛ نوفه‌ی (noise) موجود در SGD به فرار از آن‌ها کمک می‌کند.

پارامترسازی بیش از حد چشم‌انداز را هموار می‌کند. شبکه‌هایی که تعداد پارامترهایشان بیشتر از تعداد داده‌های آموزشی است، سطوح زیان هموارتر و به‌هم‌پیوسته‌تری دارند. شبکه‌های عریض‌تر کمینه‌های محلی بد کمتری دارند. این گزاره با شهود اولیه ناسازگار به نظر می‌رسد، اما از نظر تجربی کاملاً ثابت شده است.

ساختار چشم‌انداز زیان:

نوفه‌ی تصادفی مثل منظم‌سازی ضمنی عمل می‌کند. در Mini-batch SGD، نمونه‌برداری دسته‌ای تصادفی نوفه‌ای اضافه می‌کند که مانع از ماندن در کمینه‌های تیز می‌شود. کمینه‌های تیز به بیش‌برازش (overfitting) می‌انجامند، درحالی‌که کمینه‌های مسطح قدرت تعمیم دارند. این نوفه، بهینه‌سازی را به‌سمت نواحی مسطح چشم‌انداز زیان سوق می‌دهد.

روش‌های مرتبه دوم در عمل

استفاده از روش خالص نیوتن برای مدل‌های بزرگ غیرعملی است. چند تقریب مختلف استفاده از اطلاعات مرتبه دوم را امکان‌پذیر می‌کنند:

الگوریتم L-BFGS (یا BFGS با حافظه‌ی محدود): معکوس ماتریس هسیان را با استفاده از تفاضل گرادیان‌ها در $m$ گام آخر تقریب می‌زند. این روش به‌جای حافظه‌ی $O(n^2)$ تنها به $O(mn)$ حافظه نیاز دارد. برای مسئله‌هایی تا حدود 10000 پارامتر بسیار خوب کار می‌کند. در یادگیری ماشین کلاسیک (رگرسیون لجستیک، CRFها) کاربرد دارد، اما برای یادگیری عمیق مناسب نیست.

گرادیان طبیعی (Natural gradient): به‌جای هسیان معمولی از ماتریس اطلاعات فیشر (امید ریاضی هسیان لگاریتم درست‌نمایی) استفاده می‌کند. این رویکرد ساختار هندسی توزیع‌های احتمال را در نظر می‌گیرد. الگوریتم K-FAC با تقریب ماتریس فیشر به‌صورت حاصل‌ضرب کرونکر، استفاده از آن را برای شبکه‌های عصبی عملی می‌کند.

بهینه‌سازی بدون هسیان (Hessian-free optimization): با استفاده از گرادیان مزدوج، معادله‌ی $Hx = g$ را بدون تشکیل صریح ماتریس $H$ حل می‌کند. این روش فقط به حاصل‌ضرب‌های هسیان در بردار نیاز دارد که با مشتق‌گیری خودکار در زمان $O(n)$ قابل محاسبه است.

تقریب‌های قطری: گشتاور دوم در Adam در حقیقت یک تقریب قطری از قطر ماتریس هسیان است. الگوریتم AdaHessian با استفاده از برآوردگر هاچینسون، درایه‌های واقعی قطر هسیان را تخمین می‌زند و این ایده را گسترش می‌دهد.

پیاده‌سازی گام‌به‌گام

گام 1: بررسی‌کننده‌ی کوژی تابع

تابعی بسازید که کوژ بودن را به‌صورت تجربی با نمونه‌برداری از نقاط و بررسی تعریف ریاضی آن بیازماید.

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

گام 2: روش نیوتن برای توابع دوبعدی

روش نیوتن را با استفاده از ماتریس هسیان صریح پیاده‌سازی کنید و سرعت همگرایی آن را با گرادیان کاهشی بسنجید.

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

گام 3: حل‌کننده‌ی ضریب لاگرانژ

بهینه‌سازی مقید را با استفاده از گرادیان کاهشی روی فرمول لاگرانژ حل کنید.

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

گام 4: مقایسه‌ی روش‌های مرتبه اول و مرتبه دوم

گرادیان کاهشی و روش نیوتن را روی یک تابع درجه دوم یکسان اجرا کنید و تعداد گام‌های لازم تا همگرایی را بشمارید.

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]]

روش نیوتن در 1 گام همگرا خواهد شد (چون برای توابع درجه دوم کاملاً دقیق عمل می‌کند). اما گرادیان کاهشی صدها گام طول خواهد کشید؛ زیرا مقادیر ویژه‌ی هسیان با ضریب 5 با یکدیگر تفاوت دارند و دره‌ای کشیده ایجاد می‌کنند.

کاربرد در دنیای واقعی

تحلیل کوژی مستقیماً هنگام انتخاب مدل‌ها و بهینه‌سازهای یادگیری ماشین کاربرد دارد.

برای مسئله‌های کوژ (رگرسیون لجستیک، SVM، LASSO):

• از بهینه‌سازهای اختصاصی استفاده کنید (liblinear، CVXPY یا scipy.optimize.minimize با متد method='L-BFGS-B')
• انتظار یک جواب بهینه‌ی سراسری یکتا را داشته باشید
• روش‌های مرتبه دوم عملی و بسیار سریع هستند

برای مسئله‌های ناکوژ (شبکه‌های عصبی):

• از روش‌های مرتبه اول استفاده کنید (SGD، Adam)
• بپذیرید که پاسخ مدل به مقداردهی اولیه و متغیرهای تصادفی وابسته است
• از پارامترسازی بیش از حد، نوفه و زمان‌بندی نرخ یادگیری به‌عنوان منظم‌سازی ضمنی کمک بگیرید
• وقت خود را برای پیدا کردن کمینه‌ی سراسری هدر ندهید؛ یک کمینه‌ی محلی مناسب کاملاً کافی است.

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ها، فرمول‌بندی دوگان امکان استفاده از ترفند کرنل را فراهم می‌کند:

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. گالری توابع کوژ. کوژ بودن این توابع را با بررسی‌کننده‌ی ساخته‌شده بیازمایید: $f(x) = x^4$، $f(x) = \sin(x)$، $f(x,y) = x^2 + y^2$، $f(x,y) = xy$، $f(x) = \max(x, 0)$. دلیل منطقی هر پاسخ را شرح دهید.

2. مسابقه‌ی روش نیوتن و گرادیان کاهشی. هر دو روش را روی تابع $f(x,y) = 50x^2 + y^2$ با نقطه‌ی شروع $(10, 10)$ اجرا کنید. هر کدام به چند گام نیاز دارند تا مقدار زیان را به کمتر از 1e-10 برسانند؟ اگر عدد حالت (نسبت بزرگ‌ترین مقدار ویژه‌ی هسیان به کوچک‌ترین آن) افزایش یابد، چه بر سر گرادیان کاهشی می‌آید؟

3. هندسه‌ی ضرایب لاگرانژ. تابع $f(x,y) = (x-3)^2 + (y-3)^2$ را مشروط به $x + 2y = 4$ کمینه کنید. با بررسی موازی بودن گرادیان $f$ با گرادیان $g$ در جواب به‌دست‌آمده، درستی آن را تأیید کنید.

4. قید منظم‌سازی. بهینه‌سازی با قید L1 را پیاده‌سازی کنید: کمینه‌سازی $(x-3)^2 + (y-2)^2$ مشروط به $\lvert x \rvert + \lvert y \rvert \le 1$. نشان دهید که در نقطه‌ی بهینه، یکی از مختصات دقیقاً صفر می‌شود (ایجاد تنکی ناشی از قید لوزی‌شکل).

5. تحلیل مقادیر ویژه‌ی هسیان. ماتریس هسیان تابع روزن‌بروک (Rosenbrock) را در دو نقطه‌ی (1,1) و (-1,1) محاسبه کنید و مقادیر ویژه‌ی آن را به دست آورید. این مقادیر ویژه چه نکاتی را درباره‌ی انحنای تابع در نقطه‌ی کمینه در مقایسه با نقاط دورتر نشان می‌دهند؟

راهنمایی‌ها

تمرین 1. پیش از اجرای check_convexity نتیجه را پیش‌بینی کنید: در حالت یک‌بعدی به علامت $f''(x)$ نگاه کنید؛ در حالت دوبعدی مقادیر ویژه‌ی هسیان را بررسی کنید. برای تابع $f(x,y) = xy$، هسیان مقادیر ویژه‌ی 1 و -1 دارد؛ بنابراین بررسی‌کننده باید گزارش دهد که تابع کوژ نیست.

تمرین 2. توابع optimize_gd و newtons_method را با گرادیان و ماتریس هسیانِ $f$ فراخوانی کنید. روش نیوتن یک تابع درجه دو را در یک گام حل می‌کند. در گرادیان کاهشی، نرخ یادگیری به‌خاطر عبارت $50x^2$ باید کمتر از $2/100$ باشد؛ بنابراین حرکت در جهت $y$ کند خواهد بود. کار را با $100x^2$ تکرار کنید و تعداد گام‌ها را دوباره بشمارید.

تمرین 3. از lagrange_solve با ورودی $g(x,y) = x + 2y - 4$ استفاده کنید. در جواب به‌دست‌آمده بررسی کنید که $x + 2y = 4$ باشد و $\nabla f = (2(x-3), 2(y-3))$ مضربی از $\nabla g = (1, 2)$ درآید.

تمرین 4. کمینه‌ی نامقید در (3, 2) بیرون از لوزی قرار دارد، بنابراین جواب حتماً روی مرز لوزی است. از گرادیان کاهشی تصویرشده (projected gradient descent) استفاده کنید: یک گام گرادیانی بردارید، سپس نقطه را روی $\lvert x \rvert + \lvert y \rvert \le 1$ تصویر کنید. بررسی کنید که جواب در قید با تساوی صدق کند و آن را با demo_regularization_geometry مقایسه کنید.

تمرین 5. تابع rosenbrock_hessian را در هر نقطه فراخوانی کنید و خروجی را به hessian_eigenvalues_2d بدهید. در نقطه‌ی (1, 1)، هر دو مقدار ویژه مثبت‌اند و نسبت آن‌ها بسیار بزرگ است؛ این یعنی دره در یک جهت باریک و در جهت دیگر مسطح است. این نسبت را با نسبت حاصل در (-1, 1) مقایسه کنید.

اصطلاحات کلیدی

برای مطالعه‌ی بیشتر

• کتاب Boyd & Vandenberghe: Convex Optimization — کتاب مرجع استاندارد که به‌رایگان آنلاین در دسترس است
• مقاله‌ی Bottou, Curtis, Nocedal: Optimization Methods for Large-Scale Machine Learning (2018) — پیوند میان نظریه‌ی بهینه‌سازی کوژ و کاربرد عملی آن در یادگیری عمیق
• مقاله‌ی Choromanska et al.: The Loss Surfaces of Multilayer Networks (2015) — چرایی عملکرد مناسب چشم‌اندازهای ناکوژ در شبکه‌های عصبی
• کتاب Nocedal & Wright: Numerical Optimization — مرجعی جامع پیرامون روش نیوتن، L-BFGS و بهینه‌سازی مقید