月別: 2020年5月

正則化の意味～制約条件付最適化

/ tau / コメントする

疑　問

L2ノルムによるRidge回帰やL1ノルムによるLasso回帰に登場する罰則項。Lpノルムで表現すると次のようになる。

(1)   \begin{equation*} L(\boldsymbol{w}) = E(\boldsymbol{w}) + \alpha \sum_i |w_i|^p \end{equation*}

ここでEは正則化がない場合の下の損失関数、w=(w1, … , wm)は特徴量に対する重みでLは正則化考慮後の損失関数。

このLを最小となるようなwを計算していくことになるのだが、多くの文献やサイトでL1正則化やL2正則化を説明するのに次のような図を使って、制約条件付きの最小化問題としている。

確かに式(1)の形はLagrrangeの未定乗数法に似ているのだが、ここで分からなくなるのが、αがハイパーパラメーターとして設定される点である。未定乗数法の場合、wとαを未知数として、Lを偏微分して解いていくが、ここではαは変数としては用いられない。

考え方

まず、以下のように重みwに対する制約を設定する。

(2)   \begin{equation*} \sum_i |w_i|^p \le \frac{1}{\mu} \qquad (\mu > 0) \end{equation*}

これは、重みのノルムが高々1/μであることを意味している。これを0以下の制約条件として以下のように変形する。

(3)   \begin{equation*} g(\boldsymbol{w}) = \mu \sum_i |w_i|^p - 1 \le 0 \end{equation*}

一般化するとa\sum |w_i|^p + bの形になるが、不等式の両辺をaで割ることで、このような表現とすることは差し支えない。

これを制約条件として、元々の損失関数E(w)を最小化するため、λを導入して不等式制約条件付きのLagrangeの未定乗数法の問題を立てる。

(4)   \begin{align*} &\mathrm{minimize} \quad E(\boldsymbol{w}) \\ &\mathrm{subject~to} \quad g(\boldsymbol{w}) = \mu \sum_i |w_i|^p - 1 \le 0 \\ &\rightarrow \quad M(\boldsymbol{w}, \lambda) = E(\boldsymbol{w}) - \lambda \left( \mu \sum_i |w_i|^p - 1 \right) \end{align*}

ここでKKT条件からλ ≤ 0となるので、ξ = −λ ≥ 0を導入して、以下のように表す。

(5)   \begin{align*} M(\boldsymbol{w}, \lambda) = E(\boldsymbol{w}) + \xi \left( \mu \sum_i |w_i|^p - 1 \right) \end{align*}

以降、冒頭の正則化の式と上記の最小化問題の式を並べる。

(6)   \begin{align*} &L(\boldsymbol{w}) = E(\boldsymbol{w}) + \alpha \sum_i |w_i|^p \\ &M(\boldsymbol{w}, \xi) = E(\boldsymbol{w}) + \xi \left( \mu \sum_i |w_i|^p - 1 \right) \end{align*}

これらをwiで偏微分する。

(7)   \begin{align*} &\frac{\partial L}{\partial w_i} = \frac{\partial E}{\partial w_i} + \alpha \frac{d |w_i|^p}{d w_i} \\ &\frac{\partial M}{\partial w_i} = \frac{\partial E}{\partial w_i} + \xi \mu \frac{d |w_i|^p}{d w_i} \end{align*}

上式から、wに関しては2つの問題は等価と言える。しかしながら、Lの最小化についてはwの解が求まるのに対して、Mの最小化で解を確定するためには、ξを未知数としてこれについても偏微分をとり、未知数と方程式を1つ加えなければならない。どうしてLの最小化だけで最適解が定まるのか。

解　釈

ところで、αはハイパーパラメーターとして外部で設定するのであった。Lに関してはwiの個数分の未知数と方程式となり、wの解が確定する。すなわち、元の正則化の式を解くだけで「最適化された」係数のセットがw空間において1つに定まる。

ここからがミソで、wが求められるとこれを満たす制約条件の境界が定まり、同時に|w|pに対する制約も定まるというのがどうもこの計算の仕組みらしい。

そこで、αを設定した後のながれを追ってみる。

  • αを設定してLを最適化する
  • w = (w1, … , wm)が定まる
  • 点wを通る制約条件の境界g(w) = 0が定まる → Σ|wi|p = μ−1

すなわち、αを設定してLを最適化することで制約条件の境界g = 0が決定され、重みに対する制約の強さμも決まることになる。

なお、α = 0として罰則項の効果をなくす場合のほかは必ず制約条件の境界上で解を求めることになる。一般的なLagrangeの未定乗数法のように、与えられた制約条件と目的関数の関係によって純粋な極値問題となるということはない(後述する∇Eと∇gのgradientの向きの関係からも確認できる)。

ξやμはどのように定まるのか

本来なら生真面目に未定乗数法を解いて求めるはずのξはどこへ行ったのか。

  • 式(7)のノルム項の比較よりα = ξμ
  • αは事前に設定した値で、μはLの計算結果から導出されることから、ξ = μ/αも計算可能
  • なおMについて、点wにおいては∇E = −ξμ∇gが成り立っており、この点でEとgのgradientが平行(−ξμの符号から、両ベクトルは逆向き)

すなわち、ξはμと組み合わさって、境界条件における目的関数Eと制約条件gのgradientの比となっている。

μについては、α = ξμの関係から、αを大きくするとμも大きくなる傾向になりそうである。それにつれて式(2)から重みをより小さく制約する方向に効きそうである。ただしこの場合、ξも変動するので単純な比例関係にはならず、αの値を試行錯誤で変化させて学習効果を確認することになる。

参考サイト

本記事をまとめるにあたって、下記サイトが大変参考になったことに感謝したい。

過学習を防ぐ「正則化」とは？～○×（まるぺけ）つくろーどっとコム

 

 

 

ラグランジュの未定乗数法～不等式制約条件

/ tau / コメントする

概要

不等式制約条件を持つLagrangeの未定乗数法は以下のように表示される(等式条件の場合はこちらを参照)。

(1)   \begin{align*} & \mathrm{maximize/minimize} \quad f(\boldsymbol{x}) \\ & \mathrm{subject~to} \quad g(\boldsymbol{x}) \le 0 \end{align*}

この場合、停留点が制約条件の範囲外にあれば等式条件と同じ問題となり、範囲内にあれば制約条件なしの通常の極値問題となる。

例題

停留点が制約条件の範囲内の場合

停留点が制約条件の境界内にある次のような問題を考える。

(2)   \begin{align*} & \mathrm{minimize} \quad f(x, y) = \left(x - \frac{1}{2} \right)^2 + \left(y - \frac{1}{2} \right)^2 +10 \\ & \mathrm{subject~to} \quad g(x, y) =x^2 + y^2 - 4\le 0 \\ &L(x, y, \lambda) = (x - 1)^2 + (y - 1)^2 + 10 - \lambda (x^2 + y^2 - 4) \end{align*}

この問題を解くのに、まず停留点が制約条件の範囲内にあるかをチェックする。上の式で\lambda=0と置いて最適化問題を解く。

(3)   \begin{gather*} \frac{\partial f}{\partial x} = 2\left(x - \frac{1}{2} \right) = 0 \\ \frac{\partial f}{\partial y} = 2\left(y - \frac{1}{2} \right) = 0 \\ \Downarrow \\ x = y = \frac{1}{2} \end{gather*}

上記の解は制約条件g(x, y) \le 0を満足する。この停留点が極値だということが分かっていれば、これが問題の解ということになる。

 

停留点が制約条件の範囲外の場合

今度は目的関数の停留点が制約条件の境界の範囲外にある問題を考えてみる。

(4)   \begin{align*} & \mathrm{minimize} \quad f(x, y) = (x - 3)^2 + (y-2)^2 +10 \\ & \mathrm{subject~to} \quad g(x, y) =x^2 + y^2 - 4\le 0 \\ &L(x, y, \lambda) = (x - 3)^2 + (y - 2)^2 + 10 - \lambda (x^2 + y^2 - 4) \end{align*}

まず停留点が境界条件の範囲内にあるとして、\lambda = 0として問題を解いてみる。

(5)   \begin{gather*} \frac{\partial f}{\partial x} = 2(x - 3) = 0 \\ \frac{\partial f}{\partial y} = 2(y - 2) = 0 \\ \Downarrow \\ x = 3 , \; y = 2 \end{gather*}

ところがこの解は制約条件g(x, y) \le 0を満足しない。解は制約条件の境界上にあることになるので、\lambda \ne 0の条件でLagrangeの未定乗数法によって解く。

(6)   \begin{gather*} \left\{ \begin{array}{c} \dfrac{\partial L}{\partial x} = 2(x - 3) - 2\lambda x = 0\\ \\ \dfrac{\partial L}{\partial y} = 2(y - 2) - 2\lambda y = 0\\ \\ \dfrac{\partial L}{\partial \lambda} = -(x^2 + y^2 - 4) = 0 \end{array} \right. \quad \Rightarrow \quad \left\{ \begin{array}{c} (1 - \lambda) x = 3\\ (1 - \lambda) y = 2\\ x^2 + y^2 = 4 \end{array} \right. \end{gather*}

\lambda \ne 1として、

(7)   \begin{gather*} x = \frac{3}{1 - \lambda} , \; y = \frac{2}{1 - \lambda} , \; 1 - \lambda = \pm \frac{\sqrt{13}}{2} \\ \left\{ \begin{array}{rll} \lambda &= 1 \mp \dfrac{\sqrt{13}}{2} & \fallingdotseq -0.8028 , \; 2.8028 \\ x &= \pm \dfrac{6}{\sqrt{13}} & \fallingdotseq 1.6641 , \; -1.6641 \\ y &= \pm \dfrac{4}{\sqrt{13}} & \fallingdotseq 1.1094 , \; -1.1094 \\ f(x, y) &= 17 \pm \dfrac{52}{\sqrt{13}} & \fallingdotseq 12.5778 , \; 41.4222 \end{array} \right. \end{gather*}

いずれの解も制約条件g(x, y)=0を満たしており、このうち最小値となる解と目的関数の値は以下の通り。

(8)   \begin{gather*} (x, y, f(x, y)) = \left( \frac{6}{\sqrt{13}} , \frac{4}{\sqrt{13}} , 17 - \dfrac{52}{\sqrt{13}} \right) \fallingdotseq (1,6641, 1.1094, 12.5778) \end{gather*}

λの符号について

有界でない例

以下、制約条件がg(x, y) \le 0で有界でない場合を考える。

最小化問題でgradientが逆向き(極値が制約条件外)

まず、目的関数を最小化する場合を考える。以下の問題では目的関数fの極値が制約条件の範囲外にあり、fとgのgradientがgの境界上で逆向きになる。

(9)   \begin{align*} &\mathrm{minimize} \quad f(x, y) = (x - 1)^2 + (y - 1)^2 \\ &\mathrm{subject~to} \quad g(x, y) = x + y \le 0 \\ &L(x, y, z) = (x - 1)^2 + (y - 1)^2 - \lambda(x + y) \end{align*}

停留点は制約条件の境界上となることから、λ≠0として未定乗数法で解いて以下を得る。λ<0となり、gradientが逆向きであることが現れている(∇f = λ∇g)。

(10)   \begin{equation*} x = 0, \; y = 0, \; \lambda = -2 \end{equation*}

最小化問題でgradientが同じ向き(極値が制約条件内)

次の問題では極値が制約条件の範囲内にあり、fとgのgradientがgの境界上で同じ向きとなる。

(11)   \begin{align*} &\mathrm{minimize} \quad f(x, y) = (x + 1)^2 + (y + 1)^2 \\ &\mathrm{subject~to} \quad g(x, y) = x + y \le 0 \\ &L(x, y, z) = (x + 1)^2 + (y + 1)^2 - \lambda(x + y) \end{align*}

この場合、fの極値は制約条件(緑色)の範囲内にあり、fとgのgradientがgの境界上で同じ向きになる。停留点は制約条件内にあることから、λ=0として制約条件の効果をなくし、単純にfの極値問題を解いて以下を得る(∇f =0)。

(12)   \begin{equation*} x = -1, \; y = -1, \; \lambda = 0 \end{equation*}

最大化問題でgradientが同じ向き(極値が制約条件範囲外)

次に目的関数を最大化する場合を考える。以下の問題では目的関数fの極値が制約条件の範囲外にあり、fとgのgradientがgの境界上で同じ向きになる。

(13)   \begin{align*} &\mathrm{minimize} \quad f(x, y) = - (x - 1)^2 - (y - 1)^2 \\ &\mathrm{subject~to} \quad g(x, y) = x + y \le 0 \\ &L(x, y, z) = - (x - 1)^2 - (y - 1)^2 - \lambda(x + y) \end{align*}

停留点は制約条件の境界上となることから、λ≠0として未定乗数法で解いて以下を得る。λ>0となり、gradientが同じ向きであることが現れている(∇f = λ∇g)。

(14)   \begin{equation*} x = 0, \; y = 0, \; \lambda = 2 \end{equation*}

最大化問題でgradientが逆向き(極値が制約条件範囲内)

次の問題では極値が制約条件の範囲内にあり、fとgのgradientがgの境界上で逆向きとなる。

(15)   \begin{align*} &\mathrm{minimize} \quad f(x, y) = - (x + 1)^2 - (y + 1)^2 \\ &\mathrm{subject~to} \quad g(x, y) = x + y \le 0 \\ &L(x, y, z) = - (x + 1)^2 - (y + 1)^2 - \lambda(x + y) \end{align*}

この場合、fの極値は制約条件(緑色)の範囲内にあり、fとgのgradientがgの境界上で逆向きになる。停留点は制約条件内にあることから、λ=0として制約条件の効果をなくし、単純にfの極値問題を解いて以下を得る(∇f =0)。

(16)   \begin{equation*} x = -1, \; y = -1, \; \lambda = 0 \end{equation*}

λの符号について

以上の4つのパターンをまとめると、以下のようになる。

∇fと∇gが同方向 ∇fと∇gが逆方向
fを最小化 制約条件内
λ = 0,  g(x, y) < 0		 制約条件外(境界上)
λ < 0,  g(x, y) = 0
fを最大化 制約条件外(境界上)
λ > 0, g(x, y) = 0		 制約条件内
λ = 0,  g(x, y) < 0

たとえばfを最大化する場合の条件をまとめて書くと、

(17)   \begin{equation*} g(x, y) \le 0 , \quad \lambda \ge 0 , \quad \lambda g(x, y) = 0 \end{equation*}

これがKKT条件と呼ばれるもの。

ただし上記の場合分けは、最小化問題か最大化問題かによってλの符号が異なっている。さらに未定乗数を求める関数をここではL = f − λgとしたが、L = f + λgとしている場合もあり、このときはまたλの不等号が逆になってややこしい。

KKT条件では、一般にλ ≥ 0とされるが、元の問題が最小化か最大化か、不等式制約条件を正とするか負とするか、未定乗数法の関数形がf − λgかf + λgか、設定条件によってこの符号が反転する。逆に言えば、もともとのKKT条件がλ ≥ 0と示されているので、最小化(あるいは最大化)に対して−∇gとしたり、L = f ± gを使い分けたり、g ⋚ 0の設定を選んだりしている節がある。

KKT条件

不等式制約条件付きの最適化問題において、Lagrangeの未定乗数法を適用する場合の条件は、一般にKKT条件(Karush-Kuhn-Tucker condition)として示されるが、問題設定の形式を明示する必要がある(あるいは最小化問題と最大化問題でλの不等号を反転させた形で示す)。

最大化問題を基本とし、不等式制約条件は0又は負とする。ラグランジュ関数の制約条件項の符号はマイナスとする。

(18)   \begin{align*} &\mathrm{maximize} \quad f(\boldsymbol{x}) \\ &\mathrm{subject~to} \quad g(\boldsymbol{x}) \le 0 \\ &\rightarrow \; \mathrm{maximize} \quad L(\boldsymbol{x}, \lambda) = f(\boldsymbol{x}) - \lambda g(\boldsymbols{x}) \end{align*}

この時、ラグランジュ関数を最大化するKKT条件は

(19)   \begin{gather*} g(x, y) \le 0 \\ \lambda \ge 0\\ \lambda g(x, y) = 0 \end{gather*}

最小化問題の場合には、最大化問題となるように目的関数を反転する。

(20)   \begin{align*} &\mathrm{minimize} \quad f(\boldsymbol{x}) \\ &\mathrm{subject~to} \quad g(\boldsymbol{x}) \le 0 \\ &\rightarrow \; \mathrm{maximize} \quad L(\boldsymbol{x}, \lambda) = - f(\boldsymbol{x}) - \lambda g(\boldsymbols{x}) \end{align*}

あるいは元のままの関数形として、最小化問題とKKT条件を以下のように設定してもよい。

(21)   \begin{gather*} \mathrm{minimize} \quad L(\boldsymbol{x}, \lambda) = f(\boldsymbol{x}) - \lambda g(\boldsymbols{x}) \\ g(x, y) \le 0 \\ \lambda \le 0\\ \lambda g(x, y) = 0 \end{gather*}

参考サイト

本記事をまとめるにあたって、下記サイトが大変参考になったことに感謝したい。