あいまい検索とLocality Sensitive Hashing
これは30日チャレンジの6日目（2019/09/14）に書かれた文章です
「あいまい検索」と聞いて何を思い浮かべるだろうか。 例えばGoogleもあいまい検索機能を提供している。 試しに「あいまい検索」と検索してみてほしい。おそらく「曖昧検索」にヒットしたページも結果に表示されるだろう。
本文では、我々が「あいまい検索」と呼んでいる機能の観察からはじめ、実装のひとつであるLocality Sensitive Hashingをみていきたい。
さて、今一度冒頭の質問にもどろう。 Googleのあいまい検索を例として挙げたが、それではSQLのLIKE文は「あいまい検索」と呼べるだろうか。 あるいはSlackの絵文字検索はあいまい検索機能を実装していると言えるだろうか。
誤解を招かないよう、先に言葉の定義を済ませたいと思う。 本文では「あいまい検索」という単語を「Fuzzy Search」を指すものとして用いる。 すなわち、「与えられた検索パターンに対してスペルミスやギャップも考慮して検索結果を返してくれる、あいまい性を含んだ検索」を指すものとする。
単純な文字列（厳密）一致に関する効率的なアルゴリズムやデータ構造は古から研究が進んでいる。 オンライン検索では対象文字長lに対して線形時間O(l)、インデックスを用いればパターン長mの線形時間O(m)で検索を完了できる*1。
一方で、あいまい性を含んだ検索は厳密一致ほどうまくいかない。 あいまい性には定義からして不確定・確率的な要素が含まれており、厳密な理論的解析を行うことが難しいからだ*2。 あるいは逆に全てのあいまい性を受け入れ、あらゆるケースを完全に網羅した検索を考えると、その計算量は組合せ論的な様子を呈すことが予想される。
じつは、あいまい検索のタスクには上記で述べた文字列検索的なアプローチとは別に、より実用的な近傍点探索のアプローチが存在する。 近傍点探索のアプローチでは、読んで字の如く、検索対象の集合Tと検索パターンPを同一空間内で表現（写像）し、Tの要素の中からPの近傍点を探し出す。散布図上で近い点を集めるイメージをすると理解しやすい。
さらに近傍点探索のアプローチとしては、とくにLocality Sensitive Hashing（以下、LSH）を用いた近傍点探索手法が広く知られている。 一般にハッシュ関数と言うときはハッシュ値が入力に依存せずに偏りなく分布することが望ましいが、LSHにおいては類似データA,Bはそのハッシュ値H(A), H(B)も近い値を持つことが期待される。 本アプローチのポイントの要諦は、LSHの性質を利用しハッシュ値の類似性であいまい検索を実現することにある。
例えば、以下表のような検索対象集合Tとハッシュ関数hがあり、検索パターンP=“pineapple”であいまい検索を行うことを考えよう。
e.g. LocalitySensitiveHashな関数hと検索対象の集合T
| i | T[I] | h(T[i]) |
|---|---|---|
| 1 | apple | 12345 |
| 2 | lemon | 23456 |
| 3 | orange | 34567 |
手順は非常に簡単だ。まずPに対して同じハッシュ関数hを適用する。 いま、h(P)=12356が得られたとしよう。あとはこの値と適当な閾値xを用いて検索をかければ良い。 すなわち、h(P) - x ≤ h(T[I]) ≤ h(P) + xを満たすT[i]をすべて集めれば、あいまい検索が完了する。 この例ではx=15程度に設定しておけば、あいまい検索の結果として「apple」が取得できる。
抽象的な議論が多く要諦が掴みづらい文章になってしまった。 近々、より具体的な例を用いてLSHの解説に再挑戦したい。
これは30日チャレンジの7日目（2019/09/15）に書かれた文章です
前回は「あいまい検索」のタスクと、その実装の一手段としてLocality Sensitive Hashing（以下、LSH）を学んだ。 本文ではより具体的な議論に踏み込み、自然言語処理の分野で古くから用いられるMinHashアルゴリズムにふれたあと、実際にMinHashアルゴリズムを用いたあいまい検索の実装を行う。
まずはMinHashアルゴリズム（以下、MinHash）とは何かを説明する。 MinHash自体は非常にシンプルで、「入力として適当なハッシュ関数h: R -> Rと、ベクトルv=(v_1, …, v_d)を受け取り、出力としてmin{h(v_i} | i = 1, ..., d }を返す」操作を指す。 このときハッシュ関数hはLSHである必要はなく、むしろ分布が偏らない性質を備えていることが望ましい。 紛らわしいが、逆にMinHashで得られた値はLSHとして利用できる。つまり、類似するベクトルはその成分の最小値をとる操作を行っても似たような値をもつ。
MinHashにおいて最も重要な洞察は、むしろMinHashの出力をJaccard係数の近似として用いることができるという事実の方だ*3。 どうしてJaccard係数の近似となるのかという議論に関してはPFI岡野原さんの記事が詳しいので参照されたい。
近似値の評価については後述するが、ここではまず「文字列として与えられる検索対象をベクトルに変換するか」を述べておく。 文字列のベクトル表現にはさまざまな種類がある。素朴なものとしてn-gramやbag of words、あるいは機械学習技術によって意味論まで考慮に入れたベクトル表現も登場した。 本文では最も素朴な表現であるbag of words（以下、BoW）表現を用いる。 BoW表現は「集合に含まれる要素を列挙した表現」と捉えることができ、Jaccad係数による類似度を計算するにも都合が良い。
本文では検索対象の単位として英単語を想定しているため、BoW表現のインデックスとしては英文字[a-z]に相当する26次元の2値ベクトルを考える。
e.g. apple, lemon, orangeのBoW表現
[apple] v: [1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0] [lemon] v: [0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0] [orange] v: [1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0]
さて、MinHashはあくまでJaccard係数の近似を与えるにすぎないという点に注意されたい。 近似を真の値に近づけるためには複数のMinHashを用意し、それらの出力を統合して評価する必要がある。 そして複数のMinHashを得るには、MinHashのもう一つの入力である”任意のハッシュ関数h”も複数必要になる。 それでは、複数の”任意のハッシュ関数h”は一体どのようして用意すればよいだろうか。
この問いの答えは、ハッシュ関数hの使われ方を考えると自然に見えてくる。 ハッシュ関数hはMinHashの中でベクトルv=(v_1, …, v_d)の各要素v_iに適用され、それぞれを不偏な他の値に変換することが期待される。 この要件を達成するには、入力と同じ次元を持ったランダムなベクトルr=(r_1, …, r_d)を生成し、v_iに対して同じインデックスの値r_iを返すだけで十分である。 プログラマはハッシュ関数というとMD5やSHA256のような高級な関数をイメージしがちだが、ここで言うハッシュ関数hはごく限られた範囲の入力を不偏な値に変換するだけで十分だ。
ここで一度、上記の議論をまとめよう。 今回解こうとしているタスクは「検索対象T[i]と検索パターンPを与えられたとき、TからPに似た文字列を得る」ことだ。 タスクの解決策としてはLSH（MinHash）を考える。 文字列のベクトル変換にはBoW表現を用い、文字列の類似度にはJaccard係数の近似を用いる。 Jaccard係数の近似は、N個のハッシュ関数を用意し”MinHash値の衝突回数”を数え上げることで得られる。 またこの際、N個のハッシュ関数はランダムな値をもったベクトルをN個生成して得る。
今回は本手法を実際にgolangを用いて実装した。 作成したgoプログラムは以下URLからアクセスできる。興味のある方は参照されたい。
以下に実行結果を記す。
Enter query: raspberry query: raspberry, v: [1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 3 1 0 0 0 0 0 1 0] [apple] v: [1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 0 0 0 0 0] [pineapple] v: [1 0 0 0 2 0 0 0 1 0 0 1 0 1 0 3 0 0 0 0 0 0 0 0 0 0] [orange] v: [1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0] [lemon] v: [0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0] [grape] v: [1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0] [cherry] v: [0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 1 0] [strawberry] v: [1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 3 1 1 0 0 1 0 1 0] [banana] v: [3 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0] [peach] v: [1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0] [apple] score: 33 [pineapple] score: 24 [orange] score: 34 [lemon] score: 9 [grape] score: 51 [cherry] score: 39 [strawberry] score: 72 [banana] score: 23 [peach] score: 28
検索対象としていくつかのフルーツの名前を用意しておき、パターンとして”raspberry”を与えた。 ハッシュ関数はN=100個用意し、scoreはMinHashの衝突回数をそのまま表示している。
検索結果をみると、”raspberry”と同じく”berry”を接尾辞としてもつ” strawberry”が最も高いscoreを記録した。 逆に構成文字として”e”のみを共有する”lemon”は最も低いスコアとなっている。
以上、MinHashアルゴリズムの説明とその実装例をみてきた。 本文では一貫して単語を検索対象としていたが、MinHashはむしろ文章の類似度推定に用いられることが多い。 その場合にはBoW表現のインデックスに単語を用いることに注意されたい。
