はじめに

「TextRetrieval と 検索エンジン」第3回目の更新です。
いよいよ、ベクトル空間の話をします。
ここから徐々に数式が増えてきます。
これで、week 1 は終わりになります。

1-5 ベクトル空間の基本的な考え方

前回いろいろなText Retrieval モデルを紹介しましたが、今回はその中で、ベクトル空間モデルについて、詳しくみていきます。

ベクトル空間モデルは、ランキング関数を $f(q,d) = similarity(q,d)$　のようにおきます。
このベクトル空間モデルでは、一つの仮説を設けます。
Assumption
もし、クエリとドキュメントが似ているならば、ドキュメントはより関連性がある。
関連性をクエリとドキュメントの類似性と位置付けておきます。

3次元だと、３単語しか、表現できませんので、各軸が表す単語を決めておきます。
(色は、図で使われている軸の色です。)

\vec{d_i} =\begin{pmatrix}
search  \\
car  \\
engine
\end{pmatrix}
=\begin{pmatrix}
red  \\
green  \\
blue
\end{pmatrix} \\
\vec{q_i} =\begin{pmatrix}
search  \\
car  \\
engine
\end{pmatrix}
=\begin{pmatrix}
red  \\
green  \\
blue
\end{pmatrix} \\

例えば、「search engine」と書かれたドキュメントを上記ベクトルで表すと、次のようになります。

\vec{d_1} =\begin{pmatrix}
search  \\
car  \\
engine
\end{pmatrix}
=\begin{pmatrix}
1  \\
0  \\
1
\end{pmatrix}

「engine」と書かれたドキュメントを、同様に表すと次のようになります。

\vec{d_2} =\begin{pmatrix}
search  \\
car  \\
engine
\end{pmatrix}
=\begin{pmatrix}
0  \\
0  \\
1
\end{pmatrix}

「car」と書かれたドキュメントを、同様に表すと次のようになります。

\vec{d_3} =\begin{pmatrix}
search  \\
car  \\
engine
\end{pmatrix}
=\begin{pmatrix}
0  \\
1  \\
0
\end{pmatrix}

これまでに定義したベクトルを３次元の図に描くとこうなります。

では、クエリに「car engine」とした場合、クエリベクトルは次のようになり、３次元の図は下の図のようになります。

\vec{q_1} =\begin{pmatrix}
search  \\
car  \\
engine
\end{pmatrix}
=\begin{pmatrix}
0  \\
1  \\
1
\end{pmatrix}

直感的に、$\vec{q_1}$ は、$\vec{d_2}$と$\vec{d_3}$により近く、$\vec{d_1}$　からは離れていることがわかると思います。
（ベクトルの要素を0,1にしてしまうと、言葉的に意味のある例を作れる数に限界が・・・）
この結果から、$\vec{d_2}$と$\vec{d_3}$のドキュメントをユーザーに返すのはリーズナブルな感じがしますよね？

これが、ベクトル空間モデルを検索に生かす基本的な考え方です。

ベクトル空間をフレームワークとして考える

ベクトル空間をフレームワークとして考えると、次のような定義ができます。

• ドキュメントもクエリもTerm Vectorとして、表現する。
• Term (ターム)を基本的なコンセプトとし、単語やフレーズとする。
• 1次元につき、1タームを割り当てる。(Bag Of Wordsとして有名な考え方です。)
• $N$タームあった場合、それは $N$次元ベクトルになる。
  • 今回は、3タームの3次元ベクトル
• クエリベクトルは$\vec{q} = \begin{pmatrix} x_1, ... , x_N \end{pmatrix}$, $x_i\in \mathbb{R}$ is クエリタームの重み
• ドキュメントベクトルは$\vec{d} = \begin{pmatrix} y_1, ... , y_N \end{pmatrix}$, $y_j\in \mathbb{R}$ is ドキュメントタームの重み
• $relevance(q,d) \propto similarity(q,d) = f(q,d)$　とする。

ベクトル空間モデルが対象外としていること

ベクトル空間モデルで、検索エンジンの問題の全てが解決できるわけではありません。

• どのようにタームを定義するか
• どのようにドキュメントとクエリを空間に配置するか　i.e. どのように重みをつけるか
  • クエリタームの重みは、その単語がどのくらい重要かを表す。
  • ドキュメントタームの重みは、そのドキュメントをどのくらい特徴付けているかを表す。
• どのように$similarity(q,d)$を計算するか

1-6ベクトル空間モデル実装編

ベクトル空間モデルを実装するために、

• どのように重みをつけるか
• どのように$similarity(q,d)$を計算するか

を考えなければなりません。

まずは、とても簡単に重みを次のように置いてみます。

$\vec{q} = \begin{pmatrix} x_1, ... , x_N \end{pmatrix}$, $x_j\in $　{ $ 0,1 $ }
$\vec{d} = \begin{pmatrix} y_1, ... , y_N \end{pmatrix}$, $y_j\in $　{ $ 0,1 $ }

該当する単語があった場合、$x_i = 1$となり、存在しない場合、$x_i = 0$とします。
上でみたベクトルと同じです。
$0,1$で表すので、これを Bit Vector といいます。

次に、$similarity(q,d)$　を計算する方法を考えます。
上記で、
「直感的に、$\vec{q_1}$ は、$\vec{d_2}$と$\vec{d_3}$により近く、$\vec{d_1}$　からは離れていることがわかると思います。
この結果から、$\vec{d_2}$と$\vec{d_3}$のドキュメントをユーザーに返すのはリーズナブルな感じがしますよね？」
という話をしましたが、二つのベクトルが近いか遠いかを判断するのに最適な道具を多分高校生の時に習いましたね！

ベクトルの内積(Dot Product)です。
ここで、内積の復習です。
ベクトルの内積は次のように定義されて、そこから $cos({\theta})$について解くと次のような関係がわかります。

\vec{A} \cdot \vec{B} =   |A|\cdot |B| cos({\theta}) \\
cos({\theta}) = \frac{ \vec{A} \cdot \vec{B}}{ |A|\cdot |B| }

実際に、$\vec{A}$ と$\vec{B}$ を同じ要素を持ったベクトルにすると、$ cos({\theta}) = 1$となります。
$ cos({\theta}) = 1$ となるような、$\theta$は、０になります。
この特性を生かして、クエリと"にている"ドキュメントを探す。
これが、基本的な検索のためのベクトル空間モデルの考え方です。　

まとめ：超単純 VSM （The Simplest VSM）

ここまでで、私たちは、検索のためのベクトル空間を次のように定義しました。

• Dimension: 1次元につき、1単語に割り当てる。(Bag of Words)
• Vector: ベクトルの重みは、ドキュメントに単語があるかないかで、1か0を振り分ける。
  • $\vec{q} = \begin{pmatrix} x_1, ... , x_N \end{pmatrix}$, $x_j\in $　{ $ 0,1 $ }
  • $\vec{d} = \begin{pmatrix} y_1, ... , y_N \end{pmatrix}$, $y_j\in $　{ $ 0,1 $ }
• $similarity(q,d)$は、ベクトルの内積を使う。

このベクトル空間を使ったランキングは、良いものでしょうか？
どんな問題があるでしょうか？

それを次回ご紹介します！
ベクトル空間の Retrieval Model　の問題点などを紹介します。

終わりに

今回のベクトル空間で遊んでみたい人もし良ければ、どうぞ。
geogebra