ML Interview Q Series: Could you explain how Locally Linear Embedding works for reducing the dimensionality of data?

📚 Browse the full ML Interview series here.

Comprehensive Explanation

Locally Linear Embedding (LLE) is a powerful unsupervised learning method for dimensionality reduction. It is classified as a manifold learning technique, based on the idea that high-dimensional data often lie on or near a low-dimensional manifold. LLE attempts to capture the local geometric relationships in the data in such a way that those relationships are preserved when the data is mapped into a lower-dimensional space.

Core Idea

In high-dimensional spaces, each data point typically has some neighbors that collectively capture the local structure around that point. LLE learns weights that describe how each data point can be reconstructed (approximated) from its nearest neighbors in the original high-dimensional space. It then uses those same weights to construct each point’s lower-dimensional representation, ensuring local neighborhood relationships are preserved.

Step 1: Selecting Neighbors

For each data point x_i (in plain text for inline expressions): • We usually identify K nearest neighbors. The choice of K is crucial because it defines the local neighborhood size. • We can use Euclidean distance or other distance metrics to find these K neighbors.

Step 2: Computing Reconstruction Weights

LLE finds weights w_ij that minimize the reconstruction error for each point using its K neighbors. The algorithm solves the following optimization problem to obtain these weights:

Here: • x_i is the i-th data point in the original high-dimensional space (dimension D). • N(i) denotes the set of indices of the K nearest neighbors of x_i. • w_ij is the weight that represents the contribution of neighbor x_j in reconstructing x_i. • N is the total number of data points in the dataset. • The constraint often imposed is that the weights from each point to its neighbors sum to 1, which helps with invariance to certain transformations.

After solving for these weights, we will have a matrix W capturing local linear relationships between points and their neighborhoods.

Step 3: Generating the Low-Dimensional Embedding

In the final step, we embed the data into a space of dimension d (d < D) by constructing new points y_i that minimize a similar reconstruction cost in the low-dimensional space:

Here: • y_i is the embedding (the low-dimensional vector of dimensionality d) corresponding to x_i. • We want to preserve the exact same weights w_ij that we found in the high-dimensional space.

Mathematically, this becomes an eigenvalue problem. By imposing the constraints that the embedded points y_i have zero mean and unit covariance, we can solve for Y via standard linear algebra tools: • Compute the matrix M = (I – W)(I – W)^T, where I is the identity matrix and W is the weight matrix obtained from the reconstruction step. • Find the bottom d+1 eigenvectors of M (excluding the eigenvector corresponding to the smallest eigenvalue 0, which typically corresponds to the translation-invariance constraint). • The embedding is then found from the second to the (d+1)-th eigenvectors (similar in spirit to spectral methods like Laplacian Eigenmaps).

Properties and Advantages

• Non-linearity: LLE preserves local linear relationships but can discover complex, curved manifold structures. • No explicit function mapping: The method provides an embedding but does not produce a direct function from the original space to the latent space. • Minimal parameters: Primarily, you have to pick the neighborhood size K. Selecting K is critical because if K is too small, local relationships might become too local (or points might become disconnected); if K is too large, local neighborhoods might not be truly local.

Practical Implementation Considerations

• Data scaling: Preprocessing (e.g., normalizing or standardizing) is often beneficial. • Choice of K: Methods like cross-validation or elbow methods can be employed to find a suitable K. • Out-of-sample extension: LLE does not directly define how to embed new points that are not in the training set. Methods like barycentric interpolation using the same neighbor weights can be used for out-of-sample points. • Computational complexity: Constructing the neighbor graph and solving the eigenvalue problem can be expensive if N is large.

Follow-up Questions

What happens if the chosen number of neighbors K is too large or too small?

Choosing K too small might lead each neighborhood to contain too few points to accurately model the local geometry, causing many small disconnected local patches. This can result in poor embeddings or disconnected regions in the low-dimensional space.

On the other hand, choosing K too large can blur the local manifold structure because it starts to approximate a more global region. This can cause distortions, as the assumption that each point lies in the linear span of its few nearest neighbors is violated when the neighborhood becomes large. Practically, you want enough neighbors so that local linear reconstruction is valid, but not so many that it becomes a quasi-global operation.

How would you handle out-of-sample points in LLE?

LLE in its basic form is not designed for handling new points outside the training set. One approach is to approximate the low-dimensional representation of a new data point x_new by: • Finding the same K nearest neighbors among the original training data. • Reusing the same reconstruction weights found by minimizing the reconstruction error for x_new with those neighbors (in the original space). • Then applying those weights in the low-dimensional space to get y_new.

In code terms, you would find the neighbors of x_new using the high-dimensional space, solve for the weights w_new based on those neighbors, and finally compute y_new = sum_j( w_newj * y_j ) using the already established embeddings y_j of the neighbors.

When might Locally Linear Embedding fail or produce poor results?

LLE can produce suboptimal results when: • The manifold is highly non-uniform, with regions of very different densities, making a fixed K problematic. • The data contains significant noise or outliers that can disrupt neighborhood relationships. • The manifold is not well-sampled (e.g., if there are insufficient data points to capture the local geometry). • There is a mismatch between the chosen embedding dimension d and the intrinsic dimension of the manifold.

Additionally, if K is chosen incorrectly or if the data distribution is particularly complex, the local linear assumption might break down.

How does LLE compare to other manifold learning methods like t-SNE or Isomap?

LLE, t-SNE, and Isomap are all manifold learning techniques, but they have distinct approaches:

• LLE focuses on preserving local linear relationships via reconstruction weights. It is relatively straightforward but can be sensitive to parameters like K.

• t-SNE focuses on capturing local similarities in a probabilistic framework, often producing visually appealing embeddings especially for high-dimensional data like images. However, it can be more computationally intensive for large N and might require careful tuning of perplexity.

• Isomap preserves geodesic distances between data points by approximating the manifold distance through shortest paths in a neighborhood graph. It is more global in nature and can sometimes struggle with non-convex manifolds or noise.

Each method has its strengths and weaknesses, and the best choice often depends on the specific data, the purpose of the embedding, and resource constraints.

How does LLE ensure invariance to translations, rotations, and scalings?

In the reconstruction weight optimization, LLE constrains the sum of the weights for each point to be 1. As a result: • Translational invariance: Adding a constant vector to each data point x_i does not change the relative reconstruction error since the constant vector cancels out when the weights sum to 1. • Rotational and scaling invariance: The local reconstruction error depends only on the relative positions of points within each neighborhood. Changing the basis or uniformly scaling the data typically does not affect the relative geometry.

This invariance helps LLE to recover the intrinsic manifold structure without being distracted by certain rigid transformations.

Could LLE be used for data visualization?

Yes. A common use of LLE is to embed high-dimensional data into 2D or 3D for visualization purposes. By preserving local relationships, LLE helps reveal low-dimensional structure that might correspond to meaningful clusters or variations in the data. However, when visualizing, you still have to pay attention to the choice of K and interpret the embeddings carefully, especially if the data has very complex geometry or you have many outliers.

Is there a way to reduce the computational complexity of LLE for large datasets?

Standard LLE involves an eigen-decomposition of an N x N matrix, which becomes computationally expensive when N is large. Potential strategies to mitigate this include: • Using approximate nearest neighbor methods to find neighbors faster. • Employing randomized methods or specialized solvers for large-scale eigenvalue problems (e.g., partial or approximate SVD/eigen-decomposition). • Using landmark-based approaches: Instead of computing the entire matrix for all data points, select a subset (landmarks) to reduce the dimensionality first, and then extend to the full dataset.

These methods can help scale LLE to larger datasets while preserving its main manifold-learning characteristics.