class: center, middle, inverse, title-slide .title[ # Dimension ReductionLLE ] .author[ ### Anastasios Panagiotelis ] .institute[ ### University of Sydney ] --- #Outline - Local Geometry -- + Affine Combination of Neighbours -- - Local Linear Embedding (LLE) algorithm -- - Applications -- - Initially proposed in Roweis, S. T., & Saul, L. K. (2000). "Nonlinear dimensionality reduction by locally linear embedding.", *Science*, **290**, 2323-2326. --- class: center, middle, inverse # Local Geometry --- #Idea - A smooth manifold may be locally flat (at least approximately). -- - Each point can be approximated by a weighted affine combination of its neighbours. -- - These weights "capture" the local geometry around that point. -- - Aim is for points in the output space to have the same local geometry (as measured by weights) --- # An artist's view <img src="img/mandolin.jpeg" width="244" height="450" style="display: block; margin: auto;" /> Girl with a Mandolin by Pablo Picasso --- # A mathematician'view - Each point `\(\bx_i\)` is estimated as a linear combination of neighbours -- `$$\bx_i\approx\sum\limits_{j\in \mathcal{N}_i} w_{ij}\bx_j$$` -- where `\(\mathcal{N}_i\)` is set of nearest neighbours of `\(\bx_i\)` -- - Subject to constraint `\(\sum\limits_{j\in \mathcal{N}_i} w_{ij}=1\)` -- - This is known as an **affine** combination. --- #Closed form solution - For each `\(i\)`, minimise `$$||\bx_i-\sum\limits_{j\in \mathcal{N}_i} w_{ij}\bx_j||_2^2$$` - Letting `\(\bC\)` be a matrix where `\(\bC_{jk}=(\bx_i-\bx_j)'(\bx_i-\bx_k)\)` the solution is `$$\bw_j=\frac{\sum\limits_k \bC^{-1}_{jk}}{\sum\limits_{k}\sum\limits_{l}\bC^{-1}_{jk}}$$` --- # Singular `\(\bC\)` - In some cases (e.g. `\(k>d\)`) the matrix `\(\bC\)` is singular. -- - This is handled by adding a small constant to the diagonal of `\(\bC\)`. -- - This has the effect of penalising large weights. --- # Example <img src="08LLE_files/figure-html/unnamed-chunk-2-1.png" height="600" style="display: block; margin: auto;" /> --- #Weights <img src="08LLE_files/figure-html/unnamed-chunk-3-1.png" height="600" style="display: block; margin: auto;" /> --- # Negative weights possible <img src="08LLE_files/figure-html/unnamed-chunk-4-1.png" height="450" style="display: block; margin: auto;" /> --- # Why an affine combination? - Local geometry should be invariant to -- + Rotation + Scaling + Translation -- - Minimising `\(||(\bx_i+\bv)-\sum\limits_{j\in \mathcal{N}_i} w_{ij}(\bx_j+\bv)||_2^2\)` -- is the same as minimising `\(||\bx_i-\sum\limits_{j\in \mathcal{N}_i} w_{ij}\bx_j||_2^2\)` -- only if weights sum to one. --- class: center, middle, inverse # LLE Algorithm --- #Three steps - Find nearest neighbours -- + Can be KNN or `\(\epsilon\)`-ball -- - Find all `\(w_{ij}\)` and put into a matrix `\(\bW\)` -- + This matrix will be sparse -- - Keeping weights fixed find output vectors `\(\by_i\)` that reflect the local geometry as encoded by the weights --- # Step three - Objective is to find `\(\by_1,\by_2,\dots,\by_n\)` to minimise -- `$$\sum\limits_{i}||\by_i-\sum\limits_j w_{ij}\by_j||^2_2$$` -- - The same objective as before but with `\(\by_i\)` in place of `\(\bx\)`. -- - Rather than optimise with respect to weights `\(w_{ij}\)`, the weights are held fixed and optimisation is with respect to `\(\by_i\)` --- # Solution - To make this problem well-posed the following constraints are placed on the `\(\by_i\)` -- - Have zero mean - Have unit variance - Are uncorrelated -- - The solution is given by finding the eigenvectors of `\((\bI-\bW)'(\bI-\bW)\)`. -- --- # Eigenvalue decomposition - The eigenvector corresponding to the smallest eigenvalue simply maps every point on the manifold to the same value. -- - This eigenvector is discarded. -- - The eigenvectors corresponding to the next `\(d\)` smallest eigenvalues are retained as the output coordinates. -- - The sparsity of `\(\bW\)`, and the need to only find a subset of eigenvectors ensures LLE is computationally efficient. --- class: center, middle, inverse # Application --- # S Curve ```r dat <- loadDataSet("3D S Curve") plot(dat,type='3varsrgl') ```
--- # Isomap (K=20) ```r isoout <- embed(dat, "Isomap", knn = 20) plot(isoout, type = "2vars") ``` <img src="08LLE_files/figure-html/unnamed-chunk-7-1.png" height="450" style="display: block; margin: auto;" /> --- # Implementation - Up until June, there was a package called `LLE` that could be called using `dimRed`. -- - This package has been removed from CRAN. -- - The following images were produced using that package, but calling from `dimRed` will no longer work. -- - An archived version of the `LLE` package can still be installed and used. --- # LLE (K=20)  --- # LLE (K=30)  --- # LLE (K=40)  --- # Pros and Cons - Advantages + Fast due to exploitation sparse eigenvalue algorithms + This can be implementation dependent -- - Disadvantages + Only captures local geometry + Can be inaccurate on less smooth parts of the manifold