مقدمه‌ای بر جبر خطی (ریاضیات پیش‌نیاز GNN)

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

مفاهیم اولیه

- اسکالر: یک عدد.

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

\begin{bmatrix}
x_1 \\
x_2 \\
\vdots \\
x_n
\end{bmatrix}

- نُرم p: نرم یک بردار، طول آن را اندازه‌گیری می‌کند. نرم \(L_p\) به صورت زیر تعریف می‌شود:

\[\|\mathbf{x}\|_p = \left( \sum_{i=1}^{n} |x_i|^p \right)^{\frac{1}{p}}\]

نرم \(L_1\)، نرم \(L_2\) و \(L_\infty\) معمولا در یادگیری ماشین استفاده می‌گردند. هرچی \(p\) بزرگ‌تر بشود، مؤلفه‌هایی که مقدار بزرگ‌تری دارند، تأثیر بیشتری در نتیجه دارند.

شکل ساده شدۀ نرم 1 به صورت زیر است:

\[\|\mathbf{x}\|_1 = \sum_{i=1}^{n} |x_i|\]

در فضای اقلیدسی \(\mathbb{R}^n\)، نرم \(L_2\) برای اندازه‌گیری طول بردارها استفاده می‌گردد که به صورت زیر است:

\[\|\mathbf{x}\|_2 = \left( \sum_{i=1}^{n} x_i^2 \right)^{\frac{1}{2}}\]

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

\[\|\mathbf{x}\|_\infty = \max_{1 \leq i \leq n} |x_i|\]

با نرم \(L_p\) فاصلۀ بین دو بردار \(x_1\) و \(x_2\) (که در یک فضای خطی هستند) به صورت زیر تعریف می‌شود:

\[D_p(x_1,x_2)=\|x_1-x_2\|_p\]

گوییم مجموعۀ بردارهای \(x_1,x_2, ...,x_m\) به صورت خطی مستقل هستند، اگر و تنها اگر مجموعه‌ای از اسکالرهای \(\lambda_1, \lambda_2, ..., \lambda_m\) وجود نداشته باشد (به صورتی که همگی برابر صفر نباشند) که داشته باشیم:

\[\lambda_1x_1+\lambda_2x_2+...+\lambda_mx_m=0\]

-ماتریس: ماتریس آرایۀ دوبعدی است که به صورت زیر نمایش داده می‌شود:  \[A=\begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn}
\end{bmatrix}\]

به نحوی که \(A \in \mathbb{R}^{m \times n}\).

اگر دو ماتریس \(A \in \mathbb{R}^{m \times n}\) و \(B \in \mathbb{R}^{n \times p}\) را داشته باشیم، ضرب ماتریسی \(AB\) به صورت \(C \in \mathbb{R}^{m \times p}\) خواهد بود که:

\[C_{ij} = \sum_{k=1}^n A_{ik}B_{kj}\]

برای ماتریس مربعی \(n \times n\) \(A\)، دترمینان آن که با \(|A|\) نشان داده می‌شود برابر است با:

\[det(A)= \sum_{k_1k_2...k_n} (-1)^{\tau (k_1k_2...k_n)}a_{1k_1}a_{2k_2}...a_{nk_n}\]

در اینجا \(k_1k_2...k_n\) یک جایگشت از \(1\) تا \(n\) است و \(\tau (k_1k_2...k_n)\) تعداد وارونگی‌های جایگشت است که به صورت زیر تعریف می‌گردد:

\[
\tau(k_1 \ldots k_n) =
\left| \left\{ (i,j) \mid 1 \le i < j \le n,\; k_i > k_j \right\} \right|
\]

معکوس یک ماتریس مربعی که به صورت \(A^{-1}\) نشان داده می‌شود بیانگر آن است که: \(A^{-1}A=I\) به نحوی که \(I\) یک ماتریس همانی مربعی است. می‌دانیم که \(A^{-1}\) تنها در صورتی وجود دارد که \( |A| \neq 0\).

ترانهادۀ ماتریس \(A\) که به صورت \(A^T\) است، به صورت روبرو نشان داده می‌شود: \(A^T_{ij}=A_{ji}\).

یکی از ضرب‌های پر استفاده در بین ماتریس‌ها، ضرب هادامارد است. حاصل این ضرب برای دو ماتریس \(A \in \mathbb{R}^{m \times n}\) و \(B \in \mathbb{R}^{m \times n}\) برابر \(C \in \mathbb{R}^{m \times n}\) است که:

\[C_{ij}=A_{ij}B_{ij}\]

- تنسور: آرایه‌ای با بُعد دلخواه (یا چندبُعدی). بیشتر عملیات مربوط به ماتریس‌ها را می‌توان بر روی تنسورها نیز اعمال کرد.

تجزیه‌ی به مؤلفه‌های ویژه (Eigen Decomposition)

اگر \(A\) یک ماتریس در فضای \(\mathbb{R}^{n \times n}\) باشد، یک بردار غیر صفر \(v \in \mathbb{C}^{n}\) یک بردار ویژۀ \(A\) نامیده می‌شود به نحوی که یک اسکالر \(\lambda \in \mathbb{C}^n\) داریم که:

\[Av= \lambda v\]

در اینجا یک مقدار ویژۀ \(\lambda\) متناسب با بردار ویژۀ \(v\) داریم. اگر ماتریس \(A\) دارای \(n\) بردار ویژه \(\{v_1,v_2,...,v_n\}\) باشد که به صورت خطی مستقل باشند، که متناسب با \(\{\lambda_1, \lambda_2, ..., \lambda_n\}\)، اینطور می‌توان استنباط کرد که:

\[ \mathbf{A}  \begin{bmatrix} \mathbf{v}_1 & \mathbf{v}_2 & \cdots & \mathbf{v}_n \end{bmatrix} = \begin{bmatrix} \mathbf{v}_1 & \mathbf{v}_2 & \cdots & \mathbf{v}_n \end{bmatrix} \begin{bmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n \end{bmatrix} \]

اگر در نظر بگیریم که \( \mathbf{V} =  \begin{bmatrix} \mathbf{v}_1 & \mathbf{v}_2 & \cdots & \mathbf{v}_n \end{bmatrix} \)، این واضح است که \(V\) یک ماتریس معکوس‌پذیر است. ما تجزیه ویژه \(\mathbf{A}\) را داریم (که قطری‌سازی نیز نامیده می‌شود):

\[\mathbf{A} = \mathbf{V} \, \mathrm{diag}(\boldsymbol{\lambda}) \, \mathbf{V}^{-1} \]

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

\[ \mathbf{A} = \sum_{i=1}^{n} \lambda_i \, \mathbf{v}_i \, \mathbf{v}_i^{T} \]

با این حال، همهٔ ماتریس‌های مربعی قابل قطری‌سازی به این صورت نیستند، زیرا ممکن است یک ماتریس به تعداد کافی (یعنی \(n\) تا) بردار ویژهٔ خطی مستقل نداشته باشد.
خوشبختانه، می‌توان اثبات کرد که هر ماتریس متقارن حقیقی دارای تجزیهٔ ویژه (Eigendecomposition) است.

تجزیه مقدار تکین (Singular Value Decomposition)

از آن‌جایی که تجزیه‌ی ویژه (Eigendecomposition) تنها برای برخی از ماتریس‌ها قابل استفاده است، تجزیه‌ی مقدار تکین (Singular Value Decomposition یا SVD) را معرفی می‌کنیم که تعمیم‌یافته‌ای برای تمام ماتریس‌ها است.

ابتدا لازم است مفهوم مقدار تکین (singular value) را معرفی کنیم. فرض کنید \(r\) رتبۀ ماتریس \(A^TA\) باشد. در این صورت \(r\) عدد حقیقی مثبت وجود دارند که:

\[\sigma_1 \ge \sigma_2 \ge ... \ge \sigma_r > 0\]

به طوری که برای هر \(r \ge i \ge 0\)، \(v_i\) بردار ویژۀ \(A^TA\) است که مقدار ویژۀ متناسب آن برابر با \(\sigma_i^2\) است. توجه شود که بردارهای \(v_1,v_2,...,v_i\) با یکدیگر مستقل خطی هستند. این \(r\) عدد \(\sigma_1,\sigma_2,...\sigma_r\) را مقادیر تکین ماتریس \(A\) می‌نامیم. در نتیجه تجزیۀ مقدار تکین به صورت زیر خواهد بود:

\[
\mathbf{A} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^T
\]

به نحوی که \(\mathbf{U} \in \mathbb{R}^{m \times m}\) و \(\mathbf{V} (n \times n)\) ماتریس‌های متعامد هستند و \(\mathbf{\Sigma}\) یک ماتریس \(m \times n\) است که به صورت زیر تعریف می‌گردد:

\[ \Sigma_{ij} =  \begin{cases} \sigma_i & \text{if } i = j \le r, \\ 0 & \text{otherwise.} \end{cases} \]