demo.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<br>\n",
    "\n",
    "---\n",
    "\n",
    "<div align=\"center\"> \n",
    "  <font size=\"3\"><b>Machine Learning</b> </font>\n",
    "</div>\n",
    "<br>\n",
    "<div align=\"center\"> \n",
    "  <font size=\"6\">\n",
    "      <b>Winner Take All Hash<br></b>\n",
    "    </font>\n",
    "    <br>\n",
    "    <font size=\"4\">\n",
    "        A brief study on Winner Take All Hash algorithm, inspired by Jay Yagnik. \n",
    "    </font>\n",
    "    <br>\n",
    "    <br>\n",
    "    <font size=\"3\">\n",
    "        Original paper: \n",
    "        <a href=\"http://www.cs.toronto.edu/~dross/YagnikStrelowRossLin_ICCV2011.pdf\">\n",
    "            The Power of Comparative Reasoning <br>Jay Yagnik, Dennis Strelow, David A. Ross, Ruei-sung Lin - 2011\n",
    "        </a>\n",
    "    </font>\n",
    "</div>\n",
    "\n",
    "---\n",
    "\n",
    "<div align=\"center\"> \n",
    "    <font size=\"4\">\n",
    "         <b>Konstantinos Nikoletos, ML Research</b>\n",
    "     </font>\n",
    "</div>\n",
    "\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# WTA: Basic idea"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rank Correlation Spaces\n",
    "\n",
    "This algorithm benefits the nature of the given embeddings. Embeddings must be rank ordered (partialy or fully). What do we mean when say rank ordered embedding or vector. Lets take an example. Assume $Y$ is our initial vector.\n",
    "$$\n",
    "Y = [4, -1.5, 2.1, 5.5, 0]\n",
    "$$\n",
    "Then the ranked ordered vector of $Y$ will be:\n",
    "$$\n",
    "Y_{rankedOrdered} = [3, 0, 2, 4, 1]\n",
    "$$\n",
    "\n",
    "And what's a __rank correlation__?\n",
    "\n",
    "Rank correlation is any of several statistics that measure an ordinal association — the relationship between rankings of different ordinal variables or different rankings of the same variable, where a \"ranking\" is the assignment of the ordering labels 1st, 2nd, 3rd, etc. to different observations of a particular variable. __Rank correlation coefficient__ measures the degree of similarity between two rankings, and can be used to assess the significance of the relation between them. Rank correlation measures are known for their stability to perturbations in\n",
    "numeric values while giving a good indication of inherent similarity / agreement between items / vectors being considered.\n",
    "\n",
    "\n",
    "__Partial order rankings__\n",
    "\n",
    "There's no need to have embeddings or vectors of full rankings. For example $Y$ is a full ranking as it has all indexes from 0 to 4. Partial rankings miss a number of that indexes. \n",
    "\n",
    "## Goal\n",
    "\n",
    "WTA algorithms goal is a feature space transformation that results in a space that is not sensitive to the absolute values of the feature dimensions but rather on the implicit ordering defined by those values. In effect the similarity between two points is defined by the degree to which their feature dimension rankings agree.\n",
    "\n",
    "## Algorithms main functionality\n",
    "\n",
    "Takes as input a set of vectors (embeddings), and for each vector:\n",
    "- Permutes with a random pemutation\n",
    "- Takes the first K components from the permuted vector\n",
    "- Finds and outputs the index of the maximum value of that components\n",
    "- Repeats for every vector in the set\n",
    "\n",
    "The maximum index is the hash code. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A simple pairwise-order measure\n",
    "\n",
    "The algorithms main point is to make a feature space transformation that benefits the most from the ordering of the vectors. In effect the similarity between two points is defined by the degree to which their feature dimension rankings agree. As an example, Yagnik's proposal is a measure like the above:\n",
    "\n",
    "__Equation 1__:\n",
    "$$\n",
    "    PO(X,Y) = \\sum_{i} \\sum_{j<i}  T((x_i − x_j ) (y_i − y_j)) \n",
    "$$\n",
    "\n",
    "where:\n",
    "- $x_i$ and $y_i$ are the i-th feature dimensions in\n",
    "- $X,Y$: ranked ordered vectors\n",
    "- $T$ is simply a threshold function\n",
    "\n",
    "Equation 1 simply measures the number of pairs of feature dimensions in X and Y that agree in ordering.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above PO function and the Threshold: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def WTA_similarity(vector1,vector2):\n",
    "    \n",
    "    PO=0\n",
    "    for i in range(0,len(vector1),1):\n",
    "        for j in range(0,i,1):\n",
    "            ij_1 = vector1[i] - vector1[j]\n",
    "            ij_2 = vector2[i] - vector2[j]\n",
    "            PO += WTA_Threshold(ij_1*ij_2)\n",
    "            \n",
    "    return PO\n",
    "\n",
    "def WTA_Threshold(x):    \n",
    "    if x>0:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Comparison with MinHash\n",
    "\n",
    "WTA is a generalization of the well-known MinHash and should enjoy the theoretical benefits of LSH schemes. MinHash is a special case of WTA when applies to binary feautures.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## __Implementation code in Python__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Import of libraries__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Main code__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from wta import WTA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example and Remarks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Example (from original paper)\n",
    "\n",
    "An example with 6-dimensional input vectors, \n",
    "- K = 4, and \n",
    "- θ = (1, 4, 2, 5, 0, 3). \n",
    " \n",
    "X in (a) and (b) are unrelated and result in different output codes, 1 and 2 respectively. X in (c) is a scaled and offset version of (a) and results in the same code as (a). X in (d) has each element perturbed by 1 which results in a different ranking of the elements, but the maximum of the first K elements is the same, again resulting in the same code.\n",
    "\n",
    "\n",
    "#### Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[10,  5,  2,  6, 12,  3],\n",
       "       [ 4,  5, 10,  2,  3,  1],\n",
       "       [22, 12,  6, 14, 26,  8],\n",
       "       [11,  4,  3,  7, 13,  2]])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [10,5,2,6,12,3]\n",
    "b = [4,5,10,2,3,1]\n",
    "c = [22,12,6,14,26,8]\n",
    "d = [11,4,3,7,13,2]\n",
    "theta = [1, 4, 2, 5, 0, 3]\n",
    "vectors = np.array([a,b,c,d])\n",
    "vectors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "882b1a523c9b485e953c9038a7ddd840",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "WTA hashing:   0%|                                                                                            …"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "K = 4\n",
    "model = WTA(\n",
    "    K=K,\n",
    "    number_of_permutations=1\n",
    ")\n",
    "buckets, new_vectors = model.hash(vectors, theta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'1-0': {0, 2, 3}, '2-0': {1}}"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "buckets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 5, 12,  2,  3],\n",
       "       [ 5,  3, 10,  1],\n",
       "       [12, 26,  6,  8],\n",
       "       [ 4, 13,  3,  2]], dtype=int64)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "new_vectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pairwise agreement of a,b,c,d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Similarity on X: \n",
      "WTA_similarity(a,b) =  5\n",
      "WTA_similarity(a,c) =  15\n",
      "WTA_similarity(a,d) =  14\n",
      "\n",
      "\n",
      "\n",
      "Similarity on X': \n",
      "WTA_similarity(a,b) =  2\n",
      "WTA_similarity(a,c) =  6\n",
      "WTA_similarity(a,d) =  5\n",
      "\n",
      "\n",
      "\n",
      "Similarity on X'[:K]: \n",
      "WTA_similarity(a,b) =  2\n",
      "WTA_similarity(a,c) =  6\n",
      "WTA_similarity(a,d) =  5\n"
     ]
    }
   ],
   "source": [
    "print(\"Similarity on X: \")\n",
    "print(\"WTA_similarity(a,b) = \",WTA_similarity(a,b))\n",
    "print(\"WTA_similarity(a,c) = \",WTA_similarity(a,c))\n",
    "print(\"WTA_similarity(a,d) = \",WTA_similarity(a,d))\n",
    "print(\"\\n\\n\")\n",
    "print(\"Similarity on X': \")\n",
    "print(\"WTA_similarity(a,b) = \",WTA_similarity(new_vectors[0],new_vectors[1]))\n",
    "print(\"WTA_similarity(a,c) = \",WTA_similarity(new_vectors[0],new_vectors[2]))\n",
    "print(\"WTA_similarity(a,d) = \",WTA_similarity(new_vectors[0],new_vectors[3]))\n",
    "print(\"\\n\\n\")\n",
    "print(\"Similarity on X'[:K]: \")\n",
    "print(\"WTA_similarity(a,b) = \",WTA_similarity(new_vectors[0][:K],new_vectors[1][:K]))\n",
    "print(\"WTA_similarity(a,c) = \",WTA_similarity(new_vectors[0][:K],new_vectors[2][:K]))\n",
    "print(\"WTA_similarity(a,d) = \",WTA_similarity(new_vectors[0][:K],new_vectors[3][:K]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Kendal Tau similarity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.stats import kendalltau"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarity based on Kendal Tau for the initial vectors ($X$)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "kendalltau(a,b) =  -0.3333333333333333\n",
      "kendalltau(a,c) =  0.9999999999999999\n",
      "kendalltau(a,d) =  0.8666666666666666\n"
     ]
    }
   ],
   "source": [
    "similarity_prob, p_value = kendalltau(a,b)\n",
    "print(\"kendalltau(a,b) = \", similarity_prob)\n",
    "similarity_prob, p_value = kendalltau(a,c)\n",
    "print(\"kendalltau(a,c) = \", similarity_prob)\n",
    "similarity_prob, p_value = kendalltau(a,d)\n",
    "print(\"kendalltau(a,d) = \", similarity_prob)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarity based on Kendal Tau for the permuted vectors ($X'$)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a,b similarity:  -0.3333333333333334\n",
      "a,c similarity:  1.0\n",
      "a,d similarity:  0.6666666666666669\n"
     ]
    }
   ],
   "source": [
    "similarity_prob, p_value = kendalltau(new_vectors[0],new_vectors[1])\n",
    "print(\"a,b similarity: \", similarity_prob)\n",
    "similarity_prob, p_value = kendalltau(new_vectors[0],new_vectors[2])\n",
    "print(\"a,c similarity: \", similarity_prob)\n",
    "similarity_prob, p_value = kendalltau(new_vectors[0],new_vectors[3])\n",
    "print(\"a,d similarity: \", similarity_prob)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a,b similarity:  -0.3333333333333334\n",
      "a,c similarity:  1.0\n",
      "a,d similarity:  0.6666666666666669\n"
     ]
    }
   ],
   "source": [
    "similarity_prob, p_value = kendalltau(new_vectors[0][:K],new_vectors[1][:K])\n",
    "print(\"a,b similarity: \", similarity_prob)\n",
    "similarity_prob, p_value = kendalltau(new_vectors[0][:K],new_vectors[2][:K])\n",
    "print(\"a,c similarity: \", similarity_prob)\n",
    "similarity_prob, p_value = kendalltau(new_vectors[0][:K],new_vectors[3][:K])\n",
    "print(\"a,d similarity: \", similarity_prob)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Overall Remarks\n",
    "\n",
    "\n",
    "## Advantages\n",
    "\n",
    "1. Very fast hashing method. For example, consider using it in a classification problem.\n",
    "2. No need of trainning\n",
    "\n",
    "## Disadvantages\n",
    "\n",
    "1. Only applied to ranked vectors\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# References\n",
    "\n",
    "[1.]   [The Power of Comparative Reasoning Jay Yagnik, Dennis Strelow, David A. Ross, Ruei-sung Lin](http://www.cs.toronto.edu/~dross/YagnikStrelowRossLin_ICCV2011.pdf)"
   ]
  }
 ],
 "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.10.5"
  },
  "toc-autonumbering": false,
  "toc-showcode": false,
  "toc-showmarkdowntxt": false,
  "toc-showtags": false
 },
 "nbformat": 4,
 "nbformat_minor": 4
}