はじめに
初めまして。来夏です。大阪大学院で確率微分方程式の統計理論を専攻しています。現在の興味関心は数学を用いた機械学習・最適化のアルゴリズム開発です。
さて、今回は初投稿ということで、自己紹介から入らせていただきましたが、ここから本題、ちょっとtwitterのTLでフォロワーの話を聞いてこの手の話題に関心を持ち、この勉強記録を書いていこうと思います。
本当は積分表現理論のアルゴリズムについて書きたかったんだけど、あっちは論文にしていく説ある関係上現段階でQiita記事にするのは厳しそう。
解析学や確率論ばっかり学んできたので数学科卒なのにガロア理論やガウスボンネの定理すら怪しい状態であるため、とりあえず簡単な定義の復習から入ろうと思います。
幾何学の専門家から見たらなんじゃこりゃって思われるかもしれないけど、微分幾何の記事じゃなくて最適化アルゴリズムの記事なので厳密性は勘弁してください。（予防線）
使いそうな数学の復習
多様体
座標近傍
位相空間$M$に対し、その開集合$U$に対して、ユークリッド空間上の開集合$U'$への同相写像$\phi$があるとき、$(U,\phi)$の組を座標近傍という。
要するに「局所的にユークリッド空間と見なせる」的な？
複数の座標近傍の組$S:=(U_\lambda,\phi_\lambda)_{\lambda\in\Lambda}$において、$U_\lambda$たちが$M$を被覆できているなら、$S$を座標近傍系という
位相多様体
ハウスドルフ空間$M$があるとする。任意の元$a$に対し、それを含む座標近傍が存在するとき、これを位相多様体という。（対象のユークリッド空間が$m$次元なら、これを$m$次元位相多様体と呼ぶ）
可微分多様体
$m$次元位相多様体$M$に対して、任意の座標近傍２つ$(U_1,\phi_1), (U_2,\phi_2)$のうち、$U_1\cap U_2$が空でないものに対して、ユークリッド空間からユークリッド空間への写像$\phi_2\circ \phi_1^{-1}$が、任意の$a\in \phi_1(U_1\cap U_2)$に対して微分可能なら、これを可微分多様体という。
$C^2$級や$C^\infty$級についても同様
接ベクトル空間
B1のとき松本多様体読んだ際はこの辺でつまずいた気がする。
$M$上の点$p$の接ベクトル空間を$T_p M$と書く。局所座標に対して$\phi(p)$の各元への方向微分の線形結合の集合。
微分幾何の記事じゃないので厳密性はご勘弁。松島多様体読んで。
リーマン計量
正定値写像$g_p:T_pM\times T_pM\rightarrow \mathbb{R}$のこと。この関数の値は適宜決め、これを持った多様体を$(M,g)$と書き、リーマン多様体と呼ぶ。
$$g_p=\sum_{i,j}g_p^{ij}dx^i\otimes dx^j$$
これ要は行列表記。
確か多様体上の距離や角度を決める存在だったハズ。
特異値分解
線形代数の復習
$m$行$n$列行列$A$に対して、$m$次ユニタリ行列$U$と$n$次ユニタリ行列$V$が存在して、$$A=U\Sigma V$$と書ける。
ただし$\Sigma$は$n=m$なら$\DeclareMathOperator{\diag}{diag}\diag(\sigma_1,......,\sigma_q)$で、そうでないなら演算が成立するよう適宜ゼロ行列を付け加える。ただし$q=\min(n,m)$
各$\sigma$のことを行列$A$の特異値と呼び、$\{\sigma_i \mid i=1,2,......,q\}$は並び変えを同一視すればAに対して一意に定まる（ここでは降順に並んでいるものとする）。$U,V$には一意性がありません。
この文書では一貫して$n\leq m$を仮定する。
ここで、列ベクトル表記を行い、$U=(u_1,u_2,......,u_m),V=(v_1,v_2,......,v_n)$と書くと、この特異値分解はこう書き下せます。
$$A=\sum^n_{i=1}\sigma_i u_iv_i^T$$
最適化問題
問題設定
この特異値分解は次の最適化問題と密接に絡みます。
$\DeclareMathOperator{\tr}{tr}\text{minimize}:-\tr(U^TAVN)$
$\text{subject to}:U\in\mathbb{R}^{m\times p},V\in\mathbb{R}^{n\times p},U^TU=V^TV=I_p$
$\DeclareMathOperator{\diag}{diag}p(\leq n),A,N(:=\diag(\mu_1,\mu_2,......,\mu_p)(\mu_1 \geq \mu_2 \geq ......\geq \mu_p))$は所与
この最適化問題の解$U.V$がそのまま$A$の特異値分解を行う$U,V$となります。
ところで、この最適化における条件を満たす$U$の集合$St(m,p):=\{ U\in \mathbb{R}^{m\times p} \mid U^TU=I_p \}$は、「シュティーフェル多様体」と呼ばれる。多様体になることの証明は読者の演習問題とする。（いっぺん言ってみたかった）
まどろっこしいけどこの多様体を使って同じ最適化問題を書くと、
$\DeclareMathOperator{\tr}{tr}\text{minimize}:F(U,V) =-\tr(U^TAVN)$
$\text{subject to}:U,V\in St(m,p)\times St(n,p)$
従来の最適化アルゴリズム
ところで、機械学習や最適化をやっている方ならみんな知ってるだろうけど、解析的に最適解が求まるような簡単な問題でなければ、基本的に最適化のアルゴリズムというものは次のような形をしています。
$\mathbb{R}^N$上の最適化アルゴリズム
初期値$x_0\in\mathbb{R}^N$を決定する
for $k=0,1,2,......,$ do
なんらかの手段で移動方向,$\eta_k\in\mathbb{R}^N$と、移動幅$t_k>0$を決定する
$x_{k+1}:=x_k+t_k\eta_k$で値を更新する
end for
ここで、$N$がパラメータの数、$t_k\eta_k$が学習率×損失関数の勾配となるようにおけば、これが機械学習での勾配降下法です。その他特殊な機械学習での最適化アルゴリズムも同様。
ここでは$x$が$\mathbb{R}^N$全体を動けたけど、もしもこれが多様体$M\subset\mathbb{R}^N$上でしか動けないという条件だとどうでしょうか。するとこれは途端に難しくなります。
一番の問題は、いい感じに見繕ったハズの次の値$x_{k+1}:=x_k+t_k\eta_k$、これに対して一般には$x_{k+1}\in M$が成り立たないところです。(場合によっては、$M$が半群ではないかもしれず、そもそも和が定義されない可能性も。まあ今回はユークリッド空間に埋め込まれてるので問題ありませんが)
特異値分解問題は、$N=m\times p + n\times p$と置けば、まさにこの多様体上の最適化問題なわけです。
これを解くためには、リーマン多様体上の最適化問題を解いていく必要があります。
レトラクション
接ベクトルをいい感じに多様体上の移動に変換してくれる写像$R_x:T_xM\rightarrow M$というのを定義しちゃいましょう。これを用いて$$x_{k+1}=R_{x_k}(t_k\eta_k)$$という形で更新することにしてしまえば、多様体から飛び出してしまう問題は解決できます。
この$R$はレトラクションと呼ばれ、$$R_x(0)=x$$$$\frac{d}{dt}R_x(t\eta)|_{t=0}=\eta$$という条件は最低限満たしておいてほしいところ。詳しいレトラクションの定義は[1]をご覧ください。
さて、このレトラクションを用いると、多様体上の最適化問題はこうかけます。
$M$上の最適化アルゴリズム
初期値$x_0\in M$を決定する
for $k=0,1,2,......,$ do
なんらかの手段で移動方向,$\eta_k\in T_{x_k}M$と、移動幅$t_k>0$を決定する
$x_{k+1}:=R_{x_k}(t_k\eta_k)$で値を更新する
end for
ステップサイズは往々にしてアルミホルールで求められます。まずは通常の$\mathbb{R}^N$上でのアルミホルールについて述べ、次にそれを$M$上で通用する形に整形しようと思います。
参考文献
[1]佐藤 寛之,岩井 敏洋,リーマン多様体上の共役勾配法 およびその特異値分解問題への応用(2013)
その他微分幾何の本をいろいろと