【機械学習】社内輪講 Week8 〜教師なし学習: 特に固有値問題〜

13886 ワード
勉強会 coursera 機械学習 線形代数 勉強会 テキストリンク

はじめに

スタンフォード大学 Andrew Ng氏による機械学習の講義動画を各週社内メンバーで持ち回りで受講し、学んだことを発表、Qiitaで共有しています。

【機械学習】社内輪講はじめました -Qiita

これまでの講義内容

【機械学習】社内輪講 Week1 〜 線形単回帰 〜

【機械学習】社内輪講 Week2 〜線形重回帰〜

【機械学習】社内輪講 Week3 〜ロジスティック回帰・正規化〜

【機械学習】社内輪講 Week4 〜ニューラルネットワーク: 基本的な仕組み〜

[ 機械学習 ] 社内輪講 Week5 〜 ニューラルネットワーク: 誤差逆伝播法 〜

【機械学習】社内輪講 Week6 〜モデルの評価と改善〜

【機械学習】社内輪講 Week7 〜サポートベクターマシン〜

第4週は以下の内容でした。

  • Unsupervised Learning
  • Dimensionality Reduction

cousera講義の主題としては「教師なし学習」でその中の k-means法 と 主成分分析 について学びました。

関係性を図にするとこんな感じです。

ただし、本記事は「教師なし学習」についてではなく主に固有値問題について解説していきます。私自身、couseraを受講して k-means法 と 主成分分析 について利用用途や直観的イメージは理解出来たが、主成分分析の特に固有値問題について消化不良を起こしてしまったため、これを解消するための記事となります。k-means法 と 主成分分析 の詳しい解説は別の方の記事を紹介いたします。

k-means法: Qiita - k近傍法とk平均法の違いと詳細．
主成分分析: Qiita - 意味がわかる主成分分析

誰のための記事か

  • 主成分分析を利用するモチベーションはよくわかるが、数学的に何が起きているかわからない人向け
  • どう線形代数の勉強をすれば主成分分析にたどり着けるかわからない人向け

数学は元々得意でさくっと主成分分析を数学的に理解したいという方には不向きな記事です。

この記事のゴール

  • 主成分分析と固有値問題に軽く触れる
  • 主成分分析で使われる固有値問題理解のためのロードマップ紹介
  • そのロードマップをざっくりなぞり、固有値問題を解く

主成分分析とは

主成分分析とは、次元削減の手法の一つです。

  • 4次元以上のデータを可視化する
  • 計算コスト削減のため高次元データを圧縮する

このような時に活躍します。

主成分分析の手順は、

  • ある方向に射影したときのデータの分散を計算する = 分散共分散行列を求める
  • 分散が最大になるような方向を見つける = 分散共分散行列の固有値問題を解く

ふむ。よくわからん。

少なくとも、ある行列の固有値問題を解けばよいということがわかりました。

主成分分析が固有値問題に帰着することは aidemy の記事がたいへんわかりやすく解説しています。
https://blog.aidemy.net/entry/2017/10/19/222941

ただし、そもそも私のように「そもそも固有値問題ってなんじゃいな」という状態ではいまいち理解出来ません。ある程度固有値問題に対して歩み寄る必要があります。

固有値分解のロードマップ

固有値問題が線形代数の講義のどのあたりに位置付けられているかを確認しましょう。例えばwebで見つかるもので 武内修先生@筑波大 線形代数Ｉ をみてみると、だいぶ後半にあります。

  • 行列
  • 連立一次方程式
  • 行列の階数
  • 行列式
  • ベクトル空間と線形写像
  • 内積
  • 固有値と固有ベクトル ← ここ!!
  • 対角化（一般の場合）
  • 実対称行列の対角化

つまり、固有値問題を理解するためには線形代数の基礎知識がない初見状態ではだいぶ無謀ということがわかります。

私が線形代数の基礎を学ぶためにやったことは、

この後に aidemy のブログ 主成分分析と固有値問題を読むと、無事ちんぷんかんぷんから脱却出来ました。

ここから先、固有値問題のためのキーワードをまとめ、実際に固有値問題を解いていきます。固有値問題や線形代数に興味が湧いた方、より深く学びたい方はヨビノリと武内先生のページをのぞいてみてください。

キーワード

正方行列

A = \begin{bmatrix}
a & b & c & d \\
e & f & g & h \\
i & j & k & l \\
m & n & o & p \\
\end{bmatrix}

行列の縦横が同じ大きさの行列のこと。固有値問題は基本的に正方行列を扱う。

単位行列

I = \begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
\end{bmatrix}

対角成分が $1$ でそれ以外が $0$ の正方行列。この行列を掛けても元の行列は変化しない。実数における $1$ のようなもの。 $I$ や $E$ で表される。

対称行列

A = \begin{bmatrix}
a & b & c & d \\
b & f & g & h \\
c & g & k & l \\
d & h & l & p \\
\end{bmatrix}

$A^{T} = A$ を満たす正方行列(転置しても同じ行列になる)。対称行列は必ず固有値問題を解くことができる。ありがたいことに、主成分分析で固有値分解する分散共分散行列は対称行列。

ゼロ行列

\boldsymbol{0} = \begin{bmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{bmatrix}

成分が全てゼロの行列。この行列を掛けると元の行列もゼロ行列になる。

逆行列

ある行列 $A$ にもし、

AX = XA = I

という行列 $X$ がある場合、そのような $X$ はただ一つであり、逆行列と呼ぶ。実数における逆数に似ている。 $A^{-1}$ と表すこともある。逆行列が存在しない場合がある。

行列式

2次の正方行列 $A$ の行列式は

detA = \begin{vmatrix}
A
\end{vmatrix}\
= \begin{vmatrix}
a&b\\
c&d
\end{vmatrix}\ = ad - bc

行列式は行列の様々な特徴を表す重要な値になる。$n$次の行列式の一般化は割愛。

正則

  • 逆行列が存在すること
  • 行列式がゼロではないこと ($detA \neq 0$)

固有値問題を解く

行列Aとベクトルxの関係

ベクトル $\boldsymbol{x}$ と正方行列 $A$ の関係性を考える。

$A\boldsymbol{x}$は元のベクトル$\boldsymbol{x}$と同じ次元を持つが、必ずしも平行にはならない。つまり、

A\boldsymbol{x} \neq k\boldsymbol{x}

例）

A = \begin{bmatrix}
3 & 1 \\
1 & 3 \\
\end{bmatrix}
,\ 
\boldsymbol{x_1} = \begin{bmatrix}
2  \\
1  \\
\end{bmatrix}

であれば、

A\boldsymbol{x_1} = \begin{bmatrix}
7  \\
5  \\
\end{bmatrix} \neq k\boldsymbol{x_1}

しかし、$\boldsymbol{x}$ をうまく選ぶと $A\boldsymbol{x} = k\boldsymbol{x}$ になる場合がある。

\boldsymbol{x_2} = \begin{bmatrix}
1  \\
1  \\
\end{bmatrix},\ 
\boldsymbol{x_3} = \begin{bmatrix}
1  \\
-1  \\
\end{bmatrix}

のとき、

A\boldsymbol{x_2} = \begin{bmatrix}
4  \\
4  \\
\end{bmatrix} = 4\begin{bmatrix}
1  \\
1  \\
\end{bmatrix} = 4\boldsymbol{x_2},\ 
A\boldsymbol{x_3} = \begin{bmatrix}
2  \\
-2  \\
\end{bmatrix} = 2\begin{bmatrix}
1  \\
-1  \\
\end{bmatrix} = 2\boldsymbol{x_3}

固有値問題

このように、与えられた正方行列 $A$ に対して、 $\lambda, \boldsymbol{x}$ が

A\boldsymbol{x} = \lambda\boldsymbol{x}

を満たすとき、

  • $\lambda$ を $A$ の 固有値
  • $\boldsymbol{x}$ を $A$ の 固有ベクトル

と呼ぶ。

固有値問題とは、与えられた正方行列 $A$ に対して、 固有値と固有ベクトルを求める問題のことである。

一般に、１つの行列 $A$ は複数の固有値 $\lambda_1, \lambda_2, \cdots$ を持つ。
また、それぞれの固有値には、その固有値に属する固有ベクトルが存在する。すなわち固有値と固有ベクトルは必ずペアになっている。

固有値問題の解法

まず固有値を求める。

A\boldsymbol{x} = \lambda\boldsymbol{x}

が成り立つとすれば、これに単位行列 $I$ を掛けて

A\boldsymbol{x} = \lambda I \boldsymbol{x}

と書ける。すると、

A\boldsymbol{x} - \lambda I \boldsymbol{x} = (A - \lambda I) \boldsymbol{x} = \boldsymbol{0}

が成立しなければならない。
行列 $(A - \lambda I)$ が正則である場合、上式の左から逆行列を書けると、

(左辺) = (A - \lambda I)^{-1}(A - \lambda I) \boldsymbol{x} = \boldsymbol{x} \\
(右辺) = (A - \lambda I)^{-1} \boldsymbol{0} = \boldsymbol{0}

となり、 $\boldsymbol{x} = \boldsymbol{0}$ が導かれてしまう。
すなわち、ある $\lambda$ について行列 $(A - \lambda I)$ が 正則になったなら、その $\lambda$ に対して固有ベクトルは存在しない。
つまり、正則でなくなるための条件 $\left| A - \lambda I \right| = 0$ が固有ベクトルが存在するための必要条件になる。
この方程式は行列 $A$ の固有方程式と呼ばれる。

固有値問題の解放の手順をまとめる。

  • 固有方程式 $\left| A - \lambda I \right| = 0$ から固有値 $\lambda$ を求める
  • それぞれの $\lambda$ について $(A-\lambda I) \boldsymbol{x} = \boldsymbol{0}$ を解いて 固有ベクトル $\boldsymbol{x}$ を求める

固有値問題の具体例

A = \begin{bmatrix}
3 & 1  \\
1 & 3  \\
\end{bmatrix}

のとき、まず固有方程式を解いて固有値 $\lambda$ を求める。固有方程式は $\lambda$ の$n$次方程式に帰着する。

A - \lambda I = \begin{bmatrix}
3 & 1  \\
1 & 3  \\
\end{bmatrix} - \
\lambda\begin{bmatrix}
1 & 0  \\
0 & 1  \\
\end{bmatrix}\\
=\begin{bmatrix}
3 & 1  \\
1 & 3  \\
\end{bmatrix} - \begin{bmatrix}
\lambda & 0  \\
0 & \lambda  \\
\end{bmatrix}\\
= \begin{bmatrix}
3-\lambda & 1  \\
1 & 3-\lambda  \\
\end{bmatrix}

\begin{vmatrix}
A-\lambda I
\end{vmatrix}
=
\begin{vmatrix}
3-\lambda & 1  \\
1 & 3-\lambda  \\
\end{vmatrix}\\
= (3-\lambda)^{2}-1^2\\
=(3-\lambda+1)(3-\lambda-1)\\
=(4-\lambda)(2-\lambda)

\lambda = 2, 4

固有ベクトルは それぞれの $\lambda$ に対して個別に求める。

$\lambda = 2$ のとき、

(A - \lambda I)\boldsymbol{x} = \begin{bmatrix}
3−2 & 1  \\
1 & 3-2  \\
\end{bmatrix} \
\begin{bmatrix}
x   \\
y   \\
\end{bmatrix}
=\begin{bmatrix}
0   \\
0   \\
\end{bmatrix}

すなわち、連立方程式を解くことに帰着する。

  \begin{cases}
    x + y = 0 \\
    x + y = 0
  \end{cases}

$y=s$ とすると、 $x=-s$ になる。よって、

\boldsymbol{x} = \begin{bmatrix}
-s   \\
s   \\
\end{bmatrix} = \
s\begin{bmatrix}
-1   \\
1   \\
\end{bmatrix}

同様に、 $\lambda = 4$ のとき、

(A - \lambda I)\boldsymbol{x} = \begin{bmatrix}
3−4 & 1  \\
1 & 3-4  \\
\end{bmatrix} \
\begin{bmatrix}
x   \\
y   \\
\end{bmatrix}
=\begin{bmatrix}
0   \\
0   \\
\end{bmatrix}

  \begin{cases}
    -x + y = 0 \\
    x -y = 0
  \end{cases}

$y=t$ とすると、 $x=t$ になる。よって、

\boldsymbol{x} = \begin{bmatrix}
t   \\
t   \\
\end{bmatrix} = \
t\begin{bmatrix}
1   \\
1   \\
\end{bmatrix}

これで固有値と各固有ベクトルがもとまった。

まとめ

Coursera の Andrew Ng 先生の講義を元に、主成分分析、特に固有値問題について学びました。

次回、Coursera Machine Learning Week9 異常検知 について学んでいきます。