CVIMチュートリアル勉強会#11「3. 最小化のための数値計算」

勉強会 最適化

第11回「コンピュータビジョン最先端ガイド」勉強会に参加し，1章バンドルアジャストメントの3. 最小化のための数値計算を発表してきました．


今回の資料をアップロードしました．

CVIM#11 3. 最小化のための数値計算
View more presentations from sleepy_yoshi


前回がカーネル法だったのでのこのこと参加したところ，未発表の人間は発表しろゴルァと幹事のt@kminさんに言われ，ビジョンよくわかんないけれど，最適化の部分はとても興味のある分野だったので，勇気を出して担当をさせて頂くことにしました．

今回のバンドルアジャストメントは，複数のカメラによって撮影された画像を合成したり，特徴点を推定するような問題において，誤差関数 (目的関数) がカメラの位置パラメータと，画像の特徴点という複数のパラメータがあるに依存しているため，非線形最小二乗法を使って解きますよという流れ．

コンピュータビジョンでは割とよくある問題設定らしいのですが，最初は問題設定が全く理解できず，ひとりぽつねんと未知語をググる作業を行っていました．発表は，個人的には議論が盛り上がってとても楽しかったのですが，「正直，最適化とか興味ないんで」という心の声が聞こえてくるような気もしたりしました．長い発表にお付き合いくださり，みなさまありがとうございました．



さて，今回の話は数値計算とか，最適化と呼ばれるようなところ．その中でもコンピュータビジョンでよく扱われる「非線形最小二乗法問題」がメイン．

非線形なので，最小二乗解は閉形式で求めることができず，反復計算を用いる必要がある．そこでみんな大好きニュートン法が出てくるのだけれど，その後，出てくる問題を解消するような手法の紹介が続いている．

発表の流れ

  • ニュートン法
    • ヘッセ行列の計算が大変
  • ガウス・ニュートン法
    • 誤差を二乗和で表現できるからヤコビ行列でヘッセ行列を近似するぜヒャッハァー
  • レベンバーグ・マーカート法
    • 探索初期は勾配を利用して探索効率を向上する
  • 線型方程式の計算
    • 逆行列なんて計算してらんない
    • 対称行列だからコレスキー分解使えるぜヒャッハァー―
  • 疎行列の性質の利用
    • 疎行列データ構造使う
    • 結果が疎になるよう
  • 数値計算ライブラリの紹介

その他メモ (宿題)

@wk77さんや@tsubosakaさんたちを中心に，数値計算のバックグラウンドがある方々から貴重なコメントを頂いたので忘れないうちにメモ．それ以外も気になったところをメモ．できれば時間を見つけて色々やってみたい．

  • Nelder-Mead法の理解
  • テイラー展開の二次近似が怪しいのでフォロー
  • ニュートン法の二次収束の証明
  • 優決定では二乗誤差最小化でパラメータ求めればいい
    • 変数の数 < 方程式の数 の場合には一般には解は存在しないので最小二乗解を利用する
  • クラメル・ラオの下界って中二ぽい名前でかっこいい
  • Neyman-Scott問題
  • フィッシャー情報行列をきちんと理解
  • コレスキー分解の実装
    • ついでに線型方程式のソルバーを実装
  • BLASの実装どれか使ってみる

感想

レベンバーグ・マーカート法で勾配情報を利用するために(A+\lambda I)\delta \mathbf{x} = \mathbf{a}というように単位行列を用いていたけれど，[1]によるとヘッセ行列の対角成分を用いたりもするらしい．また，\lambdaの更新方法もいろいろあるようで，レベンバーグ・マーカート法の実装によって違うらしい．

以前からいろいろ聞いたことはあったけれど，最適化・数値計算まわりはなかなか体系立てて文書化されないノウハウがたくさんあるような気がする．

特に大域的最適解が保証される凸最適化ならともかく，非線形最適化はいかにうまくヒューリスティクスを活用するのかがキモになってくる．[4]が，ずっと積読になっているのでざっと読みたい．

やはり実装してみないとわからないこともあるので名著[5]に沿って色々実装したいなぁ．今年のはじめに最適化まわりを勉強したいと言っていたけれど，ちゃんと腰を据えてやってみたい．

参考文献

今回の資料で紹介したのは以下の二冊．

また最適化関連の本では，以下の文献も参考にした．