ML day 8: ラグランジュの未定乗数法と制約付き最適化問題
モチベーション
Python機械学習プログラミングの”3.3.5 正則化による過学習への対処”で突然ロジスティック回帰の損失関数に過学習予防のために正則化項を追加する話が出てくるのだが、初見ではなぜ正則化項を追加していいのか、またそれがなぜ過学習を防ぐことに繋がるのかわからなかった。後者は次の記事で具体的に説明するとして、本記事では正則化項を足す(足せる)ことの理論を確認する。
正則化項とラグランジュの未定乗数法
ロジスティック回帰の損失関数は正則化項を追加する前は単純な凸関数であるため、勾配降下法、つまり重みに対して偏微分をすることで局所解を求められる。これは Python機械学習プログラミングをはじめから読んでいれば理解できる。一方で、その損失関数に正則化項を足したときに数学的にどのような問題を解いているのかは端折られているためわかりにくい。これを理解するにはラグランジュの未定乗数法を理解する必要がある。
ラグランジュの未定乗数法は、制約付き最適化問題を解くための数学的手法であり、制約条件を目的関数(この場合は損失関数)に組み込むことによって、制約付き最適化問題を無制約最適化問題に変換し、解を求めることを可能にする。制約付きの最適化問題を解くのは難しいから無制約の最適化問題に変換してしまえば凸関数である限り局所解は偏微分で出せるから嬉しいよねというのがこの手法の味噌だ。
ラグランジュの未定乗数法は目的関数と制約条件の組み合わせで構成され、ラグランジュ乗数を導入して制約条件を表現する。この関数はラグランジュ関数と呼ばれ、一般的に以下の数式で表される。
ここで、f(𝐱)は目的関数、g_i(𝐱)は不等式制約、h_j(𝐱)は等式制約、𝜆_iと𝜇_jはラグランジュ乗数である。
ラグランジュの未定乗数法とKKT条件
KKT条件（Karush-Kuhn-Tucker condition）とラグランジュの未定乗数法は、制約付き最適化問題を解く際に使用される数学的手法である。両者は密接に関連しており、KKT条件はラグランジュの未定乗数法に基づいて非線形制約付き最適化問題の最適解を特徴づけるために用いられる。そして、KKT条件は、非線形制約付き最適化問題の最適解に関する必要条件であり、次の条件を満たす必要がある。
- 勾配条件（stationarity condition）
- 制約付き最適化問題において、最適解（局所最適解）におけるラグランジュ関数の勾配がゼロになること
- 実行可能性条件（primal feasibility）
- 制約条件が満たされること。
- 双対実行可能性条件（dual feasibility）
- ラグランジュ乗数が非負であること。
- 補完スラック条件（complementary slackness）
- ラグランジュ乗数と制約条件の積が0になること。
これらを使うことで、制約条件を目的関数(この場合は損失関数)に組み込むことによって、制約付き最適化問題を無制約最適化問題に変換可能になる。
正則化項があるロジスティック回帰の損失関数を読み解く
以上を踏まえて、本記事の目的だったロジスティック回帰の損失関数と正則化項の式を解釈していく。実際に書籍で唐突に出現している数式
この数式に 1/2n が含まれているが2は微分したときに打ち消されるように都合のいい数字を使っているだけ。nは正則化項を損失と同じスケールにしているだけ。どちらも、定数なのでまるっと無視すれば式 (2) は、
とすることができる。この式 (3) はロジスティック回帰の損失関数と正則化項の和になっているが、これはラグランジュの未定乗数法を使って制約付最適化問題をすでに無制約最適化問題に変換した後の式(ラグランジュ関数)である。つまり式(1)の不等式制約がないラグランジュ関数を考えると元の式は次の制約付きの最小化問題にほかならない。
このとき、R は 正則化パラメータλ で決まる実数である。式 (4) は ラグランジュの未定乗数法により式 (3) に変換できる。つまり、重みのL2ノルムの二乗がλで決まる実数に等しくなるような制約のもとに損失関数が最小になるところを探す問題を解きたかったということだ。こちらの方がイメージはしやすい。式 (4) は意味はわかりやすいものの計算はしにくいからラグランジュの未定乗数法を使って式 (3) のラグランジュ関数に変換しているのだ。ちなみに正則化パラメータがλなのは、ラグランジュ乗数がλだからなのだ。
ラグランジュの未定乗数法の注意点
制約付き最適化問題を無制約最適化問題に変換する利点は、無制約最適化問題の解法（勾配降下法、ニュートン法など）を使用して、制約付き最適化問題の解を求めることができる点である。しかし、KKT条件は局所最適解に対してのみ成立するため、最適解が複数存在する場合や非凸問題の場合は使えない(はず？ちょっと自信がない)。
なるほどわからんというときは・・・
完全に理解しなくてもいいと思う。このYoutube動画はすごくわかりやすかった。
所感
理系の学生は学部で履修する範囲(微積分か線形代数でやったはず)だから自分も例にもれずにラグランジュの未定乗数法は習った。でも、テストの問題を解くために覚えていただけで、現実として何に使うかわかってなかった。こういうときに使うのか。
読んでいる書籍
以下の本の”3.3 ロジスティック回帰”まで読んだ。
