Help us understand the problem. What is going on with this article?

自然勾配法を理解する(古典も、量子も)

はじめに

甘利先生によって提案された、連続最適化のアルゴリズムの1つである自然勾配法について解説します。自然勾配法は最急降下法を発展させた手法です。最急降下法は座標変換に対して不変ではないですが、自然勾配法は座標変換に対して不変です。つまり、どの座標系で考えても全く同じ収束性になります。人が恣意的に選ぶ座標に依らないという意味で、「自然」な手法と考えることができます。

自然勾配法の数学的な部分はよく知らないので、以下の内容はテキトーです。全て雰囲気だけの疑似数学による解説です。

設定

$m$次元のリーマン多様体$\mathcal{M}$が与えられているとします。例えば、$\mathcal{M}$は確率モデルのなす空間です。このとき$\mathcal{M}$上の滑らかな関数$f(\theta)$の極小値を求める連続最適化問題を考えます。

関数$f(\theta)$の$\theta$における勾配を$\nabla f(\theta)$で表します。$\nabla f(\theta)$は$m$次元のベクトルであり、$\theta\to(x_1,\dots,x_m)\in\mathbb{R}^m$という座標系で、成分表示をすると$(\partial^1 f,\dots,\partial^m f)^{\top}$になります。ここで特定の座標系での$f(\theta)$の表示も同じ記号$f$で表していて、$\partial^\mu f$は$\frac{\partial f}{\partial x_\mu}$の略記です。

最急降下法

最も単純な最適化の方法の1つが最急降下法(Gradient descent)です。最急降下法は勾配が最も急になる方向に降下していくことで、最適解を探すアルゴリズムです。このような勾配の情報を利用して、最適解を探すアルゴリズムは一般に勾配法と呼ばれています。以下では$\theta\to(x_1,\dots,x_m)$の座標系において、最急降下法を説明していきます。

最急降下法では、ある初期解$\theta^{(0)}\in\mathcal{M}$からスタートして、座標表示で

x^{(k+1)}_\mu=x^{(k)}_\mu+\alpha^{(k)}dx^{(k)}_\mu

のように点$\theta^{(k)}$を更新させていきます。このとき、$\boldsymbol{d}^{(k)}:=(dx^{(k)}_1,\dots,dx^{(k)}_m)$は降下方向、$\alpha^{(k)}$はステップ幅と呼ばれます。とくに最急降下法で降下方向は

dx^{(k)}_{\mu}=-\frac{\partial f(\theta^{(k)})}{\partial x_\mu}

のように設定されます。とくにステップ幅をWolfe条件を満たすようにしたときには、$k\to\infty$で$\nabla f(\theta^{(k)})\to\boldsymbol{0}$となり、停留点に収束します。

座標変換

次に最急降下法が座標変換に対して、不変でないことを示します。そこで新しい座標系として$(y_1,\dots,y_m)$を考えます。そして、もとの座標系$(x_1,\dots,x_m)$から新しい座標系$(y_1,\dots,y_m)$に変換する関数を$\boldsymbol{\phi}=(\phi_1,\dots,\phi_m)$と表すことにします。つまり、$(y_1,\dots,y_m)=\boldsymbol{\phi}(x_1,\dots,x_m)$です。このとき$f$の勾配について、

\frac{\partial f}{\partial x_\mu}=\sum_\nu\frac{\partial \phi_\nu}{\partial x_\mu}\frac{\partial f}{\partial y_\nu}

が成り立ちます。$J_{~~~\nu}^{\mu}:=\partial^\mu \phi_\nu$を成分とする行列$J$はヤコビ行列と呼ばれます。以下ではヤコビ行列は正則であると仮定します。つまりヤコビ行列には逆行列$J^{-1}$が存在します。

新しい座標系$(y_1,\dots,y_m)$での最急降下法を考えましょう。このときの更新の仕方は、

y^{(k+1)}_\nu=y^{(k)}_\nu+\alpha^{(k)}dy^{(k)}_\nu

で、降下方向は

dy_{\nu}^{(k)}=-\frac{\partial f(\theta^{(k)})}{\partial y_\nu}

になります。このとき$(y_1^{(k)},\dots,y_m^{(k)})=\boldsymbol{\phi}(x_1^{(k)},\dots,x_m^{(k)})$であっても、$(y_1^{(k+1)},\dots,y_m^{(k+1)})=\boldsymbol{\phi}(x_1^{(k+1)},\dots,x_m^{(k+1)})$が成り立つとは限りません。実際$\alpha^{(k)}$が微小であるとして1次まで展開すると、

\begin{align}
\phi_\nu(x^{(k+1)}_1,\dots,x^{(k+1)}_m)
&=\phi_\nu(x^{(k)}_1,\dots,x^{(k)}_m)+\alpha^{(k)}\sum_{\mu}J_{~~~\nu}^{\mu}dx^{(k)}_\mu
\\
&=\phi_\nu(x^{(k)}_1,\dots,x^{(k)}_m)-\alpha^{(k)}\sum_{\mu}J_{~~~\nu}^{\mu}\partial^\mu f(\theta^{(k)})
\\
&=y^{(k)}_\nu+\sum_{\mu,\nu'}J_{~~~\nu}^{\mu}J_{~~~\nu'}^{\mu} dy_{\nu'}^{(k)}
\end{align}

となります。このとき

\begin{align}
y^{(k+1)}_{\nu}=\phi_{\nu}(x^{(k+1)}_1,\dots,x^{(k+1)}_m)
\end{align}

が成り立つためには

\begin{align}
\sum_{\mu}{J_{~~~\nu}^{\mu}} {J_{~~~\nu'}^{\mu}}=\delta_{\nu\nu'}
\end{align}

が必要となりますが、これは一般の$\boldsymbol{\phi}$では成立しません。したがって、最急降下法は座標変換では不変ではありません。

自然勾配法

では本題の自然勾配法について説明します。自然勾配法では勾配方向が、座標系に依存しないように設定します。座標系$(x_1,\dots,x_m)$での点の更新の仕方を

x^{(k+1)}_\mu=x^{(k)}_\mu+\alpha^{(k)}dx^{(k)}_{\mu}

としたときに、これが座標変換で不変であるためには、

dy^{(k)}_{\nu}=\sum_{\mu}J_{~~~\nu}^{\mu}dx^{(k)}_\mu

が成立すれば十分です。これを満たすためには、座標変換で

T_{\mu\mu'}\to\sum_{\mu\mu'}J_{~~~\nu}^{\mu}J_{~~~\nu'}^{\mu'}T_{\mu\mu'}

と変換するテンソル$T_{\mu\mu'}$を導入して、

dx^{(k)}_\mu=-\sum_{\mu'}T_{\mu\mu'}\partial^{\mu'}f

とすれば良いです。

ところでリーマン多様体$\mathcal{M}$上には、計量テンソルと呼ばれるテンソルが存在しています。計量テンソルは多様上の微小な線分の長さ(の2乗)を規定するテンソルです。計量テンソルを$g$と書くことにすれば、$\boldsymbol{d}$で表される微小な曲線の多様体$\mathcal{M}$上での長さは

\sum_{\mu\mu'}g^{\mu\mu'}dx_{\mu}dx_{\mu'}

で与えられます。これは長さなので座標変換で不変です。つまり計量テンソルは、座標変換で

g^{\mu\mu'}\to \sum_{\mu\mu'}(J^{-1})_{~~~\nu}^{\mu}(J^{-1})_{~~~\nu'}^{\mu'}g^{\mu\mu'}

のように変換されます。よって計量テンソルの逆$g^{-1}$は

g_{\mu\mu'}\to\sum_{\mu\mu'}J_{~~~\nu}^{\mu}J_{~~~\nu'}^{\mu'}g_{\mu\mu'}

のように変換されます。ここで、$g_{\mu\mu'}=(g^{-1})^{\mu\mu'}$です。つまり計量テンソルの逆$g^{-1}$は、更新が座標変換で不変であるための条件を満たすのです。そこでリーマン多様体上に自然に定義されている計量テンソルの逆を利用して、座標変換で不変になるようにするのが自然勾配法です。

計量テンソル$g^{\mu\mu'}$が単位行列に一致する場合には、自然勾配法は最急降下法と全く同じになります。また、$g^{\mu\mu'}$が目的関数のHessianに一致する場合には、自然勾配法はNewton法と同じになります。

確率モデルの場合

リーマン多様体の例として、確率モデルが作る統計多様体を考えます。この例では、確率モデルのパラメータが座標系に対応します。標本空間$\Omega$上の確率モデルがパラメータ$\boldsymbol{x}:=(x_1,\dots,x_m)$を用いて、$p(\omega;\boldsymbol{x})$と表されているとします。このとき、この確率モデル全体が多様体$\mathcal{M}$に対応します。

次に計量テンソルとして、どのようなものを選べばよいのかについて考えていきます。確率モデルの距離を測るのに自然な量の一つは、Kullback–Leibler divergenceです。これは$D(P|| Q):=\sum_\omega P(\omega)\log [P(\omega)/Q(\omega)]$のように定義されます。しかし、よく知られているようにKullback–Leibler divergenceには対称性がなく、厳密な意味での距離にはなっていません。そこでKullback–Leibler divergenceと近似的に等しくなるような距離を考えることにします。$p(\omega;\boldsymbol{x})$とパラメータを微小に変化させた$p(\omega;\boldsymbol{x}+\boldsymbol{d})$の間のKullback–Leibler divergenceを計算します。すると、

D(p(\omega;\boldsymbol{x})\|| p(\omega;\boldsymbol{x}+\boldsymbol{d}))
=\frac{1}{2}\sum_{\mu\mu'} g^{\mu\mu'}dx_{\mu}dx_{\mu'}

と展開したとき、$g^{\mu\mu'}$は

g^{\mu\mu'}(\boldsymbol{x})
:=\sum_{\omega}p(\omega;\boldsymbol{x})\frac{\partial \log p(\omega;\boldsymbol{x})}{\partial x^{\mu}}\frac{\partial \log p(\omega;\boldsymbol{x})}{\partial x^{\mu'}}

で与えられます。この$g^{\mu\mu'}$はFisher information metricと呼ばれている量であり、$\mu\leftrightarrow\mu'$の入れ替えで不変な対称テンソルになっています。これが確率モデルのなす多様体における自然な計量テンソルです。各ステップで、この計量テンソルを使って点を更新していくのが、確率モデルに対する自然勾配法になります。

量子状態の場合

最後にリーマン多様体の例として、量子状態のなす空間を考えましょう。量子状態は長さが1の複素ベクトルで表されるので、複素射影空間を考えていることになります。ここでは量子状態が1つ前の例における確率モデルに相当しています。同様に量子状態もパラメータ$\boldsymbol{x}$に依存していて、$|{\psi(\boldsymbol{x})}\rangle$と表されているとします。

量子状態の空間の距離として使われるのは

\gamma(|\psi(\boldsymbol{x})\rangle,|\psi(\boldsymbol{x}')\rangle):=\arccos(|\langle\psi(\boldsymbol{x})|\psi(\boldsymbol{x}')\rangle|)

で定義されるFubini–Study距離です。まず、この距離から導かれる計量テンソルを求めます。1つ前の例と同様に微小な距離だけ離れた2点のFubini–Study距離を計算します。すると、

\gamma(|\psi(\boldsymbol{x})\rangle,|\psi(\boldsymbol{x}+\boldsymbol{d})\rangle)
=\sum_{\mu\mu'} g^{\mu\mu'}(\boldsymbol{x})dx_{\mu}dx_{\mu'}

と展開したとき、$g^{\mu\mu'}$は

g^{\mu\mu'}(\boldsymbol{x})
:=\operatorname{Re}\left(
\langle\partial_{\mu}\psi|\partial_{\mu'}\psi\rangle
-\langle\partial_{\mu}\psi|\psi\rangle\langle\psi|\partial_{\mu'}\psi\rangle
\right)

で与えられます。$\operatorname{Re}$は複素数の実部だけを取り出す演算子です。ここで定義した$g^{\mu\mu'}(\boldsymbol{x})$はFubini-Study metric tensorと呼ばれています。また実部を取る前の

G^{\mu\mu'}(\boldsymbol{x})
:=\langle\partial_{\mu}\psi|\partial_{\mu'}\psi\rangle
-\langle\partial_{\mu}\psi|\psi\rangle\langle\psi|\partial_{\mu'}\psi\rangle

はQuantum Geometric Tensorと呼ばれます。したがってパラメトリックな量子状態に依存した関数に対する自然勾配法では、Fubini-Study metric tensorを用いて更新が行われます。

参考文献

Kashalpha
物理系の大学院生で量子アニーリングを研究しているつもりです。
http://kashalpha.wp.xdomain.jp/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away