TextRetrieval と 検索エンジン1-5 ベクトル空間モデル

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

# 1-5 ベクトル空間の基本的な考え方
前回いろいろなText Retrieval モデルを紹介しましたが、今回はその中で、ベクトル空間モデルについて、詳しくみていきます。

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

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

```math
\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」と書かれたドキュメントを上記ベクトルで表すと、次のようになります。

```math
\vec{d_1} =\begin{pmatrix}
search  \\
car  \\
engine
\end{pmatrix}
=\begin{pmatrix}
1  \\
0  \\
1
\end{pmatrix}
```
「engine」と書かれたドキュメントを、同様に表すと次のようになります。

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

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

```math
\vec{d_3} =\begin{pmatrix}
search  \\
car  \\
engine
\end{pmatrix}
=\begin{pmatrix}
0  \\
1  \\
0
\end{pmatrix}
```
これまでに定義したベクトルを３次元の図に描くとこうなります。
![Screen Shot 2020-05-11 at 0.09.33.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/75208/79157ec1-15f2-8d9e-1fb7-2fa2787c6559.png)

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

```math
\vec{q_1} =\begin{pmatrix}
search  \\
car  \\
engine
\end{pmatrix}
=\begin{pmatrix}
0  \\
1  \\
1
\end{pmatrix}
```
![Screen Shot 2020-05-11 at 0.18.43.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/75208/4f68de82-3d6f-fc2f-7276-aa6770f309b4.png)
直感的に、$\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})$について解くと次のような関係がわかります。

```math
\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](https://www.geogebra.org/3d/vbezt7gh)