Unit4 - Subjective Questions

The Curse of Dimensionality refers to various phenomena that arise when analyzing and organizing data in high-dimensional spaces that do not occur in low-dimensional settings.

Impacts on Machine Learning Algorithms:

• Sparsity of Data: As the number of dimensions increases, the volume of the space increases exponentially, making the available data sparse. This sparsity makes it difficult to find statistical significance.
• Distance Metrics Degradation: In high-dimensional spaces, the difference between the maximum and minimum distances between data points approaches zero. Algorithms relying on distance metrics (like k-NN or K-Means) lose their effectiveness because all points appear almost equidistant.
• Overfitting: With many features, machine learning models become overly complex and tend to memorize the training data (including noise), leading to poor generalization on unseen data.
• Computational Cost: High dimensions drastically increase the computational time and memory required to train models.

Dimensionality Reduction is the process of reducing the number of random variables under consideration by obtaining a set of principal variables. It transforms data from a high-dimensional space into a low-dimensional space while retaining meaningful properties of the original data.

Primary Reasons for Dimensionality Reduction:

• Mitigating the Curse of Dimensionality: Reduces data sparsity and improves distance metric reliability.
• Computational Efficiency: Fewer features mean less computation time and less memory usage during model training and inference.
• Data Visualization: It is impossible to visualize data in more than 3 dimensions. Techniques like PCA and t-SNE reduce data to 2D or 3D, allowing humans to identify patterns, clusters, and outliers.
• Noise Reduction: Many dimensions represent irrelevant features or noise. Removing them can improve model accuracy.
• Simplifying Models: A model with fewer features is simpler, easier to interpret, and less prone to overfitting.

Both Feature Selection and Feature Extraction are techniques used to reduce dimensionality, but they operate differently:

Feature Selection:

• Definition: The process of selecting a subset of relevant, existing features from the original dataset.
• Mechanism: It evaluates existing features and discards those that are redundant or irrelevant.
• Output: The resulting features are exactly the same as the original ones, just fewer in number.
• Examples: Variance Thresholding, Recursive Feature Elimination (RFE), L1 Regularization (Lasso).

Feature Extraction:

• Definition: The process of transforming the original high-dimensional features into a new, lower-dimensional set of features.
• Mechanism: It combines original features to create new, independent variables that capture the most important information.
• Output: The resulting features are entirely new and often lack the physical interpretation of the original features.
• Examples: Principal Component Analysis (PCA), Autoencoders, t-SNE.

Geometric Intuition of PCA:

Imagine a scatter plot of data points in a 2D space. The data forms an elliptical cloud. PCA seeks to find a new coordinate system for this data such that the axes represent the directions of maximum variance.

1. Finding the First Principal Component (PC1): PCA looks for a straight line through the data that minimizes the orthogonal projection distances from the data points to the line. Geometrically, this is equivalent to finding the direction in which the data is most spread out (maximum variance).
2. Finding the Second Principal Component (PC2): The second principal component is calculated under the constraint that it must be orthogonal (perpendicular) to the first principal component. Among all possible orthogonal directions, PC2 captures the second largest variance.
3. Rotation: PCA essentially rotates the original coordinate axes to align with these new principal components. The center of the data (mean) becomes the origin of the new coordinate system.
4. Dimensionality Reduction: To reduce dimensions, we project the data onto the first principal components, discarding the components with negligible variance (which geometrically represent 'thickness' or noise in the data cloud).

Step-by-Step Algorithm for PCA:

1. Standardization: Standardize the -dimensional dataset so that each feature has a mean of 0 and a variance of 1.
   
2. Covariance Matrix Computation: Compute the covariance matrix of the standardized data to understand how variables vary together.
   
   where is the data matrix.
3. Eigen Decomposition: Calculate the eigenvectors and eigenvalues of the covariance matrix .
   
   Here, represents the eigenvectors (principal directions) and represents the eigenvalues (magnitude of variance).
4. Sorting: Sort the eigenvalues in descending order and arrange the corresponding eigenvectors accordingly. This ranks the principal components by their significance.
5. Projection Matrix Creation: Select the top eigenvectors corresponding to the largest eigenvalues to form a projection matrix of shape .
6. Transformation: Project the original data onto the new subspace using the projection matrix .
   
   The new dataset has dimensions .

In PCA, eigenvectors and eigenvalues are derived from the covariance matrix of the data and play a fundamental role in defining the new feature space:

• Eigenvectors: These are vectors that do not change their direction when a linear transformation (the covariance matrix) is applied to them. In PCA, the eigenvectors of the covariance matrix represent the directions of the new feature axes (the Principal Components). They are orthogonal to each other.
• Eigenvalues: Each eigenvector has a corresponding eigenvalue. The eigenvalue represents the magnitude or the amount of variance in the data that is captured along the direction of its corresponding eigenvector.

Role in PCA:
By pairing eigenvectors with their eigenvalues and sorting them in descending order based on the eigenvalues, PCA allows us to identify which principal components (directions) are the most important. To reduce dimensionality, we keep the eigenvectors with the highest eigenvalues and discard those with near-zero eigenvalues, as they contain very little information (variance).

Manifold Learning is a class of non-linear dimensionality reduction techniques based on the premise that high-dimensional data actually lies on or near a lower-dimensional manifold embedded within the high-dimensional space. The goal is to unroll or unfold this manifold to reveal its true low-dimensional structure.

The Swiss Roll Example:

• Imagine a flat, rectangular sheet of dough with some sprinkles scattered on it (a 2D manifold).
• Now, roll this sheet up into a spiral shape (a Swiss Roll) in a 3D space. The data now appears to be 3-dimensional.
• If we apply a linear technique like PCA to this 3D Swiss Roll, it will simply squash the spiral flat into 2D, causing data points from different layers of the roll to overlap. It destroys the true structural relationship.
• Manifold Learning algorithms attempt to "unroll" the Swiss Roll back into the flat 2D sheet. They understand that the true distance between two sprinkles is the distance along the surface of the dough (the manifold), not the straight-line distance cutting through empty 3D space.

Understanding the difference between these two distance metrics is crucial for Manifold Learning:

• Euclidean Distance:

  • Definition: The straight-line distance between two points in the ambient high-dimensional space.
  • Formula (2D):
  • Limitation: In manifold learning (e.g., the Swiss Roll), Euclidean distance might measure the distance between two points on different layers of the roll by cutting straight through the empty space. It fails to capture the actual structure of the data.

• Geodesic Distance:

  • Definition: The shortest path between two points along the surface of the manifold.
  • Intuition: Imagine an ant walking from point A to point B on a curved surface; the geodesic distance is the length of the ant's path.
  • Advantage: Geodesic distance correctly captures the intrinsic geometry of the data. Manifold learning algorithms (like Isomap) estimate geodesic distances by constructing a neighborhood graph and calculating the shortest path along the edges of the graph.

Linear dimensionality reduction techniques like PCA assume that the data lies on a linear subspace. They fail on complex real-world data for the following reasons:

1. Inability to Capture Non-Linear Relationships: PCA can only perform linear transformations (rotations and scaling). If the data lies on a curved, non-linear manifold (like a sphere or a Swiss roll), PCA will simply flatten the data, losing the underlying topological structure.
2. Overlapping Subspaces: When projecting non-linear data linearly, points that are far apart on a curved manifold might be projected onto the same coordinate in the lower-dimensional space, causing classes or clusters to overlap entirely.
3. Global vs. Local Structure: PCA focuses on maximizing global variance. It does not explicitly attempt to preserve local neighborhood structures. In complex datasets (like images or text), the local relationships between nearby points are often more informative than global variance.

Because real-world data (e.g., images, voice, text) is highly non-linear, non-linear techniques like t-SNE, UMAP, or Autoencoders are required to accurately model their lower-dimensional representations.

t-SNE (t-Distributed Stochastic Neighbor Embedding) is a non-linear dimensionality reduction technique primarily used for data visualization of high-dimensional datasets.

Conceptual Framework:

1. Probability in High-Dimensional Space: t-SNE starts by calculating the probability that a pair of data points are neighbors in the high-dimensional space. It uses a Gaussian distribution centered at each point. Points that are close together have a high probability of being chosen as neighbors, while points far apart have an infinitesimally small probability.
2. Probability in Low-Dimensional Space: Next, t-SNE creates a similar probability distribution for the points in the target low-dimensional space (usually 2D or 3D). However, it uses a Student's t-distribution (which has heavier tails than a Gaussian) to compute these probabilities.
3. Minimizing Divergence: The goal of t-SNE is to make the low-dimensional probability distribution match the high-dimensional probability distribution as closely as possible. It does this by minimizing the Kullback-Leibler (KL) divergence between the two distributions using Gradient Descent.
4. Result: The algorithm iteratively adjusts the positions of the points in the low-dimensional space until the local neighborhood structure of the high-dimensional space is preserved.

The Crowding Problem in SNE:
In high-dimensional space, the volume scales exponentially. Therefore, a single point can have a massive number of neighbors that are relatively close. When reducing to a 2D or 3D space, there simply isn't enough "room" to accommodate all these points at the correct relative distances. As a result, standard SNE tends to crush all points together in the center of the low-dimensional map, making it impossible to distinguish clusters. This is known as the crowding problem.

How t-SNE solves it:
t-SNE solves the crowding problem by changing the probability distribution used in the low-dimensional space. While standard SNE uses a Gaussian distribution for both high and low dimensions, t-SNE uses a Student's t-distribution with one degree of freedom (a Cauchy distribution) for the low-dimensional space.

• The t-distribution has heavy tails compared to a Gaussian.
• To match the probabilities of moderately distant points in the high-dimensional Gaussian space, the heavy-tailed t-distribution requires these points to be placed much further apart in the low-dimensional space.
• This effectively pushes moderately distant points further away from each other, alleviating the crowding in the center and resulting in clear, distinct clusters.

In t-SNE, the Kullback-Leibler (KL) divergence acts as the cost function (or loss function) that the algorithm attempts to minimize.

• Function of KL Divergence: KL divergence measures how one probability distribution differs from a second, reference probability distribution.
• Application in t-SNE: t-SNE calculates two sets of pairwise probabilities:
  1. : The probability of points and being neighbors in the high-dimensional space.
  2. : The probability of points and being neighbors in the low-dimensional space.
• Optimization: The cost function is the sum of KL divergences over all pairs of points:
  
• Behavior:
  • If is large (points are close in high-D) and is small (points are far in low-D), the penalty is very high. Thus, t-SNE strongly prioritizes preserving local structures.
  • If is small (points are far in high-D) and is large, the penalty is relatively small.
• Gradient descent is used to minimize this cost function, updating the coordinates of the low-dimensional points.

Comparison of PCA and t-SNE:

UMAP (Uniform Manifold Approximation and Projection) is a modern non-linear dimensionality reduction technique based on Riemannian geometry and algebraic topology.

Conceptual Intuition:

1. Topological Representation: UMAP assumes that the data is uniformly distributed on a Riemannian manifold. Since real data is rarely uniform, UMAP defines a custom, local distance metric for each data point based on the distance to its nearest neighbor. This localized distance ensures that the data appears 'uniform' locally.
2. Fuzzy Simplicial Complex: UMAP constructs a high-dimensional graph (a fuzzy simplicial complex) connecting data points based on these local distances. Edges have weights representing the likelihood that two points are connected.
3. Low-Dimensional Optimization: UMAP then initializes a low-dimensional layout (usually using Spectral Embedding rather than random initialization) and constructs a similar fuzzy graph in the low-dimensional space.
4. Cross-Entropy Minimization: Unlike t-SNE which uses KL divergence, UMAP minimizes the Cross-Entropy between the high-dimensional graph and the low-dimensional graph. This forces the low-dimensional representation to capture both the local neighborhood structure and, to a better extent than t-SNE, the global structure of the data.

While both UMAP and t-SNE are excellent for visualizing non-linear data, UMAP offers several distinct advantages:

1. Speed and Scalability: UMAP is significantly faster than t-SNE. It can handle much larger datasets and higher dimensional spaces without the severe computational bottlenecks associated with t-SNE.
2. Preservation of Global Structure: t-SNE is notorious for preserving local clusters but completely distorting the global distances between those clusters. Because UMAP utilizes cross-entropy and different topological principles, it strikes a much better balance between preserving local neighborhoods and maintaining the global macroscopic structure of the data.
3. Support for New Data: UMAP allows for a fitted model to transform new, unseen data into the existing lower-dimensional space. Standard t-SNE lacks this capability (it is non-parametric in that sense) and must be rerun on the entire dataset.
4. Flexibility of Metric: UMAP can handle a wider variety of distance metrics beyond just Euclidean distance (e.g., cosine, Manhattan, Hamming).

An Autoencoder is a type of artificial neural network used in unsupervised learning to learn efficient representations (encodings) of unlabeled data. The network is trained to output a reconstruction that is as close as possible to its original input.

Basic Architecture:

1. Encoder: The first part of the network takes the high-dimensional input data and applies a series of hidden layers (linear transformations and non-linear activations) to compress it. Mathematically: .
2. Bottleneck (Latent Space): The central layer of the autoencoder has significantly fewer nodes than the input layer. This forces the network to compress the data, extracting only the most essential features (the latent representation or code ). This is where the dimensionality reduction occurs.
3. Decoder: The second part of the network takes the compressed code from the bottleneck and attempts to reconstruct the original input data. It mirrors the encoder's structure but expands the dimensions. Mathematically: .

The goal is to train the network weights to minimize the difference between the input and the output .

Reconstruction Loss is the objective function used to train an Autoencoder. It measures the discrepancy between the original input data () and the reconstructed output data () produced by the decoder.

Concept and Role:

• The autoencoder's goal is identity mapping (output = input). However, because the data must pass through a constrained bottleneck layer, it cannot simply memorize the data. It must learn a compressed, meaningful representation.
• The reconstruction loss quantifies how much information was lost during this compression-decompression cycle.
• Common Metrics:
  • For continuous data, Mean Squared Error (MSE) is commonly used:
  • For binary or probabilistic data, Binary Cross-Entropy (BCE) is often used.
• Learning Process: During training, Backpropagation calculates the gradient of the reconstruction loss with respect to the network's weights. Gradient descent algorithms (like Adam or SGD) update the weights of both the encoder and decoder to minimize this loss, forcing the bottleneck to learn the most salient features of the data.

Relationship with PCA:
If an Autoencoder is constructed with only a single hidden layer (the bottleneck) and uses purely linear activation functions (like the identity function), the network learns to project the data onto a linear subspace that minimizes the mean squared reconstruction error.

• In this scenario, the subspace learned by the bottleneck layer of the autoencoder is essentially the same subspace spanned by the Principal Components in PCA.
• While the exact weights might not be identical to PCA's eigenvectors (they might not be orthogonal), they span the exact same linear plane.

Benefit of Non-Linear Activation Functions:
The true power of Autoencoders emerges when we use non-linear activation functions (like ReLU, Sigmoid, or Tanh) and add multiple hidden layers (Deep Autoencoders).

• Non-linearity allows the autoencoder to model complex, curved manifolds in the data.
• It acts as a non-linear dimensionality reduction technique, capturing complex relationships and structures that PCA (a strictly linear technique) would completely miss.

Removing the Bottleneck:
If an autoencoder has an internal layer with a dimensionality equal to or greater than the input layer (without any constraints), it is called an Overcomplete Autoencoder.

Consequences:

• If left unconstrained, the autoencoder can trivially learn the identity function. It can just copy the input directly to the output without learning any useful or compressed representation of the data.
• It defeats the purpose of dimensionality reduction and representation learning because no underlying patterns or structures are extracted.

Making Overcomplete Autoencoders Useful:
To make an overcomplete architecture useful for feature extraction, we must add regularizations or constraints. Examples include:

• Sparse Autoencoders: Adding a sparsity penalty (like L1 regularization) to the hidden layer activations, forcing only a small number of neurons to fire at once.
• Denoising Autoencoders: Corrupting the input data with noise and forcing the network to reconstruct the original, uncorrupted data, forcing it to learn robust features rather than copying.

Perplexity is a crucial hyperparameter in the t-SNE algorithm that roughly defines the number of effective nearest neighbors each data point has.

Significance:

• Balancing Local and Global Aspects: Perplexity dictates how t-SNE balances attention between local and global aspects of the data. A low perplexity focuses primarily on local variations, while a high perplexity takes more global structure into account.
• Mathematical Role: It determines the variance () of the Gaussian distribution centered over each point in the high-dimensional space. A denser region of data will have a smaller variance to maintain the same perplexity.
• Tuning: Typical values range from 5 to 50.
  • If the perplexity is too low (e.g., 2), the algorithm might create artificial small clusters that represent noise rather than actual data structure.
  • If it is too high, it might merge distinct clusters together, failing to capture the local structure.
• It is highly recommended to run t-SNE with multiple perplexity values to ensure the observed clusters are robust and not just artifacts of a specific hyperparameter setting.