高次元空間でのユークリッド距離とコサイン類似度

以下のツイートを見かけたので、実験して考察してみました。

https://twitter.com/minomazda/status/1464901882342633476?s=21

# 実験①

ランダムに選んだ3つの点 $x,y,z\in\mathbb{R}^n\setminus\\{0\\}$ について、ユークリッド距離とコサイン類似度による遠近が一致する確率を考えれば良さそうです。つまり

$$ ||x-y||\leq||x-z|| \Leftrightarrow\mathrm{cos}(x,y)\geq\mathrm{cos}(x,z) $$

が成立する確率を考えます。当然これは $x,y,z$ をどのような分布からサンプリングするかに依存します。とりあえず、ここでは簡単な例として多次元の標準正規分布と一様分布の場合を調べてみます。解析的に調べるのはちょっと大変そうな気がしたので、まずプログラムを書いてサンプリングして実験してみました。

<details><summary>プログラムはこちら</summary><div>

```python
import numpy as np
import scipy.stats as stats
import matplotlib.pyplot as plt
from tqdm import tqdm

distributions = {
    'N(0,1)': lambda N,D: stats.norm.rvs(size=(N,D)),
    'U(0,1)': lambda N,D: stats.uniform.rvs(size=(N,D)),
}

def euc(x, y):
    return np.linalg.norm(x-y)

def cos(x, y):
    return np.dot(x,y)/(np.linalg.norm(x)*np.linalg.norm(y))

def C(x, y, z):
    return (euc(x,y) >= euc(x,z)) == (cos(x,y) <= cos(x,z))

N = 1000
for name in distributions:
    distribution = distributions[name]
    dims = range(1, 500)
    ps = []
    for D in tqdm(dims, desc=name):
        x = distribution(N, D)
        y = distribution(N, D)
        z = distribution(N, D)

        p = np.mean([
            C(x[i], y[i], z[i])
            for i in range(N)
            ])
        ps.append(p)

    plt.scatter(dims, ps, s=1, label=name)
    plt.legend()

plt.ylabel('P(euc=cos)')
plt.xlabel('dim')
plt.savefig('euclidean-cos.png')
```

</div></details>

結果は下図の通り。

![1B92CEC7-41E6-47E8-B400-646D9579222C.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/83682/91659f19-4610-e0d3-406c-a20b7500a8fe.png)

プログラムが誤ってなければ、少なくともこの2つの単純な分布では高次元になるほど遠近が一致するという現象は **見られませんでした**。
ごく低次元を除けば、遠近が一致する確率は次元によらず標準正規分布ならば80%程度、一様分布ならば87%程度になっていそうです。
ところで、上のツイートへのコメントに、球面集中現象の働きではないかというものが見受けらましたが、これらの分布でも同様の現象は生じているので関係ないと思います。

以上の実験から、単に高次元であるというだけでは標題の現象は起こらないと言えます。(もちろんそれはそう)
となると、「高次元になるほどユークリッド距離とコサイン類似度による遠近が一致する」ような確率分布はどの様なものであるか興味が湧いてきますね。例えば $||x||=\text{const.}$ であるような空間であれば遠近が一致しますが、この場合は低次元であっても一致するわけなので「高次元になるほど」という訳ではありません。

# 実験②
近傍探索の状況での実験を行う為に、続いて以下のセッティングで実験をしてみました。

ランダムに選んだ1点 $x\in\mathbb{R}^n\setminus\\{0\\}$ と、ランダムに選んだ $y_1,\ldots,y_N\in\mathbb{R}^n\setminus\\{0\\}$ に関して、 $y_1,\ldots,y_N$ の中で $x$ に最も近いものが、ユークリッド距離とコサイン類似度を使った場合で一致する確率を求める。

<details><summary>プログラムはこちら</summary><div>

```python
import numpy as np
import scipy.stats as stats
import matplotlib.pyplot as plt
from tqdm import tqdm

def normed(x):
    return x/np.linalg.norm(x, axis=-1, keepdims=True)

distributions = {
    'N(0,1)': lambda size: stats.norm.rvs(size=size),
    'U(0,1)': lambda size: stats.uniform.rvs(size=size),
    'normed U(0,1)': lambda size: normed(stats.uniform.rvs(size=size)),
}

def euc(x, y):
    return np.linalg.norm(x-y)

def cos(x, y):
    return np.dot(x,y)/(np.linalg.norm(x)*np.linalg.norm(y))

N = 1000
G = 100 # group size
for name in distributions:
    distribution = distributions[name]
    dims = range(1, 500)
    ps = []
    for D in tqdm(dims, desc=name):
        x = distribution((N, D)) # query point
        y = distribution((N, G, D))

        neq = 0
        for i in range(N):
            ei = np.argmin([
                euc(x[i], y[i,j])
                for j in range(G)
                ])
            ci = np.argmax([
                cos(x[i], y[i,j])
                for j in range(G)
                ])
            neq += (ei == ci)

        ps.append(neq/N)

    plt.scatter(dims, ps, s=1, label=name)
    plt.legend()

plt.ylabel('P(euc=cos)')
plt.xlabel('dim')
plt.savefig('eucledean-cos-NN.png')
```

</div></details>

以下が結果ですが、正規分布、一様分布の場合には5~8次元あたりで一致する確率がピークになるという面白い結果になりました。

`normed U(0,1)` というのは一様分布から取ったサンプルをノルム1に正規化した場合で、念のため追加しました。当たり前ですが、この場合は近傍探索の結果は必ず一致します。

![DD497893-F157-42EC-8FAD-6E09F5E67A4A.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/83682/57d4e7e9-e004-aff1-7359-f1f055ccc5bd.png)

# 考察

$n$ 次元標準正規分布に従うベクトル $x$ について

$$ \frac{n}{\sqrt{n+1}} \leq E[||x||] \leq \sqrt n,\quad 0 \leq V[||x||] \leq 1 $$ 

ですので、ベクトルのノルムの平均値は増えていく一方、ノルムの分散は $1$ 以下に抑えられます。
従って $x$ は $n$ が大きいほど超球面上に分布していると見なせる(球面集中効果)ようになっていくので、そうなるとコサイン類似度とユークリッド距離が近づいていくはずだというのは、なんかそんな気もします。ただ、上の結果はそれとは反しています。

一つ思い当たる事としては、$x,y$ が標準正規分布に従う時、 $E[\mathrm{cos}(x,y)]=0$ になりますが、$n$が大きいと$V[\mathrm{cos}(x,y)]\rightarrow 0 $ になってしまいます。つまりほとんどの場合 $\mathrm{cos}(x,y)$ はほぼ $0$ になるという事です。つまり、確かに球面集中効果によって超球面上に分布はするものの、それぞれは互いに直交してしまっているという事ですね。
一方で $n$ を大きくしても、 $V[||x||]$ は $0$ に収束しません(1/2かな?)。従って

- 高次元では超球面上に分布するようになるが、ほとんど全て直交してしまう。一方でノルム方向のばらつきは0にはならず残る。

という事です。これが、球面集中効果が働いていてもユークリッド距離とコサイン類似度による遠近が一致せずギャップが生じている理由ではないかと思います。(もちろん以上は正規分布の場合の話で、他の分布では状況は変わります)

以上、全く厳密な議論ではないですが、なんかそれっぽい結論が得られました。是非誰か詳しく調べて見て欲しいです。