class: center, middle, inverse, title-slide .title[ # Dimension ReductionEvaluation ] .author[ ### Anastasios Panagiotelis ] .institute[ ### University of Sydney ] --- #Outline - "Topological" measures -- + Lee, J.A. and Verleysen, M., (2009), Quality assessment of dimensionality reduction: Rank-based criteria. *Neurocomputing*, **72**, pp.1431-1443. -- - "Geometric" measures -- + Goldberg, Y. and Ritov, Y.A., (2009), Local procrustes for manifold embedding: a measure of embedding quality and embedding algorithms. *Machine learning*, **77**, pp.1-25. --- class: center, middle, inverse # How to evaluate manifold learning? --- # Motivation - Quality measures can be used to compare -- + Different Algorithms (e.g. Isomap v LLE). -- + Different tuning parameters for a given algorithm (e.g. number of nearest neighbours). -- + Different output dimension (choose `\(d\)`). -- - Also is the output accurate in some 'absolute' sense? --- # Topological measures - Main focus will be on "topological" measures (my terminolgy). -- - Are the input neighbours the same/similar as the output neighbours? -- - A unifying framework for these is provided by the co-ranking matrix --- # Distance ranks - Letting `\(\delta_{ij}\)` be the Euclidean distance between `\(\bx_i\)` and `\(\bx_j\)` and `\(d_{ij}\)` be the Euclidean distance between `\(\by_i\)` and `\(\by_j\)` denote -- `$$\begin{align}\rho_{ij}&=\left\{k:\delta_{ik}<\delta_{ij}\right\}\\r_{ij}&=\left\{k:d_{ik}<d_{ij}\right\}\end{align}$$` -- - These are the ranks of the input and output interpoint distances respectively. --- # Co-Ranking matrix - Let the matrix `\(\bQ\)` have elements -- `$$q_{kl}=|\left\{(i,j):d_{ij}=k,\delta_{ij}=l\right\}|$$` -- - This counts the number of pairs for which a distance ranked `\(l\)` in the input space is ranked `\(k\)` in the output space. -- - Non-zeros in lower triangle indicate distant input points collapsed together. -- - Non-zeros in upper triangle indicate close input points pulled apart. --- # S Curve ```r dat <- loadDataSet("3D S Curve") plot(dat,type='3varsrgl') ```
--- # Isomap (K=20) ```r isoout20 <- embed(dat, "Isomap", knn = 20) plot(isoout20, type = "2vars") ``` <img src="12Eval_files/figure-html/unnamed-chunk-3-1.png" height="450" style="display: block; margin: auto;" /> --- #Co-Ranking <img src="12Eval_files/figure-html/unnamed-chunk-4-1.png" height="450" style="display: block; margin: auto;" /> --- # Isomap (K=5) ```r isoout4 <- embed(dat, "Isomap", knn = 5) plot(isoout4, type = "2vars") ``` <img src="12Eval_files/figure-html/unnamed-chunk-5-1.png" height="450" style="display: block; margin: auto;" /> --- #Co-Ranking <img src="12Eval_files/figure-html/unnamed-chunk-6-1.png" height="450" style="display: block; margin: auto;" /> --- # Isomap (K=500) ```r isoout500 <- embed(dat, "Isomap", knn = 500) plot(isoout500, type = "2vars") ``` <img src="12Eval_files/figure-html/unnamed-chunk-7-1.png" height="450" style="display: block; margin: auto;" /> --- #Co-Ranking <img src="12Eval_files/figure-html/unnamed-chunk-8-1.png" height="450" style="display: block; margin: auto;" /> --- # Remarks - A narrow ridge along the diagonal indicates input and output distances have similar rank. -- - The input distances are Euclidean distances in the ambient space and not geodesics. -- + Non zeros in the bottom right hand corner (upper triangle) are not necessarily a bad thing. -- - Can these plots be summarised into a single number? --- # LCMC - The local continuity meta criterion can be expressed in terms of the `\(\bQ\)` matrix as -- `$$LCMC=\frac{H}{1-N}+\frac{1}{NH}\sum\limits_{h=1}^H\sum\limits_{h=1}^H q_{hl}$$` -- - The parameter `\(H\)` does not need to be the same as the nearest neighbours used in the manifold learning algorithm --- # LCMC <img src="12Eval_files/figure-html/unnamed-chunk-9-1.png" height="450" style="display: block; margin: auto;" /> --- class: inverse, middle, center # Geometric Properties --- # Topology v Geometry - Quality measures so far based on ranks of distances. -- - Only measure how well algorithm preserves the topology of manifold. -- - Interpreting the output of manifold learning often involves comments about distances, angles, and shapes of scatterplots. -- - Makes sense to have a measure that reflects whether these quantities are preserved. --- # Local Procrustes measure - Take a small neighbourhood of `\(k\)` points around input point `\(i\)` + Stack into a `\(p\times k\)` matrix `\(\bX_{(i)}\)` with columns `\(\bx_j:\bx_j\in N(\bx_i)\)` + Stack into a `\(m\times k\)` matrix `\(\bY_{(i)}\)` with columns `\(\by_j:\bx_j\in N(\bx_i)\)` -- - Rotate and translate into a `\(p\)`-dimensional space. -- + This is done via `\(\bA\bY_{(i)}+\bbb\)` where `\(\bA'\bA=\bI\)` -- - Do this so `\(\bX_{(i)}\)` and `\(\bY_{(i)}\)` "match" up --- # Why "Procrustes"? <img src="img/Prokroustis.jpg" width="227" height="450" style="display: block; margin: auto;" /> --- # Procrustes Analysis - Procrustes Analysis is all about matching up similar shapes. -- - Used in biology and computer vision (amongst other areas). -- - The version we consider only allows for translations and rotations since other distortions would distort the geometry of our points. --- # Local Procrustes Measure - For all `\(i\)` find -- `$$G(\bX_{(i)},\bY_{(i)})=\underset{\bA,\bbb:\bA'\bA=\bI}{\min}||(\bX_{(i)}-\bA\bY_{(i)}-\iota\bbb')||_F$$` -- - The values of `\(\bA\)` and `\(\bbb\)` can be solved using the singular value decomposition. -- - The overall measure is given by -- `$$G=\sum\limits_{i=1}^{N}\frac{G(\bX_{(i)},\bY_{(i)})}{||\bH\bX_{(i)}||^2_F}$$` --- class: inverse, center, middle # Concluding Remarks --- # Concluding Remarks - Hopefully you now appreciate the value of dimension reduction algorithms. -- - You should now be able to potentially apply these algorithms to your own research problems. -- - Also I hope you have an appreciation on how dimension reduction algorithms draw on different fields of mathematics. --- # Open problems - Finding the dimension of the manifold. -- - Finding tuning parameters. -- - Better understanding of why and when certain algorithms perform better. -- - Better understanding of non-uniform sampling on a manifold