MML
  • 数学プログラミング置き場
  • 数学記号記法一覧
  • 機械学習のための数学
    • 確率論
  • 機械学習・データサイエンス
    • 1. 機械学習・データサイエンス（概要）
    • 2. 機械学習
      • 2.1. 機械学習をこれから始める人へ
      • 2.2. 回帰問題
        • 2.2.1. 線形回帰の基礎
        • 2.2.2. 線形回帰モデルと正則化
        • 2.2.3. 線形基底関数モデル
          • いろいろな基底関数
        • 2.2.4. ベイズ線形回帰モデル
        • 2.2.5. カーネル回帰
        • 2.2.6. ガウス過程回帰
        • 2.2.7. 一般化線形モデル
        • 2.2.8. 一般化加法モデル
        • 2.2.9. 分位点回帰
        • 2.2.10. 3層ニューラルネットワーク
        • 2.2.11. 深層学習
        • 2.2.12. 深層学習とガウス過程
      • 分類問題
        • 線形判別分析
        • SVM
        • カーネルSVM
      • 強化学習
    • 3. データサイエンス
      • 主成分分析
      • 白色化
      • 低ランク行列近似
      • 行列補完
      • NMF
      • スパースモデリング
        • LASSO
          • FISTA
          • ADMM
        • 全状態探索法
    • 4. ニューラルネットワーク
      • CNN
      • GAN
      • VAE
      • GNN
      • word2vec
    • 5. ベイズ推論
      • 確率
      • 確率分布
      • ちょっとだけ振り返って
      • MCMC
      • ギブスサンプリング
      • 変分推論
  • 連続最適化
    • 1. Taylor展開と関数近似
    • 2. Taylorの定理と誤差の評価
    • 3. 最適化問題
    • 4. 直線探索法
      • 4.1. 最急降下法
      • 4.2. Armijo条件・Wolfe条件
      • 4.3. ニュートン法
      • 4.4. 共役勾配法
        • 4.4.1. 原始的な共役勾配法
        • 4.4.2. PRP法
        • 4.4.3. HS法
      • 4.5. 準ニュートン法
        • 4.5.1. DFP法
        • 4.5.2. BFGS法
        • 4.5.3. L-BFGS法
        • 4.5.4. Bryoden family of methods
        • 4.5.5. Broyden法
    • 5. 確率的最適化
      • 5.1. 確率的勾配降下法（SGD）
      • 5.2. 確率的準ニュートン法（SQN）
  • 行列計算
    • QR分解
    • コレスキー分解
    • 一般化コレスキー分解
    • 固有値分解
    • 一般化固有値問題
    • 特異値分解
  • その他
    • 位相限定相関法
  • カーネル法
    • カーネル法（概要）
  • Riemannian最適化
    • Riemann多様体って？
    • Riemannian最適化（概要）
    • 概説
    • 詳説
      • 解析学
      • 線形代数学（反変性・共変性・不変量）
      • テンソル解析
      • リーマン積分と微分形式
      • 位相空間論
      • 多様体論（解析幾何学）
      • Riemann多様体
  • プログラミングサイドブック
    • はじめに
    • Step 0. 勉強の仕方
      • いつ始める？どれくらい勉強する？
      • どうやって勉強する？
      • どこから手をつけたらいい？
    • Step 1. インターネットで調べる
    • Step 2. コンピュータの仕組みを学ぶ
    • Step 3. 開発環境を整える
    • Step 4. プログラミング言語を学ぶ
    • Step 5. 次のステップへ進むには
    • Step 6. 情報科学を学ぶ
  • プログラミング
    • プログラミング（概要）
    • システムの構成
    • サーバーのセットアップ
      • OSセットアップ
        • ユーザの作成
        • SSHの設定
        • ファイアウォールの設定
      • ドメインの取得と設定（Google domain）
    • Dockerによる仮想化
    • サーバーサイド（golang/gin）
    • リバースプロキシの設置（nginx）
    • SSL/TLS（Let's Encrypt）
    • フロントエンド（Elm）
    • Authentication（Firebase）
    • DB（MySQL）
    • KVS（Redis）
  • 数学勉強ノート
    • 0. 数学勉強ノート（概要）
    • 1. 第1群（基礎1）
      • 1.1. 集合
      • 1.2. ファジィ集合
      • 1.3. 論理学
      • 1.4. 位相
      • 1.5. 代数学
        • 1.5.1. 群
        • 1.5.2. 環
        • 1.5.3. 体
      • 1.6. 多様体論
    • 2. 第2群（基礎2）
      • 2.1. 線形代数学
      • 2.2. 解析学
        • 2.2.1. 常微分
        • 2.2.2. 全微分/偏微分
        • 2.2.3. 反変・共変と不変量
        • 2.2.4. リーマン積分
        • 2.2.5. 外微分
        • 2.2.6. ベクトル解析
      • 2.3. 複素解析学
      • 2.4. 圏論
      • 2.5. 測度論
      • 2.6. 確率論
    • 3. 第3群（情報科学）
      • 3.1. 情報理論
      • 3.2. 通信符号理論
      • 3.3. 暗号理論
      • 3.4. グラフ理論
    • 4. 第4群（基礎3）
      • 4.1. 位相幾何学
      • 4.2. 微分幾何学
      • 4.3. 関数解析学
      • 4.4. 偏微分方程式論
      • 4.5. 数値解析学
        • 4.5.1. 常微分方程式
        • 4.5.2. 偏微分方程式
        • 4.5.3. 固有値問題/特異値分解
      • 4.6. 数理統計学
    • 5. 第5群（物理学）
      • 5.1. 古典力学
      • 5.2. 剛体力学
      • 5.3. 流体力学
      • 5.4. 解析力学
      • 5.5. 電磁気学
      • 5.6. 相対性理論
      • 5.7. 熱力学
      • 5.8. 統計力学
      • 5.9. 量子力学
    • 6. 第6群（電気・機械工学）
      • 6.1. 電気回路学
      • 6.2. システム制御理論
    • 7. 第7群（基礎4）
      • 7.1. 情報幾何学
      • 7.2. 確率解析
  • 書籍メモ
    • 書籍メモ（概要）
  • 論文メモ
    • 論文メモ（概要）
    • 線形代数
      • The Matrix Cookbook
      • ON THE EARLY HISTORY OF THE SINGULAR VALUE DECOMPOSITION
      • The tensor rank decomposition
    • 行列分解
      • Probabilistic Matrix Factorization
      • Probabilistic Matrix Factorization with Non-random Missing Data
      • Graph Regularized Non-negative Matrix Factorization for Data Representation
      • Alternating least squares for personalized ranking
    • 連続最適化
      • Quasi-Newton Methods: Superlinear Convergence Without Line Searches for Self-Concordant Functions
    • 確率・統計
      • Statistical inference of Langevin distributionfor directional data
      • Bayesian Inference over the Stiefel Manifold via the Givens Representation
      • あとで読む（Langevin distribution）
    • Riemannian最適化
      • A Broyden Class of Quasi-Newton Methods for Riemannian Optimization
      • Riemannian stochastic quasi-Newton algorithm with variance reduction and its convergence analysis
      • Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
      • Extending FISTA to Riemannian Optimization for Sparse PCA
    • RCD空間
      • On the geometry of metric measure spaces. I
      • On the geometry of metric measure spaces. II
      • Cohomology and other analyticalaspects of RCD spaces
      • Untitled
  • 雑記帳
    • 球面幾何（楕円幾何）
    • 双曲幾何
  • なんかの部屋
    • データの表現について
Powered by GitBook
On this page
  • はじめに
  • Overview
  • 0. 固有値分解
  • 1. 多様体をユークリッド空間に埋め込む
  • 2. ユークリッド空間での勾配を多様体の接ベクトル空間に直交射影する
  • 3. はみ出た点をレトラクションで多様体上に戻す
  • 4. ベクタートランスポートで接ベクトルの足を揃える
  • 5. 多様体にリーマン計量を入れる
  • 最急降下法
  • 共役勾配法
  • L-BFGS法
  • ニュートン法
  • おまけ

Was this helpful?

  1. Riemannian最適化

概説

【編集中】

はじめに

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 5 years ago

Was this helpful?