概説

【編集中】

はじめに

Riemann多様体上の直線探索法（Absilらの手法）について簡単に解説する。実際、細かいことや理論的背景を気にしなければ実装するのは比較的簡単である。

Overview

ユークリッド空間上の直線探索法からRiemann多様体上の直線探索法（最急降下法、共役勾配法、準ニュートン法など）に拡張する上で気を付ける点は以下の5点である。

  1. 多様体をユークリッド空間に埋め込む

  2. 埋め込んだユークリッド空間上で計算した勾配を多様体の接ベクトル空間に直交射影する

  3. 直交射影した接ベクトルに沿って移動しても多様体からはみ出るのでレトラクションによって多様体上に戻す

  4. 共役勾配法のように多様体上の異なる点で計算した接ベクトルどうしで演算を行う場合はベクタートランスポートによって接ベクトルの足を揃える

  5. 接ベクトルどうしの内積を計算するときはリーマン計量を入れる

実装する際や論文を読む際はこれらの点にさえ気をつけておけば大体理解できる。上記の手法はせいぜいRiemann多様体上の一次の幾何（1階微分）、または一次の幾何で二次の幾何を近似しているだけなのでそこまで難しくないが、ニュートン法に関してはRiemann多様体上の二次の幾何（2階微分）になるので数段は手強くなる。

では順を追って説明する。

0. 固有値分解

今回例題として扱うのは固有値分解である。今回はこの例しか扱わないが、他のケースでもやることは同じで

  1. 想定している多様体は何で、どのようにユークリッド空間に埋め込まれているか

  2. ユークリッド空間の接ベクトル空間から多様体の接ベクトル空間への直交射影$P _ x$はどう定義されるか

  3. レトラクション$R$はどう定義されているか

を確認すれば最急降下法は実装できる。共役勾配法のように近似的に二次の幾何に踏み込むときは追加で

  1. ベクタートランスポート$\mathcal{T}$はどう定義されるか

  2. リーマン計量$g$はどう定義されるか

を確認すればよい。特に isometric ではない通常のベクタートランスポート$\mathcal{T}$は直交射影$P _ x$とレトラクション$R$を用いて構成できるし、多様体がユークリッド空間に埋め込まれていればリーマン計量$g$はユークリッド空間からの誘導計量、すなわち通常の内積を用いて定義できるので、後ろ2点についてはほとんどチェックする必要もない。

1. 多様体をユークリッド空間に埋め込む

Absil本ではユークリッド空間に埋め込める多様体（Stiefel多様体、Grassmann多様体など）を扱っている。多様体上の点を行列で表せるので「行列多様体(matrix manifold)」とも呼んでいる。

2. ユークリッド空間での勾配を多様体の接ベクトル空間に直交射影する

3. はみ出た点をレトラクションで多様体上に戻す

4. ベクタートランスポートで接ベクトルの足を揃える

5. 多様体にリーマン計量を入れる

多様体にリーマン計量を入れるのは同意のもとで行いましょう。

最急降下法

Armijo条件

Wolfe条件

共役勾配法

L-BFGS法

準ニュートン法の中でもL-BFGS法は$m$ステップ前までの勾配を用いてヘシアンの逆行列を近似する効率的な手法。Riemann多様体上の準ニュートン法はBroydenクラス（DFP法やBFGS法）の計算量が軒並みヤバいのでL-BFGS法以外は現実的でない。

L-BFGS法は実装的には共役勾配法に毛が生えたようなもので、追加の注意事項としては$m$ステップ前までの勾配をすべて現在の点までベクタートランスポートしてくるだけである。

ニュートン法

おまけ

本や論文に載っているようなバックトラッキング法で実装しても相当細かく区切らない限り大抵は直線探索に失敗する。しかし探索の区切りを細かくすると計算効率が絶望的に悪化する。

結果と計算速度を改善するための秘密のテクニックがあるのだがこれは秘密なので教えられない（2年後くらいには公開するかもしれない）。

明かせる範囲での分析結果だけは共有しておく。直線探索が失敗する原因は

  1. Armijo条件が厳しすぎる（ステップサイズの上限が小さすぎる）

  2. Wolfe条件が厳しすぎる（ステップサイズの下限が大きすぎる）

の2点である。条件の厳しさは人間が勝手に決めるハイパーパラメータとなっているが、条件を厳しくしすぎると両方の条件を満たす点が存在する領域は非常に小さくなり、バックトラッキング法のような荒い区切りを用いる探索ではその領域を容易にまたいでしまう。

これらの条件は理論的に収束を保証するためには必要だが、実用上は厳しすぎるので、極限まで緩和したほうがよい。特にArmijo条件は更新前の点の近傍で必ず成立するので、無理をしなければArmijo条件を満たす点は必ず見つかる。

また、目的関数がRiemann多様体上で凸関数であることを証明するのは容易ではない。したがって目的関数の素性がわからないまま手法を適用することはよくあるのだが、もしも運悪く目的関数が探索直線に沿って非凸であったならば、Wolfe条件を満たす点が存在する領域は絶望的に小さくなる。愚直に実装した共役勾配法の収束性が再急降下法より悪化するのは、主にWolfe条件を満たす点が見つからないからである。

以上をまとめると

  1. Armijo条件は緩和して用いる

  2. Wolfe条件は満たされなくてもArmijo条件が満たされていればとりあえず更新する

という点に気をつけて直線探索を実装するとよい。Wolfe条件の情報を用いないならば、愚直には緩和したArmijo条件だけを用いておけばよく、記事中のコードではこの愚直な方法を採用している。

PreviousRiemannian最適化（概要）Next詳説

Last updated