主成分分析の定式化

概要

主成分分析では、複数の特徴量を持つデータセットから、そのデータセットの特徴を最もよく表す特徴量軸を発見していく。

ここで「特徴を最もよく表す」ことを数学的に「最も分散が大きくなる」と定義する。そして、分散が最も大きくなるような方向を探すことを目的とする。

ある軸に沿った分散が大きくなるということは、その軸に沿った性質のバリエーションが多いことになる。逆に分散が小さい場合は、その性質を表す数量によっては各データの特徴の違いが判別しにくい。

主成分分析では、分散が最大となるような軸の方向を発見することが目的となる。この軸は元の特徴量の線形和で表現されるもので、各特徴量の係数は、それぞれの特徴量の寄与を表す。

(1)    \begin{align*} \boldsymbol{v} &= a_1 \boldsymbol{x}_1 + \ldosts + a_m \boldsymbol{x_m} \\ &= a_1 \left( \begin{array}{c} \x_1  \\ 0 \\ \vdots \\ 0 \end{array} \right) + \cdots + a_m \left( \begin{array}{c} 0 \\ \vdots \\ 0 \\ x_m \end{array} \right) \\ v &= | \boldsymbol{v} | = a_1 x_1 + \cdots + a_m x_m \end{align*}

以後、複数の特徴量を持つデータを、特徴量を成分とするベクトルでx表し、多数のベクトルデータxiがデータセットを構成しているとする。

最大化すべき分散の導出

多数のデータの中のデータiが空間内の点に対応し、その位置ベクトルをxiであるとする。このxiの成分が特徴量に対応する。長さが1のあるベクトルdが与えられたとき、xidへの射影の長さは以下のように計算される。

(2)    \begin{align*} x_{i | \boldsymbol{d}} = {\boldsymbol{x}_i}^T \boldsymbol{d} = \boldsymbol{d}^T \boldsymbol{x}_i \quad (| \boldsymbol{d} | = 1) \end{align*}

たとえば特徴量が2つなら、2次元で以下のような計算になる。

(3)    \begin{align*} \boldsymbol{x}_i = \left( \begin{array}{C} x_{i1} \\ x_{i2} \end{array} \right) , \quad \boldsymbol{d} = \left( \begin{array}{C} d_1 \\ d_2 \end{array} \right) \end{align*}

(4)    \begin{align*} x_{i | \boldsymbol{d}} = ( d_1 , d_2 ) \left( \begin{array}{c} x_{i1} \\ x_{i2} \end{array} \right) = ( d_1 x_{i1} + d_2 x_{i2} ) \end{align*}

n個のデータ(i = 1~n)について、射影の平均は以下のように計算される。これは全データのベクトルdの方向に沿った値の平均となる。

(5)    \begin{align*} E( x_{i | \boldsymbol{d}} ) = E \left( \boldsymbol{d}^T \boldsymbol{x}_i  \right) = \boldsymbol{d}^T E \left( \boldsymbol{x}_i \right) = \boldsymbol{d}^T \boldsymbol{\mu}_i \end{align*}

これも2次元の場合で確認すると以下の通り。

(6)    \begin{align*} E(x_{i | \boldsymbol{d}} ) &= E\left[ (d1, d2) \left( \begin{array}{c} x_{i1} \\ x_{i2} \end{array} \right) \right] = (d_1, d_2) \left( \begin{array}{c} E(x_{i1}) \\ E(x_{i2}) \end{array} \right) \\ &= (d_1, d_2) \left( \begin{array}{c} \mu_{i1} \\ \mu_{i2} \end{aray} \right) \end{align*}

式(5)を使ってベクトルdの方向に沿ったデータの分散を計算する。

(7)    \begin{align*} V( x_{i | \boldsymbol{d}} ) &= V \left( \boldsymbol{d}^T \boldsymbol{x}_i \right) \\ &= E \left[ \left( \boldsymbol{d}^T \boldsymbol{x}_i - E \left( \boldsymbol{d}^T \boldsymbol{x}_i \right) \right)^2 \right] \\ &= E \left[ \left( {\boldsymbol{d}}^T \left( \boldsymbol{x}_i - E(\boldsymbol{x}_i) \right) \right)^2 \right] \\ &= E \left[ {\boldsymbol{d}}^T (\boldsymbol{x}_i - \boldsymbol{\mu}_i ) (\boldsymbol{x}_i - \boldsymbol{\mu}_i )^T \boldsymbol{d} \right] \\ &= \boldsymbol{d}^T E\left[ (\boldsymbol{x}_i - \boldsymbol{\mu}_i ) (\boldsymbol{x}_i - \boldsymbol{\mu}_i )^T \right] \boldsymbol{d} \\ &= \boldsymbol{d}^T \boldsymbol{\Sigma} \boldsymbol{d} \end{align*}

中央の平均の項が共分散行列Σとなっていることに留意。これより、あるベクトルが与えられたとき、その方向に沿った全データの成分の分散が、そのベクトルと元のデータの共分散行列を使って求めることができる。

こちらを2次元で確認すると以下の通り。

(8)    \begin{align*} &E\left[ (\boldsymbol{x}_i - \boldsymbol{\mu}_i ) (\boldsymbol{x}_i - \boldsymbol{\mu}_i )^T \right] \\ &= E \left[ \left( \begin{array}{c} x_{i1} - \mu_1 \\ x_{i2} - \mu_2 \end{array} \right) (x_{i1} - \mu_1, x_{i2} - \mu_2) \right] \\ &= \left[ \begin{array}{cc} (x_{i1} - \mu_1)^2 & (x_{i1} - \mu_1)(x_{i2} - \mu_2) \\ (x_{i2} - \mu_2)(x_{i1} - \mu_1) & (x_{i2} - \mu_2)^2 \end{array} \right] \end{align*}

分散の最大化

式(8)で計算された分散が最大となるようにベクトルdの方向を決定する。このとき、dの大きさが1であるという制約条件があるため、問題は制約条件付きの最大化問題となる。

(9)    \begin{gather*} {\rm max} \quad \boldsymbol{d}^T \boldsymbol{\Sigma} \boldsymbol{d} \quad \rm{s.t.} \; | \boldsymbol{d} | = 1 \end{gather*}

これをLagrangeの未定乗数法で解いていく。。

(10)    \begin{gather*} L( \boldsymbol{d}, \lambda ) = \boldsymbol{d}^T \boldsymbol{\Sigma} \boldsymbol{d} - \lambda (|\boldsymbol{d}|^2 - 1) = 0 \\ \frac{\partial L}{\partial d_i} = 0 \quad ( {\rm for \; all} \; i ) \end{gather*}

Lagrange関数の第1項については、

(11)    \begin{align*} \boldsymbol{d}^T \boldsymbol{\Sigma} &= \begin{array}{ccc} ( & d_1 V_1 + \cdots + d_n C_{n1} & , \\ & \vdots & ,\\ & d_1 C_{1j} + \cdots + d_n C_{n, j} & , \\ & \vdots & ,\\ & d_1 C_{1n} + \cdots + d_n V_n & ) \end{array} \end{align*}

より、以下のような長い式になる。

(12)    \begin{align*} \boldsymbol{d}^T \boldsymbol{\Sigma d} &= \begin{array}{c} {d_1}^2 V_1 + \cdots  + d_j d_1 C_{j1} + \cdots + d_n d_1 C_{n1} + \\ \vdots \\ d_1 d_j C_{1j} + \cdots + {d_j}^2 V_j + \cdots + d_n d_j C_{nj} + \\ \vdots \\ d_1 d_n C_{1n} + \cdots + d_j d_n C_{jn} + \cdots + {d_n}^2 V_n \end{array} \end{align*}

また第2項の括弧の中については以下のようになる。

(13)    \begin{align*} | \boldsymbol{d} |^2 - 1 = ( {d_1}^2 + \cdots + {d_j}^2 + \cdots + {d_n}^2 ) -1 \end{align*}

これらを前提に、Ldjで微分すると以下のようになる。

(14)    \begin{align*} 2 d_1 C_{1j} + \cdots + 2 d_j V_{j} + \cdots 2 d_n C_{2j} - 2 \lambda d_j = 0 \end{align*}

全てのdjについて考慮した連立方程式を行列形式で表すと以下のようになる。

(15)    \begin{gather*} \boldsymbol{\Sigma d} = \lambda \boldsymbol{d} \\ | \boldsymbol{d} | = 1 \end{gather*}

1つ目の式は共分散行列に関する固有値問題の式で、di (i=1~n)とλn+1個の変数に対してn個の式となる。これに先ほど脇に置いていたdの大きさに関する制約式を加えて式の数もn+1個となり、dλが求められる。

特徴量が2つの場合

特徴量が2つの場合を考え、以下のように記号を定義する。

(16)    \begin{align*} \boldsymbol{\Sigma} = \left( \begin{array}{cc} \sigma_{11} & \sigma_{12} \\ \sigma_{21} & \sigma_{22} \end{array} \right) , \quad \boldsymbol{d} = \left( \begin{array}{c} d_1 & d_2 \end{array} \right) \end{align*}

このとき、分散を最大化する方向の単位ベクトルdを求める方程式は以下のようになる。

(17)    \begin{equation*} \left\{ \begin{array}{l} \left( \begin{array}{cc} \sigma_{11} & \sigma_{12} \\ \sigma_{21} & \sigma_{22} \end{array} \right) \left( \begin{array}{c} d_1 & d_2 \end{array} \right) = \lambda \left( \begin{array}{c} d_1 & d_2 \end{array} \right) \\ {d_1}^2 + {d_2}^2 = 1 \end{array} \right. \end{equation*}

1つ目の式を解くと、

(18)    \begin{equation*} \left\{ \begin{array}{l} \sigma_{11} d_1 + \sigma_{12} d_2 = \lambda d_1 \\ \sigma_{21} d_1 + \sigma_{22} d_2 = \lambda d_2 \end{array} \rhight. \end{equation*}

この方程式は不定なのでd1d2それぞれは求められないが、μ = d2/d1は計算できる。これは固有ベクトルの方向が定まる。具体的には下記の通り。

(19)    \begin{gather*} \left\{ \begin{array}{l} \sigma_{11} + \sigma_{12} \mu = \lambda \\ \sigma_{21} + \sigma_{22} \mu = \lambda \mu \end{array} \right. \\ \lambda = \sigma_{11} + \sigma_{12} \mu = \frac{\sigma_{21}}{\mu} + \sigma_{22} \\ \sigma_{12} \mu^2 + ( \sigma_{11} - \sigma_{22} ) \mu - \sigma_{21} = 0 \end{gather*}

これを解いてベクトルdの方向が定まる。これに制約条件|d|2 =1を加味することで、大きさ1の単位ベクトルとしてdが決定される。

この解き方は最大化問題ではないので、連立方程式から2つの固有ベクトルと固有値が求まる。

第2主成分以降

一般的な固有値問題では、元の変数と同じ数の固有ベクトルと固有値のセットが求まるが、最大化問題として解いた場合には主成分が1つだけ求まる。

scikit-learnのPCAインスタンス生成時にn_componentsで主成分の数に制約をかけることができるが、このことから、PCA.fit()の実行時には連立方程式を解いているのではなく、最大化問題で1つずつ主成分を計算しているのではないかと思われる。

第2主成分以降の計算についての紹介はあまり見られないが、以下の手順と考えらえれる。

  1. 各データについて、第1主成分の方向への射影を計算
  2. その射影の符号を逆にしたベクトルを各データに加える
  3. これで第1主成分に沿ったばらつきが全てゼロになるので、残りの成分の中で最大となるベクトルの方向を計算し、第2主成分とする
  4. 以上を繰り返し、順次最大主成分沿いの情報を消しながら、各主成分を計算

主成分の意味

主成分の意味の一つに、元のデータを構成する成分という捉え方がある。

たとえば特徴量の数がnである元データXがあり、主成分の数をm(<= n)でモデルを構築するとする。scikit-learnでPCAのインスタンスを生成するのにn_components=mと指定し、fit(X)を実行すると、m個の主成分が生成される。この主成分は共分散行列に対する固有ベクトルであり、要素数n個(特徴量数に等しい)の1次元配列がm行(主成分の数に等しい)並んだ2次元配列として、PCAインスタンスのプロパティーcomponents_に保存される。

(20)    \begin{equation*} \tt{components\_} = \left[ \begin{array}{ccc} (p_{0, 0} & \cdots & p_{0, n-1} ) \\ & \vdots &\\ (p_{m-1, 0} & \cdots & p_{m-1, n-1}) \end{array} \right] = \left[ \begin{array}{c} \boldsymbol{p}_0 \\ \vdots \\ \boldsymbol{p}_m \end{array} \right] \end{equation*}

元のデータは、各主成分(固有ベクトル)の重み付き和として表現される。

(21)    \begin{equation*} \boldsymbol{x} = (x_0, ..., x_n) = a_0 \boldsymbol{p}_0 + a_1 \boldsymbol{p}_1 + a_2 \boldsymbol{p}_2 + \cdots \end{equation*}

この様子を2次元で示したのが以下の図で、直行する2つの主成分から元データの1つxが定まる。

xの主成分1、2の方向の大きさはxの各主成分に対する射影で、それらの長さはxと各主成分の内積で得られる。

(22)    \begin{equation*} \boldsymbol{x} = (x_0, ..., x_n) = ( \boldsymbol{x} \cdot \boldsymbol{p}_0 ) \boldsymbol{p}_0 + ( \boldsymbol{x} \cdot \boldsymbol{p}_1 ) \boldsymbol{p}_1 + ( \boldsymbol{x} \cdot \boldsymbol{p}_2 ) \boldsymbol{p}_2 + \cdots \end{equation*}

 

点と直線の距離~媒介変数による愚直な解法

Pと直線lの距離を、媒介変数を通して愚直に求める。具体的には点Pから直線lへの垂線の足Hと点Pの距離となる。

直点をパラメーター表示し、点H(xH, yH)に対応するパラメーターをtHとする。

(1)    \begin{equation*} \left\{ \begin{align} x_H &= u t_H + x_0\\ y_H &= v t_H + y_0 \end{align} \right. \end{equation*}

このとき、直線に沿う方向のベクトルと直線に直角なベクトルを与えられた変数で表示すると以下の通り。

(2)    \begin{equation*} \boldsymbol{d} = \left[\begin{array}{c} u \\ v \end{array}\right] \quad , \quad \boldsymbol{h} = \left[\begin{array}{c} x_H - x_P \\ y_H - y_P \end{array}\right] \end{equation*}

これらのベクトルが直交する条件として内積をゼロとする。

(3)    \begin{gather*} \boldsymbol{d} \cdot \boldsymbol{h} = 0 \\ u(x_H - x_P) + v(y_H - y_P) = 0 \\ u(u t_H + x_0 - x_P) + v(v t_H + y_0 - y_P) = 0 \\ (u^2 + v^2)t_H + ux_0 + vy_0 - ux_P - vy_P = 0 \end{gather*}

これから点Hに対する直線のパラメーターが得られる。

(4)    \begin{equation*} t_H = \frac{u(x_P - x_0) + v(y_P - y_0)}{u^2 + v^2} \end{equation*}

このパラメーターを使ってHの座標を表示すると以下の通り。

(5)    \begin{equation*} \left\{ \begin{align} x_H &= u t_H + x_0 = \frac{u(u x_P + v y_P) + v(v x_0 - u y_0)}{u^2 + v^2} \\ y_H &= v t_H + y_0 = \frac{v(u x_P + v y_P) - u(v x_0 - u y_0)}{u^2 + v^2} \\ \end{align} \right. \end{equation*}

Pと直線lの距離はベクトルhの大きさとなる。

(6)    \begin{equation*} |\boldsymbol{h}|^2 = (x_H - x_P)^2 + (y_H- y_P)^2 \end{equation*}

以下、それぞれの項を計算していく。

(7)    \begin{equation*} \left\{ \begin{align} x_H - x_P &= \frac{v^2(x_0 - x_P) + uv(y_P-y_0)}{u^2 + v^2}\\ y_H - y_P &= \frac{u^2(y_0 - y_P) + uv(x_P-x_0)}{u^2 + v^2}\\ \end{align} \reigh. \end{equation*}

(8)    \begin{equation*} \left\{ \begin{align} (x_H - x_P)^2 &= \frac{v^4(x_0 - x_P)^2 + u^2v^2(y_P-y_0)^2 + 2uv^3(x_0 - x_P)(y_P - y_0)}{(u^2 + v^2)^2}\\ (y_H - y_P)^2 &= \frac{u^4(y_0 - y_P)^2 + u^2v^2(x_P-x_0)^2 + 2u^3v(y_0 - y_P)(x_P - x_0)}{(u^2 + v^2)^2}\\ \end{align} \reigh. \end{equation*}

これらの結果から以下を導く。

(9)    \begin{align*} |\boldsymbol{h}|^2 &= (x_H - x_P)^2 + (y_H - y_P)^2 \\ &= \frac{ \begin{array}{l} \phantom{+}v^2(u^2+v^2)(x_0 - x_P)^2 \\ + u^2(u^2+v^2)(y_0 - y_P)^2 \\ - 2uv(u^2+v^2)(x_0 - x_P)(y_0 - y_P) \end{array} }{(u^2 + v^2)^2} \\ &= \frac{v^2(x_0 - x_P)^2 + u^2(y_0 - y_P)^2 - 2uv(x_0 - x_P)(y_0 - y_P)} {u^2 + v^2} \\ &= \frac{[v(x_0 - x_P) - u(y_0 - y_P)]^2}{u^2 + v^2} \\ &= \frac{(v x_0 - u y_0 - v x_P + v y_P)^2}{u^2 + v^2} \end{align*}

ここで直線の一般式とパラメーター表示を比較すると

(10)    \begin{gather*} \frac{x - x_0}{u} = \frac{y - y_0}{v} \\ vx - uy - v x_0 + u y_0 = 0 \\ ax + by + c = 0 \\ \therefore v = a , -u = b , -v x_0 + u y_0 = c \end{gather*}

この結果を先の式に代入して以下を得る。

(11)    \begin{gather*} |\boldsymbol{h}|^2 = \frac{(a x_P + b x_P + c)^2}{a^2 + b^2} \\ |\boldsymbol{h}| = \frac{|a x_P + b x_P + c|}{\sqrt{a^2 + b^2}} \end{gather*}

 

 

Lasso回帰の理解

定義

Ridge回帰は単純な多重回帰の損失関数に対してL2正則化項を加え、多重共線性に対する正則化を図った。Lasso解析はこれに対してL1正則化項を加えて最小化する(正則化の意味についてはこちら)。

(1)    \begin{align*} L &= \frac{1}{2} \sum_{i=1}^n ( y_i - \hat{y}_i )^2 + \alpha (|w_1| + \cdots + |w_m|) \\ &= \frac{1}{2} \sum_i ( y_i - w_0 - w_1 x_{1i} - \cdots - w_m x_{mi} )^2 + \alpha (|w_1| + \cdots + |w_m|) \end{align*}

L1正則化の意味

準備

L2正則化は各重み係数が全体として小さくなるように制約がかかったが、L1正則化では値がゼロとなる重み係数が発生する。このことを確認する。

係数wを求めるためには損失関数Lを最小化すればよいが、Ridge回帰とは異なりL1正則化項は通常の解析的な微分はできない。

(2)    \begin{align*} \frac{\partial L}{\partial w_k} &= - \sum_i x_{ki} ( y_i - w_0 - w_1 x_{1i} - \cdots - w_m x_{mi} ) + \alpha \frac{\partial |w_k|}{\partial w_k} \\ &= - \sum_i x_{ki}y_i + w_0 \sum_i x_{ki} + \sum_{j \ne k} w_j \sum_i x_{ji} x_{ki} + w_k \sum_i {x_{ki}}^2 + \alpha \frac{\partial |w_k|}{\partial w_k} \\ &= 0 \end{align*}

ここで\frac{\partial |w_k|}{\partial w_k}=|w_k|'と表し、左辺のwk以外に関わる項をMkwkの係数となっている2乗和をSkkと表す。

(3)    \begin{equation*} M_k  + w_k S_{kk} + \alpha |w_k|' = 0 \end{equation*}

場合分け

ここで|wk|’についてはwkの符号によって以下の値をとる。

(4)    \begin{equation*} |w_k|' = \left\{ \begin{array}{rl} -1 & (w_k < 0) \\ 1 & (w_k > 0) \end{array} \end{equation*}

これらを式(3)に適用する。まずwk < 0に対しては

(5)    \begin{gather*} w_k < 0 \quad \rightarrow \quad M_k  + w_k S_{kk} - \alpha = 0 \\ -M_k + \alpha < 0 \quad \rightarrow \quad  w_k = \frac{-M_k + \alpha}{S_{kk}} \end{gather*}

またwk > 0に対しては、

(6)    \begin{gather*} w_k > 0 \quad \rightarrow \quad M_k  + w_k S_{kk} + \alpha = 0 \\ -M_k - \alpha > 0 \quad \rightarrow \quad  w_k = \frac{-M_k - \alpha}{S_{kk}} \end{gather*}

以上をまとめると、

(7)    \begin{equation*} w_k = \left\{ \begin{array}{ll} \dfrac{-M_k - \alpha}{S_{kk}} & (M_k < -\alpha) \\ \\ \dfrac{-M_k + \alpha}{S_{kk}} & (M_k > \alpha) \\ \end{array} \right. \end{equation*}

劣微分の導入

式(7)で−αMkαについては得られていない。Mk → ±αについてそれぞれの側から極限を計算すると0となるのでその間も0でよさそうだが、その保証はない。

ここでこちらのサイトのおかげで”劣微分(subdifferential)”という考え方を知ることができた。|wk|’についてwk = 0では解析的に微分不可能だが、その両側から極限をとった微分係数の範囲の集合を微分係数とするという考え方のようだ。

(8)    \begin{equation*} \frac{d |x|}{dx} = \left\{ \begin{array}{cl} -1 & (x < 0) \\ \left[ -1, 1 \right] & (x = 0) \\ 1 & (x > 0) \end{array} \right. \end{equation*}

そこで、wk = 0に対してこの劣微分を適用してみる。

(9)    \begin{gather*} w_k = 0 \quad \rightarrow \quad M_k +w_k S_{kk} + \alpha \left[ -1, 1 \right] = \left[ M_k - \alpha , M_k + \alpha \right] = 0\\ M_k - \alpha \le 0 \le M_k + \alpha \quad \rightarrow \quad -\alpha \le M_k \le \alpha \quad \rightarrow \quad w_k = 0 \end{gather*}

以上のことから、重みwkについて以下のようになり、−αMkαの範囲ではwk = 0となることがわかる。

(10)    \begin{equation*} w_k = \left\{ \begin{array}{cl} \dfrac{-M_k - \alpha}{S_{kk}} & (M_k < -\alpha \quad)\\ \\ 0 & (-\alpha \le M_k \le \alpha) \\ \\ \dfrac{-M_k + \alpha}{S_{kk}} & (M_k > \alpha) \end{array} \right. \end{equation*}

すなわちL1正則化の場合、ハイパーパラメータαは重み係数の大きさを制限すると同時に重み係数がゼロとなるような効果も持ち、αが大きいほど多くの重み係数がゼロとなりやすい。

参考サイト

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

Lassoを数式から実装まで(理論編)Miidas Research

 

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

概要

不等式制約条件を持つ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の極値が制約条件の範囲外にあり、fgの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が同じ向き(極値が制約条件内)

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

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

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

次に目的関数を最大化する場合を考える。以下の問題では目的関数fの極値が制約条件の範囲外にあり、fgの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が逆向き(極値が制約条件範囲内)

次の問題では極値が制約条件の範囲内にあり、fgの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の極値は制約条件(緑色)の範囲内にあり、fgの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λgf + λ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*}

参考サイト

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

 

 

arg max

maxが関数の最大値を意味するのに対して、arg maxは関数が最大値をとる場合の定義域を意味する。

(1)    \begin{align*} &\max x(4-x) = 4\\ &\arg \max x(4-x) = 2 \end{align*}

定義域を指定する場合。

(2)    \begin{align*} &{\arg \max}_{-1 \le x \le 0} \, x(x + 1)(x - 1) = -\frac{1}{\sqrt{3}}\\ &\max_{-1 \le x \le 0} x(x + 1)(x - 1) = \frac{2\sqrt{3}}{9} \end{align*}

本来arg maxは関数が最大値をとる定義域の集合を表す。

(3)    \begin{equation*} {\arg \max}_{0 \le x \le 4\pi} \, \cos x = \{ 0, 2\pi, 4\pi\} \end{equation*}

 

行列式の定義

定義式

(1)    \begin{align*} |\boldsymbol{A}| &= \sum_{\sigma \in S_n} {\rm sgn}(\sigma) \prod_{i=1}^n a_{i\sigma(i)} \\ &= \sum_{\sigma \in S_n} {\rm sgn}(\sigma) a_{1\sigma(1)} a_{2\sigma(2)} \cdots a_{n\sigma(n)} \end{align*}

計算例

次数2の場合

(2)    \begin{align*} |\boldsymbol{A}| &= \left| \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right| \\ &= {\rm sgn}(\sigma_1)a_{1\sigma_1(1)}a_{2\sigma_1(2)} + {\rm sgn}(\sigma_2)a_{1\sigma_2(1)}a_{2\sigma_2(2)} \end{align*}

ここで、

(3)    \begin{equation*} \sigma_1 = \left( \begin{array}{cc} 1 & 2 \\ 1 & 2 \end{array} \right) ,\quad \sigma_2 = \left( \begin{array}{cc} 1 & 2 \\ 2 & 1 \end{array} \right) \end{equation*}

(4)    \begin{equation*} {\rm sgn}(\sigma_1) = 1 ,\quad {\rm sgn}(\sigma_2) = -1 \end{equation*}

(5)    \begin{equation*} \sigma_1(1) = 1 ,\; \sigma_1(2) = 2 ,\; \sigma_2(1) = 2 ,\; \sigma_2(2) = 1 \end{equation*}

したがって行列式の値は、

(6)    \begin{equation*} |\boldsymbol{A}| = a_{11}a_{22} - a_{12}a_{21} \end{equation*}

次数3の場合

(7)    \begin{align*} |\boldsymbol{A}| =& \left| \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right| \\ =& {\rm sgn}(\sigma_1)a_{1\sigma_1(1)}a_{2\sigma_1(2)}a_{3\sigma_1(3)} + {\rm sgn}(\sigma_2)a_{1\sigma_2(1)}a_{2\sigma_2(2)}a_{3\sigma_2(3)}\\ &{\rm sgn}(\sigma_3)a_{1\sigma_3(1)}a_{2\sigma_3(2)}a_{3\sigma_3(3)} + {\rm sgn}(\sigma_4)a_{1\sigma_4(1)}a_{2\sigma_4(2)}a_{4\sigma_4(3)}\\ &{\rm sgn}(\sigma_5)a_{1\sigma_5(1)}a_{2\sigma_5(2)}a_{3\sigma_5(3)} + {\rm sgn}(\sigma_6)a_{1\sigma_6(1)}a_{2\sigma_6(2)}a_{4\sigma_6(3)} \end{align*}

ここで、

(8)    \begin{gather*} \sigma_1 = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 1 & 2 & 3 \end{array} \right) ,\quad \sigma_2 = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 1 & 3 & 2 \end{array} \right) \\ \sigma_3 = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 3 \end{array} \right) ,\quad \sigma_4 = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \end{array} \right) \\ \sigma_5 = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \end{array} \right) ,\quad \sigma_6 = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 3 & 2 & 1 \end{array} \right) \end{gather*}

(9)    \begin{equation*} \begin{array}{ll} {\rm sgn}(\sigma_1) = \phantom{-}1 ,& {\rm sgn}(\sigma_2) = -1 \\ {\rm sgn}(\sigma_3) = -1 ,& {\rm sgn}(\sigma_4) = \phantom{-}1 \\ {\rm sgn}(\sigma_5) = \phantom{-}1 ,& {\rm sgn}(\sigma_6) = -1 \end{array} \end{equation*}

(10)    \begin{gather*} \sigma_1(1) = 1 ,\; \sigma_1(2) = 2 ,\; \sigma_1(3) = 3 \\ \sigma_2(1) = 1 ,\; \sigma_2(2) = 3 ,\; \sigma_2(3) = 2 \\ \sigma_3(1) = 2 ,\; \sigma_3(2) = 1 ,\; \sigma_3(3) = 3 \\ \sigma_4(1) = 2 ,\; \sigma_2(2) = 3 ,\; \sigma_4(3) = 1 \\ \sigma_5(1) = 3 ,\; \sigma_5(2) = 1 ,\; \sigma_5(3) = 2 \\ \sigma_6(1) = 3 ,\; \sigma_6(2) = 2 ,\; \sigma_6(3) = 1 \end{gather*}

したがって行列式の値は、

(11)    \begin{align*} |\boldsymbol{A}| &= a_{11}a_{22}a_{33} - a_{11}a_{23}a_{32} \\ &- a_{12}a_{21}a_{33} + a_{12}a_{23}a_{31} \\ &+ a_{13}a_{21}a_{32} - a_{13}a_{22}a_{31} \end{align*}

 

ベクトル・行列を含む微分

記号の定義

以下の記号で統一的に定義しておく。ベクトルは原則として列ベクトル表示を標準とする。

(1)    \begin{equation*} \boldsymbol{x} = \left[ \begin{array}{c} x_1 \\ \vdots \\ x_n \\ \end{array} \right] \end{equation*}

(2)    \begin{equation*} \boldsymbol{X} = \left[ \begin{array}{ccc} x_{11} & \ldots & x_{1n} \\ \vdots & x_{ij} & \vdots \\ x_{m1} & \ldots & x_{mn} \end{array} \right] \end{equation*}

(3)    \begin{equation*} f(\boldsymbol{x}) = f(x_1, \ldots, x_m) \end{equation*}

(4)    \begin{equation*} \boldsymbol{f}(x) = \left[ \begin{array}{c} f_1(x) \\ \vdots \\ f_n(x) \end{array} \right] \end{equation*}

(5)    \begin{equation*} \boldsymbol{f}(\boldsymbol{x}) =\ \left[ \begin{array}{c} f_1(x_1, \ldots, x_n) \\ \vdots \\ f_m(x_1, \ldots, x_n) \end{array} \right] \end{equation*}

(6)    \begin{equation*} \boldsymbol{F}(x) = \left[ \begin{array}{ccc} F_{11}(x) & \ldots & F_{1n}(x) \\ \vdots & F_{ij} & \vdots \\ F_{m1}(x) & \ldots & F_{mn}(x) \\ \end{array} \right] \end{equation*}

ベクトル・行列をスカラーで微分

これらは素直にベクトル・行列の要素を微分すればよい。

(7)    \begin{equation*} \frac{d \boldsymbol{f}(x)}{dx} = \left[ \begin{array}{c} \dfrac{d f_1(x)}{dx} \\ \vdots \\ \dfrac{d f_n(x)}{dx} \end{array} \right] \end{equation*}

(8)    \begin{equation*} \frac{d \boldsymbol{F}(x)}{dx} = \left[ \begin{array}{ccc} \dfrac{dF_{11}(x)}{dx} & \ldots & \dfrac{dF_{1n}(x)}{dx} \\ \vdots & \dfrac{dF_{ij}(x)}{dx} & \vdots \\ \dfrac{dF_{m1}(x)}{dx} & \ldots & \dfrac{dF_{mn}(x)}{dx} \end{array} \right] \end{equation*}

スカラーをベクトルで微分

スカラーを\mathbb{R}^nのベクトルで微分すると、同じ次数のベクトルになる。

(9)    \begin{equation*} \frac{df(\boldsymbol{x})}{d\boldsymbol{x}} = \left[ \begin{array}{c} \dfrac{\partial f}{\partial x_1} \\ \vdots \\ \dfrac{\partial f}{\partial x_m} \end{array} \right] \end{equation*}

これは便宜的に偏微分係数を要素とするベクトルを導入して以下のように考えるとよい。

(10)    \begin{equation*} \frac{d}{d\boldsymbol{x}}f(\boldsymbol{x}) = \left[ \begin{array}{c} \dfrac{\partial}{\partial x_1} \\ \vdots \\ \dfrac{\partial}{\partial x_m} \end{array}\right] f(\boldsymbol{x}) \end{equation*}

スカラーを行列で微分

スカラーを\mathbb{R}^m\times\mathbb{R}^nの行列で微分すると、同じ次元・次数の行列になる。

(11)    \begin{equation*} \frac{df(\boldsymbol{X})}{d\boldsymbol{X}} = \left[ \begin{array}{ccc} \dfrac{\partial f}{\partial x_{11}} & \ldots & \dfrac{\partial f}{\partial x_{1n}} \\ \vdots & \dfrac{\partial f}{\partial x_{ij}} & \vdots \\ \dfrac{\partial f}{\partial x_{m1}} & \ldots & \dfrac{\partial f}{\partial x_{mn}} \\ \end{array} \right] \end{equation*}

これは便宜的に以下のように考えるとよい。

(12)    \begin{equation*} \frac{d}{d\boldsymbol{X}} f(\boldsymbol{X}) = \\ \left[ \begin{array}{ccc} \dfrac{\partial}{\partial x_{11}} & \ldots & \dfrac{\partial}{\partial x_{1n}} \\ \vdots & \dfrac{\partial}{\partial x_{ij}} & \vdots \\ \dfrac{\partial}{\partial x_{m1}} & \ldots & \dfrac{\partial}{\partial x_{mn}} \\ \end{array} \right] f(\boldsymbol{X}) \end{equation*}

ベクトルをベクトルで微分

この場合、微分する変数側を行ベクトルとするか、微分される関数側を行ベクトルとするか2通りの表現があるが、ここでは変数側を行ベクトルとする。

(13)    \begin{equation*} \frac{d\boldsymbol{f}(\boldsymbol{x})^T}{d\boldsymbol{x}} = \left[ \begin{array}{ccc} \dfrac{\partial f_1}{\partial x_1} & \ldots & \dfrac{\partial f_n}{\partial x_1} \\ \vdots & \dfrac{\partial f_j}{\partial x_i} & \vdots \\ \dfrac{\partial f_1}{\partial x_m} & \ldots & \dfrac{\partial f_n}{\partial x_m} \\ \end{array} \right] \end{equation*}

これは(10)で導入した偏微分係数ベクトルを導入して、便宜的に以下のように考えるとよい。

(14)    \begin{equation*} \frac{d}{d\boldsymbol{x}} \boldsymbol{f}(\boldsymbol{x})^T = \left[ \begin{array}{c} \dfrac{\partial}{\partial x_1} \\ \vdots \\ \dfrac{\parial}{\partial x_m} \end{array} \right] [ f_1(\boldsymbol{x}) \; \ldots \; f_n(\boldsymbol{x}) ] = \left[ \begin{array}{ccc} \dfrac{\partial f_1}{\partial x_1} & \cdots & \dfrac{\partial f_n}{\partial x_1} \\ & \dfrac{\partial f_j}{\partial x_i} &\\ \dfrac{\partial f_1}{\partial x_m} & \cdots & \dfrac{\partial f_n}{\partial x_m} \end{array} \right] \end{equation*}

公式

一般形

単位行列

ベクトルを同じベクトルで微分すると、単位ベクトルではなく単位行列になる。

(15)    \begin{equation*} \frac{d\boldsymbol{x}}{d\boldsymbol{x}} = \boldsymbol{I} \end{equation*}

合成関数

スカラーの合成関数と似ているが、イメージと積の順番が逆で、この順番は変えられない。

(16)    \begin{align*} \frac{df(\boldsymbol{u}(\boldsymbol{x}))}{d\boldsymbol{x}} = \frac{d\boldsymbol{u}(\boldsymbol{x})}{d\boldsymbol{x}} \frac{df(\boldsymbol{u})}{d\boldsymbol{u}} \\ \end{align*}

これは以下のように確認できる。

(17)    \begin{align*} \frac{df}{dx_i} &= \frac{\partial f}{\partial u_1}\frac{\partial u_1}{\partial x_i} + \cdots + \frac{\partial f}{\partial u_j}\frac{\partial u_j}{\partial x_i} + \cdots + \frac{\partial f}{\partial u_n}\frac{\partial u_n}{\partial x_i} \\ &= \left[ \begin{array}{ccc} \dfrac{\partial u_1}{\partial x_1} & \cdots & \dfrac{\partial u_n}{\partial x_1} \\ \vdots && \vdots \\ \dfrac{\partial u_1}{\partial x_m} & \cdots & \dfrac{\partial u_n}{\partial x_m} \\ \end{array} \right] \left[ \begin{array}{c} \dfrac{\partial f}{\partial u_1} \\ \vdots \\ \dfrac{\partial f}{\partial u_n} \end{array} \right] \\ &= \left[ \begin{array}{c} \dfrac{\partial}{\partial x_1} \\ \vdots \\ \dfrac{\partial}{\partial x_m} \end{array} \right] [u_1 \; \cdots \; u_n] \left[ \begin{array}{c} \dfrac{\partial}{\partial u_1} \\ \vdots \\ \dfrac{\partial}{\partial u_n} \end{array} \right] f(\boldsymbol{u}) \end{align*}

積の微分

行列の積のスカラーによる微分

(18)    \begin{equation*} \frac{d\boldsymbol{(FG)}}{dx} = \frac{d\boldsymbol{F}}{dx}\boldsymbol{G} + \boldsymbol{F} \frac{d\boldsymbol{G}}{dx} \end{equation*}

これは素直に次のように確認できる。

(19)    \begin{align*} \frac{d(\boldsymbol{FG})}{dx} &= \frac{d}{dx}\left[\sum_{j=1}^m f_{ij} g_{jk}\right] = \left[\sum_{j=1}^m \left(\frac{df_{ij}}{dx} g_{jk} + f_{ij} \frac{dg_{jk}}{dx} \right)\right] \\ &= \left[ \sum_{j=1}^m \frac{df_{ij}}{dx} g_{jk} \right] + \left[ \sum_{j=1}^m f_{ij} \frac{dg_{jk}}{dx} \right] \end{align*}

一次~二次形式の微分

Axの形式

(20)    \begin{align*} &\frac{d( \boldsymbol{Ax} )}{d\boldsymbol{x}} = \boldsymbol{A}^T \\ & \frac{d}{d\boldsymbol{x}} \left[ \begin{array}{c} a_{11}x_1 + \cdots + a_{1j}x_j + \cdots a_{1n}x_n \\ \vdots \\ a_{i1}x_1 + \cdots + a_{ij}x_j + \cdots a_{1n}x_n \\ \vdots \\ a_{m1}x_1 + \cdots + a_{mj}x_j + \cdots a_{mn}x_n \\ \end{array} \right] \\ &= \left[ \begin{array}{ccccc} a_{11} & \cdots & a_{i1} & \cdots & a_{m1} \\ \vdots && \vdots && \vdots \\ a_{i1} & \cdots & a_{ij} & \cdots & a_{in} \\ \vdots && \vdots && \vdots \\ a_{m1} & \cdots & a_{mj} & \cdots & a_{mn} \\ \end{array} \right] \end{align*}

x^2の形式

(21)    \begin{equation*} \frac{d(\boldsymbol{x}^T \boldsymbol{x})}{d\boldsymbol{x}} = 2 \boldsymbol{x} \end{equation*}

[証明]

(22)    \begin{equation*} \left[ \begin{array}{c} \dfrac{\partial}{\partial x_1} \\ \vdots \\ \dfrac{\partial}{\partial x_n} \end{array} \right] [ x_1^2 + \cdots + x_n^2 ] = \left[ \begin{array}{c} 2x_1 \\ \vdots \\ 2x_n \end{array} \right] \end{equation*}

xTAxの形式

この場合、\boldsymbol{A}は正方行列で、\boldsymbol{x}と同じ次数でなければならない。

(23)    \begin{equation*} \frac{d}{d\boldsymbol{x}} \left(\boldsymbol{x}^T \boldsmbol{A} \boldsymbol{x} \right)= \left( \boldsymbol{A} + \boldsymbol{A}^T \right) \boldsymbol{x} \end{equation*}

[証明]

(24)    \begin{align*} &\frac{d}{d \boldsymbol{x}} \left( [x_1 \; \cdots \; x_n] \left[ \begin{array}{ccc} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn} \\ \end{array} \right] \left[ \begin{array}{c} x_1 \\ \vdots \\ x_n \end{array} \right] \right)\\ &=\frac{d}{d \boldsymbol{x}} \left( [x_1 \; \cdots \; x_n] \left[ \begin{array}{c} a_{11} x_1 + \cdots + a_{1n} x_n \\ \vdots \\ a_{n1} x_1 + \cdots + a_{nn} x_n \end{array} \right] \right)\\ &= \frac{d}{d \boldsymbol{x}} \left( \left( a_{11} {x_1}^2 + \cdots + a_{1n} x_1 x_n \right) + \cdots + \left( a_{n1} x_n x_1 + \cdots + a_{nn} {x_n}^2 \right) \right) \end{array}\\ &=\left[ \begin{array}{c} \left( 2 a_{11} x_1 + \cdots + a_{1n} x_n \right) + a_{21} x_2 + \cdots + a_{n1}  x_n \\ \vdots \\ a_{1n} x_1 + \cdots + a_{1n-1} x_{n-1} + \left( a_{n1} x_1 + \cdots + 2a_{nn} x_n \right) \end{array} \right] \\ &=\left[ \begin{array}{c} \left( a_{11} x_1 + \cdots + a_{1n} x_1 \right) + \left( a_{11} x_1 + \cdots + a_{n1} x_n \right) \\ \vdots \\ \left( a_{n1} x_1 + \cdots + a_{nn} x_n \right) + \left( a_{1n} x_1 + \cdots + a_{nn} x_n \right) \end{array} \right] \end{align*}

 

転置行列

定義

(1)    \begin{equation*} {\boldsymbol{A}^T}_{ij} = {\boldsymbol{A}}_{ji} \end{equation*}

性質

単独の行列

転置の転置

(2)    \begin{equation*} \left(\boldsymbol{A}^T\right)^T = \boldsymbol{A} \end{equation*}

逆行列

(3)    \begin{equation*} \left( \boldsymbol{A}^T \right)^{-1} = \left( \boldsymbol{A}^{-1} \right)^T \end{equation*}

[証明]

(4)    \begin{align*} &\boldsymbol{AA}^{-1} = \boldsymbol{I} \; \Leftrightarrow \; \left( \boldsymbol{AA}^_{-1} \right)^T = \boldsymbol{I}^T \; \Leftrightarrow \; \left( \boldsymbol{A}^{-1} \right)^T \boldsymbol{A}^T = \boldsymbol{I} \\ &\boldsymbol{A}^{-1} \boldsymbol{A} = \boldsymbol{I} \; \Leftrightarrow \quad \left( \boldsymbol{A}^{-1} \boldsymbol{A} \right)^T = \boldsymbol{I}^T \; \Leftrightarrow \; \boldsymbol{A}^T \left( \boldsymbol{A}^{-1} \right)^T = \boldsymbol{I} \end{align*}

行列式

(5)    \begin{equation*} \left| \boldsymbol{A}^T \right| = \left| \boldsymbol{A} \right| \end{equation*}

行列演算

線形性

(6)    \begin{equation*} (\alpha \boldsymbol{A})^T = \alpha \boldsymbol{A}^T \end{equation*}

(7)    \begin{equation*} \left(\boldsymbol{A} + \boldsymbol{B}\right)^T = \boldsymbol{A}^T + \boldsymbol{B}^T \end{equation*}

交換法則は成り立たない。

(8)    \begin{equation*} (\boldsymbol{AB})^T = \boldsymbol{B}^T \boldsymbol{A}^T \end{equation*}

[証明]

(9)    \begin{align*} \left( [ \boldsymbol{AB} ]_{ij} \right)^T = \left( \sum_k \boldsymbol{A}_{ik} \boldsymbol{B}_{kj} \right)^T = \sum_k \boldsymbol{B}_{jk} \boldsymbol{A}_{ki} =\boldsymbol{B}^T \boldsymbol{A}^T \end{align*}

行列とベクトル

行列とベクトルの積

(10)    \begin{equation*} (\boldsymbol{Ax})^T = \boldsymbol{x}^T \boldsymbol{A}^T \end{equation*}

すなわち

(11)    \begin{equation*} \left[ \begin{array}{ccc} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{m1} & \cdots & a_{mn} \\ \end{array} \right] \left[ \begin{array}{c} x_1 \\ \vdots \\ x_n \end{array} \right] = [x_1 \; \cdots \; x_n] \left[ \begin{array}{ccc} a_{11} & \cdots & a_{m1} \\ \vdots & & \vdots \\ a_{1n} & \cdots & a_{mn} \\ \end{array} \right] \end{equation*}

内積

(12)    \begin{equation*} \boldsymbol{x}^T \boldsymbol{x} = \langle \boldsymbol{x} , \boldsymbol{x} \rangle \end{equation*}

すなわち

(13)    \begin{equation*} [x_1 \; \cdots \; x_n] \left[ \begin{array}{c} x_1 \\ \vdots \\ x_n \end{array} \right] = x_1^2 + \cdots + x_n^2 \end{equation*}

Gradient~勾配ベクトル

定義

多変数の関数のグラジエント(gradient)は勾配とも呼ばれ、以下で定義される。

(1)    \begin{equation*} \nabla f( x_1, \ldots, x_n ) = \left( \frac{\partial f}{\partial x_1} , \ldots , \frac{\partial f}{\partial x_n} \right) = \left( f_{x_1} , \ldots , f_{x_n} \right) \end{equation*}

2変数の場合

(2)    \begin{equation*} \nabla f( x, y ) = \left( \frac{\partial f}{\partial x} , \ldots , \frac{\partial f}{\partial y} \right) = \left( f_x , \ldots , f_y \right) \end{equation*}

準備~1変数関数の微分係数

微分係数の符号だけを見た場合

gradientの前に、1変数関数の微分係数についてもう一度考えてみる。

たとえばy = (x - 1)^2 + 1x = 1で極値を持ち、その前後で微分係数の符号が変わる。

(3)    \begin{equation*} y' = 2(x - 1) \left\{ \begin{align} < 0 \quad (x < 1) \\ = 0 \quad (x = 1) \\ > 0 \quad (x > 1) \end{align} \right. \end{equation*}

教科書的には、極値をとる点の前後で減少から増加に変わるということになる。

微分係数の符号を方向としてみた場合

同じ微分係数の値を、それが得られる値に対して、符号を考慮して矢印で表してみる。

ただしここでは、矢印の重なりを避けるために、少しずつ縦方向にずらして描いている。

こう描いてみると分かるが、微分係数の正負が方向を表すと考えると、「微分係数は、その方向に関数がどれだけ増加の傾きを持っているか」という意味を持つことがわかる。

微分係数の曲線上での分布

関数の曲線上で、微分係数の方向と大きさを考慮してベクトルを描いてみる。ベクトルの水平方向の成分を微分係数と同じ符号で長さ1、垂直方向の成分を微分係数の絶対値としている。

こうしてみると、微分係数は各位置での関数の増加方向とその増分を表していることがわかる。

2変数関数のgradient

勾配ベクトルの分布

2変数の関数について、gradientの分布を描いてみる。

関数としてz = x^2 + y^2を考えると、そのgradientは( 2x, 2y)であり、ベクトル場は以下のようになる。

中心から外側に向かって増加しており、その傾きは外側ほど大きくなっている(ベクトルの長さが長くなり、コンター間隔は小さくなっている)。

勾配ベクトルの曲面上での分布

微分係数の時と同じように、曲面上にgradientoの分布を描いてみたのが以下の図。

2次元の曲線の時と同じく、勾配ベクトルが曲面に沿った傾きを表していることがわかる。

なお上記で(u, v) = (u, v) / wとしているが、\nabla f方向で長さ1のベクトルを意味していて、これに対して\nabla fをz方向の成分とすると曲面に沿ったベクトルとなる。

gradientの意味

2変数の場合

(4)    \begin{equation*} df(x, y) = \frac{\partial f}{\partial x} dx + \frac{\partial f}{\partial y} dy = f_x dx + f_y dy \end{equation*}

gradientの方向の意味

先の微分係数の考え方から、勾配の各成分は関数の各点においてその成分方向に増加する。

したがって、gradientの方向は、関数が増加する方向を指している。

gradientの大きさの意味

コーシー・シュワルツの不等式から、

(5)    \begin{equation*} | df(x, y) | ^2 = \left( f_x dx + f_y dy \right) ^2 \le ( f_x^2 + f_y^2 ) ( dx^2 + dy^2) \end{equation*}

ここで右辺の最初の項がgradientの絶対値だから、

(6)    \begin{align*} | df(x, y) | ^2 \le | \nabla f |^2 ( dx^2 + dy^2) \end{align*}

{\boldsymbol d} = (dx, dy)| {\boldsymbol d} | = Cとすると、f(x, y){\boldsymbol d}方向の変化量の大きさはC | \nabla f |以下である。

また等号が成立するためには、

(7)    \begin{gather*} \left( f_x dx + f_y dy \right) ^2 - ( f_x^2 + f_y^2 ) ( dx^2 + dy^2) = 0 \\ 2 f_x dx f_y dy - f_x^2 dy^2 - f_y^2 dx^2 = 0 \\ (f_x dy - f_y dx)^2 = 0 \\ (f_x , f_y) \cdot (dy, -dx) = 0 \end{gather*}

これは、\nabla f(dx, dy)2つのベクトルが平行であることを意味している。

すなわちgradientの方向は、関数の変化量の大きさが最も大きくなる方向を指している。

gradientの意味

上記のことを併せると、gradientは以下のように最も勾配が大きな方向を意味することがわかる。

  1. gradientの方向は、関数がその点で最も大きく増加する方向
  2. gradientと逆の方向は、関数がその点で最も大きく減少する方向

n変数の場合

gradientの方向と大きさの意味は、2変数の場合と同じ。

不等式で等号が成立する場合を考える。

(8)    \begin{equation*} (f_{x_1} dx_1 + \cdots + f_{x_n} dx_n)^2 - (f_{x_1} ^2 + \cdots + f_{x_n} ^2) (dx_1 ^2 + \cdots + dx_n ^2) = 0 \end{equation*}

左辺第1項は、

(9)    \begin{equation*} \begin{array}{cccccccc} f_{x_1} ^2 dx_1 ^2 &+& f_{x_1} dx_1 f_{x_2} dx_2 &+& \cdots &+& f_{x_1} dx_1 f_{x_n} dx_n &+\\ f_{x_2} dx_2 f_{x_1} dx_1 &+& f_{x_2} ^2 dx_2 ^2 &+& \cdots &+& f_{x_2} dx_2 f_{x_n} dx_n &+\\ &&&& \cdots &&& \\ f_{x_n} dx_n f_{x_1} dx_1 &+& f_{x_n} dx_n f_{x_1} dx_1 &+& \cdots &+& f_{x_n} ^2 dx_n ^2 \end{array} \end{equation*}

また左辺第2項は、

(10)    \begin{equation*} \begin{array}{cccccccc} f_{x_1} ^2 dx_1 ^2 &+& f_{x_1} ^2 dx_2 ^2 &+& \cdots &+& f_{x_1} ^2 dx_n ^2 &+\\ f_{x_2} ^2 dx_1 ^2 &+& f_{x_2} ^2 dx_2 ^2 &+& \cdots &+& f_{x_2} ^2 dx_n ^2 &+\\&&&& \cdots &&& \\ f_{x_n} ^2 dx_1 ^2 &+& f_{x_n} ^2 dx_2 ^2 &+& \cdots &+& f_{x_n} ^2 dx_n ^2 &+\\\end{array} \end{equation*}

それぞれ各項が行列でいえば対角になっていることに留意しながら、(10)から(9)を差し引いて以下を得る。

(11)    \begin{equation*} \sum_{i=1}^{n} \sum_{j=i}^{n} \left( f_{x_i} dx_j - f_{x_j} dx_i \right) ^2 = 0 \end{equation*}

これは以下のようにも表せる。

(12)    \begin{equation*} f_{x_i} dx_j = f_{x_j} dx_i \quad (i \ne j) \end{equation*}

これは以下を意味する。

(13)    \begin{equation*} f_{x_i} : dx_i = f_{x_j} : dx_j \quad (i \ne j) \end{equation*}

すなわちn変数の場合でも、\nabla f{\boldsymbol d}の方向が一致するときにfの変化量が最も大きい。

 

コーシー・シュワルツの不等式

公式

Cauchy-Schwaltz inequality

(1)    \begin{equation*} \left( \sum_{i=1}^n a_i ^2 \right) \left( \sum_{i=1}^n b_i ^2 \right) \ge \left( \sum_{i=1}^n a_i b_i \right) ^2 \end{equation*}

証明

n=2の場合

(2)    \begin{equation*} \left( a_1^2 + a_2^2 \right) \left(b_1^2 + b_2^2 \right) \ge \left( a_1 b_1 + a_2 b_2 \right) ^2 \end{equation*}

(3)    \begin{align*} &\left( a_1^2 + a_2^2 \right) \left(b_1^2 + b_2^2 \right) - \left( a_1 b_1 + a_2 b_2 \right) ^2 \\ &= a_1 ^2 b_1^2 + a_1^2 b_2^2 + a_2^2 b_1^2 + a_2^2 b_2^2 - a_1^2 b_1^2 - 2 a_1 b_1 a_2 b_2 - a_2^2 b_2^2 \\ &= a_1^2 b_2^2 + a_2^2 b_1^2 - 2 a_1 b_1 a_2 b_2 \\ &= \left( a_1 b_2 - a_2 b_1 \right) ^2 \ge 0 \end{align*}

nが任意の場合

2次方程式の判別式による方法

以下の2次方程式を考える。

(4)    \begin{equation*} \sum_{i=1}^n \left( a_i x + b_i \right)^2 = 0 \end{equation*}

ここで関数f(x) = \sum_{i=1}^2 (a_i x + b_i)^2 \ge 0であり、上記の2次方程式の数は0個または1個である。

この方程式は以下のように変形できる。

(5)    \begin{equation*} \left( \sum a_i^2 \right) x^2 + 2 \left( \sum a_i b_i \right) x + \left( \sum b_i^2 \right) = 0 \end{equation*}

もとの方程式の解の個数が0 or 1なので、上記の方程式の判別式から

(6)    \begin{gather*} 4 \left( \sum a_i b_i \right)^2 - 4 \left( \sum a_i^2 \right) \left( \sum b_i^2 \right) \le 0 \\ \therefore \left( \sum a_i^2 \right) \left( \sum b_i^2 \right) \ge \left( \sum a_i b_i \right)^2 \end{gather*}

イメージ

{\boldsymbol a} = (a_1, \ldots , a_n){\boldsymbol b} = (b_1, \ldots , b_n)とすると、ベクトルの内積となす角の関係から

(7)    \begin{gather*} \left( {\boldsymbol a}{\boldsymbol b} \right)^2 = \left( \sum a_i b_i \right)^2 = | {\boldsymbol a} |^2 | {\boldsymbol b} |^2 \cos^2 \theta \le | {\boldsymbol a} |^2 | {\boldsymbol b} |^2 = \left( \sum a_i^2 \right) \left( \sum a_i^2 \right) \end{gather*}