Location_Sensitive_Hashing_Cosine_Similarity.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What is cosine distance and cosine similarity\n",
    "\n",
    "### Use case of LSH\n",
    "\n",
    "A classical application of similarity search is in recommender systems: Suppose you have shown interest in a particular item, for example a news article x. The semantic meaning of a piece of text can be represented as a high-dimensional feature vector, for example computed using latent semantic indexing. In order to recommend other news articles we might search the set P of article feature vectors for articles that are “close” to x.\n",
    "\n",
    "In this case, for a large textual dataset containing millions of words, the problem is there may be far too many pairs of items to calculate the similarity of each pair. And also, we will have sparse amounts of overlapping data for all items. So in this case, LSH can be used for compressing the rows into “signatures”, or sequences of integers, which will let us compare published-papers or news-articles without having to compare the entire sets of words. Reducing the computational intensity of the model.\n",
    "\n",
    "And note, Locality Sensitive Hashing (LSH) is actually a family of algorithm, different distance metric will correspond to a different method. Here we will be focusing on cosine distance. However, many LSH is calculated based on many other distances including, most famously the Euclidean distance between two vectors or the Hamming Distance and so on.\n",
    "\n",
    "First I shall go over the building block concepts of Location Sensitive Hashing which are cosine similarity, Normal of a Vector and the concept of Hyperplanes.\n",
    "\n",
    "#### What is cosine distance and cosine similarity\n",
    "\n",
    "Let’s consider the following dataset:\n",
    "\n",
    "#### Some other different form of expressing Cosine Similarity mathematically\n",
    "\n",
    "\n",
    "cosine similarity between two points p and q is their dot product divided by their L2-norms:\n",
    "\n",
    "\n",
    "The Cosine Distance (also called angular distance) is one of the most popular distances for LSH and is used as the main metric in this thesis. It is defined for spaces with a dimension, such that points can be considered as vectors as shown in Figure 3. Rather than to distinguish vectors by their length, the Cosine Distance is defined as an angle between two vectors. On any dimension, the angle between two vectors always ranges from 0° to 180°, which is then used to define the distance. Unlike the Euclidean distance, the cosine distance is scale-insensitive.\n",
    "\n",
    "The cosine distance is useful when we need a distance proportional to the angle between two vectors. If the direction is the same, the distance is null, while it is maximum when the angle is equal to 180° (meaning opposite directions). This distance can be employed when the clustering must not consider the L2 norm of each point. For example, a dataset could contain bidimensional points with different scales and we need to group them into clusters corresponding to circular sectors. Alternatively, we could be interested in their position according to the four quadrants because we have assigned a specific meaning (invariant to the distance between a point and the origin) to each of them.\n",
    "\n",
    "The beauty of this distance is its sheer speed at calculating distances between sparse vectors. For instance, if we had 1,000 attributes collected about houses and 300 of these were mutually exclusive (meaning that one house had them but the others don’t), then we would only need to include 700 dimensions in the calculation. Visually this measures the inner product space between two vectors and presents us with cosine as a measure.\n",
    "\n",
    "#### The cosine distance is 1 minus the cosine similarity of two vectors:\n",
    "\n",
    "#### What is a Hyperplane?\n",
    "\n",
    "In mathematics, a hyperplane H is a linear subspace of a vector space V such that the basis of H has cardinality one less than the cardinality of the basis for V. In other words if V is an n-dimensional vector space than H is an (n-1)-dimensional subspace. Examples of hyperplanes in 2 dimensions are any straight line through the origin. In 3 dimensions, any plane containing the origin. In higher dimensions, it is useful to think of a hyperplane as member of an affine family of (n-1)-dimensional subspaces (affine spaces look and behavior very similar to linear spaces but they are not required to contain the origin), such that the entire space is partitioned into these affine subspaces. This family will be stacked along the unique vector (up to sign) that is perpendicular to the original hyperplane.\n",
    "\n",
    "#### Mathematical Representation of Random Hyperplane Hash (RHH) algorithm from [this](https://link.springer.com/chapter/10.1007/978-3-540-87481-2_17) paper\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "Some more mathematical explanation of hyperplane-vs-plane from [math.stackexchange](https://math.stackexchange.com/a/1905956/517433)\n",
    "\n",
    "![](https://imgur.com/z72TWI5.png)\n",
    "\n",
    "\n",
    "#### What is a normal of a Vector ?\n",
    "\n",
    "A surface normal from a surface at P, is a vector perpendicular to the tangent plane to that surface at P. If you know the tangent T and bi-tangent B of the surface at P (which defines the plane tangent to the surface at P) then we can compute the surface normal at P using a simple cross product between T and B:\n",
    "\n",
    "### $$N=T×B$$\n",
    "\n",
    "\n",
    "#### The tangent (T) and bi-tangent (B) are lying in the plane tangent at P. Taking the cross product between T and B gives the surface normal N. Note that T, B and N are orthogonal to each other and form a Cartesian coordinate system.\n",
    "\n",
    "#### Calculus definition of Unit normal vector of a surface\n",
    "\n",
    "\n",
    "[Source](https://www.khanacademy.org/math/multivariable-calculus/integrating-multivariable-functions/flux-in-3d-articles/a/unit-normal-vector-of-a-surface)\n",
    "\n",
    "#### Equation connecting Plane to its Normal or Equation of a Plane being explained by the Normal to the Plane\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "Now we will go through an example to understand the Equation above. From high school geometry, you may recall that a plane is determined by three (noncollinear) points.\n",
    "\n",
    "Let’s find an equation of the plane that contains the points P 0 (1, 2, 0), P 1 (3, 1, 2), and P 2(0, 1, 1).\n",
    "\n",
    "There are two ways to solve this problem. The first approach is algebraic and rather uninspired. From the aforementioned remarks, any plane must have an equation of the form Ax + By + C z = D for suitable constants A, B, C, and D. Thus, we need only to substitute the coordinates of P 0, P 1 , and P 2 into this equation and solve for A, B, C, and D. We have that\n",
    "\n",
    "• substitution of P 0 gives A + 2B = D; • substitution of P 1 gives 3A + B + 2C = D; and • substitution of P 2 gives B + C = D.\n",
    "\n",
    "Hence, we must solve a system of three equations in four unknowns:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "After solving we will get\n",
    "\n",
    "#### `x − 4y − 3z = −7.`\n",
    "\n",
    "#### And now the 2-nd way to solve..\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "If we take P0 (1, 2, 0) to be the particular point in equation (1), we find that the equation we desire is\n",
    "\n",
    "#### (i − 4j − 3k) · ((x − 1)i + (y − 2)j + zk) = 0\n",
    "\n",
    "or\n",
    "\n",
    "#### (x − 1) − 4(y − 2) − 3z = 0.\n",
    "\n",
    "Which is the same equation as the one given by the first method.\n",
    "\n",
    "#### Basic Idea of Location-Sensitive-Hashing\n",
    "\n",
    "LSH refers to a family of functions (known as LSH families) to hash data points into buckets so that data points near each other are located in the same buckets with high probability, while data points far from each other are likely to be in different buckets. This makes it easier to identify observations with various degrees of similarity.\n",
    "\n",
    "Hashing data points can be done in many different ways and depend on the given distance metric. Considering the angular distance as metric, the vector space is divided by randomly generated hyperplanes. These planes cut the space into subspaces, where each subspace represents a bucket. Now, any point within that subspace is distributed to the corresponding bucket (or leaf).\n",
    "\n",
    "Locality Sensitive Hashing (LSH) is a computationally efficient approach for finding nearest neighbors in large datasets. The main idea in LSH is to avoid having to compare every pair of data samples in a large dataset in order to find the nearest similar neighbors for the different data samples. With LSH, one can expect a data sample and its closest similar neighbors to be hashed into the same bucket with a high probability. By treating the data samples placed in the same bucket as candidates for similarity checking, we significantly reduce the computational burden associated with similarity detection in large datasets.\n",
    "\n",
    "#### Mathematical Representation of Locality Sensitive Hashing from [this](https://link.springer.com/chapter/10.1007/978-3-540-87481-2_17) paper\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "Simply put, a locality-sensitive hash function is designed in such a way that if two vectors are close in the intended distance measure, the probability that they hash to the same value is high; if they are far in the intended distance measure, the probability that they hash to the same value is low.\n",
    "\n",
    "#### Actual Implementation steps for LSH\n",
    "\n",
    "\n",
    "\n",
    "The above picture summarizes the generation of Hyperplanes, note the points below about this hyperplane generation math.\n",
    "\n",
    "*   A. How to generate the random plane `π` ? As this `π` hyperplane is passing through origin its equation is `W^T * x = 0` And if Equation of a plane is `W^T * x = 0` that means **W is nothing but the normal to the plane** by definition of Normal of a Vector.\n",
    "*   B. Random hyperplane is generated using `w^Tx = 0` where w is \"normal\" to the plane passing through origin, since w is normal to the plane we have taken values from N(0,1) in order to initialize its value.\n",
    "\n",
    "And now the next steps\n",
    "\n",
    "First make `**m**` hyperplanes to split into regions and create slices such that cluster of points lie in a particular slice and be called their neighbourhood. Typically `m = int(log(number_of_data_points))`\n",
    "\n",
    "*   We consider those hyper-planes vectors, that slice out the regions, as unit vectors. As only the direction of the vector is of importance here.\n",
    "\n",
    "1.  Next for each point create a vector by `W1(transpose).point`. if it is greater than 0 , it lies on the same side of that hyperplane else other side. Based on that create a vector of m size. For eg the vector can be [1,-1,-1] denoting point x lies on same side of normal to hyperplane 1, opposite side to normal of hyperplane 2 and 3. Now this vector serves as key to the hash table and all the points with the same key or vector representation will go in the same bucket as they have similar vector representation denoting they lie in the neighborhood of each other.\n",
    "2.  Random hyperplane is generated using w^Tx = 0 where w is “normal” to the plane passing through origin, since w is normal to the plane we have taken values from N(0,1) in order to initialize its value.\n",
    "3.  Typically many will choose `int(log(number_of_data_points))` hyperplane, but you can opt for any number of hyperplanes to get better results.\n",
    "4.  Now it may happen that two points which are very close fall on different slice due to placing of hyperplane and hence not considered as nearest neighbour. To resolve this problem, create `**l**` hash tables (l is typically small). In other words repeat step 2 above `**l**` times thus creating `**l**` hash tables and `**m**` random hyper-planes `**l**` times. So when a query point comes compute the hash function each of the `**l**` times and get its neighbours from each of bucket.\n",
    "5.  Union them and find the nearest neighbours from the list. So basically in each `**l**` iterations create `**m**` hyperplanes and hence region splitting will be different thus vector representation or hash function of the same query point will be different in each of the representations. Thus the hash table will be different as points which lied on the same region in previous iteration might lie in a different region in this iteration and vice versa due to different placement of hyperplanes.\n",
    "\n",
    "**Time complexity** is `O(m*d*l)` for each query point. And for creating the hash table `O(m*d*l*n)` which is one time only\n",
    "\n",
    "where m is the number of planes. And usually, m will be `int(log(number_of_data_points))`, so time complexity is `O(log n *d)`.\n",
    "\n",
    "Dont think that LSH is trying to break the space in regions such that each of the neighbors is in the same region/cell like in KD-Tree. Unlike KD-Tree, in LSH, we are not trying to break the space into regions. Each hyperplane is independent of others as each of them is chosen randomly. Each hyperplane separates points into two bins: those on each side of the hyperplane. Now as the number of hyperplanes increases, the chance that two points that are close (angularly close as we are using cosine similarity) have the same hash value, h(x), increases as there would be more planes that place the close-by points in the same side.\n",
    "\n",
    "So explaining the whole above steps together, LSH is technique used to create a hash table for identifying the nearest neighbors faster as compared to the other methods. In the other methods, we consider all the points and then carefully shortlist the points which leads to high time complexity. Since KNN is a lazy algorithm, this method retains the complete dataset and builds a model over it. This in turn creates the space complexity.\n",
    "\n",
    "To avoid the above and obtain the nearest neighbors we developed the LSH, where we develop a hashing table basing on the locality ( Nearest neighbors) of the points ( not the query point). This hash table helps us in reducing n different points to a set of points(union) basing on hyperplanes.\n",
    "\n",
    "These hyperplanes are planes which slice through the points and identify the nature of the points i.e., basing on for all i = 1 to m (# of hyper planes)\n",
    "\n",
    "WiXj > 0 is considered as +1 and WiXj < 0 is considered as -1. Basing on this we create a hash table by finding the union of every point with respect to every plane that slices these points We are using Unions here because, if we use intersections then there are chances of losing some numbers.\n",
    "\n",
    "This hash table is stored as the trained data for the new query point that is given as the input. When the new query point is given then we identify the same WiXq for all i =1 to m and identify the nature of the point. Using the output of WXq key we search through the hash table we created with the data and identify the nearest neighbors of the Xq.\n",
    "\n",
    "Accuracy of the model increases with more hyperplanes.\n",
    "\n",
    "#### Time Complexity Improvement\n",
    "\n",
    "Given `**m**` is the number of hyperplanes, and usually, `**m**` will be `int(log(number_of_data_points))`, so time complexity is `O(log n *d)`.\n",
    "\n",
    "If you use the traditional method, it will be `O(n*d)`. There is a significant difference in both these approaches.\n",
    "\n",
    "#### How increasing m increases the accuracy ?\n",
    "\n",
    "The hyperplane generation does not take any information about the dataset into account. Especially when the dataset contains dense clusters of points, it can happen that a generated hyperplane separates those points into different subspaces and does not consider them as near neighbor to each other. Hence, the information. And this problem is largely solved by creating many hyperplanes.\n",
    "\n",
    "As we have more planes, angular distance gets closer to actual distance. In that case if points are pretty much close then only they both get same value else a plane out of pool of planes passes between two points(if distance is reasonable) and assign them two different values. so as m increases points condition to get same value for near points get stricter and stricter so only points which are very close get same value. so accuracy increases\n",
    "\n",
    "#### How exactly the union of Hashed-Bucket work\n",
    "\n",
    "We take all the buckets in which the query point lies and take all the points in those buckets. This is what we are calling union. After taking those points we choose k nearest neighbours.\n",
    "\n",
    "Let us consider we have 3 sets of hash tables h1, h2, h3;\n",
    "\n",
    "1.  h1(x_q) ===> {x4, x7, x9}\n",
    "2.  h2(x_q) ===> {x7, x9}\n",
    "3.  h3(x_q) ===> {x5, x67, x8, x9}\n",
    "\n",
    "Now we consider union of all the 3 sets above the points. And calculate the Nearest neighbours.\n",
    "\n",
    "#### More explanatory points on the above steps described\n",
    "\n",
    "1.  we are not computing the distance here but the sign(W^TX) right.Now since -1 <= cos(theta) <=1 so if w^TX >=0 we have just placed +1 if it is negative then it means points are on the other side right <=0 so we have placed the sign -1.\n",
    "2.  here W^TX gives the projection of X on normal to the plane(W^T). If it comes out to be positive then X got projected toward positive side(in direction of normal to the plane) and if negative then in direction opposite to the normal of the plane.\n",
    "\n",
    "[**Link to Kaggle Notebook**](https://www.kaggle.com/paulrohan2020/location-sensitive-hashing-for-cosine-similarity) **for this entire blog.**"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}