### Manifolds¶

• An approach to non-linear dimensionality reduction (DR) tasks.
• Basic idea: in many cases, data dimensionality is artificially high - which adds to visualization difficulty.
• The simplest method is by taking a random projection of the data. This may aid visualization, but you're likely losing interesting structures within the data.
• Manifold learning is an extension of linear DR techniques (ex: PCA) to nonlinear data.

### Isomap (Isometric Mapping)¶

• Can be viewed an extension of MDS (Multi-dimensional Scaling) or Kernel PCA.
• Isomap finds a lower-D embedding which maintains geodesic distances between all points.
• Three algorithm steps:
• Nearest neighbor search using a BallTree.
• Shortest-path graph search: path_method selects either Dijkstra's or Floyd-Warshall algorithm. The code chooses a method, based on the dataset, if not specified.
• Partial eigenvalue decomposition:
• The embedded model is stored in the eigenvectors corresponding to the $d$ largest eigenvalues of the $NxN$ isomap kernel.
• eigen_solver controls the solver method & looks for a best method, based on the data, if not specified. The computation cost can be improved if ARPACK is used.

### Locally Linear Embedding (LLE)¶

• Finds a lower-D data projection while preserving distances between local neighborhoods.
• Algorithm description:
• Nearest neighbor search: same as above.
• Local neighborhood weight matrix construction: $kxk$, for each of $N$ local neighborhoods.
• Partial eigenvalue decomposition: same as above.

### Modified LLE (MLLE)¶

• LLE's problem is with regularization - if #neighbors > #dimensions, then matrix that defines each local neighborhood is rank deficient.
• Standard LLE solves this with a regularization parameter $r$ which is chosen due to the trace of the local weight matrix (def?). The solution should converge to a desired embedding as r->0, but there's no guarantee that it will do so. This can result in distortions.
• MLLE uses multiple weight vectors in each neighborhood to overcome this weakness.
• method="modified" controls this feature. It requires n_neighbors > n_components.
• Algorithm description:
• Nearest neighbor search: same as above.
• Local neighborhood weight matrix construction: similar to above, except for adding the weight matrix from multiple weights.
• Partial eigenvalue decomposition: same as above.

### Hessian-based LLE¶

• Another method of solving the LLE regularization problem.
• Uses a hessian-based quadratic form at each neighborhood to recover locally linear structures.
• method="hessian" controls this feature. It requires n_neighbors > n_components*(n_components+3)/2.
• Algorithm description:
• Nearest neighbor search: same as above.
• Local neighborhood weight matrix construction: similar to standard LLE, plus a QR decomposition of a local Hessian estimator.
• Partial eigenvalue decomposition: same as above.

### Local Tangent Space Alignment (LTSA)¶

• reference (2004)
• Algorithmically similar to LLE, but technically not a variant.
• LTSA finds a description of each neighborhood geometry via its tangent space
• Aligns local tangent spaces to learn the low-D embedding.
• Algorithm description:
• Nearest neighbor search: same as above.
• Weight matrix construction: (TBD)
• Partial eigenvalue decomposition: same as above.

### Multi-dimensional Scaling (MDS)¶

• wikipedia
• Technique for analyzing data similarity. Models similarity as distances in geometric space. Data can be ratings, interaction frequencies, or other similar indices.
• $S$ is the similarity matrix; $X$ = input coordinates of $n$ points. The disparities ($\hat{d}_{ij}$) are transforms of the similarities, chosen in an optimal manner.
• The objective (aka "stress") is defined as $\sum_{i < j} d_{ij}(X) - \hat{d}_{ij}(X)$.
• Two variants:
• metric: distances between two output points are set to as close together as possible to the similarity metric. (def?)
• non-metric: algorithm tries to preserve order of distances - therefore looks for a monotonic relation between the embedded-space distances.