src/04_Dimensionality_Reduction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dimensionality Reduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Main Approaches for Dimensionality Reduction\n",
    "\n",
    "- ___Projection___\n",
    "- ___Manifold___"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Projection\n",
    "\n",
    "In most real-world problems, training instances are not spread out uniformly across\n",
    "all dimensions. Many features are almost constant, while others are highly correlated. As a result, all training instances actually lie within\n",
    "(or close to) a much lower-dimensional subspace of the high-dimensional space.\n",
    "\n",
    "__Explaining beyond this more clearly requires more reading of this topic.__\n",
    "\n",
    "__i hope the images help a bit.__\n",
    "\n",
    "we took a dataset and found that this can be squashed into a hyperplane with no change in interpretation of data.\n",
    "\n",
    "![Projection1](img/projection1.PNG)\n",
    "\n",
    "Projected Dataset Plot\n",
    "\n",
    "![Projection2](img/projection2.PNG)\n",
    "\n",
    "However this doesnt always work as we see in this following example\n",
    "\n",
    "![Projection3](img/projection3.PNG)\n",
    "\n",
    "![Projection4](img/projection4.PNG)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Manifold Learning\n",
    "\n",
    "The Swiss roll is an example of a 2D manifold. Put simply, a 2D manifold is a 2D\n",
    "shape that can be bent and twisted in a higher-dimensional space. More generally, a\n",
    "d-dimensional manifold is a part of an n-dimensional space (where d < n) that locally\n",
    "resembles a d-dimensional hyperplane. In the case of the Swiss roll, d = 2 and n = 3: it\n",
    "locally resembles a 2D plane, but it is rolled in the third dimension.\n",
    "Many dimensionality reduction algorithms work by modeling the manifold on which\n",
    "the training instances lie; this is called Manifold Learning. It relies on the manifold\n",
    "assumption, also called the manifold hypothesis, which holds that most real-world\n",
    "high-dimensional datasets lie close to a much lower-dimensional manifold. This\n",
    "assumption is very often empirically observed.\n",
    "\n",
    "__\"The manifold assumption is often accompanied by another implicit assumption: that\n",
    "the task at hand (e.g., classification or regression) will be simpler if expressed in the\n",
    "lower-dimensional space of the manifold. For example, in the top row of Figure 8-6\n",
    "the Swiss roll is split into two classes: in the 3D space (on the left), the decision\n",
    "boundary would be fairly complex, but in the 2D unrolled manifold space (on the\n",
    "right), the decision boundary is a simple straight line.\n",
    "However, this assumption does not always hold. For example, in the bottom row of\n",
    "Figure 8-6, the decision boundary is located at x1\n",
    " = 5. This decision boundary looks\n",
    "very simple in the original 3D space (a vertical plane), but it looks more complex in\n",
    "the unrolled manifold (a collection of four independent line segments).\n",
    "In short, if you reduce the dimensionality of your training set before training a\n",
    "model, it will definitely speed up training, but it may not always lead to a better or\n",
    "simpler solution; it all depends on the dataset.\n",
    "Hopefully you now have a good sense of what the curse of dimensionality is and how\n",
    "dimensionality reduction algorithms can fight it, especially when the manifold\n",
    "assumption holds. The rest of this chapter will go through some of the most popular\n",
    "algorithms.\"__\n",
    "\n",
    "___See Figure for a better idea___\n",
    "\n",
    "![manifold](img/mani1.PNG)\n",
    "\n",
    "___As of now even I have hard time understanding this and further reading on this will help in getting a more clearer ides___\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## PCA - Principal Component Analysis\n",
    "\n",
    "First it identifies the hyperplane that lies closest to the data, and then\n",
    "it projects the data onto it.\n",
    "\n",
    "### Preserving Variance\n",
    "Before you can project the training set onto a lower-dimensional hyperplane, you\n",
    "first need to choose the right hyperplane. For example, a simple 2D dataset is repre‐\n",
    "sented on the left of Figure 8-7, along with three different axes (i.e., one-dimensional\n",
    "hyperplanes). On the right is the result of the projection of the dataset onto each of\n",
    "these axes. As you can see, the projection onto the solid line preserves the maximum\n",
    "variance, while the projection onto the dotted line preserves very little variance, and\n",
    "the projection onto the dashed line preserves an intermediate amount of variance.\n",
    "\n",
    "It seems reasonable to select the axis that preserves the maximum amount of var‐\n",
    "iance, as it will most likely lose less information than the other projections. Another\n",
    "way to justify this choice is that it is the axis that minimizes the mean squared dis‐\n",
    "tance between the original dataset and its projection onto that axis. This is the rather\n",
    "simple idea behind PCA.\n",
    "\n",
    "![](img/pca1.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Principal Components\n",
    "\n",
    "PCA identifies the axis that accounts for the largest amount of variance in the train‐\n",
    "ing set. In Figure 8-7, it is the solid line. It also finds a second axis, orthogonal to the\n",
    "first one, that accounts for the largest amount of remaining variance. In this 2D\n",
    "example there is no choice: it is the dotted line. If it were a higher-dimensional data‐\n",
    "set, PCA would also find a third axis, orthogonal to both previous axes, and a fourth,\n",
    "a fifth, and so on—as many axes as the number of dimensions in the dataset.\n",
    "\n",
    "> The direction of the principal components is not stable: if you per‐\n",
    "turb the training set slightly and run PCA again, some of the new\n",
    "PCs may point in the opposite direction of the original PCs. How‐\n",
    "ever, they will generally still lie on the same axes. In some cases, a\n",
    "pair of PCs may even rotate or swap, but the plane they define will\n",
    "generally remain the same.\n",
    "\n",
    "So how can you find the principal components of a training set? Luckily, there is a\n",
    "standard matrix factorization technique called Singular Value Decomposition (SVD)\n",
    "that can decompose the training set matrix X into the matrix multiplication of three\n",
    "matrices\n",
    "\n",
    "$U.Σ.V^T$\n",
    "\n",
    "```python\n",
    "\n",
    "X_centered = X - X.mean(axis=0)\n",
    "U, s, Vt = np.linalg.svd(X_centered)\n",
    "c1 = Vt.T[:, 0]\n",
    "c2 = Vt.T[:, 1]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Projecting Down to d Dimensions\n",
    "\n",
    "Once you have identified all the principal components, you can reduce the dimen‐\n",
    "sionality of the dataset down to d dimensions by projecting it onto the hyperplane\n",
    "defined by the first d principal components. Selecting this hyperplane ensures that the\n",
    "projection will preserve as much variance as possible.\n",
    "\n",
    "To project the training set onto the hyperplane, you can simply compute the matrix\n",
    "multiplication of the training set matrix X by the matrix Wd\n",
    ", defined as the matrix\n",
    "containing the first d principal components (i.e., the matrix composed of the first d\n",
    "columns of V)\n",
    "\n",
    "$X_{d‐proj} = X.W_d$\n",
    "> PCA assumes that the dataset is centered around the origin. As we\n",
    "will see, Scikit-Learn’s PCA classes take care of centering the data\n",
    "for you. However, if you implement PCA yourself (as in the pre‐\n",
    "ceding example), or if you use other libraries, don’t forget to center\n",
    "the data first."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Scikit-Learn\n",
    "\n",
    "```python\n",
    "\n",
    "from sklearn.decomposition import PCA\n",
    "pca = PCA(n_components = 2)\n",
    "X2D = pca.fit_transform(X)\n",
    "\n",
    "```\n",
    "\n",
    "## Exaplained Variance Ratio\n",
    "\n",
    "Exaplained Variance Ratio indicates\n",
    "the proportion of the dataset’s variance that lies along the axis of each principal component. \n",
    "\n",
    "```python\n",
    ">>> pca.explained_variance_ratio_\n",
    "array([0.84248607, 0.14631839])\n",
    "```\n",
    "\n",
    "This tells you that 84.2% of the dataset’s variance lies along the first axis, and 14.6%\n",
    "lies along the second axis. This leaves less than 1.2% for the third axis, so it is reason‐\n",
    "able to assume that it probably carries little information.\n",
    "\n",
    "## Choosing the Right Number of Dimensions\n",
    "\n",
    "Instead of arbitrarily choosing the number of dimensions to reduce down to, it is\n",
    "generally preferable to choose the number of dimensions that add up to a sufficiently\n",
    "large portion of the variance (e.g., 95%). Unless, of course, you are reducing dimen‐\n",
    "sionality for data visualization—in that case you will generally want to reduce the\n",
    "dimensionality down to 2 or 3.\n",
    "\n",
    "\n",
    "```python\n",
    "pca = PCA(n_components=0.95)\n",
    "X_reduced = pca.fit_transform(X_train)\n",
    "```\n",
    "\n",
    "\n",
    "how to find number of dimensions\n",
    "```python\n",
    "pca = PCA()\n",
    "pca.fit(X_train)\n",
    "cumsum = np.cumsum(pca.explained_variance_ratio_)\n",
    "d = np.argmax(cumsum >= 0.95) + 1\n",
    "```\n",
    "\n",
    "![](img/seldim.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## PCA for Compression\n",
    "Try applying PCA to the MNIST dataset while preserving 95% of its var‐\n",
    "iance. You should find that each instance will have just over 150 features, instead of\n",
    "the original 784 features. So while most of the variance is preserved, the dataset is\n",
    "now less than 20% of its original size! This is a reasonable compression ratio, and you\n",
    "can see how this can speed up a classification algorithm (such as an SVM classifier)\n",
    "tremendously.\n",
    "It is also possible to decompress the reduced dataset back to 784 dimensions by\n",
    "applying the inverse transformation of the PCA projection. Of course this won’t give\n",
    "you back the original data, since the projection lost a bit of information (within the\n",
    "5% variance that was dropped), but it will likely be quite close to the original data.\n",
    "The mean squared distance between the original data and the reconstructed data\n",
    "(compressed and then decompressed) is called the reconstruction error. \n",
    "\n",
    "```python\n",
    "\n",
    "pca = PCA(n_components = 154)\n",
    "X_reduced = pca.fit_transform(X_train)\n",
    "X_recovered = pca.inverse_transform(X_reduced)\n",
    "```\n",
    "\n",
    "$X_{recovered} = X_{d‐proj}.W_d\n",
    "^T$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Randomized PCA \n",
    "\n",
    "If you set the svd_solver hyperparameter to \"randomized\", Scikit-Learn uses a sto‐\n",
    "chastic algorithm called Randomized PCA that quickly finds an approximation of the\n",
    "first d principal components. Its computational complexity is \n",
    "$O(m × d^2) + O(d^3)$,\n",
    "instead of \n",
    "$O(m × n^2) + O(n^3)$ for the full SVD approach, so it is dramatically faster\n",
    "than full SVD when d is much smaller than n:\n",
    "```python\n",
    "rnd_pca = PCA(n_components=154, svd_solver=\"randomized\")\n",
    "X_reduced = rnd_pca.fit_transform(X_train)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Incremental PCA\n",
    "\n",
    "One problem with the preceding implementations of PCA is that they require the\n",
    "whole training set to fit in memory in order for the algorithm to run. Fortunately,\n",
    "Incremental PCA (IPCA) algorithms have been developed: you can split the training\n",
    "set into mini-batches and feed an IPCA algorithm one mini-batch at a time. \n",
    "\n",
    "The following code splits the MNIST dataset into 100 mini-batches (using NumPy’s\n",
    "array_split() function) and feeds them to Scikit-Learn’s IncrementalPCA class5\n",
    " to\n",
    "reduce the dimensionality of the MNIST dataset down to 154 dimensions (just like\n",
    "before). \n",
    "\n",
    "```python\n",
    "\n",
    "from sklearn.decomposition import IncrementalPCA\n",
    "n_batches = 100\n",
    "inc_pca = IncrementalPCA(n_components=154)\n",
    "for X_batch in np.array_split(X_train, n_batches):\n",
    " inc_pca.partial_fit(X_batch)\n",
    "X_reduced = inc_pca.transform(X_train)\n",
    "```\n",
    "\n",
    "\n",
    "Alternatively, you can use NumPy’s memmap class, which allows you to manipulate a\n",
    "large array stored in a binary file on disk as if it were entirely in memory; the class\n",
    "loads only the data it needs in memory, when it needs it. Since the IncrementalPCA\n",
    "class uses only a small part of the array at any given time, the memory usage remains\n",
    "under control. This makes it possible to call the usual fit() method, as you can see\n",
    "in the following code:\n",
    "```python\n",
    "X_mm = np.memmap(filename, dtype=\"float32\", mode=\"readonly\", shape=(m, n))\n",
    "batch_size = m // n_batches\n",
    "inc_pca = IncrementalPCA(n_components=154, batch_size=batch_size)\n",
    "inc_pca.fit(X_mm)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Kernal PCA\n",
    "\n",
    "Kernel Trick can be applied to PCA making it possible to perform complex nonlinear projections for dimensionality redution. This is called KernelPCA or KPCA.\n",
    "\n",
    "It is often good at preserving clusters of instances after projection, or\n",
    "sometimes even unrolling datasets that lie close to a twisted manifold.\n",
    "```python\n",
    "from sklearn.decomposition import KernelPCA\n",
    "rbf_pca = KernelPCA(n_components = 2, kernel=\"rbf\", gamma=0.04)\n",
    "X_reduced = rbf_pca.fit_transform(X)\n",
    "\n",
    "```\n",
    "\n",
    "![](img/kpca.PNG)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Selecting a Kernel and Tuning Hyperparameters\n",
    "\n",
    "As kPCA is an unsupervised learning algorithm, there is no obvious performance\n",
    "measure to help you select the best kernel and hyperparameter values. However,\n",
    "dimensionality reduction is often a preparation step for a supervised learning task\n",
    "(e.g., classification), so you can simply use grid search to select the kernel and hyper‐\n",
    "parameters that lead to the best performance on that task.\n",
    "\n",
    "For example, the following\n",
    "code creates a two-step pipeline, first reducing dimensionality to two dimensions\n",
    "using kPCA, then applying Logistic Regression for classification. Then it uses Grid\n",
    "SearchCV to find the best kernel and gamma value for kPCA in order to get the best\n",
    "classification accuracy at the end of the pipeline:\n",
    "\n",
    "```python\n",
    "\n",
    "from sklearn.model_selection import GridSearchCV\n",
    "from sklearn.linear_model import LogisticRegression\n",
    "from sklearn.pipeline import Pipeline\n",
    "\n",
    "clf = Pipeline([\n",
    " (\"kpca\", KernelPCA(n_components=2)),\n",
    " (\"log_reg\", LogisticRegression())\n",
    " ])\n",
    "param_grid = [{\n",
    " \"kpca__gamma\": np.linspace(0.03, 0.05, 10),\n",
    " \"kpca__kernel\": [\"rbf\", \"sigmoid\"]\n",
    " }]\n",
    "grid_search = GridSearchCV(clf, param_grid, cv=3)\n",
    "grid_search.fit(X, y)\n",
    "```\n",
    "```python\n",
    ">>> print(grid_search.best_params_)\n",
    "{'kpca__gamma': 0.043333333333333335, 'kpca__kernel': 'rbf'}\n",
    "```\n",
    "\n",
    "Another approach, this time entirely unsupervised, is to select the kernel and hyperparameters that yield the lowest reconstruction error. \n",
    "\n",
    "You may be wondering how to perform this reconstruction. One solution is to train a\n",
    "supervised regression model, with the projected instances as the training set and the\n",
    "original instances as the targets. Scikit-Learn will do this automatically if you set\n",
    "fit_inverse_transform=True, as shown in the following code:\n",
    "```python\n",
    "rbf_pca = KernelPCA(n_components = 2, kernel=\"rbf\", gamma=0.0433,\n",
    " fit_inverse_transform=True)\n",
    "X_reduced = rbf_pca.fit_transform(X)\n",
    "X_preimage = rbf_pca.inverse_transform(X_reduced)\n",
    "```\n",
    "> By default, fit_inverse_transform=False and KernelPCA has no\n",
    "inverse_transform() method. This method only gets created\n",
    "when you set fit_inverse_transform=True\n",
    "\n",
    "You can then compute the reconstruction pre-image error:\n",
    "```python\n",
    ">>> from sklearn.metrics import mean_squared_error\n",
    ">>> mean_squared_error(X, X_preimage)\n",
    "32.786308795766132\n",
    "```\n",
    "Now you can use grid search with cross-validation to find the kernel and hyperpara‐\n",
    "meters that minimize this pre-image reconstruction error."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LLE - Locally Linear Embedding\n",
    "\n",
    " It is a Manifold Learning technique that does not rely\n",
    "on projections like the previous algorithms. In a nutshell, LLE works by first measuring how each training instance linearly relates to its closest neighbors (c.n.), and then\n",
    "looking for a low-dimensional representation of the training set where these local\n",
    "relationships are best preserved (more details shortly). This makes it particularly\n",
    "good at unrolling twisted manifolds, especially when there is not too much noise.\n",
    "\n",
    "```python\n",
    "from sklearn.manifold import LocallyLinearEmbedding\n",
    "lle = LocallyLinearEmbedding(n_components=2, n_neighbors=10)\n",
    "X_reduced = lle.fit_transform(X)\n",
    "```\n",
    "\n",
    "![](img/lle1.PNG)\n",
    "\n",
    "Equation 8-4. LLE step 1: linearly modeling local relationships\n",
    "\n",
    "$\\hat{W} = argmin_W \\sum_{i=1}^{m} (x^{(i)}-\\sum_{j=1}^{m} w_{i,j}x^{(j)})^2$\n",
    "\n",
    "\n",
    "subject to $w_i, j = 0 $ if  \n",
    " $x^j$ \n",
    " is not one of the k c.n. of \n",
    " $x^i$\n",
    "\n",
    "and\n",
    "\n",
    "\n",
    "$\\sum_(j = 1)^m w_{i, j} = 1 for i = 1, 2, ⋯, m$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Equation 8-5. LLE step 2: reducing dimensionality while preserving relationships\n",
    "\n",
    "$\\hat{Z} = argmin_Z \\sum_{i=1}^m ( z^{(i)} - \\sum_{j=1}^m \\hat{w}_{i,j} z^{(j)} )^2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Other Dimensionality Reduction Techniques \n",
    "\n",
    "- Multidimensional Scaling (MDS) reduces dimensionality while trying to preserve the distances between the instances\n",
    "- Isomap creates a graph by connecting each instance to its nearest neighbors, then reduces dimensionality while trying to preserve the geodesic distances9 between the instances\n",
    "- t-Distributed Stochastic Neighbor Embedding (t-SNE) reduces dimensionality while trying to keep similar instances close and dissimilar instances apart. It is mostly used for visualization, in particular to visualize clusters of instances in high-dimensional space (e.g., to visualize the MNIST images in 2D).\n",
    "- Linear Discriminant Analysis (LDA) is actually a classification algorithm, but during training it learns the most discriminative axes between the classes, and these axes can then be used to define a hyperplane onto which to project the data. The benefit is that the projection will keep classes as far apart as possible, so LDA is a good technique to reduce dimensionality before running another classification algorithm such as an SVM classifier\n",
    "\n",
    "![](img/dimred.PNG)"
   ]
  }
 ],
 "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}