(勉強メモ) Information bottleneck (2)

前回に引き続いてinformation bottleneck (IB) 関連の論文を読んでいました。

特に、information plane (IP) という図の上で深層学習の挙動を説明する議論について調べていました。ひとまず現状把握という感じのメモで、細かいところは読んでいません。

Information plane

発端

深層学習の挙動をinformation bottleneckの言葉で解析する研究の発端は、以下の2つだと思われる。

  • [1] Tishby and Zaslavsky (2015). Deep Learning and the Information Bottleneck Principle. (URL)
  • [2] Shwartz-Ziv and Tishby (2017). Opening the Black Box of Deep Neural Networks via Information. (URL)

Information bottleneckでやりたいことを直感的に述べると、ある入力信号Xを圧縮するに当たって、別の信号Yの情報をなるべく喪失しないようにしつつ可能な限り小さく圧縮するというトレードオフを考えるというものであった。分類問題のように、特徴量Xを入力としてラベルYを予測したい状況を考えると、この思想に自然に行き着く。[1] では、DNNによる分類の挙動をIBの言葉で解析した場合に、どんなことが言えてほしいかという議論をしている（具体的な解析というより、解析方針の提言みたいな感じである）。IBの議論より、中間層表現をLとすると、入力Xの情報が中間層においてどの程度圧縮されているかは $I(X, L)$ がどの程度小さいかに対応している (厳密には違うけどrate distortion theoryを意識するとそう思うこともできる)。また、中間層LにおいてラベルYの情報がどの程度残存しているかは、$I(L, Y)$ がどの程度大きいかに対応している。そこで、DNNにおいてある時点での $I(X, L)$ と $I(Y, L)$ を縦軸と横軸にプロットすることによって、現在のDNNの状態がIBのトレードオフにおいてどの位置にあるかを可視化することができるでしょう、ということである。この図をinformation planeと呼んでいる。

[2] は、[1] の提言に基づいて具体的な解析を行った初めての論文で、SGDのエポックを追うごとにinformation plane上ではどの位置にいるかを可視化した。主な主張として、information plane上で、SGDで訓練したDNNの典型的な挙動は下図のようになると言っている。 (この図は [4] から借りてきた。実際の実験を表したものではなく、概念図である。)

横軸が符号の大きさ (レート) に対応する $I(X, L)$ なので、左に行くほど圧縮率が高い。縦軸は $Y$ に関する情報の残存量であり、上に行くほど $Y$ に関する情報は多く保持している。よって直感的には、よい汎化のためには、「左上」のほうに向かうのが嬉しいということになる。[2] は、DNNをSGDで訓練するとき、次の2つのフェーズがあるということを主張している。

  1. 初期のエポックはERMフェーズで、データに対してDNNをフィッティングさせることに費やされる。この間、圧縮率は上がらない ($I(X, L)$ が増える) ので、IP上では「右上」に向かっていく。
  2. 十分に訓練誤差が下がった段階で、圧縮フェーズに移行する。圧縮フェーズでは、$Y$ に関する情報残存量 $I(Y, L)$ はあまり変えないが、中間表現 $L$ の余計な部分が削ぎ落とされて $I(X, L)$ は下がる。

[2] では、tanh活性化関数をもつNNによる実験で、実際にこのような図を描いている。こういった実験を通して、この論文では次のような主張をしている。

  • SGDによるNNの訓練では、ERMフェーズは相対的に短く、ほとんどのエポックは圧縮フェーズに費やされる
  • SGDの軌道は、初期段階では訓練誤差を減らすべく速く遷移する (drift phase)。十分に訓練誤差が小さくなると、勾配はとても小さくなって、SGDのノイズに起因した拡散過程的な動きが支配的になる (diffusion phase)。Information plane上での圧縮は ($I(X, L)$ の減少はdiffusion phaseによって起こっている。(こういう感じのストーリーは、SGDをdiffusionとして解析する他の研究でも言われている気がする。ICAの論文 とか)
  • NNの隠れ層を増やすと、compressionが速くなって訓練が速くなる (必要なepoch数が減少する)
  • DNNはIBの意味での限界に近いところに収束できる

批判

これらの主張は、成り立つとすれば面白いが、一般のDNNの訓練で成り立つと結論づけてしまうには強すぎると思われた。で、このあたりのストーリーが果たして本当なのかについて、後続研究で議論が続いているように思われる。例えば、以下の [3] では、上の主張はどれも必ずしも成り立たないということを述べている。

  • [3] Saxe et al. (2018). On the Information Bottleneck Theory of Deep Learning. (URL)

[3] では、次のようなことが指摘されている。

  • 圧縮フェーズの存在はtanhのように両側がsaturateした活性化関数に特有の現象なのではないか？ 実際に、ReLU DNNにおいて実験してみるとcompression phaseのような挙動が見えなくなったり (IP上では一貫して右肩上がりになる)、linear networkに関してはcompression phaseがないことが示せる。
  • 圧縮フェーズのためにrandomness (diffusion phase) が必要とは限らない。Batch gradient descentでもcompression phaseのような挙動が見えることがある。

[3] は論文だけでなくて、Openreview 上で [2] の著者と直接議論が進められているので、そちらも眺めた。いずれにせよ [2] も [3] も何かを結論づけるにはまだ早いが、重要な議論であるので後続研究を続けよう、というのが [3] の採択理由でも述べられている。

出力 $Y$ は分類問題においては離散変数であるが、入力 $X$ や中間層 $L$ は (計算機上で実装しているとはいえ) 連続変数とみるのが自然とも考えられる。実験では、相互情報量は厳密計算しているわけではなく、空間をbinに区切ったり、カーネル密度推定量ベースの推定量を使ったりして推定を行っている。実際、この推定量の選択が実験結果 (＝information plane上での挙動の違い) に影響しうるよね、ということがopenreviewでも議論されている。タイミングのいいことに、先週、相互情報量の推定量の選択にもフォーカスしたinformation planeのサーベイ論文が公開された。

  • [4] Geiger (2020). On Information Plane Analyses of Neural Network Classifiers – A Review. (URL)

このサーベイ論文をみると、[3] 以降にもinformation planeの後続研究がたくさん出ていることがわかる。下の表が立派で、unpublished workも調べ上げて、(i) NNのアーキテクチャ (ii) 活性化関数の選択 (iii) 訓練アルゴリズム (iv) データセット (v) 相互情報量の推定手法の組み合わせに基づいて、compression phaseが観察されたかどうかについてまとめられている。

まとめると、information planeを利用した研究において、現状では [1] や [2] で期待されたようなストーリーが成り立っているとは言い切れない。一方、思想的には色々と面白い部分があるし、依然として可能性は感じるので、それなりの数の研究者が取り組んでいるのだと思う。

感想

ちなみに、[4] に書いてあって、個人的に気になる文章はこちら:
Our analysis suggests that compression visualized in information planes is not information-theoretic, but is rather compatible with geometric compression of the activations.

確かに、相互情報量ってgeometryの情報を陽に考慮した概念ではないので、完全にinformation-theoreticな議論にこだわらずに、幾何学的に何が起きてるのか考えるのは面白そう (もともと符号理論にしてもレート歪み理論にしても離散的なビット列のようなものに圧縮するための理論である)。相互情報量を推定するときにbinningやKDEを使うと、例えば近いセルをひとまとめにするという意味でgeometryの情報は暗に使っているのだが、そのへんの働きをクリアにしたいよねというのは思った。

(勉強メモ) Information bottleneck (1)

Information bottleneck関係の個人的勉強メモです。

ブログでは、書くことの心理障壁を下げるために以前よりも勉強内容を小出しにしていくことを考えており、今日の目標は以下の元論文の主張をまとめておくことです。

  • Tishby, Pereira, and Bialek (2000). The information bottleneck method. (URL)

背景

Information bottleneck法 (Tishby et al. 2000) とは、レート歪み理論 を一般化した概念である。レート歪み理論は非可逆圧縮の達成限界についての理論で、符号の空間のサイズ (レート) と復号時のエラー (歪み) の間のトレードオフを記述したものである。具体的に、このトレードオフは、「レート歪み関数」という、相互情報量をともなう最適化問題の最適値によって書ける。レート歪み関数の定義には、復号時のエラーを定義するための損失関数 (歪み関数) を指定する必要があるが、実用上は適切な損失関数を選ぶことが難しいことがある。Information bottleneck法では、$X$ に対する損失関数は陽に指定せず、その代わりに、符号のサイズは小さくしつつ別の信号 $Y$ に関係する情報を最大限保つという目的関数を考えることで、「$X$ の中の $Y$ に関係する情報」を抽出する問題を定式化する。例えば、$X$ を入力として $Y$ を予測する機械学習の問題があるとき、$Y$ の予測のために必要な情報はなるべく失わずに、最小限の大きさの特徴量 $\hat{X}$ を抽出したいというような状況が考えられるが、それを情報理論 (レート歪み理論) 的に解釈して定式化したのがinformation bottleneckであるというイメージ。

レート歪み理論の歪み (distortion) は「ひずみ」と読みます。

Information bottleneckの基礎

レート歪み理論

確率変数 $X$ を有限集合に値をとる符号に圧縮したい。$X$ の分布 $p(x)$ は既知とする。エンコーダーとデコーダーは確率的でもよいとし、まず (i) エンコーダーによって $X$ を $Z$ に符号化し、次に (ii) デコーダーによって $Z$ を $\hat{X}$ に復号化するプロセスを、まとめて条件付き分布 $p(\hat{X} \mid X)$ で表現するものとする。このプロセスの良さをはかるために、損失関数 $d$ を使って

$$
D = \mathbb{E} [d(X, \hat{X})]
$$

によって損失を定義する。

$Z$ が値をとる空間のcardinalityの対数を $R$ と書き、レートと呼ぶ。原理的には、$R$ を増やすと信号 $X$ を無限に細かく離散化できるので、歪み $D$ は小さくなるはずである。逆に、$R$ を減らすと、表現力の低い符号によって $X$ の挙動を説明しなければならなくなるので、$D$ は大きくなる。したがって $R$ と $D$ にはトレードオフがあるが、このトレードオフの意味で最適なフロンティアがどこにあるか知りたい。$D > 0$ を与えたときに、可能な限り最も短い $R$ を $R(D)$ と書く (これをレート歪み関数という)。

レート歪み理論によると、$R(D)$ は次の最適化問題の最適値に等しい。

$$
\min_{p(\hat{x} \mid x)} I(X, \hat{X})
\text{ s.t. } \mathbb{E} [d(X, \hat{X})] \leq D
\tag{1}
$$

つまり、歪みが $D$ 以下に抑えられるようなエンコーダー/デコーダー対 $p(\hat{x} \mid x)$ のなかで、$X$ と $\hat{X}$ の相互情報量の最小値が、ぎりぎり達成可能な符号のサイズに対応している。

たまたま最近Cover and Thomasの輪読会をやったので、証明はその本で読んだ。$R \geq I(X, \hat{X})$ のようなことは不等式評価ですぐにわかるのだけど、達成可能性のほうは具体的なエンコーダー/デコーダーを作らなければならず、ちょっと込み入っているように感じた。他の方法はないのかと思って2冊目も確認したけど、だいたい同じ証明だった。

レート歪み関数の計算

現実には (1) の最適化問題の解や最適値をclosed formで計算するのは難しいので、数値計算のアルゴリズムが提案されている。ここでは、Tishby et al. (2000) で紹介されているBlahut–Arimoto (BA) アルゴリズムについて書く。

(1) のLagrangianを書くと
$$
I(X, \hat{X}) + \beta (\mathbb{E} [d(X, \hat{X})] - D)
\tag{2}
$$
となる。$\beta$ はLagrange乗数である。

ここで、($D$ そのものではなく) $\beta > 0$ を与えたときにLagrangianを最小化する問題を考えてみる。Lagrangianの $p(\hat{x} \mid x)$ に関する変分を考えると、停留条件は

$$
p(\hat{x} \mid x) \propto p(\hat{x}) \exp( - \beta d(\hat{x}, x))
$$

のようになる。この停留条件の式に $p_t(\hat{x} \mid x)$ を再代入していくアルゴリズムを考えると、やがて不動点に収束することが示される。これがBAアルゴリズムと呼ばれている。

BAアルゴリズムは通信路容量を計算するのにも使われる。探したら以下のスライドがあった。収束性についてちゃんと勉強していないので、そのうち勉強したい。

Information bottleneck method

現実には歪み関数 $d$ として適切なものが何であるのか判断するのが難しい状況がある。代わりに、「ある別の変数 $Y$ に関する情報を最大限保ちつつなるべく小さな空間にエンコードする」という問題を考えるというのがinformation bottleneckの発想である。具体的には、(2) の代わりに

$$
I(X, \hat{X}) - \beta I(\hat{X}, Y)
\tag{3}
$$

を最小化する $p(\hat{x} \mid x)$ を考える。それぞれの項について考えてみると、

  • $I(X, \hat{X})$ はもとのレート歪み理論の定式化 (2) にも出てくる項で、これが小さければ小さいほど圧縮率が高い符号を意味する。例えば、$X$ を1点集合に潰してしまうのが自明に最も短い符号だけど、このとき $I(X, \hat{X}) = 0$ となる。逆に、$X$ を無限に細かくquantizeすれば無限に高精度で復号できるが、上限値として $I(X, \hat{X}) = I(X, X) = H(X)$ にどんどん近づいていくはず。
  • $- \beta I(\hat{X}, Y)$ は符号化によって $Y$ の情報をなるべく失わないための正則化である。データ処理不等式から一般に $I(X, Y) \geq I(\hat{X}, Y)$ となるから、エンコード/デコードの処理で $Y$ に関する情報が増えることはない。

よって、第1項を最小化することはなるべく小さく圧縮することを目指すのに対して、第2項を最小化することはなるべく元の情報を保つことを目指すので、どこかに均衡点が発生する。

Information bottleneckの式 (3) の停留条件を書くと、

$$
p(\hat{x} \mid x) \propto p(\hat{x}) \exp( - \beta D_{KL}(p(y \mid x) \parallel p(y \mid \hat{x})))
$$

となる。よって、information bottleneck法では、結果的に $D_{KL}(p(y \mid x) \parallel p(y \mid \hat{x}))$ を歪み関数として採用したことになっているといえる。

元論文 では、(3) を解くためのBlahut–Arimoto型のアルゴリズムも与えられている。

次回メモ

もともと、最近の機械学習 or 深層学習の文脈で、information bottleneckが (思想として) どう理解されているのか気になったので、次回はより最近の論文をランダムに読みます。特に、深層学習の汎化の説明として、Tishby and Zaslavsky (2015) がinformation planeという概念を導入しており、そのあたりの整理が目標です。

最近出した論文 (劣モジュラ正則化とかGANとか)

ブログを約2年放置してしまいました (前回は2018/4/30)。

この2年ほどのあいだに、自分の環境 (職場、家庭、学位) がいろいろ変わって大変でした。しかしそろそろ仕事以外の勉強も再開していきたいので、リハビリがてら色々書いていこうと思います。

久しぶりすぎて何から書き始めるか迷ったのですが、自分が関わった論文が直近1年の間に何本か出たので、それらについて書きます。

劣モジュラ正則化

劣モジュラ正則化 (submodular regularization) というテーマで論文を2つ書きました。これは自分の博士課程の研究です。

劣モジュラ正則化とは何かというと、LassoとかGroup lasso, Fused lassoのような凸正則化法を拡張した概念です。これらの正則化法は、推定したいパラメータに対する構造的スパース性 (structured sparsity) を誘導するものです。例えば、線形回帰におけるLassoは

$$
\min_{\theta \in \mathbb{R}^p} \frac{1}{2} | y - X \theta |^2_2 + \lambda | \theta |_1
$$

というような凸最適化問題の解として定義されるものですが (※記号の説明は略)、ここでL1正則化項はパラメータ $\theta$ に対するcoordinate sparsity (いわゆる普通のsparsity) を誘導します。しかし、もっと「構造のあるスパース性」を考えることもできます。例えば、generalized fused lassoという手法では

$$
\sum_{(i, j) \in E} |\theta_i - \theta_j|
$$

という正則化項を利用しますが、これは与えられたグラフ $G = (V, E)$ 上で区分的に定数となるような性質を誘導します。

こういった正則化項が、実は 劣モジュラ関数 と関係があるということを指摘した 2010年の論文 があります。具体的には、Lasso, Group lasso, Fused lassoといったような代表的な手法も含む比較的広いクラスの正則化項が、劣モジュラ関数の凸緩和 (Lovász extension) として書けます。

このテーマについて本も出ているので、興味があればそちらを参照するのがわかりやすいかと思います。

こういった一般化をするひとつの利点として、proximal operator (以前のブログ でも書きました) の計算が劣モジュラ関数最小化と関係のあるアルゴリズムで解けるという話があります。というわけで、劣モジュラ正則化というのは、数理統計 (Lasso)、機械学習 (structured sparsityのモデリング)、離散最適化 (劣モジュラ関数最小化) のインターセクションにある研究テーマになっているというわけです。自分が博士課程に進学した当初、こういう分野横断的な話が面白そうだなと思って勉強してましたが、大学で 劣モジュラ関数の教科書 (すごく難しい) などを輪読したりしているうちに最適化の関係ない勉強が楽しくなり、どんどん脱線して収拾がつかなくなってきました。博士課程あるあるっぽい話ですが、皆さん気をつけましょう (?)

自分の研究ですが、以下のことをしました。（圧縮した説明）

  1. Degrees of freedomの研究 (論文はこちら ): Degrees of freedomというのは、線形回帰モデルの推定量に対して定義される「実効パラメータ数」のような概念です。あるいは、fixed design regressionにおいてバイアスバリアンス分解したときの、バリアンスに相当する部分です。具体例としては、Mallows’ Cp やAICによるモデル選択では「変数の数」が罰則になりますが、実際にGaussian noiseの設定でOLSのdegrees of freedomを計算すると変数の数が出てきます。一方、degrees of freedom自体は非線形推定量に対しても定義することができて、例えばLassoでは解の非ゼロパラメータ数と一致する ことなどが知られています。この研究では、劣モジュラ正則化に対してdegrees of freedomを統一的に計算する公式を導出しています。とくに、計算するアルゴリズムが劣モジュラ関数の選択に依らず、「解の成分の中でユニークな値を数える」という方法でdegrees of freedomが計算できます (現実にはソートの計算量があればOK)。こういった「アルゴリズム的な性質」が劣モジュラ正則化に特有なところで、一般の凸正則化ではこうなるとは限らないのが面白いところです。
  2. 「区分単調信号推定」の研究 (論文はこちら ): Nearly-isotonic regression という手法があり、それについて解析した論文です。単調関数の推定手法で isotonic regression という歴史ある手法があるのですが、それを正則化法に拡張した版がnearly-isotonic regressionです。もともと「単調増加である」というハードな制約があったところを、正則化法にすることによってソフトな制約として扱っているので、ある程度構造的なmisspecificationがあることも許されます。Rのパッケージ もあります。自分の研究の文脈としては、実はこのnearly-isotonic regressionは劣モジュラ正則化の一例になっているので、その事実を利用してアルゴリズムを導出したり、上の研究成果を使ってdegrees of freedomを導出したりできます。この論文としては、区分単調信号 (piecewise monotone signal) の推定という設定を考えて、その状況下でのリスクバウンドを導出したりしています。

博士課程は、(つい最近の生々しい出来事なのであまり整理して語れないですが) まあまあつらかったです。能力的な意味では、自分の場合はコードを書いたり英語での論文ライティングがボトルネックになっていると感じていたので、たくさん練習しようと試みました。が、勉強とか「素振り」ばかりしていると、その間アウトプットが全然ないので、普通にどんどん心が折れていきます…。単著論文中心の研究生活だったのですが、とはいえ、自分に対する報酬の設計はうまくやったほうが精神衛生上よかったなと思いました。また、研究の一貫で劣モジュラ最小化のCython実装とかをかなり時間をかけて書いてました。これは、残念ながら論文成果にはほとんど繋がっていないのですが、劣モ最小化のプログラムは世の中にあまり存在しないはずなので、せめて整理してGithubにでも上げておきたい…が、なかなか時間がとれず、という感じであります。

GAN

2019年4月にPFNという会社に入社し、業務で研究をしています。依然として論文も書いたりしており、昨年度はインターン生と書いた論文についての解説記事を会社のブログに書いたりしました。これはGANの理論についての研究ですが、こういった複雑なアウトプットを出せる生成モデルにはずっと興味があるので、今後も何かできたらいいなと思っています。ちなみに、論文が採択されたICLR2020はエチオピア (!) で開催されるはずだったのですが、COVID19の影響で現地開催はなくなってしまいました。どうなることやら…

Backpropしないニューラルネット入門 (2/2)

1. 概要

下記のarXiv論文を紹介します。

Jinshan Zeng, Tim Tsz-Kit Lau, Shaobo Lin, Yuan Yao (2018).
Block Coordinate Descent for Deep Learning: Unified Convergence Guarantees.arXiv:1803.00225

現時点では投稿されて間もない論文ですが、個人的には機械学習の論文を読んでいて久々に楽しい気持ちになれました。

論文の提案手法はgradient-free methodと呼ばれる手法の一種なので、本記事はそのあたりのレビューも少し兼ねます。

2. 勾配法の収束条件

ニューラルネットの構造をひとつ固定し、その構造を使って表せる関数の全体を $\mathcal{F}$ と書きます。ニューラルネットの学習とは、与えられた損失を最小化する関数を見つけることです。例えば、二乗損失なら
$$
\hat{f} \in \arg \min_{f \in \mathcal{F}} \sum_{i=1}^n (y_i - f(x_i))^2
$$
のようになります。Part 1で述べたとおり、この最適化問題が解けるという前提のもとで、いくつかの新しい汎化誤差バウンドが得られています。しかし、これは一般には非凸最適化となり、大域最適解へが得られることは保証できません。

現在、ニューラルネットの学習はSGD, AdaGrad, Adam, RMSPropといった勾配法ベースの最適化手法が使われていることが多く、主要な深層学習ライブラリも、勾配計算 (Backprop) の機能を提供することを主な目的としていると思います。これらの手法は、目的関数が凸であれば大域解への収束が保証されていることが多いです。

が、実際に興味のある目的関数は凸ではなく、もっというと、ReLUを使った場合は微分可能ですらありません。ちなみに、目的関数が凸でも、微分可能性のようなもの (正確にはsmoothness) は収束レートに関わることがあります。

また近年、ハードウェアへの移植などを目的として、Binarized Neural Networksのようにパラメータが離散的な値をとる深層学習モデルがあります。このようなモデルではそもそも勾配が存在しないため、勾配ベースの最適化アルゴリズムを直接適用することはできません。

3. Block Coordinate Descent (BCD, ブロック座標降下法)

だけど、

  • 目的関数が非凸でも
  • 微分不可能でも
  • 勾配を使わなくても
  • 初期値をどこに設定しても

局所解に収束することを理論的に示せるよ。ブロック座標降下法 ならね!!

3.1. アルゴリズムの概要

記号

$T$ 層のニューラルネットを学習する問題を抽象的に定義します。まず、

  • $d_0, d_1, \ldots, d_T$ : ニューラルネットの各層の幅。特に、$d_0$ は入力 $x$ の次元、$d_T$ はラベル $y$ の次元と一致
  • $W_i \in \mathbb{R}^{d_{i} \times d_{i - 1}}$ : 第 $i$ 層のパラメータ
  • $\sigma_i$ : 活性化関数

として、ニューラルネットで表現している関数は
$$
f(x) = W_T \sigma_{T - 1} (W_{T-1} \sigma_{T-2}(\cdots \sigma_{1}(W_1 x) \cdots ))
$$
であるとします。また、

  • $X := [x_1, \ldots, x_n] \in \mathbb{R}^{d_0 \times n}$ : 入力データ
  • $Y := [y_1, \ldots, y_n] \in \mathbb{R}^{d_T \times n}$ : ラベルデータ
  • $\mathcal{L}(f, y)$ : 損失関数 (非負・連続だが凸とは限らない)

として、経験損失を
$$
\ell(f(X); Y) := \frac{1}{n} \sum_{i = 1}^n \mathcal{L}(f(x_i), y_i)
$$
と定義します。$r_i, s_i$ を事前分布や正則化項を表す関数とします。このとき、興味のある最適化問題は、以下のような等式制約のある問題として書けます。

なお、本来最適化すべきパラメータは $W_i$ ($i = 1, \ldots, T$) ですが、スラック変数を導入して $(W_i, V_i, U_i)$ の三つ組を最適化するという意味で、論文中では上の最適化問題を3-splitting formulationと呼んでいます。

BCDアルゴリズム

BCDアルゴリズムのアイデアは簡単です。まず、上記の等式制約をFrobeniusノルムによるペナルティとして表現します。

拡張ラグランジュ関数 から線形のラグランジュ乗数を取り除いた格好ですが、なんと呼ぶのが適切かはちょっと知りません。二次バリア関数とか？

あとは、$V_i, U_i, W_i$ のそれぞれに関する最小化をサイクリックに行うだけです。論文からアルゴリズムを引用します。

それぞれの部分問題はちょうど近接作用素を求めるような形になっており、例えば「損失 $\ell$ が2次関数、$\sigma$ がReLU、$s_i$, $r_i$ が0」といった典型的な場合ではclosed-formの解が得られます (e.g. Lemma 1)．

ニューラルネットがconvolution層を含む場合も等式制約を追加すればよいので、アルゴリズムを拡張することは容易であることが述べられています。また、ResNetに拡張した例がAlgorithm 2として提案されています。

なお、後述するように、このアルゴリズムには理論収束保証もあります。しかし、オリジナルの問題についてではなく、この $\bar{\mathcal{L}}$ が局所解に収束することを保証するものですので、その点に関しては注意が必要です。

3.2. 数値例

論文の数値例を紹介します。追実験などはしていません。

$T = 4$ 層のDNNでMNISTとCIFAR-10の学習を、BCDおよびSGDで行った結果の引用です。NNの構造やSGDの学習率の詳細は論文を参照してください。

実時間ではなくエポック数の比較ですが、SGDが学習に約100エポック必要とするのに対し、BCDは5エポック以下（！）で学習がほとんど終了していることがわかります。また、最終的なtest accuracyもSGDと比較して遜色ないものとなっています (Table 1).

定式化から明らかなようにBCDの1回の更新にかかるコストは大きく、メモリに乗らない量のデータをどう扱うかなど疑問点はありますが、promissingな結果であることは間違いないと思われます。

3.3. その他のgradient-free method / 先行研究

先行研究に少し触れておきます。（このあたりはまだ勉強中です）。

ニューラルネットの学習をgradient-freeに行うアルゴリズムとしては、 ADMMベースの手法[1],[2],BCDベースの手法[3]が提案されています。Gradient-freeな方法の動機として、紹介論文や [1] では勾配法との比較が述べられています。計算面での主な違いは、勾配法は小さなミニバッチを使った低コストな更新を多数回行うのに対し、勾配フリー法は多くのデータを使った高コストな更新を小数回行う手法になっており、前者はGPU、後者はCPU上での実行が適しています。勾配法の収束については、勾配消失やプラトーなど既知の問題がありますが、勾配フリー法では紹介論文のような収束保証が得られています。

[1] Gavin Taylor, Ryan Burmeister, Zheng Xu, Bharat Singh, Ankit Patel, Tom Goldstein (2016).
Training Neural Networks Without Gradients: A Scalable ADMM Approach. In ICML2016. arXiv:1605.02026

[2] Ziming Zhang, Yuting Chen, Venkatesh Saligrama (2016).
Efficient Training of Very Deep Neural Networks for Supervised Hashing. In CVPR2016. arXiv:1511.04524

[3] Ziming Zhang, Matthew Brand (2017).
Convergent Block Coordinate Descent for Training Tikhonov Regularized Deep Neural Networks. In NIPS2017. arXiv:1711.07354

4. 収束保証

BCDアルゴリズムでは、$\bar{\mathcal{L}}$ が局所解に収束することが、比較的広い条件のもとで示されています。

4.1. Kurdyka-Łojasiewicz (KL)条件

最近の非凸最適化の論文では、目的関数に課す正則条件としてKurdyka-Łojasiewicz (KL) propertyというものがトレンドになっているようです。まず定義を書きます

記号

(凸とは限らない) 関数 $f: \mathbb{R}^d \to \mathbb{R}\cup \{ + \infty \}$ の $x \in \mathbb{R}^d$ における劣勾配 $g \in \partial f(x)$ とは $(x_k, g_k) \to (x, g)$ となる点列が存在して、$f(x_k) \to f(x)$ かつ
$$
f(x^\prime) \geq f(x_k) + \langle g_k, x^\prime - x_k \rangle + o(\lVert x^\prime - x_k \rVert_2)
$$
が成り立つことをいう (正確な定義は この文献 など)。劣勾配の集合 $\partial f(x)$ を $x$ における $f$ の劣微分という．

$\partial f(x)$ が空でない $x \in \mathbb{R}^d$ の集合を $\mathrm{dom}(\partial f)$ と書く。また、
$$
\mathrm{dist}(0, \partial f(x)) := \min\{ \lVert g \rVert_2: g \in \partial f(x) \}
$$
とする。

定義：KL条件

関数 $f: \mathbb{R}^d \to \mathbb{R} \cup \{ + \infty \}$ が点 $x^* \in \mathrm{dom}(\partial f)$ においてKL propertyをもつとは、3つ組

  • $\eta \in (0, +\infty]$
  • $x^*$ の近傍 $U$
  • 凹関数 $\varphi: [0, \eta) \to \mathbb{R}_+$

が存在して以下の条件を満たすことをいう：

  1. $\varphi(0) = 0$, $\varphi$ は $(0, \eta)$ で $C^1$ 級
  2. 任意の $s \in (0, \eta)$ に対して $\varphi^\prime(s) > 0$
  3. 任意の $x \in U \cap \{ x: f(x^*) < f(x) < f(x^*) + \eta \}$ に対して、次の Kurdyka-Łojasiewicz不等式 が成り立つ
    $$
    \varphi^\prime(f(x) - f(x^*)) \mathrm{dist}(0, \partial f(x)) \geq 1.
    $$

KL不等式が何を言っているかというのが問題ですね。KL条件の意味についてはこのスライド がわかりやすいです。(確か、以前tmaeharaさんに教えていただいたものです)

まず、$0 \in \partial f(x)$ というのは $x$ が $f$ の停留点であるということなので、逆に $\mathrm{dist}(0, \partial f(x))$ が大きいならば点 $x$ において $f$ が大きく傾いているということを表します。もし $f$ の等高線でスライスした領域 $\{ x: a < f(x) < b \}$ において一様に $\mathrm{dist}(0, \partial f(x)) \geq c > 0$ が成り立つのであれば、関数の「谷」のような部分に向かって急に落ち込んでいるものと考えられます。

(図は Bolte(2015) から引用)

この性質が成り立つとき、$f$ はこのスライスにおいてsharpである、ということにします。もし $f$ がsharpであれば、近接点法のようなアルゴリズムは有限ステップで「谷底」のような部分に到達できます (ラフな証明は Bolte(2015) p.17)。

KL条件は、本質的には
$$
\mathrm{dist}(0, \partial(\varphi\circ (f(x) - f(x^*)))) \geq 1
$$
と等価です。これは、凹関数 $\varphi$ によって、等高線のスライスを高さ $f(x^*)$ の「谷底」に近づける速さをコントロールしたときにsharpと見做せる、ということを述べています。よって、なんとなくですが、$f$ 自身が凸でなくても、谷底に到達する何らかの手段は手に入るような感じがします。

KL条件を満たす関数

重要な点は、実はかなり多くの関数がKL条件を満たすことがわかります。というか、「KL条件を満たす関数がたくさんある」ということそのものがこの理論の根幹をなす結果になっているようです。

  • 解析関数はKL条件を満たす。
  • グラフが半代数的集合になる関数を半代数的関数 (semialgebraic function) という。すべての半代数的関数はKL条件を満たす。
  • 半代数的関数は有限個の和や積、合成などの操作で閉じる。

例えば、2次関数やReLUなどは半代数的関数なのでKL条件を満たします。よって、それらの和・積・合成によってできている訓練損失もKL条件を満たすことが示せます (Proposition 1)。

KL条件から何が言えるか

ずばり、近接点法や座標降下法のようなアルゴリズムの収束保証と収束レートの導出に使えます[4] [5]。具体的には、近接点法では $\varphi(s) = c s^(1- \theta)$ ($\theta \in [0, 1)$) のような形をしているとき、$\theta = 0$ なら有限ステップで停留点に収束、$0 < \theta \leq 1/2$ ならば誤差が $O(\exp(-k))$ で収束、$1/2 < \theta < 1$ ならば $O(k^{-(1 - \theta)/(2\theta - 1)})$ で収束、という結果が得られており [4]、紹介論文でもこの結果に帰着することで収束レートを出しています。

[4] Hedy Attouch, Jérôme Bolte (2009).
On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming, 116, 5–16. プレプリント

[5] Hedy Attouch, Jérôme Bolte, Benar Fux Svaiter (2013).
Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods. Mathematical Programming, 137, 91–129. URL

4.2. BCDの収束

DNNに対するBCDの収束は次のことが示せます。($\bar{\mathcal{L}}$ の収束であることに注意)

仮定

  • $i = 1, \ldots, T-1$ について、活性化関数 $\sigma_i$ は $L$-Lipschitzである
  • 関数 $\bar{\mathcal{L}}$ はある点でKL条件を満たす。特に、(a) $s_i, r_i$ が半代数的関数であり、(b) 損失関数が2乗損失、ロジスティック損失、ヒンジ損失のいずれかであり、(c) 活性化関数がReLU、シグモイド、線形リンクのいずれかであれば、どの組み合わせでもこの条件は満たされる。

Theorem 2 (要点のみ)
上の仮定が成り立つとする。BCDアルゴリズムの第 $k$ ステップでの出力を $P^k$ とする。

  1. BCDアルゴリズムにおいて、$\mathrm{dist}^2(0, \partial \bar{\mathcal{L}}(P^k))$ のrunning best rate ($k$ステップまでの最良値) は $o(1/k)$ である。
  2. 関数 $\bar{\mathcal{L}}$ がある点において、$\varphi(s) = c s^{1 - \theta}$ に対してKL条件を満たすならば、停留点への収束レートが得られる。

5. 結論

現在、「GPUに廃課金して勾配法で殴る」という手法が主流になっていると思われますが、これを機に今後はgradient-freeな手法にも期待できるかもしれません。

(参考)

Backpropしないニューラルネット入門 (1/2)

はじめに

最近、統数研で行われた関数推論のワークショップを聴講したり、面白いarXiv論文に出会ったりしまして、深層学習の理論への個人的な関心が高まってきました。そこで、いくつか関心があることをブログにまとめようと思います。

タイトルはほぼ釣りですが、

  • 今回は「最適化マターをすべて無視した場合の汎化理論」
  • 次回は「Backpropしない最適化手法」

という予定なので、そこまで間違ってはいないつもりです。ちなみに、網羅的なレビューではありません。

汎化というミーム

機械学習の研究は「手法そのものの基礎研究」という側面がありますので、深層学習の研究の目標としては

  1. なぜ深層学習がうまくいっているように見えるのか
  2. どうすれば「理論保証つきで」もっとうまくいくのか

ということはぜひ解明されるべきかと思います。（もちろん、一枚岩の分野ではなく、応用研究が重要です）。

「なぜうまくいくのか」というのは、汎化 (generalization) の理論を掘りすすめるということです。

今までの統計的機械学習は、汎化というパラダイムとともにずっと歩んできました。汎化というのは、「手元にあるデータがとある未知の法則から発生したものであるとき、同じ法則から発生するであろう未来のデータをうまく説明できる能力」です。もう少し現場で使われている表現だと、test accuracyが良くなる状態というのが汎化といえます。

そして、よい学習とモデルの複雑さにはトレードオフの関係があります。

  • 理論的には、リスクや汎化誤差の上界に「モデルの大きさ」に相当する項が含まれてしまうため、トレードオフを考慮して モデルはなるべく小さく選ぶ、というのがAIC以来の世界観になっています。
  • 経験的にも、訓練誤差が良いのにテスト誤差がとても悪いという現象（過学習）があることが良く知られていて、モデル選択や正則化といったツールが実務上も欠かせない存在になっています。

しかし、「汎化」や「過学習しないようにモデルは小さく」というのはあくまで ミームではあるものの公理ではなく、現実にはもっと色々なことがありえます。

例えば深層学習では、標準的な意味ではモデルが大きすぎるが、依然としてうまく行っているように見える現象が報告されるなど、従来からの「過学習のストーリー」には乗らない例が増えていますし、それに伴って 汎化の定義を再考する試み なども行われています。要するに、「こういう指針でやればだいたいの場合うまく行く」という思想のようなものをアップデートする必要が出てきている、ということかと認識しています。

2018年の汎化理論：関数クラスの拡大

ここで、ちょっと回帰の問題を考えてみます。

データとして、$(x_i, y_i)$ ($i = 1, \ldots, n$) という入出力ペアが与えられたとします。真の法則は $y_i = f(x_i) + noise$ というな形をしているとして、関数 $f(x)$ を推定する問題を考えます。

ニューラルネットの構造を適当にひとつ固定して、パラメータを変えることで表現できる関数の全体を $\mathcal{F}$ としたとき、最小二乗法によるフィット
$$
\hat{f} \in \arg \min_{f \in \mathcal{F}} \sum_{i=1}^n (y_i - f(x_i))^2
\tag{1}
$$
によって関数を推定することができます。明示的な正則化などは、数式の上ではひとまず考えないことにします。

この最小化問題が厳密に解けたと仮定して、予測誤差の意味でどれだけよいかを考えます。

統計学においては、このような問題は、いわゆるノンパラメトリック回帰と呼ばれている分野の守備範囲でした。ノンパラ回帰の理論は、「関数が滑らかである（与えられた回数微分可能である）」という仮定に負っていた部分が多く、最適性などもその範疇で考えられてきました。しかし、このままでは、ニューラルネットを学習して作った関数$\hat{f}$ が「他と比べてことさらに良い」ことの理由を答えるのが難しくなってしまいます。仮定が現実と合わなくなったケースですね。

そこで、関数が大域的に滑らかであるという仮定から離れ、現実のデータに即して「よりカスタマイズされた関数構造」を考えることでニューラルネットの良さを説明しよう、というアイデアがあります。この流れで、前述の統数研ワークショップ の講演の中から最近の研究を挙げると：

といったように、従来の仮定とは異なる構造をもった関数クラスに対する汎化能力が議論されるようになっています。

ところで、最適化問題 (1) は非凸最適化になり、一般には大域最適解を得ることができません (computableかどうかわからない)。最適化の問題が絡んだ場合の情報はかなり錯綜している印象で、「実はすべての局所解は大域解だから最適化の問題はない」「SGDなどの特定のアルゴリズムが汎化の意味でよい局所解を自動的に選択するから問題ない」などの意見があるようです（文献は割愛）。

感想：何がうまくいっていないか

従来の考え方のままでは、現状何がうまくいかなくなっているのかを考えてみると、要するに

  1. 理論で使われていた仮定が現実と合わなくなった（定式化の欠陥）
  2. 不安定な方法やヒューリスティックスに頼っている（アルゴリズムの欠陥）

ということなんじゃないかなあと思います。

定式化に欠陥があると、理論的に最適な手法と現実に起きていることにズレが生じますし、どんなに解析を精密にしても深層学習が強い理由はそこにはない、ということになってしまいます。そこで、上でレビューしたように、新しい適切な問題設定を探すということが理論面での大きな目標のひとつになるのかな、という所感です。

また、アルゴリズムが不安定だと結果の再現性がなくなってしまいます。そうすると分野全体としても、いろいろな結果から示唆を得て新しい思想を固める作業に時間がかかってしまう気がします。会議の締め切り前になると、エポックごとに誤差が上がった下がったと一喜一憂する人々の姿が世界各地で見られるそうですが、やはり、最適化手法の側にも理論保証がついていないと安心して夜も眠れないのではないかと思います。

というわけで次回はアルゴリズムの話を書きたいです。

SODA'18読み会に参加した

先月ですが、理研AIPでSODA2018読み会なるものが開催されたので、自分も論文を読んできました。

読んだ論文：
Blais, et al. (2018) Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism (URL)

スライド：

内容としては性質検査 (property testing) という分野に属する研究で、与えられたブール関数がk-juntaという性質をもつかどうかを、入力長によらない定数時間で判定するアルゴリズムを提案したものです。（もう少し正確には、tolerant testingという設定で、kの多項式回のクエリアクセスでの検査が可能であることが示された点が新しいです）。

個人的には、SODA (理論CS) の論文にちゃんと触れるのは初めてだったので、どの発表もとても勉強になりました。

機械学習アルゴリズムをテストしたい

動機

論文などを読みながら機械学習のアルゴリズムを実装していると、

  • 出力が浮動小数点数の巨大な配列である
  • 出力がランダムに決まる
  • テストケースに対する正しい出力を手計算するのが不可能
  • そもそもアルゴリズムを自分が理解してない（死）

とかの理由で、書いたコードが正しいかどうか全然わからないです。そして、だいたい正しくないです。

本当は小さい単位でテストしながら書きたいのですが、何がベストプラクティスなのかよく知らないし、とりあえず試したことのメモを蓄積することにしました。

書いたもの（随時更新）

[意訳] FOCS著者へのアドバイス (CS理論系論文の書き方)

この文章は、Boaz Barak教授 (現: Harvard大) による2014年のブログ
Advice for FOCS authors
を意訳したものです。

FOCSは、STOCなどと並ぶコンピュータサイエンスの理論系トップ会議です。情報系の分野ではなぜか、国際会議に採択されることがメインの業績として扱われることが多いです。（論文が論文誌に投稿されないので、他分野から見ると「え、何で論文書いてないの」のような反応がしばしば見受けられます。）

しかし、情報系と一口に言っても、研究の進むスピードは分野によってさまざまです。
機械学習などでは、分野としては非常に速いスピードでトレンドが流れていく印象があります。近年は深層学習ブームと言われていますが、arXivに投稿した論文が次の日に他のグループによって引用されている、というような極端な話を方々で耳にします。そういった時間感覚を持つ分野では、年に一度や二度の国際会議ですら情報の速報性が足りない、ということを言う人もいます。

こういった、「イケてる・速い・競争的・採択率低い」世界に論文を通す技術として、どうやらある特定の方向性のプレゼンテーション能力が要求されてるっぽいぞ、というコンセンサスがなんとなく共有されているように思います。
例えば、下記のredditは一時期流行ったものです。
Tips on publishing in NIPS, ICML or any top tier conferences for ML
内容はほぼほぼ自虐ネタですが、うかつに無視できない部分があったりして大変つらい。
個人的に心が痛いのは2と3でして、

  • 機械学習トップ会議に通すには定理は1つか2つあったほうがいい。内容は問わない。査読者は定理が好きだから。
  • 数学はいいぞ。でもバランスが必要で、数式が多すぎてはだめ。もし数式が多すぎるならCOLT（注：学習理論の会議）に投稿すべきだ。もし数式がないなら、シグモイドとかソフトマックス関数の定義式を別行立て数式で載せときゃいい。

とのこと。

一方、理論系のコミュニティに目を向けると、かなり違う印象を受けます。

CSの理論研究は基本的には「定理と証明」の地道な繰り返しによって成り立っています。よって、どちらかというと数学系の論文誌と似たような精度で、数学的なステートメントの正しさが検証されます。（応用研究では証明が検証されない、という意味ではないです。）
それにもかかわらず、学会の開催頻度は情報系の他の分野と同じです。このため、投稿者はハードな締め切りまでに理論的な貢献を含む論文を書かなければならず、査読者も、一年のある期間に集中して大量の論文を読まなければならないという現象が起きていると考えられます。

表題のブログは、私が把握している限りでは、CS分野の理論研究の論文を書くにあたっての注意点を紹介している数少ない記事でした。特に、情報系の会議文化のなかで、定理と証明が主体の論文を書くというのはどういうことか ということがわかって、個人的には勉強になっています。

以下は引用です。本記事では、導入とサマリーを除いた主要な部分のみを意訳しています。

読者のことを考える

FOCSの投稿論文、そして任意の科学論文を書くにあたって最もチャレンジングなことのひとつは、様々なタイプの読者に同時に対処することです。網羅的ではありませんが、次のようなタイプの読者が含まれると思ってください。

(1) その分野の専門家。あなたのアプローチが彼らの2007年の論文と比べてどう異なるのか、全て詳細に検証したい読者です。
(2) 専門家ではない査読者。あなたのやったことは何なのか、なぜその問題が解きたいのか、論文で使われているテクニックに関して、何らかのとっかかりを掴みたい読者です。
(3) あなたの論文にアサインされたPCメンバー。論文を数分間だけ流し読みして、上記の内容の近似を得たい読者です。

これらの異なる読者に対処するためのおおよその方針としては、前半の数セクションはコンピュータサイエンス理論の一般的な読者でも理解できるように書き、専門家に向けた詳細は後半のセクションに含まれるようにする ことです。この方針は次の視点を導きます。

全力を出せ (Put your best foot forward)

(2014年現在) FOCSにはページ数制限はありませんが、査読者も投稿論文の全てを読まなくてよい規定になっています。これが実際に意味するところは、私が「Impagliazzoのルール」と呼んでいるものに従うべきということです。つまり、任意のXに対して、論文の最初のXページを、読者が次のXページを読みたくなるように書く べきです。

特に、あなたの結果、テクニック、研究の動機、研究が置かれている文脈、および先行研究と比較した新規性が、論文中の早い段階で明確に述べられるように心がけるべきです。もし、主定理を簡潔に述べるのが難しいならば、その主定理の正式でない版または重要な具体例をまず述べて、完全なステートメントが書いてある箇所を後方参照する、という方法があります。

上の方法は結果だけでなくテクニックについても適用できます。あなたの素晴らしいアイデアを、テクニカル・セクションまで取っておく必要はありません。最もよく書けている論文の中には、イントロに続いて “Our techniques”, “Proof outline”, “Warmup”, “Toy problem” といった章が設けてあることがあり、証明の背後にあるアイデアを非正式な形でわかりやすく説明しています。

謙虚さは良いことですが、FOCSの投稿にあたってはそれを徹底する必要はありませんし、あなたの貢献を論文の端っこの方に隠してしまう必要はないのです。逆に、貢献を喧伝しすぎるということも、もちろんしたくありません。

というわけで…

さらけ出せ (Put your worst foot forward)

科学者としては、自分の研究内容について欠陥の可能性・注意点・改善の余地がちゃんと見えるように身をかがめる姿勢をとりたいものです。FOCSの著者にもその姿勢が欠けていないことを期待します。

主結果がとても制限された状況でしか成り立たない、ということが、論文のSection 4を読んだ段階でようやく発覚したりすると、査読者にとってはめちゃくちゃ腹が立ちます。すべての制限・注意点・仮定・限界は論文の早い段階で述べられるべきです。実際、いくつかの注意点は非常にメジャーなので、イントロで言及してもまだ遅いということがあります。例えば、あなたが単調回路 (monotone circuit) でのみ成立する下界を証明した場合、アブストラクトではっきりとそう書くだけでなく、monotone という単語をタイトルに入れるべきです。一般的に、問題をより簡単にするためのモデルの仮定を選んだならばそれについて議論すべきで、別のモデルを選んだ場合にどのような変更点が生じるか説明すべきです。

同様に、先行研究との任意の関係およびオーバーラップは論文の早い段階で述べるべきです。もし、結果が先行研究の一般化であるならば、それらがどのように異なるのか、また、そのような一般化を行う動機について説明しましょう。結果があるパラメータについては改善になっているが、他のパラメータについては改善になっていないのであれば、それらの重要性についての議論を行うことが適切です。関連研究の存在を知っているならば、それが仮に出版されていなかったり、あなたの仕事の後になされていたとしても、なおも引用した上で、それらの関連性や前後関係を説明しましょう。

疑わしきを排除せよ

科学論文は小説ではありません。理想的には、読者が疑いの中にとどまってしまうことや、良い意味でも悪い意味でも驚きが生じたりすることは、起こらないべきです。FOCSのPCメンバーは信じられないくらい才能のある集団ですが、それでもなお、読者が抱きそうなすべての疑問点と誤解を予測しつつ “foolproof” なやり方で論文が書かれるべきです。（特に、限られた時間のなかで40本もの論文を査読しなければならないような読者についてはそうです）。

例えばですが、査読コメントに「主定理の証明はXを使えば非常に簡易化できるだろう」と書いてあって、しかしそのXというのがあなたが最初に試してみてうまくいかなかった方法だったりすると、著者にとっては非常に腹立たしいことだと思います。これを避けるには、 “First attempt” というタイトルの章を設けてXについて議論し、なぜうまくいかないか説明するという方法があります。同様に、一見するとあなたの仕事に関係がありそうだが実際には関係がない論文が存在する場合は、それをなお引用して、なぜ「実際には関係がない」のか説明するべきです。

他には、査読が「シンプルすぎるのでリジェクト」っぽいことを述べているときもムカつきますね。私や他のFOCS PCメンバーは単純さは美徳であると信じていますから、それが原因でリジェクトにすることはありません。しかし、論文が単純すぎて査読者に驚かれるということを避けたいのであれば、証明が先行研究のものに対して「3行の短縮」になっていることを論文の後半のほうで議論します。もし証明が単純なのであれば、それは誇るべきことなので初めからそう言いましょう。もし特定の補題の証明が標準的な手法におけるルーチンの適用であるならば、それは削らずに書くかappendixに移動しましょう。ただし、この場合は証明の最初の部分でそのことを説明し、詳細を追うことをあまり目的としていない査読者が読み飛ばせるようにしましょう。このことは他の場合にも当てはまります。証明中に奇抜な飛躍点 / 些細な点があるならば、そうであることを告げる文章を追加して読者にわかるようにしましょう。

Langevin Monte Carlo法には棄却が必要か

機械学習系のベイズっぽい論文を読んでいると、SGLD [WT11] やSGRLD [PT13] といった文字列を見ることがあります。これらが何かというとマルコフ連鎖モンテカルロ法 (MCMC) の一種で、正規化定数がわからない高次元の確率分布からのサンプリングを得たい場合などに使われます。

アルゴリズムの位置づけとしては、

  • Langevin Monte Carlo (LMC) とか Langevin Dynamics などという名前で呼ばれている既存アルゴリズムがまずあり、
  • それに伴う勾配計算をサブサンプリングを利用して簡略化したもの
    という感じです。勾配降下法 (GD) を確率的勾配降下法 (SGD) に拡張することにインスパイアされているのだったと思います。

LMCのモチベーションとしてよく言われるのは、LMCでは (Metropolis–Hastings法に見られるような) 棄却ステップが必要ないということです。MHは、提案分布がうまく選べていなかったりすると棄却がたくさん発生してしまうことが知られていて、サンプリングに無駄な時間がかかってしまいます。MHの採択確率を（ほとんど）1にするというのは全ベイジアンの夢ですが、ある意味それを達成しているのがLMC系のアルゴリズムです。実際に、SGLDの元論文 [WT11] などでは、「棄却率を低くしたい」という動機がかなり強調して書いてあったりします。

動機だけを聞くとLMCは棄却が要らないという誤解が生じる可能性があるのですが、残念ながらそういうわけではない です。実際には、見た目上は同じアルゴリズムでも、サンプルを得たい分布の性質によって棄却が必要な場合とそうでない場合が存在します（ただし、その理論的な境界線をひとことで説明するのは難しい模様です）。

上のような知識を何度か論文で見かけたことはあったのですが、棄却せずに強行突破すると何が起きてしまうか正直よくわかってなかったです。
なので実際にやってみたというのが本記事の趣旨です。