{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "#
cs231n. [A1, part 1](http://cs231n.github.io/assignments2018/assignment1/). k-Nearest Neighbor (kNN) exercise\n", "\n", " \n", "####
**Comments on `compute_distances_no_loops`** by @yorko" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- $num\\_test$, $num\\_train$ – are the numbers of test and train images correspondingly\n", "- $d$ – is the number of features\n", "- $X$ – is a test set feature matrix. Dimensions: $num\\_test \\times d$\n", "- $X^{(tr)}$ – is a training set feature matrix. Dimensions: $num\\_train \\times d$\n", "\n", "We need to compute matrix $D$ which stores all pairwise distances between test and training samples. \n", "\n", "$$\\Large D_{ij} = {\\lVert X_{i,:} - X^{(tr)}_{j,:}\\rVert }_2$$\n", "\n", "where $X_{i,:}$ designates the $i$-th row of matrix $X$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Further, $$\\Large D^2_{ij} = \\sum_{k=1}^d {(X_{ik} - X^{(tr)}_{jk})} ^ 2$$\n", "\n", "where $D^2_{ij}$ is a square of an element of $D$ at row $i$ and column $j$. $k$ iterates over $d$ features of the $i$-th test sample and $j$-th training sample. \n", "\n", "$$\\large D^2_{ij} = \\sum_{k=1}^d (X^2_{ik} - 2 X_{ik} X^{(tr)}_{jk} + {X^{(tr)}_{jk}}^2) = \\sum_{k=1}^d X^2_{ik} - 2\\sum_{k=1}^d X_{ik} X^{(tr)}_{jk} + \\sum_{k=1}^d {X^{(tr)}_{jk}}^2$$\n", "\n", "From here, we get a closed-form vectorized expression for $D * D$:\n", "\n", "$$\\Large D * D = {(X * X)}_{:,\\Sigma} - 2X{X^{(tr)}}^{\\text{T}} + {(X^{(tr)} * X^{(tr)})}_{:,\\Sigma}^{\\text{T}}$$\n", "\n", "where $*$ designates element-wise multiplication and $A_{:,\\Sigma}$ stands for a vector derived from matrix $A$ by summing all values in each row. \n", "\n", "Lastly, for all dimensions to match, we assume [broadcasting](https://docs.scipy.org/doc/numpy-1.13.0/user/basics.broadcasting.html) here, that is, ${(X * X)}_{:,\\Sigma}$ is comprised of $num\\_train$ identical column vectors, stacked horizontally, and ${(X^{(tr)} * X^{(tr)})}_{:,\\Sigma}^{\\text{T}}$ is made of $num\\_test$ identical row vectors, stacked vertically. Thus, each term in the above formula has shape $num\\_test \\times num\\_train$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Simple broadcasting example**\n", "\n", "$a$ is a column-vector of length 3, $b$ is a row-vector of length 4. $a - b$ is a matrix of shape $3 \\times 4$. " ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import numpy as np" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "a, b = 3 * np.ones((3, 1)), 4 * np.ones((1, 4))" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[ 3.],\n", " [ 3.],\n", " [ 3.]])" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[ 4., 4., 4., 4.]])" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[-1., -1., -1., -1.],\n", " [-1., -1., -1., -1.],\n", " [-1., -1., -1., -1.]])" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a - b" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Testing the derived formula**" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "X = np.array([[4, 3, 2, 1],\n", " [1, 1, 1, 1]])\n", "\n", "X_tr = np.array([[1, 2, 3, 4],\n", " [0, 1, 2, 3],\n", " [1, 1, 1, 1]])" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[ 4.47213595, 4.89897949, 3.74165739],\n", " [ 3.74165739, 2.44948974, 0. ]])" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "np.sqrt((X * X).sum(axis=1, keepdims=True) - 2 * X.dot(X_tr.T) + \\\n", " (X_tr * X_tr).sum(axis=1, keepdims=True).T)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Double-check by calculating the same distances with two loops." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Distance between 1 test sample and 1 train sample: 4.47213595499958\n", "Distance between 1 test sample and 2 train sample: 4.898979485566356\n", "Distance between 1 test sample and 3 train sample: 3.7416573867739413\n", "Distance between 2 test sample and 1 train sample: 3.7416573867739413\n", "Distance between 2 test sample and 2 train sample: 2.449489742783178\n", "Distance between 2 test sample and 3 train sample: 0.0\n" ] } ], "source": [ "for test_id in range(X.shape[0]):\n", " for train_id in range(X_tr.shape[0]):\n", " print(\"Distance between {} test sample and {} train sample: {}\".format(\n", " test_id + 1, train_id + 1,\n", " np.linalg.norm(X[test_id, :] - X_tr[train_id, :])))" ] } ], "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.1" } }, "nbformat": 4, "nbformat_minor": 2 }