大学でReduced Rank Regressionを用いて研究を行っていたのですが、他の解説記事では途中の式変形が詳しく書かれていなかったので、もうちょい詳しく解説していこうと思います。勉強や研究の足がかりにしていただけたら光栄です(^_^)
Eckart-Youngの定理
いきなり定理が出てきて身構えるかもしれませんが、この定理があると便利なので理解しておきましょう。またこの記事では詳しい証明などは省くので、知りたい方は他の記事を参考にしてくださいね。ではまずEckart-Youngの定理の概要は以下になります。
階数がr以下の行列$M^{n\times m}$の行列が与えられた時,$||M-Z||_F$を最小にする$Z$は$M=UDV^{T}$と特異値分解した時の$Z=U_rD_rV^{T}_r$で与えられる。ただし$U\in\mathbb{R}^{n\times m}$,$D\in\mathbb{R}^{m\times m}$,$V^{T}\in\mathbb{R}^{m\times m}$$U_r\in\mathbb{R}^{n\times r}$,$D_r\in\mathbb{R}^{r\times r},V^{T}\in\mathbb{r\times m}$である。
これを読んでも「ナンノコッチャ」と思うかもしれませんが、ちゃんと紐解くとそんなに難しいことは言っていません。この定理は簡単に言うと「ある行列$M$があって、その行列よりもランクの低くて似ている行列$Z$は$M$を特異値分解すると作れますよ」ということです。特異値分解についてはこの記事で詳しく解説されているのでわからない方はチェックしてみてください。では一つづつ紐解いてみましょう。まず行列$M$を
M=
\begin{pmatrix}
u_1 & u_2 & \dots & u_m
\end{pmatrix}
\begin{pmatrix}
d_1 & 0 & \dots & 0\\
0 & d_2 & \dots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \dots & d_m
\end{pmatrix}
\begin{pmatrix}
v_1\\
v_2\\
\vdots\\
v_m
\end{pmatrix}
となるよう特異値分解します。このとき$D$は特異値を要素とする単位行列です。特異値は大きい順に上から並んでいるのですが、ここで小さい値は無視しても元の行列とさほど変わらないんじゃないかというのがこの定理です。では特異値を大きい方から$r$個選んでそれ以外を0にすると
\begin{pmatrix}
u_1 & u_2 & \dots & u_m
\end{pmatrix}
\begin{pmatrix}
d_1 & 0 & \dots & 0 & 0 & \dots & 0\\
0 & d_2 & \dots & 0 & 0 & \dots & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \dots & \vdots \\
0 & 0 & \dots & d_r & 0 & \dots & 0\\
0 & 0 & \dots & 0 & 0 & \dots & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots\\
0 & 0& \dots & 0 & 0 & \dots & 0
\end{pmatrix}
\begin{pmatrix}
v_1\\
v_2\\
\vdots\\
v_m
\end{pmatrix}
となります。こうすると,左特異ベクトルの列が1~$r$番目はそのまま、$r+1$~$m$番目までが0になりますね。同様に右特異ベクトルの行も1~$r$番目まではそのまま、$r+1$~$m$番目までが0になります。つまり
Z=
\begin{pmatrix}
u_1 & u_2 & \dots & u_r
\end{pmatrix}
\begin{pmatrix}
d_1 & 0 & \dots & 0\\
0 & d_2 & \dots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \dots & d_r
\end{pmatrix}
\begin{pmatrix}
v_1\\
v_2\\
\vdots\\
v_r
\end{pmatrix}
として求まった$Z$がランクを$r$に制限した行列となります。実際に書いてみるとすんなり理解できると思うのでぜひやってみてくださいね。Reduced Rank Regressionでは名前の通りランクを削減した回帰モデルを推定するのでこの定理を用います。
Reduced Rank Regressionの解の推定
Reduced Rank Regressionの損失関数は$Y\in\mathbb{R}^{n\times q},X\in\mathbb{R}^{n\times p},\beta\in\mathbb{R}^{p\times q}$とした時以下のように書かれます。
||Y - X\beta||^{2}_{2} \;\;s.t.\;\; rank(\beta)\leq r
ここで$||・||^{2}_2$はフロベニウスノルムを表します。また$r\leq min(p,q)$とします。この関数を最小化する$\beta$がReduced Rank Regressionの解となります。通常の最小二乗法であったら正規方程式$\hat{\beta}=(X^{T}X)^{-1}X^TY$を用いて簡単に求めることができるのですが、今回はランクが$r$以下の$\beta$を求めろということなので解けませんね。ただランクを制限するので、Eckart-Youngの定理を適用できるような形にできれば求めることができそうです。そこで適用できるよう式変形をしていきます。まず通常の最小二乗法で求めた解を$\hat{\beta}$として以下のように書きかえます。
||Y-X\beta||^{2}_2 = ||Y-X\hat{\beta} + X\hat{\beta}-X\beta||^2_2
この式を変形していきましょう。ノルムの性質を用いて展開すると
||Y-X\hat{\beta} + X\hat{\beta}-X\beta||^2_2=||Y-X\hat{\beta}||^2_2+||X\hat{\beta}-X\beta||^2_2-2tr(Y-X\hat{\beta})(X\hat{\beta}-X\beta)
となります。ここでトレースの項に注目します。まず$Y-X\hat{\beta}$の式を見ると、$X\hat{\beta}$は$span(X)$に対する$Y$の正射影であることから、$Y-X\hat{\beta}$は$span(X)$に垂直なベクトルであることがわかります。次に$X\hat{\beta}-X\beta$をみると、このベクトルは$span(X)$に存在するベクトルであることがわかります。この２つから$Y-X\hat{\beta}$と$X\hat{\beta}-X\beta$は垂直であることがわかります。つまりこの２つのベクトルの内積はゼロになるので、トレースの項は０になります。これを先程の式に代入すると
||Y-X\hat{\beta}||^2_2+||X\hat{\beta}-X\beta||^2_2
となります。また$Y-X\hat{\beta}$は既知の行列で書かれているので、これを定数としてみると
||X\hat{\beta}-X\beta||^2_2+const
となります。この式を最小にする$\beta$を求めれば良いということになりますね。この形であれば$X\hat{\beta}$を低ランクで近似した行列$X\beta$をEckart-Youngの定理で求める事ができそうです。では適用していきましょう。Eckart-Youngの定理より$X\hat{\beta}$を$UDV^T$と特異値分解したとき、ランクを$r$に指定した行列$X\beta$は以下のように書くことができます。
X\beta=U_rD_rV^T_r
ただ今回求めたいのは$\beta$のみで上記の結果では$X$が邪魔です。なのでうまいこと行列をかけて$X$を消します。$V_r$は右特異ベクトルで直交行列なので$V_rV_r^T=I_r$です。これを$X\hat{\beta}$に右からかけてみましょう。
X\hat{\beta}V_rV_r^{T}=UDV^TV_rV_r^T
ここで$V^{T}V_r$について注目します。$V_r$は$V$の$r$番目までの行列なので行数と列数が合わず積を取ることができません。なので$V_r$の$r$番目以降を0として$V$と同じサイズの行列として見ます。すると$V^TV_r$は以下のようになります。
V^TV_r=\begin{pmatrix}
v_1\\
v_2\\
\vdots\\
v_m
\end{pmatrix}\begin{pmatrix}
v_1 & v_2 & \dots & v_r & 0 & \dots & 0
\end{pmatrix}\\
=I_r
$r$番目以降が0なので積をとると$r$個の1が並び、それ以降は0となる単位行列$I_r$となります。なので$I_r$の左にある$D$も$r$番目以降は0になり、そのとなりにある$D$も同様に$r$番目以降は0になります。なので
X\hat{\beta}V_rV_r^T=UDI_rV_r^T=U_rD_rV_r^T=X\beta
となることがわかります。両辺に$X$があるのでこれで$X$を消すことができますね。よってもとめたい$\beta$は
\beta=\hat{\beta}V_rV_r^T
と導けました。