14日前公開・13日前更新・29 min read

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

機械学習数学深層学習E資格特異値分解

※本記事は過去にQiitaで投稿したものを再編集したものです。

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

本記事をクリックして下さってありがとうございます！

今回は、応用数学より線形代数の特異値分解について取り扱いたいと思います。

特異値分解は、E資格の勉強でまず初めに立ちふさがる関門だと思います。計算自体も面倒だし、解けても何が嬉しいのかいまひとつわかりません。そんな特異値分解についてしっかり計算手順と使い道と解釈を教えてくれる記事があればとても嬉しいですよね。それがこの記事です。

特異値分解の全ての疑問にカシウスの槍をぶっ刺して回っていきますので記事を読み終えた頃には特異値分解に悩まされてきた過去の全てにさようならできると思います。もちろん文系出身の方にもわかるようになるべく丁寧に詳しく解説していきますので是非最後までご覧ください。

また、特異値分解では計算手順の中で固有値について理解していると分かりやすくなる場面があります。理解度を深めたい方は前回の記事【ハックしないE資格対策記ｰ02ｰ】～固有値分解って結局何なの？圏を突破しよう～と合わせてどうぞ。

【本シリーズの概要】

▼ハックしない"って何？

ハック/-Hack-は…

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

と言う意味を持っています。

この意味合いで、世の中には生活術や仕事術としての「○○ハック」という言葉が広がっていますよね。塾や予備校で学ぶ受験対策術も「お受験ハック」です。”傾向と対策”など、大学入試の際に私もお世話になりました。しかし、本シリーズではそういった対策術だけを記事にすることはありません。 ”E資格合格のための５つのコツ”とか”○○時間で合格できるE資格”とか”覚えておきたいコスパ最強10の公式”などは期待しないでください。ディープラーニングについて頭の中に体系を作り上げていただける様に、記事の内容もコツコツと必要な知識を述べ、体系的に整理して使えるような形を目指して作っていきます。

それが【ハックしないE資格対策記】です。

▼なぜハックしないのか

何故なら、資格試験の合格はゴールではなくあくまで客観的な知識と技術の基準として存在するものであり、合格後に知識と能力を活かせるかの方が遥かに大切だからです。

ここで一般社団法人日本ディープラーニング協会の公式ホームページからE資格の目的に関する記述を引用します。

ご挨拶

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

E資格概要

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

E資格が目的としていることは引用の通りで、要するにディープラーニングについての能力と知識レベルを客観的な基準で認定して、一定のレベルを担保した上で議論や事業開発が出来るようにすために実施されているのです。

この資格が、合格後にディープラーニングを議論や事業に活かしてもらうためにあると分かった上でもう一度考えてみると、やはりハックせずにコツコツとディープラーニングについての体系を組み立てて長期的に役立つ方向に向かった方が良いなと思いませんか。

概要を読んで良いコンセプトだと感じて下さった方は是非これからのシリーズを見届けていってもらえると嬉しいです。また、訂正、アドバイス、追加の参考資料の提案などなど、この記事をより良いものにするコメントをして下さるセカンドクリエイターの皆様をお待ちしております。

また、コメントで盛り上げて頂けるとモチベーションに繋がりますのでよろしくお願い致します！

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

〔ファスト特異値分解〕

特異値分解の計算手順をサクッと確認したい方はこの章を参考にして下さい。

特異値、特異ベクトルとは何ぞ？という方は次章以降じっくり読んで理解した上でこの章で確認していただくことをおすすめします。

◆基本の手順◆

$(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$ 転置直交行列
転置行列 $A^{T}$ を求める
$AA^{T}$ の固有値 $\lambda$ を $r$ 個求める

サラスの公式か余因子展開を使って固有方程式 $det(\lambda I-AA^{T})=0$ を $\lambda$ について解く
$AA^{T}$ の固有値 $\lambda$ の非負の平方根 $\sqrt{\lambda}=\sigma$ を大きい順に並べて $Σ$ を完成させる
$AA^{T}$ の固有値 $\lambda$ から正規化した固有ベクトル $u$ を求め、 $U$ を完成させる

同次連立一次方程式を行基本変形を使って解く
$A^{T}A$ の固有値 $\lambda$ を $n$ 個求める

$Σ^{T}Σ=n$ 次元対角行列 $Λ$ を解いて $n-r$ 個の固有値を求める
$A^{T}A$ の固有値 $\lambda$ から正規化した固有ベクトル $v$ を求め、 $V$ を転置させて完成させる

同次連立一次方程式を行基本変形を使って解く。

$r$ 個分は、 $v_{i}=\frac{1}{\sqrt{\lambda_{i}}}A^{T}u_{i}$ を解くことで固有ベクトルを求める。
１で確認した形と大きさに当てはまっているか確認する
特異値分解 $A=UΣV^{T}$ の完成！！
完成した $UΣV^{T}$ と行列 $A$ が一致するか確認する

〔行列の形と大きさ〕

特異値分解をするにあたって最初に気を付けるべきことが行列の形と大きさです。

固有値分解では、 $n$ 次元正方行列の場合には $P,Λ,P^{-1}$ の形と大きさは単純に $n$ 次元正方行列だと考えればよかったのですが、特異値分解は少し複雑です。

特異値分解の行列の形と大きさの基本のイメージは以下の通りです。

$ｍ$ が行列 $A$ の行数、 $n$ が行列 $A$ の列数、 $r$ は固有値の数です。これら３つの数値によって特異値分解の基本形は３種類に分けられます。③に関しては固有値分解と同じであり、特異値分解が固有値分解も包括しており、固有値分解の一般形であることが分かります。

また、実際に $U$ と $V^{T}$ を計算する際には $AA^{T}$ と $A^{T}A$ をそれぞれ固有値分解した際の固有ベクトルを利用するという手順があるために $U$ と $V^{T}$ は正方行列である必要があり、辻褄合わせ要員の固有ベクトルが登場します。この固有ベクトルは特異値0に対応した固有ベクトルですが、あくまで固有値計算時の辻褄合わせ要員なので0成分で形と大きさを拡張した $Σ$ を掛けて実質的な影響を排除します。

イメージは以下の通りで、基本形の①と②に対応してそれぞれ形が異なります。

特異値分解の行列の形と大きさについて理解できたので次から中身についてみていきましょう。

〔特異値分解とは〕

◆定義◆

$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}$ ノルムが１となる単位ベクトルに正規化する理由▽

特異値分解では、固有値分解と異なり固有ベクトルを単位ベクトルに正規化する必要があります。

その理由について、分かりやすく説明していきます。

まず、特異値分解の定義として左特異ベクトル $U$ と右特異ベクトル $V$ を直交行列としている理由について説明します。それは、特異値を求めるのに固有値分解の手法を応用するために都合の良い特異値・特異ベクトルの定義を導き出すためです。詳しくは、〔特異値・特異ベクトル〕の◆定義式のイメージ◆の内容を確認してください。

その上で、直交行列であるために各固有ベクトル $\{u_{1},u_{2},…,u_{n}\}$ を $L_{2}$ ノルムが１となる単位ベクトルに正規化する理由を証明します。

$U$ についての証明は $Ｖ$ にそのまま当てはまるので、 $U$ について証明していきます。

$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$ になります。

$(u_{i},u_{j})=1(i=j)(i,j=1,2,…,n)$ が成り立つには、各固有ベクトル $u_{1},u_{2},…,u_{n}$ がそれぞれ正規直行基底である必要があり、そのためには各固有ベクトルの $L_{2}$ ノルムが１となる単位ベクトルに正規化すればよいです。

よって、 $U$ が直交行列であるために各固有ベクトル $\{u_{1},u_{2},…,u_{n}\}$ を $L_{2}$ ノルムが１の単位ベクトルに正規化します。

理由が証明できました。次の項では実際に単位ベクトルに正規化する方法を説明します。

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

単位ベクトルは、ベクトルの $L_{2}$ ノルムが１となればよいので、以下の様に計算できる。

$U$ の１つの固有ベクトル

u_{1}=\begin{pmatrix} u_{11}\\ u_{12}\\ \vdots\\ u_{1n} \end{pmatrix}

の $L_{2}$ ノルムは通常

\|x\|_{2}=\sqrt{|u_{11}|^{2}+|u_{12}|^{2}+\dots+|u_{1n}|^{2}}=\sqrt{u_{11}^{2}+u_{12}^{2}+\dots+u_{1n}^{2}}

ですが、その解をその解で割ることで

\|x\|_{2} =\frac{ \sqrt{ |u_{11}|^{2}+|u_{12}|^{2}+\dots+|u_{1n}|^{2}} }{ \sqrt{u_{11}^{2}+u_{12}^{2}+\dots+u_{1n}^{2}} } =\frac{ \sqrt{u_{11}^{2}+u_{12}^{2}+\dots+u_{1n}^{2}} }{ \sqrt{u_{11}^{2}+u_{12}^{2}+\dots+u_{1n}^{2}}} =1

となり、

\|x\|_{2}= \sqrt{ |\frac{u_{11}}{\sqrt{u_{11}^{2}+u_{12}^{2}+\dots+u_{1n}^{2}}}|^{2}+ |\frac{u_{12}}{\sqrt{u_{11}^{2}+u_{12}^{2}+\dots+u_{1n}^{2}}}|^{2}+ \dots+ |\frac{u_{1n}}{\sqrt{u_{11}^{2}+u_{12}^{2}+\dots+u_{1n}^{2}}}|^{2} }\\=1

で計算できる。つまり、固有値ベクトル $u_{1}$ の単位ベクトルは

u_{1}=\begin{pmatrix} \frac{u_{11}}{\sqrt{u_{11}^{2}+u_{12}^{2}+\dots+u_{1n}^{2}}}\\ \frac{u_{12}}{\sqrt{u_{11}^{2}+u_{12}^{2}+\dots+u_{1n}^{2}}}\\ \vdots\\ \frac{u_{1n}}{\sqrt{u_{11}^{2}+u_{12}^{2}+\dots+u_{1n}^{2}}} \end{pmatrix}

となります。これだと一般化され過ぎて良く分からないので、

u_{1}=\begin{pmatrix} 3\\ 2\\ 3\\ \end{pmatrix}

だとしたときの単位ベクトルを求めます。

\|x\|_{2}=\sqrt{|3|^{2}+|2|^{2}+|3|^{2}}=\sqrt{9+4+9}=\sqrt{22}

\|x\|_{2} =\frac{ \sqrt{|3|^{2}+|2|^{2}+|3|^{2}} }{ \sqrt{22} } =\frac{ \sqrt{22} }{ \sqrt{22} } =1

\|x\|_{2}= \sqrt{ |\frac{3}{\sqrt{22}}|^{2}+ |\frac{2}{\sqrt{22}}|^{2}+ |\frac{3}{\sqrt{22}}|^{2} }=1

以上により、

u_{1}=\begin{pmatrix} \frac{3}{\sqrt{22}}\\ \frac{2}{\sqrt{22}}\\ \frac{3}{\sqrt{22}} \end{pmatrix}

と求まります。

以上が単位ベクトルの求め方です。

次章では、さらに特異値・特異ベクトルとは何なのか深堀りしていきます。

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

◆定義◆

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

$Av=\sigma u$

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

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

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

◆定義式のイメージ◆

特異値・特異ベクトルの定義式が

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

である理由は、特異値分解の定義から導き出すことができます。順を追って図示しながら説明します。

まず、特異値分解の定義から

A=UΣV^{T} =(u_{1}u_{2}…u_{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) \begin{pmatrix}v_{1}\\v_{2}\\\vdots\\v_{n}\end{pmatrix}\\ =u_{1}\sigma_{1}v_{1}^{T}+\dots+u_{n}\sigma_{n}v_{n}^{T} =\sigma_{1}u_{1}v_{1}^{T}+\dots+\sigma_{n}u_{n}v_{n}^{T}…(a)

に変形することができます。そして、 $U$ と $V^{T}$ が直交行列であることから

(u_{i}^{T},u_{j})=(v_{i}^{T},v_{j})=\left\{\begin{array}{}0 & (i≠j) \\1 & (i=j) \end{array}\right.\\=\delta_{ij}…(b)

であります。

この性質(b)によって式(a)の両辺に右側から $v_{1}$ を掛けると、

Av_1=\sigma_1u_1v_1^Tv_1+\dots+\sigma_mu_mv_m^Tv_1\\ =\sigma_1u_11+\dots+\sigma_mu_m0\\ =\sigma_1u_1

となり、特異値・特異ベクトルの定義式の１行目が求まりました。

$A^{T}$ に関して特異値分解の定義から式(a)の様に

A^{T}=(UΣV^{T})^{T}=VΣ^{T}U^{T}=\sigma_{1}^{T}v_{1}u_{1}^{T}+\dots+\sigma_{m}^{T}v_{m}u_{m}^{T}=\sigma_{1}v_{1}u_{1}^{T}+\dots+\sigma_{m}v_{m}u_{m}^{T}…(c)

変形することができます。その上で直交行列の性質によって、(b)の両辺に右側から $u_{1}$ を掛けると、

Au_1=\sigma_1v_1u_1^Tu_1+\dots+\sigma_mv_mu_m^Tu_1\\ =\sigma_1v_11+\dots+\sigma_mv_m0\\ =\sigma_1v_1

となり、特異値・特異ベクトルの定義式の２行目が求まりました。

ここで、実例を用いて式(a)に関して更に理解を深めましょう。

取り扱う行列 $A$ は

A=\begin{pmatrix}2&1&1\\1&1&2\end{pmatrix}

です。この行列 $A$ を特異値分解して(a)の様に変形し、左辺第一項のみを取り出した

A=\sigma_1u_1v_1^T…(d)

を計算すると

A=u_{1} \sigma_{1}v_{1}^{T}=\frac{1}{\sqrt{2}}\begin{pmatrix}1&0\\1&0\end{pmatrix} \begin{pmatrix}\sqrt{11}&0&0\\0&0&0\end{pmatrix}\frac{1}{\sqrt{22}}\begin{pmatrix}3&2&3\\0&0&0\\0&0&0\end{pmatrix} \\=\begin{pmatrix}\frac{3\sqrt{11}}{\sqrt{2}\sqrt{22}}&\frac{3\sqrt{11}}{\sqrt{2}\sqrt{22}}&\frac{2\sqrt{11}}{\sqrt{2}\sqrt{22}}\\\frac{2\sqrt{11}}{\sqrt{2}\sqrt{22}}&\frac{3\sqrt{11}}{\sqrt{2}\sqrt{22}}&\frac{3\sqrt{11}}{\sqrt{2}\sqrt{22}} \end{pmatrix}=\begin{pmatrix}1.5&1&1.5\\1.5&1&1.5\end{pmatrix}

となります。図示してみると以下の通りになります。

この式(d)の両辺に $v_{1}$ を掛けると

Av_{1}=\sigma_1u_1v_1^Tv_{1}

であり、左辺を計算すると

Av_{1}= \begin{pmatrix}2&1&1\\1&1&2\end{pmatrix}\frac{1}{\sqrt{22}} \begin{pmatrix}3&0&0\\2&0&0\\3&0&0\end{pmatrix}= \begin{pmatrix}\frac{11}{\sqrt{22}}\\\frac{11}{\sqrt{22}}\end{pmatrix}

となり、右辺を計算すると

u_{1} \sigma_{1}v_{1}^{T}v_{1}= \frac{1}{\sqrt{2}}\begin{pmatrix}1&0\\1&0\end{pmatrix} \begin{pmatrix}\sqrt{11}&0&0\\0&0&0\end{pmatrix}\frac{1}{\sqrt{22}} \begin{pmatrix}3&2&3\\0&0&0\\0&0&0\end{pmatrix}\frac{1}{\sqrt{22}} \begin{pmatrix}3&0&0\\2&0&0\\3&0&0\end{pmatrix}\\=u_{1}\sigma_{1}= \frac{1}{\sqrt{2}}\begin{pmatrix}1&0\\1&0\end{pmatrix} \begin{pmatrix}\sqrt{11}&0&0\\0&0&0\end{pmatrix}= \begin{pmatrix}\frac{\sqrt{11}}{\sqrt{2}}\\\frac{\sqrt{11}}{\sqrt{2}}\end{pmatrix}= \sigma_{1}u_{1}

となります。つまり、

Av_{1}=\sigma_{1}u_{1}\begin{pmatrix}\frac{11}{\sqrt{22}}\\\frac{11}{\sqrt{22}}\end{pmatrix} =\begin{pmatrix}\frac{\sqrt{11}}{\sqrt{2}}\\\frac{\sqrt{11}}{\sqrt{2}}\end{pmatrix} \frac{\sqrt{11}}{\sqrt{11}}

になります。これで更に特異値・特異ベクトルの定義式の理解が深まりました。

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

定義式を変形すると特異値と固有値の関係が見えてきて、固有値分解の手法を使って計算可能であることが分かります。それでは説明していきます。

まず、定義式の一行目の両辺に $A$ を右から、定義式の二行目の両辺に $A^{T}$ を左から掛けます。

すると定義式は以下の通りに変化します。

A^{T}Av=\sigma A^{T}v=\sigma \sigma v=\sigma^{2}v\\ AA^{T}u=\sigma Au=\sigma \sigma u=\sigma^{2}u

簡潔にはこうです。

A^{T}Av=\sigma^{2}v\\ AA^{T}u=\sigma^{2}u

この形、何かに似ていると思いませんか？

そうです、固有値・固有ベクトルの定義

Av=\sigma v\\

です。つまり、

A^{T}A=\sigma^{2}\\ AA^{T}=\sigma^{2}

だということです。特異値が $AA^{T}$ の固有値 $\lambda$ の非負の平方根 $\sqrt{\lambda}$ なのは、この式から導かれたものだったのです。これにより、特異値分解だけの複雑な計算方法を覚えることなく、慣れ親しんだ固有値分解の手法をそのまま使ってもよいことになるのです。

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

ここで、もう一つのアプローチ方法を示したいと思います。人によってはこちらの方が分かりやすいかもしれません。それでは説明していきます。

まず、固有値分解の定義と転置行列の性質から、

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

が得られます。そうすると、 $A^{T}A$ は

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

で表せ、直交行列の性質から $U^{T}U=I,VV^{T}=I$ なので、

A^{T}A=VΣ^{T}ΣV^{T}=Σ^{T}Σ\\

と式変形でき、

A^{T}A=Σ^{T}Σ

であることが分かります。

次に、 $AA^{T}$ は

AA^{T}=UΣV^{T}VΣ^{T}U^{T}

で表せ、直交行列の性質から $UU^{T}=I,V^{T}V=I$ なので、

AA^{T}=UΣΣ^{T}U^{T}=ΣΣ^{T}UU^{T}= ΣΣ^{T}\\

と式変形でき、

AA^{T}=ΣΣ^{T}

であることが分かります。

つまり、

A^{T}A=Σ^{T}Σ\\ AA^{T}=ΣΣ^{T}

です。結果的に、特異値・特異ベクトルの定義式から導き出した

A^{T}A=\sigma^{2}\\ AA^{T}=\sigma^{2}

と同義ですが、行列の形と大きさが簡単に求められるのでこちらの方が便利かもしれないです。

〔特異値分解の求め方〕

これまで学んできたことを使って実際に計算してみましょう。

今回取り扱う行列は $2×3$ の以下の行列です。

A=\begin{pmatrix}2&1&1\\1&1&2\end{pmatrix}

手順を確認しながら進めていきましょう。

$(r≤m≤n)$ である $m×n$ 行列 $A$ を $UΣV^{T}$ に分解する際の各行列の形と大きさを確認する

$Σ$ ：固有値が重解でない限り $r=m$ なので、形と大きさは②’を想定して $2×3$

$U$ ：固有値が重解でない限り $r=m$ なので、形と大きさは②’を想定して $2×2$

$V^{T}$ ：固有値が重解でない限り $r=m$ なので、形と大きさは②’を想定して $3×3$
転置行列 $A^{T}$ を求める
$A^{T}=\begin{pmatrix}2&1\\1&1\\1&2\end{pmatrix}$
$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$ と置きます。
$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}$
が完成します。
$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)$
が完成します。
$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$ となります。
$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}$

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

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

【本シリーズの概要】

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

〔ファスト特異値分解〕

◆基本の手順◆

〔行列の形と大きさ〕

〔特異値分解とは〕

◆定義◆

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

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

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

◆定義◆

◆定義式のイメージ◆

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

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

〔特異値分解の求め方〕

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