【ハックしないE資格対策記-03-(前編)】~さようなら、全ての付け焼刃特異値分解~

【ご挨拶】こんにちは！ぬかさんエンジニアリングです。

【本シリーズの概要】

〔物事をうまくやるための〕こつ、アイデア [^1]

人工知能の分野は、良くも悪くも、「人工知能の定義がない」ということに由来する特徴があります。さまざまな技術を取り込む寛容性がある一方で、なんでもかんでも人工知能と言ってしまうことができ、過剰期待を生みやすい性質もあります。だからこそ、人工知能の分野においては、ある一定の知識レベル・技術レベルの基準を作るということが大変重要と考えます。本協会では、初期の重要な活動としてディープラーニングに関する資格試験を実施したいと考えています。ユーザ企業やエンジニアが、一定の知識レベルを担保することで、地に足の着いた議論や事業開発ができるものと考えています。[^2]

ディープラーニングの理論を理解し、適切な手法を選択して実装する能力や知識を有しているかを認定する。[^3]

【今回のテーマ】～特異値分解のイメージと計算方法～

〔ファスト特異値分解〕

◆基本の手順◆

1. $(r≤m≤n)$である$m×n$行列$A$を$UΣV^{T}$に分解する際の各行列の形と大きさを確認する
   $Σ$：特異値(固有値$\lambda$の非負の平方根$\sqrt{\lambda}$)$=\sigma$を対角成分に持つ$r×n$の対角行列
   $U$：左特異ベクトル($AA^{T}$の固有値$\lambda$から求めた固有ベクトル$u$)を並べた$m×m$の直交行列
   $V^{T}$：右特異ベクトル($A^{T}A$の固有値$\lambda$から求めた固有ベクトル$v$)を並べた$n×n$転置直交行列
2. 転置行列$A^{T}$を求める
3. $AA^{T}$の固有値$\lambda$を$r$個求める
   サラスの公式か余因子展開を使って固有方程式$det(\lambda I-AA^{T})=0$を$\lambda$について解く
4. $AA^{T}$の固有値$\lambda$の非負の平方根$\sqrt{\lambda}=\sigma$を大きい順に並べて$Σ$を完成させる
5. $AA^{T}$の固有値$\lambda$から正規化した固有ベクトル$u$を求め、$U$を完成させる
   同次連立一次方程式を行基本変形を使って解く
6. $A^{T}A$の固有値$\lambda$を$n$個求める
   $Σ^{T}Σ=n$次元対角行列$Λ$を解いて$n-r$個の固有値を求める
7. $A^{T}A$の固有値$\lambda$から正規化した固有ベクトル$v$を求め、$V$を転置させて完成させる
   同次連立一次方程式を行基本変形を使って解く。
   $r$個分は、$v_{i}=\frac{1}{\sqrt{\lambda_{i}}}A^{T}u_{i}$を解くことで固有ベクトルを求める。
8. １で確認した形と大きさに当てはまっているか確認する
9. 特異値分解$A=UΣV^{T}$の完成！！
10. 完成した$UΣV^{T}$と行列$A$が一致するか確認する

〔行列の形と大きさ〕

〔特異値分解とは〕

◆定義◆

$m×n$行列$A(m≤n)$が特異値$\sigma$と左特異ベクトル$u$と右特異ベクトル$v$を持つとき、

$$A=UΣV^{T}$$

ただし、

$$Σ=(diag(σ1,σ2,...,σm)|0m×(n-m)) =\left(\begin{array}{cccc|ccc} σ_{1} & 0 & \dots & 0 & 0 & \dots & 0\\ 0 & σ_{2} & \dots & 0 & 0 & \dots & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \dots & σ_{m} & 0 & \dots & 0 \end{array}\right)$$

の対角行列、

U=(u_{1}u_{2}…u_{m})

の直交行列、

V^{T}=\begin{pmatrix}v_{1}\v_{2}\\vdots\v_{n}\end{pmatrix}

の直交行列の転置行列に変形することを特異値分解という。[^4]

• $Σ$
  この定義は$m=r$を前提としており〔行列の形と大きさ〕における②’の形を取っています。実際、$m=r$であることが多いので引用しました。０成分の部分の形と大きさは$m$と$n$の数字によって計算が可能です。
• $U$(左特異ベクトル)
  $AA^{T}$の異なる固有値$\lambda$に対応する固有ベクトル$\{u_{1},u_{2},…,u_{n}\}$を列方向に並べた直交行列
  $U$が直交行列であるために、各固有ベクトル$\{u_{1},u_{2},…,u_{n}\}$を$L_{2}$ノルムが１の単位ベクトルに正規化する理由
  $AA^{T}$は、転置用列の性質により実対称行列であり、実対称行列の性質により異なる固有値に対する固有ベクトルは直交するため、$u_{1},u_{2},…,u_{n}$ は互いに直交しています。互いに直交しているので、ベクトルの直交性から$(u_{i},u_{j})=0(i≠j)(i,j=1,2,…,n)$であることが分かり、あとは$(u_{i},u_{j})=1(i=j)(i,j=1,2,…,n)$であれば$u_{1},u_{2},…,u_{n}$はそれぞれ正規直行基底であり、正規直行基底の集合である$\{u_{1},u_{2},…,u_{n}\}$は正規直交系となる。よって、直交行列の性質から正規直交系$U$は直交行列となります。
  正規直交系であるということは、各固有ベクトル$u_{1},u_{2},…,u_{n}$がそれぞれ正規直行基底であるということであり、つまり各固有ベクトルの$L_{2}$ノルムが１となっている必要があります。
• $V_{T}$(右特異ベクトル)
  $A^{T}A$の異なる固有値$\lambda$に対応する固有ベクトル$\{v_{1},v_{2},…,v_{n}\}$を列方向に並べた直交行列

▽U,Vが直交行列であるために、各固有ベクトルの$L_{2}$ノルムが１となる単位ベクトルに正規化する理由▽

▽単位ベクトルの求め方▽

〔特異値・特異ベクトル〕

◆定義◆

任意の零行列ではない$m×n$行列$A$に対して、

$Av=\sigma u$

$A^{T}u=\sigma v$

(ただし、$\sigma>0$、$u$、$v$はともに零ベクトルではない)

を満たすような正の数$\sigma$を特異値、$m$次元ベクトル$u$を左特異ベクトル、 $n$次元ベクトル$v$を右特異ベクトルと呼びます。 [^5]

◆定義式のイメージ◆

◆定義式から求める特異値と固有値の関係◆

◆固有値分解の定義式から求める特異値と固有値の関係◆

〔特異値分解の求め方〕

1. $(r≤m≤n)$である$m×n$行列$A$を$UΣV^{T}$に分解する際の各行列の形と大きさを確認する
   $Σ$：固有値が重解でない限り$r=m$なので、形と大きさは②’を想定して$2×3$
   $U$：固有値が重解でない限り$r=m$なので、形と大きさは②’を想定して$2×2$
   $V^{T}$：固有値が重解でない限り$r=m$なので、形と大きさは②’を想定して$3×3$
2. 転置行列$A^{T}$を求める
   $$A^{T}=\begin{pmatrix}2&1\\1&1\\1&2\end{pmatrix}$$
3. $AA^{T}$の固有値$\lambda$を$r$個求める
   まずは実対称行列$AA^{T}$を求めます。
   $$AA^{T}= \begin{pmatrix}2&1&1\\1&1&2\end{pmatrix} \begin{pmatrix}2&1\\1&1\\1&2\end{pmatrix}\\= \begin{pmatrix}6&5\\5&6\end{pmatrix}$$
   次に、固有方程式に$AA^{T}$を代入して$λ$について解きます。
   $$det(A-λI)= \begin{vmatrix}\begin{pmatrix}6 & 5 \\5 & 6 \\ \end{pmatrix}-\begin{pmatrix}λ & 0 \\0 & λ \\ \end{pmatrix}\end{vmatrix}= \begin{vmatrix}6-λ & 5-0 \\5-0 & 6-λ \\ \end{vmatrix}=0$$
   サラスの公式を使い行列式を解くと
   $$(6-λ)(6-λ)-25=λ^{2}-12λ+11=(λ-11)(λ-1)=0$$
   となり、よって固有値は$λ=11,1$です。
   この後、各固有値を使ってそれぞれの固有ベクトルを求めるため$λ1=11，λ2=1$と置きます。
4. $AA^{T}$の固有値$\lambda$の非負の平方根$\sqrt{\lambda}=\sigma$を大きい順に並べて$Σ$を完成させる
   まず、〔特異値分解とは〕の◆定義◆より、今回の例では
   $$Σ= \begin{pmatrix} \sigma_{1}&0&0\\ 0&\sigma_{2}&0 \end{pmatrix}$$
   であることが分かります。
   そして、◆固有値分解の定義式から求める特異値と固有値の関係◆より、
   $$AA^{T}=ΣΣ^{T}$$
   なので、$AA^{T}$の固有値$λ1=11，λ2=1$を
   $$\begin{pmatrix} λ_{1}&0\\ 0&λ_{2} \end{pmatrix}= \begin{pmatrix} 11&0\\ 0&1 \end{pmatrix}$$
   とすると、
   $$ΣΣ^{T}= \begin{pmatrix}σ_{1} & 0 & 0\\ 0 & σ_{2}& 0\end{pmatrix} \begin{pmatrix}σ_{1} & 0\\ 0 & σ_{2}\\ 0 & 0\end{pmatrix}= \begin{pmatrix}σ_{1}^{2} & 0 \\ 0 & σ_{2}^{2} \end{pmatrix}= \begin{pmatrix}λ_{1} & 0 \\ 0 & λ_{2} \end{pmatrix}= \begin{pmatrix}11 & 0 \\ 0 & 1 \end{pmatrix}$$
   と表せて
   $$σ_{1}^{2}=11,σ_{2}^{2}=1\hspace{10pt}\therefore σ_{1}=\sqrt{11},σ_{2}=1$$
   となります。
   この結果から固有値$λ_{1}=11，λ_{2}=1$の非負の平方根 $\sqrt{λ_{1}}=\sqrt{11}，\sqrt{λ_{2}}=\sqrt{1}$を大きい順に並べて
   $$Σ= \begin{pmatrix} \sqrt{\lambda_{1}}&0&0\\ 0&\sqrt{\lambda_{2}}&0 \end{pmatrix}= \begin{pmatrix} \sqrt{11}&0&0\\ 0&\sqrt{1}&0 \end{pmatrix}$$
   が完成します。
5. $AA^{T}$の固有値$\lambda$から正規化した固有ベクトル$u$を求め、$U$を完成させる
   同次連立一次方程式
   $$(A-\lambda_{i} I)\boldsymbol{u_{j}}=0\\ (i=1,2,...,n)(j=1,2,...,n)$$
   の自明でない解を求めます。
   まず、$λ1=11$の場合について計算します。
   ここでは$u$を一つ目の固有ベクトルとして$u_{1}$と表記し、 $(A−λ_{i}I)u_{1}=0$とします。
   ここで$λ_{i}$に$11$を代入すると
   $$(A-λ_{i}I)\boldsymbol{u_1}= \begin{Bmatrix}\begin{pmatrix}6 & 5 \\5 & 6 \\ \end{pmatrix}- \begin{pmatrix}11 & 0 \\0 & 11 \\ \end{pmatrix} \end{Bmatrix}\boldsymbol{u_1}= \begin{pmatrix}6-11 & 5-0 \\5-0 & 6-11 \\ \end{pmatrix}\boldsymbol{u_1}= \begin{pmatrix}-5 & 5 \\5 & -5 \\ \end{pmatrix}\boldsymbol{u_1}=0$$
   が求まり、
   $$\boldsymbol{u_1}=\begin{pmatrix}x_{11} \\x_{12} \\ \end{pmatrix}$$
   なので
   $$(A-λ_{i}I)\boldsymbol{u_1}= \begin{pmatrix}-5 & 5 \\5 & -5 \\ \end{pmatrix} \begin{pmatrix}x_{11} \\x_{12} \\ \end{pmatrix}= \begin{pmatrix}0 \\0 \\ \end{pmatrix}$$
   となります。係数行列を行基本変形によって階段行列に変形し
   $$\begin{pmatrix}-5 & 5 \\5 & -5 \\ \end{pmatrix} \rightarrow \begin{pmatrix}1 & -1 \\0 & 0 \\ \end{pmatrix}$$
   が求まるので、$u_{1}$を掛けて
   $$\begin{pmatrix}1 & -1 \\0 & 0 \\ \end{pmatrix} \begin{pmatrix}x_{11} \\x_{12} \\ \end{pmatrix}= \begin{pmatrix}x_{11} & -x_{12} \\0 & 0 \\ \end{pmatrix}= \begin{pmatrix}0 \\0 \\ \end{pmatrix}$$
   となるので、$x_{11}$と$x_{12}$について一次方程式を解くと
   $$x_{11}-x_{12}=0$$
   であり、解は自明ではない解であるため任意定数$ｃ$を用いて
   $$x_{11}=c\\ x_{12}=c$$
   です。つまり、
   $$u_{1}= \begin{pmatrix} x_{11}\\ x_{12} \end{pmatrix}= \begin{pmatrix} c\\ c \end{pmatrix}= c\begin{pmatrix} 1\\ 1 \end{pmatrix}$$
   です。
   特異値分解では、$U$を直交行列にするために固有ベクトルを大きさ１の単位ベクトルに直してあげる必要がありますので、$L_{2}$ノルムを用いて
   $$\|x\|_{2}=\sqrt{|c|^{2}+|c|^{2}}=\sqrt{2c^{2}}=\sqrt{2}\sqrt{c^{2}}=\sqrt{2}c=1$$
   $$\|x\|_{2}=c=\frac{1}{\sqrt{2}}$$
   以上により
   $$u_{1}=\frac{1}{\sqrt{2}} \begin{pmatrix} 1\\ 1\\ \end{pmatrix}= \begin{pmatrix} \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\\ \end{pmatrix}$$
   と求まりました。
   では、次に$λ_{2}=1$の場合について計算します。
   $λ_{1}=11$の場合と同様の計算を行った結果、
   $$u_{2}=\begin{pmatrix} \frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\\ \end{pmatrix}$$
   と求まりました。
   よって、
   $$U=\left(\begin{array}{cc}u_{1} & u_{2} \end{array}\right)\\ \quad= \left(\begin{array}{cc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{array}\right)$$
   が完成します。
6. $A^{T}A$の固有値$\lambda$を$n$個求める
   $V^{T}$が$n$次元正方行列を満たすために固有ベクトルが$n$個ある必要があるため、$A^{T}A$ の固有値も$n$個必要です。今回の例では固有値が３つ必要です。しかし、手順３で求めた固有値は２つです。ですので、残り１つの固有値を何かで補う必要があります。そこで登場するのが固有値$λ_{3}=0$ です。
   $λ_{1}=11,λ_{2}=1,λ_{3}=0$を代入してみると
   $$\begin{pmatrix} λ_{1}&0&0\\ 0&λ_{2}&0\\ 0&0&λ_{3} \end{pmatrix}= \begin{pmatrix} 11&0&0\\ 0&1&0\\ 0&0&0 \end{pmatrix}$$
   になります。何故固有値$λ_{3}=0$を用いるのかは、◆固有値分解の定義式から求める特異値と固有値の関係◆より、
   $$A^{T}A=Σ^{T}Σ$$
   を使って説明できます。
   $AA^{T}$の固有値$λ1=11，λ2=1$に$λ_{3}=x$を加えた$A^{T}A$の固有値を
   $$\begin{pmatrix} λ_{1}&0&0\\ 0&λ_{2}&0\\ 0&0&λ_{3} \end{pmatrix}= \begin{pmatrix} 11&0&0\\ 0&1&0\\ 0&0&x \end{pmatrix}$$
   とすると、
   $$ΣΣ^{T}= \begin{pmatrix}σ_{1} & 0\\ 0 & σ_{2}\\ 0 & 0\end{pmatrix} \begin{pmatrix}σ_{1} & 0 & 0\\ 0 & σ_{2}& 0\end{pmatrix}= \begin{pmatrix}σ_{1}^{2} & 0 & 0\\ 0 & σ_{2}^{2} & 0\\ 0&0&0 \end{pmatrix}= \begin{pmatrix}λ_{1}&0&0\\0&λ_{2}&0\\0&0&λ_{3}\end{pmatrix}= \begin{pmatrix}11&0&0\\0&1&0\\0&0&x\end{pmatrix}$$
   と表せて
   $$σ_{1}^{2}=11,σ_{2}^{2}=1,0=x$$
   となります。よって、固有値$λ_{3}=0$となります。
7. $A^{T}A$の固有値$\lambda$から正規化した固有ベクトル$v$を求め、$V$を転置させて完成させる
   $U$と同じく同次連立一次方程式
   $$(A-\lambda_{i} I)\boldsymbol{u_{j}}=0\\ (i=1,2,...,n)(j=1,2,...,n)$$
   の自明でない解を求め…なくても$V$を計算できる方法があるのでご紹介します。
   それは、
   $$v_{i}=\frac{1}{\sqrt{\lambda_{i}}}A^{T}u_{i}$$
   です。
   これは、$σ_{i}=\sqrt{λ_{i}}$であることから、定義式
   $$A^{T}u=\sigma v$$
   を変形して
   $$A^{T}u_{i}=\sqrt{λ_{i}}v_{i}\rightarrow v_{i}=\frac{1}{\sqrt{\lambda_{i}}}A^{T}u_{i}$$
   としたものである。これで、$U$で求めた$r$固有値と固有ベクトルを使って$v$の固有ベクトルを$r$個まで求めることができます。
   実際に計算してみると、$v_{1}$は
   $$v_{1}= \frac{1}{\sqrt{\lambda_{1}}}A^{T}u_{1}= \frac{1}{\sqrt{11}} \begin{pmatrix}2&1\\1&1\\1&2\end{pmatrix} \begin{pmatrix}\frac{1}{\sqrt{2}}\\-\frac{1}{\sqrt{2}}\end{pmatrix}\\= \frac{1}{\sqrt{11}} \begin{pmatrix}\frac{3}{\sqrt{2}}\\\frac{2}{\sqrt{2}}\\\frac{3}{\sqrt{2}}\end{pmatrix}= \begin{pmatrix}\frac{3}{\sqrt{22}}\\\frac{2}{\sqrt{22}}\\\frac{3}{\sqrt{22}}\end{pmatrix}$$
   であり、$v_{2}$は
   $$v_{2}= \frac{1}{\sqrt{\lambda_{2}}}A^{T}u_{2}= \frac{1}{\sqrt{1}} \begin{pmatrix}2&1\\1&1\\1&2\end{pmatrix} \begin{pmatrix}\frac{1}{\sqrt{2}}\\-\frac{1}{\sqrt{2}}\end{pmatrix}\\= \begin{pmatrix}\frac{1}{\sqrt{2}}\\0\\-\frac{1}{\sqrt{2}}\end{pmatrix}$$
   であることが分かります。
   最後に、$λ_{3}=0$の場合の固有ベクトル$v_{3}$を求めます。
   計算結果は
   $$v_{3}= \begin{pmatrix} -\frac{1}{\sqrt{11}}\\ -\frac{3}{\sqrt{11}}\\ \frac{1}{\sqrt{11}} \end{pmatrix}$$
   です。導出は自分で計算してみましょう。
   よって、
   $$V= \left(\begin{array}{cc}u_{1} & u_{2} & u_{3} \end{array}\right)\\ \quad= \left(\begin{array}{cc} \frac{3}{\sqrt{22}} & \frac{1}{\sqrt{2}} &\frac{1}{\sqrt{11}}\\ \frac{2}{\sqrt{22}} & 0 & -\frac{3}{\sqrt{11}}\\ \frac{3}{\sqrt{22}} & -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{11}} \end{array}\right)$$
   が完成します。
   最後に、
   $$\left(\begin{array}{cc} \frac{3}{\sqrt{22}} & \frac{2}{\sqrt{22}} &\frac{3}{\sqrt{22}}\\ \frac{1}{\sqrt{2}} & 0 & -\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{11}} & -\frac{3}{\sqrt{11}} & \frac{1}{\sqrt{11}} \end{array}\right)$$
   転置行列にしてあげて本当の完成です。
8. １で確認した形と大きさに当てはまっているか確認する
   $$U=\left(\begin{array}{cc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{array}\right)\\ Σ=\begin{pmatrix} \sqrt{11}&0&0\\ 0&\sqrt{1}&0 \end{pmatrix}\\ V^{T}=\left(\begin{array}{cc} \frac{3}{\sqrt{22}} & \frac{2}{\sqrt{22}} &\frac{3}{\sqrt{22}}\\ \frac{1}{\sqrt{2}} & 0 & -\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{11}} & -\frac{3}{\sqrt{11}} & \frac{1}{\sqrt{11}} \end{array}\right)$$
   $U$は$2×2$、$Σ$は$2×3$、$V^{T}$は$3×3$で初めの想定と同じ形と大きさの行列であることが確認できます。
9. 特異値分解$A=UΣV^{T}$の完成！！
   $$A=UΣV^{T}=\left(\begin{array}{cc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{array}\right) \begin{pmatrix} \sqrt{11}&0&0\\ 0&\sqrt{1}&0 \end{pmatrix} \left(\begin{array}{cc} \frac{3}{\sqrt{22}} & \frac{2}{\sqrt{22}} &\frac{3}{\sqrt{22}}\\ \frac{1}{\sqrt{2}} & 0 & -\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{11}} & -\frac{3}{\sqrt{11}} & \frac{1}{\sqrt{11}} \end{array}\right)\\$$
   分解完了です！！皆様お疲れ様です！！
10. 完成した$UΣV^{T}$と行列Aが一致するか確認する
    各自確め計算をしてみましょう。