اکسترمم‌ها

فهرست مطالب

19.1 مقدمه
19.2 سخنرانی
19.3 مثال‌ها
تمرین‌ها

19.1 مقدمه

19.1.1 بررسی یادگیری به عنوان یک فرآیند بهینه‌سازی

یادگیری یک فرآیند بهینه‌سازی با هدف افزایش دانش، مهارت‌ها و قدرت خلاقیت است. این امر هم برای آموزش و هم برای یادگیری ماشین صدق می‌کند. برای ردیابی فرآیند یادگیری، به تابعی نیاز داریم که پیشرفت را اندازه‌گیری کند. یک معیار قدیمی، معدل (GPA) است که میانگین برخی نمرات در یک سیستم آموزشی را محاسبه می‌کند، و معیار دیگر نمرات IQ است که با انجام آزمون‌ها اندازه‌گیری می‌شود. یک مثال دیگر از معیار در یک محیط تحقیقاتی، امتیاز شبکه اجتماعی مانند تعداد استنادها یا شاخص h است. برای خودرویی که به طور خودران رانندگی می‌کند، می‌تواند تابع $f (x) = 100 / (1 + N (x))$ باشد که در آن $N (x)$ تعداد تصادفات ایجاد شده با استفاده از پیکربندی پارامتر $x$ در یک دوره زمانی ثابت است.

**شکل 1.** تصویر کلوندایک از دیوید پرکینز جستجوی راه‌حل‌ها را در یک چشم‌انداز با ابعاد بالاتر که توسط تابع ارتفاع $f$ تعریف شده است، نشان می‌دهد. حساب دیفرانسیل و انتگرال پیشنهاد می‌کند که از گرادیان $\nabla f$ پیروی کنیم زیرا این کار به **بیشینه‌های محلی** منجر می‌شود. برای یافتن بیشینه‌های سراسری (که می‌توانند ایده‌های پیشگامانه باشند)، باید سخت‌تر جستجو کنیم و فهرستی از همه بیشینه‌ها تهیه کنیم. این فرآیند به نام منطقه کلوندایک در کانادا نامگذاری شده است که در طول تب طلا بدنام شد.

19.1.2 آیا هوش مصنوعی بر همه حوزه‌ها غلبه خواهد کرد؟

هنگامی که چارچوب و تابع $f$ ثابت شد، سوال این است که چگونه $f$ را به طور مؤثرتری افزایش دهیم. این تصویر ساده‌انگارانه هم برای هوش انسانی و هم برای هوش مصنوعی کاملاً مؤثر است. برای بسیاری از توابعی که در نظر گرفته شده‌اند (برنده شدن در بازی‌های شطرنج، قدرت محاسباتی، نگهداری داده‌ها، تشخیص ویژگی، رانندگی با خودرو یا پرواز با هواپیما)، ماشین‌ها به سرعت پیشرفت کردند. به ندرت کسی وجود دارد که به طور جدی شک کند که انسان‌ها در نهایت برای هر تابع $f$ که قابل تصور است، نبرد را خواهند باخت. هنوز حوزه‌هایی وجود دارند که ماشین‌ها در آنها تسلط پیدا نکرده‌اند. نمونه‌هایی از آن هنر یا نوشتن مقالات علمی هستند.¹

19.1.3 مزیت یادگیری ماشین در بهینه‌سازی مبتنی بر گرادیان

هنگامی که یک ماشین تابع $f$ را می‌شناسد، می‌تواند به راحتی از یک موقعیت $x$ تعیین کند که برای افزایش $f$ در کدام جهت تغییر کند. جهت سریع‌ترین افزایش جهت گرادیان $\nabla f$ تابع $f$ است. در حساب دیفرانسیل و انتگرال، به موقعیت‌هایی نگاه می‌کنیم که موقعیت فقط از چند متغیر تشکیل شده است. حساب دیفرانسیل و انتگرال تک متغیره با وضعیت یک متغیر سروکار دارد. ما در اینجا به وضعیت با $n$ متغیر نگاه می‌کنیم اما بیشتر با $2$ متغیر کار خواهیم کرد زیرا این کار ایده اصلی را ارائه می‌دهد. اصل این است که به یک بهینه رسیده‌ایم که در آن هیچ تغییری دیگر نمی‌تواند تابع $f$ را افزایش دهد. این از نظر ریاضی به این معنی است که مشتق $d f$ تابع $f$ صفر است. ما چنین نقاطی را "نقاط بحرانی" می‌نامیم.

19.1.4 استفاده از گرادیان‌ها برای یافتن جهت بهبود

اجازه دهید ابتدا به نرخ تغییر یک تابع در امتداد یک جهت $v$ نگاه کنیم. یک منحنی $r (t) = x + t v$ را در نظر بگیرید که در آن $v$ یک بردار واحد است. با قاعده زنجیره‌ای، نرخ تغییر در $x$ به صورت زیر داده می‌شود: ما برای ضرب داخلی می‌دانیم که این برابر است با $| \nabla f (x) | | v | \cos (α) = | \nabla f (x) | \cos (α) .$ این مقدار برای $\cos (α) = 1$ بیشینه می‌شود، به این معنی که $v$ در همان جهت $\nabla f$ اشاره می‌کند. بنابراین، گرادیان به سمت جهت حداکثر افزایش اشاره می‌کند. این مهم است که به خاطر بسپارید. اگر در یک چشم‌انداز هستید که توسط ارتفاع $f (x)$ داده شده است، برای افزایش بیشتر باید به سمت $\nabla f (x) / | \nabla f (x) |$ بروید. البته، این اگر $\nabla f (x) = 0$ باشد منطقی نیست، اما این وضعیتی است که در یک بیشینه هستید و دیگر نمی‌توانید $f$ را افزایش دهید.

19.2 سخنرانی

19.2.1 یافتن بهینه‌ها با گرادیان‌ها

همه توابع در اینجا فرض می‌شوند که در $C^{2}$ باشند، به این معنی که دو بار پیوسته مشتق‌پذیر هستند. همه چیز با یک مشاهده شروع می‌شود که به پیر دو فرما برمی‌گردد:

قضیه 1. اگر $x_{0}$ یک بیشینه از $f : ℝ^{m} \to ℝ$ باشد، آن‌گاه $\nabla f (x_{0}) = 0$ .

اثبات. ما این را با برهان خلف اثبات می‌کنیم. فرض کنید $\nabla f (x_{0}) \neq 0$ ، بردار $v =$ $\nabla f (x_{0})$ را تعریف کنید و به $g (t) = f (x_{0} + t v)$ نگاه کنید، که تابعی از یک متغیر است. با قاعده زنجیره‌ای، این تابع را برآورده می‌کند. این بدان معنی است که $f (x_{0} + t v) > 0$ برای $t > 0$ کوچک. نقطه $x_{0}$ نمی‌توانسته بیشینه بوده باشد. این یک تناقض است. ◻

19.2.2 آشکارسازی نقاط بحرانی

نقطه $x$ با $\nabla f (x) = 0$ یک نقطه بحرانی از $f$ نامیده می‌شود. با فرمول تیلور، در یک نقطه بحرانی $x_{0}$ تقریب درجه دوم $Q (x) = f (x_{0}) + (x - x_{0})^{T} H (x_{0}) (x - x_{0}) / 2$ را داریم، که در آن $H (x_{0})$ ماتریس هسین $H (x_{0}) = [\begin{array}{llll} f_{x_{1} x_{1}} & f_{x_{1} x_{2}} & \dots & f_{x_{1} x_{m}} \\ f_{x_{2} x_{1}} & f_{x_{2} x_{2}} & \dots & f_{x_{2} x_{m}} \\ \dots & \dots & \dots & \dots \\ f_{x_{m} x_{1}} & f_{x_{m} x_{2}} & \dots & f_{x_{m} x_{m}} \end{array}]$ است.

19.2.3 آزمون مشتق دوم وارد عمل می‌شود

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

19.2.4 ماتریس‌های معین مثبت و معین منفی

یک ماتریس $A$ معین مثبت نامیده می‌شود اگر $v \cdot A v > 0$ برای همه بردارهای $v \neq 0$ باشد. معین منفی نامیده می‌شود اگر $v \cdot A v < 0$ برای همه بردارهای $v \neq 0$ باشد. یک ماتریس قطری با درایه‌های قطری مثبت معین مثبت است. در عبارات زیر، فرض می‌کنیم $x_{0}$ یک نقطه بحرانی است.

19.2.5 آشکارسازی نقش هسین‌های معین مثبت

می‌گوییم $x_{0}$ یک بیشینه محلی از $f$ است اگر $r > 0$ وجود داشته باشد به طوری که $f (x) \leq f (x_{0})$ برای همه $| x - x_{0} | < r$ . می‌گوییم، یک کمینه محلی از $f$ است اگر $f (x) \geq f (x_{0})$ برای همه $| x - x_{0} | < r$ . چگونه می‌توانیم بررسی کنیم که یک نقطه بیشینه یا کمینه محلی است؟

قضیه 2. فرض کنید $\nabla f (x_{0}) = 0$ . اگر $H (x_{0})$ معین مثبت باشد، آن‌گاه $x_{0}$ یک کمینه محلی است. اگر $H (x_{0})$ معین منفی باشد، آن‌گاه $x_{0}$ یک بیشینه محلی است.

اثبات. از آنجایی که $\nabla f (x_{0}) = 0$ ، تقریب درجه دوم در $x_{0}$ به صورت $Q (x) = f (x_{0}) + H (x_{0}) v \cdot v / 2 > f (x_{0})$ برای $v = x - x_{0}$ غیرصفر کوچک و هسین $H$ است. عبارت مشابه برای کمینه را می‌توان با جایگزینی $f$ با $- f$ استنتاج کرد. ◻

19.2.6 طبقه‌بندی نقاط اکسترمم در دو بعد

اجازه دهید به حالتی نگاه کنیم که $f (x, y)$ تابعی از دو متغیر است به طوری که $f_{x} (x_{0}, y_{0}) = 0$ و $g_{x} (x_{0}, y_{0}) = 0$ . ماتریس هسین به صورت $H (x_{0}, y_{0}) = [\begin{array}{ll} f_{x x} & f_{x y} \\ f_{y x} & f_{y y} \end{array}]$ است.

در این حالت دو بعدی، می‌توانیم نقاط بحرانی را اگر دترمینان $D = \det (H) = f_{x x} f_{y y} - f_{x y}^{2}$ از $H$ غیرصفر باشد، طبقه‌بندی کنیم. عدد $D$ همچنین ممیز در یک نقطه بحرانی نامیده می‌شود.

**شکل 2.** $f = x^{2} + y^{2}$ یک کمینه، $f = - x^{2} - y^{2}$ یک بیشینه و $f = x^{2} - y^{2}$ یک زین اسبی را نشان می‌دهد. حالت $f = x^{2} y - y x^{2}$ مورس نیست.

19.2.7 توابع مورس و آزمون مشتق دوم

می‌گوییم $(x_{0}, y_{0})$ یک نقطه مورس است، اگر $(x_{0}, y_{0})$ یک نقطه بحرانی باشد و دترمینان غیرصفر باشد. یک تابع $C^{2}$ یک تابع مورس است اگر هر نقطه بحرانی مورس باشد. نمونه‌هایی از توابع مورس عبارتند از $f (x, y) = x^{2} + y^{2}$ ، $f (x, y) = - x^{2} - y^{2}$ و $f (x, y) = x^{2} - y^{2}$ . حالت آخر یک زین اسبی هذلولوی نامیده می‌شود. به طور کلی، یک نقطه بحرانی یک زین اسبی هذلولوی است اگر $D \neq 0$ باشد و اگر نه بیشینه باشد و نه کمینه. در اینجا آزمون مشتق دوم در بعد $2$ آمده است:

قضیه 3. فرض کنید $f \in C^{2}$ یک نقطه بحرانی $(x_{0}, y_{0})$ با $D \neq 0$ داشته باشد.

اگر $D > 0$ و $f_{x x} > 0$ آن‌گاه $(x_{0}, y_{0})$ یک کمینه محلی است.
اگر $D > 0$ و $f_{x x} < 0$ آن‌گاه $(x_{0}, y_{0})$ یک بیشینه محلی است.
اگر $D < 0$ آن‌گاه $(x_{0}, y_{0})$ یک زین اسبی هذلولوی است.

اثبات. پس از انتقال $(x, y) \to (x - x_{0}, y - y_{0})$ و جایگزینی $f$ با $f -$ $f (x_{0}, y_{0})$ ، داریم $(x_{0}, y_{0}) = (0, 0)$ و $f (0, 0) = 0$ . در نقطه بحرانی، تقریب درجه دوم اکنون $Q (x, y) = a x^{2} + 2 b x y + c y^{2}$ است. این را می‌توان به صورت $a (x + \frac{b}{a} y)^{2} + (c - \frac{b^{2}}{a}) y^{2} = a (A^{2} + D B^{2})$ با $A = (x + \frac{b}{a} y), B = b^{2} / a^{2}$ و ممیز $D$ بازنویسی کرد. اگر $a = f_{x x} > 0$ و $D > 0$ آن‌گاه $c - b^{2} / a > 0$ و تابع برای همه $(x, y) \neq (0, 0)$ مقادیر مثبت دارد. نقطه $(0, 0)$ آن‌گاه یک کمینه است. اگر $a = f_{x x} < 0$ و $D > 0$ ، آن‌گاه $c - b^{2} / a < 0$ و تابع برای همه $(x, y) \neq (0, 0)$ مقادیر منفی دارد و نقطه $(x, y)$ یک بیشینه محلی است. اگر $D < 0$ ، آن‌گاه $f$ در نزدیکی $(0, 0)$ مقادیر منفی و مثبت می‌گیرد. ◻

19.2.8 از هسین تا انحنای گاوس

می‌توان پرسید، چرا $f_{x x}$ انتخاب شده است و نه $f_{y y}$ . مهم نیست، زیرا اگر $D > 0$ ، آن‌گاه هر دو $f_{x x}$ و $f_{y y}$ باید غیرصفر باشند و علامت یکسانی داشته باشند. به جای $f_{x x}$ ، می‌توانستیم اثر طبیعی‌تر $tr (H)$ را نیز انتخاب کنیم. این تحت تغییرات مختصات مشابه دترمینان $D$ ناوردا است. ممیز $D$ همچنین انحنای گاوس سطح در آن نقطه است.

19.2.9 لم مورس

در ابعاد بالاتر، وضعیت توسط لم مورس توصیف می‌شود. این لم می‌گوید که در نزدیکی یک نقطه بحرانی، یک تغییر مختصات $ϕ$ وجود دارد به طوری که $g (x) = f (ϕ (x))$ یک تابع درجه دوم $f (x) = B (x - x_{0}) \cdot (x - x_{0})$ است که در آن $B$ قطری با درایه‌های $+ 1$ یا $- 1$ است. سپس می‌توان به نقطه بحرانی یک شاخص مورس نسبت داد که تعداد درایه‌های $- 1$ در $B$ است. لم مورس در واقع یک قضیه است (قضایا از لم‌ها=قضایای کمکی مهم‌تر هستند).

قضیه ۴. در نزدیکی یک نقطه بحرانی مورس $x_{0}$ از یک تابع $C^{2}$ به نام $f$ ، یک تغییر مختصات $ϕ : ℝ^{m} \to ℝ^{m}$ وجود دارد به طوری که $g (x) = f (ϕ (x)) - f (x_{0})$ برابر است با $g (x) = - x_{1}^{2} - \dots - x_{k}^{2} + x_{k + 1}^{2} + \dots + x_{m}^{2} .$

اثبات. از استقرا نسبت به $m$ استفاده می‌کنیم.

پایه استقرا: برای $m = 1$ ، نتیجه می‌گوید که برای یک نقطه بحرانی مورس، تابع به صورت $y = x^{2}$ یا $y = - x^{2}$ است. ابتدا نشان می‌دهیم که اگر ، ، آنگاه $f (x) = x^{2} h (x)$ یا $f (x) = - x^{2} h (x)$ برای یک تابع $C^{2}$ مثبت $h$ است. اثبات. با یک تغییر مختصات خطی فرض می‌کنیم $x_{0} = 0$ و $f (0) = 0$ . آنگاه $g (x)$ وجود دارد به طوری که $f (x) = x g (x)$ : این $g (x) = f (x) / x$ برای $x \neq 0$ است و در حد $x \to 0$ مقدار $lim_{x \to 0} (f (x) -$ است. با قاعده ضرب، با $g (0) = 0$ . چون می‌توان $f (x) / x^{2}$ را برای $x \neq 0$ تعریف کرد و حد $x \to 0$ را گرفت، زیرا با اعمال دو بار هوپیتال، حد برابر است. تغییر مختصات اکنون توسط تابعی $y = ϕ (x)$ داده می‌شود که در $g (x, y) = y \sqrt{h (y)} = x$ صدق می‌کند. مشتق‌گیری ضمنی $g_{y} (0, 0) = \sqrt{h (y)} \neq 0$ را می‌دهد، بنابراین با قضیه تابع ضمنی $y (x)$ وجود دارد.
گام استقرا $𝒎 \to 𝒎 + 1$ : ابتدا توجه می‌کنیم که تیلور برای $C^{2}$ با جمله باقی‌مانده دلالت بر این دارد که $f (x_{1}, \dots, x_{n}) = \sum_{i, j} x_{i} x_{j} h_{i j} (x_{1}, \dots, x_{n})$ با برخی توابع پیوسته $h_{i j}$ . علاوه بر این، مقدار تابع $h_{i j} (0) = f_{x_{i} x_{j}} (0) = H_{i j} (0)$ مختصات هسین هستند. ابتدا یک چرخش اعمال کنید تا $h_{11} \neq 0$ . حال به $x_{1}$ نگاه کنید و سایر مختصات را ثابت نگه دارید. مانند (i)، یک تغییر مختصات $ϕ$ پیدا کنید به طوری که $f (ϕ (x)) = \pm x_{1}^{2} + g (x_{2}, \dots, x_{m})$ ، که در آن $g$ ویژگی‌های $f$ را به ارث می‌برد اما یک بعد کمتر دارد. با فرض استقرا، یک تغییر مختصات دوم وجود دارد به طوری که $g (ψ (x)) = x_{2}^{2} - \dots - x_{l}^{2} + x_{l + 1}^{2} + \dots + x_{m}^{2} .$ ترکیب $ϕ$ و $ψ$ فرم نرمال مورس را تولید می‌کند.

◻

۱۹.۳ مثال‌ها

مثال ۱. سوال: نقاط بحرانی $f (x, y) = x^{3} - 3 x - y^{3} - 3 y$ را طبقه‌بندی کنید.
پاسخ: از آنجایی که $\nabla f (x, y) = {[3 x^{2} - 3, - 3 y^{2} + 3]}^{T}$ است، نقاط بحرانی عبارتند از $(1, 1)$ ، $(- 1, 1)$ ، $(1, - 1)$ و $(- 1, - 1)$ . ما محاسبه می‌کنیم $H (x, y) = [\begin{array}{cc} 2 x & 0 \\ 0 & - 2 y \end{array}] .$ برای $(1, 1)$ و $(- 1, - 1)$ داریم $D = - 4$ و بنابراین نقاط زینی هستند. برای $(- 1, 1)$ ، داریم $D = 4$ ، $f_{x x} = - 2$ ، یک بیشینه محلی. برای $(1, - 1)$ که در آن $D = 4$ ، $f_{x x} = 2$ داریم یک کمینه محلی.

تمرین‌ها

تمرین ۱.

نقاط بحرانی تابع $f (x, y) = x^{2} + y^{3} - x y$ را طبقه‌بندی کنید. (بیشینه، کمینه یا نقاط زینی).
حال همین کار را برای $f (x, y, z) = x^{2} + y^{3} - x y + z^{2}$ انجام دهید و شاخص مورس را در هر نقطه بحرانی پیدا کنید.

تمرین ۲. تمام نقاط بحرانی تابع $3$ بعدی منطقه $51$ $f (x, y, z) = x^{51} - 51 x + y^{51} - 51 y + z^{51} - 51 z$ را پیدا کنید. هسین $H = d^{2} f$ را در هر نقطه بحرانی محاسبه کنید و بیشینه‌ها (همه مقادیر ویژه منفی) و کمینه‌ها (همه مقادیر ویژه مثبت) را تعیین کنید.
پ.ن. منطقه $51$ یک موضوع قدیمی است. اما منطقه $3$ بعدی $51$ هنوز بسیار طبقه‌بندی شده است و شایعه شده است که در نزدیکی سمت تاریک ماه قرار دارد.

تمرین ۳. روی سطح پارامتری $r (u, v) = [u^{2}, v^{3}, u v]$ دما $T (x, y, z) = 12 x + y - 12 z$ در کجا کمینه است. تمام نقاط بحرانی تابع $f (u, v) = T (r (u, v))$ را طبقه‌بندی کنید. [اگر تابع $f (u, v)$ را پیدا کرده‌اید، می‌توانید دوباره $u$ و $v$ را با $x$ و $y$ جایگزین کنید اگر ترجیح می‌دهید با یک تابع $f (x, y)$ کار کنید.]

تمرین ۴. تمام نقاط بحرانی تابع $f (x, y, z) = (x - 1)^{2} - y^{2} + x z^{2}$ را پیدا کنید. در هر یک از موارد، ماتریس هسین را پیدا کنید. همچنین در اینجا مقادیر ویژه را محاسبه کنید. اینها اعداد $λ$ هستند به طوری که $H v = λ v$ برای یک بردار غیرصفر. می‌توان آنها را با جستجوی ریشه‌های چندجمله‌ای مشخصه $χ_{H} (λ) = \det (L - λ)$ پیدا کرد. می‌توانید آنها را روی کامپیوتر محاسبه کنید. در هر مورد مقادیر ویژه را پیدا کنید.

تمرین ۵.

یک تابع $f (x, y)$ با $3$ بیشینه و $3$ نقطه زینی و یک کمینه پیدا کنید.
در زیر یک نقشه کانتور از یک تابع دو متغیره می‌بینید. چند نقطه بحرانی وجود دارد؟ آیا تابع یک تابع مورس است؟

ممکن است مقاومت وجود داشته باشد: انسان‌ها ممکن است تصمیم بگیرند که به پیشرفت‌های علمی توسط ماشین‌ها استناد نکنند. از سوی دیگر، چه کسی نمی‌خواهد یک "نظریه همه چیز" را یاد بگیرد حتی اگر توسط یک ماشین کشف شده باشد؟↩︎