My Enigmaさんに触発されてIntroduction to Applied Linear Algebraを読んだのでそのメモ。ベクトル、行列のあたりは知っていることが多かったので、最小二乗法だけまとめます。

本の内容はPDFファイルで公開されているので、興味のある人は以下のURLから見てください。 http://web.stanford.edu/~boyd/vmls/vmls.pdf

作者: Stephen Boyd,Lieven Vandenberghe
出版社/メーカー: Cambridge University Press
発売日: 2018/06/07
メディア: ハードカバー
この商品を含むブログを見る

線形最小二乗法

最適化すべき変数を $x$ として、以下の問題を考える。

$\min_x ||Ax-b||^2$

この問題の解は、変分法によって以下のように求められる。

$\hat{x} = (A^TA)^{-1} A^Tb$

ここで $(A^ T A)^ {-1} A^ T$ は $A$ の擬似逆行列である。

等式拘束条件がある場合も、線形最小二乗法なら結局のところ擬似逆行列を使う方法に帰着できるので、擬似逆行列が線形最小二乗法のキモと言える。

非線形最小二乗法

以下の問題を扱う。

$\min ||f(x)||^2 \quad \text{s.t.} \quad g(x)=0$

$f(x), g(x)$ はともに非線形関数である。このような場合、線形最小二乗法の場合とは違い、繰り返し計算で解を求めていくしかない。

拘束条件がない場合に、非線形関数の二乗値を最小化する手法として、Gauss-Newton 法とLevenberg-Marquardt 法が紹介されている。これらは非線形関数を逐次的に一次近似して、線形最小二乗法で求めた解で状態変数を更新していく手法である。 Gauss-Newton 法に計算を安定させるための工夫を施したのがLevenberg-Marquardt 法という位置づけ。

ちなみに、本書では、変数 $\lambda$ （ラグランジュ乗数ではない）の導入は、現在のステップの解と次のステップの解の差を小さくするためのものと位置付けられている一方で、書籍「機械学習のための連続最適化」では、正定値性を保証するものとして紹介されている。

また、Newton法は、目的関数のヤコビアンが正方行列のとき、すなわち目的関数の入出力次元が一致するときのGauss-Newton法の特別な形としてみなせるとして紹介されている。

等式拘束条件がある場合のアルゴリズムとしては、ペナルティ法と拡張ラグランジュ法が紹介されている。前者は、拘束条件を評価関数の中に組み込み、拘束条件なしとして問題を解く手法である。後者では、通常のラグランジュ関数ではなく、拡張ラグランジュ関数を最小化する問題を解く。制約なしとみなして次ステップの状態変数を決定するという点はペナルティ法と似ているが、拡張ラグランジュ法では、最適性条件を満たすようにラグランジュ乗数を決定する点が異なる。拡張ラグランジュ法の方がよりよい結果を得られるとのこと。

正直、僕の説明よりも以下の金森先生の資料の方がわかりやすい。 3ページ目の3. 乗数法　の項に記載がある。

数理情報学演習 I 第 10 回等式制約あり最適化問題の解法 – 拡張ラグランジュ関数と乗数法 –

雑記

作成したモデルに過学習が起きているかどうかを調べるには、データを訓練データとテストデータに分けるとよい。両者の誤差に乖離（訓練データの誤差の方が小さい）があれば、過学習が起きている。
- 機械学習でデータを訓練用＆テスト用に分けていた意味がようやくわかった。。
非線形最小二乗法でMNISTを分類すると、人間と同じくらいの性能（誤答率2%）が出る
19.4節の車の非線形制御問題の運動方程式の導出: https://www.springer.com/cda/content/document/cda_downloaddocument/9783319247274-c2.pdf?SGWID=0-0-45-1532785-p177708750のp.12、2.1.4節参照
- 後輪速度 $s$ 、かつ後輪周りの角速度 $\dot{\theta}$ で走行している車の前輪速度はどうなるか？を考えると理解しやすい
- 前輪速度も $s$ では？と勘違いしていたので理解に時間がかかった

参考

myenigma.hatenablog.com