HELLO CYBERNETICS

深層学習、機械学習、強化学習、信号処理、制御工学、量子計算などをテーマに扱っていきます

【多様体学習】LLEとちょっとT-SNE

人工知能 人工知能-機械学習

　

　

follow us in feedly

f:id:s0sem0y:20170706073834p:plain

 

 

多様体学習の必要性

クラスタリングという観点

データ\bf x_i \in \mathcal R^DがD次元空間にプロットされる際には、データに意味があれば、似たようなデータは近い位置に現れることが期待できます。そのような考えに基づいて、K平均法などによってデータをクラスタリングすることが可能になります。

 

s0sem0y.hatenablog.com

 

しかし、実際には似たようなデータが必ずしもD次元空間上で近い位置に現れるとは限りません。例えば以下のようなデータがあったとしましょう。色が近いほど、本来は似ているデータだとします。

 

f:id:s0sem0y:20170706073723p:plain

 

3次元空間上に、データが配置されています。赤色は中心にまとまっていますが、青や緑はいろんなところに広がってしまっています。こういうデータに対してK-平均法などを使ってクラスタリングを行っても実りのある成果は得られないでしょう。

 

それでも何らかの法則によってデータは空間上に配置されると考えられます。何とかその法則らしいものを取り出す方法があれば嬉しいはずです。そして、多様体学習はこのようなケースに対して上手い解を与えてくれることが期待できます。

 

次元削減という観点

機械学習やデータ解析では次元削減という手法が必要になります。次元削減は高次元のデータを可視化するために3次元未満に落としたり、あるいはデータを機械学習に用いる際に不要な成分を落としてしまう際に用いられます。

 

特に一番有名なのが主成分分析（Principal Component Analysis:PCA)で、実装も単純であるため、多くの場面で活用されます。他にも独立成分分析(Independent Component Anaysis:ICA)も有名です。

 

これらの基本的アイデアは高次元データ{\bf x_i} = (x_1,\cdots,x_D) \in \mathcal R^Dの各成分を

 

x' = a_1x_1 + a_2x_2 + \cdots + a_Dx_D

 

と線形結合することで、もっと上手い成分x'が得られないか、というものです。上手い成分は複数あってもよく、上記のように線形結合を何個か考えれば

 

\bf x' = Ax

 

と表すことができます。あとは行列Aを上手く決めたいというものです。

 

s0sem0y.hatenablog.com

 

これらの方法はあくまで、線形変換によって上手い成分を見つけたいというものです。従って\bf xは空間上で拡大・回転を行われるに過ぎません（あるいは座標系の方を回転していると見ても良い）。

 

そうして取り出されたd (\leq D)個の成分が良い成分であるかは場合によります。例えば分類問題の特徴量として用いたい場合に置いては、分離が上手くできるような部分空間だけを取り出せたかが重要です。

 

そのようなケースに置いて、例えば以下のような3次元空間のデータ（実はこれはさっきのものと同じ）に対して、線形変換による手法を用いてもあまり役に立ちません。PCAやICAでデータを2次元データへ次元削減することは、2次元平面を好きな角度で置いて、そこにデータを射影するということです。どんな上手い平面を置いても、データがぐちゃぐちゃに混ざってしまうでしょう。

 

f:id:s0sem0y:20170706073834p:plain

 

しかも今は、あくまで3次元のデータを扱っているため、線形ではダメそうだと目で見て判断できます。しかし通常のデータはそういうわけにもいかないため、更に判断が難しくなります。

 

多様体とは

多様体とは簡単に言えば、局所的に見たら線形空間で表すことのできるような空間になります。

 

以下のデータは3次元空間に存在はしていますが、本質的には2次元なのです。なぜならば、長方形がくるくると丸められているだけであり、局所的に見たら単なる平面に過ぎないからです（地球は丸いが、人間の小ささからには地平に見える）。

 

f:id:s0sem0y:20170706073834p:plain

 

従って、このデータは3次元空間に埋め込まれた2次元多様体であると言います。

 

多様体学習の狙い

先ほど、K-平均法が上手く使えないのではないかと言いました。実際、2次元多様体が埋め込まれた先ほどの画像では、「赤とオレンジの距離」と、「赤と黄緑の距離」を3次元空間上で比較した場合、（色は本来前者が似ているにも関わらず）後者の方が近くなっています。

 

しかし、実際には赤とオレンジの方が近いデータです。仮に先ほどの画像が、カラーになっておらず、全く情報が無いとしましょう。そうだとしても、普通は一繋がりになっているということに着目したくなるはずです。

 

遠くても一繋がりになっている方が近いと考えるやり方があっても良く、まさに多様体学習はそのような方法を与えてくれます。

 

まず、基本的に「一繋がりになっている」ことを意識するのは、データに沿って曲線的に距離を図っているからです。そうすれば赤とオレンジはかなり近い位置にあると言えます。これはデータを多様体だと捉えるということに相当します。つまり曲がった座標をデータに沿って構築しているということです。

 

以下は曲がった座標をデータ上に配置し、その座標を新たに縦軸と横軸にして散布図を描いたものです。言い換えるとこれは、曲がった座標を考えてから、その座標を真っ直ぐにしてデータもろとも連れて来てしまうということです。

 

f:id:s0sem0y:20170706074059p:plain

 

\bf x \in \mathcal R^Dはあくまで人間がデータ集める方法によって、座標が決まってしまいます。データの持つ本質的な座標を取り直すのが多様体学習というわけです。

 

 

ところで曲がった座標を立てるということは、言わばPCAやICAのような真っ直ぐな座標を空間上に良い角度で配置し直すことの進化版だと捉えることもできます。曲がった座標を配置し、それを引き伸ばして真っ直ぐにするというのは、すなわちデータに対して非線形変換を行っているに他なりません。

 

 

 

多様体学習の例

Locally Linear Embedding(LLE)

多様体学習の狙いを最も如実にしている例がこのLLEという手法だと思います。

LLEは以下によって定式化されます。

 

 

１．たくさんのデータの点の中から、とあるデータ\bf xに対してK最近傍を選出する。

 

\bf xのK最近傍とは\bf xに近いK個のデータのことを言います。ここで近さはユークリッド距離で測ります。以後、このK最近傍で得られたデータ集合を\mathcal Kと書きます。

 

2.\mathcal Kに属するデータ集合{\bf x_j} \in \mathcal Kの線形結合

 

\displaystyle \sum_j w_{j} {\bf x_j} = w_1{\bf x_1} + w_K{\bf x_K}

 

を考え、この線形結合により得られるベクトルと\bf xの二乗距離を表す関数を作ります。

 

\displaystyle \left| {\bf x} - \sum_{{\bf x_j} \in \mathcal K} w_j {\bf x_j} \right|^2

 

これが小さくなるようにすれば、最近傍のデータで\bf xを表現できるということになります。

 

3.今はとあるデータ\bf xについて行ったが、全てのデータ\bf x_iに対して上記の関数を作ります(データ点\bf x_iごとに最近傍を選出し直すので、その集合を\mathcal K^{(i)}と書くことにする)。

 

\displaystyle \left| {\bf x_i} - \sum_{\bf {x_j} \in \mathcal K^{(i)}}  w^{(i)}_{j} {\bf x_j} \right|^2

 

それぞれのデータ点が、ごく少数の近傍のデータ点の線形結合で表せるということは、局所的に線形空間と見ることが可能になります（つまり多様体になっていそうだということ）。

 

4.そこで各データの近傍での再構成誤差の和

 

\displaystyle E({\bf W}) = \sum_{i=1}^N \left| {\bf x_i} - \sum_{\bf {x_j} \in \mathcal K^{(i)}} \ w^{(i)}_{j} {\bf x_j}\right|^2

 

を最小化するようなw^{(i)}_jを求めます。すなわちデータが多様体になっているのであれば局所的な線形空間を考えられるはずであり、そうであれば局所的な線型結合の再構成誤差の和は小さくなるはずであると考えるのです。言わば、こいつを最小化することで多様体になっていることを要請しているというわけです。

 

ただし、\sum_j w^{(i)}_j = 1という制約を与えます（ベクトルの線型結合の係数の和が1である場合、それを特別にアフィン結合という。アフィン結合は座標原点をどこに取っても良いという性質があり、データの相対的な位置関係のみを表現する）。

 

添字の数を考えれば行列を用いて計算式を以下の形にできます。

 

\displaystyle E({\bf W}) = \sum_{i=1}^N \left| {\bf x_i} - \sum_{j}  W_{ij} {\bf x_j}\right|^2

 

ここでW_{ij}は行列{\bf W} \in \mathcal R\{N \times N} のi,j成分です。各点の線型結合を考えるのなんて面倒なので、その係数たちを行列に格納したということです。ただしこの時、\bf Wのi行目に関して\mathcal K^{(i)}に含まれないj列目の成分を予め0で埋めておきます（なぜなら近傍でないデータは線型結合で使わないから）。これにより\bf Wはスパースな行列になります。

 

 

5. d \leq Dの{\bf y} \in \mathcal R^dを考え

 

\displaystyle L({\bf W}) = \sum_{i=1}^N \left| {\bf y_i} - \sum_{j} W_{ij} {\bf y_j}\right|^2

 

を最小化する\bf y_iを求めます。Wは高次元空間でのデータの局所的な位置関係を保存しており、適当な低次元空間の点y_jに係数W_{ij}を掛けて和をとることによって局所的な位置関係を保って、低次元で復元できます（注意、これはあくまでベクトルを線形結合しているものであって、行列演算ではない）。ただし、データは局所的な位置関係のみを手が掛かりに再構成されるため、その絶対値に意味を見出すのは難しくなります。

 

以下はLLEの結果です。 

元々がこれ

 

f:id:s0sem0y:20170706073834p:plain

 

元々の空間で近かったものは、同じように近い場所に配置されています。まさに多様体を取り出してきた結果になっています。

 

f:id:s0sem0y:20170706073908p:plain

 

※

しかし、次第に潰れる形になってしまっている。この問題は入力の次元数よりも近傍の数が多い場合に起こる。今回は３次元データに対して近傍を１２個選んでいるので起こりうる問題だ。データ点は１５００点のため、これに比べ近傍は十分少なく、局所的に線形であるとはみなせるだろう。しかし、３次元のベクトルを表現するときに線形空間で１２個の基底を選べばそれは不定問題となる（解が一意に定まらない）。そこで普通は正則化項を入れてミニマムノルム問題に持ち込む。解は一意に定まる代わりに、再構成を歪ませる結果となる。

 

※

Kを大きく取り過ぎると、近傍じゃないものまで線型結合に参加してしまう。その重みが再構成に使われるわけだが、局所的に線形と見なせないデータまでK近傍で拾ってしまうともっとおかしなことになる。

 

※

局所的な位置関係しか保たないと言っても、それを少しずつずらしながら行っているため、赤はオレンジとの位置関係を考慮し、オレンジは黄色との位置関係を考慮する（実際はもっと細かく刻まれているが）。結果として、赤と青が一番離れているというグローバルな情報も残る。

 

 

※

LLEは最適解が保証されている(ただしKはハイパーパラメータ)。そういう意味では逐次最適化を用いる必要がなく、機械学習という感じではないかもしれないが、一応機械学習の一種(そんなこと言い出したら主成分分析は機械学習じゃなくなるがな)。

最適解とは損失関数を最小化するという意味であって、そもそも仮定が間違っていたら、つまらない最適解が得られるだけである（例えばデータがそもそも多様体でない場合＝局所的に見ても線形ではない）。

 

 

他の多様体学習の紹介

Modified Locally Linear Embedding

f:id:s0sem0y:20170706074059p:plain

冒頭で見せました以下の画像は、LLEの改良版である Modified Locally Linear Embeddingと呼ばれる手法です。見事に歪みを修正することに成功しています。

 

 

 

t-distributed Stochastic Neighbor Embedding

f:id:s0sem0y:20170706075024p:plain

これは確率分布によって多様体学習を行うユニークな方法です。データ点x_i,x_j同士の親和性を同時分布p(x_i, x_j)で表現します。そして低次元空間に対しては、スチューデントt分布で復元します。学習にはKLダイバージェンスを用い、低次元空間と高次元空間で（確率分布の観点で）近い位置に復元されるようになります。

 

この手法は、グローバルな情報を一切保持できません。

 

代わりに、ローカルな情報に非常に忠実であり、データ空間に多様体が複数ある場合でも上手く動作します。（LLEは一繋がりになっていないと上手くいかない。低次元空間でデータが原点中心に寄ってくる傾向がある。）

 

例えば、MNISTでは10個の手書き数字を使いますから、データ空間（784次元）に全てのデータを置いたら、10個の多様体があると考えられます。

そういった場合にデータ空間に複数存在する個々の多様体を取り出すことが期待できるため、クラスタリングに直結します。

 

TensorBoardのEmbeddingのチュートリアルでも利用されている手法です（素晴らしく上手くクラスタリングしています教師なしであることが信じられない程です）。

 

TensorBoard: Embedding Visualization  |  TensorFlow

 

 

多様体学習の発展版

私自身も昨年、以下の記事で存在を知りました。TDA（位相的データ解析）という手法は、多様体学習の発展版とも言えます。

 

qiita.com

 

つい最近もqiitaに更新があった模様。

 

qiita.com

 

多様体学習では、データの局所的な構造を見る際の、局所的な範囲が問題になります（LLEならKがそれにあたる）。これを大きく取り過ぎると線形ではない場所で線形と仮定することになりますし、小さすぎると上手く構造が見出だせなくなります。

 

位相的データ解析では局所的に見る範囲は、解析の中で変動させながら同時に済ませてしまっています。また、対象が局所的に線形だと嬉しいという前提も特に無くなります。（多様体という概念は微分幾何学へ発展する分野だが、多様体から距離の構造とか微分とか色々なものを取り除いたのが位相幾何学です。微分可能とは接平面を考えられる＝局所的に線形ということであり、そういう概念自体がそもそもありません）

 

 

 

 

最後に

ディープラーニング以外の手法もたまには見てみると面白いと思います。

 

今回の分野は私自身もまだ勉強できていない状態ですが、データ解析や機械学習をやる上では、ディープラーニングは選択肢の１つに過ぎなく、他の多くの手法について理解していたほうが良いと思います。というより、絶対そうであるべきだと個人的には思っています。

 

 

多様体に関する基本知識を抑えられるように以下の記事を書きました。

是非ご覧になってください。

s0sem0y.hatenablog.com

 

s0sem0y

スポンサーリンク

コメントを書く