min-wise 独立性による文書類似度の算出とランダムサンプリング手法 (1998)

Min-Wise Independent Permutations

Brahms サンプリング^[1] の論文に出てきた Min-Wise Independent Permutations^[2] (1998) という特性を使ったアルゴリズムが興味深かったのでその論文を読み解いたまとめと昔話。

論文は AltaVista Search が文書の類似度を効率的に算出するために提案した min-wise 独立置換族 (min-wise independent permutation family; 最小値独立置換族) の特性と、実際にそれを使用した類似度の算出方法やランダムサンプリングの方法について書かれていた。紙面の多くが証明と置換族 $\mathcal{F}$ の大きさの下限を導くのに割かれていたので、min-wise 独立の定義をその意味するところを理解するのが主なところだった。

AltaVista の前夜話

昔々、DEC というコンピュータ企業があった。Intel の Pentium プロセッサがいよいよ 100MHz を超えたと騒いでいた時期に DEC Alpha シリーズは 500MHz を達成していて当時は非常に高い技術力を持った企業だった。しかし往時の Sun Microsystems と同じく、企業が独自のアーキテクチャを売りとする時代は終焉を迎え、惜しまれながら Compaq に合併吸収された企業である (その後に Compaq も合併吸収され現 HP に至る)。

また DEC は黎明期のインターネットを支えた企業で、ネットを構成するサーバやルーターに DEC の VAX マシンがよく使われていた。ポピュラーな通信プロトコルの改行コードが CRLF を採用していたりバイト順序がビッグエンディアンを採用しているあたりは当時の VAX の名残である。

そんな DEC は Google ができる以前に AltaVista Search という強力な Web 検索サービスを持っていた。日本語が使い物にはならなかったので国内では依然として goo、Excite、Yahoo! などが主流だったが、当時の英語圏での全文検索エンジンとしての評判は抜きん出て高かったことを記憶してる。

さて、全文検索では 2 つの文書 $A$ と $B$ がどれだけ似ているかという類似度を頻繁に計算する。例えば類似度 $r(A,B) \in [0,1]$ が 1 に近いほど $A$ と $B$ は類似しているとしよう。率直な全文検索では、ユーザの入力した検索クエリーと最も類似度の高い文書を検索する。つまり、自身の文書データベースの中から $r($検索クエリー$,D)$ の大きい順に文書 $D$ を抽出したリストを作成して応答する。また、応答リストにほぼ同じ内容の文書を入れても無駄なので、類似する文書は代表的な 1 つを除いてランクを下げるような動作も必要である。

当時の AltaVista は重複文書の検出のために $r(A,B)=\frac{|S_A\cap S_B|}{|S_A\cup S_B|}$ となる w-shingling という類似度を使用していた。まあ、これは「両文書のどちらにも出現する単語数 ÷ 少なくともどちらか片方の文書に出現する単語数」という Jaccard 係数による古典的な指標である ($S_A$ を文書 $A$ に含まれる単語の(非順序/非多重)集合とする / 対象の文法要素が何かの記述はなかったのでここでは雑に "単語" としておく)。

ここで問題がある。愚直に w-shingling を適用するにはすべての文書に含まれるすべての単語を保存しておく必要がある。しかし世界中から収集した膨大な量の文書をそのような形で保存するのは現実的ではない。そこで DEC のエンジニアは、1 文書ごとに min-wise で 1000 程度の単語をランダムに抽出してそれを比較すれば良いんじゃね? 🤔といううまい方法 (後述) を思いついたようである。そのランダムサンプリングと類似度算出に必要な数学的特徴を説明するために min-wise 独立という特徴が導入された。

min-wise 独立置換族

まず min-wise 独立とはどういう性質かを定義しよう。

定義 1: ある集合 $X$ に含まれる任意の要素 $x \in X$ を範囲 $\{0,\ldots,M-1\}$ に写す写像の族を $\mathcal{F}$ とする。$\mathcal{F}$ から一様にランダムに選んだ写像 $\pi$ が次の条件を満たすとき、族 $\mathcal{F}$ は min-wise 独立である。

$${\rm Pr}\left(\min\{\pi(X)\}=\pi(x)\right)=\frac{1}{|X|}$$

min-wise 独立性を持つ置換族 $\mathcal{F}$ を min-wise 独立置換族 (min-wise independent permutations family; 最小値独立置換族) と呼ぶ。

ここでの置換 (permutation) とは "並べ換え", "入れ替え", "交換" の意味で、写像、つまり関数や変換マップのようなものを指している。族とは同じ数学的特徴を持った集まりである。

置換 $\pi$ と置換族 $\mathcal{F}$

厳密さは置いておいて、置換 $\pi$ をハッシュ関数で置き換えてみると理解しやすくなる。ここでは SHA-256 のような単一で固定的なハッシュ関数に Salt を組み合わせて「置換族」を生成するとしよう。つまり「$\mathcal{F}$ から $\pi$ を一様にランダムに選ぶ」ことを、Salt $\sigma$ をランダムに選んでハッシュ関数に $\pi: x \mapsto {\rm sha256}(\sigma\,||\,x)$ のように束縛することで代替する (表記の $||$ は連結の意味)。

import secrets
import hashlib

def choose_pi_at_random_from_f():
  sigma = secrets.token_bytes(16)
  return lambda x: hashlib.sha256(sigma + x).digest()

pi = choose_pi_at_random_from_f()
print(pi(b"abc").hex())   // 実行ごとに変わるが同じπとxに対して同一の値となる256-bit 値

SHA-256 のハッシュ値は 256-bit なので上記の $\pi$ は任意のバイト列で構成される集合 $X$ を範囲 $\{0,\ldots,2^{256}-1\}$ に写す写像と考えることができる。

min-wise 独立の意味と応用

さらに集合 $X$ の例としてユーザ ID の集合を考えてみよう。このとき定義 1 は「あるユーザ ID をハッシュ値にしたとき、それが全ユーザ ID のハッシュ値の中で最小である確率は均等に "1÷全ユーザ数" である」ということを述べている。重要なのは、各ユーザ ID が最小になる事象がそれぞれ独立であることと、すべてのユーザ ID で一様の確率であるということである。そのような数学的性質を持つ置換 $\pi$ の族 $\mathcal{F}$ を min-wise 独立置換族と呼んでいる。

この性質がランダムサンプリングとどう関係しているのだろうか? 🤔 上記を逆に説明すると「min-wise 独立な性質を持つハッシュ関数 $\pi$ を使って全ユーザ ID の中から最も小さいハッシュ値を持つユーザ ID を求めることは、全ユーザ ID の中からランダムに 1 つのユーザ ID を選ぶことに等しい」という意味が現れる。min-wise 独立とは、このような方法でランダムサンプリングする時にハッシュ関数 $\pi$ に必要な性質を表している。

異なる $n$ 個の $\pi$ を用意してそれぞれで最小となるユーザ ID を求めれば $n$ 個の復元ランダムサンプリング (重複する可能性のある) を構成することができるのは明らかだろう。そうなると自然に「$\pi$ を一つ用意して小さい順に $n$ 個保持すれば非復元サンプリング (重複なし) になんじゃね?」という考えが浮かぶが、最小から 2 番目以降の確率も均等という前提は今回の min-wise 独立の定義の範疇を超える。そのような着想のアプローチに (昇順/降順が逆だが) Reservoir サンプリング法と呼ばれているアルゴリズムがあるので興味があれば調べてみると良い。

近似 min-wise 独立性

我々は SHA-256 のような暗号論的ハッシュ関数がおおむねランダムなハッシュ値を生成することを経験的に知っているが、しばしばそれが数学的に証明および保証された性質ではないことに注意する必要がある。少なくとも (現実的に困難な頻度ながらも) 強衝突を持つハッシュ関数は定義 1 を満たすことはできないだろう。したがって、厳密にはここまでの説明で使用した $\pi$ をハッシュ関数とした族は min-wise 独立ではないということになる。

しかし、$\pi$ の手段としてハッシュ関数を適用することは現実的には十分に合理的である。ここで定義 1 を少し緩和した近似 min-wise 独立 (approximately min-wise independent) を追加する。

定義 2: ある集合 $X$ に含まれる任意の要素 $x \in X$ を範囲 $\{0,\ldots,M-1\}$ に写す写像の族を $\mathcal{F}$ とする。$\mathcal{F}$ から一様にランダムに選んだ写像 $\pi$ が次の条件を満たすとき、族 $\mathcal{F}$ は近似 min-wise 独立である。

$$\left|Pr(\min\{\pi(X)\}=\pi(x)) - \frac{1}{|X|}\right| \le \frac{\epsilon}{|X|}$$

定義 2 での緩和は、最小値となる確率がそれぞれの要素で異なることを許すが、その差はある (微少な) 定数の範囲内であるということを述べている。$\pi$ へのハッシュ関数やその他の現実的に実装可能な関数の適用はこの近似 min-wise 独立の性質に相当するだろう (ただし私には $\epsilon$ を見積もれるほどの知識はないが🗿)。

なお、この近似 min-wise 独立に対して定義 1 の性質を厳密 min-wise 独立と呼ぶ。

制約 min-wise 独立性

$\pi$ を関数ではなくランダムな変換表となるように実装することもできる。この場合、像の衝突を完全に排除することができるため厳密 min-wise 独立の要件を満たすことも難しくはない。しかし、現実的な実装を考慮すると集合の大きさの上限を $|X|\le k$ のように制限する必要がある。このような制限を持った族を制限 min-wise 独立 (restricted min-wise independent) と呼ぶ。

定義 3: ある集合 $X$ に含まれる任意の要素 $x \in X$ を範囲 $\{0,\ldots,M-1\}$ に写す写像の族を $\mathcal{F}$ とする。$\mathcal{F}$ から一様にランダムに選んだ写像 $\pi$ が次の条件を満たすとき、族 $\mathcal{F}$ は制限 min-wise 独立である。

$$Pr(\min\{\pi(X)\}=\pi(x)) = \frac{1}{|X|},\;\; |X|\le k$$

AltaVista での局所性に依存する応用

さて話を戻して、AltaVista Search は min-wise 独立の性質をどのように文章の類似度計算に応用したのだろうか。論文によれば先の w-shingling 類似度は min-wise 独立な $\pi$ に次のように対応する。

つまり「文書 $A$ と $B$ の類似度は、$A$ と $B$ から min-wise で選んだ単語が一致する確率と一致する」と述べている。これが成立する証明は論文にはなかったが、直感的に、$S_A$ と $S_B$ が完全に同じ集合ならどのような $\pi$ に対しても 1 になるし、完全に異なれば 0 になることは明らかである。

とりあえずこの式が成立すると仮定すると、次のようなアルゴリズムで文書の類似度を求めることができる。

1. 設定: min-wise 独立な族 $\mathcal{F}$ から異なる $\pi$ を $n$ 個用意し、それぞれを $\pi_i$ とする (おおむね $n=1000$ 程度)。
2. 保存: 文書 $A$ をインデックスするときに、各 $\pi_i$ に対して最小となる単語 $\min\{\pi_i(S_A)\}=w_{A,i}$ を算出して保存する。
3. 比較: 文書 $A$ と $B$ の類似度は、各 $i$ に対して $w_{A,i}$ と $w_{B,i}$ が等しい数÷$n$ である。

この比較ステップは単語集合の和と積を都度構築しなければならない愚直な Jaccard 係数算出より遙かに低コストであることは明らかだろう。

さらに、AltaVista Search が実際に採用していた置換族 $\mathcal{F}$ は線形変換 $\pi(x)=ax+b \bmod p$ だったと書いている。これは… ( ﾟдﾟ)ﾊｯ! 線形合同法? つまり線形合同法の疑似乱数生成器を使って一様乱数に変換していたという意味だろう。もちろんこの線形変換では近似 min-wise 独立すらも満たさないのだが、ハッシュ演算や巨大な変換表より効率が良いのは見ての通りだし、これでも実際に当時の実用には耐え得る精度が出たならこまけぇこたぁいいんだよ!! (直感的に $\pi$ が疑似乱数生成器でも十分機能するとは思うが、論文にはこの形式の線形変換を適用したときの確率も記載されている)。

min-wise 独立置換族の応用

AltaVista Search の話題で min-wise 独立の性質が文書の類似度を算出するのに大きく役立つことを示した。この AltaVista の類似度算出スキームは MinHash という名前で知られている。しかし、いま時点で自然言語処理において古典的と言われる手法でも TF-IDF + コサイン類似度を使うのが一般的であるように思うため、w-shingling に依存するこの方法がどこまで現代に向いているかは分からない。

また min-wise 独立性で任意の集合からランダムサンプリングに使用できることも示した。この利点は、まず、集合 $X$ のサイズが巨大でも (何なら無限であっても) $O(1)$ の空間複雑性でサンプリングを行うことができる。観測した要素で最小要素を更新すれば良いだけなのでストリームデータ処理にも向いている。さらに、要素の取得と更新を繰り返してゆけばランダムにサンプリングされた "真の" 部分集合に収束するという確率論的な振る舞いをすることから、完全に正確でなくても無限集合のような巨大な集合を対象にしたいというケースに適用できるだろう。例えば Brahms ではこの方法を使って動的なネットワークからランダムにノードをサンプリングする方法を提案している。

現代の min-wise 独立は、どちらかというと文書類似度の算出よりも大規模データ処理の方が適用局面は多いかも知れない。

脚注

1. BORTNIKOV, Edward, et al. Brahms: Byzantine resilient random membership sampling. In: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing. 2008. p. 145-154.

2. BRODER, Andrei Z., et al. Min-wise independent permutations. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing. 1998. p. 327-336.