機械学習の13、SVD特異値分解

はじめに

本文には、大文字表現=行列/マトリクス、\(\boldsymbol{bold}\)小文字表現=ベクトル\(R^d\)、普通小文字表現=スカラー\(R\) と記す。

SVD(Singular Value Decomposition)は機械学習の分野で広く使用されているアルゴリズムで、次元削減アルゴリズムの特徴分解だけでなく、推薦システム(Recommender System)や自然言語処理(Nature Language Process)にも使用される。

原理

SVDは前述した特徴分解同じく行列を分解するが、SVDは分解する行列が正方行列にする必要ない。行列Aの形状が\(m×n\)であると仮定すると、行列AのSVDを次のように定義する。
$$ A = UΣV^T $$
ただし、\(U\)は\(m×m\)の行列\((u_1, u_2,…, u_m)\)、\(Σ\)は\(m×n\)の行列、主対角線上の要素を除く全ての要素が実数ゼロ\(0\)であり、主対角線上の各要素は特異値(Singular Value)という、\(V\)は\(n×n\)行列\((v_1, v_2,…, v_n)\)。

\(A\)の転置\(A^T\)と\(A\)を行列で乗算すると、\(n×n\)の正方行列\(A^T A\)が得られる。\(A^T A\)は正方行列であるため、特徴の分解を実行でき、得られた固有値と固有ベクトルは次の式を満たす。
$$ (A^T A)\boldsymbol{v_i}=λ_i\boldsymbol{v_i} $$
これで行列\(A^T A\)の\(n\)個の固有値と対応する\(n\)個の固有ベクトル\(v_i\)を取得できる。

\(A\)と\(A\)の転置\(A^T\)を行列で乗算すると、\(m×m\)の正方行列\(AA^T\)が得られる。\(AA^T\)は正方行列であるため、特徴の分解を実行でき、得られた固有値と固有ベクトルは次の式を満たす。
$$ (AA^T) \boldsymbol{u_i}=λ_i\boldsymbol{u_i} $$
これで行列\(AA^T\)の\(m\)個の固有値と対応する\(m\)個の固有ベクトル\(u_i\)を取得できる。

\(Σ\)は対角線上の特異値を除いて全て\(0\)で、各特異値\(σ_i\)を見つけるだけで\(Σ\)が求められる。
$$ \sigma_i = \sqrt{λ_i} $$

各特異値\(σ_i\)のうち、比較的大きいほう(主成分)とそれに対応する特異ベクトル\(u_i, v_i\)を\(k\)個\((k << n)\)残すとAの次元を削減する。
$$ A_{m×n}=U_{m×m}Σ_{m×n}V^T_{n×n} ≈ U_{m×k}Σ_{k×k}V^T_{k×n} $$

実装

以下行列dataSetに対して、SVDアルゴリズムで\((U, \Sigma, V^T)\)を求めて、5次元→3次元つまり2次元を削減してが新しい\(\Sigma\)で\((U* \Sigma*V^T)\)が元の行列dataSetに戻せるかを確かめる。

from numpy import *
def loadExData():
    return[[0, 0, 0, 2, 2],
           [0, 0, 0, 3, 3],
           [0, 0, 0, 1, 1],
           [1, 1, 1, 0, 0],
           [2, 2, 2, 0, 0],
           [5, 5, 5, 0, 0],
           [1, 1, 1, 0, 0]]
dataSet = loadExData()
U, Sigma, VT = linalg.svd(dataSet)
print(f'dataSet:\n{dataSet}')
print(f'U:\n{U}\nSigma:\n{Sigma}\nVT:\n{VT}')
// 小さいSigmaを0にする(削除)
Sig3 = mat([[Sigma[0], 0, 0], [0, Sigma[1], 0], [0, 0, Sigma[2]]])
print(f'U[:,:3] * Sig3 * VT[:3,:]:\n{U[:,:3] * Sig3 * VT[:3,:]}')

ソースコード
https://github.com/soarbear/Machine_Learning/tree/master/svd

結果

\((U* \Sigma*V^T)\)は元のdataSetとほぼ同じ行列だと分かる。

dataSet:
[[0, 0, 0, 2, 2], [0, 0, 0, 3, 3], [0, 0, 0, 1, 1], [1, 1, 1, 0, 0], [2, 2, 2, 0, 0], [5, 5, 5, 0, 0], [1, 1, 1, 0, 0]]
U:
[[-2.22044605e-16  5.34522484e-01  8.41641151e-01 -1.37443101e-02
  -7.57428665e-02 -1.11022302e-16  1.38777878e-17]
 [ 0.00000000e+00  8.01783726e-01 -4.92426901e-01 -2.47257115e-01
   2.31349353e-01  3.15719673e-16 -2.77555756e-17]
 [ 0.00000000e+00  2.67261242e-01 -2.06001597e-01  7.69259966e-01
  -5.42562325e-01 -7.55450741e-16  1.09551769e-16]
 [-1.79605302e-01  2.77555756e-17 -3.00520660e-02 -2.15935735e-01
  -2.94749442e-01  9.05439185e-01 -1.16246358e-01]
 [-3.59210604e-01  5.55111512e-17 -6.01041319e-02 -4.31871470e-01
  -5.89498885e-01 -4.19124526e-01 -3.97074256e-01]
 [-8.98026510e-01  0.00000000e+00  3.60624791e-02  2.59122882e-01
   3.53699331e-01  5.40010673e-16 -6.71525577e-17]
 [-1.79605302e-01  2.77555756e-17 -3.00520660e-02 -2.15935735e-01
  -2.94749442e-01 -6.71901321e-02  9.10394870e-01]]
Sigma:
[9.64365076e+00 5.29150262e+00 8.36478329e-16 6.91811207e-17
 1.11917251e-33]
VT:
[[-5.77350269e-01 -5.77350269e-01 -5.77350269e-01  0.00000000e+00
   0.00000000e+00]
 [-2.46566547e-16  1.23283273e-16  1.23283273e-16  7.07106781e-01
   7.07106781e-01]
 [-7.01908483e-01 -1.02844064e-02  7.12192890e-01 -2.22044605e-16
  -1.66533454e-16]
 [-4.17122461e-01  8.16431808e-01 -3.99309347e-01  0.00000000e+00
  -1.11022302e-16]
 [-0.00000000e+00 -1.96261557e-16  1.96261557e-16  7.07106781e-01
  -7.07106781e-01]]
U[:,:3] * Sig3 * VT[:3,:]:
[[ 4.47427211e-17  1.57774942e-15  2.08638397e-15  2.00000000e+00
   2.00000000e+00]
 [-7.56974048e-16  5.27282824e-16  2.29691224e-16  3.00000000e+00
   3.00000000e+00]
 [-2.27747782e-16  1.76121044e-16  5.16267387e-17  1.00000000e+00
   1.00000000e+00]
 [ 1.00000000e+00  1.00000000e+00  1.00000000e+00  1.03851855e-16
   1.03851855e-16]
 [ 2.00000000e+00  2.00000000e+00  2.00000000e+00  2.07703709e-16
   2.07703709e-16]
 [ 5.00000000e+00  5.00000000e+00  5.00000000e+00 -6.69808260e-33
  -5.02356195e-33]
 [ 1.00000000e+00  1.00000000e+00  1.00000000e+00  1.03851855e-16
   1.03851855e-16]]

参考文献

[1] PeterHarrington. Machine Learning in Action.

ロボット・ドローン部品お探しなら
ROBOT翔・電子部品ストア