【Day-23】機械学習で使う"距離"や"空間"をまとめてみた

f:id:imslotter:20171223191319p:plain

ここまでデータをどういう風に処理したり、どういうタスクをこなしていくかについて勉強してきたが、一度基礎的な事項に戻ってみたいと思う。基礎だから簡単というわけではない。基礎だからこそ難しく、また本質的な内容。

データ分析で使われている手法などをまとめて集約して、簡単な説明を付け加えていく。しかし、このあたりの数学*1は苦手なので、なるべく直感的に自分のイメージを書いていく。

われわれが生きている空間や、距離は"正しい"のか
- ユークリッド空間/ユークリッド距離
点の距離
分布の距離
- wasserstein計量
カーネル(再生核ヒルベルト空間)
Topological Data Analysis(TDA)
次元削減/Embedding
まとめ

われわれが生きている空間や、距離は"正しい"のか

"正しい"というのは、データ分析に使うのに適切なのか。という意味で書いている。たとえば、新宿まで1.2km"というような表示を見る。地球という座標空間の中で、新宿までの距離が1.2kmというわけだ。われわれは日常生活の中で、それに対して何の疑問も抱かない。それは、日常の距離はユークリッド空間が大前提にあるからである。

ユークリッド空間/ユークリッド距離

簡単に言うと、高校まで*2われわれが生きてきた空間である。たとえば、(0,0)から(3,4)までの距離は？ときかれると、大体の人は三平方の定理だ！となって、5という数字が思い浮かぶ。

けれど、下図を見てほしい。空間が必ずしもx,yの直交座標であらわされるわけではない。厳密に言うと、地球は丸いので、曲がった空間での距離を求めるべきなのである。また、距離の測り方だってバリエーションがあっていいはずだ。ユークリッド距離といえば、斜辺の距離と思いがちだが、たとえば街などは、斜めに横切れないことだってあるので、かくかくと進んでいくことを前提に距離を測ったりする*3。このように状況によって空間や測りかたは変わるべきなのである。

データ分析とは、いろいろなジャンル/いろいろなタスクがあるわけで、それが本当にユークリッド空間/ユークリッド距離で考えるべき話題なのかどうかというのは、考えておくべき問題なのである。非常に根本的な話であるだけに、きれいな空間や距離で解けたものは美しく、汎用性がある。

点の距離

Name	名前	式	備考(あれば)
Euclid	ユークリッド	$\sqrt{ \sum_{i}^{n} {\left(x_{1i}-x_{2i}\right)^{2}} }$	一般的な距離
Manhattan	マンハッタン	$\sum_{i}^{n} \|x_{1i}-x_{2i}\|$	外れ値の影響を受けにくい
Minkowski	ミンコフスキー	$\left(\sum_{i}^{n}{\|x_{1i}-x_{2i}\|^{p}}\right)^{1/p}$	Euclid, Manhattan, Chebyshevを一般化したもの
Chebyshev	チェビシフ	$\max_{i}\|x_{1i}-x_{2i}\|$	成分の差がもっとも大きい次元だけを抽出している
Mahalanobis	マハラノビス	$\sqrt{\mathbf{ \left( x_{1}-\bar{x} \right)^{T} S^{-1} \left(x_{2}-\bar{x}\right)}}$	正規分布の共分散の形にあわせて算出する距離。よく使う
Hellinger	ヘリンジャー	$\sqrt{ \sum_{i}^{n} {\left(\sqrt{x_{1i}}-\sqrt{x_{2i}}\right)^{2}} }$	外れ地の影響を受けにくいの
Hamming	ハミング	$dim(\mathbf{x})-\sum_{i}^{n}\delta\left( x_{1i},x_{2i} \right)$	ベクトルの要素中で一致していない要素数。カテゴリ変数に利用

分布の距離

分布の距離というときにもいろいろな距離/距離尺度がある。厳密には距離の公理(非負性・同じ点なら0・対称性・三角不等式が成り立つ)*4を満たしていないものもあり、それらは距離とはいえないが、差をあらわすものとしてよく使われるものなので、距離尺度として用いられる。

名前	式	備考(あれば)
Histogram Intersection	$D_{HI}(p,q) = \sum_i \mathrm{min}(p,q)$	(距離じゃなくて類似度)ヒストグラムのような離散値に使う。2つの分布の共通領域。
KL divergence	$D_{KL}(p\|\|q) = \int_{-\infty}^{\infty}p(x)\log{\frac{p(x)}{q(x)}}dx$	相対エントロピーの概念に基づいて、2分布間の距離を算出(非対称)
JS divergence	$m(x) = \frac{p(x)+q(x)}{2}$ $D_{JS}(p,q) = \frac{D_{KL}(p\|\|m)+D_{KL}(p\|\|m)}{2}$	KLを改良して** $p,q$ に対称性をもたせたもの
L1 norm	$D_{L1}(p,q) = \int_{\infty}^{\infty}\|p-q\|dx$	連続的な分布における誤差の絶対値の和
L2 norm	$D_{L1}(p,q) = \int_{\infty}^{\infty}(p-q)^2dx$	連続的な分布における二乗誤差の和
Wasserstein distance	$W_p(\mu, \nu)=\left( \inf_{\gamma\in \Gamma \left(\mu,\nu\right)} \int_{M\times M} d(x,y)^{p}d\gamma(x,y) \right)^{1/p}$	分布を荷物量とみなし、荷物を他の分布に移しかえるときにかかるコスト

それぞれの違いの実装をgithubにあげておく(day23)

github.com

wasserstein計量

物理では昔からある輸送距離だが、WGANの登場により、分布の距離表現として注目される様になってきた。

輸送コスト最小化問題を解いた場合の最小の輸送コスト

最小コストをいちいち計算するため、計算時間はめちゃくちゃかかるが、その分物理的にも本質的な距離になっている。

実装にはPOTというライブラリを使う(Optimal Transportation)github

pip install Cython
pip install POT

Earth Mover's Distance *5の説明(直感的にわかりやすい)
Wasserstein GANの記事(Wasserstein距離の細かな説明アリ)
Wassersteinで機械学習
WassersteinGANのPyTorch実装

カーネル(再生核ヒルベルト空間)

非線形の問題を扱うものとしては、かなり伝統的な手法。数式を抜いて文字だけで説明するとこんな感じ

線形の特徴量 $x_1,x_2$ を組み合わせて、非線形な特徴量を作りたい。

こんな特徴量の組み合わせは無数にある(例: $x_{1}^2, x_1x_2,...,x_{1}^{4}x_{2}^{3}$ ,...)

多いほど非線形性は高まるが、組み合わせが膨大

カーネル関数を使うと、無限次元の特徴ベクトルを用いているのと等価*6

でも、計算量は無限じゃなくて、データ数に依存する*7

一般的化線形モデルは、カーネル関数によって書き換えることが出来るので、データ数に依存する形で非線形を学習できる