多様体上の最適化の概論

Published

2025-02-07

Modified

2025-02-07

最適化問題とは

集合 X 上で定義された実数値関数 f をある集合 \Omega \subset X 上で最小化する問題
- f を目的関数という
- x\in \Omega を制約条件という
  - 変数 x を決定変数という
  - \Omega を実行可能集合といい, x\in \Omega を実行可能界という
無制約最適化問題と, 制約付き最適化問題がある
- \Omega = X のときと, そうでないとき

例えば, n 次元ユークリッド空間 \mathbb{R}^n における制約条件 \mathbf{x}^T \mathbf{x}=1 が定められていると見る代わりに, n 次元球面 S^{n-1} における無制約最適化問題とみなすことができる

ユークリッド空間 \mathbb{R}^n における制約問題では, 最急降下法などの無制約最適化アルゴリズムは使えない
- そのため, 3章で学ぶようなバリア法などを使う必要が生じる
無制約最適化アルゴリズムを多様体上に拡張できれば, 最急降下法などの収束性を引き継ぐことが期待できる

一旦, 多様体の構造は入れずに単に集合として例を挙げる

前提
- n 変量からなるデータが K 個の正規分布が咬合された確率分布から生成されたと仮定する.
- 混合の重みは総和が 1 となる \mathbf{w}=[w_k]_k\in \mathbb{R}^K によって表し
- 各 k=1,2,\ldots ,K に対する重みは w_k>0とし, 多変量正規分布は平均ベクトル \mathbf{\mu}_k\in \mathbb{R}^n, 分散共分散行列 \Sigma_k \in \mathrm{Sym}_{++}(n) を持つものとする

以上の条件のもとで, 最尤推定量を求める問題は次のように定式化される

\Delta_K=\{\mathbf{w}\in \mathbb{R}^K \mid \mathbf{1}_K^T \mathbf{w}=1, \mathbf{w} >0\} とおく
積多様体 \Delta_K\times (\mathbb{R}^n)^K\times (\mathrm{Sym}_{++}(n))^K 上の無条件最適化問題として
目的関数は以下のようになる(対数尤度を取り, 最小化問題なので符号を入れ替えている) f(\mathbf{w}, \mathbf{\mu}_1, \mathbf{\mu}_2,\ldots, \mathbf{\mu}_K, \Sigma_1, \Sigma_2,\ldots, \Sigma_K) = -\sum_{t=1}^T \log\left(\sum_{k=1}^K w_k p(\mathbf{x_t}; \mathbf{\mu}_k, \Sigma_k)\right)

このようにしておくと, ユークリッド空間における最小化問題とみなすよりも, 分散共分散行列が正値対称行列であることが扱いやすいらしい

発展的らしいので一旦スルー