1. 本記事について
1.1 モチベーション
機械学習の数学的理論を勉強しているとしばしばラグランジュ未定乗数法を用いる場面があります．私自身，ラグランジュ未定乗数法自体は知っていましたが，それがどのように機械学習の実装時に用いられるのか疑問があったため本記事で備忘録を兼ねてまとめます．
1.2 記事の構成
本記事はまず，ラグランジュ未定乗数法の理論を解説します．次に，ラグランジュ未定乗数法を機械学習で用いる場面を，SVMをメインにサンプルコードを含めつつ紹介します．
1.3 注意点
- 本記事は微積分や線形代数，機械学習についてざっくりと知っている人向けです
- とはいえ，数学的な厳密さを追いかけるわけではありません
- 素人が書いているので間違いがあるかもしれません
2. ラグランジュ未定乗数法の理論
2.1 問題設定
なんらかの$d$変数関数$f(x_1, x_2, ..., x_d)$があるとします．ここで，$f$を制約条件$g(x_1, x_2,...,x_d)=0$のもとで最大化あるいは最小化させたいシーンを考えます．つまり，条件付き極値問題を解きたい状況です．
では，この問題にラグランジュ未定乗数法を適用し，解を求めてみましょう．
2.2 求解
まず，ラグランジュ関数$L(x_1, x_2, ..., x_d)$を定義します．以下のようになります．
$$
L(x_1, x_2, ..., x_d) = f(x_1, x_2, ..., x_d) - \lambda g(x_1, x_2,...,x_d)
$$
ここで，$\lambda$はラグランジュ乗数と呼ばれる数です．$\lambda$を導入することで，ラグランジュ未定乗数法を解くことができます．次に，$L$の偏微分を計算します．すなわち，
$$
\frac{\partial L}{\partial x_1}=0,\frac{\partial L}{\partial x_2}=0,...,\frac{\partial L}{\partial x_d}=0,\frac{\partial L}{\partial \lambda}=0,
$$
を計算します．偏微分をした各式を連立して解き，$x_1, x_2,...,x_d,\lambda$を得ます．こうして得られた$x_1, x_2,...,x_d$が極値候補点というわけです．
注：ラグランジュ未定乗数法で得られた値はあくまで極値候補であり，極大か極小かという議論は値を$f$に代入したり，ヘッセ行列を用いた議論をしないと分かりません．
ではなぜ，ラグランジュ未定乗数法を用いて極値候補を得られるのでしょうか？端的に言えば，$f$と$g$の勾配が平行になる点を探せば良いためです．これについては以下のサイトで分かりやすく解説されているのでご参照ください．
https://mathlandscape.com/lagrange-multiplier/
2.3 例題
例1
まず，次の問題を考えます．
関数$f(x, y) = x^2 + 2y$について，条件$x^2 + y^2 = 1$のもとで極値候補を求める．
以下に解答を示します．
ラグランジュ関数は$L(x,y)= x^2 + 2y - \lambda(x^2 + y^2 - 1)$です．これの偏微分を求めると，
\frac{\partial L}{\partial x} = 2x - 2\lambda x = 0
\frac{\partial L}{\partial y} = 2 - 2\lambda y = 0
\frac{\partial L}{\partial \lambda} = x^2 + y^2 - 1 = 0
となります．これらを解くと，$x=0, y=1, \lambda=1$となります．したがって，極値候補は$f(0, 1) = 2$となります．得られた解を考察します．今回の条件式は円の方程式であるため，有界です．したがって，現段階では，得られた極値候補は極大・極小のどちらの可能性もあります．ここで，ヘッセ行列を計算します．ヘッセ行列$H$は以下の通りです．
H =
\begin{pmatrix}
f_{xx}\,\, f_{yx}\\
f_{xy}\,\, f_{yy}
\end{pmatrix}
=
\begin{pmatrix}
2 \,\, 0\\
0 \,\, 0
\end{pmatrix}
ヘッセ行列より，$f_{xx}>0$であるため，極小値をとることが分かります．このように，ラグランジュ未定乗数法に$+\alpha$の考察をすることで極値候補点が極小なのか極大なのかを判別できます．とはいえ，多くの問題において，極値候補点さえ求まれば十分というシーンが多いです．最適化したい関数$f$が凸関数とかだとなおさらです．
例2
変数の数を増やした場合も考えましょう．
関数$f(x, y, z) = x^2 + y^2 + z^2$について，条件$x + 2y - z = 3$のもとで極値を求める．
以下に解答を示します．
ラグランジュ関数は$L(x,y,z)= x^2 + y^2 + z^2 - \lambda(x + 2y - z - 3)$です．これの偏微分を求めると，
\frac{\partial L}{\partial x} = 2x - \lambda = 0
\frac{\partial L}{\partial y} = 2y - 2\lambda = 0
\frac{\partial L}{\partial z} = 2z + \lambda = 0
\frac{\partial L}{\partial \lambda} = -x - 2y + z + 3 = 0
となります．これらを解くと，$x = \frac{1}{2}, y = 1, z = -\frac{1}{2}, \lambda = 1$となります．したがって，極値候補は$f(\frac{1}{2}, 1,-\frac{1}{2}) = \frac{3}{2}$となります．
得られた解を考察します．今回の条件式は平面の方程式にほかならないため，条件式の範囲は有界ではないです．すなわち，極大値はありません．したがって，今回得られた極値候補は極小値であることが分かります．
3. 機械学習への応用
ここまでで，ラグランジュ未定乗数法の数学的理論を取り上げました．では，機械学習（あるいは深層学習）の分野においてラグランジュ未定乗数法がどのように用いられているのか例を挙げたいと思います．
余談ですが，私はAIという広い主語の言葉を極力使いたくないというこだわりがあるので「機械学習」，「深層学習」という言葉を使いますが，まあざっくりと言うとAI技術でラグランジュ未定乗数法はどのように用いられるのかということです．
3.1 SVM
サポートベクトルマシン(SVM; Support Vector Machine)は何らかのデータを線形分離する手法です（ドイツ語読みだとサポートベクターマシン）．ざっくりとですが定式化しましょう．
$d$次元の入力$\vec{x}=(x_1, x_2, ..., x_d)^{\text{T}}$を，2クラス$(c_1=1, c_2=-1)$のいずれかに分類する関数$g(\vec{x})$を
g(\vec{x}) = \vec{w}^{\text{T}}\,\vec{x} + b
と定義します．ここで，$\vec{w}$は重みベクトル（本記事ではベクトルを縦向きとするため転置している），$b$はバイアス項です．クラス分けの方法は$g(\vec{x})$の符号に応じて，
c_1:\,\, \text{if}\,\, g(\vec{x}) > 0, \,\,\,\,\, c_2:\,\, \text{if}\,\, g(\vec{x}) < 0
とします．また，$g(\vec{x})=0$となる集合は決定境界と呼ばれ，$d-1$次元の超平面となります（例えば，2次元平面上での決定境界は直線です）．しかし，このままだと，$g(\vec{x})$の候補は無数に存在するため決定境界をただ一つに定めるために，サポートベクトルという点を用います．サポートベクトルは各クラスで最も決定境界に近い点のことです．いろいろ難しい話が出てきましたが，まとめると，SVMは以下の問題を解くことに帰着されます．
\text{min}_{\vec{w}, b}\frac{1}{2}||\vec{w}||^2,\,\, \text{subject to:}\,\, c_i(\vec{w}^{\text{T}}\,\vec{x} + b)\geq 1
ここで，$c_i$は，$i$番目の訓練データが属するクラス$(c_1=1,c_2=-1)$です．すなわち，訓練データの属するクラスの符号と分類器の符号が一致するという条件を付けています．また，重みベクトルを最小化する意図は，サポートベクトル間の距離（マージンと呼ぶ）は$\frac{2}{||\vec{w}||}$であり，これを最大化するためには$\vec{w}$を最小化する必要があるためです．この問題はラグランジュ未定乗数法を用いて解くことができます．
ここまでで，SVMの基本的な考えを紹介しました．では，実用例としてSVMを家賃のクラス分類に適用してみましょう．ある地域の一人暮らし用アパートの築年数と駅からの距離を用いて，家賃を2クラスに分類します．データの内訳は以下の通りです．（このデータはフィクションです．）
- データ総数: 12件（高価格帯: 6件，低価格帯: 6件）
- データの次元: 2次元（築年数，駅からの距離）
- クラス数: 2クラス（高価格帯: 10万円以上，低価格帯: 10万円未満）
今回は，Python(Jupyter Notebook)およびscikit-learnを用いてSVMを実装します．まずは，データを可視化します．以下の通りです．
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
from sklearn.svm import SVC
from sklearn.preprocessing import StandardScaler
# training data
c1 = np.array([[5, 5], [6, 5], [7, 7], [8, 10], [9, 10], [10, 5]]) # class1 data (age, time)
c2 = np.array([[11, 15], [12, 17], [13, 15], [20, 14], [25, 16], [30, 20]]) # class2 data (age, time)
# plot
c1_age = c1[:, 0]
c1_time = c1[:, 1]
c2_age = c2[:, 0]
c2_time = c2[:, 1]
plt.figure(figsize=(8, 6))
plt.scatter(c1_age, c1_time, label='high cost', color='blue')
plt.scatter(c2_age, c2_time, label='low cost', color='red')
plt.xlabel('Building age [years]')
plt.ylabel('Time from station [min]')
plt.legend()
plt.grid(True)
plt.show()
データの分布を見ると，左上から右下に決定境界を引けそうですね．では，scikit-learnを用いてSVMを学習します．学習後の結果も可視化します．
# training
x = np.vstack((c1, c2))
y = np.array([0] * len(c1) + [1] * len(c2))
scaler = StandardScaler()
x_scaled = scaler.fit_transform(x)
svm = SVC(kernel='linear', random_state=42)
svm.fit(x_scaled, y)
print('Done')
# plot result
x_min, x_max = x_scaled[:, 0].min() - 0.1, x_scaled[:, 0].max() + 0.1
y_min, y_max = x_scaled[:, 1].min() - 0.1, x_scaled[:, 1].max() + 0.1
plt.figure(figsize=(8, 6))
w = svm.coef_[0]
b = svm.intercept_[0]
x_line = np.linspace(x_min, x_max, 100)
y_line = -(w[0] / w[1]) * x_line - (b / w[1])
plt.plot(x_line, y_line, 'k-', label='Boundary')
scatter = plt.scatter(x_scaled[:, 0], x_scaled[:, 1], c=y, cmap=plt.cm.coolwarm, marker='o', edgecolors='k', s=80)
plt.scatter(svm.support_vectors_[:, 0], svm.support_vectors_[:, 1], s=200, facecolors='none', edgecolors='k', linewidth=1.5, label='Support Vectors')
plt.xlim(x_min, x_max)
plt.ylim(y_min, y_max)
plt.xlabel('Building age (Scaled)')
plt.ylabel('Time from station (Scaled)')
plt.legend()
plt.grid(True)
plt.show()
結果を見ると，いい感じに決定境界を引けていることが分かります．また，サポートベクトルも明示させました．なお，SVM実行時に値の正規化を行っているため実行前の画像と軸のスケールが異なりますがご了承ください．
3.2 その他
詳細を述べることはしませんが，以下のような場面でラグランジュ未定乗数法が用いられます．
- 主成分分析
- 制約付き強化学習
- 制約付き最適化問題全般
まとめ
本記事では，ラグランジュ未定乗数法の基礎理論と機械学習への応用を取り上げました．我々が機械学習ライブラリを使って実装する際に，知らず知らずのうちにラグランジュ未定乗数法のお世話になっているかもしれません．機械学習や深層学習はアルゴリズムの詳細が分からなくても実装可能ですが，やはり分かった方が面白いですし，モデルの信頼性も増すと思うので頑張って紐解いていきたいですね．最後まで読んでいただきありがとうございました．