データ分析ガチ勉強アドベントカレンダー 23日目。
ここまでデータをどういう風に処理したり、どういうタスクをこなしていくかについて勉強してきたが、 一度基礎的な事項に戻ってみたいと思う。基礎だから簡単というわけではない。基礎だからこそ難しく、また本質的な内容。
データ分析で使われている手法などをまとめて集約して、簡単な説明を付け加えていく。 しかし、このあたりの数学*1は苦手なので、なるべく直感的に自分のイメージを書いていく。
- われわれが生きている空間や、距離は"正しい"のか
- 点の距離
- 分布の距離
- カーネル(再生核ヒルベルト空間)
- Topological Data Analysis(TDA)
- 次元削減/Embedding
- まとめ
われわれが生きている空間や、距離は"正しい"のか
"正しい"というのは、データ分析に使うのに適切なのか。という意味で書いている。 たとえば、新宿まで1.2km"というような表示を見る。地球という座標空間の中で、新宿までの距離が1.2kmというわけだ。われわれは日常生活の中で、それに対して何の疑問も抱かない。それは、日常の距離はユークリッド空間が 大前提にあるからである。
ユークリッド空間/ユークリッド距離
簡単に言うと、高校まで*2われわれが生きてきた空間である。たとえば、(0,0)から(3,4)までの距離は?ときかれると、大体の人は三平方の定理だ!となって、5という数字が思い浮かぶ。
けれど、下図を見てほしい。空間が必ずしもx,yの直交座標であらわされるわけではない。厳密に言うと、地球は丸いので、曲がった空間での距離を求めるべきなのである。また、距離の測り方だってバリエーションがあっていいはずだ。 ユークリッド距離といえば、斜辺の距離と思いがちだが、たとえば街などは、斜めに横切れないことだってあるので、かくかくと進んでいくことを前提に距離を測ったりする*3。このように状況によって空間や測りかたは変わるべきなのである。
データ分析とは、いろいろなジャンル/いろいろなタスクがあるわけで、それが本当にユークリッド空間/ユークリッド距離で考えるべき話題なのかどうかというのは、考えておくべき問題なのである。 非常に根本的な話であるだけに、きれいな空間や距離で解けたものは美しく、汎用性がある。
点の距離
Name | 名前 | 式 | 備考(あれば) |
---|---|---|---|
Euclid | ユークリッド | 一般的な距離 | |
Manhattan | マンハッタン | 外れ値の影響を受けにくい | |
Minkowski | ミンコフスキー | Euclid, Manhattan, Chebyshevを一般化したもの | |
Chebyshev | チェビシフ | 成分の差がもっとも大きい次元だけを抽出している | |
Mahalanobis | マハラノビス | 正規分布の共分散の形にあわせて算出する距離。よく使う | |
Hellinger | ヘリンジャー | 外れ地の影響を受けにくいの | |
Hamming | ハミング | ベクトルの要素中で一致していない要素数。カテゴリ変数に利用 |
分布の距離
分布の距離というときにもいろいろな距離/距離尺度がある。厳密には距離の公理(非負性・同じ点なら0・対称性・三角不等式が成り立つ)*4を満たしていないものもあり、それらは距離とはいえないが、差をあらわすものとしてよく使われるものなので、距離尺度として用いられる。
名前 | 式 | 備考(あれば) |
---|---|---|
Histogram Intersection | (距離じゃなくて類似度)ヒストグラムのような離散値に使う。2つの分布の共通領域。 | |
KL divergence | 相対エントロピーの概念に基づいて、2分布間の距離を算出(非対称) | |
JS divergence | KLを改良して**に対称性をもたせたもの | |
L1 norm | 連続的な分布における誤差の絶対値の和 | |
L2 norm | 連続的な分布における二乗誤差の和 | |
Wasserstein distance | 分布を荷物量とみなし、荷物を他の分布に移しかえるときにかかるコスト |
それぞれの違いの実装をgithubにあげておく(day23)
wasserstein計量
物理では昔からある輸送距離だが、WGANの登場により、分布の距離表現として注目される様になってきた。
- 輸送コスト最小化問題を解いた場合の最小の輸送コスト
- 最小コストをいちいち計算するため、計算時間はめちゃくちゃかかるが、その分物理的にも本質的な距離になっている。
- 実装にはPOTというライブラリを使う(Optimal Transportation)github
pip install Cython pip install POT
- Earth Mover's Distance*5の説明(直感的にわかりやすい)
- Wasserstein GANの記事(Wasserstein距離の細かな説明アリ)
- Wassersteinで機械学習
- WassersteinGANのPyTorch実装
カーネル(再生核ヒルベルト空間)
非線形の問題を扱うものとしては、かなり伝統的な手法。数式を抜いて文字だけで説明するとこんな感じ
というわけで、データ数分の計算量で、無限次元空間の学習が出来るって感じ。 注意としては、入力するデータ数が多くなると、計算が厳しくなる(データ数×データ数の逆行列を解く)
以下、わかりやすい&数式もきちんと載っている説明。
Topological Data Analysis(TDA)
persistent homologyの生成元の発生と消滅のイメージ
上図のように円を広げていき、発生の時刻と消滅の時刻を2次元プロットにしたのがpersistent diagram
以下、わかりやすい説明と論文
- 位相的データ解析と3D画像認識 - ニンゲンメモ
- Statistical Topological Data Analysis - A Kernel Perspective
- データ科学への 機械学習的アプローチ(統数研:福水健次)
次元削減/Embedding
特徴量が非常に多い場合、その特徴量全てがデータとして重要かどうかは微妙。 特徴量を重要な部分だけ抽出したり(Dimension Reduction) 相性の良い空間へ今ある雑多なデータを埋め込んだり(Embedding)することが多い。以下は主要/有望な手法と簡単な説明、文献を列挙する(随時更新)
PCA(principal component analysis)
典型的な次元削減の方法。次元を落としても情報をなるべく落とさないような軸を計算で求める。
ちなみに、AutoEncoderはPCAの純粋な拡張になりうることが数学的に証明できる *8
t-SNE(t-Distributed Stochastic Neighbor Embedding)
PCAが点だけを見るのに対し、t-SNEは分布単位で見る。圧縮前と圧縮後の確率分布のKLダイバージェンスを最小化することにより求める。
[t-SNEの仕組み(ALBERT)](https://blog.albert2005.co.jp/2015/12/02/tsne/)より引用
- t-SNE(Slideshare)
- LLEとちょっとT-SNE
- PCAとの性能差がわかる TSNE vs PCA | Kaggle
Word2Vec
CBoW(Continuous Bag-of-Words)を用いて、文脈中の単語から対象単語が現れる条件付き確率を最大化するように学習を進めていく。
そうすることで、単語を座標空間上に埋め込むことができる。 これによって、言葉の足し算引き算ができる可能性が拓けた。
男女間の関係が近い値のベクトルで表現される(参考記事より画像を引用)
最近では、word2vecだけではなくdoc2vecなどもあり、ますます応用可能性が増している。
Poincare Embeddings
Word2Vecの空間改良版といったところ。双曲空間にデータを埋め込むことで、
- 階層構造/木構造を自然に空間の中に埋め込める。そういう構造のデータに良い。
- リッチな空間表現のため、元の次元を減らすことも出来る
- 空間に少しの補正を加えるだけで使えるので、拡張が容易
な点などから、注目されている。双曲空間というのは、下図真中のような、曲がった空間。外に行くほど密になっている(=空間が広い)
[Fig]双曲空間。場所によって距離尺度が変わる
実際、単語は階層構造をなすことが多く、下図の結果のように、空間上に効率よく単語を配置することができる。
[Fig] 論文の実験結果、ハブと周辺語の階層関係が表せている
- 異空間への埋め込み!Poincare Embeddingsが拓く表現学習の新展開
- PythonでPoincare embeddingsを使う(gensim)
- 原論文: Poincaré Embeddings for Learning Hierarchical Representations
Wasserstein Embeddings
この前読んだ論文が、Wasserstein空間が作る距離上の空間に埋め込むというものだった。
LEARNING WASSERSTEIN EMBEDDINGS
まとめると
- wassersteinは計量として優秀。分布の差をうまく表す。
- でも計算重い。だいたい次元の3乗の計算量
- うまく近似する関数をディープラーニングで作ろう
- 近似にはSiamese networkが有効そうだから学習して関数を作る
- うまく近似できた。理論的裏づけが課題。
使ったのはSiamese network。距離学習によく使われる。
2つのネットワークを用意して、パラメータの更新は
- で変換されたベクトル同士のの二乗誤差と、Wasserstein距離の差を近づけるように
- との誤差(再構成誤差)を小さくするように
行う。今後、リッチな空間で、計算量がネックになる場合は、このようにニューラルネットで空間の計量を近似するような手法が主流になるかもしれない*9
まとめ
今日は、かなり基礎的な内容になった。 個人的には、このレベルでの新しいアルゴリズムが今後出てくるのではないのかなと思っている。基礎的なところからの変更は、ドラスティックな変革を引き起こすことが多いので。今後も随時追っていきたいと思う。
いよいよあと2日。明日は、これで本サイトで書いてきたデータ分析/機械学習に関する内容を総まとめしたいと思う。必見です!ではでは。