ماتریس‌ها و مشتق: حل مسأله

نوشته شده در ۹ بهمن ۱۳۹۷

عمده‌ی کارکرد مشتق‌گیری، یافتن نقاط اکسترموم است؛ اما نحوه‌ی استفاده از مشتق برای رسیدن به اکسترموم می‌تواند یا از طریق روش‌های iterative بهینه‌سازی باشد یا حل فرمال معادلات. برای اینکه از هر کدام از این موارد یک مثال دیده باشیم، اول مقدار ماتریس correlation را از روی تعدادی نمونه از یک توزیع گوسی تخمین می‌زنیم و بعدش گرادیان یک MLP را نسبت به وزن‌هایش محاسبه می‌کنیم.

تخمین ماتریس correlation

فرمول توزیع گوسی چند متغیره چیزی است که در زیر آمده:

$$p(x|\mu ,\mathrm{\Sigma })=\text{det}(2\pi \mathrm{\Sigma }{)}^{-\frac{1}{2}}\text{exp}(-\frac{1}{2}(x-\mu {)}^T{\mathrm{\Sigma }}^{-1}(x-\mu ))$$

خب حالا اگر نمونه‌های $x_1$ تا $x_n$ از این توزیع داشته باشیم، چه مقادیری از $\mu$ و $\mathrm{\Sigma }$ احتمال رخداد این نمونه‌ها را بیشینه می‌کنند؟

با فرض اینکه نمونه‌ها از هم مستقل باشند، احتمال رخداد همه‌شان می‌شود:

$$\begin{array}{cc}& p(x_1,x_2,\dots x_n|\mu ,\mathrm{\Sigma })=\prod p(x_i|\mu ,\mathrm{\Sigma })\\ & \text{log}(p(x_1,x_2,\dots x_n|\mu ,\mathrm{\Sigma }))=\sum \text{log}(p(x_i|\mu ,\mathrm{\Sigma }))\end{array}$$

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

$$\text{log}(p(x_1,x_2,\dots x_n|\mu ,\mathrm{\Sigma }))=\sum [\text{log}(\text{det}(2\pi \mathrm{\Sigma }{)}^{-\frac{1}{2}})-\frac{1}{2}(x_i-\mu {)}^T{\mathrm{\Sigma }}^{-1}(x_i-\mu )]$$

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

$$\begin{array}{cc}y& =\text{log}(p(x_1,x_2,\dots x_n|\mu ,\mathrm{\Sigma }))\\ & =-\frac{n}{2}\text{log}\left(2^m{\pi }^m\right)-\frac{n}{2}\text{log}(\text{det}(\mathrm{\Sigma }))-\frac{1}{2}\sum (x_i-\mu {)}^T{\mathrm{\Sigma }}^{-1}(x_i-\mu )\end{array}$$

برای این ساده‌سازی، من اول عبارت دترمینان را که ربطی به اندیس جمع نداشت از جمع خارج کردم که طبیعتاً ضرب در تعداد دفعات جمع خوردن می‌شود (یعنی $n$). بعدش $-\frac{1}{2}$ را از لگاریتم خارج کردم که بصورت ضرب ظاهر شود. در مرحله‌ی بعد، $\text{det}(2\pi \mathrm{\Sigma })$ را با استفاده از رابطه‌ی $\text{det}(kA)=k^n\text{det}(A)$ ساده کردم. در نهایت هم ضریب $-\frac{1}{2}$ را از درون جمع به بیرون انتقال دادم که به دلیل خاصیت پخشی ضرب امکان‌پذیر است (توجه کرده‌اید که $n$ تعداد نمونه‌ها و $m$ تعداد عناصر هر نمونه است؟)

حالا کافیست دو تا مشتق بگیریم و برابر صفر قرار دهیم. یکی نسبت به $\mu$(یک بردار) و دیگری نسبت به $\mathrm{\Sigma }$ (یک ماتریس). اول با بردار شروع می‌کنیم:

$$\begin{array}{cc}& \frac{\partial y}{\partial \mu }=-\frac{1}{2}({\mathrm{\Sigma }}^{-1}+{\mathrm{\Sigma }}^{-T})((\sum x_i)-n\mu )=0\\ & \Rightarrow \mu =\frac{1}{n}\sum x_i\end{array}$$

به همین سرعت محاسبه شد! می‌دانید چرا به ${\mathrm{\Sigma }}^{-1}$ و همزادش ${\mathrm{\Sigma }}^{-T}$ محل ندادم؟ چون طبق فرمول، این ماتریس‌ها معکوس‌پذیرند و فقط در یک حالت حاصل ضرب آن‌ها در یک بردار برابر صفر می‌شود و آن وقتی است که خود آن بردار صفر باشد؛ یعنی $(\sum x_i)-n\mu =0$. اما مشتق دوم که جذاب‌تر هم هست:

$$\begin{array}{cc}& \frac{\partial y}{\partial \mathrm{\Sigma }}=\frac{\partial y}{\partial {\mathrm{\Sigma }}^{-1}}\frac{\partial {\mathrm{\Sigma }}^{-1}}{\partial \mathrm{\Sigma }}\\ & \frac{\partial y}{\partial {\mathrm{\Sigma }}^{-1}}=-\frac{n}{2}{\text{vec}}^T({\mathrm{\Sigma }}^T)-\frac{1}{2}\sum ((x_i-\mu {)}^T\otimes (x_i-\mu {)}^T)\\ & \frac{\partial {\mathrm{\Sigma }}^{-1}}{\partial \mathrm{\Sigma }}=-({\mathrm{\Sigma }}^{-T}\otimes {\mathrm{\Sigma }}^{-1})\\ & \Downarrow \\ & \frac{\partial y}{\partial \mathrm{\Sigma }}=\begin{array}{cc}& \frac{n}{2}{\text{vec}}^T({\mathrm{\Sigma }}^T)({\mathrm{\Sigma }}^{-T}\otimes {\mathrm{\Sigma }}^{-1})\\ & +\frac{1}{2}\sum ((x_i-\mu {)}^T\otimes (x_i-\mu {)}^T)({\mathrm{\Sigma }}^{-T}\otimes {\mathrm{\Sigma }}^{-1})\end{array}\end{array}$$

از طول و درازای فرمول بالا نترسید، در دلش چیزی نیست. کافیست از رابطه‌ی زیر برای ساده‌سازی استفاده کنیم:

$$\text{vec}(AXB)=(B^T\otimes A)\text{vec}(X)$$

و یا معادلش:

$${\text{vec}}^T(AXB)={\text{vec}}^T(X)(B\otimes A^T)$$

با جایگذاری به نتیجه‌ی زیر می‌رسیم:

$$\frac{\partial y}{\partial \mathrm{\Sigma }}=\frac{n}{2}{\text{vec}}^T({\mathrm{\Sigma }}^{-T})+\frac{1}{2}[\sum ((x_i-\mu {)}^T\otimes (x_i-\mu {)}^T)]({\mathrm{\Sigma }}^{-T}\otimes {\mathrm{\Sigma }}^{-1})=0$$

یا به عبارتی:

$${\text{vec}}^T({\mathrm{\Sigma }}^{-T})({\mathrm{\Sigma }}^{-T}\otimes {\mathrm{\Sigma }}^{-1}{)}^{-1}=\frac{1}{n}\sum ((x_i-\mu {)}^T\otimes (x_i-\mu {)}^T)=0$$

باز هم همان رابطه‌ی $\text{vec}(AXB)$. در پست اول که گفتم، این رابطه در مشتق‌گیری خیلی کاربرد دارد:

$${\text{vec}}^T({\mathrm{\Sigma }}^{-T})({\mathrm{\Sigma }}^{-T}\otimes {\mathrm{\Sigma }}^{-1}{)}^{-1}={\text{vec}}^T({\mathrm{\Sigma }}^{-T})({\mathrm{\Sigma }}^T\otimes \mathrm{\Sigma })={\text{vec}}^T({\mathrm{\Sigma }}^T{\mathrm{\Sigma }}^{-T}{\mathrm{\Sigma }}^T)={\text{vec}}^T({\mathrm{\Sigma }}^T)$$

اورکا، اورکا:

$${\text{vec}}^T({\mathrm{\Sigma }}^T)=\frac{1}{n}\sum ((x_i-\mu {)}^T\otimes (x_i-\mu {)}^T)$$

باز هم $\text{vec}(AXB)$! اگر $X$ یک عدد اسکالر، $A$ یک بردار سطری ($n\times 1$) و $B$ یک بردار ستونی باشد، چه رابطه‌ای حاصل می‌شود؟

$$\begin{array}{cc}& \text{vec}(\alpha ab)=\text{vec}(a\alpha b)=(b^T\otimes a)\text{vec}(\alpha )=\alpha (b^T\otimes a)\\ & {\text{vec}}^T(\alpha ab)={\text{vec}}^T(a\alpha b)={\text{vec}}^T(\alpha )(b\otimes a^T)=\alpha (b\otimes a^T)\end{array}$$

زیبا نیست؟ با این حساب:

$$\begin{array}{cc}& (x_i-\mu {)}^T\otimes (x_i-\mu {)}^T={\text{vec}}^T((x_i-\mu )(x_i-\mu {)}^T)\\ & {\text{vec}}^T({\mathrm{\Sigma }}^T)=\frac{1}{n}\sum {\text{vec}}^T((x_i-\mu )(x_i-\mu {)}^T)\\ & {\text{vec}}^T({\mathrm{\Sigma }}^T)={\text{vec}}^T(\frac{1}{n}\sum ((x_i-\mu )(x_i-\mu {)}^T))\\ & \Rightarrow \mathrm{\Sigma }={\mathrm{\Sigma }}^T=\frac{1}{n}\sum ((x_i-\mu )(x_i-\mu {)}^T)\end{array}$$

در اینجا باید بپرسید که چرا $\mathrm{\Sigma }={\mathrm{\Sigma }}^T$؟ جوابش این است که وقتی ${\mathrm{\Sigma }}^T=\frac{1}{n}\sum ((x_i-\mu )(x_i-\mu {)}^T)$ باشد، ترانهاده‌اش برابر خودش می‌شود.

مشتق نسبت به وزن‌های MLP

لایه‌های یک شبکه‌ی MLP را می‌توان بصورت زیر نشان داد:

$$y_{n+1}=\varphi (W_n{y}_n+b_n)$$

بسته به این که MLP مورد نظر ما چند لایه باشد، وقتی می‌خواهیم آموزشش بدهیم، خروجی لایه‌ی $m$م را با نتایج دلخواه مقایسه می‌کنیم و خطا را محاسبه می‌کنیم. فرض کنیم که معیار خطای کمترین متوسط مربعات را در نظر داشته باشیم:

$$j(W_0,b_0,W_1,b_1,\dots W_{m-1},b_{m-1})=\frac{1}{2}\Vert y_m-y{\Vert }^2=\frac{1}{2}(y_m-y{)}^T(y_m-y)$$

از ماشین‌آلاتی که برای مشتق‌گیری ساختیم برای محاسبه‌ی $\frac{\partial j}{\partial W_i}$ استفاده می‌کنیم. محاسبه‌ی مشتق نسبت به بایاس‌ها هم کاملاً مشابه است:

$$\frac{\partial j}{\partial W_i}=\frac{\partial j}{\partial y_m}\left(\prod _{m-1}^i\frac{\partial y_{j+1}}{\partial y_j}\right)\frac{\partial y_i}{\partial W_i}$$

حالا کافیست هر جزء را محاسبه کنیم.

$$\begin{array}{cc}& \frac{\partial j}{\partial y_m}=(y_m-y{)}^T\\ & \frac{\partial y_{j+1}}{\partial y_j}=\text{diag}\left(\text{vec}({\varphi }^{\prime }(W_j{y}_j+b_j))\right)W_j\\ & \frac{\partial y_i}{\partial W_i}=(y_i^T\otimes I)\end{array}$$

یافتن اینکه این‌ها را چطور با استفاده از مطالبی که در سه پُست گذشته ارائه کردم محاسبه کرده‌ام به خود شما واگذار می‌کنم که بیابید (این خودش تمرین خوبی است.) اما مباحث از اینجا به بعد شیرین‌تر می‌شود. برای اینکه بتوانم ادامه بدهم باید یک رابطه‌ی جدید را معرفی کنم.

$$a\odot b=\text{diag}(a)b\Rightarrow (a\odot b{)}^T=b^T\text{diag}(a)$$

علامت $\odot$ نمایشگر ضرب هادامارد یا عنصربه‌عنصر است. از طرفی وقتی $W_j{y}_j+b_j$ یک بردار است، ${\varphi }^{\prime }$ هم رویش اعمال شود، باز هم خروجی یک بردار است، پس می‌شود کل مشتق بالا را اینگونه نوشت:

$$\frac{\partial j}{\partial W_i}=(y_m-y{)}^T(\prod \text{diag}({\varphi }^{\prime }(W_j{y}_j+b_j))W_j)(y_i^T\otimes I)$$

بد نیست ببینیم، آن $\prod$ در وسط در واقع چه بلایی سر مقدار خطا ($y_m-y$) می‌آورد. از خود خطا شروع می‌کنیم:

$$e_j^T=(y_m-y{)}^T\text{diag}({\varphi }^{\prime }(W_j{y}_j+b_j))W_j={((y_m-y)\odot {\varphi }^{\prime }(W_j{y}_j+b_j))}^T{W}_j$$

انگار هر عنصر از خطا، با مقدار مشتق تابع $\varphi$ به ازای همان عنصر وزن‌دهی می‌شود و بعدش بردار به دست آمده از سمت چپ در ماتریس وزن لایه‌ی قبلی ضرب می‌شود. این همان پس انتشار خطاست. هر عنصری از خطا، با وزن مربوطه، به یکی از گره‌های لایه‌ی زیرین مرتبط می‌شود. همین عملیات را می‌شود ادامه داد:

$$e_{j-1}^T=e_j^T\text{diag}({\varphi }^{\prime }(W_{j-1}{y}_{j-1}+b_{j-1}))W_{j-1}={(e_j\odot {\varphi }^{\prime }(W_j{y}_j+b_j))}^T{W}_{j-1}$$

باز هم مقدار خطای لایه‌ی بالا با مشتق $\varphi$ در لایه‌ی زیرین وزن‌دهی شده و به لایه‌ی پایین‌تر منتشر می‌شود. اگر با همین فرمان پیش برویم به خطای لایه‌ی مورد نظر یعنی $e_i$ می‌رسیم:

$$\frac{\partial j}{\partial W_i}=e_i^T(y_i\otimes I)={\text{vec}}^T(e_i{y}_i^T)$$

تمرین خوبی است که ببینید چرا رابطه‌ی بالا برقرار است. بررسی اینکه $\text{vec}(e_i)$ چه فرمی دارد در این مورد نقطه‌ی شروع است. بگذریم.

در نهایت این مقدار مشتق چه کاربردی دارد؟ از آن در بهینه‌سازی و رفتن به سمت مقدار آموزش دیده‌ی وزن‌ها استفاده می‌کنیم. در روش‌های بهینه‌سازی مبتنی بر گرادیان، همیشه مقدار گرادیان خطا نسبت به پارامترها با نسبتی منفی جمع می‌شود. این اساس همه‌ی روش‌های بهینه‌سازی مبتنی بر گرادیان است. اما در اینجا گرادیان نسبت به $W_i$ ابعادی مشابه با $W_i$ ندارد؛ چگونه باید این دو را جمع بزنیم؟

اگر از ابتدا سراغ تنسورها رفته بودیم، این مشکل پیش نمی‌آمد. مقدار مشتق هم ابعادی برابر با خود $W_i$ می‌داشت (صد البته چون $j$ یک عدد اسکالر است.) حالا هم اتفاق خاصی نیفتاده. یادتان هست که برای تعریف اینگونه مشتق‌گیری که در این چهار پُست با هم مرورش کردیم، از ابتدا قرار گذاشتیم که هر ماتریس را با یک زوج مرتب $(\text{vec}(A),(m,n))$ نمایش بدهیم. الآن هم که مشتق را داریم، ابعاد ماتریس‌های $W_i$ را هم که داریم. کافیست مشتق محاسبه شده را با ابعاد ماتریس اولیه باز نمایی کنیم. تعداد عناصر مشتق طبق تعریف یکی است.

نکته‌ی جالب ماجرا اینجاست که تا الآن که این پست را می‌نویسم، بدون استثنا، باز مرتب‌سازی مشتق برای من برابر با نگاه کردن به درون عملگر $\text{vec}$ بوده است. همین مثال MLP را نگاه کنید:

$$\frac{\partial j}{\partial W_i}=e_i^T(y_i\otimes I)={\text{vec}}^T(e_i{y}_i^T)$$

مقدار $e_i{y}_i^T$ ابعادی دقیقاً برابر ماتریس اولیه دارد!

نتایج اخلاقی

در نهایت این نتایج را به عنوان خلاصه تقدیم می‌کنم:

۱-برای گرفتن مشتق نسبت به ماتریس نیازی به محاسبات تنسوری نیست ۲-مشتق‌گرفتن برای ورزش ذهنی خوب است ۳-اصولاً اکثر اوقات نیاز نیست خودتان مشتق نسبت به ماتریس بگیرید!