Abstract＆Introduction｜NUTS(No-U-Turn Sampler)の論文を読む #1

PyMC3などを用いたMCMCベースの手法は所々で利用されていますが、PyMC3ではNUTS(No-U-Turn Sampler)などが元になっています。
NUTSはMetropolis法の発展であるHMC(Hamiltonian Monte Carlo)の拡張として導入されています。
当シリーズではNUTSに関する2011年の論文を確認していきます。

[1111.4246] The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo

#1ではAbstractionとIntroductionの記述を元に論文の概要を掴みます。
以下、目次になります。
1. Abstractの確認
2. Introductionの確認
3. まとめ

1. Abstractの確認
1節ではAbstractの確認を行います。以下各文の和訳とともに解説を行います。

Hamiltonian Monte Carlo (HMC) is a Markov chain Monte Carlo (MCMC) algorithm that avoids the random walk behavior and sensitivity to correlated parameters that plague many MCMC methods by taking a series of steps informed by first-order gradient information. These features allow it to converge to high-dimensional target distributions much more quickly than simpler methods such as random walk Metropolis or Gibbs sampling.

和訳：『ハミルトニアンモンテカルロ(HMC; Hamiltonian Monte Carlo)は1次の勾配情報に基づいて、ランダムウォーク行動やMCMCを行う上で悩ましい相関パラメータへの過敏性を避けるアルゴリズムである。これらの特徴によって(HMCは)、ランダムウォークを用いるMetropolisやGibbs Samplingのような単純な手法よりずっと早く、高次元の目標分布に収束させることができる。』
解説：『まず導入としてハミルトニアンモンテカルロの概要について記載されています。HMCはleap frog algorithmをベースに1次の勾配情報を用いてMCMCの収束を早めることを試みているアルゴリズムです。』

However, HMC’s performance is highly sensitive to two user-specified parameters: a step size ε and a desired number of steps L. In particular, if L is too small then the algorithm exhibits undesirable random walk behavior, while if L is too large the algorithm wastes computation. We introduce the No-U-Turn Sampler (NUTS), an extension to HMC that eliminates the need to set a number of steps L.

和訳：『しかしながら、HMCのパフォーマンスは"step sizeのε"と"ステップ数のL"という二つのユーザー指定のパラメータの影響を強く受けがちである。特に、Lが小さ過ぎる場合においてHMCは望ましくないランダムウォークの挙動を示す一方で、Lが大き過ぎる場合は計算資源の無駄になる。そこで、HMCの拡張としてステップ数のLの設定を不必要にするNUTS(No-U-Turn Sampler)を導入する。』
解説：『HMCの良い点について考える一方で、改善の余地として更新時のステップサイズや繰り返しの回数を手動で設定する必要がある点について言及されています。この解決策としてNUTS(No-U-Turn Sampler)を導入するとされています。』

NUTS uses a recursive algorithm to build a set of likely candidate points that spans a wide swath of the target distribution, stopping automatically when it starts to double back and retrace its steps.

和訳：『NUTSはもっともらしい候補点を構築するにあたって再帰的アルゴリズムを用いている。』
解説：『訳しにくかったので途中からは省略しました。』

Empirically, NUTS perform at least as efficiently as and sometimes more efficiently than a well tuned standard HMC method, without requiring user intervention or costly tuning runs. We also derive a method for adapting the step size parameter ε on the fly based on primal-dual averaging. NUTS can thus be used with no hand-tuning at all. NUTS is also suitable for applications such as BUGS-style automatic inference engines that require efficient “turnkey” sampling algorithms.

和訳：『包括的に見ると、NUTSはユーザーの介入やコストの大きいチューニング実行なしで、よくチューニングされたHMCの手法と少なくとも同様の効率で時には上回る効率を見せた。また手法の派生として、primal-dual averagingに基づいてステップサイズのパラメータのεの適応を行なった。このようにNUTSを用いることで、手動でのチューニングを不要にすることができた。NUTSは、効率的な"turnkey"のサンプリングアルゴリズムを必要とするBUGSに類似する自動推論エンジンのような応用に適している。』
解説：『NUTSのパフォーマンスとして、よくチューニングされたHMCと基本的には同様で時には上回ったとされています。NUTSはHMCのハイパーパラメータのチューニングを減らした手法と考えることもできるので、この時点でプラスだと考えても良さそうです。』

2. Introductionの確認
2節ではIntroductionをパラグラフ単位で確認していきます。

第一パラグラフでは階層ベイズ(Hierarchical Bayesian)のようなモデリングにおいて正確な事後分布の推論は難しいことを受け、近似推論(approximate inference)などにも言及しながらMCMCについて紹介しています。MCMCは時には計算効率があまりよくないものの、汎用的に用いることができるアルゴリズムであることを述べ、NUTSの主題である計算効率向上の背景であることを示唆しています。

第二パラグラフではMCMCの詳細の手法の比較として、random-walk Metropolis[1953]、Gibbs sampling[1984]、Hamiltonian Monte Carlo[2011]などについて紹介しています。この中ではHamiltonian Monte Carloの計算効率が良いとされています。

第三パラグラフではHMCにおいて計算コストがかかる状況として、「①複雑なモデリングにおけるlog-posteriorの勾配の計算について」、「②ステップサイズのεとステップ数のLの設定について」の二つが挙げられています。BUGSやJAGS、PyMCなどの一般的なライブラリに導入するにあたって、この問題について取り組む必要があるとされています。

第四パラグラフでは第三パラグラフで挙げた課題の解決としてNUTSを紹介しています。

3. まとめ
NUTS(No-U-Turn Sampler)の論文を確認するにあたって、#1ではAbstractとIntroductionを確認することで概要を把握しました。
#2では、Section2のHamiltonian Monte Carloについて取り扱っていきます。