Generalized Autoencoderのメモ

# [Generalized Autoencoder: A Neural Network Framework for Dimensionality Reduction](http://openaccess.thecvf.com/content_cvpr_workshops_2014/W15/papers/Wang_Generalized_Autoencoder_A_2014_CVPR_paper.pdf)

* Wang et al, 2014, CVPR2014 workshop paper
* 個人用メモ．図と数式が抜けています．



## abst 

* Generalized Autoencoderを使って多様体学習するアルゴリズム．
* AEのようにデータ自身の復元ではなく，データxiからxjを復元する
* 得られるデータ多様体で定義される関数で，xiとxjの再構成誤差が重み付けられる
* 3データセットで評価し，promissingな結果

## conclusion

* denoising AEはノイズ付きから画像を復元する．GAEはデータの近傍にある同一クラスの崩壊したデータから復元するとみることが出来る．今後はこの両者を比較する．
* GAEは大量のラベルの情報を利用できる

## 1. intro

* PCAは線形次元削減であり，最大分散方向にデータを射影するが，データ間の関係は考えない．
* LDA, Marginal Fisher Analysis (MFA)はクラスラベルを，データの関係情報として低次元separating部分空間をさがすのに使う．
* データの関係を抽出することは背後の構造を見つけるのに有用．
    * ex.ISOMAP, LLEではデータ点は周辺の線形結合となり，射影先の低次元空間でも線形関係が保持される，Laplacian Eignemapは元の空間での距離に応じて重み付けられたペアごとの距離を最小化することでて異次元空間を見通す．
    * **これらみな，[out-of-sample](https://stats.stackexchange.com/questions/260899/what-is-difference-between-in-sample-and-out-of-sample-forecasts/261594)問題に対応できない．**
    * これらは局所的なデータの関係を利用しているが，関係は固定されており，元の高次元空間で定義されている．そのような関係は多様体上で有効とは限らない
        * ex. 多様体上の最近傍との測地線距離は元の空間のユークリッドによる最近傍とは異なる
* AEは次元削減の特殊型で，再構成誤差を最小化する圧縮された表現を学習する．intrinsic data structureを含む”意味のある特徴”を学習できる．が，dataの**関係**は無視している
* 多様体構造を追求するため，データの関係を繰り返し探索する，AEを拡張した多様体学習を提案する．Generalized AEで行う．
    * GAEはデータxiの圧縮表現yiを学習し，それを利用してxiと他のデータ{xi, xk ...}の間の関係を，xiそのものではなく集合の中のほかの要素(xk, x....)を再構成するために学習する．
    * GAEは関係の重みs_ijを再構成誤差||xj - x'i||^2に適用する．ゆえに重み付き再構成誤差を最小化することでデータ空間の構造を捉える．
    * GAEのsigmoid関数を線形変換に変えることで，その線形GAEとlinear graph embedding[19]は同様の目的関数を持っていることを示す．
        * これはGAEが再構成集合と重みを定義することによる次元削減の一般的なフレームワークであることを示す．
        * 6種類のGAEを実装し，複数レイヤに拡張したdeepGAE(dGAE)も提案する．
* 2. GAEの式, graph embedingとの関係，GAEを次元削減のフレームワークとして提案，２.3でdGAE，
* 3. 実験結果
* 4. 議論と結論


## 2. Dimensionality Reduction by Manifold Learning 

### 2.1. The method 

* algorithm 1 が提案手法．
    * (1)データのペアごとの距離・類似度を元の高次元空間で計算し，relation/reconstruction 集合Omega_iを各データ点xiに関して決める．たとえばk-nearest neighborsで．(データ関係の初期化)
    * (2) 各データ点付近の局所多様体構造がGAEを使ってその再構成集合から学習される
    * (3) 学習された多様体上で，データ関係は隠れ表現によって定義されたペアごとの類似度，距離に応じて更新される．
    * 移行２，３をくりかえす

### 2.2

* GAEの構造はAE同様
    * (2)式で，デコーダのW'行列がエンコーダの行列Wの転置W^Tでもよいと書いてある
    * データ点xiに対して，圧縮表現はyiと書き，再構成表現はx'iで書くg, fは活性化関数(線形再構成の場合はidentity, or binary 再構成の場合はsigmoid)
* データの関係をモデル化するため，decoderは特定の重みSi= {sij, sik, ...}で，Omega = {j,k,...}でindexされたデータを再構成する．
    * 重み付き再構成誤差は(3)式 e_i(W, W')= sum_{j in Omega_i}{s_ij L(x_j, x'_ i)}
        * Lは再構成誤差(線形再構成の場合は２乗誤差，binary 再構成の場合はcross-entropy)
    * トータルの再構成誤差Eはｎ個のサンプルで(3)を足した(4)式，GAEはこのEを再消化しながら(W, W')を学習する

### 2.2.1 connecion to Graph Embedding

* Graph embeddingは，各データが低次元ベクトル中のグラフノードとして表現される次元削減の一般的フレーム．グラフのエッジはデータペア間の類似度を保持している．
    * 類似度はデータ分布の統計量，または構造的な特性を特徴づける．グラフ埋め込みの式は(5)
        * y* = arg min_{y^T By =c}{sum_i,j sij ||y_i - y_j||^2}
            * s_ijは頂点iとjの類似度で，s_ij = sjiが一般的．(対称性を満たす)
            * cは定数，Bは自明な解を避けるための定数行列
* 線形グラフ埋め込み(LGE)は線形写像y=X^T wにより低次元表現が得られることを仮定している．ここでwは射影ベクトルで，X=[x_1, x_2, ..., x_n]
    * 目的関数は(6)
        * w* = arg min_{w^T XBX^T w=c, or w^T w =c} sum_{i,j}{s_ij ||w^T x_i - w^T x_j||^2}
        * 同様に，GAEの隠れ表現は，d_y < d_x(圧縮表現のほうが元の空間より次元数が少ない)の時データの低次元多様体を含む．ここでデータ間の関係/類似度/距離は他のデータを再構成するデータを通して定義される
        * 2,1,4式より，トータル再構成誤差Eは(7)
            * (W, W')* = argmin sum_{i,j}{s,j ||x_j - f(W'g(Wxi))||^2}
                * 線形再構成の場合，W' = W^Tでありnetwork中に一つしか隠れノードを仮定しない，つまりdy=1の場合，Wは列ベクトルｗに縮退する．目的関数(7)は(8)になる
                    * w* = argmin sum_{i,j} s_ij ||x_j - ww^T x_i||^2
                * w^Tw=c, y_i = w^T x_iとすれば，(8)は(9)になる
                    * w* = argmin_{w^T w = c}sum_{i,j}{s_ij}(||w^T x_i -w^T x_j||^2 + (c/2 - 1)y_i^2)
* LGEの(6)と比べて，GAEはcを変えて隠れ表現yをコントロールする調整項が余分にある．c=2の時，GAEはLGEと類似の目的関数，c>2ならwのノルムが大きくなったとしてもyが大きくなりすぎることを防ぐ．ｃ＜２ならwが小さい時でもyが大きくなるようにする
* 上記のモデルの線形番はGAEとグラフ埋め込みのconnectionを示す．実用的には，GAEのg()は表現能力がほしいので非線形にする


### 2.2.2 GAEの変種の実装

* 上記の解析からわかるように，GAEは異なる再構成集合と重みを定義する一般的な次元削減フレームワークとなることができる
    * 次に，6個の実装を示す(PCA, LDA, ISOMAP, LLE, LE, MFAからインスパイアされている)

#### GAE-PCA

* GAE-PCA: 入力x_iがそれ自身を再構成する．w^Tw=1の制約．式(8)は(10)になる
    * 平均０のPCAの式である．また，NNで実装した場合はAEと全く同じものになる．

#### GAE-LDA

* GAE-LDA: 入力x_iが自身と同じクラスからきたすべてのデータを再構成するのに使われる．つまりj in Omega_{c_i}で，Omega_{c_i}はx_iが属するクラスc_iのインデックス集合．重みs_{ij}はクラスc_iのサンプルサイズn_{ci}に逆比例する．s_{ij}=1/n_{ci}．
    * １次元の線形GAE-LDAは式(9)に従う．GAE-LDAは通常のLDAのような次の２つの制約に従う必要ない．
        * (1) 各クラスのデータはガウス分布に従う
        * (2) 射影の次元数はクラス数より少ない

#### GAE-ISOMAP

* すべてのデータXを再構成するためにxiが使用される．すべてのデータペアに対するD_Gを測地線距離とする．
* 重み行列S= -H Lambda H/2とする
    * H=1-1/n e e^T
    * e次元の1ベクトル(?)
    * Lambda_ij=D_G^2(i,j)である
    * １次元線形GAE-ISOMAPは式9．

### GAE-LLE 
    
* xiがそのk-最近傍を再構成するため，またxi除くするその他の入力のk最近傍を再構成するために使用される．(LLE同様，あるデータはその最近傍で表現するから)．
    * つまりN_k(i)をx_iのk近傍のindex集合として，j in {N_k(i), N_k(m)m, m}である．もしすべてのmについて，i in N_k(m)，ならばj neq i である．
    * Mを局所再構成係数行列として，sum_{j in N_k(i)}， M_{ij}=1で，j not in N_k(i)の場合は M_{ij}=0(最近傍に対応するところを足すと１になり，そうでない部分は０)．
    * この重み行列はもしi neq jならS_ij=(M+M^T - M^T M)_ {ij}であり，それ以外は0
    * 一次元の線形GAE-LLEは式(9)に従う

### GAE-LE

* x_iはk最近傍を再構成するのに使用される．つまり j in N_k(i)．再構成重みはs_ij = exp{-||x_i - x_j||^2 /t}，ここでtは調整パラメータ．目的関数があたえられた時，LEは式(5)．


### GAE-MFA

* xiはその同じクラスのk_1-最近傍を再構成するのに使用される．また，その他のクラスのk_2-最近傍にも使用される．
    * つまり，もしj in Omega_{c_i}^{k_1}なら，s_{ij} =1 であり，もしj in Omega_{c_i}^{k_2}なら，s_{ij}=-1である．ここでOmega_{c_i}^{k_1}はx_iのk_1-最近傍のindex集合であり，Omega_{k_2}(c_i)はその他すべてのクラスにおけるx_iのk_2-最近傍のindex集合．(クラスラベルと，データ点間の距離の両方を利用している)．
    * MFA同様，正の再構成はクラス内コンパクトさを特徴づけ，負の再構成はクラス間の分離度を特徴づける

* 再構成集合のsummaryを表１に示す．
* クラスラベルをGAE-LE(or GAE-LLE)に導入して，x_iと同じクラスのk-最近傍を選ぶと，教師ありGAE-LE(or 教師ありGAE-LLE)を得る


## 2.3. Deep Generalized Autoencoder

* ディープに拡張してもっと複雑なデータセットを扱う．deep generalized autoencoder(dGAE)
    * enc, decともにdeep(複数レイヤ)．これらは低次元表現について(を中心として)対称．
        * 図２を参照．
    * 重みの初期値を良いものにするため，レイヤごとにpretrainした．[5]．200binary featureの最初の隠れレイヤをpretrainするとき,入力層でのreal-valued face dataは，ガウス分布でモデルされる．
        * 最初の隠れ層と，inputレイヤはGaussian restricted boltzmann machineとしてモデリングされる
    * ２番めのレイヤを100個のreal-valued featureで事前訓練した．最初の隠れレイヤは二番目の隠れそうの入力．
        * 最初と２番めの隠れレイヤは他のGRBMを構成するために結合される(図２)．
            * これらの２つのGRBMはcontrastive divergenceを使って効率的に訓練される
* pretrain後，enc, dec両方についておもみ{W_i}_ {i=1,2}を得る．
    * 全体の再構成誤差(4)の微分をBPしてさらにfine tuneしていく．
        * 図2は同じクラスの別の顔を再構成するGAE-LDAのfine-tune手順を示す

## 3. 実験結果

* GAEの応用を２つ見る．一つは顔認識，もう一つは数字分類
    * 最初に，GAEによる多様体学習の効果とその拡張を見る


### 3.1 データセット

* ３つのデータで実験．
    * face dataset F1，グレースケール，ビデオから取った，20x28px，
    * CMU PIE face database ，68名の被験者，41368画像，32x32px，ポーズ，照明，表情を変えている
    * MNIST 28x28，
        * 6つのGAE実装のうち，いくつかの再構成重みについて考える
            * GAE-ISOMAPのgeodesic deistanceは，datasetが大きいと計算時間がかかるので，10,000画像をランダムに選んだ．
        * 各数字のうち，500が訓練で500がtest    

### 3.2 多様体学習

* 一般に，高次元実数データは低次元空間に潜んでいると考えられる．顔画像や手書き数字のように．
    * 先行研究同様，GAEは効率的な非線形多様体構造の発見ができる[15][1][12]
* まず，繰り返し学習中に，データのｋ近傍の変化をチェックすることで，GAEの多様体構造の発見能力を調べる．
    * fig3はCMU PIE datasetでのGAE-LEの学習に関して，最初の２０iterationの間で顔の18近傍の変化を示す．
    * 色ボックスの中にある顔は別人のもの．
        * 色は人を特定する
        * 結果より，iterationごとに，顔の近傍はその自身のクラスに収束する．また同じ人物の顔に収束する，同じような照明が動く場合．
    * 訓練中のdatasetでの18最近傍の平均"不純度"の変化を計算する．
        * 不純度は18近傍に別のクラスから来たデータの割合として定義される．
        * 図4は最初の20iterationでの不純度が減少していく状況を示す．
            * GAEが学習するごとに類似する近傍を発見できている．
* 加えて，異なるモデル(LPP, dGAE-PCA, dGAE-LE, )で，F1データセットでのmanifold learningの結果を比較する．(dGAE-PCA and dGAE-LEのみ示す)
    * visualizationのため，face images を学習された二次元多様体空間にmapする
    * どちらの手法もsize(20x28)-200-2のレイヤサイズで，decoderも対称．
    * 2D manifold は図5．点の隣に代表する顔が示される．
        * データ点の分布は放射状である．
        * 放射軸と角dimensionにそって，表情とポーズがなめらかに変わる．
* ２つのunsupervised手法（LPP, dGAE-LE）と４つの教師あり手法(MFA, LDA, dGAE-MFA, dGAE-LDA)で学習されたMNISTの2D data manifoldを示す．図6
    * 10個の数字のデータ点は異なる色とシンボルで示される．３つの提案手法(d-GAExxxのこと)はレイヤサイズ(28x28)-1000-400-250-2 のencoderと対称なdecoderを使っている．
        * LPP, MFA, LDAの場合は異なる数字がひどく重なっている
        * 一方，提案手法では区別できている．
        * さらに，クラスラベルを使用すると，dGAE-MFA, dGAE-LDAからのクラスタは(使用していない)dGAE-LEよりも区別できる．


### 3.4. 数字分類への応用

* GAEの性能をさらに評価するため，MNISTの数字を分類する
    * 784次元のraw dataを入力する
    * deep GAEでは，encoder layersは784-500-200-30のサイズ，
    * 顔認識実験と同様の手順を使い，manifold dimensionは30にした．
* 表３は14個の手法の分類結果．
    * baselineはraw dataでの最近傍分類器，error rateは6.5%
        * (1): このデータでは，提案手法がほかより優れている
        * (2): ベースラインよりは優れているが，他の８手法よりは優れていない．
            * GAEがデータ関係を繰り返し探索することで，もっと妥当な多様体構造を発見できるかもしれないことを示す．
        * (3): kernel PCAのエラー率(8.5%)とPCA(6.2%)から，kernelの拡張は常に改善をもたらすわけではなく，適したkernel関数を見つけることはkey issueである．
            * しかし，多層NN構造のために，提案手法は**universal approxiation property[6]**があり，もっと複雑なデータ構造を捉えられる．