====== Descompuneri în Valori Proprii ====== Valorile proprii sunt adesea una dintre cele mai utile noțiuni pe care le vom întâlni când studiem algebra liniară, totuși, ca începător, este ușor să trecem cu vederea importanța lor. Mai jos, introducem descompunerea în valori proprii și încercăm să transmitem un sens al motivului pentru care este atât de importantă. Presupuneți că avem o matrice $A$ cu următoarele intrări: $$ \mathbf{A} = \begin{bmatrix} 2 & 0 \\ 0 & -1 \end{bmatrix}. $$ Dacă aplicăm $A$ oricărui vector $\mathbf{v} = [x, y]^\top$, obținem un vector $\mathbf{A}\mathbf{v} = [2x, -y]^\top$. Acest lucru are o interpretare intuitivă: întinde vectorul pentru a fi de două ori mai lat în direcția $x$, și apoi întoarce-l în direcția $y$. Totuși, există //câțiva// vectori pentru care ceva rămâne neschimbat. Anume $[1, 0]^\top$ este trimis la $[2, 0]^\top$ și $[0, 1]^\top$ este trimis la $[0, -1]^\top$. Acești vectori sunt încă pe aceeași linie, și singura modificare este că matricea îi întinde cu un factor de $2$ și respectiv $-1$. Numim astfel de vectori //vectori proprii// (eigenvectors) și factorul cu care sunt întinși //valori proprii// (eigenvalues). În general, dacă putem găsi un număr $\lambda$ și un vector $\mathbf{v}$ astfel încât $$ \mathbf{A}\mathbf{v} = \lambda \mathbf{v}. $$ Spunem că $\mathbf{v}$ este un vector propriu pentru $A$ și $\lambda$ este o valoare proprie. ===== Găsirea Valorilor Proprii ===== Să ne dăm seama cum să le găsim. Scăzând $\lambda \mathbf{v}$ din ambele părți, și apoi factorizând vectorul, vedem că cele de mai sus sunt echivalente cu: $$(\mathbf{A} - \lambda \mathbf{I})\mathbf{v} = 0.$$ Pentru ca :eqref:''%%eq_eigvalue_der%%'' să se întâmple, vedem că $(\mathbf{A} - \lambda \mathbf{I})$ trebuie să comprime o anumită direcție la zero, deci nu este inversabilă, și astfel determinantul este zero. Astfel, putem găsi //valorile proprii// găsind pentru ce $\lambda$ este $\det(\mathbf{A}-\lambda \mathbf{I}) = 0$. Odată ce găsim valorile proprii, putem rezolva $\mathbf{A}\mathbf{v} = \lambda \mathbf{v}$ pentru a găsi //vectorul(ii) propriu(i)// asociat(ți). ==== Un Exemplu ==== Să vedem acest lucru cu o matrice mai provocatoare $$ \mathbf{A} = \begin{bmatrix} 2 & 1\\ 2 & 3 \end{bmatrix}. $$ Dacă considerăm $\det(\mathbf{A}-\lambda \mathbf{I}) = 0$, vedem că acest lucru este echivalent cu ecuația polinomială $0 = (2-\lambda)(3-\lambda)-2 = (4-\lambda)(1-\lambda)$. Astfel, două valori proprii sunt $4$ și $1$. Pentru a găsi vectorii asociați, trebuie apoi să rezolvăm $$ \begin{bmatrix} 2 & 1\\ 2 & 3 \end{bmatrix}\begin{bmatrix}x \\ y\end{bmatrix} = \begin{bmatrix}x \\ y\end{bmatrix} \; \textrm{și} \; \begin{bmatrix} 2 & 1\\ 2 & 3 \end{bmatrix}\begin{bmatrix}x \\ y\end{bmatrix} = \begin{bmatrix}4x \\ 4y\end{bmatrix} . $$ Putem rezolva acest lucru cu vectorii $[1, -1]^\top$ și respectiv $[1, 2]^\top$. Putem verifica acest lucru în cod folosind rutina încorporată ''%%numpy.linalg.eig%%''. #@tab pytorch %matplotlib inline from d2l import torch as d2l from IPython import display import torch torch.linalg.eig(torch.tensor([[2, 1], [2, 3]], dtype=torch.float64)) Rețineți că ''%%numpy%%'' normalizează vectorii proprii pentru a fi de lungime unu, în timp ce noi i-am luat pe ai noștri să fie de lungime arbitrară. În plus, alegerea semnului este arbitrară. Totuși, vectorii calculați sunt paraleli cu cei pe care i-am găsit manual cu aceleași valori proprii. ===== Descompunerea Matricelor ===== Să continuăm exemplul anterior cu un pas mai departe. Fie $$ \mathbf{W} = \begin{bmatrix} 1 & 1 \\ -1 & 2 \end{bmatrix}, $$ matricea unde coloanele sunt vectorii proprii ai matricei $\mathbf{A}$. Fie $$ \boldsymbol{\Sigma} = \begin{bmatrix} 1 & 0 \\ 0 & 4 \end{bmatrix}, $$ matricea cu valorile proprii asociate pe diagonală. Atunci definiția valorilor proprii și a vectorilor proprii ne spune că $$ \mathbf{A}\mathbf{W} =\mathbf{W} \boldsymbol{\Sigma} . $$ Matricea $W$ este inversabilă, deci putem înmulți ambele părți cu $W^{-1}$ la dreapta, vedem că putem scrie $$\mathbf{A} = \mathbf{W} \boldsymbol{\Sigma} \mathbf{W}^{-1}.$$ În secțiunea următoare vom vedea câteva consecințe plăcute ale acestui lucru, dar pentru moment trebuie doar să știm că o astfel de descompunere va exista atâta timp cât putem găsi o colecție completă de vectori proprii liniar independenți (astfel încât $W$ să fie inversabilă). ===== Operații pe Descompuneri în Valori Proprii ===== Un lucru plăcut despre descompunerile în valori proprii :eqref:''%%eq_eig_decomp%%'' este că putem scrie multe operații pe care le întâlnim de obicei curat în termeni de descompunere în valori proprii. Ca un prim exemplu, considerați: $$ \mathbf{A}^n = \overbrace{\mathbf{A}\cdots \mathbf{A}}^{\textrm{$n$ times}} = \overbrace{(\mathbf{W}\boldsymbol{\Sigma} \mathbf{W}^{-1})\cdots(\mathbf{W}\boldsymbol{\Sigma} \mathbf{W}^{-1})}^{\textrm{$n$ times}} = \mathbf{W}\overbrace{\boldsymbol{\Sigma}\cdots\boldsymbol{\Sigma}}^{\textrm{$n$ times}}\mathbf{W}^{-1} = \mathbf{W}\boldsymbol{\Sigma}^n \mathbf{W}^{-1}. $$ Acest lucru ne spune că pentru orice putere pozitivă a unei matrice, descompunerea în valori proprii este obținută doar ridicând valorile proprii la aceeași putere. Același lucru poate fi arătat pentru puteri negative, deci dacă vrem să inversăm o matrice trebuie doar să considerăm $$ \mathbf{A}^{-1} = \mathbf{W}\boldsymbol{\Sigma}^{-1} \mathbf{W}^{-1}, $$ sau cu alte cuvinte, doar inversăm fiecare valoare proprie. Acest lucru va funcționa atâta timp cât fiecare valoare proprie este nenulă, deci vedem că inversabil este același lucru cu a nu avea valori proprii zero. Într-adevăr, muncă suplimentară poate arăta că dacă $\lambda_1, \ldots, \lambda_n$ sunt valorile proprii ale unei matrice, atunci determinantul acelei matrice este $$ \det(\mathbf{A}) = \lambda_1 \cdots \lambda_n, $$ sau produsul tuturor valorilor proprii. Acest lucru are sens intuitiv deoarece orice întindere face $\mathbf{W}$, $W^{-1}$ o anulează, deci în final singura întindere care se întâmplă este prin înmulțirea cu matricea diagonală $\boldsymbol{\Sigma}$, care întinde volumele prin produsul elementelor diagonale. În cele din urmă, reamintiți-vă că rangul a fost numărul maxim de coloane liniar independente ale matricei voastre. Examinând descompunerea în valori proprii îndeaproape, putem vedea că rangul este același cu numărul de valori proprii non-zero ale lui $\mathbf{A}$. Exemplele ar putea continua, dar sperăm că punctul este clar: descompunerea în valori proprii poate simplifica multe calcule algebrice liniare și este o operație fundamentală care stă la baza multor algoritmi numerici și a mult din analiza pe care o facem în algebra liniară. ===== Descompunerile în Valori Proprii ale Matricelor Simetrice ===== Nu este întotdeauna posibil să găsim suficienți vectori proprii liniar independenți pentru ca procesul de mai sus să funcționeze. De exemplu matricea $$ \mathbf{A} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}, $$ are doar un singur vector propriu, anume $(1, 0)^\top$. Pentru a gestiona astfel de matrice, avem nevoie de tehnici mai avansate decât putem acoperi (cum ar fi Forma Canonică Jordan, sau Descompunerea Valorii Singulare). Va trebui adesea să ne restrângem atenția la acele matrice unde putem garanta existența unui set complet de vectori proprii. Cea mai frecvent întâlnită familie sunt //matricele simetrice//, care sunt acele matrice unde $\mathbf{A} = \mathbf{A}^\top$. În acest caz, putem lua $W$ să fie o //matrice ortogonală//—o matrice ale cărei coloane sunt toate vectori de lungime unu care sunt la unghiuri drepte unul față de celălalt, unde $\mathbf{W}^\top = \mathbf{W}^{-1}$—și toate valorile proprii vor fi reale. Astfel, în acest caz special, putem scrie :eqref:''%%eq_eig_decomp%%'' ca $$ \mathbf{A} = \mathbf{W}\boldsymbol{\Sigma}\mathbf{W}^\top . $$ ===== Teorema Cercului Gershgorin ===== Valorile proprii sunt adesea dificil de raționat intuitiv. Dacă este prezentată o matrice arbitrară, se poate spune puțin despre care sunt valorile proprii fără a le calcula. Există, totuși, o teoremă care poate face ușoară aproximarea bine dacă cele mai mari valori sunt pe diagonală. Fie $\mathbf{A} = (a_{ij})$ orice matrice pătratică ($n\times n$). Vom defini $r_i = \sum_{j \neq i} |a_{ij}|$. Fie $\mathcal{D}_i$ discul în planul complex cu centrul $a_{ii}$ raza $r_i$. Atunci, fiecare valoare proprie a lui $\mathbf{A}$ este conținută în unul dintre $\mathcal{D}_i$. Acest lucru poate fi un pic de despachetat, deci să ne uităm la un exemplu. Considerați matricea: $$ \mathbf{A} = \begin{bmatrix} 1.0 & 0.1 & 0.1 & 0.1 \\ 0.1 & 3.0 & 0.2 & 0.3 \\ 0.1 & 0.2 & 5.0 & 0.5 \\ 0.1 & 0.3 & 0.5 & 9.0 \end{bmatrix}. $$ Avem $r_1 = 0.3$, $r_2 = 0.6$, $r_3 = 0.8$ și $r_4 = 0.9$. Matricea este simetrică, deci toate valorile proprii sunt reale. Aceasta înseamnă că toate valorile noastre proprii vor fi în unul dintre intervalele $$[a_{11}-r_1, a_{11}+r_1] = [0.7, 1.3], $$ $$[a_{22}-r_2, a_{22}+r_2] = [2.4, 3.6], $$ $$[a_{33}-r_3, a_{33}+r_3] = [4.2, 5.8], $$ $$[a_{44}-r_4, a_{44}+r_4] = [8.1, 9.9]. $$ Efectuarea calculului numeric arată că valorile proprii sunt aproximativ $0.99$, $2.97$, $4.95$, $9.08$, toate confortabil în interiorul intervalelor furnizate. #@tab pytorch A = torch.tensor([[1.0, 0.1, 0.1, 0.1], [0.1, 3.0, 0.2, 0.3], [0.1, 0.2, 5.0, 0.5], [0.1, 0.3, 0.5, 9.0]]) v, _ = torch.linalg.eig(A) v În acest fel, valorile proprii pot fi aproximate, și aproximările vor fi destul de precise în cazul în care diagonala este semnificativ mai mare decât toate celelalte elemente. Este un lucru mic, dar cu un subiect complex și subtil precum descompunerea în valori proprii, este bine să obținem orice înțelegere intuitivă putem. ===== O Aplicație Utilă: Creșterea Hărților Iterate ===== Acum că înțelegem ce sunt vectorii proprii în principiu, să vedem cum pot fi folosiți pentru a oferi o înțelegere profundă a unei probleme centrale pentru comportamentul rețelei neuronale: inițializarea corectă a ponderilor. ==== Vectorii Proprii ca Comportament pe Termen Lung ==== Investigația matematică completă a inițializării rețelelor neuronale profunde este dincolo de scopul textului, dar putem vedea o versiune de jucărie aici pentru a înțelege cum valorile proprii ne pot ajuta să vedem cum funcționează aceste modele. Așa cum știm, rețelele neuronale operează prin intercalarea straturilor de transformări liniare cu operații neliniare. Pentru simplitate aici, vom presupune că nu există neliniaritate, și că transformarea este o singură operație matriceală repetată $A$, astfel încât ieșirea modelului nostru este $$ \mathbf{v}_{out} = \mathbf{A}\cdot \mathbf{A}\cdots \mathbf{A} \mathbf{v}_{in} = \mathbf{A}^N \mathbf{v}_{in}. $$ Când aceste modele sunt inițializate, $A$ este luată să fie o matrice aleatoare cu intrări Gaussiene, deci să facem una dintre acelea. Pentru a fi concreți, începem cu o matrice $5 \times 5$ distribuită Gaussian cu medie zero, varianță unu. #@tab pytorch torch.manual_seed(42) k = 5 A = torch.randn(k, k, dtype=torch.float64) A ==== Comportament pe Date Aleatoare ==== Pentru simplitate în modelul nostru de jucărie, vom presupune că vectorul de date pe care îl introducem $\mathbf{v}_{in}$ este un vector Gaussian aleatoriu cinci dimensional. Să ne gândim la ce vrem să se întâmple. Pentru context, să ne gândim la o problemă generică ML, unde încercăm să transformăm datele de intrare, cum ar fi o imagine, într-o predicție, cum ar fi probabilitatea ca imaginea să fie o fotografie a unei pisici. Dacă aplicarea repetată a lui $\mathbf{A}$ întinde un vector aleatoriu pentru a fi foarte lung, atunci mici schimbări în intrare vor fi amplificate în schimbări mari în ieșire—modificări minuscule ale imaginii de intrare ar duce la predicții vast diferite. Acest lucru nu pare corect! Pe de altă parte, dacă $\mathbf{A}$ micșorează vectorii aleatorii pentru a fi mai scurți, atunci după rularea prin multe straturi, vectorul se va micșora esențial la nimic, și ieșirea nu va depinde de intrare. Acest lucru de asemenea nu este clar corect! Trebuie să mergem pe linia îngustă dintre creștere și descompunere pentru a ne asigura că ieșirea noastră se schimbă în funcție de intrarea noastră, dar nu mult! Să vedem ce se întâmplă când înmulțim repetat matricea noastră $\mathbf{A}$ cu un vector de intrare aleatoriu, și ținem evidența normei. #@tab pytorch # Calculate the sequence of norms after repeatedly applying `A` v_in = torch.randn(k, 1, dtype=torch.float64) norm_list = [torch.norm(v_in).item()] for i in range(1, 100): v_in = A @ v_in norm_list.append(torch.norm(v_in).item()) d2l.plot(torch.arange(0, 100), norm_list, 'Iteration', 'Value') Norma crește necontrolat! Într-adevăr dacă luăm lista câturilor, vom vedea un tipar. #@tab pytorch # Compute the scaling factor of the norms norm_ratio_list = [] for i in range(1, 100): norm_ratio_list.append(norm_list[i]/norm_list[i - 1]) d2l.plot(torch.arange(1, 100), norm_ratio_list, 'Iteration', 'Ratio') Dacă ne uităm la ultima porțiune a calculului de mai sus, vedem că vectorul aleatoriu este întins cu un factor de ''%%1.974459321485[...]%%'', unde porțiunea de la sfârșit se schimbă puțin, dar factorul de întindere este stabil. ==== Relaționarea Înapoi la Vectorii Proprii ==== Am văzut că vectorii proprii și valorile proprii corespund cantității cu care ceva este întins, dar asta a fost pentru vectori specifici, și întinderi specifice. Să aruncăm o privire la ce sunt acestea pentru $\mathbf{A}$. Un mic avertisment aici: se pare că pentru a le vedea pe toate, va trebui să mergem la numere complexe. Vă puteți gândi la acestea ca la întinderi și rotații. Luând norma numărului complex (rădăcina pătrată a sumelor pătratelor părților reale și imaginare) putem măsura acel factor de întindere. Să le și sortăm. #@tab pytorch # Compute the eigenvalues eigs = torch.linalg.eig(A).eigenvalues.tolist() norm_eigs = [torch.abs(torch.tensor(x)) for x in eigs] norm_eigs.sort() print(f'norms of eigenvalues: {norm_eigs}') ==== O Observație ==== Vedem că se întâmplă ceva puțin neașteptat aici: acel număr pe care l-am identificat înainte pentru întinderea pe termen lung a matricei noastre $\mathbf{A}$ aplicat unui vector aleatoriu este //exact// (precis până la treisprezece zecimale!) cea mai mare valoare proprie a lui $\mathbf{A}$. Aceasta nu este clar o coincidență! Dar, dacă ne gândim acum la ce se întâmplă geometric, acest lucru începe să aibă sens. Considerați un vector aleatoriu. Acest vector aleatoriu indică puțin în fiecare direcție, deci în particular, indică cel puțin un pic în aceeași direcție ca vectorul propriu al lui $\mathbf{A}$ asociat cu cea mai mare valoare proprie. Aceasta este atât de importantă încât este numită //valoarea proprie principală// și //vectorul propriu principal//. După aplicarea $\mathbf{A}$, vectorul nostru aleatoriu este întins în fiecare direcție posibilă, așa cum este asociat cu fiecare vector propriu posibil, dar este întins cel mai mult în direcția asociată cu acest vector propriu principal. Ceea ce înseamnă acest lucru este că după aplicare în $A$, vectorul nostru aleatoriu este mai lung, și indică într-o direcție mai apropiată de a fi aliniată cu vectorul propriu principal. După aplicarea matricei de multe ori, alinierea cu vectorul propriu principal devine din ce în ce mai apropiată până când, pentru toate scopurile practice, vectorul nostru aleatoriu a fost transformat în vectorul propriu principal! Într-adevăr acest algoritm este baza pentru ceea ce este cunoscut sub numele de //iterația puterii// (power iteration) pentru găsirea celei mai mari valori proprii și a vectorului propriu al unei matrice. Pentru detalii vedeți, de exemplu, ((Golub.Van-Loan.1996)). ==== Fixarea Normalizării ==== Acum, din discuțiile de mai sus, am concluzionat că nu vrem ca un vector aleatoriu să fie întins sau turtit deloc, am dori ca vectorii aleatorii să rămână cam de aceeași dimensiune pe parcursul întregului proces. Pentru a face acest lucru, rescalăm acum matricea noastră cu această valoare proprie principală astfel încât cea mai mare valoare proprie este în schimb acum doar unu. Să vedem ce se întâmplă în acest caz. #@tab pytorch # Rescale the matrix `A` A /= norm_eigs[-1] # Do the same experiment again v_in = torch.randn(k, 1, dtype=torch.float64) norm_list = [torch.norm(v_in).item()] for i in range(1, 100): v_in = A @ v_in norm_list.append(torch.norm(v_in).item()) d2l.plot(torch.arange(0, 100), norm_list, 'Iteration', 'Value') Putem, de asemenea, să reprezentăm grafic raportul dintre normele consecutive ca înainte și să vedem că într-adevăr se stabilizează. #@tab pytorch # Also plot the ratio norm_ratio_list = [] for i in range(1, 100): norm_ratio_list.append(norm_list[i]/norm_list[i-1]) d2l.plot(torch.arange(1, 100), norm_ratio_list, 'Iteration', 'Ratio') ===== Discuție ===== Vedem acum exact ce am sperat! După normalizarea matricelor prin valoarea proprie principală, vedem că datele aleatoare nu explodează ca înainte, ci mai degrabă eventual se echilibrează la o valoare specifică. Ar fi frumos să putem face aceste lucruri din primele principii, și se pare că dacă ne uităm profund la matematica acestui lucru, putem vedea că cea mai mare valoare proprie a unei matrice aleatoare mari cu intrări Gaussiene independente cu medie zero, varianță unu este în medie aproximativ $\sqrt{n}$, sau în cazul nostru $\sqrt{5} \approx 2.2$, datorită unui fapt fascinant cunoscut sub numele de //legea circulară// ((Ginibre.1965)). Relația dintre valorile proprii (și un obiect înrudit numit valori singulare) ale matricelor aleatoare s-a dovedit a avea conexiuni profunde cu inițializarea corectă a rețelelor neuronale așa cum a fost discutat în ((Pennington.Schoenholz.Ganguli.2017)) și lucrările ulterioare. ===== Rezumat ===== * Vectorii proprii sunt vectori care sunt întinși de o matrice fără a schimba direcția. * Valorile proprii sunt cantitatea cu care vectorii proprii sunt întinși prin aplicarea matricei. * Descompunerea în valori proprii a unei matrice poate permite ca multe operații să fie reduse la operații pe valorile proprii. * Teorema Cercului Gershgorin poate oferi valori aproximative pentru valorile proprii ale unei matrice. * Comportamentul puterilor matriceale iterate depinde în primul rând de mărimea celei mai mari valori proprii. Această înțelegere are multe aplicații în teoria inițializării rețelelor neuronale. ===== Exerciții ===== - Care sunt valorile proprii și vectorii proprii ai $$ \mathbf{A} = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}? $$ - Care sunt valorile proprii și vectorii proprii ai următoarei matrice, și ce este ciudat la acest exemplu comparativ cu cel anterior? $$ \mathbf{A} = \begin{bmatrix} 2 & 1 \\ 0 & 2 \end{bmatrix}. $$ - Fără a calcula valorile proprii, este posibil ca cea mai mică valoare proprie a următoarei matrice să fie mai mică de $0.5$? //Notă//: această problemă poate fi făcută în minte. $$ \mathbf{A} = \begin{bmatrix} 3.0 & 0.1 & 0.3 & 1.0 \\ 0.1 & 1.0 & 0.1 & 0.2 \\ 0.3 & 0.1 & 5.0 & 0.0 \\ 1.0 & 0.2 & 0.0 & 1.8 \end{bmatrix}. $$ [[https://discuss.d2l.ai/t/1086|Discuții]]