第 5 章 ま と めと 今後の課題
A.2 検索精度に関する 考察
本節ではStaged LSHにおけ る ハッ シュ 探索， スク リ ーニン グ， 精査の各工程を 正解指 紋がパスする 確率を 求め， 検索精度に大き な影響を 与え る ハッ シュ 値のビッ ト 数について 1つの最適解を 求める 。
こ こ でいう 正解指紋と は、 ク エリ 指紋の元と なっ た音楽と 同じ 音楽から 生成さ れた指紋 のこ と である 。 逆に不正解指紋と は， ク エリ 指紋の元と なっ た音楽と は別の音楽から 生成 さ れた指紋のこ と である 。 “一致な し”と いう 検索結果も 存在する が， こ れは正解指紋と も 不正解指紋と も 異な る 。
精度に は指紋生成ア ルゴリ ズム に 起因する も のと 指紋検索ア ルゴリ ズム に 起因する も のが考え ら れる が， 本稿では指紋生成に関し て は十分な精度が保証さ れて いる 想定で， 指 紋検索に関する 精度を 考察する 。
A.2.1 不正解指紋が精査を パスし て し ま う 確率
ま ずは検索精度について 考え る 。 検索精度を 確保する 上では， 異なる 音楽の指紋のハミ ン グ距離がある 程度離れて いる こ と が最低限必要である 。 でき ればε2よ り 大き いこ と が 望ま し い。 さ も なく ば， 不正解の音楽を 検索結果と し て 返す恐れが生じ る 。 誕生日のパラ ド ッ ク ス に よ れば， 乱数を 大量に 発生さ せる と ， 同じ 値が複数回発生(衝突)し て いる 確 率は直感よ り も 高い。 こ こ では4096ビッ ト のHiFP2.0の指紋について 誕生日のパラ ド ッ ク スを 考慮し て も 千万曲の指紋同士が互いにε2よ り 離れて いる こ と を 確認し て おき たい。
ま ず， 2指紋Rf p, Wf pのハミ ン グ距離がε2以下である 確率は， 指紋が乱数と みな せる な ら ば次のよ う に表さ れる 。
P2,2 = P[HD(Rf p, Wf p)≤ε2]
= 1
2L2
ε2
X
i=0
L2Ci (A.1)
こ れを 3指紋， 4指紋， · · ·， N指紋と 増やし て いく と ，
P2,N < 1− {1−P2,2}{1−2P2,2} · · · {1−(N −1)P2,2}
≃ 1− {1−NP2,2}(N−1)/2
≃ 1−exp
"
−N(N −1) 2 P2,2
#
(A.2) と な る 。 こ こ で途中計算の簡単化のためN は奇数， N ·P2,2 ≪ 1と し た。 N が偶数の場 合も 最終的な 式は同じ である 。 こ の式を L2 = 4096, ε2 = 1024, N = 107の条件で計算す る と P2,N ≃0である 。 つま り HiFP2.0が生成する 指紋が乱数に近け れば， 千万曲の指紋
実際にはHiFP2.0が生成する 指紋は必ずし も 乱数と はみな せな い。 特に4096ビッ ト の 先頭付近は0である こ と が多い。 指紋DB内にハミ ン グ距離の近い指紋がある 場合の対応 について は今後の課題と する 。
な お数値計算には次のMathematicaスク リ プト を 実行し た。
✓ ✏
l2 = 4096;
e2 = 1024;
n = 10^7;
p22 = 2^(-l2) * Sum[l2!/k!/(l2-k)!, {k,0,e2}];
p2n = 1 - Exp[-n*(n-1)/2 * p22];
Print[N[p2n]];
✒ ✑
A.2.2 正解指紋が精査を パスでき ない確率
歪んだク エリ 指紋と 正解指紋のハミ ン グ距離を 考え る 。 も し こ のハミ ン グ距離が精査の 閾値ε2よ り 大き いよ う では， どれだけハッ シュ 探索と スク リ ーニン グを チュ ーニン グし て も 検索は必ず失敗する 。 確率計算を する と ， 指紋はL2ビッ ト である から ， 歪み率pber >0 のク エリ 指紋Qf pと 正解指紋Rf pのハミ ン グ距離がε2よ り 大き い確率は，
P2 = P[HD(Qf p, Rf p)> ε2]
= 1−
ε2
X
i=0
h
L2Ci·(pber)i(1−pber)L2−ii (A.3) である 。 L2 = 4096, ε2 = 1024の条件の下， 歪み率を 変え な がら こ の式の確率を 計算し た も のを 図A.1に 示す。 歪み率pber ≤ 0.22であれば， 0.99以上の確率で正解指紋は精査を パスする 。 HiFP2.0の指紋の歪み率(ビッ ト エラ ー率)は文献[1]では最大0.15であり ， こ の時P2 = 1.0×10−62である ので， 正解指紋が精査を パスでき ない心配はほと んど 不要で ある 。
0 0.2 0.4 0.6 0.8 1
0 0.1 0.2 0.3 0.4 0.5 確率P2
歪み率
図 A.1: ク エリ 指紋の歪みによ り 正解指紋が精査を パスし な い確率
な お数値計算には次のMathematicaスク リ プト を 実行し た。
✓ ✏
l2 = 4096;
e2 = 1024;
n = 10^7;
For[i = 1, i <= 50, i = i + 1, pber = i / 100;
p2 = 1 - Sum[l2!/(k!*(l2-k)!) * pber^k * (1-pber)^(l2-k), {k,0,e2}];
Print[N[pber], " ", N[p2]];
✒]; ✑
A.2.3 正解指紋がスク リ ーニン グを パスでき ない確率
ス ク リ ーニン グに ついて も ， 正解指紋がパス でき な いこ と はあま り な い。 ク エリ 指紋 Qf rと 正解指紋Rf rのハミ ン グ距離がε1よ り 大き い確率は， フ レ ーム がL1ビッ ト である から ，
P1 = P[HD(Qf r, Rf r)> ε1]
= 1−
ε1
X
i=0
h
L1Ci·(pber)i(1−pber)L1−ii (A.4) である 。 L1 = 96, ε1= 24の条件の下， 歪み率を 変え な がら こ の式の確率を 計算し たも の を 図A.2に示す。 歪み率pber ≤0.16であればスク リ ーニン グで検出でき る 確率は0.99以 上である 。
0 0.2 0.4 0.6 0.8 1
0 0.1 0.2 0.3 0.4 0.5 確率P1
歪み率
図 A.2: ク エリ 指紋の歪みによ り 正解指紋のフ レ ームがスク リ ーニン グを パスし ない確率 な お数値計算には次のMathematicaスク リ プト を 実行し た。
✓ ✏ l1 = 96;
e1 = 24;
n = 10^7;
For[i = 1, i <= 50, i = i + 1, pber = i / 100;
p1 = 1 - Sum[l1!/(k!*(l1-k)!) * pber^k * (1-pber)^(l1-k), {k,0,e1}];
Print[N[pber], " ", N[p1]];
✒]; ✑
A.2.4 LSH のハッ シュ 値にビッ ト エラ ーがある 確率
以上から ， 検索全体の精度はほと んど ハッ シュ 探索の成功確率のみに左右さ れる 。 そこ でク エリ 指紋の1フ レ ーム のハッ シュ 値に rnビッ ト よ り 多く のビッ ト エラ ーがある 確率 を 求める と 次の通り である 。
P0 = P[Hash(Qf r)6= Hash(Rf r)]
= 1−
rn
X
i=0
h
L0Ci·(pber)i(1−pber)L0−ii (A.5) こ れがハッ シュ 探索1回の失敗確率である 。 Staged LSHではハッ シュ 探索を 最大でnm回 (nm = (Lf p−Lf r+ 32)÷32 = 126)繰り 返す。 nm回全て 失敗する 確率は
Pall =P0 nm
(A.6) である 。 最終的に， Staged LSHの検索全体と し て の精度は1−Pallにほぼ等し い。
Pallは図A.3のよ う にな る 。 歪み率pber ≤0.25ま でを 想定し ， 隣接LSHの探索対象の ハミ ン グ半径rn = 0,1,2と し た。
0 0.2 0.4 0.6 0.8 1
0 10 20 30 40 50
確率 1 - Pall
ハッシュ値のビット数 L0
rn = 0 rn = 1 rn = 2
図 A.3: ハッ シュ 探索が126回全て 失敗する 確率 数値計算には次のMathematicaスク リ プト を 実行し た。
✓ ✏ nm = 126;
pber = 0.25;
Print["0 0 0 0"];
For[l0 = 1, l0 <= 50, l0 = l0 + 1, pall0 = N[(1 - (1-pber)^l0)^nm];
pall1 = N[(1 - Sum[l0!/(k!*(l0-k)!) * pber^k * (1-pber)^(l0-k), {k,0,1}])^nm];
pall2 = N[(1 - Sum[l0!/(k!*(l0-k)!) * pber^k * (1-pber)^(l0-k), {k,0,2}])^nm];
Print[l0, " ", pall0, " ", pall1, " ", pall2];
✒]; ✑
A.2.5 ハッ シュ 値のビッ ト 数の最適値
ハッ シュ 値のビッ ト 数L0の最適解を 求める 。 L0が大き いと ， 衝突の発生確率が下がる ので検索速度は向上する が， ク エリ 指紋の歪みがハッ シュ 値に波及し やすく なる ので精度 が落ち る 。 ま たハッ シュ テーブルのメ タ データ が大き く な る と いう 問題も ある 。
そこ で一つの最適解は， ク エリ 指紋の歪み率pberの許容上限を 設定し ， その範囲内で例 え ばPall <0.05に な る よ う な 最大のL0を 選ぶこ と である 。 図A.3に おいて Pall <0.05 に抑え る には， rn= 0な ら ばL0 = 13， rn = 1な ら ばL0 = 20， rn = 2な ら ばL0 = 26が それぞれ最適である 。 な お rn = 0について は， Yangの研究[4]でも L0 = 13が最適と さ れて いる 。
ハッ シュ テーブルのメ タ データ のサイ ズに ついて 考え る と ， 図2.14のデータ 構造な ら ば2L0 ·4バイ ト にな る 。 表A.3に示す通り ， 千万曲の指紋DBと ハッ シュ テーブル(本体 データ)の合計サイ ズが約10GBである こ と を 考え る と ， いずれも メ タ データ のサイ ズは 比較的小さ い。 ただし 組込み用途ではコ スト の観点から 10GBのDRAMを 用意する よ り ， 小容量の高速メ モリ と 大容量の低速メ モリ を 組み合わせて 使う こ と が考え ら れる 。 そ の 場合， 256MiBも ある と 現時点では小容量の高速メ モリ を 圧迫し かねな いため， も う 少し ハッ シュ のビッ ト 数を 減ら すか， 1隣接を 採用する べき である 。
表 A.3: ハッ シュ 値のビッ ト 数と ハッ シュ テーブルのメ タ データ のサイ ズ ハッ シュ 値のビッ ト 数L0 メ タ データ のサイ ズ(2L0 ·4バイ ト )
13 32KiB
20 4MiB
26 256MiB