読者です 読者をやめる 読者になる 読者になる

最適化(微分可能な解析式があって制約が無い場合)

統計・機械学習

微分可能な解析式がある場合(制約なし)
 →1階微分と2階微分が0になる点を探せばいい
 ・そんな点って?N変量ならN個の偏微分で得られる連立方程式を解けばいい.
  →線形な場合は解けるよね?
   →いやいや.制約ないならそもそも解が無い.
  →非線形な場合は?
   →解析的に解けない場合がほどんど.反復法(勾配法)を使う.
  →局所解に陥らないの?
   →局所探索では当然陥る.但し,凸関数なら大域解が保証できる.
  →凸関数ってどうやって判断できるの?
   →ヘッセ行列(偏微分係数を要素とする行列)が半正定値行列
    ⇔ヘッセ行列の固有値が全て非負.
   →実際は3次以上のヘッセ行列の固有値が全て非負であるか判定する式には変数が残る.
    2次元ならば固有値が変数を含まずに求めることができて,凸性が判定できる.

  *半正定値行列Aの他の性質
   ・A=X^TXとなるXが存在する.
   ・任意のベクトルvに対して,v^TAv = 0となる
    →これって,v'=AvでAを変換したv'と元のベクトルvの内積が0,つまり,変換後の
     ベクトルと変換前のベクトルが直行するってこと?
     つまり,2階微分操作が元のベクトルを直行するベクトルを生むような関数が
     凸関数ってことなのか?

 ・実際に反復法はどうする?
  基本は現在地点xkから,最適値に向かう方向dに少しづつ近づいていく.つまり,
  x(k+1) = x(k) + a・d (dは方向ベクトル)
  ここで,aは学習率.結局はこのdとaをどう選ぶか?ってこと.次の4つの手法が基本.
  1.最急降下法
  2.ニュートン法
  3.準ニュートン法(BFGS法)
  4.共役勾配法(CG法)

 1.最急降下法
  もっとも直感的な勾配法.方向ベクトルdをある地点Xkの勾配(∇f)として求める.
  ∇fは最も傾きの大きい(勾配がきつい)方向ベクトルなので,それにしたがって進める.
  ただ,実際はこれはあんまりうまく行かない場合が多い.ジグザグに進むから,という理由
  が良く説明されているけど,よく分からない・・・.
  もうひとつの理由は学習率をどうするか?って問題が残るから.大きすぎても駄目だし,
  小さすぎてもだめ.で,結局どうするか?っていうとf(x - a∇f)を最も小さくする
  aを求めることになる.これも厳密にやることは難しい.黄金分割法とかで探索する.
  最急降下法でaを学習パラメタとして入力させる方法は固定のaを使うのかな?

 2.ニュートン法
  一回微分(勾配)だけでなく2階微分も使う.具体的には,現在地Xkの周りで2次関数に
  近似して,テイラー展開して,その2次関数の最小値に進む.テイラー展開した関数の
  最小値だから,テイラー展開した式の微分が0ということで,
  ∇^2f(Xk)d = -∇f(Xk)
となるdを選択する.おお!これは学習率aを決めなくていい!っていうのが楽でいい.

 3.準ニュートン法(BFGS法)
  実際は2階微分のヘッセ行列を求めるのが結構たいへん.1階微分と差分ベクトルで近似的に
  やろう,というのが準ニュートン法.そうは言っても,うまい近似は?っていうので
  Broyden等が提案したヘッセ行列の計算式があって,それに従うのがBFGS法.BFGSは提案者の頭文字.
  正直,このヘッセ行列の計算式を導出がわからない...
  欠点はヘッセ行列は変数が大きくなるとメモリを大量に食ってしまう点.
  その点を解決しているのがL-BFGS法と呼ばれる手法.
  *BFGSについては現時点で理解できていない.再勉強が必要.

 4.共役勾配法(CG法)
  これは実装方法は単純に見える.ただ,その意味がニュートン法よりもっと良くわからない.
  最急降下法でジグザグに進んでしまうのを避ける方法らしいが,方向ベクトルの更新式からは
  どうしてそれが実現できているのかルカイできない...
  *数学力が低いのは嘆いても仕様が無い.分からない点まで戻って再学習するよりほか無い.

 で,使うだけならどれがいいか?
 →おそらくCG法だと思われる.
  最急降下法は直感的だが遅い.ニュートン法準ニュートン法は早いかもしれないがメモリを食う.
  CG法はメモリも食わない(勾配ベクトルだけでいい)し,更新処理も軽いと思われる.