08.4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "view-in-github"
   },
   "source": [
    "<a href=\"https://colab.research.google.com/github/udlbook/udlbook/blob/main/Notebooks/Chap08/8_4_High_Dimensional_Spaces.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "EjLK-kA1KnYX"
   },
   "source": [
    "# **Notebook 8.4: High-dimensional spaces**\n",
    "\n",
    "This notebook investigates the strange properties of high-dimensional spaces as discussed in the notes at the end of chapter 8.\n",
    "\n",
    "Work through the cells below, running each cell in turn. In various places you will see the words \"TO DO\". Follow the instructions at these places and make predictions about what is going to happen or write code to complete the functions.\n",
    "\n",
    "Contact me at udlbookmail@gmail.com if you find any mistakes or have any suggestions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "id": "4ESMmnkYEVAb"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import scipy.special as sci"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "MonbPEitLNgN"
   },
   "source": [
    "# How close are points in high dimensions?\n",
    "\n",
    "In this part of the notebook, we investigate how close random points are in 2D, 100D, and 1000D.   In each case, we generate 1000 points and calculate the Euclidean distance between each pair.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "id": "vZSHVmcWEk14"
   },
   "outputs": [],
   "source": [
    "# Fix the random seed so we all have the same random numbers\n",
    "np.random.seed(0)\n",
    "n_data = 1000\n",
    "# Create 1000 data examples (columns) each with 2 dimensions (rows)\n",
    "n_dim = 2\n",
    "x_2D = np.random.normal(size=(n_dim,n_data))\n",
    "# Create 1000 data examples (columns) each with 100 dimensions (rows)\n",
    "n_dim = 100\n",
    "x_100D = np.random.normal(size=(n_dim,n_data))\n",
    "# Create 1000 data examples (columns) each with 1000 dimensions (rows)\n",
    "n_dim = 1000\n",
    "x_1000D = np.random.normal(size=(n_dim,n_data))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "id": "PhVmnUs8ErD9"
   },
   "outputs": [],
   "source": [
    "from scipy.spatial.distance import pdist\n",
    "\n",
    "def distance_ratio(x):\n",
    "  # TODO -- replace the two lines below to calculate the largest and smallest Euclidean distance between\n",
    "  # the data points in the columns of x.  DO NOT include the distance between the data point\n",
    "  # and itself (which is obviously zero)\n",
    "  dists = pdist(x.T)\n",
    "  smallest_dist = np.min(dists[dists != 0])\n",
    "  largest_dist = np.max(dists)\n",
    "\n",
    "  # Calculate the ratio and return\n",
    "  dist_ratio = largest_dist / smallest_dist\n",
    "  return dist_ratio"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "id": "0NdPxfn5GQuJ"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ratio of largest to smallest distance 2D: 2840.258\n",
      "Ratio of largest to smallest distance 100D: 2.038\n",
      "Ratio of largest to smallest distance 1000D: 1.221\n"
     ]
    }
   ],
   "source": [
    "print('Ratio of largest to smallest distance 2D: %3.3f'%(distance_ratio(x_2D)))\n",
    "print('Ratio of largest to smallest distance 100D: %3.3f'%(distance_ratio(x_100D)))\n",
    "print('Ratio of largest to smallest distance 1000D: %3.3f'%(distance_ratio(x_1000D)))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "uT68c0k8uBxs"
   },
   "source": [
    "If you did this right, you will see that the distance between the nearest and farthest two points in high dimensions is almost the same.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "b2FYKV1SL4Z7"
   },
   "source": [
    "# Volume of a hypersphere\n",
    "\n",
    "In the second part of this notebook we calculate the volume of a hypersphere of radius 0.5 (i.e., of diameter 1) as a function of the radius.  Note that you you can check your answer by doing the calculation for 2D using the standard formula for the area of a circle and making sure it matches."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "id": "CZoNhD8XJaHR"
   },
   "outputs": [],
   "source": [
    "def volume_of_hypersphere(diameter, dimensions):\n",
    "  # Formula given in Problem 8.7 of the book\n",
    "  # You will need sci.gamma()\n",
    "  # Check out:    https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.gamma.html\n",
    "  # Also use this value for pi\n",
    "  pi = np.pi\n",
    "  # TODO replace this code with formula for the volume of a hypersphere\n",
    "  radius = diameter / 2  \n",
    "  # Calculate the volume using the formula for the volume of a hypersphere\n",
    "  volume = (pi ** (dimensions / 2) * (radius ** dimensions)) / sci.gamma(dimensions / 2 + 1)  \n",
    "  \n",
    "  return volume\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "id": "fNTBlg_GPEUh"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Volume of unit diameter hypersphere in 1 dimensions is 1.000\n",
      "Volume of unit diameter hypersphere in 2 dimensions is 0.785\n",
      "Volume of unit diameter hypersphere in 3 dimensions is 0.524\n",
      "Volume of unit diameter hypersphere in 4 dimensions is 0.308\n",
      "Volume of unit diameter hypersphere in 5 dimensions is 0.164\n",
      "Volume of unit diameter hypersphere in 6 dimensions is 0.081\n",
      "Volume of unit diameter hypersphere in 7 dimensions is 0.037\n",
      "Volume of unit diameter hypersphere in 8 dimensions is 0.016\n",
      "Volume of unit diameter hypersphere in 9 dimensions is 0.006\n",
      "Volume of unit diameter hypersphere in 10 dimensions is 0.002\n"
     ]
    }
   ],
   "source": [
    "diameter = 1.0\n",
    "for c_dim in range(1,11):\n",
    "  print(\"Volume of unit diameter hypersphere in %d dimensions is %3.3f\"%(c_dim, volume_of_hypersphere(diameter, c_dim)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "PtaeGSNBunJl"
   },
   "source": [
    "You should see that the volume decreases to almost nothing in high dimensions.  All of the volume is in the corners of the unit hypercube (which always has volume 1)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "GdyMeOBmoXyF"
   },
   "source": [
    "# Proportion of hypersphere in outer shell\n",
    "\n",
    "In the third part of the notebook you will calculate what proportion of the volume of a hypersphere is in the outer 1% of the radius/diameter.  Calculate the volume of a hypersphere and then the volume of a hypersphere with 0.99 of the radius and then figure out the ratio.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "id": "8_CxZ2AIpQ8w"
   },
   "outputs": [],
   "source": [
    "def get_prop_of_volume_in_outer_1_percent(dimension):\n",
    "  diameter = 1\n",
    "  volume_full = volume_of_hypersphere(diameter, dimension)  \n",
    "    \n",
    "  diameter_inner = 0.99\n",
    "  volume_inner = volume_of_hypersphere(diameter_inner, dimension)  \n",
    "\n",
    "  volume_outer = volume_full - volume_inner  \n",
    "  proportion = volume_outer / volume_full\n",
    "\n",
    "  return proportion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "id": "LtMDIn2qPVfJ"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Proportion of volume in outer 1 percent of radius in 1 dimensions =0.010\n",
      "Proportion of volume in outer 1 percent of radius in 2 dimensions =0.020\n",
      "Proportion of volume in outer 1 percent of radius in 10 dimensions =0.096\n",
      "Proportion of volume in outer 1 percent of radius in 20 dimensions =0.182\n",
      "Proportion of volume in outer 1 percent of radius in 50 dimensions =0.395\n",
      "Proportion of volume in outer 1 percent of radius in 100 dimensions =0.634\n",
      "Proportion of volume in outer 1 percent of radius in 150 dimensions =0.779\n",
      "Proportion of volume in outer 1 percent of radius in 200 dimensions =0.866\n",
      "Proportion of volume in outer 1 percent of radius in 250 dimensions =0.919\n",
      "Proportion of volume in outer 1 percent of radius in 300 dimensions =0.951\n"
     ]
    }
   ],
   "source": [
    "# While we're here, let's look at how much of the volume is in the outer 1% of the radius\n",
    "for c_dim in [1,2,10,20,50,100,150,200,250,300]:\n",
    "  print('Proportion of volume in outer 1 percent of radius in %d dimensions =%3.3f'%(c_dim, get_prop_of_volume_in_outer_1_percent(c_dim)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "n_FVeb-ZwzxD"
   },
   "source": [
    "You should see that by the time we get to 300 dimensions most of the volume is in the outer 1 percent. <br><br>\n",
    "\n",
    "The conclusion of all of this is that in high dimensions you should be sceptical of your intuitions about how things work.  I have tried to visualize many things in one or two dimensions in the book, but you should also be sceptical about these visualizations!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyPAKqlf9VxztHXKylyJwqe8",
   "include_colab_link": true,
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}