機械学習とかコンピュータビジョンとか

CVやMLに関する勉強のメモ書き。

Clustering with Deep Learning: Taxonomy and New Methodsを読んだのでメモ

はじめに

Clustering with Deep Learning: Taxonomy and New Methodsを読んだのでメモ.

気持ち

DNNベースのクラスタリング手法について体系的にまとめて定式化することで,システマティックに新しいクラスタリングの方法を作れる様にしようというもの.

モデル構造

多くのDNNのクラスタリング手法は入力データクラスタリングしやすい表現(潜在表現)に落とし込むための"main branch"が存在する.そのためのモデルには従来以下の5つのモデルが使われる.

  • Multilayer Perceptron (MLP)

  • Convolutional Neural Network (CNN)

  • Deep Belief Network (DBN)

  • Generative Adversarial Network (GAN)

  • Variational Autoencoder (VAE)

各々の説明は割愛.

潜在表現

クラスタリングしやすい表現を得る際の方法としてmain branchの最後の表現のみを得る場合と複数の層から得る場合の2種類に分けられる.

  • One layer

 利点としては次元が低いこと.主に最終層の表現が使われる.

  • Several layers

 利点としては表現がリッチであること.

Non-clustering loss

Non-clustering lossはクラスタリングとは関係のない損失項で正則化項の様な役割として用いられる.以下の選択肢がある.

  • No non-clustering loss

Non-clustering lossを使わない(正則化なし).局所解にハマりやすいという点が指摘されてるがたまにいい結果をもたらす場合もある.

  • Autoencoder reconstruction loss

Decoderを使った再構成誤差.入力と再構成されたデータ間の距離を損失項とし一般的には平均2乗誤差.再構成に必要なデータの重要な情報を残した潜在表現を得られることが保証される.

  • Self-Augmentation Loss

元のデータとaugmentationされたデータ間の表現の類似性を保証する.次のような関数で表される.

\displaystyle
L=-\frac{1}{N}\sum_Ns(f(x),f(T(x)))

xが元のデータでTがaugmentationの関数.f(x)は潜在表現への変換でsは類似度でcross-entropy等.

  • Other tasks

学習データに関する追加情報の項.クラスや属性ラベルが使える場合など.

Clustering loss

クラスタリング手法に依存した損失項.一番重要な部分で以下のような様々な方法が存在.

  • No clustering loss

Non-clustering lossのみを使う方法.次元圧縮等の目的で使われる.基本的にclustering lossがあった方が良い結果となる.

  • k-Means loss

K-Meansしやすい表現を獲得するための損失.データ点がクラスタ中心の周りに分布するような表現を得る方法で次のような損失関数で定義.

\displaystyle
L(\theta)=\sum_{i=1}^N\sum_{k=1}^Ks_{ik}| z_i-\mu_k|^2

z_iはデータ点の潜在表現で\mu_kクラスタ中心.s_{ik}は所属クラスタを表すboolean(普通はone-hot?).

  • Cluster assignment hardening

データ点をクラスタにソフトに割り当てる損失.1例として次のstudentのt分布を元にした関数を使ってソフトな割り当てを行う.

\displaystyle
q_{ij}=\frac{(1+| z_i+\mu_j|^2/\nu)^{-\frac{\nu+1}{2}}}{\sum_{j'}(1+| z_i+\mu_{j'}|^2/\nu)^{-\frac{\nu+1}{2}}}

\nuはハイパーパラメータの定数.データ点の潜在表現とクラスタ中心間の正規化された類似度となっていてクラスタの所属確率としてみなせる.Cluster assignment harging lossは上記の確率が一つのクラスタのみに大きくなるように強いる損失で,そのために次の補助分布を導入する.

\displaystyle
p_{ij}=\frac{p^2_{ij}/\sum_iq_{ij}}{\sum_{j'}(q_{ij'}^2/\sum_iq_{ij'})}

この補助分布と正規化された類似度によって表現される分布間のKLダイバージェンスを損失とする.

\displaystyle
L=\sum_i\sum_jp_{ij}\log\frac{p_{ij}}{q_{ij}}

  • Balanced assignment loss

他の損失と同時に用いられ,クラスタ間の大きさのバランスをとる.各クラスタの大きさ(所属するデータ点の量)はある程度均一であるという仮定から成り立ち,次のKLダイバージェンスとして表現できる.

\displaystyle
L_{ba}=D_{KL}(G| U)

Uは一様分布でGクラスタの大きさに関する分布で次のように定義される.

\displaystyle
g_k=P(y=k)=\frac{1}{N}\sum_iq_{ik}

当然データに偏りがある場合は成り立たず,クラスタサイズに何かしらの事前知識がある場合には一様分布を別な分布に置き換えることもできる.

  • Locality-preserving loss

元の表現での位置関係のようなものを保存するように強いる損失.データ点x_ik近傍集合に対し近傍のデータ点の類似度s(x_i,x_j)を使って次のような損失関数を定義する.

\displaystyle
L_{lp}=\sum_i\sum_{j\in N_k(i)}s(x_i,x_j)| z_i-z_j|^2

  • Group sparsity loss

隠れユニットがクラスタG個に分けられるという仮定を置いたもので,データ点x_iの潜在表現は{\phi^g(x_i)}_{g=1}^GのようにG個の表現として与えられ,group sparsity lossは次のような損失関数として定義される.

\displaystyle
L_{gs}=\sum_{i=1}^N\sum_{g=1}^G\lambda_g|\phi^g(x_i)|

{\lambda_g}_{g=1}^G\lambda_g=\lambda\sqrt{n_g}で定義される重み.ただしn_gはグループサイズ.

  • Cluster classification loss

後述のcluster updateの間に得られるクラスタの割り当て結果をクラスラベルとしてclassification lossに使うというもの.

  • Agglomerative clustering loss

類似度が最も高いクラスタをstopping criterionが満たされるまで統合していき,統合されたクラスタ間の類似度を最適化するような手法.クラスタリングに適した表現が得られる.

損失の組み合わせ方

Clustering lossとnon-clustering lossは次のように組み合わされる.

\displaystyle
L(\theta)=\alpha L_c(\theta)+(1-\alpha)L_n(\theta)

L_c(\theta)はclustering lossでL_n(\theta)はnon-clustering loss.\alpha\in[0;1]は二つの関数のバランスをとるハイパーパラメータ.\alphaの決め方には次のような選択肢がある.

  • Pre-training, fine-tuning

まず\alpha=0として学習した後,\alpha=1とする方法.場合によっては結果を悪くすることもある.

  • Joint training

0\lt\alpha\lt 1として学習する方法.

  • Variable schedule

\alphaを変数と見て,学習中に変化させていく方法.例えば\alphaを初期では小さくして徐々に大きくしていくなど.

基本的に\alpha=1\alpha=0も欠点がある.

クラスタの更新

大雑把にクラスタリングは階層的なものとクラスタ中心に基づく手法に分けられる.学習段階でクラスタの割り当て結果が(クラスタ中心に基づく方法においてはクラスタ中心も)更新されていく.その更新の仕方は一般的に次の二つどちらか.

クラスタの割り当て結果は確率として定義され,ネットワークのパラメータとして定義され逆伝播によって最適化される.

クラスタの割り当て結果は決定的でネットワークのパラメータ更新とは別に更新される.この場合にはさらに次の二つの更新方法がある.

・Number of iterations

クラスタの割り当て結果が固定されるまで繰り返す方法

・Frequency of updates

ネットワークがP回更新されるたびに割り当て結果を更新する方法

学習後

学習終了後,仮に学習過程でクラスタ結果が得られたとしていても,次の理由から学習された特徴を用いて再びクラスタリングし直すのが一般的.

  • Clustering a similar dataset

獲得された潜在表現の一般生を評価するため別なデータで検証すべきというもの.

  • Obtaining better results

ある特定の状況下においては学習過程で得られたクラスタ結果よりも良い結果が得られる場合があるというもの.

関連研究

以下に載せた論文の表1に従来手法が論文の分類に合わせてまとまっている. f:id:peluigi:20180918190536p:plain

New method

手法を項目ごとに分けて,従来手法を表1のようにまとめることで簡単に分析ができて,手法の組み合わせで課題に適した新しいアルゴリズムを組むことが可能というのが主張.実際そのようなアプローチで組み立てた手法のクラスタリング結果が図3,4に記述されていて良く機能しているように見える.

まとめ

サーベイでも手法提案でもない新しい論文の書き方を見た気がする.読みやすく綺麗にまとまったいい論文だった.

Spherical Latent Spaces for Stable Variational Autoencodersを読んだのでメモ

はじめに

Spherical Latent Spaces for Stable Variational Autoencodersを読んだのでメモ.VAEのKL collapse(latent variable collapse)をpriorに\kappa固定のvon Mises-Fisher分布 (vMF) を使う事で回避するというもの.

論文自体は自然言語に寄って書かれていて自分は興味ないので簡潔に

von Mises-Fisher VAE

Von Mises-Fisher分布(vMF)は\mathbb{R}^d空間の超球上での分布で方向ベクトル\mu,\:||\mu||=1と集中度パラメータ\kappa\geq 0を持つ.vMFのPDFは次の様に定義される.

\displaystyle
f_d(x;\mu,\kappa)=C_d(\kappa)\exp(\kappa\mu^Tx)\\ \displaystyle
C_d(\kappa)=\frac{\kappa^{d/2-1}}{(2\pi)^{d/2}I_{d/2-1}(\kappa)}

ただし,I_vは第1種ベッセル関数.

priorとして\mathrm{vMF}(\cdot,\kappa=0)を使い,変分事後分布としてはq_\phi(z|x)=\mathrm{vMF}(z;\mu,\kappa)を使う.ただし,\muはencoderの出力,\kappaは定数として定める.以上からVAEのevidence lower boundにおけるKL項は次の様になる.

\displaystyle
KL(\mathrm{vMF}(\mu,\kappa)||\mathrm{vMF}(\cdot,0))=\kappa\frac{I_{d/2}(\kappa)}{I_{d/2-1}(\kappa)}+\left(\frac{d}{2}\right)\log\kappa-\frac{d}{2}\log(2\pi)-\log I_{d/2-1}(\kappa)+\frac{d}{2}\log\pi+\log 2-\log\Gamma\left(\frac{d}{2}\right)

別な論文のAppendixに丁寧な証明があったので導出は省略.この式は\kappaのみに依存していて,\kappaが定数であることからKL項はfixとなりKL collapseを起こさなくなるという主張.自分の理解が間違ってなければ学習はreconstractionのみで行われるのでその辺りどうなのか.一応\kappaを変えた時のKLの値をプロットして簡単な考察をしてたけども.

vMFからのサンプルは,"change magnitude"と呼ばれるwをrejection samplingによりサンプリングし,超球上のmuに接する単位ベクトルvをサンプリングすれば,z=w\mu+v\sqrt{1-w^2}として得ることができる.

まとめ

KL項が固定になるというのがとても気持ち悪い気がするけど実験ではそれなりにうまく行ってるっぽい.

Realistic Evaluation of Semi-Supervised Learning Algorithmsを読んだのでメモ

はじめに

Realistic Evaluation of Semi-Supervised Learning Algorithmsを読んだのでメモ.

気持ち

データを作るコストが高いことからsemi-supervised learning (SSL)は重要で,最近はそれなりのラベルデータがあればsupervisedに匹敵する性能がでる.ただ,実世界の設定に対してSSLはちゃんと機能するのかというのがこの論文が問題として提案しているところ.そこで実世界の課題に対してSSLアルゴリズムが機能するかを評価可能な新しい実験方法を提案するという論文.実験を行う上で実際以下の様な発見があったとのこと.

・同一構成のモデルに対してラベル有りのみを使った場合とラベルなしも使った場合の性能差が報告よりも小さい.

・強力な正則化をかけてラベル有りのみで学習された分類器の性能はSSLアルゴリズムを評価する上で重要.

・異なるデータで学習されたモデルをラベル有りのみでfine-tuneした分類器は全てのSSLアルゴリズムより性能がよかった.

SSLの性能はラベルなしデータがラベル有りデータと異なる分布のデータを含む場合に劇的に下がる.

・アプローチごとにラベル有りとラベルなしデータの量に対する性能の感度が違う.

・Varidationデータが少ないと比較結果の信頼性がない.

いくつかは当たり前な様な気もするが,こう言ったことがあるからこの論文では実験方法とともに全てのいろんなstate-of-th-art SSL手法を再実装して評価できる様にしたものも提供するとのこと(現時点ではgithubリポジトリはあるがコードは公開されてない).

Improved Evaluation

一般的なSSLの評価方法は,教師あり学習のためのデータセットのラベルを一部を除いて捨ててラベル有りデータ\mathcal{D}とラベルなしデータ\mathcal{D}_{UL}に分け,このデータを使って学習した後にテストデータで評価するというもの.この時,使うデータセットとラベル有りデータの数が論文によって異なるため正確な比較ができていない.主に以下の6つの項目が実問題にかけ離れているとして,これに着目して実験/評価方法を整備する.

P.1 A Shared Implementation

SSLの比較に使われる元となるモデル構造を共通化する.というのも,従来は単純な13層のCNNを異なる実装(異なるパラメータの初期化方法やデータの前処理,正則化,最適化方法など)で使っていて,ちゃんと比較できているとは言えないため.

P.2 High-Quality Supervised Baseline

SSLの目的は\mathcal{D}だけの学習に比べて\mathcal{D}\mathcal{D}_{UL}を組み合わせた学習による精度向上.このベースラインとなる\mathcal{D}だけで学習したモデルが論文によって学習の具合が違っていて,同じ条件のはずが別々の論文のベースラインを比べると最大15%程の差があるとのこと.そのため,ベースラインとSSLのチューニングにかかる計算量を同一にしようというもの.

P.3 Comparison to Transfer Learning

限られたラベル有りデータで学習する際の有効な手法として転移学習があり,これと比較しないのはおかしいだろというもの.

P.4 Consider Class Distribution Mismatch

従来の実験設定では,データセットラベルを捨てて\mathcal{D}_{UL}を作るため,\mathcal{D}_{UL}\mathcal{D}に含まれるデータと同じクラスのデータを持つ.ただ,実世界の設定においてはそうなるとは限らない.つまり,例えば10種類の識別をしたい際に,ラベルなしデータの中に識別したい10種類とは違うクラスのデータが混ざっている場合がある.なので実問題に対する評価をするためには\mathcal{D}\mathcal{D}_{UL}が異なるクラスの分布を持つ時の影響も調べる必要がある.

P.5 Varying the Amount of Labeled and Unlabeled Data

今までは\mathcal{D}\mathcal{D}_{UL}の比率を決める体系的な方法なしで比較していたが,実問題においては\mathcal{D}_{UL}がめちゃくちゃ巨大(ネットから大量に集まる自然画像で作られている)か,比較的小さい(医療データなど)の2種類に分けられる.そのためアルゴリズムごとのデータ数による性能の変動を比較すべき.

P.6 Realistically Small Validation Sets

SSLの実験の設定ではValidationデータが非常に多い.というのも,例えばSVHNデータセットを使った実験では学習用のラベル有りサンプルは1000程度に対し,Varidationデータは元のまま7000サンプルを使う.これの問題は,実問題ではこんな大きなVaridationデータは用意できず,Varidationデータを使ったパラメータのチューニング等は不可能だということ.たとえcross-validationをしたとしても不十分な上計算コスト的に厳しいと論文では主張.

Semi-Supervised Learning Methods

この論文で使うSSL手法のざっくりとした復習.

Consistency Regularization

Consistency regularizationはRealisticな摂動をデータに加えても出力は変わらないだろうという前提に基づいた手法.元のデータをx,摂動が加えられたデータを\hat{x}とすると,d(f_\theta(x),f_\theta(\hat{x}))の最小化問題として記述され,d(\cdot,\cdot)はMSEやKLダイバージェンスが使われる.これはデータが分布する多様体が滑らかであるという仮定に基づいていて,この考えは様座mなSSLに応用されている.

Stochastic perturbations/\Pi-Model

Consistency Regularizationの最も単純な設定は,f_\theta(x)が確率的な出力をだす,つまり同一の入力xに関して異なる出力を出すというもの.これはデータ拡張やdropoutなどのことで,この時の出力が元のデータを入力した際と変わらない様にd(f_\theta(x),f_\theta(\hat{x})),\mathcal{D}_{UL}正則化項としてつけるというのがこのモデル.これはregularization with stochastic transformation and perturbations,\Pi-Modelとして同時に提案されていて,ここでは\Pi-Modelの呼称を使う.

Temporal ensembling/Mean teacher

\Pi-Modelの課題として,不安定なターゲット(f_\theta(x)が変化するということ)を推定するところにある.そこでより安定したターゲット\bar{f}_\theta(x),x\in\mathcal{D}_{UL}を得る方法が提案された.一つはTemporal Ensemblingでf_\theta(x)移動平均の様なものを代わりとして使おうというもの.もう一つはMean Teacherで学習中の学習パラメータ\theta移動平均的なもので定義された関数で推定された値を使おうというもの.

Virtual adversarial training

f_\theta(x)を確率的なものにする代わりに,出力に大きな影響を及ぼす微小な摂動r_{adv}を近似して直接xに加えることで学習しようというのがVirtual adversarial trainig (VAT).摂動r_{adv}は次の様に効率的に計算できる.

\displaystyle
r\sim\mathcal{N}\left(0,\frac{\xi}{\sqrt{\mathrm{dim}(x)}}I\right)\\ \displaystyle
g=\nabla_rd(f_\theta(x),f_\theta(x+r))\\ \displaystyle
r_{adv}=\epsilon\frac{g}{||g||}

ただし,\xi,\epsilonはハイパーパラメータ.consistency regularizationはd(f_\theta(x),f_\theta(x+r))\thetaについて最小化するときに適用される.

Entropy-based

\mathcal{D}_{UL}に適用される単純な損失項は情報量を下げる(つまりカテゴリカル分布を考えたときにどこか一つのクラスが尖る)というもの.出力がsoftmax関数を通して得られた[tex]K]次元のベクトルとすればentropy minimization項は次の様に表現できる.

\displaystyle
-\sum_{k=1}^Kf_\theta(x)_k\log f_\theta(x)_k

ただこの方法はモデルの表現力が高いと簡単に過学習する.ただVATと組み合わせることで有用な結果を生んでいるとのこと.

Pseudo-labeling

Pseudo-labelingはヒューリスティックな手法だが,その単純さと適応範囲の広さから実際には広く使われている.Pseudo-labelingはあらかじめ設定された閾値を超える確率を持つクラスを正解のクラスとして\mathcal{D}_{UL}に擬似ラベルをつける方法.ただ,推定関数が役に立たないラベルを生成してしまった際には性能を悪化させる.ただ,pseudo-labelingはentropy minimizationと似た様な性質をもち,

Experiments

P.1

P.1の課題を解決するためにモデルと最適化方法の統一をした.モデルにはWide ResNetを,特に,一般的に使われているtensorflow/modelsのリポジトリにある"WRN-28-2"を使ってAdamによる最適化をした.あとは基本的な正則化とデータ拡張,前処理もしたらしい.ベースラインとSSLに関してgoogle cloud machine learningを使ったハイパーパラメータチューニングサービスを使って"Gaussian Process-based black box optimizationを1000回走らせて各アルゴリズムごとにハイパーパラメータを最適化したとのこと.

P.2

これはP.1の結果解決されて良いベースラインが作れたとのこと.実際他の文献で報告されているほどベースラインの精度は悪くない結果となった.ただ,現在提案されてる様々な正則化やデータ拡張をするとstate-of-the-art SSL手法並みに精度が出るとの事.

P.3

WRN-28-2を32x32にリサイズしたImageNetで学習したものをCIFAR-10で転移学習して比較したとの事.論文で実験した結果最も良いSSLであるVAT+EMのエラー率が13.13%に対し転移学習したものは12.0%だったそう.ただし,ImageNetに含まれるカテゴリはCIFAR-10とモロ被りしているのでこれはかなり恵まれた条件だったと論文には記載されている.後,転移学習とSSLを組み合わせても実験するのはfuture work.

P.4

クラスのミスマッチを扱うためにCIFAR-10の6クラス分類(bird, cat, deer, dog, frog, horse)をしたとの事,ラベルなしはその他4クラスを含む(分類の6クラスを含むかは微妙.The unlabeled data comes from four classesと書いてあったから多分含まない)ものとして,ラベル有りと無しのデータの比率を変えて実験.結果ラベルなしがある一定の割合を超えたらSSLより単純な教師ありが勝った.

P.5

ラベル付きのデータ数を変えた場合,ラベルなしのデータ数を変えた場合でSSL手法の比較をした結果,アルゴリズムごとに違う振る舞いでいい発見だったという感じ.

P.6

当たり前だけどVaridationデータの数を少なくしたら評価時の分散も大きくなったという結果.

まとめ

SSLに関する問題提起の論文.避けてきた点をつくいい論文だけどgoogleの宣伝感がすごい.githubで公開するとのことだけど使うにはtensorflow使う必要があるのと(よくわからないが)同一条件で自分のアルゴリズムを試そうとしたらgoogleのパラメータチューニングサービスを使う必要がありそう.

Appendixに探索したハイパーパラメータがまとまってるのでSSLする際には役に立ちそう.

Graph Convolutional Neural Networks for Web-Scale Recommender Systemsを読んだのでメモ

はじめに

Graph Convolutional Neural Networks for Web-Scale Recommender Systemsを読んだのでメモ.30億ノード,180億エッジを持つグラフデータに対しても処理可能なrandom walkに基づくgraph convolutional neural network (GCN),PinSageを提案するというもの.

問題設定

今回扱うデータはPinterestのデータで,Pinterestはユーザーが興味のあるコンテンツ(画像)を自分のboard上にpin留めしたり他人のboardにpin留めされているデータを自分のボードにpin留めすることで交流するSNSとのこと(自分は使ったことないのでよくわからないが).データとしては20億のpinと1億のboardと180億のエッジがあるらしい.

問題としてはpinの推薦のためにpin \mathcal{I}とboard \mathcal{C}からなるPinterestの環境をモデル化することでpinの表現学習を行いたいというもの(ただし提案手法は一般化され他手法で適用範囲はPinterestに限らない).ここでの推薦というのはあるユーザーがpinしたコンテンツを,興味が近いユーザーに提示してpinしてもらうこと.つまりpinと表現しているのはpinされた画像u\in\mathcal{I}を表し,そこには実数値x_u\in\mathbb{R}^dが割り当てられる.

以下,表記の一般化のためグラフのノード集合を\mathcal{V}=\mathcal{I}\cup\mathcal{C}としてpinとboardの区別をしない.

model architecture

Forward propagation algorithm

ノードuの埋め込みベクトル\mathbf{z}_uuとその近傍のノードから生成することを考える. 基本的なアプローチとしてはノードuの近傍のノードの埋め込みベクトル\mathbf{z}_\mathcal{v}|\mathcal{v}\in\mathcal{N}(u)をノードごとにニューラルネットワークに入力した後,ReLU等の非線形関数を噛ませてプーリングにより一つのベクトルを作り出す.得られたベクトルとノードuの埋め込みベクトル\mathbf{z}_uをconcatしてニューラルネットに入力して非線形関数を噛ませたのち,L2正規化して新たな埋め込みベクトル\mathbf{z}_u^{\mathrm{NEW}}を得るというもの.つまり一つのノードの埋め込みベクトルを得るのに二つのNNを使うということ.

Importance-based neighborhoods

このアプローチの重要となる点の一つとして,どの様に近接のーど\mathcal{N}(u)を定義して,前述のforward propagationにおける近接ノードの集合をどの様に選択するかということにある.一般的にはk-hopなどの方法が取られていたが,PinSageはノードuに最も影響するであろうT個のノードで定義する.最も影響するT個のノードはrandom walkで訪れた回数の多い上位T個のノードとして定義する.

この選び方はノード数が固定となることと,forward propagationで変換された近傍ノードのプーリング処理を行う際にL1正規化された訪れた回数を重みとして重み付き平均をとることができるという二つの利点がある.特にこの後半のプーリング処理をimportance poolingとして提案する.

Model training

モデルの学習はmax-margin ranking lossを使った教師あり学習で行ったとのこと.ラベルはitem iとquery item qのペアの集合(q,i)\in\mathcal{L}で定義されていて,このペアの埋め込みベクトルが近くなることが学習の目標.

目的関数は次の様に表され,この最小化問題はquery itemの埋め込みベクトル\mathbf{z}_qがポジティブペア(ラベルペア)のアイテムの埋め込みベクトル\mathbf{z}_iとの内積が大きくなる様に,逆にネガティブペアの埋め込みベクトル\mathbf{z}_{n_k}との内積が小さくなる様にする.

\displaystyle
J_\mathcal{G}(\mathbf{z}_q\mathbf{z}_i)=\mathbb{E}_{n_k\sim P_n(q)}\max\{0,\mathbf{z}_q\cdot\mathbf{z}_{n_k}-\mathbf{z}_q\cdot\mathbf{z}_i+\Delta\}

P_n(q)はアイテムqのネガティブサンプルの分布で,\Deltaはハイパーパラメータ.いわゆるtriplet lossのユークリッド距離をコサイン距離的なものにした感じ.

その他論文には巨大なデータで学習する際のいろいろな問題と解決方法を述べていたが割愛.

まとめ

データが巨大すぎて企業ならではな研究だなと.発表された会議の性質もあってアルゴリズムよりも実装面をかなり頑張った感じがあった.

Fixing a Broken ELBOを読んだのでメモ

はじめに

Fixing a Broken ELBOを読んだのでメモ.

気持ち

教師なし表現学習の一般的なアプローチとしてデータをp(x,z|\theta)=p(z|\theta)p(x|z,\theta)ので表現される様な潜在変数モデルにフィットさせる方法があげられる.通常はこのモデルを真の分布とのKLダイバージェンスL(\theta)=\mathrm{KL}[\hat{p}(x)||p(x|\theta)]を最小化する様に学習することでデータの潜在表現を獲得する.ただ,このKLダイバージェンスはほとんどの場合扱いにくく,代わりとしてevidence lower bound (ELBO)を最大化することでモデルの学習を行う.ただ,根本的な問題として,目的関数L(\theta)=\mathrm{KL}[\hat{p}(x)||p(x|\theta)]p(x|\theta)に関する式であってp(x,z|\theta)に関する式にはなってないため,不自然な目的関数になっていることがあげられる.実際先行研究の結果からも言えて,ELBOが良い表現学習をするためには十分でないことがわかっている.そこでここでは観測Xと潜在表現Z相互情報量Iの側面から良い表現を導出するというのが話の流れ.以前に読んだモントリオール大の論文でも相互情報量を使った表現学習手法を提案していたが論文の次期的にはこちらが先.

相互情報量による表現学習

ここでの目標は確率的なエンコーダーe(z|x)を使って観測データxを意味のある潜在表現zに変換すること.ただしエンコーダーは同時分布p_e(x,z)=p^\ast(x)e(z|x),周辺分布p_e(z)=\int dxp^\ast(x)e(z|x),条件付き分布p_e(x|z)=p_e(x,z)/p_e(z)で表現される.この表現の良し悪しを測る指標として次の相互情報量を用いる.

相互情報量はある確率変数がもう一方の確率変数の情報をどれほど持つかを測る指標で次の様に計算される.

\displaystyle
I_e(X;Z)=\int\int dxdzp_e(x,z)\log\frac{p_e(x,z)}{p^\ast(x)p_e(z)}

相互情報量X,Zが独立の場合0(エンコーダーはデータの情報を一切持たない状態)になり,またZ=Xの場合はXエントロピーH(X)エンコーダーはデータの情報の全てを持つ状態)になる.

課題となるところは相互情報量の計算式に真の分布p^\ast(x)が含まれていて計算が困難なことと,周辺分布を求めるための周辺化の演算p_e(z)=\int dxp_e(x,z)の計算が困難なこと.前者は経験分布\hat{p}(x)に置き換えることで,後者は相互情報量のvariational boundsを使うことで回避できる.相互情報量の下界と上界は次の様に定められる.

\displaystyle
H-D\leq I_e(X;Z)\leq R\\ \displaystyle
H\equiv-\int dzp^\ast(x)\log p^\ast(x) \\ \displaystyle
D\equiv-\int dxp^\ast(x)\int dze(z|x)\log d(x|z) \\ \displaystyle
R\equiv\int dxp^\ast(x)\int dze(z|x)\log\frac{e(z|x)}{m(z)}

d(x|z)はいわゆるデコーダーでp_e(x|z)を近似する役割をし,m(z)はmarginalと呼ばれp_e(z)を近似する役割をする.Hはデータのエントロピーでデータセットの分布具合を測る役割をするが,データセットの操作はできないので定数.Ddistortionと呼ばれ,いわゆる再構成の良し悪しを測る項.Rは比率(rate)と呼ばれ,エンコーダーとmarginalのKLダイバージェンスの平均を表している.データが離散の場合にはH,D,Rは全て非負の値をとる.

D=0はデータを完璧にエンコードしてデコードすることができる(再構成できる)という状態で,これをauto-encoding limitと呼ぶ.そのauto-encoding limitでもっとも小さいRHによって与えられる.つまりR=H,D=0の状態であり,この状態はd(x|z)=p_e(x|z)であることから下界がタイトであることを表す.逆にm(z)p_e(z)をうまく近似できていない場合,Rは大きな値をとり,m(z)Rにしか関係がないため単純にコストが大きくなっている状態を表す.

R=0RがKLダイバージェンスであることからe(z|x)=m(z)であることを表し,e(z|x)xに独立であることを意味する.したがってエンコーダーはデータの情報を全く表現できておらず,表現学習が失敗していることを表す.このとき,十分強力なデコーダーを用意すればzxが独立でも無理やり再構成を行うことができるため,Dは下界であるデータのエントロピーHまで下げることができる.これはR=0,D=Hの状態を表していて,これをauto-decoding limitと呼ぶ.Rが固定値でDが大きな値をとる場合にはd(x|z)Dとしか関係ないため単純にコストが大きくなっている状態を表す.

最後にD=H-Rの状態をとる場合にはm(z)=p_e(z),d(x|z)=p_e(x|z)の両方が成り立つため相互情報量の下界・上界共にタイトとなる.

仮に,d(x|z),m(z),e(z|x)に関して有限のパラメータしか持たない場合,一般的に相互情報量の下界・上界はタイトになることはない.ただし,不等式を最もタイトに抑えるDまたはRは存在することは保証されているため,H=R+Dを使って最適解を求めることができる.さらに,意図的にm(z)の近似精度を下げて固定されたDのもとでRを増加させることや,d(x|z)の近似精度を下げて固定されたRのもとでDを増加させることが可能.

\beta-VAEとの関係

Rを固定とする代わりに,最適なDRの関数D(R)として考える.すると,ルジャンドル変換により,固定の\beta=\frac{\partial D}{\partial R}の下で\min_{e(z|x),m(z),d(x|z)}D+\beta Rを解くことで最適なRDを求めることができる.目的関数を陽に書き表わせば次の様になる.

\displaystyle
\min_{e(z|x),m(z),d(x|z)}\int dxp^\ast(x)\int dze(z|x)\left[-\log d(x|z)+\beta\log\frac{e(z|x)}{m(z)}\right]

これは\beta-VAEの目的関数そのもので,仮に\beta=1の場合にはVAEで使われていたELBOと一致する.Dは再構成誤差の項を表し,RがKL項を表していることになる.ここでは\beta\ll 1の場合にはRが大きくてDが小さくなり,\beta\gg 1の場合にはDが大きくてRが小さくなる.

まとめ

相互情報量の挟みうちから良いELBOを導出したということ.なんとなく生成モデル(というか表現学習)で相互情報量が注目されているのかなという感じがする.

Deep Graph Laplacian Regularizationを読んだのでメモ

はじめに

Deep Graph Laplacian Regularizationを読んだのでメモ.

気持ち

ノイズ除去等の逆問題は通常不良設定問題であるた、なんらかのpriorを仮定して解く必要がある.よく知られているpriorとしてtotal variation priorやsparsity prior,graph Laplacian regularizerなどがあげられる.最近だとCNNによる力技でかなり精度良く逆問題を解けるようになっている.ただCNNは学習ベースであるためデータセットの収集問題があったり,ハイパーパラメータの調節問題等があって扱いにくい面もある.対してモデルベースなアプローチでは一般的に学習ベースなものよりもロバストであると言われているが,実践的にはパフォーマンスと柔軟性に限界がある.

そこで学習ベースとモデルベースのいいとこ取りをすれば完璧じゃないかというのが話の流れ.そこの橋渡しを行うためにgraph Laplacian regularizerをdeep learningの枠組みに取り入れるというのが論文のコントリビューション.

Graph Laplacian regularization

Graph Laplacian regularizationはその単純さとまずまずの性能からrestoration taskにおいて画像のpriorとして広く使われているらしい.簡単に言えばある画像\mathbf{x}\in\mathbb{R}^mが適切選ばれたグラフ\mathcal{G}に従って滑らかになるようにするもので,2次計画問題(QP)に使われることが多い.グラフの選び方はopen questionでいろいろなやり方が取られているが,この論文では単純な隣接グラフを使う.ただし,隣接グラフはCNNの出力から計算される点が一つ重要な点で,従来もdeepの枠組みにgraph Laplacian regularizationを取り入れた研究はあるがそれらは固定の関数を使っていてdata-drivenになっていないとのこと.

定式化

ここでは以下のように定式化されるノイズ除去の問題に焦点を絞る.

\displaystyle
\mathbf{y}=\mathbf{x}+\mathbf{n}

\mathbf{x}\in\mathbb{R}^mは元画像またはそのパッチでmピクセル数を表す.\mathbf{n}はノイズ項で\mathbf{y}は観測値.ここで,m個のピクセルを頂点とした隣接グラフ\mathcal{G}が与えられたとする.ノードijを結ぶ重み付きのエッジをw_{ij}とすれば,\mathcal{G}のadjacency matrix \mathbf{A}i,j要素がw_{ij}となるm\times m行列になる.すると\mathcal{G}のdegree matrix \mathbf{D}は対角要素が\sum_{j=1}^mw_{ij}となる対角行列になる.この時のグラフラプラシアン \mathbf{L}\mathbf{L}=\mathbf{D}-\mathbf{A}で計算される半正定値行列となる.

ノイズ除去のためのgraph Laplacian regularization付きのmaximum a posteriori problemは次のように定式化される.

\displaystyle
\mathbf{x}^\ast=\mathrm{arg}\min_\mathbf{x}||\mathbf{y}-\mathbf{x}||^2_2+\mu\cdot\mathbf{x}^T\mathbf{L}\mathbf{x}

第2項目がgraph Laplacian regularizationの項で\mu\geq 0はハイパーパラメータ.ここではグラフ\mathcal{G}は真の画像構造を反映したグラフになっている必要がある.従来は観測値\mathbf{y}やフィルタリング処理を施した\mathbf{y}からグラフを作る.\mathbf{L}=\mathbf{D}-\mathbf{A}であることを考えれば,graph Laplacian regularizationはグラフのエッジの値が大きいピクセル同士の値は似た値になるように仕向ける役割をしている.つまり,TVのような上下左右のピクセルで滑らかになるようにではなく,グラフの接続が強いピクセルで滑らかになる様にするため柔軟性が強い正則化になっている.

説明のためmatrix-valued function \mathbf{F}(\mathbf{Y}):\mathbb{R}^m\rightarrow\mathbb{R}^{m\times N}を定義する.\mathbf{F}(\mathbf{y})n行が\mathbf{f}_n\in\mathbb{R}^m,\:1\leq n\leq Nで定義されていて,観測値\mathbf{y}N個のm次元ベクトル\{\mathbf{f}_n\}_{n=1}^Nにmapする.この\mathbf{f}_nはexemplarと呼ばれexemplarを使えばエッジの重みw_{ij}は次の様に計算される.

\displaystyle
w_{ij}=\exp\left(-\frac{\mathrm{dist}(i,j)}{2\epsilon^2}\right) \\ \displaystyle
\mathrm{dist}(i,j)=\sum_{n=1}^N(\mathbf{f}_n(i)-\mathbf{f}_n(j))^2

\mathbf{f}(i)\mathbf{f}_ni番目の要素を表し,\mathrm{dist}(\cdot,\cdot)ピクセルi,j間のユークリッド距離で定義される.

Deep graph Laplacian regularization (DeepGLR)

提案手法のDeepGLRは二つのモジュールから構成されていて,一つはグラフを作るgraph construction moduleでもう一つは構成されたグラフを使って問題を解くQP solver.

Graph Laplacian regularization layer

この論文では従来と違い,graph Laplacian regularizationをCNNのモジュールとして組み込む.基本的には\mathbf{F}をCNNにしたというもの(これを\mathrm{CNN}_\mathbf{F}とする).観測画像を\mathcal{Y}と定義し,観測画像をK個のパッチ\{\mathbf{y}_k\}_{k=1}^Kに分割する.一般的にはパッチ毎に処理するが,ここでは\mathcal{Y}全体を入力し,\mathcal{Y}と同じサイズのN個のexemplar\{\mathcal{F}\}_{n=1}^{N}を出力とする.

Exemplar画像をK個のパッチ\mathbf{f}_n^{(k)}\in\mathrm{R}^m,\:1\leq kale Kに分割し,パッチごとにグラフ\mathcal{k}_kを作る.ただし,グラフは前結合ではなく8近傍のみを使って作る.こうすることによってグラフラプラシアン\mathbf{L}_kは固定のパターンを持つスパースな行列になる.グラフができたら後はそれをQP solverに渡してノイズ除去された画像\mathbf{x}_k^\ast\:(1\leq k\leq K)を得る.

DeepGLRはグラフの作成とは別にもう二つのCNN(\mathrm{CNN}_\mu\mathrm{CNN}_\hat{\mathcal{Y}})を持つ.

1.Generation of \mu (\mathrm{CNN}_\mu) 目的関数の正則化項の重み係数\{\mu_k\}^K_{k=1}を出力するCNN.

2.Pre-filtering (\mathrm{CNN}_\hat{\mathcal{Y}}) ノイズ除去手法では一般的に最適化の前にノイズ画像\mathcal{Y}にフィルタリング処理を行うが,それを学習ベースで行うための浅いCNN.

つまるところ画像からグラフを作るための\mathrm{CNN}_\mathbf{F}と,前処理を行う\mathrm{CNN}_\hat{\mathcal{Y}}正則化項の係数を決める\mathrm{CNN}_\muの3つからなる.

実験においてはノイズ除去の手続きをT回繰り返す,つまりT個のDeepGLRモデルを積み上げて処理を行う.さらに,QP solverで逆問題を解くだけでなく正解の画像を使った次のMSEの最小化する様に学習する.

\displaystyle
L_{\mathrm{res}}\left(\mathcal{X}^{(gt)},\mathcal{X}_T\right)=\frac{1}{HW}\sum_{i=1}^H\sum_{j=1}^W\left(\mathcal{x}^{(gt)}(i,j)-\mathcal{X}_T(i,j)\right)^2

この最小化に関してはstackされたDeepGLRの最終出力のみに適用される.

Numerical Stability

ここではQP solverの安定性について考える.元々のgraph Laplacian regularization付きの目的関数は本質的には次の線型方程式を解くことになる.

\displaystyle
(\mathbf{I}+\mu\mathbf{L})\mathbf{x}^\ast=\mathbf{y}

Lは半正定値行列なため(\mathbf{I}+\mu\mathbf{L})^{-1}逆行列が存在するため,\mathbf{x}^\ast=(\mathbf{I}+\mu\mathbf{L})^{-1}\mathbf{y}というclosed-formな解を持つ.問題としては\mathbf{I}+\mu\mathbf{L}の条件数\kappa(最小固有値/最大固有値)が大きいときunstableになってしまう.ただし,ここでは次の定理を利用すれば安定した計算をすることができる.

\displaystyle
\kappa\leq 1+2\mu d_{\mathrm{max}}

ただし,d_{\mathrm{max}}\mathcal{G}の最大度数.

証明

\mathrm{L}の性質から\mathrm{I}+\mu\mathrm{L}の最小固有値\lambda_{\mathrm{min}}=1となる.Gershgorin circle theoremから\lambda_{\mathrm{max}}の上界が次の様に定まる.\mathrm{L}i番目のGershgorin discは半径r_i=\sum_{j\neq i}|w_{ij}|\leq d_{\mathrm{max}}を持ち,disc iの中心は1+\mu r_iとなる.Gershgorin circle theoremから固有ベクトルは全てのGershgorin discのunionに存在するため,\lambda_{\mathrm{max}}\leq \max_i\{1+2\mu r_i\}となり,\kappa=\lambda_{\mathrm{max}}\leq 1+2\mu d_{\mathrm{max}}が成り立つ.

以上から条件数の最大を\kappa_\max\geq 1+2\mu d_\maxとすれば次の関係が導かれる.

\displaystyle
\mu\leq\frac{\kappa_\max-1}{2d_\max}=\mu_\max

よってもし\mathrm{CNN}_\mu\mu_\maxより大きな値を出力した場合には,出力値を\mu_\maxに切ることで安定性を持たせることができる.実験的には\kappa_\max=250としたそう.

まとめ

そもそもGraph Laplacian regularizationなるものの存在を知らなかったのでいい勉強になった.途中でてきたGershgorin circleはRNNの初期化に関する論文で前に見たことあったけど完全に忘れていた.

Deep Spectral Clustering Learningを読んだのでメモ

はじめに

Deep Spectral Clustering Learningを読んだのでメモ.

気持ち

クラスタリングの良さは類似度の指標とデータの表現に依存する.多くの手法はデータの表現固定であったり線形の変換によって得られることが多かったり.deepな学習ベースの手法も提案されているが勾配計算が複雑な場合が多いとのこと.そこでここではミニバッチサイズに線形に比例する計算オーダーで勾配を計算することができる表現を提案する.

Notation

実数行列A,Bのフロベニウス内積(Frobenius inner product)を\langle A,B\rangle:=\mathrm{tr}\langle AB^T\rangle,行列Aのフロベニウスノルムを||A||:=\sqrt{\mathrm{tr}(AA^T)}として定義する.A^\daggerをムーアペンローズの擬似逆行列とする.さらに集合\mathcal{F}相対的内部(relative interior)\mathrm{ri}(\mathcal{F})とする.この相対的内部というのは初めて聞いたけど,集合の内部にアフィン包の概念を入れたものっぽい.どんな意味があるかわからないけど,グラフを扱う上で定義しないとどこかでまずいことが起こるのかなと推測.

Data

ここでは一つの行列F=[\mathbf{f}_1,\dots,\mathbf{f}_n]^Tで表現されるn個のサンプルの集合\mathbf{f}_1,\dots,\mathbf{f}_n\in\mathbf{F}について考える.

Bregman divergence

Bregman divergence d_\phi:\mathcal{F}\times\mathrm{ri}(\mathcal{F})\rightarrow[0,+\infty)d_\phi(\mathbf{x},\mathbf{y})=\phi(\mathbf{x})-\phi(\mathbf{y})-\langle\mathbf{x}-\mathbf{y},\nabla\phi(\mathbf{y})\rangle,\:\phi:\mathcal{R}\rightarrow\mathbb{R}として定義する.ただし,関数\phi微分可能で凸な関数で,\nabla\phi(\mathbf{y})\in\mathbb{R}^d\phi\mathbf{y}に関する勾配を表す.

クラスタリングの文脈で使われるBregman divergenceはユークリッド距離の2乗\phi=||\mathbf{x}||_2^2,KLダイバージェンス,板倉齋藤距離などで定義されることが多いらしい.

Clustering

n個の観測F=[\mathbf{f}_1,\dots,\mathbf{f}_n]^T\in\mathcal{F}^nk個のクラスタに分けるのはassignment matrix \hat{Y}\in\{0,1\}^{n\times k}を求めることに等しい.仮定として各サンプルはただ一つのクラスタに割り当てられクラスタに所属しないサンプルはない,つまり\hat{Y}の行ごとの和をとれば必ず1になるという仮定を置く.よって\hat{Y}は次の集合に従う.

\displaystyle
\mathcal{Y}^{n\times k}:=\{\hat{Y}\in\{0,1\}^{n\times k}:\hat{Y}\mathbf{1}=\mathbf{1},\mathrm{rank}(\hat{Y})=k\}

さらに各クラスタcは一つの表現ベクトル\mathbf{z}_c\in\mathrm{ri}(\mathcal{F})で表現されると仮定し,各サンプル\mathbf{f}_i\forall b\neq c,d_\phi(\mathbf{f}_i,\mathbf{z}_c\leq d_\phi(\mathbf{f}_i,\mathbf{z}_b)の時クラスタcに割り当てられる.記述の簡略化として\mathbf{z}_c\in\mathcal{F}とし,k個の表現ベクトルを行列の形に並べたものをZ=[\mathbf{z}_1,\dots,\mathbf{z}_k]^T\in\mathcal{F}^kとして定義する.するとd_\phiの元,n個のサンプルをクラスタに分割する問題は次のエネルギー関数の最小化問題として定式化できる.

\displaystyle
\min_{\hat{Y}\in\mathcal{Y}^{n\times k},Z\in\mathcal{F}^k}\sum_{i=1}^n\sum_{c–1}^k\hat{Y}_{ic}\cdot d_\phi(\mathbf{f}_i,\mathbf{z}_c)\\ \displaystyle
=\min_{\hat{Y}\in\mathcal{Y}^{n\times k},Z\in\mathcal{F}^k}\mathbf{1}^T\Phi(F)-\mathbf{1}^T\Phi(\hat{Y}Z)-\langle F-\hat{Y}Z,\nabla\Phi(\hat{Y}Z)\rangle

ただし,\forall A=[\mathbf{a}_1,\dots,\mathbf{a}_n]^T\in\mathcal{F}^n,\Phi(A)=[\phi(\mathbf{a}_1),\dots,\phi(\mathbf{a}_n)]^T\in\mathbb{R}^n\nabla\Phi(A)=[\nabla\phi(\mathbf{a}_1),\dots,\nabla\phi(\mathbf{a}_n)]^T\in\mathbf{R}^{n\times d}のように各ベクトルを行列の形で表現したもの.

Banerjeeらは上記の目的関数の最小解\mathbf{z}_cd_\phiがBregmanダイバージェンスの時においてクラスタcに所属するサンプルの平均ベクトルになることを示したらしい.行列で表現すればZ=(\hat{Y}^T\hat{Y})^{-1}\hat{Y}^TF=\hat{Y}^\dagger Fということ.ここで集合\mathcal{P}=\{\hat{Y}\hat{Y}^\dagger:\hat{Y}\in\mathcal{Y}^{n\times k}\}を定義すれば次の1変数に関する最小化問題として書き直せる.

\displaystyle
\min_{\hat{C}\in\mathcal{P}}\mathbf{1}^T\Phi(F)-\mathbf{1}^T\Phi(\hat{C}F)-\langle F-\hat{C}F,\nabla\Phi(\hat{C}F)\rangle

Deep Spectral Clustering Learning

Constraint Relaxation

ここでは\min_{\hat{C}\in\mathcal{P}}\mathbf{1}^T\Phi(F)-\mathbf{1}^T\Phi(\hat{C}F)-\langle F-\hat{C}F,\nabla\Phi(\hat{C}F)\rangleの問題をベースとして考える.この最小化問題はNP-hardであるため,緩和問題を考える.まずは\hat{C}\in\mathcal{P}\hat{C}\in\mathcal{C}^{n,k}として緩和する.ただし,\mathcal{C}^{n,k}\mathcal{P}を含むランクkn\times nの対角行列\mathcal{C}^{n,k}:=\{\hat{C}\in\mathbb{R}^{n\times n}:\hat{C}^2=\hat{C},\hat{C}^T=\hat{C},\mathrm{randk}(\hat{C})=l\}.この緩和された問題は次のように定式化できる.

\displaystyle
f(F):=\mathrm{arg}\max_{\hat{C}\in\mathcal{C}^{n,k}}\mathbf{1}^T\Phi(\hat{C}F)+\langle F-\hat{C}F,\nabla\Phi(\hat{C}F)\rangle

ただし,上記は\hat{C}に関連しない項は式から除外している.

嬉しいことにこの解はclosed-formに求まる.s=\mathrm{rank}(F)と定義した時s\leq kならば,この問題の解はf(F)=\{\hat{C}\in\mathcal{C}^{n,k}:\hat{C}F=F\}=\{\hat{C}\in\mathcal{C}^{n,k}:\hat{C}=FF^\dagger+VV^T,VV^T\in\mathcal{C}^{n,(k-s)},VV^TF=0\}となる.特にs=kならば,VV^T=0f(F)=\{FF^\dagger\}となる.(証明はsupplementary materialにあるらしいので今度読む.)

以下,学習サンプルの次元dkより大きくなく,s\leq kを満たす場合のみを考える.もしs\gt kならば,解の集合はf(F)=\{FF^\dagger\}として考えられる.

Structured output prediction

まず,n個のサンプル\mathbf{x}_i\in\mathcal{X}と,パラメータ\thetaとする埋め込み関数\varphi_\theta:\mathcal{X}\rightarrow\mathcal{F}が与えられたとする.ただし,\varphi\forall i\in\{1,\dots,n\},\varphi_\theta(\mathbf{x}_i)=\mathbf{f}_iで,表現ベクトル\mathbf{f}_iを行列にまとめたものをF=[\mathbf{f}_1,\dots,\mathbf{f}_n]^T\in\mathcal{F}^nとする.また,正解のassignment matrix Y\in\mathcal{Y}^{n\times k}は与えられているものとする.ここでの目標は,Fの正解のクラスタリング行列をC=YY^\dagger\in\mathcal{P}とすれば,緩和問題f(F)\subseteq\mathcal{C}^{n,k}から得られた行列が真のクラスタリング行列Cに可能な限り近づくような埋め込み関数\varphi_\thetaを学習することとなる.

以下では行列F\varphi_\thetaに依存する変数として考える.行列Fの真のクラスタリングC\in\mathcal{P}f(F)から推定されたクラスタリング\hat{C}間の相違度を最小化する問題は次のempirical risk minimizationとして定式化できる.

\displaystyle
\min_{F\in\mathcal{F}^n}\max_{\hat{C}\in f(F)}||C-\hat{C}||^2

ここでf(F)のとる全ての行列が同じランクである場合,上の問題は||C-\hat{C}||^2=||C||^2+||\hat{C}||^2-2\mathrm{tr}(C\hat{C}),\:||\hat{C}||^2=\mathrm{tr}(\hat{C})=\mathrm{rank}(\hat{C})=kとして書ける.この時||\hat{C}||^2が定数となることから次の問題と等価として扱える.

\displaystyle
\max_{F\in\mathcal{F}^n}\min_{\hat{C}\in f(F)}\mathrm{tr}(C\hat{C})

この問題は次のような下界を持つ.(証明はsupplementary material)

\displaystyle
\max_{F\in\mathcal{F}^n}\min_{\hat{C}\in f(F)}\mathrm{tr}(C\hat{C}FF^\dagger)=\max_{F\in\mathcal{F}^n}\mathrm{tr}(CFF^\dagger)

ただし,\forall\hat{C}\in f(F),\hat{C}FF^\dagger=FF^\dagger.この下界は\mathrm{rank}(F)=kの時に等号が成り立つ.

この下界の最適化の難しいところはFF^\daggerの両方に依存するところ.\mathrm{rank}(F)が定数と仮定した時,この問題は微分可能となりFに関する勾配は次のように計算できる.

\displaystyle
\nabla_F=2(I-FF^\dagger)C(F^\dagger)^T

ただし,I単位行列.この論文の実験においてはFは常にフルランクで,ランクが定数になるという条件を満たしていたとのこと.

complexity

この計算が閉形式を持つだけでなく,その計算コストがサンプル数nに線形,次元dに対して2乗オーダーであることを示す.C=YY^\dagger\in\mathcal{P}が真のクラスタを表す行列とする.ただし,行列Y\in\mathcal{Y}^{n\times k}は与えられている.\mathbf{y}_cYc列とすると,(Y^\dagger)^Tc列は\frac{1}{\max\{1,\mathbf{y}_c^T\mathbf{1}\}}\mathbf{y}_cと記述できる.(Y^\dagger)^Tの計算コストはYが疎であることからnに線形になる.C=YY^\daggerの関係を使えば\nabla_Fは次のように書ける.

\displaystyle
G:=\frac{\nabla_F}{2}=(Y-F[F^\dagger Y])[F^\dagger(Y^\dagger )^T]^T

[\cdot]は計算結果がd\times k行列であることを表し,[\cdot]Yが疎であることから効率的に計算ができる.F^\daggerの計算コストは\mathcal{O}(nd\min\{n,d\})になる(d\leq nの仮定が成り立つ場合には\mathcal{O}(nd^2)).

Learning deep models

ここまで議論してきた手法を使ってニューラルネットを学習する.まず,ミニバッチの行列表現をF=[\mathbf{f}_1,\dots,\mathbf{f}_n]^T\in\mathcal{F}^nとする.ただし,\varphi_\theta(\mathbf{x}_i)=\mathbf{f}_i,つまりオリジナルのデータ\mathbf{x}_i\in\mathcal{X}ニューラルネット\varphi_\theta:\mathcal{X}\rightarrow\mathcal{F}で変換して得られた特徴ベクトルを並べたものがF.すると学習のための目的関数は次のように表現される.

\displaystyle
\mathrm{Loss}(F):=k-\mathrm{tr}(CFF^\dagger)

C=YY^\dagger\in\mathcal{P}が教師データで,この目的関数は微分が可能であるためニューラルネット\varphi_\thetaはbackpropを使って学習が可能.さらにこの方法の良いところは\mathcal{F}\mathbb{R}^dの場合に限らず,例えばKLダイバージェンスを使った確率分布の分割が目的の場合にはニューラルネットの最終層にsoftmaxを使うことで\mathcal{F}d次元の単体上に構成することができる.

まとめ

今回証明までは読めてないのでなんとも言えない部分が多くなってしまった.とりあえずニューラルネットを使った非線形の変換をgraph-based clusteringの枠組みに持って行って,離散最適化問題を緩和することでうまいことbackpropの枠組みに落とし込んだというのが大体の流れ.特に目的関数の勾配がclosed-formに求まることが論文の推しでこの界隈で初めてのアプローチと言っていた.

なんとなくgraph-based clusteringとDNNはもう少しいろんなことに使えそうな気がするけど意外と論文は多くない気がする.