GPT-2の論文中に出てくるBloom filterの解説

OpenAIが出したGPT-2の論文中でtrainデータセットとtestデータセットの間で重複したデータが無いか確かめるためにBloom filterを使ったと述べられている。 Bloom filterは与えられた集合に、ある要素が含まれるかを判別するデータ構造である。要素が無いと判別された場合は確実に存在しない(false negativeは存在しない)が、要素が有ると判別された場合に本当に存在するかは確定しない（false positiveが存在する）。このように確率的な動作をするが、メモリ使用量や計算量オーダーに優れている。

データを挿入する場合は、k個のハッシュ関数を使ってデータをk個の整数にする。フラグ配列を用意し、これらの整数をインデックスとしたk個の要素にフラグを立てる。 データが存在するかの確認は同様にデータをk個のハッシュ関数を使ってk個の整数にして、フラグ配列の対応する要素のフラグが全て立っているかどうかを確認する。全てのフラグが立っている場合は集合にデータが存在する可能性があり、立っていないフラグがある場合は集合には確実にそのデータが存在しない。 false positiveの確率はkと整数のbit数、集合の要素数に依存する。