Truncated SVD (2023)

PCA 主成分分析（PCA）は、以前の私の投稿で取り上げたテーマなので、ここでは要約のみとします。PCAによるデータ削減は、データを新しい座標系に線形変換することで達成されます。この新しい座標系では、データの変動の（ほとんど）が、元のデータよりも少ない次元で説明できます。詳細には触れませんが、これには共分散行列の固有値分解が含まれます。 SVD 特異値分解（SVD）は、実数行列 M を3つの行列 U、Σ、V に分解する行列分解技術であり、M=U*Σ*V^T となります。M が mxn の場合、U は mxm、Σ は mxn、V は nxn となります。U と V はどちらも正規直交行列であり、Σ は非負の係数を持つ長方形対角行列です。これはPCAと非常に似ていますが、SVDの分解はデータ行列に対して行われるのに対し、PCAでは共分散行列に対して分解が行われる点が異なります。 Σの対角係数はMの特異値として知られており、特異値が減少順に並べられるようにSVDを並べ替えるのが一般的です。ゼロでない特異値の数は、Mのランクに等しくなります。 SVDはPCAと密接に関連しています。Vの列は主成分方向/軸（固有ベクトル）です。U*Σの列は主成分（スコア）です。特異値は共分散行列の固有値に関連しています。 Wikipediaより: Truncated SVD 月面の1024x1024グレースケール画像で試してみましょう。このような画像は、それぞれ1024個の成分を持つ1024個のベクトルとして解釈できます。つまり、1024次元空間内の1024個のベクトルの集合です。この集合に対してPCA/SVDを実行すると、3つの行列U、Σ、Vは1024x1024になります。特に、Σは正方対角行列になります。つまり、対角上の係数のみがゼロでない可能性があります。3つの行列を、Σの対角インデックスがより大きいもの（左上）からより小さいもの（右下）へとソートされるように並べ替えるのが一般的です。 Truncated SVDは、Σのすべての係数を、左上のn個の係数以外はゼロにするという行為にすぎません。係数の切り捨ては、UとVの1024-n列も破棄することを意味します（それらはすでに0と掛け合わされるため）。切り捨てられた行列を使用して元の行列M'=U'*Σ'*V'^Tを再構築すると、M'が得られ、これはMに似たものになります。ドロップする係数が少ないほど、M'はMをより正確に近似します。しかし、PCA/SVDの情報保持特性により、上位の係数をいくつか保持するだけで、元の情報のすべて（またはほぼすべて）を復元するのに十分な場合があります。 月の画像の再構築 上記すべてを月の画像に適用してみましょう。nを単一の値で切り捨てるのはあまり示唆的ではないため、代わりにnをその全範囲にわたってスイープし、近似がどのように振る舞うかを見ていきます。以下の画像とビデオはすべて同じレイアウトを共有しています。左半分は再構築された行列M'です。右半分は再構築誤差abs(M-M')です。減少する黄色いグラフは、特異値がゼロアウトされるにつれてMSEが減少していく様子を示しています。このスクリーンショットは、わずか32個（1024個中）のコンポーネントで再構築されたM'です。1:1の品質で表示するには、右クリックして新しいタブで開いてください。 その32個のコンポーネントが実際に何をもたらしたのかを一時停止して考える価値があります。切り捨てられた因子は、U'（1024x32）、生き残った32個の特異値、およびV'（1024x32）です。これは65568個の数値であり、Mの1048576個の数値と比較すると、16倍の削減になります。それにもかかわらず、画像はまだ月として認識できます。 以下は、再構築に使用されるコンポーネントが増えるにつれて、同じ画像ペアを示したビデオです。ほとんどのアクションは最初の数フレームで発生します。 ここで注目すべきは（PCA/SVDの魔法）、誤差グラフがどれほど速く減少するかということです。これは、最初のコンポーネントがMに含まれる情報の大部分を捉えているのに対し、後続のコンポーネントは高周波/低振幅の細かい詳細のみを運んでいることを証明しています。これは、フーリエ変換、コサイン/サイン変換などと同様の現象です。これらの変換は空間と周波数の二重性を扱いますが、PCA/SVDは純粋に分散駆動の基底変換です。しかし、同様の方法で、これらのすべての方法は情報を二重形式に変換し、そこで「情報の量」が構造化され、管理しやすい方法で現れます。 FT/CT/などは、人間の知覚システムが輝度（色度に対して）と低周波数（高周波数に対して）に敏感であることを利用する.jpeg、.mp3などの圧縮システムの基盤となっています。SVD/PCAの場合、Σの上位係数は下位係数よりも多くのデータ分散を捉えます。これらは、2、4、8、16、32、64、128個の係数で再構築されたシーケンスです。 簡単なケースと難しいケース 前述のように、行列分解は、データが行列の行が互いに線形従属である特別な空間への基底変換として解釈できます。この場合、より低いランクのU/V行列で元の行列を正確に再構築するだけで十分です。実際、Σは、データ損失を引き起こすことなく破棄できる行/列の数と同じ数のゼロ値の係数を対角線上に持つようになります。 極端なケースを以下に示します（中心化された正方形のボックス形状）。この場合、係数は1つ/行/列で十分です。形状の内側と外側の両方で、すべての行/列は同一です。ちなみに、ボックスは分離可能な畳み込みフィルターです（低ランク畳み込みに関する将来の投稿を期待しています）。 PCA/SVDはそのような基底変換を「自動検出」する能力がありますが、形状を回転させると悲惨な結果になります。しかし、ここでは離散数学を扱っているため、回転した形状は「ピクセル化」され、分解が数値的に不純になります。ビデオの最初のフレームで、再構築がどうにかして回転していない正方形であろうと「主張」しているのを見るのは面白いです。 以下は五角形の形状です。 実用的な用途 データ分析における次元削減以外のSVD切り捨ての興味深い実用的な用途があります。 データ圧縮 Bart Wronskiは、この技術を使用したPBRテクスチャセットの圧縮に関する非常に興味深い記事を書いています。BCnテクスチャ圧縮も同様に次元削減に基づいています。Nathan Reedによるこのトピックに関する良い記事。 低ランク近似 低ランク近似。Bart Wronskiによるもう一つの興味深い読み物。私もいつか低ランク畳み込みに関する記事を書きたいと思っています。 実装の詳細 MaverickのAPIに古いPCA/SVD C++コードがあり、この投稿の画像/ビデオに使用しました。しかし、Atrix256によるこの投稿を読んだ後、古いxsvd_cクラスの実装部分をEigenに置き換える決断をするかもしれません。