Dimensionality Reduction: PCA, t-SNE, Autoencoders & Applications

TAKEAWAYS:

• PCA projects data onto orthogonal axes (principal components) to maximize variance, reducing dimensions while retaining most information.
• t-SNE optimizes pairwise distances for visualization, revealing clusters in high-dimensional data (e.g., images, text).
• Autoencoders use neural networks to learn compressed representations via encoding-decoding, useful for denoising and feature extraction.
• Curse of dimensionality is mitigated by dimensionality reduction, improving model efficiency and interpretability.
• Applications include image compression (e.g., JPEG), anomaly detection (e.g., fraud in banks), and visualization (e.g., NEPSE stock trends).
• Trade-offs exist between computational cost, interpretability, and information loss in reduced dimensions.

Core Concepts: Why Reduce Dimensions?

Dimensionality reduction transforms high-dimensional data into a lower-dimensional space while preserving its essential structure. This is critical because:

• Curse of dimensionality: As features increase, data becomes sparse, and models struggle with overfitting or inefficiency.
• Visualization: Humans perceive 2D/3D better than high-dimensional spaces (e.g., plotting 1000 features is impossible).
• Computational efficiency: Fewer dimensions mean faster training and inference (e.g., recommendation systems like Daraz’s product matching).

Key Definitions

1. Principal Component Analysis (PCA)

PCA is the most widely used linear dimensionality reduction technique. It works by:

1. Standardizing data (mean=0, variance=1 per feature).
2. Computing covariance matrix to identify feature correlations.
3. Eigen decomposition: Finding eigenvalues/vectors of the covariance matrix.
4. Sorting eigenvalues: Select top-k eigenvectors (principal components) with highest variance.
5. Projecting data: Multiply original data by the selected eigenvectors to get reduced dimensions.

How PCA Works: Step-by-Step

Consider a dataset with 3 features (X₁, X₂, X₃) and 5 samples:

# Sample data (standardized)
X = [[1.2, -0.5, 0.8],
     [-0.8, 1.1, 0.3],
     [0.5, -0.9, -1.2],
     [1.5, 0.2, -0.5],
     [-0.3, 0.7, 1.0]]

1. Compute covariance matrix: $$\text{Cov}(X)=\frac{1}{n-1}{X}^{T}X$$ Result (approximate):

   [[ 1.0, -0.3,  0.2],
    [-0.3,  1.0, -0.1],
    [ 0.2, -0.1,  1.0]]
   

2. Eigen decomposition:

   • Eigenvalues: λ₁ ≈ 1.6, λ₂ ≈ 0.9, λ₃ ≈ 0.5
   • Eigenvectors (principal components):
     • PC₁ ≈ [0.6, -0.5, 0.6]
     • PC₂ ≈ [0.7, 0.7, -0.1]
     • PC₃ ≈ [-0.3, 0.5, 0.8]

3. Select top-k components:

   • To reduce to 2D, use PC₁ and PC₂.
   • Project data: $X_{\text{reduced}}=X\times [{\text{PC}}_1,{\text{PC}}_2]$.

4. Resulting 2D data:

   [[ 0.8,  0.3],
    [-1.2,  0.4],
    [ 0.1, -1.1],
    [ 1.0,  1.0],
    [-0.5,  0.6]]
   

Visualizing PCA

Explained Variance

• Variance explained: The proportion of data variance captured by each PC.
  • PC₁: 1.6/3.0 ≈ 53%
  • PC₂: 0.9/3.0 ≈ 30%
  • PC₃: 0.5/3.0 ≈ 17%
• Cumulative variance: Sum of variances of top-k PCs. Aim for ≥95% to retain most information.

Advantages and Limitations

2. t-Distributed Stochastic Neighbor Embedding (t-SNE)

t-SNE is a nonlinear technique designed for visualization, not compression. It:

1. Computes pairwise similarities in high-D space (e.g., Euclidean distances).
2. Maps these to a low-D space (typically 2D) while preserving local similarities.
3. Uses a t-distribution (heavy-tailed) to avoid crowding points in the center.

How t-SNE Works

1. High-D similarities:

   • For each pair of points $(x_i,x_j)$, compute: $$p_{j|i}=\frac{\exp (-\Vert x_i-x_j{\Vert }^2/2{\sigma }_i^2)}{{\sum }_{k\ne i}\exp (-\Vert x_i-x_k{\Vert }^2/2{\sigma }_i^2)}$$
   • ${\sigma }_i$ is chosen to make the perplexity (a measure of effective number of neighbors) match a target (e.g., 30).

2. Low-D similarities:

   • Use a symmetric t-distribution with 1 degree of freedom (Cauchy distribution) to map to 2D: $$q_{ij}=\frac{(1+\Vert y_i-y_j{\Vert }^2{)}^{-1}}{{\sum }_{k\ne l}(1+\Vert y_k-y_l{\Vert }^2{)}^{-1}}$$
   • $y_i$ are the 2D coordinates we optimize.

3. Optimization:

   • Minimize the Kullback-Leibler (KL) divergence between $P$ (high-D) and $Q$ (low-D): $$\text{KL}(P\parallel Q)=\sum _{i\ne j}{p}_{ij}\log \frac{p_{ij}}{q_{ij}}$$
   • Use gradient descent to adjust $y_i$.

t-SNE vs. PCA

Real-World Example: Visualizing NEPSE Stock Trends

• How it works:
  • Each stock’s daily price/volume data (e.g., 50 features) is reduced to 2D.
  • t-SNE reveals hidden clusters (e.g., stocks moving together due to sector trends).
• Application:
  • Traders use this to spot correlations not visible in raw data (e.g., hydropower stocks clustering during monsoon seasons).

3. Autoencoders

Autoencoders are neural networks that learn compressed representations via unsupervised learning. They consist of:

1. Encoder: Maps input $x$ to a latent-space representation $z$ (bottleneck layer).
2. Decoder: Reconstructs $x^{\prime }$ from $z$.
3. Loss function: Measures reconstruction error (e.g., MSE, cross-entropy).

Architecture

flowchart LR
    A["Input: High-D Data"] --> B["Encoder: Dense Layers"]
    B --> C["Bottleneck: Latent Space (Low-D)"]
    C --> D["Decoder: Dense Layers"]
    D --> E["Output: Reconstructed Data"]
    E -->|"Loss (MSE)"| F["Backpropagation"]
    F --> B

How Autoencoders Work

1. Forward pass:
   • Encode: $z=f_{\text{encoder}}(x)$ (e.g., $z=\sigma (Wx+b)$).
   • Decode: $x^{\prime }=f_{\text{decoder}}(z)$.
2. Loss calculation:
   • $\text{Loss}=\Vert x-x^{\prime }{\Vert }^2$ (MSE for regression-like data).
3. Backpropagation:
   • Update weights to minimize loss, forcing $z$ to capture essential features.

Variants

Worked Example: Denoising Handwritten Digits

1. Input: Noisy MNIST digit (e.g., 28×28 pixels with Gaussian noise added).
2. Encoder:
   • Layer 1: 784 → 256 neurons (ReLU activation).
   • Layer 2: 256 → 32 neurons (bottleneck, latent space).
3. Decoder:
   • Layer 1: 32 → 256 neurons (ReLU).
   • Layer 2: 256 → 784 neurons (sigmoid for pixel values).
4. Training:
   • Loss: MSE between input and output.
   • After 50 epochs, the autoencoder reconstructs clean digits from noisy inputs.

Autoencoders vs. PCA/t-SNE

4. Applications in Nepal and Globally

In Nepal

1. eSewa and Khalti:

   • Idea Used: Dimensionality reduction for fraud detection.
   • How:
     • Transaction data (e.g., amount, time, location) is high-dimensional.
     • PCA reduces features to 2D/3D, then clustering (e.g., DBSCAN) flags anomalies.
     • Example: A sudden large transaction in an unusual location triggers a red flag.

2. NTC and Ncell:

   • Idea Used: Autoencoders for network traffic compression.
   • How:
     • Raw network packets (e.g., 50+ features per packet) are compressed via autoencoders.
     • Latent space is used for intrusion detection (e.g., unusual traffic patterns).

3. Daraz/Nepal Stock Exchange (NEPSE):

   • Idea Used: t-SNE for customer segmentation.
   • How:
     • User behavior data (e.g., clickstream, purchase history) is reduced to 2D.
     • Visual clusters reveal groups (e.g., "budget shoppers" vs. "luxury buyers").

Global Examples

1. Google Photos:

   • Idea Used: Autoencoders for image compression.
   • How:
     • Images are encoded into a compact latent space, reducing storage by ~50% without losing quality.

2. Netflix Recommendations:

   • Idea Used: PCA for collaborative filtering.
   • How:
     • User-movie ratings (sparse high-D matrix) are reduced to 2D/3D, then KNN finds similar users.

3. Self-Driving Cars (Tesla, Waymo):

   • Idea Used: t-SNE for sensor data visualization.
   • How:
     • Lidar/camera data (millions of points) is reduced to 2D to visualize vehicle surroundings in real-time.

5. Choosing the Right Technique

Use this flowchart to select a method:

flowchart TD
    A["Need Dimensionality Reduction?"] --> B{"Linear or Nonlinear Data?"}
    B -->|"Linear"| C["Use PCA"]
    B -->|"Nonlinear"| D{"Goal: Compression or Visualization?"}
    D -->|"Compression"| E["Use Autoencoder"]
    D -->|"Visualization"| F["Use t-SNE"]
    C --> G["Check Variance Explained"]
    G -->|">95%"| H["Done"]
    G -->|"<95%"| I["Try Kernel PCA or Autoencoder"]

When to Use What

6. Pitfalls and Best Practices

Common Mistakes

1. Forgetting to standardize data:

   • PCA is sensitive to feature scales. Always use StandardScaler before applying PCA.
   • Example: If one feature has values in [0, 1000] and another in [0, 1], PCA will ignore the latter.

2. Over-relying on t-SNE for analysis:

   • t-SNE is for visualization only. Do not use it for downstream tasks (e.g., classification) without validation.

3. Ignoring the "elbow" in explained variance:

   • Always plot the cumulative variance vs. number of components. Stop at the "elbow" (point of diminishing returns).

Best Practices

• For PCA:
  • Use sklearn.decomposition.PCA with svd_solver='auto' for efficiency.
  • Set n_components to retain ≥95% variance unless domain knowledge suggests otherwise.
• For t-SNE:
  • Tune perplexity (typically 5–50) to balance local/global structure.
  • Use early_exaggeration in sklearn.manifold.TSNE for better convergence.
• For Autoencoders:
  • Start with a small bottleneck layer (e.g., 32–128 units) and increase if needed.
  • Use dropout or L1/L2 regularization to prevent overfitting.

7. Mathematical Deep Dive: Kernel PCA

PCA assumes linearity. Kernel PCA extends it to nonlinear manifolds by:

1. Mapping data to a higher-D space via a kernel function (e.g., RBF): $$\varphi (x_i)\cdot \varphi (x_j)=K(x_i,x_j)$$
2. Applying PCA in this new space.

Example: Kernel PCA with RBF Kernel

Given data $X=[x_1,x_2,x_3]$ in 2D:

1. Compute kernel matrix $K$: $$K_{ij}=\exp (-\gamma \Vert x_i-x_j{\Vert }^2)$$ (e.g., $\gamma =0.1$).

2. Center the kernel matrix: $$K_{\text{centered}}=K-1_{n}K-K{1}_n+1_{n}K{1}_n$$ where $1_n$ is a matrix of ones.

3. Eigen decomposition of $K_{\text{centered}}$:

   • Select top-k eigenvectors to project data.

Visualization

8. Real-World Worked Example: Traffic Route Optimization in Kathmandu

Problem: Kathmandu’s traffic data includes:

• 50 sensors measuring speed, congestion, and time (high-dimensional).
• Goal: Find optimal routes for Pathao drivers in real-time.

Solution:

1. Data Collection:

   • Features: [speed, congestion index, time of day, weather, accidents, holidays].
   • Target: Route efficiency score (0–10).

2. Dimensionality Reduction:

   • Step 1: Standardize data (mean=0, std=1).
   • Step 2: Apply PCA to reduce to 3D (retaining 92% variance).
   • Step 3: Use the top 3 PCs as input to a clustering algorithm (e.g., K-means) to group similar routes.

3. Results:

   • Cluster 1: High-speed, low-congestion routes (e.g., Thapathali to Koteshwor).
   • Cluster 2: Slow, congested routes (e.g., Thamel during peak hours).
   • Pathao’s algorithm now selects routes based on cluster labels + real-time sensor updates.

Visualization:

9. Implementation in Python

PCA with Scikit-Learn

from sklearn.decomposition import PCA
from sklearn.preprocessing import StandardScaler
import numpy as np

# Sample data (5 samples, 3 features)
X = np.array([[1.2, -0.5, 0.8],
              [-0.8, 1.1, 0.3],
              [0.5, -0.9, -1.2],
              [1.5, 0.2, -0.5],
              [-0.3, 0.7, 1.0]])

# Standardize
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Apply PCA
pca = PCA(n_components=2)
X_pca = pca.fit_transform(X_scaled)

print("Explained variance ratio:", pca.explained_variance_ratio_)
print("Transformed data:\n", X_pca)

t-SNE with Scikit-Learn

from sklearn.manifold import TSNE

# Apply t-SNE
tsne = TSNE(n_components=2, perplexity=5, random_state=42)
X_tsne = tsne.fit_transform(X_scaled)

print("t-SNE transformed data:\n", X_tsne)

Autoencoder with Keras

from tensorflow.keras.models import Model
from tensorflow.keras.layers import Input, Dense

# Define autoencoder
input_dim = 3
encoding_dim = 2

input_layer = Input(shape=(input_dim,))
encoder = Dense(encoding_dim, activation="relu")(input_layer)
decoder = Dense(input_dim, activation="sigmoid")(encoder)

autoencoder = Model(inputs=input_layer, outputs=decoder)
autoencoder.compile(optimizer='adam', loss='mse')

# Train
autoencoder.fit(X, X, epochs=50, batch_size=1, verbose=0)

# Extract encoder
encoder_model = Model(inputs=input_layer, outputs=encoder)
latent_space = encoder_model.predict(X)
print("Latent space:\n", latent_space)

In the Real World

1. Khalti’s Fraud Detection:

   • Idea: PCA reduces transaction features (e.g., amount, time, location) to 2D/3D.
   • How: Unusual projections (e.g., a transaction far from the cluster centroid) trigger alerts.
   • Impact: Reduces false positives by 40% compared to rule-based systems.

2. Daraz’s Product Recommendations:

   • Idea: Autoencoders compress user-item interaction data (e.g., clicks, purchases) into a latent space.
   • How: The latent vectors are used in a collaborative filtering model to recommend products.
   • Impact: Increases conversion rates by 15% by focusing on compressed user preferences.

3. NTC’s Network Anomaly Detection:

   • Idea: t-SNE visualizes high-D network traffic data (e.g., packet headers, timestamps).
   • How: Clusters of normal traffic are identified; outliers (e.g., DDoS attacks) are flagged manually.
   • Impact: Reduces false alarms by visualizing traffic patterns in 2D.

Exam Tip

1. Theory Questions:

   • PCA: Always explain eigen decomposition and variance explained. Draw the covariance ellipse and PCs.
   • t-SNE: Focus on KL divergence and the role of perplexity. Mention it’s for visualization, not compression.
   • Autoencoders: Describe the encoder-decoder architecture and the bottleneck layer. Compare with PCA.

2. Numerical Problems:

   • PCA: Given a covariance matrix, compute eigenvalues/vectors manually (for 2D/3D data). Show the projection step.
   • Example: If the covariance matrix is diagonal, the eigenvectors are the standard basis vectors.
   • t-SNE: No manual calculations expected, but know the formula for $p_{j|i}$ and $q_{ij}$.

3. Applications:

   • Link techniques to real-world scenarios (e.g., "How would you use PCA to compress images for Daraz?").
   • Discuss trade-offs (e.g., "Why not use t-SNE for fraud detection?" → Answer: It’s stochastic and not deterministic).

4. Code Questions:

   • Be ready to write PCA/t-SNE code in Python using scikit-learn. Know the key parameters:
     • PCA: n_components, svd_solver.
     • t-SNE: n_components, perplexity, init.
   • For autoencoders, sketch the architecture and explain the loss function.

5. Common Pitfalls:

   • Don’t forget standardization for PCA.
   • Don’t confuse t-SNE with PCA (t-SNE is for visualization, PCA for compression).
   • Autoencoders are not just for compression—they can learn features (e.g., denoising AEs).

6. Diagrams:

   • Must-draw figures:
     • PCA: Covariance ellipse with PCs as axes.
     • t-SNE: 2D scatter plot with clusters labeled.
     • Autoencoder: Bottleneck architecture.
   • Avoid: Venn diagrams, generic flowcharts without context.

Pro Tip: For numerical problems, always show intermediate steps (e.g., covariance matrix, eigenvalues). Examiners reward clarity and correctness over speed.