LLE

Note

Locally Linear Embedding(LLE) is a powerful nonlinear dimensionality reduction & manifold learning technique that does not rely on projections.

Algorithm

1.Measuring how each training instance linearly relates to its closest neighbors(c.n):

\[ \hat{\mathbf{W}} = \underset{\mathbf{W}}{\mbox{argmin}}\sum_{i=1}^{n}(\mathbf{x}^{(i)} - \sum_{j\neq{i}}w_{ij}\mathbf{x}^{(j)}) \]

where \(w_{ij} = 0\) if \(\mathbf{x}^{(j)}\) is not one of the \(k\) c.n of \(\mathbf{x}^{(i)}\) and \(\sum_{j\neq{i}}w_{ij}=1\).

2.Looking for a low-dimensional representation of the training set where these local relationships are best preserved, keeping the weights fixed and finding the optimal positions:

\[ \hat{\mathbf{Z}} = \underset{\mathbf{Z}}{\mbox{argmin}}\sum_{i=1}^{n}(\mathbf{z}^{(i)} - \sum_{j\neq{i}}w_{ij}\mathbf{z}^{(j)}) \]

where \(\sum_{i=1}^{n}\mathbf{z}^{(i)} = 0\) and \(\frac{1}{n}\sum_{i=1}^{n}\mathbf{z}^{(i)}(\mathbf{z}^{(i)})^{T} = \mathbf{I}\).

Examples

from sklearn.datasets import make_swiss_roll

# 3d swiss roll
X, t = make_swiss_roll(n_samples=1000, noise=0.2, random_state=42)
X.shape

(1000, 3)

from sklearn.manifold import LocallyLinearEmbedding

# n_compnents & n_neighbors need to be specified.
lle = LocallyLinearEmbedding(n_components=2, n_neighbors=10)
X_reduced = lle.fit_transform(X)