One key method that you will use to reduce the computational cost of finding Neighbors in high dimensional spaces is locality sensitive hashing. In this video, I will teach you what hashes are and where they are used. To start thinking about locality sensitive hashing, let's first assume that you're using word vectors with just two dimensions. Other pits each vector as a circle instead of arrows. So let's say you want to find a way to know that these blue dots are somehow close to each other, and that these great thoughts are also related to each other. First divide the space using these dashed lines, which I'll call planes. I'll explain why I call them planes in a bit. Notice how the blue plain slices up the space into vectors that are above it or below it. The blue vectors all happen to be on the same side of the blue plane. Similarly, the gray vectors happen to be above the great plain. It looks like the planes can help us pocket the vectors into subsets based on their location, this is exactly what you want. A hashing function that is sensitive to the location of the items that it's assigning into buckets. You're working your way towards locality sensitive hashing. Now, let's see why I'm calling these dash lines planes. A plane would be this magenta line into two dimensional space and it actually represents all the possible vectors that would be sitting on that plane. In other words, they would be parallel to the plane such as this blue vector or this orange vector. You can define a plane with a single vector, this magenta vector is perpendicular to the plane and it's called the normal vector to that plain. The normal vector is perpendicular to any vectors that lie on the plane. It might help to think about this in three dimensions, find a sheet of paper and find a pencil. Place the paper on the table and draw some vectors on it, then hold the pencil vertically over the paper. Any vectors on the paper are perpendicular to the pencil. Let's go back to two dimensions, you are able to see visually when the vector is on one side of the plane or the other. But how do you do this mathematically? Here are three sample vectors in blue, orange and green, the normal vector to the plane is labeled P. Let's focus on vector one, what if you take the dot product of P with vector one, you get three. I'll explain in a bit why you're doing this. Now, Let's look at Vector two, if you take the dot products of P with vector two you get zero. Finally, Let's look at the extra three, if you take the dot product of P with vector three, you get negative three. So the dots products are three, zero, and negative three. Do you notice something about the science and how they're related to their position relative to the red plane? When the dot product is positive, the vector is on one side of the plane. If the dot product is negative, the vector is on the opposite side of the plane. If the dot product is zero, the vector is on the plane, so what's the dot products doing. To visualize the dot product, imagine one of the vectors such as P as if it's the surface of the earth. Gravity pulls all objects straight down towards the surface of the earth, next pretend you're standing at the end of the vector V1. You tie a string to a rock and let gravity pull the rock to the surface of vector P, the string is perpendicular to vector P. Now, if you draw a vector that's in the same direction of P, what ends up at the rock, you have what's called the projection of vector V1 onto vector P. The magnitude or length of that vector is equal to the dot product of V one and P. Furthermore, if you had this other green vector and projected it onto vector p, the projected vector would be pointing in the parallel but opposite direction of P. The dot product would be a negative number. This means that the sign of the dot product indicates the direction of the projection with respect to the purple normal vector. So whether the dot product is positive or negative can tell you whether the vector V1 or V2 are on one side of the plane or the other. Let's use code to check which side of the plane a vector is on. The function side of plane takes in the normal vector P and a vector V. Use np dot to take the dot product, use np dot sign to get a plus one, if the dot product is positive. -1 if the product is negative or zero if the dot product is zero, I'm using np dot as scalar. Notice the pronunciation of that function, if a vector can be represented as a single scalar, dysfunction retrieves that scalar and that's it. Please try it out for yourself, that was a lot of visualizations and the lots of projections. The main takeaway is that the sign of the projection of two vectors tells you which parts of the line the point lies. For example, above it or below it. In the next video, you will learn how to combine this concept with multiple planes to try to better approximate where a data point might be located.
