cos類似度の次元の呪い

元ネタはこちらの記事コサイン類似度が高いベクトルはどれくらい似ているか(岩波データサイエンス刊行イベントより) - 木曜不足．

cos類似度は計算しやすいので，言語処理界隈では単語ベクトルや画像理処理界隈ではヒストグラムをベクトルに見立てその2つが似ているかどうかに使われやすい．

上記の記事をよくよく考えると，cos類似度は次元数によって珍しい類似度の値が変わるので極端に1に近い数字，0に近い数字が出ても鵜呑みにしてはいけないんじゃないかと思ったので，それについてのメモ．（この解釈が正しいのか，スパース界隈の論文探せば触れてそうだけど似たような図が出てこなかったのでちょっとわからん．）

cos類似度おさらい

参考：コサイン類似度

2つのベクトルがどのくらい似ているかを角度を使って表す．

マイナス成分もあれば[-1, 1]で表され，1に近ければ平行より類似している，0に近ければ直交より無関係を表すと判断されることが多い．

例としては，以下が多い.

PCAやword2vecあたりで単語ベクトルを作成し2つの単語が似ているか，この場合はマイナス成分があるので[-1, 1]の範囲になりやすい．
記事などの文書から単語頻度をみてそれをベクトルとして2つの文書が似ているか，頻度の場合，マイナス成分がないので[0, 1]の範囲で扱う．
画像のRGB, HSV値などからヒストグラムを作って各ビンをベクトルとして，2つの画像が似ているか，これも頻度なので[0, 1]の範囲で扱う．

ポイントはベクトルの大きさは正規化され無視され，角度のみを見る指標になる．

2つのベクトルっがあれば次の式で計算できる，

$$ \cos{( \theta) } = \frac{\vec{x} \cdot \vec{y}}{|\vec{x}||\vec{y}|} = \frac{\vec{x}^{T} \vec{y}}{|\vec{x}||\vec{y}|} $$

ランダムでベクトルを作成しその類似度を見るシミュレーション

ランダムでベクトルを作成し類似度を見てみる．

単純な直感でいくと類似度も一様になりそうだが，そんなことは起きず，次元の呪いが起きる．

一様乱数で２つのベクトルを作成
cos類似度を計算
100,000回回してヒストグラムを作成

マイナス成分ありのベクトルの場合

一様乱数U[-1, 1]からベクトルを作成する．

こちらの記事と同じ結果になる．コサイン類似度が高いベクトルはどれくらい似ているか(岩波データサイエンス刊行イベントより) - 木曜不足

このヒストグラムの特徴をまとめると，，

ヒストグラムの形を見ると，dim=2のときは±1の時が最も高く0の時が低いお盆型，dim=3のときは一様分布に近いが±1のときが最も高くお盆型を多少引きずった形． dim=4から山型に変わる．特にdim=6から釣鐘型になり類似度0を平均とした正規分布のような形になる．次元数を増やしていくと類似度0の裾が重くなるようなt分布ぽい？形になる．
次元を増やすと類似度0が集中してくる．これはdim=2のときは±90度ときのみ直交するが，次元が増える=軸が増えるなので直交するパターンがいくつも出てくるため．
次元数が増えても，平行するパターンは増えるわけではないので，類似度1は減っていく．

さらに考察・解釈してみると，

次元数によって類似度の出現が大きく変わる（低次元では類似度は高くなりやすく，高次元では低くなりやすい）ので，他次元での類似度は一概に比較できない．
低次元であるdim=2のときは, 類似度[0.95-1]のときが約10,000/100,000=10%と一番高い（類似度[-0.95,-1]の時も同様）．つまり，テキトーにベクトルを2つ選んでも類似度は±1になりやすいのでこれは珍しい値ではない（価値が低いといえるかもしれない）．逆に直交するパターンが一番少ないので，類似度0付近の時は珍しく価値が高いといえるかもしれない．

再現code: gist: 類似度 · GitHub

import scipy as sp
import scipy.stats as stats
import scipy.spatial as spatial
import matplotlib.pyplot as plt

dims = sp.array([2, 3, 4, 5, 6, 7, 8, 9, 10, 100])
uniform = stats.uniform(-1, 2)
def cos_sim(vec1, vec2):
    return 1 - spatial.distance.cosine(vec1, vec2)

def get_cos_sim_array(count, dim):
    cos = sp.zeros(count)
    for i in sp.arange(count):
        vec_1 = uniform.rvs(dim)
        vec_2 = uniform.rvs(dim)
        cos[i] = cos_sim(vec_1, vec_2)
    return cos

n = 100000
bins = sp.linspace(-1, 1, 40+1)
fig = plt.figure(figsize=(16, 12))
for i, d in enumerate(dims):
    cos = get_cos_sim_array(n, d)
    ax = fig.add_subplot(round(len(dims)/2), 2, i+1)
    ax.hist(cos, bins)
    ax.set_title(f"dim = ${d}$", fontsize=20)
    ax.grid()

plt.tight_layout()
plt.savefig("cos_sim.png")
plt.show()

頻度のようなプラス成分のみベクトルの場合

単語頻度やヒストグラムなどに多いプラス成分のみのベクトル同士でのcos類似度ではどうなるかをみる．

一様乱数をU[0,1]の範囲に変えるだけで確認できる．

実際のところ，マイナス成分がないと，直交するパターンは軸上に乗っているとき(2次元(1,0）(0, 1)) しかないので偶然直交することはほぼない．（スパース性の恩恵みたいな効果が起きている．）

（ビン幅は1/40 = 0.25になっている）

同様に，このヒストグラムの特徴をまとめると，

マイナス成分アリの場合では左右対称であったが，こちらの場合どの次元でも左裾が長い（右側に偏った）分布になる．
次元を増やしても直交するパターンは軸上しかないので，ランダムに選んでも類似度0はほぼ出ない．上記であったランダムに選んでも直交してしまうといった次元の呪いが起きない．
低次元，特にdim=2,3の場合，類似度[0.975-1]が最も多くでる（つまり，平行になりやすい）．
次元が増えると，この最頻値はdim=4では[0.875-0.9), dim=5では[0.825-0.85)と小さくなっていき左にシフトしていく．

さらに，考察・解釈してみると，

低次元，特にdim=2,3の場合，類似度[0.75-1]が最も多くでるので，テキトーにベクトルを2つ選んでも類似度=1になりやすくこれは珍しい値ではない（価値が低いといえるかもしれない）．
全体的に直交はしないが，第1象限にベクトルが集中している． dim=4から次元数が増えると，類似度は0.8付近が一番高くなる．つまり，テキトーにベクトルを2つ選んでもこのくらいの類似度はよく起き（価値が低く）．実際に関係のあるベクトルであるかどうかは判断しにくいといえる．ただし，dim=100のような高次になればなるほど，ランダムにとっても， 0に近いまたは1に近い類似度は現れないので，珍しい（価値が高い）類似といえるかもしれない．
特に100次元では，類似度の最頻値は[0.75-0.775]で，この類似度高めの数字は，ランダムに選んでも約30, 000/100,000 = 30%近く現れる．なので，この付近の値が出ても鵜呑みにすべきではないように思える．