ラグランジュの未定乗数法は２つの関数の勾配の向きが同じになる点を求めること
機械学習の中でも有名なサポートベクターマシンについて理解するためには、ラグランジュの未定乗数法を理解する必要があります。
ところが、このラグランジュの未定乗数法を理解するのはなかなか厄介です。
そこで、今回はその必要性と、公式の背景を理解できるようになることを目的とします。
偏微分するだけでは制約条件付きの最小化問題は解けない
サポートベクターマシンは、与えられたデータを2つのグループに分類するためのアルゴリズムです。
このアルゴリズムは、ある関数を制約条件の下で最小化する問題に帰着します。
サポートベクターマシンでなくても、制約条件下で関数の最小値を求める問題は多く存在します。
通常、関数の最小値を求めたい場合、その関数の偏微分をゼロと置いた式を解けば求まります。
例えば、
f(x,y)= x2+y2
の最小値を求めたい場合、この関数の偏微分は
∂f(x,y)/∂x = 2x
∂f(x,y)/∂y = 2y
なので、
2x = 0
2y = 0
を解けばx = y = 0となるため、
f(0,0) = 0
が関数f(x,y)の最小値になります。
ところが、これに
g(x,y) = x+y-1 = 0
という制約条件が付くと、もはやこの手法は使えません。
試しに制約条件g(x)に
x = y = 0
を代入してみると、
g(0,0) = 0+0-1 ≠0
なので、制約条件を満たしません。
f(x,y)をxとyで偏微分してゼロと置く方法では、制約条件付きの最小化問題は解けないのです。
ラグランジュの未定乗数法を取り合えず信じて問題を解いてみる
ラグランジュの未定乗数法のアルゴリズム
そこで役に立つ方法がラグランジュの未定乗数法です。
制約条件g(x,y)の下で、関数f(x,y)の最小値を求めたい場合、まず
L(x,y,λ) = f(x,y) – λg(x,y)
というx、y、λの関数Lを作り、
∂L/∂x = 0
∂L/∂y = 0
∂L/∂λ = 0
の3つの偏微分方程式を解けば、f(x,y)を最小にするxとyが求まるという定理です。
まずは、この定理を信じて2つの簡単な例題を解いてみましょう。
例題１
制約条件g(x,y)=x+y-1=0の下で、f(x,y)=x2+y2の最小値を求める。
L(x,y,λ) = f(x,y) – λg(x,y)
= x2+y2 – λ(x+y-1)
∂L/∂x = 2x – λ= 0
∂L/∂y = 2y – λ= 0
∂L/∂λ = -(x+y-1) = 0
これを解くと、
x = y = ½
になります。
よって、f(x,y)の最小値は
f(1/2,1/2)= ½
です。
例題２
制約条件g(x,y)= x2+y2-1/2=0の下で、f(x,y)=x+yの最小値を求める。
L(x,y,λ) = f(x,y) – λg(x,y)
= x+y – λ(x2+y2-1/2)
∂L/∂x = 1 – 2λx = 0
∂L/∂y = 1 – 2λy= 0
∂L/∂λ = -( x2+y2-1/2) = 0
これを解くと、
x = y = ½
になります。
よって、f(x,y)の最小値は
f(1/2,1/2)= 1
です。
２つの例題は同じことを違う角度で見ているだけ
実は、この２つの例題は同じことを違う角度から見ているだけです。
例題１では、固定された直線がある時に、風船を膨らませて丁度直線と接する時の風船の半径を求める問題です。
一方、例題２は、固定された円がある時に、斜めの箸を上げ下げして平行移動させながら、丁度円と接する時の高さ（y切片）を求める問題です。
立体的に見ると勾配の向きが同じになる点を求めている
更に、これを立体的に見てみましょう。
例題１はf(x,y)=x2+y2の最小値を求める問題でした。
上の図ではx-y平面に図を描きましたが、これと垂直方向にz軸があると想像して下さい。
そしてf(x,y)の値をz軸方向にプロットします。
すると、f(x,y)は原点を底とするすり鉢状の形になります。
またg(x,y)はx-y平面のx+y-1の上にそびえ立つ壁になります。
f(x,y)のすり鉢は上開きになっていますが、どこかでg(x,y)の壁とぶつかります。
そして、ぶつかった点で輪切りにすると、f(x,y)とg(x,y)が接しているので、法線ベクトル（勾配）の方向は等しくなります。
例題２はどうでしょうか？
f(x,y)=x+yの値によって、次のような滑り台になります。
一方g(x,y)は原点の上に立つ半径1/√2の円柱になります。
そして、円柱と滑り台がぶつかった点で輪切りにすると、f(x,y)とg(x,y)が接しているので、法線ベクトル（勾配）の方向は等しくなります。
ラグランジュの未定乗数法は２つの関数の勾配の向きが同じになる点を求めること
ここで、もう一度ラグランジュの未定乗数法の公式を見てみましょう。
制約条件g(x,y)の下で、関数f(x,y)の最小値を求めたい場合、まず
L(x,y,λ) = f(x,y) – λg(x,y)
というx、y、λの関数Lを作り、
∂L/∂x = 0
∂L/∂y = 0
∂L/∂λ = 0
の3つの偏微分方程式を解けば、f(x,y)を最小にするxとyが求まるというものでした。
∂L/∂x = 0は、
∂f(x,y)/∂x＝λ∂g(x,y)/∂x
と同じです。
これは、f(x,y)のx方向の勾配と、g(x,y)のx方向の勾配が、絶対値は違うけれども方向は同じということです。
また∂L/∂y= 0は、
∂f(x,y)/∂y＝λ∂g(x,y)/∂y
と同じです。
これは、f(x,y)のy方向の勾配と、g(x,y)のy方向の勾配が、絶対値は違うけれども方向は同じということです。
つまり、f(x,y)とg(x,y)の勾配（法線ベクトル）の方向が同じになる点の条件です。
また、∂L/∂λ = 0は、
g(x,y)=0
と同じです。
これは制約条件を満たす条件ですので、当たり前ですね。
以上より、ラグランジュの未定乗数法の公式は、f(x,y)とg(x,y)の勾配の方向が一致する点を求めていることになります。
これは先に図示したような立体の底面への影で考えているのだと思えば納得できます。
そして例題１ではすり鉢の中を動きながら、問題２では滑り台の上を動きながら二つの平面が接する点を求めているのです。
【例題１】
【例題２】
