18. Maticové faktorizace pomocí SVD, její výpočet, vlastnosti a použití ve strojovém učení: souvislost s metodou hlavních komponent (PCA) (NI-PON)

---

Maticové faktorizace pomocí SVD

Koncepční úvod do problematiky

Singulární rozklad (Singular Value Decomposition, SVD) je metoda, která umožňuje rozložit libovolnou matici $A$ (reálnou nebo komplexní) na tři speciální matice: $A = U \Sigma V^T$.

Matematické základy

Pro matici $A \in \mathbb{R}^{m \times n}$:

1. Rozklad: $$A = U \Sigma V^T$$

   • $U \in \mathbb{R}^{m \times m}$: ortogonální matice (levé singulární vektory).
   • $\Sigma \in \mathbb{R}^{m \times n}$: diagonální matice obsahující singulární hodnoty ($\sigma_1, \sigma_2, ..., \sigma_r$). Zbytek diagonály je doplněn nulami
   • $V \in \mathbb{R}^{n \times n}$: ortogonální matice (pravé singulární vektory).

2. Výpočet singulárních hodnot:

   • Singulární hodnoty jsou odmocniny vlastních čísel matic $A^T A$ nebo $A A^T$: $$A^T A v_i = \sigma_i^2 v_i$$ $$A A^T u_i = \sigma_i^2 u_i$$

3. Pořadí hodnot:

   • Singulární hodnoty jsou seřazeny sestupně: $\sigma_1 \geq \sigma_2 \geq ... \geq 0$.

Algoritmus

1. Výpočet matice $A^T A$

   • Spočítej matici $$M = A^T A$$

   • Matice $M$ je symetrická a pozitivně semidefinitní, což zaručuje, že všechny její vlastní čísla jsou reálná a nezáporná.

2. Vlastní hodnotová dekompozice matice $A^T A$

   • Řeš vlastní rovnici $$A^T A\, v_i = \lambda_i\, v_i \,.$$
   • Získáš tak vlastní čísla $\lambda_i$ a odpovídající vlastní vektory $v_i$, které tvoří ortonormální bázi (díky symetrii matice $A^T A$).

3. Výpočet singulárních hodnot a sestavení matice $\Sigma$

   • Seřaď vlastní čísla sestupně: $$\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n \ge 0 \,.$$
   • Definuj singulární hodnoty jako $$\sigma_i = \sqrt{\lambda_i} \,.$$
   • Sestav diagonální matici $\Sigma \in \mathbb{R}^{m \times n}$, ve které umístíš singulární hodnoty $\sigma_i$ na hlavní diagonálu, přičemž ostatní prvky nastavíš na nulu.

4. Stanovení pravých singulárních vektorů

   • Matice $V \in \mathbb{R}^{n \times n}$ vytvoř tak, že její sloupce jsou získané vlastní vektory $v_i$ z kroku 2.

5. Odvození levých singulárních vektorů

   • Vychází se z rovnice definující SVD, tedy z $$A\, v_i = \sigma_i\, u_i \,.$$

   • Pro každé $i$ s $\sigma_i > 0$ odvoď levý singulární vektor jako $$u_i = \frac{1}{\sigma_i} A\, v_i \,.$$

   • Tento postup je platný, protože:

     • Vlastní hodnotová dekompozice matice $A^T A$ zaručuje, že pro $v_i$ platí $A^T A\, v_i = \lambda_i\, v_i$ a tím i $\sigma_i = \sqrt{\lambda_i}$.
     • Rovnice $A\, v_i = \sigma_i\, u_i$ vyplývá přímo z definice SVD, což zajišťuje, že takto získané $u_i$ jsou normalizované a zároveň tvoří ortonormální bázi.
   • Pokud se některé $\sigma_i = 0$ (což znamená, že odpovídající $v_i$ patří do jádra matice $A$), nelze použít tento vzorec. V takových případech doplň levé singulární vektory dalšími metodami, aby celá matice $U \in \mathbb{R}^{m \times m}$ byla ortonormální.
   • Sestavení konečného rozkladu SVD
   • Kombinuj získané matice do výsledného rozkladu $$A = U\, \Sigma\, V^T \,.$$

   Vlastnosti SVD

6. Rank matice: Počet nenulových singulárních hodnot odpovídá hodnosti matice.

7. Ortogonální báze: Sloupce $U$ tvoří bázi sloupcového prostoru $A$, zatímco sloupce $V$ tvoří bázi řádkového prostoru.
8. Nízkohodnotová aproximace: Nejlepší aproximace ranku $k$ je dána prvními $k$ singulárními hodnotami: $$A_k = U_k \Sigma_k V_k^T$$

Použití ve strojovém učení

1. Dimenzionální redukce (PCA):

   • PCA lze provést pomocí SVD aplikací na centrovanou datovou matici. Hlavní komponenty odpovídají pravým singulárním vektorům.
   • Výhoda oproti přímé eigen-dekompozici kovarianční matice spočívá v numerické stabilitě.

2. Komprese dat:

   • SVD umožňuje komprimovat data uchováním pouze nejdůležitějších singulárních hodnot a odpovídajících vektorů.

3. Rekonstrukce obrazu:

   • Nízkohodnotová aproximace může být použita k odstranění šumu nebo ke kompresi obrazu.

4. Recommender systémy:

   • SVD se používá pro modelování latentních faktorů v kolaborativním filtrování.

Výhody a nevýhody

Výhody

• Univerzálnost: Lze aplikovat na libovolnou obdélníkovou matici.
• Interpretabilita: Poskytuje jasnou interpretaci dat skrze singulární hodnoty a vektory.
• Robustnost vůči šumu.

Nevýhody

• Výpočetní náročnost: Pro velké matice může být výpočet časově náročný.
• Citlivost na šum: Malé změny v datech mohou ovlivnit výsledky.

Souvislost SVD s PCA

PCA (Principal Component Analysis) je speciální případ SVD (Singular Value Decomposition), který se používá k redukci dimenzionality dat a k nalezení hlavních komponent, tedy směrů maximální variance v datech. Tato metoda využívá vlastností SVD rozkladu a jeho aplikace na kovarianční matici dat.

Vycentrování dat a výpočet kovarianční matice

PCA se provádí na datové matici $X \in \mathbb{R}^{N \times p}$, kde $N$ je počet vzorků (řádků) a $p$ je počet příznaků (sloupců). Před aplikací PCA je nutné zajistit, aby byla matice $X$ vycentrovaná, což znamená, že průměry všech příznaků ve sloupcích jsou nulové:

$$\frac{1}{N} \sum_{i=1}^N X_{ij} = 0 \quad \text{pro } j = 1, \dots, p.$$

Vycentrování se dosáhne odečtením průměru každého sloupce od všech jeho hodnot. Tento krok zajišťuje, že kovarianční matice správně odráží rozptyl a vztahy mezi příznaky.

Poté se spočítá kovarianční matice příznaků:

$$C = \frac{1}{p-1} X^T X,$$

kde $C \in \mathbb{R}^{p \times p}$ je symetrická a pozitivně semidefinitní matice. Vlastní čísla této matice odpovídají rozptylům dat ve směrech hlavních komponent a vlastní vektory určují tyto směry.

Vztah mezi PCA a SVD

PCA lze chápat jako přímou aplikaci SVD na datovou matici $X$. Pokud provedeme SVD rozklad $X = U \Sigma V^T$ pak kovarianční matice $C$ lze vyjádřit jako: $$C = \frac{1}{p-1} X^T X = \frac{1}{p-1} V (\Sigma^T \Sigma) V^T.$$ Tento vztah ukazuje, že kovarianční matice má stejnou strukturu jako spektrální rozklad, kde vlastní čísla odpovídají čtvercům singulárních hodnot $\sigma_i^2$, děleným faktorem $\frac{1}{p-1}$.

Hlavní komponenty a jejich význam

Hlavní komponenty představují směry v datovém prostoru, ve kterých se rozptyl dat maximalizuje. Jinými slovy, hledají osy, podél kterých jsou data nejrozptýlenější a proto nejvíce informativní.

Tyto směry jsou určeny vlastními vektory kovarianční matice, které získáme jako sloupce matice $V$ v SVD rozkladu matice $X$. Pro matici $X$ s hodností $r$ budeme mít právě $r$ výrazných hlavních komponent. Každá z těchto komponent odpovídá směru, ve kterém se data rozptylují.

Rozptyl hlavní komponenty $PC_i$ je určen vzorcem: $$\text{Var}(PC_i) = \frac{\sigma_i^2}{p-1}\,.$$

Tento vztah znamená, že čím větší je singulární hodnota, tím větší rozptyl (variabilita) dat ve směru odpovídající hlavní komponenty a tedy i větší významnost tohoto směru při zachycování variability ve datech.

Redukce dimenzionality pomocí PCA

SVD umožňuje efektivní redukci dimenzionality tím, že zachová pouze několik největších singulárních hodnot a odpovídajících pravých singulárních vektorů. Pokud zvolíme pouze prvních $k$ hlavních komponent (odpovídajících největším $\sigma_i$), můžeme data aproximovat jako: $$X_k = U_k \Sigma_k V_k^T,$$ kde $U_k$, $\Sigma_k$, a $V_k$ obsahují pouze prvních $k$ sloupců původních matic. Tímto způsobem ztrácíme pouze minimální část variance v datech, zatímco výrazně snižujeme jejich dimenzi.