HN 日本語サマリー

← 一覧へ戻る
科学・技術

SVDを意識せずに導出する

Deriving SVD without even aiming at it (stillthinking.net)

28 pointsby pcael9 コメント

要約

この記事は、数学における概念の理解と学習方法について考察し、特に線形代数の特異値分解(SVD)を、その最終的な形式からではなく、より直感的で自然な方法で導出することを試みています。著者は、伝統的な数学書が概念の構造を把握するための道筋を示さず、形式化された最終形を提示する傾向があると指摘し、応用数学の概念は特定の課題を解決するために生まれたという視点からSVDを解説しています。具体的な線形変換の例を通じて、基底の選択がいかに複雑な表現を生み出すかを示し、行列の対角化が可能な場合のメリットと、そうでない場合にSVDがいかに有用であるかの直感的な説明を行っています。

全文翻訳

数学におけるつながり:SVDをゼロから導出する

免責事項:この記事の執筆にAIは使用されていません。不正確な表現、ぎこちない文章、奇妙な脱線はすべて100%オーガニックで、自由に飼育された人間が作成したものです。

本当に何かを学ぶには?

長い間、私は数学で何かを学ぶ、あるいは理解するとはどういうことなのかを自問してきました。これは他の分野にも拡張できると思いますが、数学の多くの概念は日常生活からかけ離れていることが多く、私にとって(少なくとも)直感的で自然な理解を得るのは難しいです。それは、概念の基盤となる構造を与え、後で自分で詳細を再構築できるようにするような理解です。私は、いくつかの分野で本当に一般的な構造を捉えたという感覚を何度か経験しました。それにより、現在理解していることだけを参照して、自分自身で表現したり、事実を推論したりすることができます。その良い例は、実解析(Real Analysis)を初めて学んだ時の経験です。最初は非常に混乱して難しく見えましたが、しばらくすると主要な概念の構造を捉えることができ、ほとんど自分で概念を動かせるようになります。

しかし、理解するのに時間がかかったことが一つあります。従来の数学の教科書は、構造を捉えるための道筋や、より直感的または自然な方法(後で再構築できるような)で概念を理解するための道筋を与えてくれないことが非常に多いのです。これは、ほとんどの数学の教科書が数学をその最終的な形式化されたバージョンで提示するからです。しかし、そこに至るまでの道筋――しばしば乱雑で、実験的で、試行錯誤的で、暫定的だった――を隠してしまいます。

このブログは、あなたがすでに数学の基本的な知識を持っていることを前提としています。最初からすべてを教えるのは現実的ではありませんが、私の目標は、概念を理解するのに役立ったつながりをここでいくつか書くことです。

何かから始める

線形代数(L.A.)から始めることにしました。それは数学の中で最も応用が効き、アクセスしやすい分野の一つです。線形代数の中核的な概念である特異値分解(SVD)を紹介されたとき、それを本当に理解するのに時間がかかりました。そして、ほとんどの教科書がそれを単純な方法で説明できないのは、通常、読者にとって意味をなさない最終的な結論から形式的に述べるからです。なぜこれがそもそも作られたのか、その動機を紹介することが極めて重要だと思います。応用数学のほとんどのものは、誰かが解決しようとしていた特定の具体的な問題から生まれました。線形代数は、より高度な非線形分野よりもある程度単純であるだけでなく、微積分、情報理論、画像処理、機械学習など、他の多くの分野とつながっているため、始めるのに良い場所です。それはある種の基本的または中心的な分野ですが、どこから始めても、十分に掘り下げ続ければ、他の分野とのつながりに到達できると思います。そして、線形代数ではこれがさらに明らかです。

目標を定めずに、自然にSVDに到達しましょう。線形変換Aの行列は、選択された入力基底と出力基底によって、同じ線形変換に対して異なる形で書くことができます。それを理解するために、意図的に単純な線形写像を考えてみましょう――x軸を3倍に引き伸ばし、y軸はそのままにします。

A(x,y) = (3x, y)

標準基底では、その行列は基底ベクトルがどこに着地するかを読み取るだけです。

M = [[3, 0], [0, 1]]

これ以上明確なものはありません。「一方の軸を引き伸ばす」です。

今、この同じ写像を歪んだ基底で記述してみましょう。傾いた、非直交基底を選択します。

P = [[1, 1], [1, 2]], P⁻¹ = [[2, -1], [-1, 1]]

この基底における同じ変換の行列は P⁻¹MP です。

P⁻¹MP = [[2, -1], [-1, 1]] [[3, 0], [0, 1]] [[1, 1], [1, 2]] = [[5, 4], [-2, -1]]

同じ変換です。実際のすべてのベクトルに対する同じ写像です。しかし、今ではそれはスケーリング、せん断、符号反転の任意の絡み合いのように見えます――それが単に「x軸を3倍に引き伸ばす」ことだったとは決して推測できないでしょう。

複雑さは決して写像にあったのではなく、基底にあったのです。

場合によっては、行列を対角化できます。これは、Aの行列を対角にするような新しい基底を選択することによって行われます(これはAが固有ベクトル基底を許容する場合にのみ可能です。ただし、この事実は証明せずに残しておきます)。もちろん、すべての線形変換が固有ベクトル基底を許容するわけではありません。実際、一部の線形変換は正方行列でさえありません(例:入力次元が出力次元と同じでない場合)。固有ベクトルはスケールを除いて固定されたままであるため、入力と出力を同じ次元に明らかに制限するため、固有ベクトルについて話すことさえできません。

行列を対角化できる場合、興味深いことが起こります。線形変換自体が、選択された基底によってより複雑に見える単純な非一様スケーリングにすぎないことがはっきりとわかります(前の操作とは逆で、単純なスケーリングがより複雑な行列形式で表されることを示しました)。そこで、対角化可能な線形変換Aの行列Mを取り、次のように書きます。

M = P⁻¹DP

そして、Mは対角行列に相似になります。したがって、潜在的に複雑なMは、行列の対角線上のいくつかの数値と、それ以外のすべてのゼロであり、特別な基底変換行列Pによるものです。これはコンピューターに保存したり、行列乗算を効率的に実行したりするのに最適です。データを一度Pの参照フレームに変換し、対角行列(簡単)を使用して数百万回の行列乗算を行い、元のフレームにP⁻¹を使用して戻すことができます。この単純化は、線形変換Aから構造を抽出できたために可能です。

行列を対角化できないのはいつでしょうか?対角化可能な行列が特別な座標系でのスケーリングの隠れ蓑にすぎない場合、線形変換が隠れ蓑スケーリング以上のものになったときに、対角化に失敗します(実際、これはAが固有ベクトルの基底を許容できないことと同等です――自分で証明してみてください)。たとえば、Aが2次元回転の場合、独立した2つの固有ベクトルを持ちません(実固有ベクトルはまったくありません。回転は平面内のすべての方向を移動させます!)。Aが2次元せん断の場合も、同様の理由で対角化できません。では、対角化可能な線形変換の場合と同じように、任意の線形変換から構造を抽出できるでしょうか?もしそれができれば、対角行列の場合のように、いくつかの利点を得られるかもしれません。

直感的には、任意の線形変換によるN次元単位球がどうなるかを見ることができます。それは単射でない可能性があります。つまり、一部の方向は消滅する可能性があります(0に潰れる――球は円盤に平坦化します)。他の方向を任意の値でスケーリングする可能性があります(球または円盤は楕円体または楕円になります)。任意の軸を通る任意の角度で他の方向を回転させるかもしれません。また、他の方向に球をせん断するかもしれません(せん断された球は依然として回転した楕円体です)。

この単純な事実は以下のように書くことができます。

sᵢ uᵢ = A vᵢ

ここで sᵢ はスカラー――ストレッチ係数――であり、uᵢ は単位出力方向です。それだけです。uᵢ と vᵢ を分離し、それらが固有ベクトルであることを要求しません。それらは単に任意のベクトルです。上記の式は新しい事実を導入していません。それは任意の線形変換に起こることですが、単位球が何らかの方法で回転した楕円体にマッピングされるという私たちの感覚を確かに捉えています。sᵢ をスケール係数、uᵢ を新しい回転した方向と見なせばそうです。私たちの感覚は今、線形変換が複数の種類の操作(回転、せん断、スケーリング)を実行する可能性があるということです。これは、対角化の場合と同様に、分解して分離し、最初は複雑に見えた変換の単純な構造を明らかにできる可能性があります。

前述のように、歪んだ基底は線形変換行列を表すのに最適ではありません。なぜなら、それらは座標基底ベクトルを混合するからです。各基底ベクトルは他のベクトルへの非ゼロ射影を持ちます。次に取るべき明白なステップは、基底 uᵢ と vᵢ が正規直交である場合に何が起こるかを見ることです。uᵢ と vᵢ が正規直交であることを常に要求できますか?私たちはそれができること、そしてそれが興味深くきちんとした事実であることを確認します。

私たちが要求していることを見てみましょう。出力ベクトルが正規直交であること:

i ≠ j ⇒ <A vᵢ, A vⱼ> = 0, <A vᵢ, A vᵢ> = 1 (1)

そして同時に、入力ベクトルが正規直交であることを望みます:

i ≠ j ⇒ <vᵢ, vⱼ> = 0, <vᵢ, vᵢ> = 1 (2)

ここで、非常に興味深いことが起こります。内積の出力を A をもう一方の辺に移動させて書き換えます(<Ax, y> = <x, Aᵀy> を使用):

<A vᵢ, A vⱼ> = <vᵢ, AᵀA vⱼ> = vᵢᵀAᵀA vⱼ (1.1)

ここまでは新しいことは何もありません――同じ式を書き換えただけです。しかし、今、AᵀA が明示的に現れ、それは対称行列です!任意の(潜在的に非正方)行列 C を取り、CᵀC を形成すると、対称行列が得られます。ここで、非常に重要な事実は、対称行列は常に固有ベクトルの正規直交基底を許容するということです(これがスペクトル定理です)。したがって、vᵢ を AᵀA の正規直交固有ベクトルとして選択しましょう。これにより、入力の正規直交性(2)が自動的に得られます。

しかし、ここが重要な点です。この選択は、出力の直交性(1)も自動的に与えます。i ≠ j の対角外の場合に何が起こるかを見てみましょう。vⱼ は AᵀA の固有ベクトルなので、AᵀA vⱼ = λⱼ vⱼ となります。したがって:

i ≠ j ⇒ <A vᵢ, A vⱼ> = vᵢᵀAᵀA vⱼ = λⱼ vᵢᵀvⱼ = λⱼ ⋅ 0 = 0 (1.2)

出力は、入力が AᵀA の直交固有ベクトルであったために、正確に直交します。出力の直交性を別途要求する必要はありませんでした――それは入力の選択から自然に導かれました。そして、それらの出力の長さは正確にスケール係数です:<A vᵢ, A vᵢ> = λᵢ。したがって、sᵢ = ||A vᵢ|| = √λᵢ となり、正規化すると正規直交出力方向 uᵢ = A vᵢ / sᵢ が得られます。

したがって、一般的に、A自体を対角化する正規直交基底を見つけることはできませんでした――しかし、対称行列 AᵀA に対しては常に正規直交基底を見つけることができ、それがまさに私たちが探していた入力基底です。

AのランクとAᵀAのランク

AのランクがAᵀAのランクと同じであるという、もう一つの驚くべき事実があります。これはすぐに必要になるので、まず証明しましょう。

A: ℝᴺ → ℝᴹ を考えます。ランク・ヌルティ定理によれば、

rank(A) = N - dim(Ker(A))

ここで N は入力次元です(カーネルは入力空間 ℝᴺ に存在します)。ここで、AᵀA は N×N 行列です(Aᵀ は N×M、A は M×N なので)。したがって、AᵀA も ℝᴺ → ℝᴺ をマッピングします。同じランク・ヌルティ定理により、

rank(AᵀA) = N - dim(Ker(AᵀA))

両方の写像は同じドメイン次元 N を持ちます。したがって、ランクが等しいことを証明するには、カーネルが等しいことを証明すれば十分です。

Ker(A) = Ker(AᵀA)

証明。

(1) まず、Ker(A) ⊆ Ker(AᵀA) — 簡単な方向:

v ∈ Ker(A) ⇒ Av = 0 ⇒ Aᵀ(Av) = 0 ⇒ v ∈ Ker(AᵀA)。

(2) 次に、Ker(AᵀA) ⊆ Ker(A) — より自明でない方向。最初は、Aのカーネルにないベクトルvが、AᵀAのカーネルに着地する可能性を止めるものは何もありません。その場合、Av ≠ 0 であっても AᵀAv = 0 になります。しかし、これは起こりえないことが判明します。AᵀAv = 0 と仮定します。すると Aᵀ(Av) = 0 となり、Av ∈ Ker(Aᵀ) となります。2つのケースがあります。

  • Av = 0 の場合、v ∈ Ker(A) となり、これで完了です。
  • Av ≠ 0 の場合、これはゼロでないベクトルを Im(A)(Av は A の出力なので)と Ker(Aᵀ) の両方に配置することになります。

しかし、この2番目のケースは不可能です。なぜなら、

Im(A)⊥ = Ker(Aᵀ) ⇒ Im(A) ∩ Ker(Aᵀ) = {0}

(部分空間とその直交補空間はゼロベクトルのみを共有します)。したがって、Av = 0、つまり v ∈ Ker(A) となります。■

この2番目の方向を証明する、より単純で自己完結した方法は、内積の正定値性を直接使用することです。

AᵀAv = 0 ⇒ vᵀAᵀAv = 0 ⇒ (Av)ᵀ(Av) = 0 ⇒ ||Av||² = 0 ⇒ Av = 0。

最後のステップはまさに正定値性です。ゼロベクトルだけがゼロの長さを持っています。どちらの方法でもうまくいきます。最初の方法は4つの基本的な部分空間につながり、2番目の方法は内積に直接向かいます。

何かを組み立てる前に、任意の線形写像 A(M×N 行列)について、今わかっていることをリストアップしましょう。対角化可能な良い行列に対して行ったのと同じように、一般的な写像に対しても構造を抽出することを目指しました――かなりの量を抽出できることがわかりました。

  • 両側の正規直交フレーム。AᵀA は対称行列なので、スペクトル定理は入力方向 vᵢ の正規直交基底(その固有ベクトル)を私たちに与えます。それらを A でプッシュし、正規化すると、出力方向 uᵢ の正規直交基底が得られます。どちらのフレームもきれいで、歪みはありません。

  • ランクが一致する。rank(AᵀA) = rank(A) = r を証明しました。したがって、固有値 λᵢ のちょうど r 個がゼロでなく、ちょうど r 個のゼロでないスケール係数 σᵢ = √λᵢ が得られます。残りの N-r 入力方向はカーネルです――A はそれらをゼロにマッピングします。

  • 中央のきれいな全単射。その r 個の生き残った入力方向は線形独立です(それらは正規直交基底の一部です)。そして、それらは r 個の線形独立な出力方向へ、1対1でマッピングされます:A vᵢ = σᵢ uᵢ。生き残った方向では、A は2つの正規直交フレーム間のクリーンで可逆なスケーリングにすぎません――それ以外のすべてを消滅させます。

最後の点は核心です。カーネルを取り除くと、A はエキゾチックなことは何も行いません。r 個の直交する入力方向を r 個の直交する出力方向にマッピングし、それぞれを独自の係数 σᵢ でストレッチします。複雑な変換は、再び、隠れ蓑にされた単純なスケーリングでした――それを見るためだけに、1つではなく2つの正規直交フレームが必要だったのです。

因数分解にまとめる

今、これらの r 個の関係を単一の行列方程式にまとめます。これは、最初に書いた sᵢ uᵢ = A vᵢ とまったく同じ関係であることに注意してください――今では vᵢ と uᵢ が正規直交として選択できること、そしてスケールが sᵢ = σᵢ = √λᵢ であることを知っています。生き残った方向ごとに1つずつ、次のようになります。

A vᵢ = σᵢ uᵢ, i = 1, ..., r

ここで {vᵢ} は入力空間で正規直交、{uᵢ} は出力空間で正規直交です。vᵢ を Vᵣ(N×r)の列として、uᵢ を Uᵣ(M×r)の列として配置します。Vᵣ の各列に A を適用すると AVᵣ となり、右辺――各 uᵢ を σᵢ でスケーリングしたもの――は、列がスケーリングされた Uᵣ であり、対角 Σᵣ が現れるまさにその場所です。

AVᵣ = ( | | | | σ₁u₁ ... σᵣuᵣ | | | | ) = Uᵣ Σᵣ

ここで Uᵣ = ( | | u₁ ... uᵣ | | )、Σᵣ = diag(σ₁, ..., σᵣ) です。

したがって、AVᵣ = UᵣΣᵣ です。2つの行列を収集してから、別に3番目の行列を分解するわけではありません――対角 Σᵣ はそれ自体で現れます。なぜなら、Uᵣ の各列をその係数 σᵢ でスケーリングすることは、Uᵣ の右から対角行列を掛けることと同じだからです。方向ごとのスケールは、自動的に対角線上に集まります。

A を分離するために、右から Vᵣᵀ を掛けます。

A Vᵣ Vᵣᵀ = Uᵣ Σᵣ Vᵣᵀ。

ここで注意が必要です。VᵣVᵣᵀ は正規直交列を持つため、VᵣᵀVᵣ = Iᵣ ですが、VᵣVᵣᵀ は完全な N×N 単位行列ではなく、vᵢ のスパンへの直交射影です。そのスパンは A の行空間であり、その補空間はカーネルであり、A はそれを消滅させます。したがって、それを射影しても何も変わりません。A Vᵣ Vᵣᵀ = A なので、次のようになります。

A = Uᵣ Σᵣ Vᵣᵀ

幅 r の3つの部分:正規直交出力フレーム Uᵣ、ストレッチの対角 Σᵣ、正規直交入力フレーム Vᵣᵀ。

その背後にある幾何学:4つの部分空間

ランク証明で、Im(A)⊥ = Ker(Aᵀ) という事実に頼りましたが、実際には見ていませんでした。それは立ち止まって見る価値があります。なぜなら、それは多くの幾何学的洞察を運び、細いSVDを構築したときにカーネル方向をきれいにドロップできた理由を説明するからです。

線形写像 A は、その2つの空間それぞれを生きている部分と死んでいる部分に分割します。入力空間 ℝᴺ では、生きている部分は行空間(A が実際に作用する方向)であり、死んでいる部分はカーネル(A がゼロにマッピングする方向)です。出力空間 ℝᴹ では、生きている部分は像(A が到達できる方向)であり、死んでいる部分は Ker(Aᵀ)(どの入力もマッピングしない方向)です。そして、両方の空間で、生きている部分と死んでいる部分は直交します。

ℝᴺ = Row(A)(生きている) ⊕ Ker(A)(死んでいる)
ℝᴹ = Im(A)(生きている) ⊕ Ker(Aᵀ)(死んでいる)

[画像:4つの基本的な部分空間]

これを2次元、最も単純なケースで描いてみましょう。各空間には2つの直交する線があります。1つは生きている、もう1つは死んでいる。ここで、すべてを理解させる洞察があります。入力の生きている線(行空間)上にあるベクトル v を取ります。A を適用します。それは出力の生きている線(像)に着地し、σ でストレッチされます。次に Aᵀ を適用して戻します。Aᵀ はそれを消滅させることができますか?それは Ker(Aᵀ)――死んでいる出力線――に位置するベクトルだけを消滅させることができます。しかし、私たちのベクトル Av は生きている出力線上にあり、それは死んでいる線と直交しています。生きている線上に完全に位置するベクトルは、死んでいる線に沿ってゼロ成分を持ちます。したがって、Aᵀ がそれを消滅させるものはありません――それはベクトルを忠実に、入力の生きている線に戻します。

それが、往復が生きている方向を維持する理由のすべてです。死んでいる方向は、生きているベクトルが存在する場所と直交しているため、それらに侵入して消滅させることはできません。生きている部分と死んでいる部分が補完的であるだけで歪んで(直交せず)いた場合、生きているベクトルは死んでいる方向へのこっそりとした成分を運び、失う可能性があります。生きている部分空間を「純粋」に保つのは、直交性――そして直交性だけです。これが、細いSVDを構築したときにカーネル列をドロップすることが何も変えなかった理由です。保持された方向と破棄された方向は直角に配置されているため、破棄は重要なものに触れません。

別の書き方:一次元の断片の合計

これまでのところ、SVD を3つの行列の積として書きました、A = Uᵣ Σᵣ Vᵣᵀ。しかし、この同じ方程式を、より洞察に富む別の読み方があります。それを展開すると、積は合計になります。

A = ∑ᵢ<0xE2><0x82><0x9D>₁ʳ σᵢ uᵢ vᵢᵀ

各項 uᵢ vᵢᵀ は外積です。列ベクトルに列ベクトルを掛けたもので、完全な M×N 行列になります――しかし、非常に特別なものです。それはランク1を持ちます。各列は uᵢ の倍数であり、各行は vᵢ の倍数です。それは最も単純な非自明な行列、単一の「パターン」です。したがって、この式は驚くべきことを述べています。任意の行列は、それぞれの単一値 σᵢ でスケーリングされた、ランク1のパターンの合計 r 個です。写像は、最も強い(σ₁)から最も弱い(σᵣ)までの r 個の一次元の断片を積み重ねることによって構築されます。

これはランクにも明確な2番目の意味を与えます。それは、行列を構築するために必要なランク1の断片の最小数です。そして、それは単なる「ストレッチ係数」を超える単一値の意味を与えます。それらを σ₁ ≥ σ₂ ≥ ... ≥ σᵣ > 0 の順に並べます。大きい σᵢ は、その方向が行列の多くを運ぶことを意味します――それは強く、真に存在するパターンです。小さい σᵢ は、その方向がほとんど貢献しないことを意味します。行列は、それなしでもほぼ同じです。σᵢ がちょうどゼロである場合、その方向はまったく貢献しません(それは実際には存在しませんでした――それはカーネルです)。したがって、単一値は、その独立した方向が行列全体にとってどれだけ重要かを測定します。

小さな断片を捨てる:圧縮

行列をランク1の断片の順序付けられた合計として見ると、アイデアは避けられません。最初の数個だけを保持したらどうなるでしょうか?上位 k 個の断片を保持し、残りをドロップすることによってランク kTruncationを定義します。

A<0xE2><0x82><0x96> = ∑ᵢ<0xE2><0x82><0x9D>₁ᵏ σᵢ uᵢ vᵢᵀ, k < r.

これはより単純な行列です――断片が少なく、保存するものが少ない――それは元の行列を近似します。近似の精度はどうでしょうか?これが美しい部分です。エッカート・ヤングの定理は、A<0xE2><0x82><0x96> が A の可能な限り最良のランク k 近似であることを述べています。ランク k のすべての行列の中で、A に近いものはありません(最小二乗/フロベニウスの意味で)。そして、あなたが犯す誤差は、あなたが捨てた単一値によって正確に制御されます。

||A - A<0xE2><0x82><0x96>||<0xE2><0x82><0x97>² = ∑ᵢ<0xE2><0x82><0x9D><0xE2><0x82><0x96>₊₁ʳ σᵢ².

したがって、再構築誤差は、捨てられた単一値の二乗の合計にすぎません。もし小さな σᵢ が本当に小さいなら、それらをドロップしても行列はほとんど変わりません――しかし、保存する量ははるかに少なくなります。これは可逆圧縮であり、SVD は最適な圧縮方法と、そのコストが正確に何であるかを教えてくれます。

[画像:上位 k 個のランク1層から行列を再構築する]

上記は、単一の行列(画像と考える)が上位 k 層から再構築されたものです。k=1 では、支配的な構造がすでにわかります。k=8 では、それは本質的に存在します。残りの数十個の断片は、細部とノイズを追加するだけです。行列全体を保存しているわけではありません――少数の強力なパターンを保存し、弱いパターンの長い尾を破棄しています。

なぜこれが実生活でうまくいくのでしょうか?なぜなら、ほとんどの実数行列は圧縮可能だからです。その単一値スペクトルは急速に減衰します。

[画像:単一値スペクトルが急速に減衰する]

上記のスペクトルは、最初のいくつかの値の後に崖のように落ち込みます。その崖は、行列が技術的には数字でいっぱいであるにもかかわらず、実際の内容はわずか数方向しか生き残っていないことを告白しているのです。残りは冗長性です。

情報とエントロピーへのリンク

ここで線形代数が情報理論に静かに触れる場所であり、私が最も満足しているつながりです。二乗単一値 σᵢ² を各方向が運ぶ「エネルギー」と考えてください。それらを合計が1になるように正規化すると、

pᵢ = σᵢ² / ∑ⱼ σⱼ²,

そして、方向に対する確率分布が得られます――行列のエネルギーがその独立したパターンにどのように分散しているか。今、スペクトルの形状は情報に関する声明になります。

  • いくつかの pᵢ が1に近く、残りが0に近い場合(スパイク状の分布、低エントロピー)、行列は非常に冗長です――ほとんどすべての内容が数方向に集中しており、劇的に圧縮できます。
  • すべての pᵢ がほぼ等しい場合(平坦な分布、高エントロピー)、行列は「非圧縮可能」です――すべての方向がほぼ同じように重要であり、破棄するものは何もありません。

この意味で、単一値分布のエントロピーは、行列がどれだけの真の情報を運んでいるか、そしてどれだけの冗長性があるかの尺度です。小さな σᵢ を切り捨てることによる圧縮は、まさに低確率、低情報量の方向を破棄することです――精神的には、任意の信号の可逆圧縮が行うのと同じ操作です。単一値は変換を分解するだけでなく、重要度順にコンテンツをランク付けします。そして重要度とは情報です。

実践に投入する

行列をより単純な方法で記述しようとすることから始め、驚くほど多くのことを行うツールを手に入れました。

  • 圧縮。上位 k 個のランク1断片を保持すると、可能な限り最良の低ランク近似が得られ、誤差は制御可能であることがわかっています。これは画像圧縮とあらゆる場所での低ランク近似のエンジンです。
  • データの中で重要な方向を見つける。A の行がデータポイントである場合、上位単一方向 vᵢ はデータにおける最大の変動の方向です――データが実際に広がる方向です。これは主成分分析(PCA)です。それは(中心化された)データ行列のSVDにすぎず、AᵀA は、私たちがずっと計算していた共分散行列の(スケールを除いた)ものです。次元削減は、上位数個の vᵢ への射影と弱いものの破棄にすぎません――データに適用される圧縮と同じ切り捨てです。
  • 写像自体を理解する。ランク、カーネル、像、4つの部分空間――すべてがSVDから直接読み取ることができます。ランクは非ゼロ σᵢ の数であり、カーネルは σᵢ = 0 の方向であり、単一値は写像が空間をどのようにストレッチするかを示します。

そして、これらすべての下には単一の絵があります。それは私たちが断片ごとに構築したものです。すべての線形写像は、正規直交入力方向のセットを直交出力方向のセットにマッピングし、それぞれを σᵢ でストレッチします――球は楕円体になります。圧縮は、その楕円体の長軸を保持することです。PCA はデータ内でそれらを見つけることです。4つの部分空間は、生きている軸と平坦な軸です。それらはすべて同じ事実であり、異なる側面から見られています――これは、式自体よりも、ここで捉えたかったことです。

次に進むこと

単一値スペクトルのエントロピーは、圧縮の1つの種類を与えてくれました。それは、行列のエネルギーがその方向全体にどのように分散しているかを尋ね、エネルギーが数個に集中しているものを冗長と呼びました。しかし、それは純粋に統計的な概念です――それが物事がどれだけ頻繁に起こるかを見るだけで、なぜ起こるかは決して見ません。したがって、この見方では答えられないパズルを残しましょう。100万桁の2つのファイルを取ります。1つはランダムノイズ、もう1つはπの最初の100万桁です。統計的には、それらは区別できません――どちらも一様に表示され、どちらも(エントロピーによって)「非圧縮可能」です。しかし、1つは3行のプログラムとして送信でき、もう1つはできません。次の投稿では、まさにそのギャップを追跡します。シャノンエントロピーをゼロから構築し(ここで使用したのと同じ量)、πの構造に気づかないのを見て、コルモゴロフ複雑性――オブジェクトを再現する最短プログラムの長さ――そして、この最も真実な圧縮の尺度が証明可能に計算不可能であることが判明するという奇妙で美しい事実に至ります。統計的冗長性は、私たちが決して完全にピン留めできない、より深い構造の計算可能な影にすぎないことが判明するでしょう。