Ccmmutty logo
Commutty IT
0 pv29 min read

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

https://cdn.magicode.io/media/notebox/bd3e3490-968d-4c87-b34b-f83b4166f2c6.jpeg
※本記事は過去にQiitaで投稿したものを再編集したものです。

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

本記事をクリックして下さってありがとうございます!
今回は、応用数学より線形代数の特異値分解について取り扱いたいと思います。
特異値分解は、E資格の勉強でまず初めに立ちふさがる関門だと思います。計算自体も面倒だし、解けても何が嬉しいのかいまひとつわかりません。そんな特異値分解についてしっかり計算手順と使い道と解釈を教えてくれる記事があればとても嬉しいですよね。それがこの記事です。
特異値分解の全ての疑問にカシウスの槍をぶっ刺して回っていきますので記事を読み終えた頃には特異値分解に悩まされてきた過去の全てにさようならできると思います。 もちろん文系出身の方にもわかるようになるべく丁寧に詳しく解説していきますので是非最後までご覧ください。
また、特異値分解では計算手順の中で固有値について理解していると分かりやすくなる場面があります。理解度を深めたい方は前回の記事【ハックしないE資格対策記ー02ー】~固有値分解って結局何なの?圏を突破しよう~と合わせてどうぞ。

【本シリーズの概要】

▼ハックしない"って何?
ハック/-Hack-は…
〔物事をうまくやるための〕こつ、アイデア [^1]
と言う意味を持っています。
この意味合いで、世の中には生活術や仕事術としての「○○ハック」という言葉が広がっていますよね。 塾や予備校で学ぶ受験対策術も「お受験ハック」です。”傾向と対策”など、大学入試の際に私もお世話になりました。 しかし、本シリーズではそういった対策術だけを記事にすることはありません。 ”E資格合格のための5つのコツ”とか”○○時間で合格できるE資格”とか”覚えておきたいコスパ最強10の公式”などは期待しないでください。 ディープラーニングについて頭の中に体系を作り上げていただける様に、記事の内容もコツコツと必要な知識を述べ、体系的に整理して使えるような形を目指して作っていきます。
それが【ハックしないE資格対策記】です。
▼なぜハックしないのか
何故なら、資格試験の合格はゴールではなくあくまで客観的な知識と技術の基準として存在するものであり、合格後に知識と能力を活かせるかの方が遥かに大切だからです。
ここで一般社団法人日本ディープラーニング協会の公式ホームページからE資格の目的に関する記述を引用します。
ご挨拶
人工知能の分野は、良くも悪くも、「人工知能の定義がない」ということに由来する特徴があります。さまざまな技術を取り込む寛容性がある一方で、なんでもかんでも人工知能と言ってしまうことができ、過剰期待を生みやすい性質もあります。だからこそ、人工知能の分野においては、ある一定の知識レベル・技術レベルの基準を作るということが大変重要と考えます。本協会では、初期の重要な活動としてディープラーニングに関する資格試験を実施したいと考えています。ユーザ企業やエンジニアが、一定の知識レベルを担保することで、地に足の着いた議論や事業開発ができるものと考えています。[^2]
E資格概要
ディープラーニングの理論を理解し、適切な手法を選択して実装する能力や知識を有しているかを認定する。[^3]
E資格が目的としていることは引用の通りで、要するにディープラーニングについての能力と知識レベルを客観的な基準で認定して、一定のレベルを担保した上で議論や事業開発が出来るようにすために実施されているのです。
この資格が、合格後にディープラーニングを議論や事業に活かしてもらうためにあると分かった上でもう一度考えてみると、やはりハックせずにコツコツとディープラーニングについての体系を組み立てて長期的に役立つ方向に向かった方が良いなと思いませんか。
概要を読んで良いコンセプトだと感じて下さった方は是非これからのシリーズを見届けていってもらえると嬉しいです。 また、訂正、アドバイス、追加の参考資料の提案などなど、この記事をより良いものにするコメントをして下さるセカンドクリエイターの皆様をお待ちしております。
また、コメントで盛り上げて頂けるとモチベーションに繋がりますのでよろしくお願い致します!

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

〔ファスト特異値分解〕

特異値分解の計算手順をサクッと確認したい方はこの章を参考にして下さい。
特異値、特異ベクトルとは何ぞ?という方は次章以降じっくり読んで理解した上でこの章で確認していただくことをおすすめします。

◆基本の手順◆

  1. (rmn)(r≤m≤n)であるm×nm×n行列AAUΣVTUΣV^{T}に分解する際の各行列の形と大きさを確認する
    ΣΣ:特異値(固有値λ\lambdaの非負の平方根λ\sqrt{\lambda})=σ=\sigmaを対角成分に持つr×nr×nの対角行列
    UU:左特異ベクトル(AATAA^{T}の固有値λ\lambdaから求めた固有ベクトルuu)を並べたm×mm×mの直交行列
    VTV^{T}:右特異ベクトル(ATAA^{T}Aの固有値λ\lambdaから求めた固有ベクトルvv)を並べたn×nn×n転置直交行列
  2. 転置行列ATA^{T}を求める
  3. AATAA^{T}の固有値λ\lambdarr個求める
    サラスの公式か余因子展開を使って固有方程式det(λIAAT)=0det(\lambda I-AA^{T})=0λ\lambdaについて解く
  4. AATAA^{T}の固有値λ\lambdaの非負の平方根λ=σ\sqrt{\lambda}=\sigmaを大きい順に並べてΣΣを完成させる
  5. AATAA^{T}の固有値λ\lambdaから正規化した固有ベクトルuuを求め、UUを完成させる
    同次連立一次方程式を行基本変形を使って解く
  6. ATAA^{T}Aの固有値λ\lambdann個求める
    ΣTΣ=nΣ^{T}Σ=n次元対角行列ΛΛを解いてnrn-r個の固有値を求める
  7. ATAA^{T}Aの固有値λ\lambdaから正規化した固有ベクトルvvを求め、VVを転置させて完成させる
    同次連立一次方程式を行基本変形を使って解く。
    rr個分は、vi=1λiATuiv_{i}=\frac{1}{\sqrt{\lambda_{i}}}A^{T}u_{i}を解くことで固有ベクトルを求める。
  8. 1で確認した形と大きさに当てはまっているか確認する
  9. 特異値分解A=UΣVTA=UΣV^{T}の完成!!
  10. 完成したUΣVTUΣV^{T}と行列AAが一致するか確認する

〔行列の形と大きさ〕

特異値分解をするにあたって最初に気を付けるべきことが行列の形と大きさです。
固有値分解では、nn次元正方行列の場合にはP,Λ,P1P,Λ,P^{-1}の形と大きさは単純にnn次元正方行列だと考えればよかったのですが、特異値分解は少し複雑です。
特異値分解の行列の形と大きさの基本のイメージは以下の通りです。
特異値分解の行列の形と大きさ1.drawio.png
が行列AAの行数、nnが行列AAの列数、rrは固有値の数です。これら3つの数値によって特異値分解の基本形は3種類に分けられます。③に関しては固有値分解と同じであり、特異値分解が固有値分解も包括しており、固有値分解の一般形であることが分かります。
また、実際にUUVTV^{T}を計算する際にはAATAA^{T}ATAA^{T}Aをそれぞれ固有値分解した際の固有ベクトルを利用するという手順があるためにUUVTV^{T}は正方行列である必要があり、辻褄合わせ要員の固有ベクトルが登場します。この固有ベクトルは特異値0に対応した固有ベクトルですが、あくまで固有値計算時の辻褄合わせ要員なので0成分で形と大きさを拡張したΣΣを掛けて実質的な影響を排除します。
イメージは以下の通りで、基本形の①と②に対応してそれぞれ形が異なります。
特異値分解の行列の形と大きさ2.drawio.png
特異値分解の行列の形と大きさについて理解できたので次から中身についてみていきましょう。

〔特異値分解とは〕

◆定義◆

m×nm×n行列A(mn)A(m≤n)が特異値σ\sigmaと左特異ベクトルuuと右特異ベクトルvvを持つとき、
A=UΣVTA=UΣV^{T}
ただし、
Σ=(diag(σ1,σ2,...,σm)0m×(nm))=(σ100000σ200000σm00)Σ=(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=rm=rを前提としており〔行列の形と大きさ〕における②’の形を取っています。実際、m=rm=rであることが多いので引用しました。0成分の部分の形と大きさはmmnnの数字によって計算が可能です。
  • UU(左特異ベクトル)
    AATAA^{T}の異なる固有値λ\lambdaに対応する固有ベクトル{u1,u2,,un}\{u_{1},u_{2},…,u_{n}\}を列方向に並べた直交行列
    UUが直交行列であるために、各固有ベクトル{u1,u2,,un}\{u_{1},u_{2},…,u_{n}\}L2L_{2}ノルムが1の単位ベクトルに正規化する理由
    AATAA^{T}は、転置用列の性質により実対称行列であり、実対称行列の性質により異なる固有値に対する固有ベクトルは直交するため、u1,u2,,unu_{1},u_{2},…,u_{n} は互いに直交しています。互いに直交しているので、ベクトルの直交性から(ui,uj)=0(ij)(i,j=1,2,,n)(u_{i},u_{j})=0(i≠j)(i,j=1,2,…,n)であることが分かり、あとは(ui,uj)=1(i=j)(i,j=1,2,,n)(u_{i},u_{j})=1(i=j)(i,j=1,2,…,n)であればu1,u2,,unu_{1},u_{2},…,u_{n}はそれぞれ正規直行基底であり、正規直行基底の集合である{u1,u2,,un}\{u_{1},u_{2},…,u_{n}\}は正規直交系となる。よって、直交行列の性質から正規直交系UUは直交行列となります。
    正規直交系であるということは、各固有ベクトルu1,u2,,unu_{1},u_{2},…,u_{n}がそれぞれ正規直行基底であるということであり、つまり各固有ベクトルのL2L_{2}ノルムが1となっている必要があります。
  • VTV_{T}(右特異ベクトル)
    ATAA^{T}Aの異なる固有値λ\lambdaに対応する固有ベクトル{v1,v2,,vn}\{v_{1},v_{2},…,v_{n}\}を列方向に並べた直交行列
▽U,Vが直交行列であるために、各固有ベクトルのL2L_{2}ノルムが1となる単位ベクトルに正規化する理由▽
特異値分解では、固有値分解と異なり固有ベクトルを単位ベクトルに正規化する必要があります。
その理由について、分かりやすく説明していきます。
まず、特異値分解の定義として左特異ベクトルUUと右特異ベクトルVVを直交行列としている理由について説明します。それは、特異値を求めるのに固有値分解の手法を応用するために都合の良い特異値・特異ベクトルの定義を導き出すためです。詳しくは、〔特異値・特異ベクトル〕の◆定義式のイメージ◆の内容を確認してください。
その上で、直交行列であるために各固有ベクトル{u1,u2,,un}\{u_{1},u_{2},…,u_{n}\}L2L_{2}ノルムが1となる単位ベクトルに正規化する理由を証明します。
UUについての証明はにそのまま当てはまるので、UUについて証明していきます。
AATAA^{T}は、転置行列の性質により実対称行列であり、対称行列の性質により異なる固有値に対する固有ベクトルは直交するため、u1,u2,,unu_{1},u_{2},…,u_{n} は互いに直交しています。互いに直交しているので、ベクトルの直交性から(ui,uj)=0(ij)(i,j=1,2,,n)(u_{i},u_{j})=0(i≠j)(i,j=1,2,…,n)であることが分かり、あとは(ui,uj)=1(i=j)(i,j=1,2,,n)(u_{i},u_{j})=1(i=j)(i,j=1,2,…,n)を満たせばu1,u2,,unu_{1},u_{2},…,u_{n}はそれぞれ正規直行基底であり、正規直行基底の集合である{u1,u2,,un}\{u_{1},u_{2},…,u_{n}\}は正規直交系となります。よって、直交行列の性質から正規直交系UUは直交行列UUになります。
(ui,uj)=1(i=j)(i,j=1,2,,n)(u_{i},u_{j})=1(i=j)(i,j=1,2,…,n)が成り立つには、各固有ベクトルu1,u2,,unu_{1},u_{2},…,u_{n}がそれぞれ正規直行基底である必要があり、そのためには各固有ベクトルのL2L_{2}ノルムが1となる単位ベクトルに正規化すればよいです。
よって、UUが直交行列であるために各固有ベクトル{u1,u2,,un}\{u_{1},u_{2},…,u_{n}\}L2L_{2}ノルムが1の単位ベクトルに正規化します。
理由が証明できました。次の項では実際に単位ベクトルに正規化する方法を説明します。
▽単位ベクトルの求め方▽
単位ベクトルは、ベクトルのL2L_{2}ノルムが1となればよいので、以下の様に計算できる。
UUの1つの固有ベクトル
u1=(u11u12u1n)u_{1}=\begin{pmatrix} u_{11}\\ u_{12}\\ \vdots\\ u_{1n} \end{pmatrix}
L2L_{2}ノルムは通常
x2=u112+u122++u1n2=u112+u122++u1n2\|x\|_{2}=\sqrt{|u_{11}|^{2}+|u_{12}|^{2}+\dots+|u_{1n}|^{2}}=\sqrt{u_{11}^{2}+u_{12}^{2}+\dots+u_{1n}^{2}}
ですが、その解をその解で割ることで
x2=u112+u122++u1n2u112+u122++u1n2=u112+u122++u1n2u112+u122++u1n2=1\|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
となり、
x2=u11u112+u122++u1n22+u12u112+u122++u1n22++u1nu112+u122++u1n22=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
で計算できる。つまり、固有値ベクトルu1u_{1}の単位ベクトルは
u1=(u11u112+u122++u1n2u12u112+u122++u1n2u1nu112+u122++u1n2)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}
となります。これだと一般化され過ぎて良く分からないので、
u1=(323)u_{1}=\begin{pmatrix} 3\\ 2\\ 3\\ \end{pmatrix}
だとしたときの単位ベクトルを求めます。
x2=32+22+32=9+4+9=22\|x\|_{2}=\sqrt{|3|^{2}+|2|^{2}+|3|^{2}}=\sqrt{9+4+9}=\sqrt{22}
x2=32+22+3222=2222=1\|x\|_{2} =\frac{ \sqrt{|3|^{2}+|2|^{2}+|3|^{2}} }{ \sqrt{22} } =\frac{ \sqrt{22} }{ \sqrt{22} } =1
x2=3222+2222+3222=1\|x\|_{2}= \sqrt{ |\frac{3}{\sqrt{22}}|^{2}+ |\frac{2}{\sqrt{22}}|^{2}+ |\frac{3}{\sqrt{22}}|^{2} }=1
以上により、
u1=(322222322)u_{1}=\begin{pmatrix} \frac{3}{\sqrt{22}}\\ \frac{2}{\sqrt{22}}\\ \frac{3}{\sqrt{22}} \end{pmatrix}
と求まります。
以上が単位ベクトルの求め方です。
次章では、さらに特異値・特異ベクトルとは何なのか深堀りしていきます。

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

◆定義◆

任意の零行列ではないm×nm×n行列AAに対して、
Av=σuAv=\sigma u
ATu=σvA^{T}u=\sigma v
(ただし、σ>0\sigma>0uuvvはともに零ベクトルではない)
を満たすような正の数σ\sigmaを特異値、mm次元ベクトルuuを左特異ベクトル、 nn次元ベクトルvvを右特異ベクトルと呼びます。 [^5]

◆定義式のイメージ◆

特異値・特異ベクトルの定義式が
Av=σuATu=σvAv=\sigma u\\ A^{T}u=\sigma v
である理由は、特異値分解の定義から導き出すことができます。順を追って図示しながら説明します。
まず、特異値分解の定義から
A=UΣVT=(u1u2um)(σ100000σ200000σm00)(v1v2vn)=u1σ1v1T++unσnvnT=σ1u1v1T++σnunvnT(a)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)
に変形することができます。そして、UUVTV^{T}が直交行列であることから
(uiT,uj)=(viT,vj)={0(ij)1(i=j)=δij(b)(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)の両辺に右側からv1v_{1}を掛けると、
Av1=σ1u1v1Tv1++σmumvmTv1=σ1u11++σmum0=σ1u1Av_1=\sigma_1u_1v_1^Tv_1+\dots+\sigma_mu_mv_m^Tv_1\\ =\sigma_1u_11+\dots+\sigma_mu_m0\\ =\sigma_1u_1
となり、特異値・特異ベクトルの定義式の1行目が求まりました。
ATA^{T}に関して特異値分解の定義から式(a)の様に
AT=(UΣVT)T=VΣTUT=σ1Tv1u1T++σmTvmumT=σ1v1u1T++σmvmumT(c)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)の両辺に右側からu1u_{1}を掛けると、
Au1=σ1v1u1Tu1++σmvmumTu1=σ1v11++σmvm0=σ1v1Au_1=\sigma_1v_1u_1^Tu_1+\dots+\sigma_mv_mu_m^Tu_1\\ =\sigma_1v_11+\dots+\sigma_mv_m0\\ =\sigma_1v_1
となり、特異値・特異ベクトルの定義式の2行目が求まりました。
ここで、実例を用いて式(a)に関して更に理解を深めましょう。
取り扱う行列AA
A=(211112)A=\begin{pmatrix}2&1&1\\1&1&2\end{pmatrix}
です。この行列AAを特異値分解して(a)の様に変形し、左辺第一項のみを取り出した
A=σ1u1v1T(d)A=\sigma_1u_1v_1^T…(d)
を計算すると
A=u1σ1v1T=12(1010)(1100000)122(323000000)=(311222311222211222211222311222311222)=(1.511.51.511.5)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}
となります。図示してみると以下の通りになります。
固有値・固有ベクトルのイメージ.drawio.png
この式(d)の両辺にv1v_{1} を掛けると
Av1=σ1u1v1Tv1Av_{1}=\sigma_1u_1v_1^Tv_{1}
であり、左辺を計算すると
Av1=(211112)122(300200300)=(11221122)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}
となり、右辺を計算すると
u1σ1v1Tv1=12(1010)(1100000)122(323000000)122(300200300)=u1σ1=12(1010)(1100000)=(112112)=σ1u1u_{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}
となります。つまり、
Av1=σ1u1(11221122)=(112112)1111Av_{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}}
になります。これで更に特異値・特異ベクトルの定義式の理解が深まりました。

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

定義式を変形すると特異値と固有値の関係が見えてきて、固有値分解の手法を使って計算可能であることが分かります。それでは説明していきます。
まず、定義式の一行目の両辺にAAを右から、定義式の二行目の両辺にATA^{T}を左から掛けます。
すると定義式は以下の通りに変化します。
ATAv=σATv=σσv=σ2vAATu=σAu=σσu=σ2uA^{T}Av=\sigma A^{T}v=\sigma \sigma v=\sigma^{2}v\\ AA^{T}u=\sigma Au=\sigma \sigma u=\sigma^{2}u
簡潔にはこうです。
ATAv=σ2vAATu=σ2uA^{T}Av=\sigma^{2}v\\ AA^{T}u=\sigma^{2}u
この形、何かに似ていると思いませんか?
そうです、固有値・固有ベクトルの定義
Av=σvAv=\sigma v\\
です。つまり、
ATA=σ2AAT=σ2A^{T}A=\sigma^{2}\\ AA^{T}=\sigma^{2}
だということです。特異値がAATAA^{T}の固有値λ\lambdaの非負の平方根λ\sqrt{\lambda}なのは、この式から導かれたものだったのです。これにより、特異値分解だけの複雑な計算方法を覚えることなく、慣れ親しんだ固有値分解の手法をそのまま使ってもよいことになるのです。

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

ここで、もう一つのアプローチ方法を示したいと思います。人によってはこちらの方が分かりやすいかもしれません。それでは説明していきます。
まず、固有値分解の定義と転置行列の性質から、
A=UΣVTAT=VΣTUTA=UΣV^{T}\\ A^{T}=VΣ^{T}U^{T}
が得られます。そうすると、ATAA^{T}A
ATA=VΣTUTUΣVTA^{T} A= VΣ^{T}U^{T}UΣV^{T}
で表せ、直交行列の性質からUTU=I,VVT=IU^{T}U=I,VV^{T}=Iなので、
ATA=VΣTΣVT=ΣTΣA^{T}A=VΣ^{T}ΣV^{T}=Σ^{T}Σ\\
と式変形でき、
ATA=ΣTΣA^{T}A=Σ^{T}Σ
であることが分かります。
次に、AATAA^{T}
AAT=UΣVTVΣTUTAA^{T}=UΣV^{T}VΣ^{T}U^{T}
で表せ、直交行列の性質からUUT=I,VTV=IUU^{T}=I,V^{T}V=Iなので、
AAT=UΣΣTUT=ΣΣTUUT=ΣΣTAA^{T}=UΣΣ^{T}U^{T}=ΣΣ^{T}UU^{T}= ΣΣ^{T}\\
と式変形でき、
AAT=ΣΣTAA^{T}=ΣΣ^{T}
であることが分かります。
つまり、
ATA=ΣTΣAAT=ΣΣTA^{T}A=Σ^{T}Σ\\ AA^{T}=ΣΣ^{T}
です。結果的に、特異値・特異ベクトルの定義式から導き出した
ATA=σ2AAT=σ2A^{T}A=\sigma^{2}\\ AA^{T}=\sigma^{2}
と同義ですが、行列の形と大きさが簡単に求められるのでこちらの方が便利かもしれないです。

〔特異値分解の求め方〕

これまで学んできたことを使って実際に計算してみましょう。
今回取り扱う行列は2×32×3の以下の行列です。
A=(211112)A=\begin{pmatrix}2&1&1\\1&1&2\end{pmatrix}
手順を確認しながら進めていきましょう。
  1. (rmn)(r≤m≤n)であるm×nm×n行列AAUΣVTUΣV^{T}に分解する際の各行列の形と大きさを確認する
    ΣΣ:固有値が重解でない限りr=mr=mなので、形と大きさは②’を想定して2×32×3
    UU:固有値が重解でない限りr=mr=mなので、形と大きさは②’を想定して2×22×2
    VTV^{T}:固有値が重解でない限りr=mr=mなので、形と大きさは②’を想定して3×33×3
  2. 転置行列ATA^{T}を求める
    AT=(211112)A^{T}=\begin{pmatrix}2&1\\1&1\\1&2\end{pmatrix}
  3. AATAA^{T}の固有値λ\lambdarr個求める
    まずは実対称行列AATAA^{T}を求めます。
    AAT=(211112)(211112)=(6556)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}
    次に、固有方程式にAATAA^{T}を代入してλλについて解きます。
    det(AλI)=(6556)(λ00λ)=6λ50506λ=0det(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=λ212λ+11=(λ11)(λ1)=0(6-λ)(6-λ)-25=λ^{2}-12λ+11=(λ-11)(λ-1)=0
    となり、よって固有値はλ=11,1λ=11,1です。
    この後、各固有値を使ってそれぞれの固有ベクトルを求めるためλ1=11λ2=1λ1=11,λ2=1と置きます。
  4. AATAA^{T}の固有値λ\lambdaの非負の平方根λ=σ\sqrt{\lambda}=\sigmaを大きい順に並べてΣΣを完成させる
    まず、〔特異値分解とは〕の◆定義◆より、今回の例では
    Σ=(σ1000σ20)Σ= \begin{pmatrix} \sigma_{1}&0&0\\ 0&\sigma_{2}&0 \end{pmatrix}
    であることが分かります。
    AAT=ΣΣTAA^{T}=ΣΣ^{T}
    なので、AATAA^{T}の固有値λ1=11λ2=1λ1=11,λ2=1
    (λ100λ2)=(11001)\begin{pmatrix} λ_{1}&0\\ 0&λ_{2} \end{pmatrix}= \begin{pmatrix} 11&0\\ 0&1 \end{pmatrix}
    とすると、
    ΣΣT=(σ1000σ20)(σ100σ200)=(σ1200σ22)=(λ100λ2)=(11001)ΣΣ^{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}
    と表せて
    σ12=11,σ22=1σ1=11,σ2=1σ_{1}^{2}=11,σ_{2}^{2}=1\hspace{10pt}\therefore σ_{1}=\sqrt{11},σ_{2}=1
    となります。
    この結果から固有値λ1=11λ2=1λ_{1}=11,λ_{2}=1の非負の平方根 λ1=11λ2=1\sqrt{λ_{1}}=\sqrt{11},\sqrt{λ_{2}}=\sqrt{1}を大きい順に並べて
    Σ=(λ1000λ20)=(1100010)Σ= \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. AATAA^{T}の固有値λ\lambdaから正規化した固有ベクトルuuを求め、UUを完成させる
    同次連立一次方程式
    (AλiI)uj=0(i=1,2,...,n)(j=1,2,...,n)(A-\lambda_{i} I)\boldsymbol{u_{j}}=0\\ (i=1,2,...,n)(j=1,2,...,n)
    の自明でない解を求めます。
    まず、λ1=11λ1=11の場合について計算します。
    ここではuuを一つ目の固有ベクトルとしてu1u_{1}と表記し、 (AλiI)u1=0(A−λ_{i}I)u_{1}=0とします。
    ここでλiλ_{i}1111を代入すると
    (AλiI)u1={(6556)(110011)}u1=(6115050611)u1=(5555)u1=0(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
    が求まり、
    u1=(x11x12)\boldsymbol{u_1}=\begin{pmatrix}x_{11} \\x_{12} \\ \end{pmatrix}
    なので
    (AλiI)u1=(5555)(x11x12)=(00)(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}
    となります。係数行列を行基本変形によって階段行列に変形し
    (5555)(1100)\begin{pmatrix}-5 & 5 \\5 & -5 \\ \end{pmatrix} \rightarrow \begin{pmatrix}1 & -1 \\0 & 0 \\ \end{pmatrix}
    が求まるので、u1u_{1}を掛けて
    (1100)(x11x12)=(x11x1200)=(00)\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}
    となるので、x11x_{11}x12x_{12}について一次方程式を解くと
    x11x12=0x_{11}-x_{12}=0
    であり、解は自明ではない解であるため任意定数を用いて
    x11=cx12=cx_{11}=c\\ x_{12}=c
    です。つまり、
    u1=(x11x12)=(cc)=c(11)u_{1}= \begin{pmatrix} x_{11}\\ x_{12} \end{pmatrix}= \begin{pmatrix} c\\ c \end{pmatrix}= c\begin{pmatrix} 1\\ 1 \end{pmatrix}
    です。
    特異値分解では、UUを直交行列にするために固有ベクトルを大きさ1の単位ベクトルに直してあげる必要がありますので、L2L_{2}ノルムを用いて
    x2=c2+c2=2c2=2c2=2c=1\|x\|_{2}=\sqrt{|c|^{2}+|c|^{2}}=\sqrt{2c^{2}}=\sqrt{2}\sqrt{c^{2}}=\sqrt{2}c=1
    x2=c=12\|x\|_{2}=c=\frac{1}{\sqrt{2}}
    以上により
    u1=12(11)=(1212)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λ_{2}=1の場合について計算します。
    λ1=11λ_{1}=11の場合と同様の計算を行った結果、
    u2=(1212)u_{2}=\begin{pmatrix} \frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\\ \end{pmatrix}
    と求まりました。
    よって、
    U=(u1u2)=(12121212)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. ATAA^{T}Aの固有値λ\lambdann個求める
    VTV^{T}nn次元正方行列を満たすために固有ベクトルがnn個ある必要があるため、ATAA^{T}A の固有値もnn個必要です。今回の例では固有値が3つ必要です。しかし、手順3で求めた固有値は2つです。ですので、残り1つの固有値を何かで補う必要があります。そこで登場するのが固有値λ3=0λ_{3}=0 です。
    λ1=11,λ2=1,λ3=0λ_{1}=11,λ_{2}=1,λ_{3}=0を代入してみると
    (λ1000λ2000λ3)=(1100010000)\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λ_{3}=0を用いるのかは、◆固有値分解の定義式から求める特異値と固有値の関係◆より、
    ATA=ΣTΣA^{T}A=Σ^{T}Σ
    を使って説明できます。
    AATAA^{T}の固有値λ1=11λ2=1λ1=11,λ2=1λ3=xλ_{3}=xを加えたATAA^{T}Aの固有値を
    (λ1000λ2000λ3)=(110001000x)\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=(σ100σ200)(σ1000σ20)=(σ12000σ220000)=(λ1000λ2000λ3)=(110001000x)ΣΣ^{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}
    と表せて
    σ12=11,σ22=1,0=xσ_{1}^{2}=11,σ_{2}^{2}=1,0=x
    となります。よって、固有値λ3=0λ_{3}=0となります。
  7. ATAA^{T}Aの固有値λ\lambdaから正規化した固有ベクトルvvを求め、VVを転置させて完成させる
    UUと同じく同次連立一次方程式
    (AλiI)uj=0(i=1,2,...,n)(j=1,2,...,n)(A-\lambda_{i} I)\boldsymbol{u_{j}}=0\\ (i=1,2,...,n)(j=1,2,...,n)
    の自明でない解を求め…なくてもVVを計算できる方法があるのでご紹介します。
    それは、
    vi=1λiATuiv_{i}=\frac{1}{\sqrt{\lambda_{i}}}A^{T}u_{i}
    です。
    これは、σi=λiσ_{i}=\sqrt{λ_{i}}であることから、定義式
    ATu=σvA^{T}u=\sigma v
    を変形して
    ATui=λivivi=1λiATuiA^{T}u_{i}=\sqrt{λ_{i}}v_{i}\rightarrow v_{i}=\frac{1}{\sqrt{\lambda_{i}}}A^{T}u_{i}
    としたものである。これで、UUで求めたrr固有値と固有ベクトルを使ってvvの固有ベクトルをrr個まで求めることができます。
    実際に計算してみると、v1v_{1}
    v1=1λ1ATu1=111(211112)(1212)=111(322232)=(322222322)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}
    であり、v2v_{2}
    v2=1λ2ATu2=11(211112)(1212)=(12012)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λ_{3}=0の場合の固有ベクトルv3v_{3}を求めます。
    計算結果は
    v3=(111311111)v_{3}= \begin{pmatrix} -\frac{1}{\sqrt{11}}\\ -\frac{3}{\sqrt{11}}\\ \frac{1}{\sqrt{11}} \end{pmatrix}
    です。導出は自分で計算してみましょう。
    よって、
    V=(u1u2u3)=(32212111222031132212111)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)
    が完成します。
    最後に、
    (32222232212012111311111)\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. 1で確認した形と大きさに当てはまっているか確認する
    U=(12121212)Σ=(1100010)VT=(32222232212012111311111)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)
    UU2×22×2ΣΣ2×32×3VTV^{T}3×33×3で初めの想定と同じ形と大きさの行列であることが確認できます。
  9. 特異値分解A=UΣVTA=UΣV^{T}の完成!!
    A=UΣVT=(12121212)(1100010)(32222232212012111311111)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ΣVTUΣV^{T}と行列Aが一致するか確認する
    各自確め計算をしてみましょう。
今回は、記事があまりにも長すぎるために計算リソースが足りなくてErrorを吐いてしまうということがあるということで、続きは後編に分割して投稿することにしました。下記リンクから後編へどうぞ。

Discussion

コメントにはログインが必要です。