HELLO CYBERNETICS

深層学習、機械学習、強化学習、信号処理、制御工学、量子計算などをテーマに扱っていきます

E資格で必須の特異値分解解説

 

 

follow us in feedly

はじめに

予め断っておきます。私はE資格を持っていませんし受けたこともありません。 なんか特異値分解は知識として必須らしいという話だけ聞きました。なのでタイトルに入れました(完全に検索対策である)。

タイトルは動機不純として…、特異値分解はデータ分析にしても信号解析にしても、線形代数での必須知識だと思われるのでここで解説しておきます。

特異値分解

定義

特異値分解は定義だけ述べれば、行列 $\mathbf X \in \mathbb C ^ {m \times n}$ に対する下記で表される分解手法です。

$$ \bf X = U \Sigma V ^ * $$

ここで $\mathbf U \in \mathbb C ^ {m \times m}$ で、$\mathbf V \in \mathbb C ^ {n \times n}$ の正方行列となっており、もともと $X$ が $m$ 行 $n$ 列であったのだから、計算結果の帳尻を合わすサイズの行列が間に必要で $\mathbf \Sigma \in \mathbb C ^ {m \times n} $ という行列が真ん中にいる形になっています。

ちなみに $\mathbf A ^ *$ は $\bf A$ の成分について共役を取り、転置した行列です。$\mathbb C ^ {m \times n}$ というのは複素数を成分に持つ $m$ 行 $n$ 列の行列ですが、一般的な状況を表現するためにそうしています。データ分析では大抵の場合実数を扱うので、共役を取るという操作は意味がなく、単に $\mathbf A ^ *$ は転置行列だと思って構いません。

兎にも角にも、正方行列でない $\bf X$ を2つの正方行列 $\bf U, V$ と正方行列でない $\bf \Sigma$ の積に分解することができます。これにはどんな意味があるのでしょうか。結局、正方行列でない $\bf \Sigma$ が残ってしまうなら、形もあまりキレイじゃないように見えます。

しかし、そうではありません。特異値分解では、

$$ \bf X = U \Sigma V ^ * $$

とした際に、$\bf \Sigma$ だけが正方行列ではありませんが、代わりに下記のようなキレイな形になります。

$$ \begin{pmatrix} \sigma _ 1 & 0 & 0 \\ 0 & \sigma _ 2 & 0 \\ 0 & 0 & \sigma _ 3 \\ 0 & 0 & 0 \end{pmatrix} $$

これは、 $m = 4$ で $n = 3$ の例ですが、$\bf \Sigma$ は $i, j$ 成分に関して $i=j$ の対角成分にしか値を持ちません。ここで出てきた $\sigma _ k$ を特異値と呼びます。

特異値分解の嬉しさ

上記のように分解できると一体何が嬉しいのでしょうか。それは 特異値 $\sigma _ k$ が行列 $\bf X$ を構成する要素となっていることに着目すると見てくるものがあります。仮に

$$ \mathbf X = \mathbf U \begin{pmatrix} \sigma _ 1 & 0 & 0 \\ 0 & \sigma _ 2 & 0 \\ 0 & 0 & \sigma _ 3 \\ 0 & 0 & 0 \end{pmatrix} \mathbf V ^ * $$

と分解できたとしましょう。ここで、もしも $\sigma _ 3$ という値が非常に小さい値だったらどうでしょうか。実際に $\bf U \Sigma V ^ *$ を計算した結果、 $\sigma _ 3$ が絡んでくる計算は、実はさほど影響力は無いと言えるかもしれません。そのことを実際に見るために、下記の簡単な例で計算をしてみましょう。

一旦 $\mathbf U = ({\bf u _ 1, u _ 2, u _ 3, u _ 4})$ と $\mathbf V = ({\bf v _ 1, v _ 2, v _ 3})$ と行列を、ベクトルを並べたものだと思って計算してみましょう。これらを、特異値分解の右辺に入れてみます。

$$ \mathbf X = \begin{pmatrix} {\bf u _ 1, u _ 2, u _ 3, u _ 4} \end{pmatrix} \begin{pmatrix} \sigma _ 1 & 0 & 0 \\ 0 & \sigma _ 2 & 0 \\ 0 & 0 & \sigma _ 3 \\ 0 & 0& 0 \end{pmatrix} \begin{pmatrix} {\bf v _ 1 ^ *\\ v _ 2 ^ * \\ v _ 3 ^ * } \end{pmatrix} $$

これを丁寧に右側から計算してみます。

$$ ... = \begin{pmatrix} {\bf u _ 1, u _ 2, u _ 3, u _ 4} \end{pmatrix} \begin{pmatrix} { \sigma _ 1 \mathbf v _ 1 ^ *\\ \sigma _ 2 \mathbf v _ 2 ^ * \\ \sigma_3 \mathbf v _ 3 ^ * \\ 0} \end{pmatrix} = \sum _ k ^ 3 \sigma _ k {\bf u _ k v _ k ^ *} $$

となります。ここで左側が縦ベクトル $\bf u _ k$ で右側が横ベクトル $\bf v _ k ^ *$ の場合の積は行列になることに注意してください(テンソル積と言ったり外積と言ったりもするようである。外積はクロス積という意味あるのでややこしい…。)。

つまり特異値分解とは、 $\bf u _ k v _ k ^ *$ という行列を $\sigma _ k$ で重み付けして足し算した行列を計算していることになります。

特異値分解について、最初は「2つの正方行列と(正方ではないが)1つの対角行列の積に分解する」と述べましたが、このような視点で見てみると、「適当なベクトル $\bf u$ と $\bf v$ で作られる行列 $\bf u _ k v _ k ^ *$ を考え、それらの重み付け足し算(線形結合)によって行列を表現する手法」だと捉えることもできるのです。

そしてこの視点に立つと、この計算をする前に述べた「$\sigma _ 3$ が絡んでくる計算は、実はさほど影響力は無いと言えるかもしれません。」というのは真実を帯びてきます。要するに、 $\sigma _ 3 \simeq 0$ のような状況だと、単に行列 $\bf u _ 3 v _ 3 ^ * $ の足し算を無視するだけの話になり、たしかにこの項は分解前の行列の構成要員としてそれほど必要なさそうだと言えるわけです。

行列の低ランク近似

特異値分解の応用を調べると真っ先に出てくるようなものが、この低ランク近似です。

特異値分解の式を見てみましょう。これも、そんなことをして良い妥当性は、和の分解の方を見るとわかりやすいです。一般的に行列 $\mathbf X \in \mathbb R ^ {m \times n}$ に関して $K = \min (m, n)$ として

$$ \mathbf X = \sum _ {k=1} ^ K \sigma _ k {\bf u _ k v _ k ^ *} $$

と分解できるのが特異値分解でした。ここで仮に $\sigma _ 1,\sigma _ 2$ はそれなりに大きな値だけど、それ以降の特異値は小さな値でした、とすれば上記の和の式を見てわかる通り、行列 $X$ の構成に $u _ k v _ k ^ *$ の $k = 3, 4, ..., K$ はあまり寄与していないと言えます。

そうであるならば、$\bf u _ k, v _ k$ をそもそも $k=1, 2$ だけ保持して他を捨ててしまっちゃおうというのが低ランク近似です。

あれ、それは $\sigma _ k$ に関して小さな値を $0$ として扱うのと同じじゃないと?と思うかもしれません。もちろん式としては同じですが、計算機としては同じではありません。ここで積の方の式を見てみましょう。

$$ \mathbf X = \begin{pmatrix} {\bf u _ 1, u _ 2, u _ 3, u _ 4} \end{pmatrix} \begin{pmatrix} \sigma _ 1 & 0 & 0 \\ 0 & \sigma _ 2 & 0 \\ 0 & 0 & \sigma _ 3 \\ 0 & 0& 0 \end{pmatrix} \begin{pmatrix} {\bf v _ 1 ^ *\\ v _ 2 ^ * \\ v _ 3 ^ * } \end{pmatrix} $$

という具合だったのでした。ここで $k = 2$ までしか考慮しないとして、 $\sigma _ 3 = 0$ と代入した場合には

$$ \mathbf X = \begin{pmatrix} {\bf u _ 1, u _ 2, u _ 3, u _ 4} \end{pmatrix} \begin{pmatrix} \sigma _ 1 & 0 & 0 \\ 0 & \sigma _ 2 & 0 \\ 0 & 0 & 0 \\ 0 & 0& 0 \end{pmatrix} \begin{pmatrix} {\bf v _ 1 ^ *\\ v _ 2 ^ * \\ v _ 3 ^ * } \end{pmatrix} $$

という計算を、計算機に行わせることになります。これは $4 \times 3$ の行列と $3 \times 3 $ の行列と $3 \times 3$ の行列の積を実行することになるわけです。一方で、関係ないと思われる $\bf u _ k v _ k $ ごと消し去ってしまうことにすれば

$$ \mathbf X = \begin{pmatrix} {\bf u _ 1, u _ 2} \end{pmatrix} \begin{pmatrix} \sigma _ 1 & 0 \\ 0 & \sigma _ 2 \end{pmatrix} \begin{pmatrix} {\bf v _ 1 ^ *\\ v _ 2 ^ * } \end{pmatrix} $$

の計算だけを実行すればよく、これは $4 \times 2$ の行列と $2 \times 2$ の行列と $2 \times 3$ の行列の積で済むのです。ああ、単に結果が同じなら計算が軽いほうが良いだけなんだね…、ということですが、これが「1280×780」の画像 $\bf X$ を低ランク近似できますという話ならかなり効いてくるのです(これであなたも圧縮アルゴリズムを開発できたことになる!)。

主成分分析の解法

これは、知らぬ間にライブラリの中で実現されていたりいなかったり…、の話でありますが主成分分析はデータを並べた行列に対する特異値分解に相当します。さて、データ行列

$$ \mathbf X \in \mathbb R ^ {N \times D} $$

の共分散行列に対する。

$$ \frac{1}{N}{\bf X ^ T X} \in \mathbf R ^ {D \times D} $$

に対する固有値分解が主成分分析の解法ですが、それは正方でないデータ行列に特異値分解を行うのと同じなのです。ちなみに行列$\bf A ^ T A$ の 固有値 $\lambda _ i ({\bf A ^ T A})$ と $\bf A$ の特異値 $\sigma _ i(\mathbf A)$ との関係は

$$ \sigma _ i(\mathbf A) = \sqrt {\lambda _ i ({\bf A ^ T A})} $$

となっています(いや、実を言うとこれが定義と言っても良い。固有値分解は正方行列にしか適用できない。だから、正方行列出ないものに対しても固有値分解っぽいものを作りたかったのである。そうしてできたのが特異値分解である)。

さて、やっていることが同じなら、なぜに主成分分析を特異値分解で実施することがあるのでしょうか。 それは、ライブラリの構成次第であると思われますが、一般に共分散行列を計算してから固有値分解を実施するのと、データ行列を直接特異値分解するのとでは、「やることが定まっているという点で」特異値分解の方が速いことがあるためです。

一体何を言っているのかというと、特異値分解は非正方行列 $\bf A$があったときに一旦 $\bf A A ^ *$ という計算を必要とします。そしてこの計算結果はエルミート行列(実数行列なら対称行列)になることが確定します。このような値に対しては逆行列計算を地道に計算する必要はなく、コレスキー分解などの効率的手法を利用できるのです。一般の固有値分解では、正方行列がエルミート行列である保証が無いので、実装上、遅いがより一般的な行列を扱える解法が実装されているケースが多いのです(まあ、オプションとして選べることも多々ある)。

つまり、手作業で分散共分散行列を計算して、固有値分解を実施したときには、せっかく対称行列と分かっているのに、非効率的な固有値分解のアルゴリズムを使ってしまうことになりかねないということです(sklearnは特異値分解を使う。もちろん低ランク近似する前提で、近似アルゴリズムを使ったりもできる。)。

行列による増幅率を定義

更に地味なところですが、非正方行列による変換を受けたベクトルがどのように「増幅」されるのかを定めることもできます。

$$ \bf A = U \Sigma V ^ * \in \mathbb R ^ {m \times n} $$

とすると $\bf y = Ax $ なる変換を実施できます。この変換は $n$ 次元から $m$ 次元へベクトルを変換することになります。さて、このとき $\bf x$ というベクトルはどのような変換を受けたことになるのでしょうか。これが正方行列であったとすれば、方向と大きさが変わるという言葉で表現できます。それに相当する概念がほしいのです。

そこで $\bf A ^ * A \in \mathbb R ^ {n \times n}$ という行列を考えます。ここに下記の関係式が成り立つようなベクトル $\bf v$ と スカラー $\sigma$ を考えることにします。

$$ {\bf A ^ * A}\mathbf v = \sigma ^ 2 \bf v $$

このとき $\sigma $ を特異値、 $\bf v$ を特異ベクトルといいます。が…ひとまず $A ^ * A$ を1つの正方行列で、 $\sigma ^ 2$ を固有値と思ってしまえば、単に $\bf v$ は $A ^ * A$ の固有ベクトルという話になります。そうすれば $\bf v$ の方向には $\sigma ^ 2$ だけ(2ノルムの意味で)ノルムを増大させるということが言えるようになります(固有値が定数倍相当の処理をすることがわからない場合は下記の記事を参考にしてください)。

www.hellocybernetics.tech

また、形式的に

$$ || {\bf A v} || ^ 2 = \sigma ^ 2 ||\bf v ||^ 2 $$

だから、$A$ のノルムは $\sigma$ であると言ってもいいでしょう(飛躍しているフロベニウスノルムを調べてほしい。そしてこのノルムを加味した上で低ランク近似を見ると、それは行列に対する最小二乗法となる)。

特異値と特異ベクトルの実態

ここまで、特異値と特異ベクトルがそもそもどういうものであるかをごまかして来ました(少しずつ実態に近づくような事例の順番にしたつもりだ)。

結局のところ線形代数で強力な行列分解の手法である固有値分解を、正方行列以外にも使えるようにしたいというのが特異値分解のモチベーションであるというのは薄々気づいていたかもしれません。ここに下記の関係式が成り立つようなベクトル $\bf u, v$ と スカラー $\sigma$ を考えることにします。

$$ \begin {align} {\bf A v} &= \sigma \bf u \\ {\bf A ^ * u} &= \sigma \bf v \end{align} $$

ここで、上の式に $\bf A ^ *$ を左から掛けてやりましょう。

$$ {\bf A ^ *A v} = \sigma {(\bf A ^ * u)} = \sigma (\sigma {\bf v}) = \sigma ^ 2 {\bf v} \\ $$

となり、ノルムがどうのこうの言っていたところでの式が出てきました。一方で下の式 $\bf A$ を掛ければ同じ手順で

$$ {\bf A A ^ * u = } \sigma ^ 2 {\bf u} $$

が出てきます。このように $\mathbf A \in \mathbb C ^ {m \times n}$ という非正方行列あったときに、${\bf A ^ * A}$ と ${\bf A A ^ *}$ という二種類の正方行列を作って、それぞれに固有値分解をしたものを上手に使えば良いのではないか…?と編み出されたのが特異値分解というわけです。

最後に

途中で、方向性を見失った(具体例を出したかったのか計算例を出したかったのか一般的な話がしたかったのか忘れた)結果、だだっぴろい記事になってしまいました。ということで、知識の補足に下記の記事を見ると良いと思います(丸投げ)。

ronri-rukeichi.hatenablog.com

www.haya-programming.com

qiita.com