{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# The oddities of distances in high dimensions\n",
"\n",
"In this notebook, you will explore how distances between data points behave in high-dimensional metric spaces. To this end, you will experiment both with artifical data as well as real image data.\n",
"\n",
"You find supplementary material for this notebook in the file notebook10.zip on the lecture's homepage. This zip file consists of the file wissrech2.py (an update of the package, which you have already used before) and a folder images, which contains natural image scenes."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Task 1: Your work horse\n",
"\n",
"This notebook in fact requires very little programming. It is essentially one simple subroutine consisting of a few lines of code, which you will implement below. This subroutine does the following:\n",
"\n",
"1. It takes an array of datapoints and computes the pairwise distances. The type of distance can be specified via named parameters.\n",
"2. Next the subroutine computes a normalized histogram of the pairwise distances using 50 bins\n",
"3. Finally, the subroutine adds a plot of the computed normalized histogram to a given AxisObject. To help the user of the subroutine in identifying the added plot, the subroutine puts an annotation box to the mode of the plotted normalized histogram. \n",
"\n",
"A plot produces by your subroutine should in style look like the example below. Everything you need to compute pairwise distances you find within the package scipy. A subroutine to compute histograms you find within the package numpy. Finally, a look at this matplotlib demo\n",
"\n",
"http://matplotlib.org/examples/pylab_examples/annotation_demo2.html\n",
"\n",
"should be helpful for getting the annotations into you plot."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![A sample plot](sample-plot.png)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def add_pd_histogram_plot(ax, data, pd_func, label=''):\n",
" \"\"\"\n",
" Plots the normalized histogram of pairwise distances to the given AxisObject ax.\n",
" \n",
" Parameters:\n",
" ax - the AxisObject to which the plot is added\n",
" data - array-like with shape (N,d) where N is the number of data points and d the dimension\n",
" pd_func - function object such that pd_func(data) computes the pairwise distances\n",
" label - Text which is placed at the mode of histogram\n",
" \"\"\"\n",
" # your code goes here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Task 2: Numerical experiments for uniformly and normally distributed data\n",
"\n",
"Do the following numerical experiments:\n",
"\n",
"1. For several dimensions $d$ of your choice up to $d=100$, draw $n=1000$ data points both from a uniform distribution in the cube $[0,1]^d$ and a standard $d$-variate normal distribution.\n",
"2. Select some distance measures of your choice, but at least the Euclidean distance and the $L_\\infty$-distance (also called Chebychev-distance).\n",
"3. For each of distance measures, generate a diagram. The diagram contains a plot of the normalized histograms of the pairwise distances for all sets of data points which you have generated.\n",
"\n",
"You find routines for random number generation in the package numpy.random.\n",
"\n",
"Discuss the concentration behavior of the histograms for increasing dimension $d$. What does this imply for the meaningfulness of pairwise distances when $d$ becomes large?\n",
"\n",
"Your answer:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# your code goes here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Task 3: Numerical experiment for projected data\n",
"\n",
"Do a numerical experiment which is identical to that from Task 2 except for the data generation (Step 1.). Instead, generate the following data this time:\n",
"\n",
"1. For $d=100$, generate once $n=1000$ uniformly distributed data points and $n=1000$ standard normally distributed data points. Now, for the dimensions which you considered in Task 2, which we name by $p$ now, generate $(p \\times d)$ random matrices from a multivariate standard normal distribution. Use this matrices to transform (project) your $d$-dimensional data into $p$-dimensional data.\n",
"\n",
"If you compare the diagrams which you obtain this time with the diagrams from Task 2, what do you observe? Do you notice something special about the Euclidean distance?\n",
"\n",
"(To see effects more clearly, it might be helpful to generate further diagrams, where you combine some plots from Task 2 and some plots from this task)\n",
"\n",
"Your answer:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# your code goes here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Task 4: Numerical experiment with real data\n",
"\n",
"So far, you worked with completely artifical data, which originated from probability distribution. In this task, you will work with patches from natural image scenes given as gray-level images. The images are contained in the folder images. To generate the image patches, you can use the subroutine wissrech2.random_image_data ('random' here only means that the patches of given size are taken from a random position within the big image).\n",
"\n",
"Now do the same experiment as in Task 2 except that you use image patches as your data. Further, as dimensions you should take values whose square root is an integer (because random_image_data transforms patches of shape $\\lfloor \\sqrt{d} \\rfloor \\times \\lfloor \\sqrt{d} \\rfloor$ into flat $d$-dimensional vectors, if you ask for $d$-dimensional data).\n",
"\n",
"Describe what you observe? Do you have an explanation why it even seems to help to increase the size of the image patches although this increases the formal dimension of your data?\n",
"\n",
"Your answer:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# your code goes here"
]
}
],
"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.5.1"
}
},
"nbformat": 4,
"nbformat_minor": 0
}