intro_to_dimension_reduction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dimension reduction: an introduction\n",
    "\n",
    "Prepared by Alex Diaz-Papkovich for the McGill initiative in Computational Medicine (MiCM)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The best way to study something is to observe it. In the same way that a microscope allows you to look at cells and that a stethoscope allows you to listen to a beating heart, dimension reduction allows you to observe data that exists in high dimensions. That is the motivation behind dimension reduction: to figure out how to best examine or model high dimensional data, which is hard to perceive, in low dimensions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is dimension reduction?\n",
    "\n",
    "In the most obvious sense, dimensionality reduction is the process of taking some high-dimensional data and bringing it down into a low-dimensional space so that we can better comprehend the data. Some motivating examples in history include reducing globes (3D) to maps (2D), or looking at how objects (in 3D) can cast shadows (in 2D). In both of these cases you can still learn a lot from the 2D representations, but you must sacrifice some information along the way. With an object and its shadow, the angle of the light and the object's physical properties will all change your perception of what it looks like in 3D.\n",
    "\n",
    "Looking at the globe-to-map example: imagine peeling the surface of a globe and trying to place it on a table. In order to do this, you will have to stretch, compress, or tear the surface somehow. How, where, and whether you decide to do these things will be motivated by what it is you wish to highlight or preserve. A nautical map versus a local town map versus a map of the world will all have different motivations and constraints, and you would have to consider your options carefully. [There are many types of map projections!](https://en.wikipedia.org/wiki/Map_projection)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Some uses for dimension reduction\n",
    "\n",
    "Terminology note: variables are often referred to as \"features\" in the literature. A feature could be, for example, a count of a particular protein, or a low-dimensional variable that you've created via dimension reduction.\n",
    "\n",
    "### Reducing noise and pre-processing\n",
    "\n",
    "Usually most of our data is not particularly useful. However, it can be very difficult to to decide which variables to keep or discard. We can use dimension reduction to select which features to keep or discard by finding out which variables are redunant (feature selection). We can also use dimension reduction to transform our data from a high dimension to a low dimension space (feature extraction). Having fewer variables can simplify analyses, allow for more traditional methods (such as principal component regression) or make computation much faster: a pre-processing step can often take data down from millions of variables to a few dozen, reducing runtimes from hours to minutes.\n",
    "\n",
    "### Visualization and exploratory analysis\n",
    "\n",
    "Visualizations are excellent tools for interrogating and exploring your data. One of the first steps in many analyses is to visualize data -- it is much easier to study something when you can see it! A typical approach is to plot your data and colour it by available variables, such as cell type labels, patient IDs, intensity of gene expression, etc. From here you can, for example, develop a hypothesis about your data. In this sense, dimension reduction is to data what a microscope is to cells: a way to scientifically examine your subjects.\n",
    "\n",
    "### Clustering\n",
    "\n",
    "Often we are interested in questions like \"how similar are these groups?\", or \"are there sub-groups within our data?\" Clustering methods are useful here, but when data is in high dimensional space it is often very sparse -- that is, there is so much space between our points that clustering may not work. By using bringing data down to a lower dimension, we can see clusters more easily. We can then spot, for example, cell sub-types, or technical artifacts like batch effects."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Why is dimension reduction necessary in biology?\n",
    "\n",
    "Traditionally, a statistical analysis might look at a handful of variables -- say, a dozen -- measured from a manageable sample size. Typical assumptions are that you have $p$ variables and $n$ samples, and $p < n$. Biological data, though, is intrinsically very highly-dimensional. The human genome contains over 3 billion base pairs, and a brand new biobank will usually have hundreds of thousands if not millions of individuals. We may also have hundreds of phenotypes. When working with single-cell data, we usually have tens of thousands of genes, proteins, or other types of markers to consider. Our regime has gone from $p < n$ to something like $p >> n$ or $p \\approx n$ where both $n$ and $p$ are huge numbers. There are so many possibly combinations of variables and confounding factors that computationally it is basically impossible to try and analyze these data using traditional methods like a straightforward regression. \n",
    "\n",
    "One common example in modern biology is defining cell types. Traditionally we might look at cells under a microscope and describe their size, shape, colour, etc, and try to classify them. This is labour-intensive and somewhat arbitrary, since we could have very different cell types that happen to look similar. What if, instead, we looked at properties that were more intrinsic? For example, we could look at measurements of proteins or genes or RNA and classify cells this way. We could take a photo of cells and colour them by gene expression. The problem then is that we might have $20,000$ genes to work with, so we have to do this $20,000$ times (once per gene). However, lots of genes are highly expressed across multiple cell types. Alternately we could look at combinations of genes and hunt for unique combinations. The issue here is that this becomes computationally intractable: given $20,000$ genes, there are over one trillion sets of $3$ alone.\n",
    "\n",
    "This problem spans across biological fields. Examples: \n",
    "* Finding patterns while working with brain scans containing millions of voxels\n",
    "* Looking at gene expresson across embyronic development in some model species\n",
    "* Identifying sub-types of cancer given samples of cell-surface proteins across individuals\n",
    "* Identifying shared admixture patterns in large population datasets\n",
    "* Finding patterns in microbiomes\n",
    "* Clustering similar species or sub-species\n",
    "* Reducing dimensionality for statistical modeling and computational efficiency"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How does dimension reduction work?\n",
    "\n",
    "Think back to our early examples: shadows and maps. We can change the shape of a shadow based on the position of the light. If we wanted a shadow to tell us a lot about the object it belongs to, we might want to do something like position it so that the shadow is as long as the object is tall. We can do something like this with some first-year linear algebra. This type of linear transformation stretches and shifts your data.\n",
    "\n",
    "If we wanted to make a map out a globe, we might be interested in preserving distances between, say, cities when going from 3D to 2D. But with a map we would have to distort relationships eventually (for example, long distances between cities would be less accurate than short distances).\n",
    "\n",
    "The basic idea is that your high-dimensional data can be represented in some low-dimensional space. This low-dimensional space could be something like a line, or perhaps a more complicated non-linear shape, like a curve (also called a manifold). By looking at linear and non-linear transformations of your data, you can learn much more about it or optimize how you use it.\n",
    "\n",
    "### The mathematical side\n",
    "\n",
    "Let us assume that our data, $X$, consists of rows as samples and columns as features. For example, the rows could be people or cells, and the columns could be base pairs or gene counts. There are, broadly, two approaches that underly most dimension reduction techniques: matrix factorization and neighbour graphs.$^1$\n",
    "\n",
    "Matrix factorization tries to define our matrix of data as the approximate product of some lower rank matrices: \n",
    "\n",
    "$$X_{N \\times D} \\approx U_{N \\times d}V_{d \\times D}$$\n",
    "\n",
    "We then minimize some loss function, $\\sum_{i=1}^{N} \\sum_{j=1}^{D}\\text{Loss}(X_{ij}, (UV)_{ij})$ subject to constraints. The different combinations of loss functions and constraints then define what our method is. If our loss function is the mean-squared error with no constraints, then we are working with PCA. Other methods include non-negative matrix facotorization (NNMF) and linear discriminant analysis (LDA). \n",
    "\n",
    "Sometimes our data doesn't lie nicely on lines so linear methods like PCA won't capture the underlying structure. Neighbour graphs instead build a mesh by drawing edges between the points of our data. How we construct this mesh, and how we choose to reconstruct it in a lower dimension, determines what our method is. Examples of neighbour graph methods include t-SNE, UMAP, and Isomap.\n",
    "\n",
    "$^1$This is not strictly true, but from an [excellent video summary by Leland McInnes](https://www.youtube.com/watch?v=9iol3Lk6kyU)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Common methods\n",
    "\n",
    "There are an ever-growing number of dimension reduction techniques. Many of them are closely related to each other and offer minor tweaks to existing approaches to make them more suitable for a particular problem. We will focus on three methods in this workshop:\n",
    "\n",
    "* Principal compoments analysis (PCA)\n",
    "* t-distributed stochastic neighbour embedding (t-SNE)\n",
    "* Uniform manifold approximation and projection (UMAP)\n",
    "\n",
    "These three were selected because they are the most commonly used in genomics. However, this is not an endorsement of them over other methods -- by all means, experiment with whichever ones you find interesting!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Principal component analysis (PCA)\n",
    "\n",
    "PCA is one of the oldest and most common methods of dimension reduction. It is a linear transformation that takes your data and projects it into a lower-dimensional space where each dimension explains the most-to-least variance. Since the projection is based on explaining the variation in data, it is particularly useful for looking at the global structure of your data. Also, because of its linear nature, it is more interpretable than other methods."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### t-distributed stochastic neighbour embedding (t-SNE)\n",
    "\n",
    "t-SNE is a neighbour graph method that has been very popular in the single-cell world. It takes your data and reduces it to two or three dimensions (depending on your selection), making it useful for visualizations. t-SNE focuses on local structure, meaning that having large distances between points in low dimensions is not necessarily meaningful."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Uniform manifold approximation and projection (UMAP)\n",
    "\n",
    "UMAP is a relatively new method, published in 2018, that has become very popular. Like t-SNE, it focuses on the local structure of data, and thus it returns results similar to t-SNE. However, it can reduce data to an arbitrary number of dimensions (instead of just 2 or 3), making it useful for general purpose dimension reduction other than visualization, and because of its design it preserves \"some aspects\"$^2$ of global structure. It also tends to be faster than t-SNE. Also like t-SNE, the focus is on preserving local structure, so global distances are not necessarily meaningful.\n",
    "\n",
    "$^2$ Note the weasel words here: UMAP tends to have fewer artificial clusters/tears than t-SNE, most of the time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Other methods\n",
    "\n",
    "Dimension reduction is an incredibly active field and there are constant updates to methods. There are numerous common methods that we will only be able to mention because of time constraints:\n",
    "* Canonical coordinate analysis (CCA) finds a shared correlation structure between two high dimensional data sets $X$ and $Y$. This can be useful for aligning multiple neuroimage or scRNA datasets.\n",
    "* Multidimensional scaling (MDS) visualizes levels of similarity between data\n",
    "* Diffusion maps can be used to interpret or track trajectories\n",
    "* Autoencoders are neural nets that try to reconstruct their original inputs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cautionary notes\n",
    "\n",
    "You should be careful with interpretting dimension reduction results. There are many factors to consider, including how your input data will shape your outputs, the methods you used, and the natural propensity of humans to see patterns where none actually exist. Visualizations should prompt downstream analysis or hypothesis generation rather than being a conclusion in themselves. Sometimes clusters and patterns will reflect technical artefacts such as batch effects or measurement bias. Outliers can also influence results. Methods like PCA are often used as pre-processing steps, and choosing how many features to include in a model is often guided by rules-of-thumb and heuristics. There is lots of literature to deal with these problems (e.g. Stuart et al, 2019 for batch effects), but they are beyond the scope of this workshop."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# References\n",
    "\n",
    "* Becht, Etienne, et al. \"Dimensionality reduction for visualizing single-cell data using UMAP.\" Nature biotechnology 37.1 (2019): 38.\n",
    "* Diaz-Papkovich, Alex, Luke Anderson-Trocmé, and Simon Gravel. \"UMAP reveals cryptic population structure and phenotype heterogeneity in large genomic cohorts.\" PLoS genetics 15.11 (2019).\n",
    "* Dorrity, Michael W., et al. \"Dimensionality reduction by UMAP to visualize physical and genetic interactions.\" Nature communications 11.1 (2020): 1-6.\n",
    "* Holmes, Susan, and Wolfgang Huber. Modern statistics for modern biology. Cambridge University Press, 2018.\n",
    "* Satija, Rahul, et al. \"Spatial reconstruction of single-cell gene expression data.\" Nature biotechnology 33.5 (2015): 495-502.\n",
    "* Stuart, Tim, et al. \"Comprehensive integration of single-cell data.\" Cell 177.7 (2019): 1888-1902."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Resources\n",
    "\n",
    "These are some online resources on dimension reduction in general I have found useful:\n",
    "\n",
    "* [A comparison of dimension reduction approaches for visualization](https://gesis.mybinder.org/binder/v2/gh/KrishnaswamyLab/visualization_selection/701455539bec9ad05c2a045adb5c476839b1f595)\n",
    "* [The beginner's guide to dimension reduction](https://idyll.pub/post/dimensionality-reduction-293e465c2a3443e8941b016d/)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}