1. ニュートン法（Newton's Method）
1.1 局所二次モデル
f:\mathbb R^d\to\mathbb R,\qquad f\in C^2,\qquad g=\nabla f(x),\qquad H=\nabla^2f(x)
f(x+\Delta x)\approx f(x)+g^\top\Delta x+\frac12\Delta x^\top H\Delta x
\begin{aligned}
H\succ0\quad&\Longrightarrow\quad
\Delta x=\arg\min_d\left[g^\top d+\frac12d^\top Hd\right]\\
&\Longrightarrow\quad g+H\Delta x=0\\
&\Longrightarrow\quad\Delta x=-H^{-1}g
\end{aligned}
x_{k+1}=x_k-[\nabla^2f(x_k)]^{-1}\nabla f(x_k)
1.2 停留条件の求根
最小点は停留条件 $\nabla f(x)=0$ を満たす。
F(x):=\nabla f(x)=0,\qquad F(x+\Delta x)\approx F(x)+F'(x)\Delta x
F(x)+F'(x)\Delta x=0\quad\Longrightarrow\quad\Delta x=-[F'(x)]^{-1}F(x),\qquad
F'(x)=D(\nabla f)(x)=\nabla^2f(x)
最適化の Newton 法は勾配の零点を求める Newton 法であり、$F$ の Jacobian が $f$ の Hessian になる。
2. Newton–Kantorovich 法
点 $x\in\mathbb R^d$ を、Banach 空間 $\mathcal X$ の元 $u$ に置き換える。
F:\mathcal X\to\mathcal Y,\qquad F(u)=0,\qquad F'(u):\mathcal X\to\mathcal Y\ \ \text{（Fréchet 微分）}
F(u+\Delta u)\approx F(u)+F'(u)\Delta u
\quad\Longrightarrow\quad
F'(u_k)\Delta u_k=-F(u_k),\qquad u_{k+1}=u_k+\Delta u_k
汎関数 $J:\mathcal X\to\mathbb R$ の最小化では、$F=J'$ とおく。
F=J':\mathcal X\to\mathcal X^*,\qquad F'=J''
\quad\Longrightarrow\quad
u_{k+1}=u_k-[J''(u_k)]^{-1}J'(u_k)
J'(u)\leftrightarrow\nabla f(x),\qquad
J''(u)\leftrightarrow\nabla^2f(x),\qquad
[J''(u)]^{-1}\leftrightarrow[\nabla^2f(x)]^{-1}
3. 分布空間上の Newton 的更新
\mathcal P=\left\{p\ge0\;\middle|\;\int p(x)\,\mathrm dx=1\right\},\qquad
\int\delta p(x)\,\mathrm dx=0
摂動をスコア型の接ベクトル $v$ で表す。
v:=\frac{\delta p}{p}\quad\Longrightarrow\quad
\delta p=pv,\qquad\mathbb E_p[v]=\int\delta p\,\mathrm dx=0
T_p\mathcal P=\{v\mid\mathbb E_p[v]=0\},\qquad
g_p(v,w)=\mathbb E_p[vw]\ \ \text{（Fisher–Rao 計量）}
汎関数 $\mathcal J:\mathcal P\to\mathbb R$ の Riemannian gradient と Hessian を使う。
g_p\!\left(\operatorname{grad}_{\mathrm{FR}}\mathcal J(p),v\right)=D\mathcal J(p)[pv],\qquad
\operatorname{Hess}_{\mathrm{FR}}\mathcal J(p)[v]=\nabla^{\mathrm{FR}}_v\operatorname{grad}_{\mathrm{FR}}\mathcal J(p)
更新方向 $v_k$ を解き、retraction $R_p$ で $\mathcal P$ 上の分布に戻す。
\begin{aligned}
\text{Newton 型}&:\quad\operatorname{Hess}_{\mathrm{FR}}\mathcal J(p_k)[v_k]=-\operatorname{grad}_{\mathrm{FR}}\mathcal J(p_k),\\
\text{自然勾配}&:\quad v_k=-\eta\operatorname{grad}_{\mathrm{FR}}\mathcal J(p_k),\\
&\quad\ \ p_{k+1}=R_{p_k}(v_k)
\end{aligned}
4. Hessian の逆と共分散
4.1 Laplace 近似
p(x)\propto e^{-J(x)},\qquad x_*=\arg\min_xJ(x),\qquad H_*=\nabla^2J(x_*)\succ0
\nabla J(x_*)=0\quad\Longrightarrow\quad
J(x)\approx J(x_*)+\frac12(x-x_*)^\top H_*(x-x_*)
\quad\Longrightarrow\quad
p(x)\approx\mathcal N(x;\,x_*,\,H_*^{-1})
\mathcal N(x;\mu,\Sigma)\propto\exp\left(-\frac12(x-\mu)^\top\Sigma^{-1}(x-\mu)\right)
\quad\Longrightarrow\quad
\mu=x_*,\qquad\Sigma^{-1}=H_*,\qquad\Sigma=H_*^{-1}
Hessian は精度行列、その逆は共分散行列に対応する。
4.2 関数空間での平均と共分散
関数 $u$ の事後分布に同じ近似を適用し、結果を Gaussian measure として表す。
J(u)=-\log p(u\mid D),\qquad u_*=\arg\min_uJ(u),\qquad H_*=J''(u_*)
J(u)\approx J(u_*)+\frac12\langle u-u_*,\,H_*(u-u_*)\rangle
\quad\Longrightarrow\quad
u\mid D\approx\mathcal N(u_*,H_*^{-1})=\mathcal{GP}(m_*,K_*),\qquad m_*=u_*,\quad K_*=H_*^{-1}
(K_*\phi)(x)=\int k_*(x,y)\phi(y)\,\mathrm dy
\begin{aligned}
H_*&:\ \text{精度作用素},\\
K_*=H_*^{-1}&:\ \text{共分散作用素},\\
k_*&:\ \text{共分散核}
\end{aligned}
共分散核の代表例は RBF 核である。
k_{\mathrm{RBF}}(x,y)=\sigma_f^2\exp\left(-\frac{\|x-y\|^2}{2\ell^2}\right)
5. Gaussian Process
5.1 有限次元分布の族
平均関数 $m$ と正定値核 $k$ は、任意の有限点集合 $X$ 上のガウス分布を定める。
f_X=(f(x_i))_{i=1}^N,\qquad m_X=(m(x_i))_{i=1}^N,\qquad(K_{XX})_{ij}=k(x_i,x_j),\qquad K_{XX}\succeq0
f\sim\mathcal{GP}(m,k)\quad:\Longleftrightarrow\quad
f_X\sim\mathcal N(m_X,K_{XX})\qquad(\forall X=\{x_1,\ldots,x_N\})
5.2 Gaussian Process 回帰
D_t=\{(x_i,y_i)\}_{i=1}^t,\qquad
y_i=f(x_i)+\varepsilon_i,\qquad
\varepsilon_i\overset{\text{i.i.d.}}{\sim}\mathcal N(0,\sigma_n^2),\qquad
f\sim\mathcal{GP}(m_0,k_0)
X_t=(x_1,\ldots,x_t),\qquad
\mathbf y_t=(y_1,\ldots,y_t)^\top,\qquad
k_0(X_t,x)=(k_0(x_i,x))_{i=1}^t,\qquad
K_t=k_0(X_t,X_t),\qquad
A_t=K_t+\sigma_n^2I
$f(x)$ と $\mathbf y_t$ の同時分布を $\mathbf y_t$ で条件付ける（Rasmussen and Williams, 2006）。
\begin{bmatrix}f(x)\\\mathbf y_t\end{bmatrix}\sim
\mathcal N\left(
\begin{bmatrix}m_0(x)\\m_0(X_t)\end{bmatrix},
\begin{bmatrix}k_0(x,x)&k_0(x,X_t)\\k_0(X_t,x)&A_t\end{bmatrix}
\right)
\begin{aligned}
m_t(x)&=m_0(x)+k_0(x,X_t)A_t^{-1}(\mathbf y_t-m_0(X_t)),\\
k_t(x,x')&=k_0(x,x')-k_0(x,X_t)A_t^{-1}k_0(X_t,x'),\\
s_t^2(x)&=k_t(x,x)
\end{aligned}
f\mid D_t\sim\mathcal{GP}(m_t,k_t)
5.3 事後分布と Newton 法
観測点での関数値 $\mathbf f=f_{X_t}$ の負の対数事後密度を考える。
J(\mathbf f)=\frac12(\mathbf f-\mathbf m)^\top K_t^{-1}(\mathbf f-\mathbf m)+\frac1{2\sigma_n^2}\|\mathbf y_t-\mathbf f\|^2+\text{const},\qquad
\mathbf m=m_0(X_t),\qquad K_t\succ0
\nabla J(\mathbf f)=K_t^{-1}(\mathbf f-\mathbf m)-\sigma_n^{-2}(\mathbf y_t-\mathbf f),\qquad
H=\nabla^2J=K_t^{-1}+\sigma_n^{-2}I\succ0
$J$ は厳密に二次なので、任意の $\mathbf f$ から Newton 法の1ステップで最小点に到達し、Laplace 近似も厳密になる。
\begin{aligned}
\mathbf f-H^{-1}\nabla J(\mathbf f)
&=\mathbf m+\sigma_n^{-2}H^{-1}(\mathbf y_t-\mathbf m)
=\mathbf m+K_tA_t^{-1}(\mathbf y_t-\mathbf m)=m_t(X_t),\\
H^{-1}&=(K_t^{-1}+\sigma_n^{-2}I)^{-1}=K_t-K_tA_t^{-1}K_t=k_t(X_t,X_t)
\end{aligned}
事後平均は Newton 更新の到達点であり、事後共分散は Hessian の逆である。
6. ベイズ最適化
6.1 代理モデルによる逐次決定
評価が高コストで、勾配も Hessian も使えない関数 $f$ を最小化する。
x_*=\arg\min_{x\in\mathcal X}f(x),\qquad f:\mathcal X\to\mathbb R
D_t\xrightarrow{\ \text{GP 回帰}\ }\mathcal{GP}(m_t,k_t)
\xrightarrow{\ \text{獲得関数}\ }\alpha_t
\xrightarrow{\ \arg\max\ }x_{t+1}
\xrightarrow{\ \text{評価}\ }D_{t+1}=D_t\cup\{(x_{t+1},y_{t+1})\}
6.2 獲得関数
f_t^{\mathrm{best}}=\min_{1\le i\le t}y_i,\qquad
f(x)\mid D_t\sim\mathcal N(m_t(x),s_t^2(x)),\qquad
\xi\ge0
Expected Improvement（EI）
EI は、現在の最良値からの改善量の期待値である（Jones et al., 1998）。
I_t(x)=\max\{0,\,f_t^{\mathrm{best}}-\xi-f(x)\},\qquad
\operatorname{EI}_t(x)=\mathbb E[I_t(x)\mid D_t]
\delta_t(x)=f_t^{\mathrm{best}}-\xi-m_t(x),\qquad
z_t(x)=\frac{\delta_t(x)}{s_t(x)},\qquad
s_t(x)>0
$f(x)=m_t(x)+s_t(x)\zeta,\ \zeta\sim\mathcal N(0,1)$ と書くと、$I_t=s_t\max{0,z_t-\zeta}$ となる。
\begin{aligned}
\operatorname{EI}_t(x)
&=s_t(x)\int_{-\infty}^{z_t(x)}(z_t(x)-\zeta)\varphi(\zeta)\,\mathrm d\zeta\\
&=s_t(x)\left[z_t(x)\Phi(z_t(x))+\varphi(z_t(x))\right]\\
&=\delta_t(x)\Phi(z_t(x))+s_t(x)\varphi(z_t(x))
\end{aligned}
EI は平均の改善（活用）と不確実性（探索）のどちらでも増える。
\frac{\partial\operatorname{EI}_t}{\partial\delta_t}=\Phi(z_t)>0,\qquad
\frac{\partial\operatorname{EI}_t}{\partial s_t}=\varphi(z_t)>0
Lower Confidence Bound（LCB）
\operatorname{LCB}_t(x)=m_t(x)-\kappa_ts_t(x),\qquad\kappa_t\ge0,\qquad
\alpha_t=-\operatorname{LCB}_t\quad\Longrightarrow\quad
x_{t+1}=\arg\min_x\operatorname{LCB}_t(x)
7. Newton 法とベイズ最適化の対応
\begin{array}{llll}
\text{Newton 法}: & f,\ \nabla f,\ \nabla^2f\ \text{既知} & \leadsto\ \text{局所二次モデル} & \leadsto\ x_{k+1}=x_k-[\nabla^2f(x_k)]^{-1}\nabla f(x_k)\\[2mm]
\text{ベイズ最適化}: & D_t\ \text{のみ既知} & \leadsto\ \mathcal{GP}(m_t,k_t) & \leadsto\ x_{t+1}=\arg\max_x\alpha_t(x)
\end{array}
Newton 法の代理モデルは $x_k$ の近傍でのみ有効な決定論的モデルであり、次の点はその最小点である。ベイズ最適化の代理モデルは $\mathcal X$ 全体の確率モデルであり、次の点は平均と不確実性の釣り合いで決まる。両者は、GP 回帰の事後分布が負の対数事後密度に対する Newton 法の1ステップで得られる点でつながる。
まとめ
\begin{aligned}
x_{k+1}&=x_k-[\nabla^2f(x_k)]^{-1}\nabla f(x_k),&
u_{k+1}&=u_k-[J''(u_k)]^{-1}J'(u_k),\\
\Sigma&=H_*^{-1}\ \ (\text{Laplace 近似}),&
K_*&=[J''(u_*)]^{-1}\ \ (\text{共分散作用素}),\\
f\mid D_t&\sim\mathcal{GP}(m_t,k_t),&
x_{t+1}&=\arg\max_x\alpha_t(x)
\end{aligned}
参考文献
- Jones, D. R., Schonlau, M., & Welch, W. J. (1998). Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4), 455–492. doi:10.1023/A:1008306431147
- Rasmussen, C. E., & Williams, C. K. I. (2006). Gaussian Processes for Machine Learning. MIT Press. gaussianprocess.org/gpml