cha_kabuのNotebooks

個人的な機械学習関連勉強のアウトプット置き場です。素人の勉強録なので、こちらに辿り着いた稀有な方、情報はあまり信じない方が身のためです。

特異値分解について勉強する（ざっくり理解する編）

はじめに

Probspaceのスパムメール判別コンペで初の自然言語処理にチャレンジ中で、これを機に「ゼロから作るDeep Learning②自然言語処理編」（以降、ゼロ作）も読み進めているのですが、2章の特異値分解のところで早速躓いたのでまとめることにしました。ただ、まとめたのが「だいたいどういうものか」までですので、分解に至る数式などは別途まとめたいと思います。

他の記事もそうですが素人が調べながら書いており、誤った情報が含まれる可能性があるので情報の信じすぎにはご注意ください。

概要

特異値分解とは次元削減手法のひとつで、任意の行列を3つの行列の積に分解し、重要度の低い余分な列ベクトルを削ることで元の行列に近似した低次元の行列を作成します。

自然言語処理では文章を単語に分割しベクトル化した上で様々な処理を行いますが、そのまま扱おうとすると語彙数に応じてベクトルの次元数が増えてしまい、計算が大変になってしまいます。

また、複数の文書をベクトル化した行列は「（様々な文書で共通に含まれる単語というのは多く無いので）多くの要素が0＝ベクトルのほとんどの要素が重要ではない」状態になりやすく、そのようなベクトルはノイズに弱く頑健性に乏しいという欠点もあるため、次元削減が重要になってきます。

前提知識

特異値分解に入る前に、「固有値と固有ベクトル」「固有値分解」について把握していると理解しやすいです。

これらについては以下二つのYouTube動画が分かりやすかったです。

特異値分解PART1：固有値分解 by 某处生活_LiveSomewhere

【大学数学】線形代数入門⑫(固有値・固有ベクトル)【線形代数】 by 予備校のノリで学ぶ「大学の数学・物理」

詳しい説明はこれらの動画を見て頂ければと思いますが、ポイントとして押さえておきたいのは以下です。

  1. 行列 Aに対して、 A\vec{v}=λ\vec{v}を満たす \vec{v}を Aの固有ベクトル、 λを Aの固有値という。
  2. 固有ベクトル \vec{v}と固有値 λの組み合わせは複数存在し、行列でまとめて表すことができる。
    • A\vec{v}=λ\vec{v} → AV=VΛ
      • 計算を考えてみたら当たり前ですが、 Λの中身である (λ_{1}, λ_{2}, \cdots, λ_{n})は、 Λの対角成分になります。

  3. 上式の両辺に V^{-1}を掛けることで、固有値分解できる。
    • A=VΛV^{-1}
      • ある行列を別の3つの行列（2つ+1つの逆行列）に変換できた！

これが分かっていると特異値分解も理解しやすいです。

特異値分解とは

こちらでも先ほど挙げたYouTubeチャンネルの続編が分かりやすかったです。

特異値分解PART2：特異値分解 by 某处生活_LiveSomewhere

固有値分解の式を見ると、行列 Aは正方行列であることが条件だと気づきます。なぜなら、右辺の両端が Vと V^{-1}となっており、どちらも同じサイズの行列だからです。

このとき、自然な考えとして出てくる「 Aが正方行列でないときも似たようなことをしたい！」という要望に応えるのが特異値分解で、固有値分解とよく似た数式ですが少しだけ異なる以下の式で分解されます。

A=UΣV^{T}

※ ΣはYouTube動画に合わせた記法で、ゼロ作では Sで記載されています。後程のpython実装ではSで表します。

これで分解できる理由は動画を確認頂ければと思いますが、ポイントは以下です。

  1. Uと V^{T}の中身は固有値分解のときと同じでベクトルが詰まっています。
    • これらの中身のベクトルはそれぞれ Aの特異ベクトルと呼ばれ、区別をつけるために Uの各ベクトルは左特異ベクトル、 V^{T}の各ベクトルは右特異ベクトルとも呼ばれます。
      • Uと Vの中身の各ベクトルは単位ベクトルで、長さはすべて1です。

  2. Σの中身も固有値分解の時と同じでスカラーが対角に並んでおり、対角成分以外はすべて0の行列です。各スカラー (σ_{1}, σ_{2}, \cdots, σ_{n})を Aの特異値と呼びます。
    • (σ_{1}, σ_{2}, \cdots, σ_{n})は σ_{1}≥σ_{2}≥ \cdots≥ σ_{n}≥0の順に並んでいる必要があります。

Aは以下の様に展開ができ、こちらの方が特異値分解が次元削減に繋がる理由が分かりやすいです。

A=\vec{u_{1}}σ_{1}\vec{v_{1}}^{T}+\vec{u_{2}}σ_{2}\vec{v_{2}}^{T}+\cdots+\vec{u_{k}}σ_{k}\vec{k_{1}}^{T}+\vec{u_{k+1}}σ_{k+1}\vec{v_{k+1}}^{T}+\cdots+\vec{u_{m}}σ_{m}\vec{v_{m}}^{T}

\vec{u_{k}}と \vec{v_{k}}は単位ベクトルであり、 \vec{σ_{k}}は降順に並んでいるという前提から、左の方（添え字が小さい方）ほど値が大きい＝ Aの大きな部分を占める＝重要で、右の方ほど反対に重要度が低いことが分かります。 この性質を利用して、「重要度の低い右の方はある程度消してしまっても、おおよそ Aのことは説明できるから消しちゃっても良いよね」としてしまうことで、次元削減を実現するわけです。

Pythonでの実装

numpyのlinalgモジュールにあるsvdメソッドで実装できます。せっかくなので正方形でない行列に適用したいので、ゼロ作で適用する共起行列（7×7）から1行減らしたものに適用してみます。こちらのQiita記事を参考にさせて頂きました。

import numpy as np
from numpy.linalg import svd

# 7*6の行列を作成
C = np.array([[0, 1, 0, 0, 0, 0, 0],
              [1, 0, 1, 0, 1, 1, 0],
              [0, 1, 0, 1, 0, 0, 0],
              [0, 0, 1, 0, 1, 0, 0],
              [0, 1, 0, 1, 0, 0, 0],
              [0, 1, 0, 0, 0, 0, 1]])

# 特異値分解（UとSとV^Tに分解）
u,s,v = svd(C, full_matrices=False)

# u,s,vのshapeを見てみる
# C(6×7)を分解した数のはず
print("u:",u.shape," s:",s.shape," v:",v.shape)

# sの中身確認
# 降順に並んでいるはず
print(s.round(2))

# uとsとvを掛けたらCに戻るか確認
# sはnp.diagで対角行列に変換する必要あり
# @は行列積を求める記号
print((u @ np.diag(s) @ v).astype("int"))

実行結果が以下。

u: (6, 6)  s: (6,)  v: (6, 7)

[2.32 2.29 1.15 0.87 0.53 0.  ]

[[0 1 0 0 0 0 0]
 [1 0 1 0 1 1 0]
 [0 1 0 1 0 0 0]
 [0 0 0 0 0 0 0]
 [0 1 0 1 0 0 0]
 [0 1 0 0 0 0 1]]

期待通りの出力になっています。

最後に

以上、特異値分解についてまとめました。自然言語処理を入口に学びましたが、当然ながら画像処理等にも使える手法とのことです。またこの記事ではゼロ作の2.4.2～2.4.3節の内容にのみ触れましたが、以降の節ではnumpyのsvdよりも高速なsklearnのrandomized_svdなども使用されています。まだまだ発展がありそうですが、基本は抑えられた気がします。