Youtube subtitles download by mo.dbxdb.com
you get attractive complexity you can do
it really really quickly but the
question is at what cost right and this
comes back to your question when you
were asking is there a chance that after
doing it with 20 tables you never find
and yes there is a chance and we can
quantify that chance
so what we're looking for are we looking
for the false negative rate for the Miss
rate of the lsh and what it means what
the Miss rate means is i have two
documents a and B they're close by they
have they're almost identical they're
different by maybe a couple of words
so what is the probability that they
will not collide in any of my l hash
tables so what's the probability that i
never find them in the same bucket and
that we can figure out right so that
happens if not of the l hash codes for
the two documents are exactly the same
so it's none of the l hash codes match
that I will never see and be in the same
bucket of some hash table so there will
be miss now what is the probability that
none of the hash tables for a and B
match now the way i'm generating the Hat
the way i'm generating the hash codes is
I'm cutting the space with random hyper
plates so that different sets of
hyperplanes are completely independent
of each other and they're also generated
in the same exact way so the hash codes
are independent of each other it was
different hash tables and they're also
identically distributed because i'm
generating them according to the same to
the same random process so the hash
codes are iid now since they're
independent i can turn bad statement
none of the hash codes match this means
every one of the l hash codes is
different and that just because a
product / l different hash codes that
are generated for each of the hashtag
Bulls the probability that I hashcode 4a
is different from the ice hashcode for
be okay so now i need to make that what
is the probability that I passion for a
is different for me but before I do that
I'm going to simplify this product of it
not only are the independent they're
also identically distributed so instead
of doing the product i can just take
this probability that i hash code is not
the same and reason to the power L
because every hash code is independent
of each other and it's identically
distributed so it's just the probability
that the hashcode of a is not the same
that the hashcode as I should be raised
to the power L so I have helped
independent events now what is the
probability that hash code is different
remember hash code is a sequence of K
bits and for the hashcode of a to be
different from the hashcode of B it's
enough to have one bit that is different
so if anyone of the K bits is different
between the two hash codes they will not
match right so the probability of the
hashcode are not equal means that any of
the K bits are different and another way
to write this is any of the cabinets are
different if it's not the case that all
K bits are the same
I'm just I'm just logical logical
negation here so the probability that
any bit is different is 1 minus the
probability that all bits are the same
and i'm still raising it to the power L
because i'm repeating it L times 4l
different table so i have 1 minus the
probability that all bits in the
hashcode or the same and now I play the
same trick the individual bits are
independent
why because they're based on separate
hyper planes which are generated
completely random and they're also
identically distributed because I'm
sampling the hyper planes from the same
random number generator so i can rewrite
that as follows the probability that all
K bits
are the same as the probability that one
bit is the same raised to the power of k
+ 1 minus the quantity is the
probability that any one of the K bits
is different so that is my final form
and usually what you do is you represent
this quan this event the probability
that some bit is the same for two
different points a and B you call it P
which is a parameter of illustration
we'll talk about where that comes from
so overall form is just going to be 1
minus P to the K so Peter MacKay is the
probability that all kids have the same
1 minus that probability that at least
one of them is different
raised to the l power it is repeated al
times in a row so that is the
probability that a and B we'll never
land in the same hash table bucket if i
generate k bit hash codes and repeat the
process
l times ok now you can make a very
similar argument for the false positive
rate so what's a false positive rate
force positive rate that's um so in
terms of the previous slide that's one
of the documents that you didn't want to
have in the hash pockets but it's still
ended up being in that in that hash
pocket by accident so you don't want a
and B to collide
what is the probability that they
collide by accident the probability that
they collide by accident is the
probability that at least one of the l
hash codes is the same and that means
that all the K bits in that one hashcode
are exactly the same so you can work it
out it works out to about that one minus
one minus q2 the K raised to the power
else we have a parameter Q here
typically you have P and Q are different
because you p is a parameter it's if the
probability that they have the same bit
assuming that they are in fact your
duplicates and q is a parameter that
they have the same that bit assuming
they're not your duplicates so here and
be our negatives you don't want them in
the same in
in the same bucket so q is the
probability that they have the same bit
now where do we get P and Q and it turns
out for lsh the way we've described it
you can figure out what P and Q are
going to be fairly simple right so I'm
gonna take my I'm gonna take my space
from the previous slide sort of and
we'll look at it from the side
ok so i have two dimensions dog and cat
and let's say i have two documents
they're landing somewhere so this is
document a document be and what I'm
interested in is uninterested in the
probability that one of the bits for a
and B is going to be the same or that
one of the bits is going to be different
that they're related events now think
about how am i how am I assigning the
bits i'm assigning the bits based on the
hyper planes so what I'm going to do is
I take the hibrane I got through that
space and then the two documents are
going to end up having the same bit if
they happen to be on the same side of
that hyper plane and they'll have
different bits in one event only if the
hyperplane cuts between them right so if
i have a hyperplane that cuts that
happens to cut between a and B then B is
gonna have one and a is gonna have 20 so
the probability that a and B have a
different bit is just the probability
that hyper plane lands between them
now what is the probability that hyper
plane falls between two vectors and be
and that you can compute quite easily
because think about how am I generating
these hyper plates i'm generating them
by sampling random numbers they're
random hyperplanes so a hyperplane is
equally likely to fall anywhere in this
quadrant so the probability that it's
going to cut between A&B is proportional
to the angle between V so this angle
shaded is theta so my probability is
just going to be
proportional to how big data is with
respect to the entire to to the entire
quadrant now what is faith a and B are
documents their unit length factors i'm
projecting them to unit sphere mine so
if i take a transpose B if I just do a
dot product between A&B when their unit
length a dot product is just the cosine
of the angle so you can compute the
angle by the product and thinking that
our cosine of that that will just give
you the angle the angle theta so the
probability that a hyperplane I given
hyperplane a random hyperplane is going
to cut between A&B is just theta is the
angle between the documents / the
overall size and angular signs which in
this case is PI over 2 so that's going
to be the probability that two documents
are separated and then are you can use
that to compute the probability that
they have the same bit it's just 1-3 i'm
substituting the arc cosine instead of
the theta so now you know how to relate
the probability now you know how to
relate the cosine between the two data
points to the probability that they will
have the same bit
well and then you think the same
probability and put it into your
estimates and you now you can compute
the Miss rate of your lsh you can figure
out how many your duplicate pairs you
will miss and how many false alarms you
will have how many false positives you
will have to compare two in your buckets
and they're both dependent on that Subtitles End: mo.dbxdb.com