Page cover image

#12: Dimensionally Reduction

  • 5 min

#12: Dimensionally Reduction content

Created
Topics
Dimensionally Reduction, PCA, Matrix Factorization

Unsupervised Learning

Only inputs, no labels

Two Learning Paradigms

  1. Dimensionality reduction: feature selection
    • PCA: linear
    • Non-negative Matrix Factorization: linear
  1. Clustering: pattern detection

Dimensionality Reduction

Purpose

Computational: less space & time complexity
Statistical: better generalizability, less-prone to overfitting
Visualization: better human understandability
Anomaly detection: can detect outliers

Assumption

Data inherently lies in the low dimensional space

Examples

Source: 2; Intrinsic: 1
Source: 3; Intrinsic: 2
notion image
Hand-written Digits

Curse of dimensionality

Given a dd-dimensional sphere with volume Vd(r)V_d(r)
Volume of the outermost shell =δd=\delta_d
As we increase dimension, most volume of the sphere in composed of the shell:
lim⁡d→∞δd=Vd(r)\lim_{d\rightarrow\infty}\delta_d=V_d(r)

Why curse? When trying to fit data in 2D

  • Granularity: maintain the # of bins in each axis
Keep density of bins constant: each bin has same number of samples
  • Size of training set explodes: need more data
Keep the number of examples constant: same # as 1D
  • Some bins becomes empty
💡
Performance of classifiers degrade when dimensionality↑
notion image
  • Need exponentially more data to fit a model in higher dimensions

Methods

  • Feature Selection
  • Feature Extraction

Feature Extraction

notion image

Types

Linear Feature Transform

  • Principal Component Analysis (PCA)
  • Non-Negative Matrix Factorization (NMF)
  • Linear Discriminant Analysis (LDA)
  • Local Linear Embedding (LLE)
  • ISOMAP, etc.

Non-Linear Feature Transform

  • Kernal PCA
  • Auto-encoders, etc.

Criteria

Signal Representation
Classification Accuracy
notion image

Principal Component Analysis (PCA)

Intuition

Find a projection z\mathcal z that can reconstruct the original input XX
  • Project (Encode): z=UTx,zj=ujTxz=U^{T} x, \quad z_{j}=u_{j}^{T} x
  • Reconstruct (Decode): x~=Uz=∑j=1pzjuj\tilde{x}=U z=\sum_{j=1}^{p} z_{j} u_{j}
  • Minimize the reconstruction error ∣∣x−x~∣∣||x-\tilde{x}||
    notion image
Equivalent to: Find a dimension with the highest variance
notion image

Computation

 

Derivation

Eigenvalue magnitude ≡\equiv % of variance

notion image

Finding one principle component

notion image

Full PCA algorithm

  1. Recenter data: subtract mean from each column
    Xc←X−XˉX_c\leftarrow X-\bar X
  1. Compute Covariance Matrix C=1nXcXcTC=\frac 1 n X_c X_c^T
  1. Find Eigenvectors & Eigenvalues of CC
  1. The pp Eigenvectors w/ highest Eigenvalues = principal components
⚠️ Note: Computationally Inefficient

Hyper-parameter pp Estimation

By visual inspection:
  • Eigenvalues drop after some value
  • Ignore the dimensions w/ small Eigenvalues

Method: Singular Value Decomposition (SVD)

✅
A practical way of performing PCA
  1. Compute SVD of input data matrix XX: X=UΣVTX=U\Sigma V^T
  1. Left singular vectors UU ≡\equiv principal components of CC
Time Complexity: O(ndp)O(ndp)

Method: Eigen Decomposition (Diagonalization)

  1. Compute eigen decomposition of covariance matrix C=PDP−1C=PDP^{-1}

Example Use Cases

Eigen Faces
notion image
Latent semantic analysis

Non-negative Matrix Factorization (NMF)

💡
PCA w/ a non-negative constraint on
  • Projection matrix WW
  • Dim-reduced input ZZ
arg⁡min⁡W,Z∥X−WZ∥F2 s.t. wij≥0,zij≥0\begin{array}{r} \arg \min _{W, Z}\|X-W Z\|_{F}^{2} \\ \text { s.t. } w_{i j} \geq 0 ,\quad z_{i j} \geq 0 \end{array}

Purpose

PCA: x^=∑wizi\hat x=\sum w_iz_i ⇒ adding / subtracting elements
NMF: x^\hat x is created only by summing elements of the dictionary
⇒ Reduced input becomes more interpretable

Why no subtraction?

E.g. subtracting noses from lips does not make any sense
⚠️
This assumption is particular to input data type
  • NMF is NOT universally better than PCA

Linear Discriminant Analysis (LDA)

💡
Dimensionality reduction w/ labels Find a direction of projection that maximizes separation
μi\mu_i: mean of input samples in class CiC_i (dimensional dd)
μ~i=wTμi\tilde \mu_i= w^T\mu_i: mean of projected samples in class CiC_i (dimensional pp)

Loss Function

L(w)=∣μ1~−μ2~∣=∣wT(μ1−μ2)∣L(w)=\left|\tilde{\mu_{1}}-\tilde{\mu_{2}}\right|=\left|w^{T}\left(\mu_{1}-\mu_{2}\right)\right|

Goal

max⁡L(w)≡\max L(w)\equiv Maximize distance between projected means

Example

Bad: small gap
Good Direction: big gap
notion image
❓In linear algebra terms: argmax the direction of eigenvector

Fischer Discriminant Analysis

💡
Increase distance between class means + Decease variance within classes
= LDA normalized by within-class scatter

Terms

  • Scatter of a class: s~i2=∑xj∈Ci(f(xj)−μ~i)2=∑xj∈Ci(wTxj−μ~i)2\tilde{s}_{i}^{2}=\sum_{x_{j} \in C_{i}}\left(f\left(x_{j}\right)-\tilde{\mu}_{i}\right)^{2}=\sum_{x_{j} \in C_{i}}\left(w^{T} x_{j}-\tilde{\mu}_{i}\right)^{2}
  • Within-class scatter s~12+s~22{\tilde s_1}^2+{\tilde s_2}^2: variance of points in a class

Loss Function

L(w)=∣μ1~−μ2~∣s1~2+s2~2L(w)=\frac{\left|\tilde{\mu_{1}}-\tilde{\mu_{2}}\right|}{\tilde{s_{1}}^{2}+\tilde{s_{2}}^{2}}