折れ線と曲線の近似誤差

円弧の長さと弦の長さの差

半径r、内角θの円弧の長さLa

(1)    \begin{equation*} L_a = r \theta \end{equation*}

これに対する弦の長さは

(2)    \begin{align*} L_c &= \sqrt {r^2 + r^2 - 2 r^2 \cos \theta} \\ &= r \sqrt {2 (1 - cos \theta)} \end{align*}

ここでLcLaの比を計算すると、rを含まないθのみの関数となる。

(3)    \begin{equation*} \frac{L_c}{L_a} = \frac{\sqrt {2 ( 1 - \cos \theta ) }}{\theta} \end{equation*}

θを度単位としてこの比をグラフにすると以下のようになる。

角度変化が30度弱で誤差が2%程度、20度で0.5%程度、10度になるとかなり誤差は小さくなっている。

そこでこの付近の誤差を計算してみる。

角度 5度 10度 15度 20度 25度 30度
Lc/La 0.9997 0.9987 0.9971 0.9949 0.9921 0.9886
誤差 0.03% 0.13% 0.29% 0.51% 0.79% 1.14%

道路線形の例

道路ネットワークのリンクを折れ線で近似する場合の誤差を考える。

式((3)の誤差率の計算結果から、円弧の内角が20~30度程度以内であれば、弧と弦の長さの差はかなり小さくなりそうだと予想される。

そこで角度に対して曲線半径rを掛けて曲線部の道路の長さを計算し、さらに誤差から曲線の道路の長さと直線で近似した長さの差を計算してみる。

角度 rad 弧長(60) 弧長(710) 差分(60) 差分(710)
5 0.08727 5.236m 61.959m 1.7mm 1.9cm
10 0.17453 10.472m 123.918m 1.3cm 15.7cm
15 0.26180 15.708m 185.878m 4.5cm 53cm
20 0.34907 20.944m 247.837m 10.6cm 1.26m
25 0.43633 26.180m 309.796m 20.7cm 2.45m
30 0.52360 31.416m 371.755m 35.8cm 4.23m

ネットワークデータの用途により、許容される誤差が決まり、必要な補完点の密度が変わってくる。

たとえばメートル単位の経路案内であれば10cmオーダーの誤差は許容され、交差点での停止になると数cmなど。後者の様にミクロなコントロールや自動運転に直接データを活用する場合は、数cm程度以下の精度が必要となると想定される。

 

オイラー関数

定義

オイラーのトーシェント関数、オイラーのφ関数とも。totientとは数学用語で「与えられた数以下でこれと素な整数の個数」というこの関数の意味そのもの。

φ(6) = 2 (1, 5)

φ(12) = 4 (1, 5, 7, 11)

φ(20) = 8 (1, 3, 7, 9, 11, 13, 17, 19)

素数に対するオイラー関数値

素数はそれ自身と1以外に約数を持たないので、オイラー関数値はその値から自身の分1を減じた値となる。

φ(p) = p − 1 

2つの素数の積のオイラー関数値は、双方から1を減じた値の積になる。

φ(pq) = (p − 1)(q − 1)

これを納得するのに時間がかかった。まどろっこしいが以下のように考えた。

まず以下のことに気づく。

(1)    \begin{equation*} (p - 1)(q - 1) = pq - p - q + 1 = pq - (p - 1) - (q - 1) - 1 \end{equation*}

次に2つの素数5と3で以下のように考えてみる。

まずφ(15)に関して。15以下の数のうち15と互いに素であるのは以下の8個。

1, 2, 4, 7, 8, 11, 13, 14

逆に互いに素でない(15と公約数を持つ)数は以下の6個。

3, 5, 6, 9, 10, 12

ここで以下のように考える。

  • φ(5)に関してはカウントされる数は1, 2, 3, 4の4つで、φ(3)に関してはカウントされる数は1, 2の2つ
  • これらの数に任意の自然数を掛けて15以下の自然数を作り出すことができる
  • ところが3×5は素数の掛け算であり、上記の数に3や5以外の数をかけてもその結果は3×5と互いに素であることに変わりはない
  • φ(3)でカウントする1, 2に対して5を掛ければ、3×5以下でこれと互いに素でない数が得られる
  • またφ(5)でカウントする1, 2, 3, 4に対して3を掛ければ、3×5以下でこれと互いに素でない数が得られる
  • しかも3と5はいずれも素数で互いに素なので、上記の結果に重複は生じない

φ(3)に関しては、対象となる数に5を掛けて以下が得られる。

1, 2 → 5, 10

φ(5)に関しては、対象となる数に3を掛けて以下が得られる。

1, 2, 3, 4 → 3, 6, 9, 12

以上を併せて、15に対して1を除いて互いに素でない6個の数が得られる。

すなわち、φ(pq)は以下のようにして得られる。

  • 重複しないp − 1個、q − 1個の数がpqと互いに素でない
  • pq自身1個もpqと互いに素でない

したがって以下のようになる。

(2)    \begin{equation*} \phi (pq) = pq - (p - 1) - (q - 1) - 1 = (p - 1)(q - 1) \end{equation*}

 

主成分分析の定式化

概要

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

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

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

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

(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})^T}{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} \\ \rightarrow \frac{df(\boldsymbol{u}(\boldsymbol{x}))}{d\boldsymbol{x}} &= \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の形式

ベクトルAxをベクトルxで微分するのに(13)の考え方で計算する。

ベクトルxn次、行列Am×nとすると、ベクトルAx次数はm次となる。微分する際に微分係数ベクトルはn×1の列ベクトル、Axは転置して1×mの行ベクトルとなり、結果はn×mの行列になる。その結果は元のAの転置行列となる。

(20)    \begin{equation*} \frac{d\left( (\boldsymbol{Ax})^T \right)}{d\boldsymbol{x}} = \boldsymbol{A}^T \end{equation*}

(21)    \begin{equation*} \begin{align} & \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_{in}x_n \\ \vdots \\ a_{m1}x_1 + \cdots + a_{mj}x_j + \cdots + a_{mn}x_n \\ \end{array} \right]^T \\ &= \left[ \begin{array}{c} \dfrac{\partial}{\partial x_1} \\ \vdots \\ \dfrac{\partial}{\partial x_j} \\ \vdots \\ \dfrac{\partial}{\partial x_n} \\ \end{array} \right] \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_{in}x_n \\ \vdots \\ a_{m1}x_1 + \cdots + a_{mj}x_j + \cdots + a_{mn}x_n \\ \end{array} \right]^T \\ &= \left[ \begin{array}{ccccc} a_{11} & \cdots & a_{i1} & \cdots & a_{m1} \\ \vdots && \vdots && \vdots \\ a_{1j} & \cdots & a_{ij} & \cdots & a_{mj} \\ \vdots && \vdots && \vdots \\ a_{1n} & \cdots & a_{in} & \cdots & a_{mn} \\ \end{array} \right] = \boldsymbol{A}^T \end{align} \end{equation*}

x^2の形式

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

[証明]

(23)    \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}と同じ次数でなければならない。

(24)    \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*}

[証明]

(25)    \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*}