Teorie Matematică

Formule și demonstrații din referatul lucrării

1. Reprezentarea imaginii

O imagine grayscale de \(h \times w\) pixeli se reprezintă ca vector \(\mathbf{x} \in \mathbb{R}^d\), cu \(d = h \cdot w\). Pentru LFW (Labeled Faces in the Wild), setul de date folosit în aplicație, după conversia la grayscale și redimensionarea la \(50 \times 37\) px, avem \(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} \]

Proprietate: \(C\) este simetrică și pozitiv semidefinită, deci admite diagonalizare ortogonală: \(C = Q \Lambda Q^\top\).

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{astfel încâ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{astfel încâ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. Condițiile KKT și formularea duală

Atașând fiecărei constrângeri un multiplicator Lagrange \(\alpha_i \geq 0\), condițiile Karush-Kuhn-Tucker conduc la:

\[ \mathbf{w} = \sum_{i=1}^n \alpha_i\, y_i\, \mathbf{x}_i, \qquad \sum_{i=1}^n \alpha_i\, y_i = 0, \qquad \alpha_i \bigl[y_i(\mathbf{w}^\top \mathbf{x}_i + b) - 1\bigr] = 0 \]

Substituind în lagrangian se obține problema duală:

\[ \max_{\boldsymbol{\alpha}}\; \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i,j=1}^{n} \alpha_i\,\alpha_j\,y_i\,y_j\, \langle \mathbf{x}_i, \mathbf{x}_j \rangle \quad \text{cu} \quad 0 \leq \alpha_i \leq C \]

Din complementaritate, doar punctele cu \(\alpha_i > 0\) contribuie la soluție - aceștia sunt vectorii suport, situați chiar pe hiperplanele de margine. Problema duală depinde de date doar prin produsele scalare \(\langle \mathbf{x}_i, \mathbf{x}_j \rangle\), ceea ce deschide drumul către funcțiile kernel.

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)) \]

4. Teorema Eckart-Young

Dintre toate matricele de rang cel mult \(k\), cea mai bună aproximare a lui \(X\) în norma Frobenius este truncarea SVD la primele \(k\) componente:

\[ X_k = \sum_{i=1}^k \sigma_i\, u_i\, v_i^\top, \qquad \|X - X_k\|_F^2 = \sum_{i=k+1}^{\min(m,n)} \sigma_i^2 \]

Pe această proprietate se bazează reducerea de dimensionalitate prin PCA: păstrarea primelor \(k\) componente minimizează eroarea de reconstrucție în sensul Frobenius.

Concepte

CLAHE: Contrast Limited Adaptive Histogram Equalization. Egalizare locală a histogramei cu limitarea amplificării zgomotului.
Computer vision: Vedere artificială; domeniu care procesează informația vizuală.
Curse of dimensionality: Blestemul dimensionalității; în spații de dimensiune mare distanțele euclidiene devin aproape uniforme și clasificarea bazată pe distanță își pierde eficacitatea.
Eigenface: Vector propriu al matricei de covarianță, reformatat ca matrice de pixeli.
Grayscale: Tonuri de gri; reprezentarea imaginii ca matrice scalară, fiecare pixel având o intensitate în \([0, 255]\).
Kernel trick: Aplicarea unui algoritm liniar într-un spațiu transformat fără calculul explicit al transformării.
KKT: Condițiile Karush-Kuhn-Tucker, condiții necesare de optimalitate pentru probleme cu constrângeri de inegalitate.
LFW: Labeled Faces in the Wild; set de date public cu fotografii de fețe etichetate.
Overfitting: Supraantrenare; modelul învață particularități ale datelor de antrenare și nu generalizează pe date noi.
PCA: Principal Component Analysis; reducerea dimensionalității prin proiecție pe direcțiile de varianță maximă.
RBF: Radial Basis Function; nucleu gaussian \(K(\mathbf{x}, \mathbf{x}') = \exp(-\gamma \|\mathbf{x} - \mathbf{x}'\|^2)\).
SVD: Singular Value Decomposition; descompunerea în valori singulare.
SVM: Support Vector Machine; clasificator care caută hiperplanul cu margine maximă.
Whitening: Normalizarea componentelor PCA prin împărțire la \(\sqrt{\lambda_i}\) astfel încât toate să aibă varianță unitară.

Evaluare și metrici

Cross-validation: Validare încrucișată; setul de antrenare se împarte în \(k\) părți disjuncte, modelul se antrenează pe \(k-1\) părți și se evaluează pe partea rămasă, repetând de \(k\) ori. Scorul raportat este media celor \(k\) valori obținute.
TP, FN, FP, TN: true positives, false negatives, false positives, true negatives; cadranele matricei de confuzie pentru o clasă fixată.
Precizie: precision; \(P = \dfrac{TP}{TP + FP}\).
Recall: \(R = \dfrac{TP}{TP + FN}\).
F1-score: Media armonică între precizie și recall: \(F_1 = \dfrac{2 P R}{P + R}\).
Suport: support; numărul de exemple dintr-o clasă în setul de evaluare.

Biblioteci software

Matplotlib: Bibliotecă pentru generarea graficelor. matplotlib.org/stable
NumPy: Bibliotecă pentru tablouri n-dimensionale și algebră liniară. numpy.org/doc/stable
OpenCV: Bibliotecă pentru procesarea imaginilor. docs.opencv.org/4.x
scikit-learn: Bibliotecă pentru învățare automată (PCA, SVM, validare încrucișată). scikit-learn.org/stable