Teorie Matematică
Formule și demonstrații din referatul lucrării
1. Reprezentarea imaginii
O imagine în tonuri de gri de \(h \times w\) pixeli se reprezintă ca vector \(\mathbf{x} \in \mathbb{R}^d\), cu \(d = h \cdot w\). Pentru LFW: \(d = 50 \times 37 = 1850\).
2. Centrarea datelor și matricea de covarianță
Fie \(X \in \mathbb{R}^{n \times d}\) matricea de date. Centrul:
\[ \boldsymbol{\mu} = \frac{1}{n} \sum_{i=1}^n \mathbf{x}_i, \qquad \tilde{X} = X - \mathbf{1}\boldsymbol{\mu}^\top \]Matricea de covarianță empirică:
\[ C = \frac{1}{n}\, \tilde{X}^\top \tilde{X} \;\in\; \mathbb{R}^{d \times d} \]3. Direcția de varianță maximă (Teorema PCA)
Prima componentă principală este soluția problemei de optimizare:
\[ \mathbf{u}_1 = \operatorname*{arg\,max}_{\|\mathbf{u}\|=1} \; \mathbf{u}^\top C \,\mathbf{u} \]Demonstrație (multiplicatori Lagrange):
\[ \mathcal{L}(\mathbf{u}, \lambda) = \mathbf{u}^\top C\, \mathbf{u} - \lambda\bigl(\|\mathbf{u}\|^2 - 1\bigr) \] \[ \frac{\partial \mathcal{L}}{\partial \mathbf{u}} = \mathbf{0} \;\Longrightarrow\; 2C\mathbf{u} - 2\lambda\mathbf{u} = \mathbf{0} \;\Longrightarrow\; C\mathbf{u} = \lambda\mathbf{u} \]Recunoaștem ecuația de valori proprii. Varianta proiectată în punctul optim:
\[ \mathbf{u}^\top C\, \mathbf{u} = \mathbf{u}^\top (\lambda\mathbf{u}) = \lambda\,\|\mathbf{u}\|^2 = \lambda \]Maximul se atinge pentru \(\lambda = \lambda_1\), cea mai mare valoare proprie a lui \(C\).
4. Proiecția și reconstrucția
Primii \(k\) vectori proprii formează matricea de proiecție \(U_k = [\mathbf{u}_1 \mid \cdots \mid \mathbf{u}_k] \in \mathbb{R}^{d \times k}\).
\[ \mathbf{z} = U_k^\top (\mathbf{x} - \boldsymbol{\mu}) \;\in\; \mathbb{R}^k \]Reconstrucție aproximativă din \(k\) eigenfaces:
\[ \mathbf{x} \;\approx\; \boldsymbol{\mu} + \sum_{i=1}^k \alpha_i\, \mathbf{u}_i, \qquad \alpha_i = \mathbf{u}_i^\top(\mathbf{x} - \boldsymbol{\mu}) \]5. Varianță explicată cumulativă
\[ \text{VEC}(k) = \frac{\displaystyle\sum_{i=1}^k \lambda_i}{\displaystyle\sum_{i=1}^d \lambda_i} \]Se alege \(k\) astfel încât \(\text{VEC}(k) \geq 0{,}95\). Whitening: \(\tilde{\alpha}_i = \alpha_i / \sqrt{\lambda_i}\) normalizează toate componentele la varianță unitară, util pentru SVM cu kernel RBF.
1. Clasificatorul cu Marjă Maximă
Dat un set de antrenare \(\{(\mathbf{z}_i, y_i)\}_{i=1}^n\) cu \(y_i \in \{-1, +1\}\), SVM liniar caută hiperplanul \(\mathbf{w}^\top \mathbf{z} + b = 0\) care maximizează marja:
\[ \min_{\mathbf{w},\,b} \; \frac{1}{2}\|\mathbf{w}\|^2 \quad \text{s.t.} \quad y_i\bigl(\mathbf{w}^\top \mathbf{z}_i + b\bigr) \geq 1, \;\forall i \]Marja geometrică față de hiperplan este \(\dfrac{2}{\|\mathbf{w}\|}\).
2. SVM cu marjă moale (Soft-Margin)
\[ \min_{\mathbf{w},\,b,\,\boldsymbol{\xi}} \; \frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^n \xi_i \quad \text{s.t.} \quad y_i(\mathbf{w}^\top \mathbf{z}_i + b) \geq 1 - \xi_i,\; \xi_i \geq 0 \]Parametrul \(C\) controlează trade-off-ul între marjă și erori de clasificare.
3. Kernel RBF
Pentru date neseparabile liniar, SVM folosește o funcție kernel care calculează produsul scalar în spațiul caracteristicilor fără a-l materializa explicit:
\[ K(\mathbf{z}_i, \mathbf{z}_j) = \exp\!\left(-\gamma \|\mathbf{z}_i - \mathbf{z}_j\|^2\right) \]Decizia de clasificare pentru un punct nou \(\mathbf{z}\):
\[ \hat{y} = \operatorname{sgn}\!\left(\sum_{i \in SV} \alpha_i y_i K(\mathbf{z}_i, \mathbf{z}) + b\right) \]unde suma rulează doar peste vectorii suport (punctele de pe marjă).
4. Extensia multiclasă (One-vs-Rest)
Pentru \(m\) persoane se antrenează \(m\) clasificatori binari. Clasa prezisă este cea cu scorul decizional maxim:
\[ \hat{c} = \operatorname*{arg\,max}_{c \in \{1,\ldots,m\}} \left(\sum_{i \in SV_c} \alpha_i y_i K(\mathbf{z}_i, \mathbf{z}) + b_c\right) \]1. Descompunerea în Valori Singulare
Orice matrice \(A \in \mathbb{R}^{m \times n}\) se poate scrie:
\[ A = U \Sigma V^\top \]unde \(U \in \mathbb{R}^{m \times m}\), \(V \in \mathbb{R}^{n \times n}\) sunt ortogonale, iar \(\Sigma \in \mathbb{R}^{m \times n}\) este diagonală cu \(\sigma_1 \geq \sigma_2 \geq \cdots \geq 0\).
2. Legătura SVD – Covarianță
Aplicând SVD matricei centrate \(\tilde{X} = U\Sigma V^\top\):
\[ \tilde{X}^\top \tilde{X} = (U\Sigma V^\top)^\top (U\Sigma V^\top) = V \Sigma^\top U^\top U \Sigma V^\top = V \Sigma^2 V^\top \] \[ C = \frac{1}{n}\tilde{X}^\top\tilde{X} = V\,\frac{\Sigma^2}{n}\,V^\top \]Deci coloanele lui \(V\) sunt vectorii proprii ai lui \(C\), iar \(\lambda_i = \sigma_i^2 / n\). Eigenfaces = coloanele lui \(V\).
3. Avantajul practic
Când \(n \ll d\) (\(n \approx 1000\), \(d = 1850\)), diagonalizarea directă a lui \(C \in \mathbb{R}^{d \times d}\) ar necesita \(\mathcal{O}(d^3)\) operații. SVD truncat (primele \(k\) valori singulare) reduce complexitatea la \(\mathcal{O}(ndk)\), semnificativ mai eficient.
\[ \tilde{X} \approx U_k \Sigma_k V_k^\top \quad (k \ll \min(n,d)) \]