probability - ミンハッシュ計算の証明

Question

2 つのセット間の類似性を推定する MinHash 手法について読んでいます。セット A と B が与えられた場合、h はハッシュ関数であり、hmin(S) はセット S の最小ハッシュです。つまり、hmin(S)=min(h(s(s) )) S の s に対して、次の方程式があります。

p(hmin(A)=hmin(B))=|A∩B| / |A∪B|

これは、A の最小ハッシュが B の最小ハッシュと等しい確率が、A と B の Jaccard 類似度であることを意味します。

私は上記の式を証明し、独自の証明を考え出そうとしています: a∈A と b∈B に対して、h(a)=hmin(A) と h(b)=hmin(B) となります。したがって、hmin(A)=hmin(B) の場合、h(a)=h(b) となります。ハッシュ関数 h がキーを個別のハッシュ値にハッシュできると仮定すると、a=b の場合にのみ h(a)=h(b) となり、その確率は |A∩B| になります。/ |A∪B|。ただし、ハッシュ関数は異なるキーに対して同じ値を返す可能性があるため、私の証明は完全ではありません。そこで、ハッシュ関数に関係なく適用できる証明を見つけるために、あなたの助けを求めています。

Answer 1

ハッシュ関数は、(A ∪ B) のランダム順列を提供する手段と考えてください。さて、その順列について考えてみましょう。

選択した順列pを使用して、(A ∪ B) のすべての可能な要素をテーブルの行として配置します。2 つの列 A と B は、次のようになります。

A = {1, 3, 5, 6}
B = {2, 3, 4, 6}
p = {5, 6, 1, 2, 4, 3}

テーブル：

   A  B
5  1  0
6  1  1
1  1  0
2  0  1
4  0  1
3  1  1

行には、X: A と B が 1 の 2 つのタイプしかありません。 Y: A != B の場合です。

全部で (A ∪ B) 行あります。ただし、タイプ Y の (A ∩ B) 行のみです。最初の行がタイプ Y の 1 つである可能性は、Y/(X+Y) です。または Pr[hmin(A) = hmin(B)] = (A ∩ B)/(A ∪ B)。

これは、Nilesh がリンクした本が言っていることとまったく同じですが、別の例で説明しようとしました。