これなら分かる最適化数学 ~第一章 数学的準備~
2019年6月からデータサイエンティストの研修に参加している新参者です。
理論やプログラミングを日々学んでは抜けていってるような気がするので、備忘録として投稿します。
参考書などを読みながら理解をしておりますが、誤解している点や大間違いをしている点などございましたらご指摘いただけますと幸いです。
定理[1.1] 法線ベクトル
曲線f(x, y) =0 \ の点(x,y)のおける法線ベクトルは\nabla fである
これは以下のようにして考えられます。
曲線上のとても近い2つの点$(x_0,y_0),(x_0 + \Delta x, y_0 + \Delta y)$を考えます。
$f(x,y)$上に存在するので、当然
f(x_0, y_0) = 0 ,f(x_0 + \Delta x, y_0 + \Delta y) = 0
上記の2番めの式をテイラー展開すると(2次以降の係数は省略しています)
f(x_0 + \Delta x, y_0 + \Delta y) = f(x_0,y_0) + \frac{\partial f_{0}}{\partial x}\Delta x + \frac{\partial f_{0}}{\partial y}\Delta y + \frac{\partial^2 f_{0}}{\partial x^2}\Delta x^2 + \frac{\partial^2 f_{0}}{\partial x \partial y}\Delta x \Delta y + \cdots
ただし、$f(x_0, y_0) = 0 ,f(x_0 + \Delta x, y_0 + \Delta y) = 0$より、
\frac{\partial f_{0}}{\partial x}\Delta x + \frac{\partial f_{0}}{\partial y}\Delta y + \frac{\partial^2 f_{0}}{\partial x^2}\Delta x^2 + \frac{\partial^2 f_{0}}{\partial x \partial y}\Delta x \Delta y + \cdots = 0
ここで同じ次数の項に注目すると
\nabla = \left(
\begin{array}{c}
\frac{\partial}{\partial x}\\
\frac{\partial}{\partial y}\\
\end{array}
\right),
\Delta \boldsymbol{x} = \left(
\begin{array}{c}
\Delta x\\
\Delta y\\
\end{array}
\right)
とおくことで、下記のように内積の形で表せる。
(\nabla f_0, \Delta \boldsymbol{x}) + \cdots = 0
したがって、$\nabla f_0$は点$(x_0,y_0)$近傍で曲線に直交する。
これをすべての点$(x,y)$に拡張して、$\nabla f$は曲線$f(x,y)$の法線ベクトルである。
ちなみに、変数がn個ある場合は曲線は曲面になり、テイラー展開と法線ベクトルは下記のようになります。
\begin{eqnarray}
f(x_1 + \Delta x_1,\ \dots \ ,x_n + \Delta x_n)
&=& \sum_{k = 0}^\infty \frac{1}{k!}\left(\Delta x_1 \frac{\partial}{\partial x_1}
+ \cdots + \Delta x_n \frac{\partial}{\partial x_n}\right)^k f
\\
\\
\nabla = \left(
\begin{array}{c}
\frac{\partial}{\partial x_1}\\
\vdots\\
\frac{\partial}{\partial x_n}\\
\end{array}
\right)&,&
\Delta \boldsymbol{x} = \left(
\begin{array}{c}
\Delta x_1\\
\vdots\\
\Delta x_n\\
\end{array}
\right)
\end{eqnarray}
もしかして、これが勾配降下法のお友達ですか?!!
定理[1.5] 一次形式の微分公式
\nabla(\boldsymbol a, \boldsymbol x) = \boldsymbol a
一次形式とは
f = a_1x_1 + a_2x_2 + \cdots + a_nx_n = \sum_{k = 1}^N a_k x_k
の形で書かれる、変数の一次の項のみからなる式です。
これは、ニューラルネットワークの重みとノード間の順伝播の式でみたような、勘違いのような。。。
また、一次形式があるということは二次形式もあります。
\begin{eqnarray}
f = a_{11} x_1^2 &+& a_{22} x_2^2 + \cdots + a_{nn} x_n^2 \\
&+& 2a_{12} x_1 x_2 + 2a_{13} x_1 x_3
+ \cdots 2a_{(n-1)n}x_{n-1}x_n\\
\\
&&ただし、a_{ij} = a_{ji}とする
\end{eqnarray}
また、係数の部分だけを抜き出して、係数行列と呼ぶようです。
$A$は条件より対称行列になっています。
すると、二次形式は
\begin{align*}
f= &(\boldsymbol x, A\boldsymbol x)\\[15pt]
A = \begin{pmatrix}
a_{11} & \cdots & a_{1n}\\
\vdots & \ddots & \vdots \\
a_{n1} & \cdots & a_{nn}
\end{pmatrix}
&,\quad
\boldsymbol x = \left(
\begin{array}{c}
x_1\\
\vdots\\
x_n\\
\end{array} \right)
\end{align*}
簡単に書くことができます。
二次形式の微分公式は、以下のようになります。
\nabla f = \nabla (\boldsymbol x, A\boldsymbol x) = 2A\boldsymbol{x}
これで、簡単に法線ベクトルが求められます。
定理[1.7] 内積と行列の計算則
また、任意のベクトル$\boldsymbol{x}, \boldsymbol{y}$と任意の行列$A$に対して
(A\boldsymbol{x}, \boldsymbol{y}) = (\boldsymbol{x}, A^T\boldsymbol{y})
とすることも可能です。
定理[1.9] 固有値と二次形式の標準変換
$n×n$の対称行列は、n個の固有値$\lambda_1, \lambda_2, \cdots, \lambda_n$を持ち(重解も含めて)、それらはすべて実数です。
これは、下記の固有方程式を解くことから得られるので割愛いたします。
\left| \lambda E \ - \ A\right| = 0
このことを用いて、二次形式を標準形と呼ばれる、円や球の式のような綺麗な形に変換していきます。
\begin{align*}
固有値、固有ベクトルの式:& \quad A\boldsymbol{x} = \lambda \boldsymbol{x}\\
直交行列と固有ベクトル:& \quad U = \begin{pmatrix}
\boldsymbol{u}_1, & \boldsymbol{u}_2, &
\cdots, & \boldsymbol{u}_n
\end{pmatrix}\\[10pt]
固有値分解(スペクトラム分解):&
U^{T} A U =
\left(
\begin{array}{cccc}
\lambda_{1} & 0 & \ldots & 0 \\
0 & \lambda_{2} & \ldots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \ldots & \lambda_{n}
\end{array}
\right)
\end{align*}
とすると、$A$は下記のように書けます。
A = U
\left(
\begin{array}{cccc}
\lambda_{1} & 0 & \ldots & 0 \\
0 & \lambda_{2} & \ldots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \ldots & \lambda_{n}
\end{array}
\right) U^T = U \Lambda U^T
ここで、$\boldsymbol{x}' = U^T \boldsymbol{x}$とおくと、$\boldsymbol{x} = U \boldsymbol{x}'$とかけるので、これを用いて
(\boldsymbol{x},A\boldsymbol{x}) = (U \boldsymbol{x}', AU \boldsymbol{x}')
= (\boldsymbol{x}', U^T A U \boldsymbol{x}')
= (\boldsymbol{x}', \Lambda \boldsymbol{x}')
これは下記の標準形と呼ばれる形になります。
(\boldsymbol{x},A\boldsymbol{x}) = \lambda_1 {x'}^2_1 + \lambda_2 {x'}^2_2 + \cdots + \lambda_n {x'}^2_n
上の方で出てきた二次形式の式が固有値を用いて、こんな簡単に書けると知ったときは感動しました!
この辺のお話に次元削減の姿がチラチラしている気がします。（僕だけですかね?笑）
定理[1.13] 固有値分解と最大値、最小値
前提として、以下のことが記載されていました。
- 対称行列の0でない固有値の個数を、その行列のランクと呼ぶ
- 固有値が全て正の対称行列を正値対称行列 と呼ぶ
- 固有値が0または正の対称行列を半正値対称行列と呼ぶ
ちなみに、これの条件が負に変わったものは負値対称行列と半負値対称行列といいます。
これを用いると、最大値と最小値が簡単にわかります。
Aが半正値対称行列のとき、二次形式(\boldsymbol{x},A\boldsymbol{x})を最小にする単位ベクトル\boldsymbol{x}は\\
Aの最小固有値に対する固有ベクトルであり、(\boldsymbol{x},A\boldsymbol{x})の最小値は行列Aの最小固有値に等しい
「これは、$f$の最小値は固有値の中で最小のものと一致して、そのときの変換元の座標は $\boldsymbol{x} = U \boldsymbol{x}'$から計算できる。」
「最大値の時は、固有値の中で最大のものと一致して、同様に求められる。」と言ってるのだとおもいます。
これによって、2次形式で標準形に変換できた瞬間に最大値と最小値とそのときの座標がまるわかりになります!(多分)
この章で参考にしている本は以下です。
これなら分かる最適化数学 -基礎原理から計算手法まで-