プロクラシスト

今日の寄り道 明日の近道

【注目記事】 Pythonでゼロから機械学習/データ分析を学ぶためのサイトマップ

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

advent-calendar-2017

スポンサーリンク

f:id:imslotter:20171223191319p:plain

データ分析ガチ勉強アドベントカレンダー 23日目。

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

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

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

"正しい"というのは、データ分析に使うのに適切なのか。という意味で書いている。 たとえば、新宿まで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

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

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

  • 線形の特徴量x_1,x_2を組み合わせて、非線形な特徴量を作りたい。
  • こんな特徴量の組み合わせは無数にある(例:x_{1}^2, x_1x_2,...,x_{1}^{4}x_{2}^{3},...)
    • 多いほど非線形性は高まるが、組み合わせが膨大
  • カーネル関数を使うと、無限次元の特徴ベクトルを用いているのと等価*6
  • でも、計算量は無限じゃなくて、データ数に依存する*7
  • 一般的化線形モデルは、カーネル関数によって書き換えることが出来るので、データ数に依存する形で非線形を学習できる

というわけで、データ数分の計算量で、無限次元空間の学習が出来るって感じ。 注意としては、入力するデータ数が多くなると、計算が厳しくなる(データ数×データ数の逆行列を解く)

以下、わかりやすい&数式もきちんと載っている説明。

Topological Data Analysis(TDA)

  • データを点群として扱うのでなく、データの持つ幾何学的な情報に基づいて識別や分類を行う
  • Persistent Homologyという分野
  • 点群の幾何学的な情報を抽出した二次元座標上の点集合(Persistence diagram)ã‚’å¾—ã‚‹
f:id:imslotter:20171223123208p:plain
persistent homologyの生成元の発生と消滅のイメージ
f:id:imslotter:20171223123233p:plain
上図のように円を広げていき、発生の時刻と消滅の時刻を2次元プロットにしたのがpersistent diagram

以下、わかりやすい説明と論文

次元削減/Embedding

特徴量が非常に多い場合、その特徴量全てがデータとして重要かどうかは微妙。 特徴量を重要な部分だけ抽出したり(Dimension Reduction) 相性の良い空間へ今ある雑多なデータを埋め込んだり(Embedding)することが多い。以下は主要/有望な手法と簡単な説明、文献を列挙する(随時更新)

PCA(principal component analysis)

典型的な次元削減の方法。次元を落としても情報をなるべく落とさないような軸を計算で求める。

ちなみに、AutoEncoderはPCAの純粋な拡張になりうることが数学的に証明できる *8

t-SNE(t-Distributed Stochastic Neighbor Embedding)

PCAが点だけを見るのに対し、t-SNEは分布単位で見る。圧縮前と圧縮後の確率分布のKLダイバージェンスを最小化することにより求める。

f:id:imslotter:20171223125426p:plain
[t-SNEの仕組み(ALBERT)](https://blog.albert2005.co.jp/2015/12/02/tsne/)より引用

Word2Vec

CBoW(Continuous Bag-of-Words)を用いて、文脈中の単語から対象単語が現れる条件付き確率を最大化するように学習を進めていく。

そうすることで、単語を座標空間上に埋め込むことができる。 これによって、言葉の足し算引き算ができる可能性が拓けた。

f:id:imslotter:20171223191909p:plain
男女間の関係が近い値のベクトルで表現される(参考記事より画像を引用)

最近では、word2vecだけではなくdoc2vecなどもあり、ますます応用可能性が増している。

Poincare Embeddings

Word2Vecの空間改良版といったところ。双曲空間にデータを埋め込むことで、

  • 階層構造/木構造を自然に空間の中に埋め込める。そういう構造のデータに良い。
  • リッチな空間表現のため、元の次元を減らすことも出来る
  • 空間に少しの補正を加えるだけで使えるので、拡張が容易

な点などから、注目されている。双曲空間というのは、下図真中のような、曲がった空間。外に行くほど密になっている(=空間が広い)

f:id:imslotter:20171223192945p:plain
[Fig]双曲空間。場所によって距離尺度が変わる

実際、単語は階層構造をなすことが多く、下図の結果のように、空間上に効率よく単語を配置することができる。

f:id:imslotter:20171223193551p:plain
[Fig] 論文の実験結果、ハブと周辺語の階層関係が表せている

Wasserstein Embeddings

この前読んだ論文が、Wasserstein空間が作る距離上の空間に埋め込むというものだった。

LEARNING WASSERSTEIN EMBEDDINGS

まとめると

  • wassersteinは計量として優秀。分布の差をうまく表す。
  • でも計算重い。だいたい次元の３乗の計算量
  • うまく近似する関数をディープラーニングで作ろう
  • 近似にはSiamese networkが有効そうだから学習して関数を作る
  • うまく近似できた。理論的裏づけが課題。

使ったのはSiamese network。距離学習によく使われる。

f:id:imslotter:20171223194521p:plain

２つのネットワーク\phi,\psiを用意して、パラメータの更新は

  • \phiで変換されたベクトル同士のの二乗誤差と、Wasserstein距離の差を近づけるように
  • \psi\phi(x)とxの誤差(再構成誤差)を小さくするように

行う。今後、リッチな空間で、計算量がネックになる場合は、このようにニューラルネットで空間の計量を近似するような手法が主流になるかもしれない*9

まとめ

今日は、かなり基礎的な内容になった。 個人的には、このレベルでの新しいアルゴリズムが今後出てくるのではないのかなと思っている。基礎的なところからの変更は、ドラスティックな変革を引き起こすことが多いので。今後も随時追っていきたいと思う。

いよいよあと２日。明日は、これで本サイトで書いてきたデータ分析/機械学習に関する内容を総まとめしたいと思う。必見です！ではでは。

【Advent Calendar】
  • 前の日 : 【Day-22】データ分析技術で仮想通貨の暴騰・暴落を捉えられるか
  • 次の日 :

    • *1:空間、計量、測度論...ムリ...

    *2:極座標を除く

    *3:マンハッタン距離

    *4:長くなるので割愛。詳しくはこちら

    *5:物理用語ではこういう。

    *6:証明

    *7:リプリゼンタ定理という

    *8:深層学習 (機械学習プロフェッショナルシリーズ)などを参照

    *9:と、個人的に注目している

    imslotter

    関連記事
    スポンサーリンク


    PROCRASIST をフォローする
    '); $(".shwbtn").click(function(){ var $this = $(this); if($Contents.css('display') == 'none'){ $Contents.slideDown(400), $this.text("目次を隠す"); }else{ $Contents.slideUp(400), $this.text("目次をみる") }; }); });
    コメントを書く

    PROCRASIST